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
| | #define _GNU_SOURCE
#include <stdlib.h>
#include <string.h>
#include <search.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;
static int __hcreate_r(size_t, struct hsearch_data *);
static void __hdestroy_r(struct hsearch_data *);
static 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;
size_t oldsize = htab->__tab->mask + 1;
ENTRY *e, *newe;
ENTRY *oldtab = htab->__tab->entries;
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 < oldtab + oldsize; 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;
}
static 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);
static 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);
static 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);
|