Mercurial > hg > xemacs-beta

comparison src/hash.c @ 380:8626e4521993 r21-2-5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-5
author cvs
date Mon, 13 Aug 2007 11:07:10 +0200
parents c5d627a313b1
children 7d59cb494b73
comparison
equal deleted inserted replaced
379:76b7d63099ad 380:8626e4521993
31 #define NULL_ENTRY ((void *) 1) 31 #define NULL_ENTRY ((void *) 1)
32 32
33 #endif /* !emacs */ 33 #endif /* !emacs */
34 34
35 #include "hash.h" 35 #include "hash.h"
36 #include "elhash.h" 36
37 37 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
38 static CONST unsigned int 38
39 primes []={ 39 /* Knuth volume 3, hash functions */
40 #define WORD_HASH_4(word) (0x9c406b55 * (word))
41 #define WORD_HASH_8(word) (0x9c406b549c406b55 * (word))
42
43 static CONST hash_size_t
44 primes [] =
45 {
40 13, 46 13,
41 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 47 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,
42 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 48 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
43 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 49 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361,
44 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 50 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449,
45 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 51 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
46 2009191, 2411033, 2893249 52 2009191, 2411033, 2893249
47 }; 53 };
48 54
49 /* strings code */ 55 #if 0
50 56 static CONST hash_size_t
51 /* from base/generic-hash.cc, and hence from Dragon book, p436 */ 57 primes [] =
58 {
59 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, 1361,
60 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 19219, 24989,
61 32491, 42257, 54941, 71429, 92861, 120721, 156941, 204047, 265271,
62 344857, 448321, 582821, 757693, 985003, 1280519, 1664681, 2164111,
63 2813353, 3657361, 4754591, 6180989, 8035301, 10445899, 13579681,
64 17653589, 22949669, 29834603, 38784989, 50420551, 65546729, 85210757,
65 110774011, 144006217, 187208107, 243370577, 316381771, 411296309,
66 534685237, 695090819, 903618083, 1174703521, 1527114613, 1985248999,
67 2580823717, 3355070839, 4361592119
68 };
69 #endif
70
52 unsigned long 71 unsigned long
53 string_hash (CONST void *xv) 72 memory_hash (CONST void *xv, size_t size)
54 { 73 {
55 unsigned int h = 0; 74 unsigned int h = 0;
56 unsigned CONST char *x = (unsigned CONST char *) xv; 75 unsigned CONST char *x = (unsigned CONST char *) xv;
57 76
58 if (!x) return 0; 77 if (!x) return 0;
59 78
60 while (*x != 0) 79 while (size--)
61 { 80 {
62 unsigned int g; 81 unsigned int g;
63 h = (h << 4) + *x++; 82 h = (h << 4) + *x++;
64 if ((g = h & 0xf0000000) != 0) 83 if ((g = h & 0xf0000000) != 0)
65 h = (h ^ (g >> 24)) ^ g; 84 h = (h ^ (g >> 24)) ^ g;
66 } 85 }
67 86
68 return h; 87 return h;
69 } 88 }
70 89
90 /* We've heard of binary search. */
91 static hash_size_t
92 prime_size (hash_size_t size)
93 {
94 int low, high;
95 for (low = 0, high = countof (primes) - 1; high - low > 1;)
96 {
97 /* Loop Invariant: size < primes [high] */
98 int mid = (low + high) / 2;
99 if (primes [mid] < size)
100 low = mid;
101 else
102 high = mid;
103 }
104 return primes [high];
105 }
106
107 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
108
109 #define KEYS_DIFFER_P(old, new, testfun) \
110 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
111
112 CONST void *
113 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value)
114 {
115 hentry *harray = hash_table->harray;
116 hash_table_test_function test_function = hash_table->test_function;
117 hash_size_t size = hash_table->size;
118 unsigned int hcode_initial =
119 hash_table->hash_function ?
120 hash_table->hash_function (key) :
121 (unsigned long) key;
122 unsigned int hcode = hcode_initial % size;
123 hentry *e = &harray [hcode];
124 CONST void *e_key = e->key;
125
126 if (!key)
127 {
128 *ret_value = hash_table->zero_entry;
129 return (void *) hash_table->zero_set;
130 }
131
132 if (e_key ?
133 KEYS_DIFFER_P (e_key, key, test_function) :
134 e->contents == NULL_ENTRY)
135 {
136 size_t h2 = size - 2;
137 unsigned int incr = 1 + (hcode_initial % h2);
138 do
139 {
140 hcode += incr; if (hcode >= size) hcode -= size;
141 e = &harray [hcode];
142 e_key = e->key;
143 }
144 while (e_key ?
145 KEYS_DIFFER_P (e_key, key, test_function) :
146 e->contents == NULL_ENTRY);
147 }
148
149 *ret_value = e->contents;
150 return e->key;
151 }
152
153 void
154 clrhash (struct hash_table *hash_table)
155 {
156 memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
157 hash_table->zero_entry = 0;
158 hash_table->zero_set = 0;
159 hash_table->fullness = 0;
160 }
161
162 void
163 free_hash_table (struct hash_table *hash_table)
164 {
165 xfree (hash_table->harray);
166 xfree (hash_table);
167 }
168
169 struct hash_table*
170 make_hash_table (hash_size_t size)
171 {
172 struct hash_table *hash_table = xnew_and_zero (struct hash_table);
173 hash_table->size = prime_size (COMFORTABLE_SIZE (size));
174 hash_table->harray = xnew_array (hentry, hash_table->size);
175 clrhash (hash_table);
176 return hash_table;
177 }
178
179 struct hash_table *
180 make_general_hash_table (hash_size_t size,
181 hash_table_hash_function hash_function,
182 hash_table_test_function test_function)
183 {
184 struct hash_table* hash_table = make_hash_table (size);
185 hash_table->hash_function = hash_function;
186 hash_table->test_function = test_function;
187 return hash_table;
188 }
189
190 #if 0 /* unused strings code */
191 struct hash_table *
192 make_strings_hash_table (hash_size_t size)
193 {
194 return make_general_hash_table (size, string_hash, string_eq);
195 }
196
197 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
71 unsigned long 198 unsigned long
72 memory_hash (CONST void *xv, size_t size) 199 string_hash (CONST void *xv)
73 { 200 {
74 unsigned int h = 0; 201 unsigned int h = 0;
75 unsigned CONST char *x = (unsigned CONST char *) xv; 202 unsigned CONST char *x = (unsigned CONST char *) xv;
76 203
77 if (!x) return 0; 204 if (!x) return 0;
78 205
79 while (size > 0) 206 while (*x != 0)
80 { 207 {
81 unsigned int g; 208 unsigned int g;
82 h = (h << 4) + *x++; 209 h = (h << 4) + *x++;
83 if ((g = h & 0xf0000000) != 0) 210 if ((g = h & 0xf0000000) != 0)
84 h = (h ^ (g >> 24)) ^ g; 211 h = (h ^ (g >> 24)) ^ g;
85 size--;
86 } 212 }
87 213
88 return h; 214 return h;
89 } 215 }
90 216
91 static int 217 static int
92 string_eq (CONST void *st1, CONST void *st2) 218 string_eq (CONST void *s1, CONST void *s2)
93 { 219 {
94 if (!st1) 220 return s1 && s2 ? !strcmp ((CONST char *) s1, (CONST char *) s2) : s1 == s2;
95 return st2 ? 0 : 1; 221 }
96 else if (!st2) 222 #endif /* unused strings code */
97 return 0; 223
98 else 224 void
99 return !strcmp ( (CONST char *) st1, (CONST char *) st2); 225 copy_hash (struct hash_table *dest, struct hash_table *src)
100 } 226 {
101
102
103 /* ### Ever heard of binary search? */
104 static unsigned int
105 prime_size (unsigned int size)
106 {
107 int i;
108 for (i = 0; i < countof (primes); i++)
109 if (size <= primes [i])
110 return primes [i];
111 return primes [countof (primes) - 1];
112 }
113
114 static void rehash (hentry *harray, c_hashtable ht, unsigned int size);
115
116 #define KEYS_DIFFER_P(old, new, testfun) \
117 ((testfun)?(((old) == (new))?0:(!(testfun ((old), new)))):((old) != (new)))
118
119 CONST void *
120 gethash (CONST void *key, c_hashtable hash, CONST void **ret_value)
121 {
122 hentry *harray = hash->harray;
123 int (*test_function) (CONST void *, CONST void *) = hash->test_function;
124 unsigned int hsize = hash->size;
125 unsigned int hcode_initial =
126 (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
127 unsigned int hcode = hcode_initial % hsize;
128 hentry *e = &harray [hcode];
129 CONST void *e_key = e->key;
130
131 if (!key)
132 {
133 *ret_value = hash->zero_entry;
134 return (void *) hash->zero_set;
135 }
136
137 if ((e_key)?
138 (KEYS_DIFFER_P (e_key, key, test_function)):
139 (e->contents == NULL_ENTRY))
140 {
141 unsigned int h2 = hsize - 2;
142 unsigned int incr = 1 + (hcode_initial % h2);
143 do
144 {
145 hcode = hcode + incr;
146 if (hcode >= hsize) hcode = hcode - hsize;
147 e = &harray [hcode];
148 e_key = e->key;
149 }
150 while ((e_key)?
151 (KEYS_DIFFER_P (e_key, key, test_function)):
152 (e->contents == NULL_ENTRY));
153 }
154
155 *ret_value = e->contents;
156 return e->key;
157 }
158
159 void
160 clrhash (c_hashtable hash)
161 {
162 memset (hash->harray, 0, sizeof (hentry) * hash->size);
163 hash->zero_entry = 0;
164 hash->zero_set = 0;
165 hash->fullness = 0;
166 }
167
168 void
169 free_hashtable (c_hashtable hash)
170 {
171 #ifdef emacs
172 if (!NILP (hash->elisp_table))
173 return;
174 #endif
175 xfree (hash->harray);
176 xfree (hash);
177 }
178
179 c_hashtable
180 make_hashtable (unsigned int hsize)
181 {
182 c_hashtable res = xnew_and_zero (struct _C_hashtable);
183 res->size = prime_size ((13 * hsize) / 10);
184 res->harray = xnew_array (hentry, res->size);
185 #ifdef emacs
186 res->elisp_table = Qnil;
187 #endif
188 clrhash (res);
189 return res;
190 }
191
192 c_hashtable
193 make_general_hashtable (unsigned int hsize,
194 unsigned long (*hash_function) (CONST void *),
195 int (*test_function) (CONST void *, CONST void *))
196 {
197 c_hashtable res = xnew_and_zero (struct _C_hashtable);
198 res->size = prime_size ((13 * hsize) / 10);
199 res->harray = xnew_array (hentry, res->size);
200 res->hash_function = hash_function;
201 res->test_function = test_function;
202 #ifdef emacs
203 res->elisp_table = Qnil;
204 #endif
205 clrhash (res);
206 return res;
207 }
208
209 c_hashtable
210 make_strings_hashtable (unsigned int hsize)
211 {
212 return make_general_hashtable (hsize, string_hash, string_eq);
213 }
214
215 #ifdef emacs
216 unsigned int
217 compute_harray_size (unsigned int hsize)
218 {
219 return prime_size ((13 * hsize) / 10);
220 }
221 #endif
222
223 void
224 copy_hash (c_hashtable dest, c_hashtable src)
225 {
226 #ifdef emacs
227 /* if these are not the same, then we are losing here */
228 if ((NILP (dest->elisp_table)) != (NILP (src->elisp_table)))
229 {
230 error ("Incompatible hashtable types to copy_hash.");
231 return;
232 }
233 #endif
234
235 if (dest->size != src->size) 227 if (dest->size != src->size)
236 { 228 {
237 #ifdef emacs 229 xfree (dest->harray);
238 if (!NILP (dest->elisp_table))
239 elisp_hvector_free (dest->harray, dest->elisp_table);
240 else
241 #endif
242 xfree (dest->harray);
243 230
244 dest->size = src->size; 231 dest->size = src->size;
245 #ifdef emacs 232 dest->harray = xnew_array (hentry, dest->size);
246 if (!NILP (dest->elisp_table)) 233 }
247 dest->harray = (hentry *) 234 dest->fullness = src->fullness;
248 elisp_hvector_malloc (sizeof (hentry) * dest->size, 235 dest->zero_entry = src->zero_entry;
249 dest->elisp_table); 236 dest->zero_set = src->zero_set;
250 else
251 #endif
252 dest->harray = xnew_array (hentry, dest->size);
253 }
254 dest->fullness = src->fullness;
255 dest->zero_entry = src->zero_entry;
256 dest->zero_set = src->zero_set;
257 dest->hash_function = src->hash_function; 237 dest->hash_function = src->hash_function;
258 dest->test_function = src->test_function; 238 dest->test_function = src->test_function;
259 memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size); 239 memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
260 } 240 }
261 241
262 static void 242 static void
263 grow_hashtable (c_hashtable hash, unsigned int new_size) 243 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
264 { 244 {
265 unsigned int old_hsize = hash->size; 245 hash_size_t old_size = hash_table->size;
266 hentry *old_harray = hash->harray; 246 hentry *old_harray = hash_table->harray;
267 unsigned int new_hsize = prime_size (new_size); 247 hentry *new_harray;
268 hentry *new_harray; 248
269 249 new_size = prime_size (new_size);
270 #ifdef emacs 250
271 /* We test for Qzero to facilitate free-hook.c. That module creates 251 new_harray = xnew_array (hentry, new_size);
272 a hashtable very very early, at which point Qnil has not yet 252
273 been set and is thus all zeroes. Qzero is "automatically" 253 hash_table->size = new_size;
274 initialized at startup because its correct value is also all 254 hash_table->harray = new_harray;
275 zeroes. */
276 if (!EQ (hash->elisp_table, Qnull_pointer) &&
277 !NILP (hash->elisp_table) &&
278 !ZEROP (hash->elisp_table))
279 new_harray = (hentry *) elisp_hvector_malloc (sizeof (hentry) * new_hsize,
280 hash->elisp_table);
281 else
282 #endif
283 new_harray = (hentry *) xmalloc (sizeof (hentry) * new_hsize);
284
285 hash->size = new_hsize;
286 hash->harray = new_harray;
287 255
288 /* do the rehash on the "grown" table */ 256 /* do the rehash on the "grown" table */
289 { 257 {
290 long old_zero_set = hash->zero_set; 258 long old_zero_set = hash_table->zero_set;
291 void *old_zero_entry = hash->zero_entry; 259 void *old_zero_entry = hash_table->zero_entry;
292 clrhash (hash); 260 clrhash (hash_table);
293 hash->zero_set = old_zero_set; 261 hash_table->zero_set = old_zero_set;
294 hash->zero_entry = old_zero_entry; 262 hash_table->zero_entry = old_zero_entry;
295 rehash (old_harray, hash, old_hsize); 263 rehash (old_harray, hash_table, old_size);
296 } 264 }
297 265
298 #ifdef emacs 266 xfree (old_harray);
299 if (!EQ (hash->elisp_table, Qnull_pointer) && 267 }
300 !NILP (hash->elisp_table) && 268
301 !ZEROP (hash->elisp_table)) 269 void
302 elisp_hvector_free (old_harray, hash->elisp_table); 270 expand_hash_table (struct hash_table *hash_table, hash_size_t needed_size)
303 else 271 {
304 #endif 272 hash_size_t size = hash_table->size;
305 xfree (old_harray); 273 hash_size_t comfortable_size = COMFORTABLE_SIZE (needed_size);
306 } 274 if (size < comfortable_size)
307 275 grow_hash_table (hash_table, comfortable_size + 1);
308 void 276 }
309 expand_hashtable (c_hashtable hash, unsigned int needed_size) 277
310 { 278 void
311 size_t hsize = hash->size; 279 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
312 size_t comfortable_size = (13 * needed_size) / 10; 280 {
313 if (hsize < comfortable_size) 281 hash_table_test_function test_function = hash_table->test_function;
314 grow_hashtable (hash, comfortable_size + 1); 282 hash_size_t size = hash_table->size;
315 } 283 hash_size_t fullness = hash_table->fullness;
316
317 void
318 puthash (CONST void *key, void *cont, c_hashtable hash)
319 {
320 unsigned int hsize = hash->size;
321 int (*test_function) (CONST void *, CONST void *) = hash->test_function;
322 unsigned int fullness = hash->fullness;
323 hentry *harray; 284 hentry *harray;
324 CONST void *e_key; 285 CONST void *e_key;
325 hentry *e; 286 hentry *e;
326 unsigned int hcode_initial = 287 unsigned int hcode_initial =
327 (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key); 288 hash_table->hash_function ?
289 hash_table->hash_function (key) :
290 (unsigned long) key;
328 unsigned int hcode; 291 unsigned int hcode;
329 unsigned int incr = 0; 292 unsigned int incr = 0;
330 unsigned int h2; 293 size_t h2;
331 CONST void *oldcontents; 294 CONST void *oldcontents;
332 295
333 if (!key) 296 if (!key)
334 { 297 {
335 hash->zero_entry = cont; 298 hash_table->zero_entry = contents;
336 hash->zero_set = 1; 299 hash_table->zero_set = 1;
337 return; 300 return;
338 } 301 }
339 302
340 if (hsize < (1 + ((13 * fullness) / 10))) 303 if (size < (1 + COMFORTABLE_SIZE (fullness)))
341 { 304 {
342 grow_hashtable (hash, hsize + 1); 305 grow_hash_table (hash_table, size + 1);
343 hsize = hash->size; 306 size = hash_table->size;
344 fullness = hash->fullness; 307 fullness = hash_table->fullness;
345 } 308 }
346 309
347 harray= hash->harray; 310 harray= hash_table->harray;
348 h2 = hsize - 2; 311 h2 = size - 2;
349 312
350 hcode = hcode_initial % hsize; 313 hcode = hcode_initial % size;
351 314
352 e_key = harray [hcode].key; 315 e_key = harray [hcode].key;
353 if (e_key && (KEYS_DIFFER_P (e_key, key, test_function))) 316 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
354 { 317 {
355 h2 = hsize - 2; 318 h2 = size - 2;
356 incr = 1 + (hcode_initial % h2); 319 incr = 1 + (hcode_initial % h2);
357 do 320 do
358 { 321 {
359 hcode = hcode + incr; 322 hcode += incr;
360 if (hcode >= hsize) hcode = hcode - hsize; 323 if (hcode >= size) hcode -= size;
361 e_key = harray [hcode].key; 324 e_key = harray [hcode].key;
362 } 325 }
363 while (e_key && (KEYS_DIFFER_P (e_key, key, test_function))); 326 while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
364 } 327 }
365 oldcontents = harray [hcode].contents; 328 oldcontents = harray [hcode].contents;
366 harray [hcode].key = key; 329 harray [hcode].key = key;
367 harray [hcode].contents = cont; 330 harray [hcode].contents = contents;
368 /* if the entry that we used was a deleted entry, 331 /* If the entry that we used was a deleted entry,
369 check for a non deleted entry of the same key, 332 check for a non deleted entry of the same key,
370 then delete it */ 333 then delete it. */
371 if (!e_key && (oldcontents == NULL_ENTRY)) 334 if (!e_key && oldcontents == NULL_ENTRY)
372 { 335 {
373 if (!incr) incr = 1 + ((unsigned long) key % h2); 336 if (!incr) incr = 1 + ((unsigned long) key % h2);
374 337
375 do 338 do
376 { 339 {
377 hcode = hcode + incr; 340 hcode += incr; if (hcode >= size) hcode -= size;
378 if (hcode >= hsize) hcode = hcode - hsize;
379 e = &harray [hcode]; 341 e = &harray [hcode];
380 e_key = e->key; 342 e_key = e->key;
381 } 343 }
382 while ((e_key)? 344 while (e_key ?
383 (KEYS_DIFFER_P (e_key, key, test_function)): 345 KEYS_DIFFER_P (e_key, key, test_function):
384 (e->contents == NULL_ENTRY)); 346 e->contents == NULL_ENTRY);
385 347
386 if (e_key) 348 if (e_key)
387 { 349 {
388 e->key = 0; 350 e->key = 0;
389 e->contents = NULL_ENTRY; 351 e->contents = NULL_ENTRY;
390 } 352 }
391 } 353 }
392 354
393 /* only increment the fullness when we used up a new hentry */ 355 /* only increment the fullness when we used up a new hentry */
394 if (!e_key || (KEYS_DIFFER_P (e_key, key, test_function))) 356 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
395 hash->fullness++; 357 hash_table->fullness++;
396 } 358 }
397 359
398 static void 360 static void
399 rehash (hentry *harray, c_hashtable hash, unsigned int size) 361 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
400 { 362 {
401 hentry *limit = harray + size; 363 hentry *limit = harray + size;
402 hentry *e; 364 hentry *e;
403 for (e = harray; e < limit; e++) 365 for (e = harray; e < limit; e++)
404 { 366 {
405 if (e->key) 367 if (e->key)
406 puthash (e->key, e->contents, hash); 368 puthash (e->key, e->contents, hash_table);
407 } 369 }
408 } 370 }
409 371
410 void 372 void
411 remhash (CONST void *key, c_hashtable hash) 373 remhash (CONST void *key, struct hash_table *hash_table)
412 { 374 {
413 hentry *harray = hash->harray; 375 hentry *harray = hash_table->harray;
414 int (*test_function) (CONST void*, CONST void*) = hash->test_function; 376 hash_table_test_function test_function = hash_table->test_function;
415 unsigned int hsize = hash->size; 377 hash_size_t size = hash_table->size;
416 unsigned int hcode_initial = 378 unsigned int hcode_initial =
417 (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key); 379 (hash_table->hash_function) ?
418 unsigned int hcode = hcode_initial % hsize; 380 (hash_table->hash_function (key)) :
381 ((unsigned long) key);
382 unsigned int hcode = hcode_initial % size;
419 hentry *e = &harray [hcode]; 383 hentry *e = &harray [hcode];
420 CONST void *e_key = e->key; 384 CONST void *e_key = e->key;
421 385
422 if (!key) 386 if (!key)
423 { 387 {
424 hash->zero_entry = 0; 388 hash_table->zero_entry = 0;
425 hash->zero_set = 0; 389 hash_table->zero_set = 0;
426 return; 390 return;
427 } 391 }
428 392
429 if ((e_key)? 393 if (e_key ?
430 (KEYS_DIFFER_P (e_key, key, test_function)): 394 KEYS_DIFFER_P (e_key, key, test_function) :
431 (e->contents == NULL_ENTRY)) 395 e->contents == NULL_ENTRY)
432 { 396 {
433 unsigned int h2 = hsize - 2; 397 size_t h2 = size - 2;
434 unsigned int incr = 1 + (hcode_initial % h2); 398 unsigned int incr = 1 + (hcode_initial % h2);
435 do 399 do
436 { 400 {
437 hcode = hcode + incr; 401 hcode += incr; if (hcode >= size) hcode -= size;
438 if (hcode >= hsize) hcode = hcode - hsize;
439 e = &harray [hcode]; 402 e = &harray [hcode];
440 e_key = e->key; 403 e_key = e->key;
441 } 404 }
442 while ((e_key)? 405 while (e_key?
443 (KEYS_DIFFER_P (e_key, key, test_function)): 406 KEYS_DIFFER_P (e_key, key, test_function):
444 (e->contents == NULL_ENTRY)); 407 e->contents == NULL_ENTRY);
445 } 408 }
446 if (e_key) 409 if (e_key)
447 { 410 {
448 e->key = 0; 411 e->key = 0;
449 e->contents = NULL_ENTRY; 412 e->contents = NULL_ENTRY;
450 /* Note: you can't do fullness-- here, it breaks the world. */ 413 /* Note: you can't do fullness-- here, it breaks the world. */
451 } 414 }
452 } 415 }
453 416
454 void 417 void
455 maphash (maphash_function mf, c_hashtable hash, void *arg) 418 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
456 { 419 {
457 hentry *e; 420 hentry *e;
458 hentry *limit; 421 hentry *limit;
459 422
460 if (hash->zero_set) 423 if (hash_table->zero_set)
461 { 424 {
462 if (((*mf) (0, hash->zero_entry, arg))) 425 if (mf (0, hash_table->zero_entry, arg))
463 return; 426 return;
464 } 427 }
465 428
466 for (e = hash->harray, limit = e + hash->size; e < limit; e++) 429 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
467 { 430 {
468 if (e->key) 431 if (e->key && mf (e->key, e->contents, arg))
469 { 432 return;
470 if (((*mf) (e->key, e->contents, arg))) 433 }
471 return; 434 }
472 } 435
473 } 436 void
474 } 437 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
475
476 void
477 map_remhash (remhash_predicate predicate, c_hashtable hash, void *arg)
478 { 438 {
479 hentry *e; 439 hentry *e;
480 hentry *limit; 440 hentry *limit;
481 441
482 if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg))) 442 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
483 { 443 {
484 hash->zero_set = 0; 444 hash_table->zero_set = 0;
485 hash->zero_entry = 0; 445 hash_table->zero_entry = 0;
486 } 446 }
487 447
488 for (e = hash->harray, limit = e + hash->size; e < limit; e++) 448 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
489 if ((*predicate) (e->key, e->contents, arg)) 449 if (predicate (e->key, e->contents, arg))
490 { 450 {
491 e->key = 0; 451 e->key = 0;
492 e->contents = NULL_ENTRY; 452 e->contents = NULL_ENTRY;
493 } 453 }
494 } 454 }