2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
4 This file is part of SXEmacs
6 SXEmacs is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 SXEmacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20 /* Synched up with: Not in FSF. */
26 #define NULL_ENTRY ((void *) 0xdeadbeef)
28 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
30 #define KEYS_DIFFER_P(old, new, testfun) \
31 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
33 static void rehash(chentry * harray, struct hash_table *ht, hash_size_t size);
35 unsigned long memory_hash(const void *xv, size_t size)
38 unsigned const char *x = (unsigned const char *)xv;
46 if ((g = h & 0xf0000000) != 0)
47 h = (h ^ (g >> 24)) ^ g;
53 unsigned long string_hash(const char *xv)
56 unsigned const char *x = (unsigned const char *)xv;
64 if ((g = h & 0xf0000000) != 0)
65 h = (h ^ (g >> 24)) ^ g;
71 /* Return a suitable size for a hash table, with at least SIZE slots. */
72 static size_t hash_table_size(size_t requested_size)
74 /* Return some prime near, but greater than or equal to, SIZE.
75 Decades from the time of writing, someone will have a system large
76 enough that the list below will be too short... */
77 static const size_t primes[] = {
78 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787,
80 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
81 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
82 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
83 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
84 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
85 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
86 243370577, 316381771, 411296309, 534685237, 695090819,
88 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
90 /* We've heard of binary search. */
92 for (low = 0, high = countof(primes) - 1; high - low > 1;) {
93 /* Loop Invariant: size < primes [high] */
94 int mid = (low + high) / 2;
95 if (primes[mid] < requested_size)
103 const void *gethash(const void *key, struct hash_table *hash_table,
104 const void **ret_value)
107 *ret_value = hash_table->zero_entry;
108 return (void *)hash_table->zero_set;
110 chentry *harray = hash_table->harray;
111 hash_table_test_function test_function =
112 hash_table->test_function;
113 hash_size_t size = hash_table->size;
114 unsigned int hcode_initial =
115 hash_table->hash_function ?
116 hash_table->hash_function(key) : (unsigned long)key;
117 unsigned int hcode = hcode_initial % size;
118 chentry *e = &harray[hcode];
119 const void *e_key = e->key;
122 KEYS_DIFFER_P(e_key, key, test_function) :
123 e->contents == NULL_ENTRY) {
124 size_t h2 = size - 2;
125 unsigned int incr = 1 + (hcode_initial % h2);
134 KEYS_DIFFER_P(e_key, key, test_function) :
135 e->contents == NULL_ENTRY);
138 *ret_value = e->contents;
143 void clrhash(struct hash_table *hash_table)
145 memset(hash_table->harray, 0, sizeof(chentry) * hash_table->size);
146 hash_table->zero_entry = 0;
147 hash_table->zero_set = 0;
148 hash_table->fullness = 0;
151 void free_hash_table(struct hash_table *hash_table)
153 xfree(hash_table->harray);
157 struct hash_table *make_hash_table(hash_size_t size)
159 struct hash_table *hash_table = xnew_and_zero(struct hash_table);
160 hash_table->size = hash_table_size(COMFORTABLE_SIZE(size));
161 hash_table->harray = xnew_array(chentry, hash_table->size);
166 struct hash_table *make_general_hash_table(hash_size_t size,
167 hash_table_hash_function
169 hash_table_test_function
172 struct hash_table *hash_table = make_hash_table(size);
173 hash_table->hash_function = hash_function;
174 hash_table->test_function = test_function;
178 static void grow_hash_table(struct hash_table *hash_table, hash_size_t new_size)
180 hash_size_t old_size = hash_table->size;
181 chentry *old_harray = hash_table->harray;
183 hash_table->size = hash_table_size(new_size);
184 hash_table->harray = xnew_array(chentry, hash_table->size);
186 /* do the rehash on the "grown" table */
188 long old_zero_set = hash_table->zero_set;
189 void *old_zero_entry = hash_table->zero_entry;
191 hash_table->zero_set = old_zero_set;
192 hash_table->zero_entry = old_zero_entry;
193 rehash(old_harray, hash_table, old_size);
199 void puthash(const void *key, void *contents, struct hash_table *hash_table)
202 hash_table->zero_entry = contents;
203 hash_table->zero_set = 1;
205 hash_table_test_function test_function =
206 hash_table->test_function;
207 hash_size_t size = hash_table->size;
208 chentry *harray = hash_table->harray;
209 unsigned int hcode_initial =
210 hash_table->hash_function ?
211 hash_table->hash_function(key) : (unsigned long)key;
212 unsigned int hcode = hcode_initial % size;
213 size_t h2 = size - 2;
214 unsigned int incr = 1 + (hcode_initial % h2);
215 const void *e_key = harray[hcode].key;
216 const void *oldcontents;
218 if (e_key && KEYS_DIFFER_P(e_key, key, test_function)) {
223 e_key = harray[hcode].key;
226 && KEYS_DIFFER_P(e_key, key, test_function));
228 oldcontents = harray[hcode].contents;
229 harray[hcode].key = key;
230 harray[hcode].contents = contents;
231 /* If the entry that we used was a deleted entry,
232 check for a non deleted entry of the same key,
234 if (!e_key && oldcontents == NULL_ENTRY) {
245 KEYS_DIFFER_P(e_key, key, test_function) :
246 e->contents == NULL_ENTRY);
250 e->contents = NULL_ENTRY;
254 /* only increment the fullness when we used up a new chentry */
255 if (!e_key || KEYS_DIFFER_P(e_key, key, test_function)) {
256 hash_size_t comfortable_size =
257 COMFORTABLE_SIZE(++(hash_table->fullness));
258 if (hash_table->size < comfortable_size)
259 grow_hash_table(hash_table,
260 comfortable_size + 1);
266 rehash(chentry * harray, struct hash_table *hash_table, hash_size_t size)
268 chentry *limit = harray + size;
270 for (e = harray; e < limit; e++) {
272 puthash(e->key, e->contents, hash_table);
276 void remhash(const void *key, struct hash_table *hash_table)
279 hash_table->zero_entry = 0;
280 hash_table->zero_set = 0;
282 chentry *harray = hash_table->harray;
283 hash_table_test_function test_function =
284 hash_table->test_function;
285 hash_size_t size = hash_table->size;
286 unsigned int hcode_initial =
287 (hash_table->hash_function) ?
288 (hash_table->hash_function(key)) : ((unsigned long)key);
289 unsigned int hcode = hcode_initial % size;
290 chentry *e = &harray[hcode];
291 const void *e_key = e->key;
294 KEYS_DIFFER_P(e_key, key, test_function) :
295 e->contents == NULL_ENTRY) {
296 size_t h2 = size - 2;
297 unsigned int incr = 1 + (hcode_initial % h2);
306 KEYS_DIFFER_P(e_key, key, test_function) :
307 e->contents == NULL_ENTRY);
311 e->contents = NULL_ENTRY;
312 /* Note: you can't do fullness-- here, it breaks the world. */
317 void maphash(maphash_function mf, struct hash_table *hash_table, void *arg)
322 if (hash_table->zero_set) {
323 if (mf(0, hash_table->zero_entry, arg))
327 for (e = hash_table->harray, limit = e + hash_table->size; e < limit;
329 if (e->key && mf(e->key, e->contents, arg))
335 map_remhash(remhash_predicate predicate, struct hash_table *hash_table,
341 if (hash_table->zero_set && predicate(0, hash_table->zero_entry, arg)) {
342 hash_table->zero_set = 0;
343 hash_table->zero_entry = 0;
346 for (e = hash_table->harray, limit = e + hash_table->size; e < limit;
348 if (predicate(e->key, e->contents, arg)) {
350 e->contents = NULL_ENTRY;