2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
4 This file is part of XEmacs.
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
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
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. */
21 /* Synched up with: Not in FSF. */
27 #define NULL_ENTRY (LISP_TO_VOID (Qnil))
31 #define NULL_ENTRY ((void *) 1)
37 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
39 /* Knuth volume 3, hash functions */
40 #define WORD_HASH_4(word) (0x9c406b55 * (word))
41 #define WORD_HASH_8(word) (0x9c406b549c406b55 * (word))
43 static CONST hash_size_t
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,
51 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
52 2009191, 2411033, 2893249
56 static CONST hash_size_t
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
72 memory_hash (CONST void *xv, size_t size)
75 unsigned CONST char *x = (unsigned CONST char *) xv;
83 if ((g = h & 0xf0000000) != 0)
84 h = (h ^ (g >> 24)) ^ g;
90 /* We've heard of binary search. */
92 prime_size (hash_size_t size)
95 for (low = 0, high = countof (primes) - 1; high - low > 1;)
97 /* Loop Invariant: size < primes [high] */
98 int mid = (low + high) / 2;
99 if (primes [mid] < size)
104 return primes [high];
107 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
109 #define KEYS_DIFFER_P(old, new, testfun) \
110 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
113 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value)
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) :
122 unsigned int hcode = hcode_initial % size;
123 hentry *e = &harray [hcode];
124 CONST void *e_key = e->key;
128 *ret_value = hash_table->zero_entry;
129 return (void *) hash_table->zero_set;
133 KEYS_DIFFER_P (e_key, key, test_function) :
134 e->contents == NULL_ENTRY)
136 size_t h2 = size - 2;
137 unsigned int incr = 1 + (hcode_initial % h2);
140 hcode += incr; if (hcode >= size) hcode -= size;
145 KEYS_DIFFER_P (e_key, key, test_function) :
146 e->contents == NULL_ENTRY);
149 *ret_value = e->contents;
154 clrhash (struct hash_table *hash_table)
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;
163 free_hash_table (struct hash_table *hash_table)
165 xfree (hash_table->harray);
170 make_hash_table (hash_size_t size)
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);
180 make_general_hash_table (hash_size_t size,
181 hash_table_hash_function hash_function,
182 hash_table_test_function test_function)
184 struct hash_table* hash_table = make_hash_table (size);
185 hash_table->hash_function = hash_function;
186 hash_table->test_function = test_function;
190 #if 0 /* unused strings code */
192 make_strings_hash_table (hash_size_t size)
194 return make_general_hash_table (size, string_hash, string_eq);
197 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
199 string_hash (CONST void *xv)
202 unsigned CONST char *x = (unsigned CONST char *) xv;
210 if ((g = h & 0xf0000000) != 0)
211 h = (h ^ (g >> 24)) ^ g;
218 string_eq (CONST void *s1, CONST void *s2)
220 return s1 && s2 ? !strcmp ((CONST char *) s1, (CONST char *) s2) : s1 == s2;
222 #endif /* unused strings code */
225 copy_hash (struct hash_table *dest, struct hash_table *src)
227 if (dest->size != src->size)
229 xfree (dest->harray);
231 dest->size = src->size;
232 dest->harray = xnew_array (hentry, dest->size);
234 dest->fullness = src->fullness;
235 dest->zero_entry = src->zero_entry;
236 dest->zero_set = src->zero_set;
237 dest->hash_function = src->hash_function;
238 dest->test_function = src->test_function;
239 memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
243 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
245 hash_size_t old_size = hash_table->size;
246 hentry *old_harray = hash_table->harray;
249 new_size = prime_size (new_size);
251 new_harray = xnew_array (hentry, new_size);
253 hash_table->size = new_size;
254 hash_table->harray = new_harray;
256 /* do the rehash on the "grown" table */
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);
270 expand_hash_table (struct hash_table *hash_table, hash_size_t needed_size)
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);
279 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
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;
287 unsigned int hcode_initial =
288 hash_table->hash_function ?
289 hash_table->hash_function (key) :
292 unsigned int incr = 0;
294 CONST void *oldcontents;
298 hash_table->zero_entry = contents;
299 hash_table->zero_set = 1;
303 if (size < (1 + COMFORTABLE_SIZE (fullness)))
305 grow_hash_table (hash_table, size + 1);
306 size = hash_table->size;
307 fullness = hash_table->fullness;
310 harray= hash_table->harray;
313 hcode = hcode_initial % size;
315 e_key = harray [hcode].key;
316 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
319 incr = 1 + (hcode_initial % h2);
323 if (hcode >= size) hcode -= size;
324 e_key = harray [hcode].key;
326 while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
328 oldcontents = harray [hcode].contents;
329 harray [hcode].key = key;
330 harray [hcode].contents = contents;
331 /* If the entry that we used was a deleted entry,
332 check for a non deleted entry of the same key,
334 if (!e_key && oldcontents == NULL_ENTRY)
336 if (!incr) incr = 1 + ((unsigned long) key % h2);
340 hcode += incr; if (hcode >= size) hcode -= size;
345 KEYS_DIFFER_P (e_key, key, test_function):
346 e->contents == NULL_ENTRY);
351 e->contents = NULL_ENTRY;
355 /* only increment the fullness when we used up a new hentry */
356 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
357 hash_table->fullness++;
361 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
363 hentry *limit = harray + size;
365 for (e = harray; e < limit; e++)
368 puthash (e->key, e->contents, hash_table);
373 remhash (CONST void *key, struct hash_table *hash_table)
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;
378 unsigned int hcode_initial =
379 (hash_table->hash_function) ?
380 (hash_table->hash_function (key)) :
381 ((unsigned long) key);
382 unsigned int hcode = hcode_initial % size;
383 hentry *e = &harray [hcode];
384 CONST void *e_key = e->key;
388 hash_table->zero_entry = 0;
389 hash_table->zero_set = 0;
394 KEYS_DIFFER_P (e_key, key, test_function) :
395 e->contents == NULL_ENTRY)
397 size_t h2 = size - 2;
398 unsigned int incr = 1 + (hcode_initial % h2);
401 hcode += incr; if (hcode >= size) hcode -= size;
406 KEYS_DIFFER_P (e_key, key, test_function):
407 e->contents == NULL_ENTRY);
412 e->contents = NULL_ENTRY;
413 /* Note: you can't do fullness-- here, it breaks the world. */
418 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
423 if (hash_table->zero_set)
425 if (mf (0, hash_table->zero_entry, arg))
429 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
431 if (e->key && mf (e->key, e->contents, arg))
437 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
442 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
444 hash_table->zero_set = 0;
445 hash_table->zero_entry = 0;
448 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
449 if (predicate (e->key, e->contents, arg))
452 e->contents = NULL_ENTRY;