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