|
0
|
1 /* Hash tables.
|
|
|
2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of XEmacs.
|
|
|
5
|
|
|
6 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 2, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with XEmacs; see the file COPYING. If not, write to
|
|
|
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
19 Boston, MA 02111-1307, USA. */
|
|
|
20
|
|
|
21 /* Synched up with: Not in FSF. */
|
|
|
22
|
|
|
23 #ifdef emacs
|
|
|
24 #include <config.h>
|
|
|
25 #include "lisp.h"
|
|
|
26
|
|
|
27 #define NULL_ENTRY (LISP_TO_VOID (Qnil))
|
|
|
28
|
|
|
29 #else /* !emacs */
|
|
|
30
|
|
|
31 #define NULL_ENTRY ((void *) 1)
|
|
|
32
|
|
|
33 #endif /* !emacs */
|
|
|
34
|
|
|
35 #include "hash.h"
|
|
380
|
36
|
|
|
37 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
|
|
0
|
38
|
|
380
|
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 {
|
|
0
|
46 13,
|
|
173
|
47 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,
|
|
|
48 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
|
|
|
49 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361,
|
|
|
50 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449,
|
|
0
|
51 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
|
|
|
52 2009191, 2411033, 2893249
|
|
|
53 };
|
|
|
54
|
|
380
|
55 #if 0
|
|
|
56 static CONST hash_size_t
|
|
|
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
|
|
|
71 unsigned long
|
|
|
72 memory_hash (CONST void *xv, size_t size)
|
|
|
73 {
|
|
|
74 unsigned int h = 0;
|
|
|
75 unsigned CONST char *x = (unsigned CONST char *) xv;
|
|
|
76
|
|
|
77 if (!x) return 0;
|
|
|
78
|
|
|
79 while (size--)
|
|
|
80 {
|
|
|
81 unsigned int g;
|
|
|
82 h = (h << 4) + *x++;
|
|
|
83 if ((g = h & 0xf0000000) != 0)
|
|
|
84 h = (h ^ (g >> 24)) ^ g;
|
|
|
85 }
|
|
|
86
|
|
|
87 return h;
|
|
|
88 }
|
|
|
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 }
|
|
0
|
196
|
|
|
197 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
|
|
|
198 unsigned long
|
|
|
199 string_hash (CONST void *xv)
|
|
173
|
200 {
|
|
0
|
201 unsigned int h = 0;
|
|
|
202 unsigned CONST char *x = (unsigned CONST char *) xv;
|
|
|
203
|
|
|
204 if (!x) return 0;
|
|
|
205
|
|
|
206 while (*x != 0)
|
|
|
207 {
|
|
272
|
208 unsigned int g;
|
|
0
|
209 h = (h << 4) + *x++;
|
|
|
210 if ((g = h & 0xf0000000) != 0)
|
|
|
211 h = (h ^ (g >> 24)) ^ g;
|
|
|
212 }
|
|
|
213
|
|
|
214 return h;
|
|
|
215 }
|
|
|
216
|
|
380
|
217 static int
|
|
|
218 string_eq (CONST void *s1, CONST void *s2)
|
|
173
|
219 {
|
|
380
|
220 return s1 && s2 ? !strcmp ((CONST char *) s1, (CONST char *) s2) : s1 == s2;
|
|
0
|
221 }
|
|
380
|
222 #endif /* unused strings code */
|
|
0
|
223
|
|
173
|
224 void
|
|
380
|
225 copy_hash (struct hash_table *dest, struct hash_table *src)
|
|
0
|
226 {
|
|
|
227 if (dest->size != src->size)
|
|
|
228 {
|
|
380
|
229 xfree (dest->harray);
|
|
0
|
230
|
|
|
231 dest->size = src->size;
|
|
380
|
232 dest->harray = xnew_array (hentry, dest->size);
|
|
0
|
233 }
|
|
380
|
234 dest->fullness = src->fullness;
|
|
|
235 dest->zero_entry = src->zero_entry;
|
|
|
236 dest->zero_set = src->zero_set;
|
|
0
|
237 dest->hash_function = src->hash_function;
|
|
|
238 dest->test_function = src->test_function;
|
|
|
239 memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
|
|
|
240 }
|
|
173
|
241
|
|
0
|
242 static void
|
|
380
|
243 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
|
|
0
|
244 {
|
|
380
|
245 hash_size_t old_size = hash_table->size;
|
|
|
246 hentry *old_harray = hash_table->harray;
|
|
|
247 hentry *new_harray;
|
|
0
|
248
|
|
380
|
249 new_size = prime_size (new_size);
|
|
0
|
250
|
|
380
|
251 new_harray = xnew_array (hentry, new_size);
|
|
|
252
|
|
|
253 hash_table->size = new_size;
|
|
|
254 hash_table->harray = new_harray;
|
|
0
|
255
|
|
|
256 /* do the rehash on the "grown" table */
|
|
|
257 {
|
|
380
|
258 long old_zero_set = hash_table->zero_set;
|
|
|
259 void *old_zero_entry = hash_table->zero_entry;
|
|
|
260 clrhash (hash_table);
|
|
|
261 hash_table->zero_set = old_zero_set;
|
|
|
262 hash_table->zero_entry = old_zero_entry;
|
|
|
263 rehash (old_harray, hash_table, old_size);
|
|
0
|
264 }
|
|
|
265
|
|
380
|
266 xfree (old_harray);
|
|
0
|
267 }
|
|
|
268
|
|
|
269 void
|
|
380
|
270 expand_hash_table (struct hash_table *hash_table, hash_size_t needed_size)
|
|
0
|
271 {
|
|
380
|
272 hash_size_t size = hash_table->size;
|
|
|
273 hash_size_t comfortable_size = COMFORTABLE_SIZE (needed_size);
|
|
|
274 if (size < comfortable_size)
|
|
|
275 grow_hash_table (hash_table, comfortable_size + 1);
|
|
0
|
276 }
|
|
|
277
|
|
173
|
278 void
|
|
380
|
279 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
|
|
0
|
280 {
|
|
380
|
281 hash_table_test_function test_function = hash_table->test_function;
|
|
|
282 hash_size_t size = hash_table->size;
|
|
|
283 hash_size_t fullness = hash_table->fullness;
|
|
0
|
284 hentry *harray;
|
|
|
285 CONST void *e_key;
|
|
|
286 hentry *e;
|
|
173
|
287 unsigned int hcode_initial =
|
|
380
|
288 hash_table->hash_function ?
|
|
|
289 hash_table->hash_function (key) :
|
|
|
290 (unsigned long) key;
|
|
0
|
291 unsigned int hcode;
|
|
|
292 unsigned int incr = 0;
|
|
380
|
293 size_t h2;
|
|
0
|
294 CONST void *oldcontents;
|
|
|
295
|
|
173
|
296 if (!key)
|
|
0
|
297 {
|
|
380
|
298 hash_table->zero_entry = contents;
|
|
|
299 hash_table->zero_set = 1;
|
|
0
|
300 return;
|
|
|
301 }
|
|
|
302
|
|
380
|
303 if (size < (1 + COMFORTABLE_SIZE (fullness)))
|
|
0
|
304 {
|
|
380
|
305 grow_hash_table (hash_table, size + 1);
|
|
|
306 size = hash_table->size;
|
|
|
307 fullness = hash_table->fullness;
|
|
0
|
308 }
|
|
|
309
|
|
380
|
310 harray= hash_table->harray;
|
|
|
311 h2 = size - 2;
|
|
0
|
312
|
|
380
|
313 hcode = hcode_initial % size;
|
|
173
|
314
|
|
0
|
315 e_key = harray [hcode].key;
|
|
380
|
316 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
|
|
0
|
317 {
|
|
380
|
318 h2 = size - 2;
|
|
0
|
319 incr = 1 + (hcode_initial % h2);
|
|
|
320 do
|
|
|
321 {
|
|
380
|
322 hcode += incr;
|
|
|
323 if (hcode >= size) hcode -= size;
|
|
0
|
324 e_key = harray [hcode].key;
|
|
173
|
325 }
|
|
380
|
326 while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
|
|
0
|
327 }
|
|
|
328 oldcontents = harray [hcode].contents;
|
|
|
329 harray [hcode].key = key;
|
|
380
|
330 harray [hcode].contents = contents;
|
|
|
331 /* If the entry that we used was a deleted entry,
|
|
0
|
332 check for a non deleted entry of the same key,
|
|
380
|
333 then delete it. */
|
|
|
334 if (!e_key && oldcontents == NULL_ENTRY)
|
|
0
|
335 {
|
|
|
336 if (!incr) incr = 1 + ((unsigned long) key % h2);
|
|
|
337
|
|
|
338 do
|
|
|
339 {
|
|
380
|
340 hcode += incr; if (hcode >= size) hcode -= size;
|
|
0
|
341 e = &harray [hcode];
|
|
|
342 e_key = e->key;
|
|
|
343 }
|
|
380
|
344 while (e_key ?
|
|
|
345 KEYS_DIFFER_P (e_key, key, test_function):
|
|
|
346 e->contents == NULL_ENTRY);
|
|
0
|
347
|
|
|
348 if (e_key)
|
|
|
349 {
|
|
|
350 e->key = 0;
|
|
|
351 e->contents = NULL_ENTRY;
|
|
|
352 }
|
|
|
353 }
|
|
|
354
|
|
|
355 /* only increment the fullness when we used up a new hentry */
|
|
380
|
356 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
|
|
|
357 hash_table->fullness++;
|
|
0
|
358 }
|
|
|
359
|
|
|
360 static void
|
|
380
|
361 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
|
|
0
|
362 {
|
|
|
363 hentry *limit = harray + size;
|
|
|
364 hentry *e;
|
|
|
365 for (e = harray; e < limit; e++)
|
|
|
366 {
|
|
|
367 if (e->key)
|
|
380
|
368 puthash (e->key, e->contents, hash_table);
|
|
0
|
369 }
|
|
|
370 }
|
|
|
371
|
|
173
|
372 void
|
|
380
|
373 remhash (CONST void *key, struct hash_table *hash_table)
|
|
0
|
374 {
|
|
380
|
375 hentry *harray = hash_table->harray;
|
|
|
376 hash_table_test_function test_function = hash_table->test_function;
|
|
|
377 hash_size_t size = hash_table->size;
|
|
173
|
378 unsigned int hcode_initial =
|
|
380
|
379 (hash_table->hash_function) ?
|
|
|
380 (hash_table->hash_function (key)) :
|
|
|
381 ((unsigned long) key);
|
|
|
382 unsigned int hcode = hcode_initial % size;
|
|
0
|
383 hentry *e = &harray [hcode];
|
|
|
384 CONST void *e_key = e->key;
|
|
|
385
|
|
173
|
386 if (!key)
|
|
0
|
387 {
|
|
380
|
388 hash_table->zero_entry = 0;
|
|
|
389 hash_table->zero_set = 0;
|
|
0
|
390 return;
|
|
|
391 }
|
|
|
392
|
|
380
|
393 if (e_key ?
|
|
|
394 KEYS_DIFFER_P (e_key, key, test_function) :
|
|
|
395 e->contents == NULL_ENTRY)
|
|
0
|
396 {
|
|
380
|
397 size_t h2 = size - 2;
|
|
0
|
398 unsigned int incr = 1 + (hcode_initial % h2);
|
|
|
399 do
|
|
|
400 {
|
|
380
|
401 hcode += incr; if (hcode >= size) hcode -= size;
|
|
0
|
402 e = &harray [hcode];
|
|
|
403 e_key = e->key;
|
|
|
404 }
|
|
380
|
405 while (e_key?
|
|
|
406 KEYS_DIFFER_P (e_key, key, test_function):
|
|
|
407 e->contents == NULL_ENTRY);
|
|
0
|
408 }
|
|
|
409 if (e_key)
|
|
|
410 {
|
|
|
411 e->key = 0;
|
|
|
412 e->contents = NULL_ENTRY;
|
|
|
413 /* Note: you can't do fullness-- here, it breaks the world. */
|
|
|
414 }
|
|
|
415 }
|
|
|
416
|
|
173
|
417 void
|
|
380
|
418 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
|
|
0
|
419 {
|
|
|
420 hentry *e;
|
|
|
421 hentry *limit;
|
|
173
|
422
|
|
380
|
423 if (hash_table->zero_set)
|
|
241
|
424 {
|
|
380
|
425 if (mf (0, hash_table->zero_entry, arg))
|
|
241
|
426 return;
|
|
|
427 }
|
|
0
|
428
|
|
380
|
429 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
|
|
0
|
430 {
|
|
380
|
431 if (e->key && mf (e->key, e->contents, arg))
|
|
|
432 return;
|
|
0
|
433 }
|
|
|
434 }
|
|
|
435
|
|
173
|
436 void
|
|
380
|
437 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
|
|
0
|
438 {
|
|
|
439 hentry *e;
|
|
|
440 hentry *limit;
|
|
173
|
441
|
|
380
|
442 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
|
|
0
|
443 {
|
|
380
|
444 hash_table->zero_set = 0;
|
|
|
445 hash_table->zero_entry = 0;
|
|
0
|
446 }
|
|
|
447
|
|
380
|
448 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
|
|
|
449 if (predicate (e->key, e->contents, arg))
|
|
0
|
450 {
|
|
|
451 e->key = 0;
|
|
|
452 e->contents = NULL_ENTRY;
|
|
|
453 }
|
|
|
454 }
|
