1 | #define _GNU_SOURCE
|
---|
2 | #include <stdlib.h>
|
---|
3 | #include <string.h>
|
---|
4 | #include <search.h>
|
---|
5 | #include "libc.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 | static struct hsearch_data htab;
|
---|
26 |
|
---|
27 | int __hcreate_r(size_t, struct hsearch_data *);
|
---|
28 | void __hdestroy_r(struct hsearch_data *);
|
---|
29 | int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
|
---|
30 |
|
---|
31 | static size_t keyhash(char *k)
|
---|
32 | {
|
---|
33 | unsigned char *p = (void *)k;
|
---|
34 | size_t h = 0;
|
---|
35 |
|
---|
36 | while (*p)
|
---|
37 | h = 31*h + *p++;
|
---|
38 | return h;
|
---|
39 | }
|
---|
40 |
|
---|
41 | static int resize(size_t nel, struct hsearch_data *htab)
|
---|
42 | {
|
---|
43 | size_t newsize;
|
---|
44 | size_t i, j;
|
---|
45 | ENTRY *e, *newe;
|
---|
46 | ENTRY *oldtab = htab->__tab->entries;
|
---|
47 | ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
|
---|
48 |
|
---|
49 | if (nel > MAXSIZE)
|
---|
50 | nel = MAXSIZE;
|
---|
51 | for (newsize = MINSIZE; newsize < nel; newsize *= 2);
|
---|
52 | htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
|
---|
53 | if (!htab->__tab->entries) {
|
---|
54 | htab->__tab->entries = oldtab;
|
---|
55 | return 0;
|
---|
56 | }
|
---|
57 | htab->__tab->mask = newsize - 1;
|
---|
58 | if (!oldtab)
|
---|
59 | return 1;
|
---|
60 | for (e = oldtab; e < oldend; e++)
|
---|
61 | if (e->key) {
|
---|
62 | for (i=keyhash(e->key),j=1; ; i+=j++) {
|
---|
63 | newe = htab->__tab->entries + (i & htab->__tab->mask);
|
---|
64 | if (!newe->key)
|
---|
65 | break;
|
---|
66 | }
|
---|
67 | *newe = *e;
|
---|
68 | }
|
---|
69 | free(oldtab);
|
---|
70 | return 1;
|
---|
71 | }
|
---|
72 |
|
---|
73 | int hcreate(size_t nel)
|
---|
74 | {
|
---|
75 | return __hcreate_r(nel, &htab);
|
---|
76 | }
|
---|
77 |
|
---|
78 | void hdestroy(void)
|
---|
79 | {
|
---|
80 | __hdestroy_r(&htab);
|
---|
81 | }
|
---|
82 |
|
---|
83 | static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
|
---|
84 | {
|
---|
85 | size_t i, j;
|
---|
86 | ENTRY *e;
|
---|
87 |
|
---|
88 | for (i=hash,j=1; ; i+=j++) {
|
---|
89 | e = htab->__tab->entries + (i & htab->__tab->mask);
|
---|
90 | if (!e->key || strcmp(e->key, key) == 0)
|
---|
91 | break;
|
---|
92 | }
|
---|
93 | return e;
|
---|
94 | }
|
---|
95 |
|
---|
96 | ENTRY *hsearch(ENTRY item, ACTION action)
|
---|
97 | {
|
---|
98 | ENTRY *e;
|
---|
99 |
|
---|
100 | __hsearch_r(item, action, &e, &htab);
|
---|
101 | return e;
|
---|
102 | }
|
---|
103 |
|
---|
104 | int __hcreate_r(size_t nel, struct hsearch_data *htab)
|
---|
105 | {
|
---|
106 | int r;
|
---|
107 |
|
---|
108 | htab->__tab = calloc(1, sizeof *htab->__tab);
|
---|
109 | if (!htab->__tab)
|
---|
110 | return 0;
|
---|
111 | r = resize(nel, htab);
|
---|
112 | if (r == 0) {
|
---|
113 | free(htab->__tab);
|
---|
114 | htab->__tab = 0;
|
---|
115 | }
|
---|
116 | return r;
|
---|
117 | }
|
---|
118 | weak_alias(__hcreate_r, hcreate_r);
|
---|
119 |
|
---|
120 | void __hdestroy_r(struct hsearch_data *htab)
|
---|
121 | {
|
---|
122 | if (htab->__tab) free(htab->__tab->entries);
|
---|
123 | free(htab->__tab);
|
---|
124 | htab->__tab = 0;
|
---|
125 | }
|
---|
126 | weak_alias(__hdestroy_r, hdestroy_r);
|
---|
127 |
|
---|
128 | int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
|
---|
129 | {
|
---|
130 | size_t hash = keyhash(item.key);
|
---|
131 | ENTRY *e = lookup(item.key, hash, htab);
|
---|
132 |
|
---|
133 | if (e->key) {
|
---|
134 | *retval = e;
|
---|
135 | return 1;
|
---|
136 | }
|
---|
137 | if (action == FIND) {
|
---|
138 | *retval = 0;
|
---|
139 | return 0;
|
---|
140 | }
|
---|
141 | *e = item;
|
---|
142 | if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
|
---|
143 | if (!resize(2*htab->__tab->used, htab)) {
|
---|
144 | htab->__tab->used--;
|
---|
145 | e->key = 0;
|
---|
146 | *retval = 0;
|
---|
147 | return 0;
|
---|
148 | }
|
---|
149 | e = lookup(item.key, hash, htab);
|
---|
150 | }
|
---|
151 | *retval = e;
|
---|
152 | return 1;
|
---|
153 | }
|
---|
154 | weak_alias(__hsearch_r, hsearch_r);
|
---|