1 #ifdef HAVE_CONFIG_H
2 #include "config.h"
3 #endif
4
5 #include <stdlib.h>
6 #include <string.h>
7 #include <stddef.h>
8 #include <inttypes.h>
9 #ifdef HAVE_SYS_MMAN_H
10 #include <sys/mman.h>
11 #endif
12
13 #include "glue.h"
14 #include "massert.h"
15
16
17 // LOHASH_BITS - number of bits in low order hash tabble
18 // ENTRY_TYPE - type of record stored in hash map
19 // GLUE_FN_NAME_PREFIX - prefix of function names
20 // HASH_ARGS_TYPE_LIST - list of find function arguments with types
21 // HASH_ARGS_LIST - list of find function arguments (also hash function)
22 // GLUE_HASH_TAB_PREFIX - prefix of hash tab name
23
24
25 // #define LOHASH_BITS 20
26 // #define ENTRY_TYPE void
27 // #define FN_NAME_PREFIX dict
28 // #define HASH_ARGS_TYPE_LIST const uint8_t *data,uint32_t leng
29 // #define HASH_ARGS_LIST data,leng
30 // #define HASH_TAB_PREFIX dict
31 // #define HASH_VALUE_FIELD hashval
32
33 #if defined(HASH_TAB_PREFIX) && !defined(GLUE_HASH_TAB_PREFIX)
34 #define GLUE_HASH_TAB_PREFIX(NAME) GLUE(HASH_TAB_PREFIX,NAME)
35 #endif
36
37 #if defined(FN_NAME_PREFIX) && !defined(GLUE_FN_NAME_PREFIX)
38 #define GLUE_FN_NAME_PREFIX(NAME) GLUE(FN_NAME_PREFIX,NAME)
39 #endif
40
41 #ifndef LOHASH_BITS
42 #define LOHASH_BITS 20
43 #endif
44
45 #ifndef ENTRY_TYPE
46 typedef struct _inthash {
47 uint32_t value;
48 struct _inthash *next;
49 } inthash;
50 #define ENTRY_TYPE inthash
51
52 #define GLUE_HELPER(X,Y) X##Y
53 #define GLUE(X,Y) GLUE_HELPER(X,Y)
54
55 #define GLUE_FN_NAME_PREFIX(Y) GLUE(inthash,Y)
56 #define HASH_ARGS_TYPE_LIST uint32_t value
57 #define HASH_ARGS_LIST value
58 #define GLUE_HASH_TAB_PREFIX(Y) GLUE(inthash,Y)
59
60
GLUE_FN_NAME_PREFIX(_cmp)61 static inline int GLUE_FN_NAME_PREFIX(_cmp)(ENTRY_TYPE *e,HASH_ARGS_TYPE_LIST) {
62 return (e->value==value);
63 }
64
GLUE_FN_NAME_PREFIX(_hash)65 static inline uint32_t GLUE_FN_NAME_PREFIX(_hash)(HASH_ARGS_TYPE_LIST) {
66 return value;
67 }
68
GLUE_FN_NAME_PREFIX(_ehash)69 static inline uint32_t GLUE_FN_NAME_PREFIX(_ehash)(ENTRY_TYPE *e) {
70 return e->value;
71 }
72 #endif
73
74
75 #define HASHTAB_LOBITS LOHASH_BITS
76 #define HASHTAB_HISIZE (0x80000000>>(HASHTAB_LOBITS))
77 #define HASHTAB_LOSIZE (1<<HASHTAB_LOBITS)
78 #define HASHTAB_MASK (HASHTAB_LOSIZE-1)
79
80 #ifndef HASHTAB_MOVEFACTOR
81 #define HASHTAB_MOVEFACTOR 5
82 #endif
83
84 #define HASHTAB_SIZEHINT 0
85
86 static ENTRY_TYPE **GLUE_HASH_TAB_PREFIX(hashtab) [HASHTAB_HISIZE];
87 static uint32_t GLUE_HASH_TAB_PREFIX(rehashpos);
88 static uint32_t GLUE_HASH_TAB_PREFIX(hashsize);
89 static uint32_t GLUE_HASH_TAB_PREFIX(hashelem);
90
91
92 /* internals */
93
GLUE_FN_NAME_PREFIX(_calc_hash_size)94 static inline uint32_t GLUE_FN_NAME_PREFIX(_calc_hash_size)(uint32_t elements) {
95 uint32_t res=1;
96 while (elements) {
97 elements>>=1;
98 res<<=1;
99 }
100 if (res==0) {
101 res = UINT32_C(0x80000000);
102 }
103 if (res<HASHTAB_LOSIZE) {
104 return HASHTAB_LOSIZE;
105 }
106 return res;
107 }
108
GLUE_FN_NAME_PREFIX(_hash_init)109 static inline void GLUE_FN_NAME_PREFIX(_hash_init)(void) {
110 uint16_t i;
111 GLUE_HASH_TAB_PREFIX(hashsize) = 0;
112 GLUE_HASH_TAB_PREFIX(hashelem) = 0;
113 GLUE_HASH_TAB_PREFIX(rehashpos) = 0;
114 for (i=0 ; i<HASHTAB_HISIZE ; i++) {
115 GLUE_HASH_TAB_PREFIX(hashtab)[i] = NULL;
116 }
117 }
118
GLUE_FN_NAME_PREFIX(_hash_cleanup)119 static inline void GLUE_FN_NAME_PREFIX(_hash_cleanup)(void) {
120 uint16_t i;
121 uint32_t j;
122 GLUE_HASH_TAB_PREFIX(hashelem) = 0;
123 GLUE_HASH_TAB_PREFIX(hashsize) = 0;
124 GLUE_HASH_TAB_PREFIX(rehashpos) = 0;
125 for (i=0 ; i<HASHTAB_HISIZE ; i++) {
126 if (GLUE_HASH_TAB_PREFIX(hashtab)[i]!=NULL) {
127 for (j=0 ; j<HASHTAB_LOSIZE ; j++) {
128 massert(GLUE_HASH_TAB_PREFIX(hashtab)[i][j]==NULL,"hash map has elements during clean up");
129 }
130 #ifdef HAVE_MMAP
131 munmap(GLUE_HASH_TAB_PREFIX(hashtab)[i],sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE);
132 #else
133 free(GLUE_HASH_TAB_PREFIX(hashtab)[i]);
134 #endif
135 }
136 GLUE_HASH_TAB_PREFIX(hashtab)[i] = NULL;
137 }
138 }
139
GLUE_FN_NAME_PREFIX(_hash_move)140 static inline void GLUE_FN_NAME_PREFIX(_hash_move)(void) {
141 uint32_t hash;
142 uint32_t mask;
143 uint32_t moved=0;
144 ENTRY_TYPE **ehptr,**ehptralt,*e;
145 mask = GLUE_HASH_TAB_PREFIX(hashsize)-1;
146 do {
147 if (GLUE_HASH_TAB_PREFIX(rehashpos)>=GLUE_HASH_TAB_PREFIX(hashsize)) { // rehash complete
148 GLUE_HASH_TAB_PREFIX(rehashpos) = GLUE_HASH_TAB_PREFIX(hashsize);
149 return;
150 }
151 if (GLUE_HASH_TAB_PREFIX(hashtab)[GLUE_HASH_TAB_PREFIX(rehashpos) >> HASHTAB_LOBITS]==NULL) {
152 #ifdef HAVE_MMAP
153 GLUE_HASH_TAB_PREFIX(hashtab)[GLUE_HASH_TAB_PREFIX(rehashpos) >> HASHTAB_LOBITS] = mmap(NULL,sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE,PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE,-1,0);
154 #else
155 GLUE_HASH_TAB_PREFIX(hashtab)[GLUE_HASH_TAB_PREFIX(rehashpos) >> HASHTAB_LOBITS] = malloc(sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE);
156 #endif
157 passert(GLUE_HASH_TAB_PREFIX(hashtab)[GLUE_HASH_TAB_PREFIX(rehashpos) >> HASHTAB_LOBITS]);
158 }
159 ehptr = GLUE_HASH_TAB_PREFIX(hashtab)[(GLUE_HASH_TAB_PREFIX(rehashpos) - (GLUE_HASH_TAB_PREFIX(hashsize)/2)) >> HASHTAB_LOBITS] + (GLUE_HASH_TAB_PREFIX(rehashpos) & HASHTAB_MASK);
160 ehptralt = GLUE_HASH_TAB_PREFIX(hashtab)[GLUE_HASH_TAB_PREFIX(rehashpos) >> HASHTAB_LOBITS] + (GLUE_HASH_TAB_PREFIX(rehashpos) & HASHTAB_MASK);
161 *ehptralt = NULL;
162 while ((e=*ehptr)!=NULL) {
163 #ifdef HASH_VALUE_FIELD
164 hash = e->HASH_VALUE_FIELD & mask;
165 #else
166 hash = GLUE_FN_NAME_PREFIX(_ehash)(e) & mask;
167 #endif
168 if (hash==GLUE_HASH_TAB_PREFIX(rehashpos)) {
169 *ehptralt = e;
170 *ehptr = e->next;
171 ehptralt = &(e->next);
172 e->next = NULL;
173 } else {
174 ehptr = &(e->next);
175 }
176 moved++;
177 }
178 GLUE_HASH_TAB_PREFIX(rehashpos)++;
179 } while (moved<HASHTAB_MOVEFACTOR);
180 }
181
GLUE_FN_NAME_PREFIX(_find)182 static inline ENTRY_TYPE* GLUE_FN_NAME_PREFIX(_find)(HASH_ARGS_TYPE_LIST) {
183 ENTRY_TYPE *e;
184 uint32_t hash;
185 uint32_t hashval;
186
187 if (GLUE_HASH_TAB_PREFIX(hashsize)==0) {
188 return NULL;
189 }
190 hashval = GLUE_FN_NAME_PREFIX(_hash)(HASH_ARGS_LIST);
191 hash = hashval & (GLUE_HASH_TAB_PREFIX(hashsize)-1);
192 if (GLUE_HASH_TAB_PREFIX(rehashpos)<GLUE_HASH_TAB_PREFIX(hashsize)) {
193 GLUE_FN_NAME_PREFIX(_hash_move)();
194 if (hash >= GLUE_HASH_TAB_PREFIX(rehashpos)) {
195 hash -= GLUE_HASH_TAB_PREFIX(hashsize)/2;
196 }
197 }
198 for (e=GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS][hash&HASHTAB_MASK] ; e ; e=e->next) {
199 #ifdef HASH_VALUE_FIELD
200 if (e->HASH_VALUE_FIELD==hashval && GLUE_FN_NAME_PREFIX(_cmp)(e,HASH_ARGS_LIST)) {
201 #else
202 if (GLUE_FN_NAME_PREFIX(_cmp)(e,HASH_ARGS_LIST)) {
203 #endif
204 return e;
205 }
206 }
207 return NULL;
208 }
209
210 static inline uint8_t GLUE_FN_NAME_PREFIX(_delete)(ENTRY_TYPE *e) {
211 ENTRY_TYPE **ehptr,*eit;
212 uint32_t hash;
213
214 if (GLUE_HASH_TAB_PREFIX(hashsize)==0) {
215 return 0;
216 }
217 #ifdef HASH_VALUE_FIELD
218 hash = (e->HASH_VALUE_FIELD) & (GLUE_HASH_TAB_PREFIX(hashsize)-1);
219 #else
220 hash = GLUE_FN_NAME_PREFIX(_ehash)(e) & (GLUE_HASH_TAB_PREFIX(hashsize)-1);
221 #endif
222 if (GLUE_HASH_TAB_PREFIX(rehashpos)<GLUE_HASH_TAB_PREFIX(hashsize)) {
223 GLUE_FN_NAME_PREFIX(_hash_move)();
224 if (hash >= GLUE_HASH_TAB_PREFIX(rehashpos)) {
225 hash -= GLUE_HASH_TAB_PREFIX(hashsize)/2;
226 }
227 }
228 ehptr = GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS] + (hash&HASHTAB_MASK);
229 while ((eit=*ehptr)!=NULL) {
230 if (eit==e) {
231 *ehptr = e->next;
232 GLUE_HASH_TAB_PREFIX(hashelem)--;
233 return 1;
234 }
235 ehptr = &(eit->next);
236 }
237 return 0;
238 }
239
240 static inline void GLUE_FN_NAME_PREFIX(_add)(ENTRY_TYPE *e) {
241 uint16_t i;
242 uint32_t hash;
243
244 if (GLUE_HASH_TAB_PREFIX(hashsize)==0) {
245 GLUE_HASH_TAB_PREFIX(hashsize) = GLUE_FN_NAME_PREFIX(_calc_hash_size)(HASHTAB_SIZEHINT);
246 GLUE_HASH_TAB_PREFIX(rehashpos) = GLUE_HASH_TAB_PREFIX(hashsize);
247 GLUE_HASH_TAB_PREFIX(hashelem) = 0;
248 for (i=0 ; i<GLUE_HASH_TAB_PREFIX(hashsize)>>HASHTAB_LOBITS ; i++) {
249 #ifdef HAVE_MMAP
250 GLUE_HASH_TAB_PREFIX(hashtab)[i] = mmap(NULL,sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE,PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE,-1,0);
251 #else
252 GLUE_HASH_TAB_PREFIX(hashtab)[i] = malloc(sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE);
253 #endif
254 passert(GLUE_HASH_TAB_PREFIX(hashtab)[i]);
255 memset(GLUE_HASH_TAB_PREFIX(hashtab)[i],0,sizeof(ENTRY_TYPE*));
256 if (GLUE_HASH_TAB_PREFIX(hashtab)[i][0]==NULL) {
257 memset(GLUE_HASH_TAB_PREFIX(hashtab)[i],0,sizeof(ENTRY_TYPE*)*HASHTAB_LOSIZE);
258 } else {
259 for (hash=0 ; hash<HASHTAB_LOSIZE ; hash++) {
260 GLUE_HASH_TAB_PREFIX(hashtab)[i][hash] = NULL;
261 }
262 }
263 }
264 }
265 #ifdef HASH_VALUE_FIELD
266 e->HASH_VALUE_FIELD = GLUE_FN_NAME_PREFIX(_hash)(e->data,e->leng);
267 hash = (e->HASH_VALUE_FIELD) & (GLUE_HASH_TAB_PREFIX(hashsize)-1);
268 #else
269 hash = GLUE_FN_NAME_PREFIX(_ehash)(e) & (GLUE_HASH_TAB_PREFIX(hashsize)-1);
270 #endif
271 if (GLUE_HASH_TAB_PREFIX(rehashpos)<GLUE_HASH_TAB_PREFIX(hashsize)) {
272 GLUE_FN_NAME_PREFIX(_hash_move)();
273 if (hash >= GLUE_HASH_TAB_PREFIX(rehashpos)) {
274 hash -= GLUE_HASH_TAB_PREFIX(hashsize)/2;
275 }
276 e->next = GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS][hash&HASHTAB_MASK];
277 GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS][hash&HASHTAB_MASK] = e;
278 GLUE_HASH_TAB_PREFIX(hashelem)++;
279 } else {
280 e->next = GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS][hash&HASHTAB_MASK];
281 GLUE_HASH_TAB_PREFIX(hashtab)[hash>>HASHTAB_LOBITS][hash&HASHTAB_MASK] = e;
282 GLUE_HASH_TAB_PREFIX(hashelem)++;
283 if (GLUE_HASH_TAB_PREFIX(hashelem)>GLUE_HASH_TAB_PREFIX(hashsize) && (GLUE_HASH_TAB_PREFIX(hashsize)>>HASHTAB_LOBITS)<HASHTAB_HISIZE) {
284 GLUE_HASH_TAB_PREFIX(rehashpos) = GLUE_HASH_TAB_PREFIX(hashsize);
285 GLUE_HASH_TAB_PREFIX(hashsize) *= 2;
286 }
287 }
288 }
289