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
155
156
157
158
159
160
161
|
#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 elem {
ENTRY item;
size_t hash;
};
struct __tab {
struct elem *elems;
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;
struct elem *e, *newe;
struct elem *oldtab = htab->__tab->elems;
struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1;
if (nel > MAXSIZE)
nel = MAXSIZE;
for (newsize = MINSIZE; newsize < nel; newsize *= 2);
htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems);
if (!htab->__tab->elems) {
htab->__tab->elems = oldtab;
return 0;
}
htab->__tab->mask = newsize - 1;
if (!oldtab)
return 1;
for (e = oldtab; e < oldend; e++)
if (e->item.key) {
for (i=e->hash,j=1; ; i+=j++) {
newe = htab->__tab->elems + (i & htab->__tab->mask);
if (!newe->item.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 struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab)
{
size_t i, j;
struct elem *e;
for (i=hash,j=1; ; i+=j++) {
e = htab->__tab->elems + (i & htab->__tab->mask);
if (!e->item.key ||
(e->hash==hash && strcmp(e->item.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->elems);
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);
struct elem *e = lookup(item.key, hash, htab);
if (e->item.key) {
*retval = &e->item;
return 1;
}
if (action == FIND) {
*retval = 0;
return 0;
}
e->item = item;
e->hash = hash;
if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
if (!resize(2*htab->__tab->used, htab)) {
htab->__tab->used--;
e->item.key = 0;
*retval = 0;
return 0;
}
e = lookup(item.key, hash, htab);
}
*retval = &e->item;
return 1;
}
weak_alias(__hsearch_r, hsearch_r);
|
