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