Loading...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | #define _GNU_SOURCE
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include "libc.h"
/*
open addressing hash table with 2^n table size
quadratic probing is used in case of hash collision
tab indices and hash are size_t
after resize fails with ENOMEM the state of tab is still usable
with the posix api items cannot be iterated and length cannot be queried
*/
#define MINSIZE 8
#define MAXSIZE ((size_t)-1/2 + 1)
struct __tab {
ENTRY *entries;
size_t mask;
size_t used;
};
static struct hsearch_data htab;
int __hcreate_r(size_t, struct hsearch_data *);
void __hdestroy_r(struct hsearch_data *);
int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
static size_t keyhash(char *k)
{
unsigned char *p = (void *)k;
size_t h = 0;
while (*p)
h = 31*h + *p++;
return h;
}
static int resize(size_t nel, struct hsearch_data *htab)
{
size_t newsize;
size_t i, j;
ENTRY *e, *newe;
ENTRY *oldtab = htab->__tab->entries;
ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
if (nel > MAXSIZE)
nel = MAXSIZE;
for (newsize = MINSIZE; newsize < nel; newsize *= 2);
htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
if (!htab->__tab->entries) {
htab->__tab->entries = oldtab;
return 0;
}
htab->__tab->mask = newsize - 1;
if (!oldtab)
return 1;
for (e = oldtab; e < oldend; e++)
if (e->key) {
for (i=keyhash(e->key),j=1; ; i+=j++) {
newe = htab->__tab->entries + (i & htab->__tab->mask);
if (!newe->key)
break;
}
*newe = *e;
}
free(oldtab);
return 1;
}
int hcreate(size_t nel)
{
return __hcreate_r(nel, &htab);
}
void hdestroy(void)
{
__hdestroy_r(&htab);
}
static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
{
size_t i, j;
ENTRY *e;
for (i=hash,j=1; ; i+=j++) {
e = htab->__tab->entries + (i & htab->__tab->mask);
if (!e->key || strcmp(e->key, key) == 0)
break;
}
return e;
}
ENTRY *hsearch(ENTRY item, ACTION action)
{
ENTRY *e;
__hsearch_r(item, action, &e, &htab);
return e;
}
int __hcreate_r(size_t nel, struct hsearch_data *htab)
{
int r;
htab->__tab = calloc(1, sizeof *htab->__tab);
if (!htab->__tab)
return 0;
r = resize(nel, htab);
if (r == 0) {
free(htab->__tab);
htab->__tab = 0;
}
return r;
}
weak_alias(__hcreate_r, hcreate_r);
void __hdestroy_r(struct hsearch_data *htab)
{
if (htab->__tab) free(htab->__tab->entries);
free(htab->__tab);
htab->__tab = 0;
}
weak_alias(__hdestroy_r, hdestroy_r);
int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
{
size_t hash = keyhash(item.key);
ENTRY *e = lookup(item.key, hash, htab);
if (e->key) {
*retval = e;
return 1;
}
if (action == FIND) {
*retval = 0;
return 0;
}
*e = item;
if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
if (!resize(2*htab->__tab->used, htab)) {
htab->__tab->used--;
e->key = 0;
*retval = 0;
return 0;
}
e = lookup(item.key, hash, htab);
}
*retval = e;
return 1;
}
weak_alias(__hsearch_r, hsearch_r);
|