Mercurial > hg > xemacs-beta

comparison src/hash.c @ 394:7d59cb494b73 r21-2-12

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-12
author cvs
date Mon, 13 Aug 2007 11:11:37 +0200
parents 8626e4521993
children 74fd4e045ea6
comparison
equal deleted inserted replaced
393:2e030b8965b1 394:7d59cb494b73
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */ 19 Boston, MA 02111-1307, USA. */
20 20
21 /* Synched up with: Not in FSF. */ 21 /* Synched up with: Not in FSF. */
22 22
23 #ifdef emacs
24 #include <config.h> 23 #include <config.h>
25 #include "lisp.h" 24 #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" 25 #include "hash.h"
36 26
27 #define NULL_ENTRY ((void *) 0xdeadbeef)
28
37 #define COMFORTABLE_SIZE(size) (21 * (size) / 16) 29 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
38 30
39 /* Knuth volume 3, hash functions */ 31 #define KEYS_DIFFER_P(old, new, testfun) \
40 #define WORD_HASH_4(word) (0x9c406b55 * (word)) 32 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
41 #define WORD_HASH_8(word) (0x9c406b549c406b55 * (word)) 33
42 34 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
43 static CONST hash_size_t
44 primes [] =
45 {
46 13,
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
53 };
54
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 35
71 unsigned long 36 unsigned long
72 memory_hash (CONST void *xv, size_t size) 37 memory_hash (CONST void *xv, size_t size)
73 { 38 {
74 unsigned int h = 0; 39 unsigned int h = 0;
85 } 50 }
86 51
87 return h; 52 return h;
88 } 53 }
89 54
90 /* We've heard of binary search. */ 55 /* Return a suitable size for a hash table, with at least SIZE slots. */
91 static hash_size_t 56 static size_t
92 prime_size (hash_size_t size) 57 hash_table_size (size_t requested_size)
93 { 58 {
59 /* Return some prime near, but greater than or equal to, SIZE.
60 Decades from the time of writing, someone will have a system large
61 enough that the list below will be too short... */
62 static CONST size_t primes [] =
63 {
64 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
65 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
66 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
67 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
68 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
69 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
70 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
71 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
72 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
73 };
74 /* We've heard of binary search. */
94 int low, high; 75 int low, high;
95 for (low = 0, high = countof (primes) - 1; high - low > 1;) 76 for (low = 0, high = countof (primes) - 1; high - low > 1;)
96 { 77 {
97 /* Loop Invariant: size < primes [high] */ 78 /* Loop Invariant: size < primes [high] */
98 int mid = (low + high) / 2; 79 int mid = (low + high) / 2;
99 if (primes [mid] < size) 80 if (primes [mid] < requested_size)
100 low = mid; 81 low = mid;
101 else 82 else
102 high = mid; 83 high = mid;
103 } 84 }
104 return primes [high]; 85 return primes [high];
105 } 86 }
106 87
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 * 88 CONST void *
113 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value) 89 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value)
114 { 90 {
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) 91 if (!key)
127 { 92 {
128 *ret_value = hash_table->zero_entry; 93 *ret_value = hash_table->zero_entry;
129 return (void *) hash_table->zero_set; 94 return (void *) hash_table->zero_set;
130 } 95 }
131 96 else
132 if (e_key ? 97 {
133 KEYS_DIFFER_P (e_key, key, test_function) : 98 hentry *harray = hash_table->harray;
134 e->contents == NULL_ENTRY) 99 hash_table_test_function test_function = hash_table->test_function;
135 { 100 hash_size_t size = hash_table->size;
136 size_t h2 = size - 2; 101 unsigned int hcode_initial =
137 unsigned int incr = 1 + (hcode_initial % h2); 102 hash_table->hash_function ?
138 do 103 hash_table->hash_function (key) :
139 { 104 (unsigned long) key;
140 hcode += incr; if (hcode >= size) hcode -= size; 105 unsigned int hcode = hcode_initial % size;
141 e = &harray [hcode]; 106 hentry *e = &harray [hcode];
142 e_key = e->key; 107 CONST void *e_key = e->key;
143 } 108
144 while (e_key ? 109 if (e_key ?
145 KEYS_DIFFER_P (e_key, key, test_function) : 110 KEYS_DIFFER_P (e_key, key, test_function) :
146 e->contents == NULL_ENTRY); 111 e->contents == NULL_ENTRY)
147 } 112 {
148 113 size_t h2 = size - 2;
149 *ret_value = e->contents; 114 unsigned int incr = 1 + (hcode_initial % h2);
150 return e->key; 115 do
116 {
117 hcode += incr; if (hcode >= size) hcode -= size;
118 e = &harray [hcode];
119 e_key = e->key;
120 }
121 while (e_key ?
122 KEYS_DIFFER_P (e_key, key, test_function) :
123 e->contents == NULL_ENTRY);
124 }
125
126 *ret_value = e->contents;
127 return e->key;
128 }
151 } 129 }
152 130
153 void 131 void
154 clrhash (struct hash_table *hash_table) 132 clrhash (struct hash_table *hash_table)
155 { 133 {
168 146
169 struct hash_table* 147 struct hash_table*
170 make_hash_table (hash_size_t size) 148 make_hash_table (hash_size_t size)
171 { 149 {
172 struct hash_table *hash_table = xnew_and_zero (struct hash_table); 150 struct hash_table *hash_table = xnew_and_zero (struct hash_table);
173 hash_table->size = prime_size (COMFORTABLE_SIZE (size)); 151 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
174 hash_table->harray = xnew_array (hentry, hash_table->size); 152 hash_table->harray = xnew_array (hentry, hash_table->size);
175 clrhash (hash_table); 153 clrhash (hash_table);
176 return hash_table; 154 return hash_table;
177 } 155 }
178 156
185 hash_table->hash_function = hash_function; 163 hash_table->hash_function = hash_function;
186 hash_table->test_function = test_function; 164 hash_table->test_function = test_function;
187 return hash_table; 165 return hash_table;
188 } 166 }
189 167
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 */
198 unsigned long
199 string_hash (CONST void *xv)
200 {
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 {
208 unsigned int g;
209 h = (h << 4) + *x++;
210 if ((g = h & 0xf0000000) != 0)
211 h = (h ^ (g >> 24)) ^ g;
212 }
213
214 return h;
215 }
216
217 static int
218 string_eq (CONST void *s1, CONST void *s2)
219 {
220 return s1 && s2 ? !strcmp ((CONST char *) s1, (CONST char *) s2) : s1 == s2;
221 }
222 #endif /* unused strings code */
223
224 void
225 copy_hash (struct hash_table *dest, struct hash_table *src)
226 {
227 if (dest->size != src->size)
228 {
229 xfree (dest->harray);
230
231 dest->size = src->size;
232 dest->harray = xnew_array (hentry, dest->size);
233 }
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);
240 }
241
242 static void 168 static void
243 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size) 169 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
244 { 170 {
245 hash_size_t old_size = hash_table->size; 171 hash_size_t old_size = hash_table->size;
246 hentry *old_harray = hash_table->harray; 172 hentry *old_harray = hash_table->harray;
247 hentry *new_harray; 173
248 174 hash_table->size = hash_table_size (new_size);
249 new_size = prime_size (new_size); 175 hash_table->harray = xnew_array (hentry, hash_table->size);
250
251 new_harray = xnew_array (hentry, new_size);
252
253 hash_table->size = new_size;
254 hash_table->harray = new_harray;
255 176
256 /* do the rehash on the "grown" table */ 177 /* do the rehash on the "grown" table */
257 { 178 {
258 long old_zero_set = hash_table->zero_set; 179 long old_zero_set = hash_table->zero_set;
259 void *old_zero_entry = hash_table->zero_entry; 180 void *old_zero_entry = hash_table->zero_entry;
265 186
266 xfree (old_harray); 187 xfree (old_harray);
267 } 188 }
268 189
269 void 190 void
270 expand_hash_table (struct hash_table *hash_table, hash_size_t needed_size)
271 {
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);
276 }
277
278 void
279 puthash (CONST void *key, void *contents, struct hash_table *hash_table) 191 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
280 { 192 {
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;
284 hentry *harray;
285 CONST void *e_key;
286 hentry *e;
287 unsigned int hcode_initial =
288 hash_table->hash_function ?
289 hash_table->hash_function (key) :
290 (unsigned long) key;
291 unsigned int hcode;
292 unsigned int incr = 0;
293 size_t h2;
294 CONST void *oldcontents;
295
296 if (!key) 193 if (!key)
297 { 194 {
298 hash_table->zero_entry = contents; 195 hash_table->zero_entry = contents;
299 hash_table->zero_set = 1; 196 hash_table->zero_set = 1;
300 return; 197 }
301 } 198 else
302 199 {
303 if (size < (1 + COMFORTABLE_SIZE (fullness))) 200 hash_table_test_function test_function = hash_table->test_function;
304 { 201 hash_size_t size = hash_table->size;
305 grow_hash_table (hash_table, size + 1); 202 hentry *harray = hash_table->harray;
306 size = hash_table->size; 203 unsigned int hcode_initial =
307 fullness = hash_table->fullness; 204 hash_table->hash_function ?
308 } 205 hash_table->hash_function (key) :
309 206 (unsigned long) key;
310 harray= hash_table->harray; 207 unsigned int hcode = hcode_initial % size;
311 h2 = size - 2; 208 size_t h2 = size - 2;
312 209 unsigned int incr = 1 + (hcode_initial % h2);
313 hcode = hcode_initial % size; 210 CONST void *e_key = harray [hcode].key;
314 211 CONST void *oldcontents;
315 e_key = harray [hcode].key; 212
316 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) 213 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
317 { 214 {
318 h2 = size - 2; 215 do
319 incr = 1 + (hcode_initial % h2); 216 {
320 do 217 hcode += incr; if (hcode >= size) hcode -= size;
321 { 218 e_key = harray [hcode].key;
322 hcode += incr; 219 }
323 if (hcode >= size) hcode -= size; 220 while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
324 e_key = harray [hcode].key; 221 }
325 } 222 oldcontents = harray [hcode].contents;
326 while (e_key && KEYS_DIFFER_P (e_key, key, test_function)); 223 harray [hcode].key = key;
327 } 224 harray [hcode].contents = contents;
328 oldcontents = harray [hcode].contents; 225 /* If the entry that we used was a deleted entry,
329 harray [hcode].key = key; 226 check for a non deleted entry of the same key,
330 harray [hcode].contents = contents; 227 then delete it. */
331 /* If the entry that we used was a deleted entry, 228 if (!e_key && oldcontents == NULL_ENTRY)
332 check for a non deleted entry of the same key, 229 {
333 then delete it. */ 230 hentry *e;
334 if (!e_key && oldcontents == NULL_ENTRY) 231
335 { 232 do
336 if (!incr) incr = 1 + ((unsigned long) key % h2); 233 {
337 234 hcode += incr; if (hcode >= size) hcode -= size;
338 do 235 e = &harray [hcode];
339 { 236 e_key = e->key;
340 hcode += incr; if (hcode >= size) hcode -= size; 237 }
341 e = &harray [hcode]; 238 while (e_key ?
342 e_key = e->key; 239 KEYS_DIFFER_P (e_key, key, test_function):
343 } 240 e->contents == NULL_ENTRY);
344 while (e_key ? 241
345 KEYS_DIFFER_P (e_key, key, test_function): 242 if (e_key)
346 e->contents == NULL_ENTRY); 243 {
347 244 e->key = 0;
348 if (e_key) 245 e->contents = NULL_ENTRY;
349 { 246 }
350 e->key = 0; 247 }
351 e->contents = NULL_ENTRY; 248
352 } 249 /* only increment the fullness when we used up a new hentry */
353 } 250 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
354 251 {
355 /* only increment the fullness when we used up a new hentry */ 252 hash_size_t comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
356 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function)) 253 if (hash_table->size < comfortable_size)
357 hash_table->fullness++; 254 grow_hash_table (hash_table, comfortable_size + 1);
255 }
256 }
358 } 257 }
359 258
360 static void 259 static void
361 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size) 260 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
362 { 261 {
370 } 269 }
371 270
372 void 271 void
373 remhash (CONST void *key, struct hash_table *hash_table) 272 remhash (CONST void *key, struct hash_table *hash_table)
374 { 273 {
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;
385
386 if (!key) 274 if (!key)
387 { 275 {
388 hash_table->zero_entry = 0; 276 hash_table->zero_entry = 0;
389 hash_table->zero_set = 0; 277 hash_table->zero_set = 0;
390 return; 278 }
391 } 279 else
392 280 {
393 if (e_key ? 281 hentry *harray = hash_table->harray;
394 KEYS_DIFFER_P (e_key, key, test_function) : 282 hash_table_test_function test_function = hash_table->test_function;
395 e->contents == NULL_ENTRY) 283 hash_size_t size = hash_table->size;
396 { 284 unsigned int hcode_initial =
397 size_t h2 = size - 2; 285 (hash_table->hash_function) ?
398 unsigned int incr = 1 + (hcode_initial % h2); 286 (hash_table->hash_function (key)) :
399 do 287 ((unsigned long) key);
400 { 288 unsigned int hcode = hcode_initial % size;
401 hcode += incr; if (hcode >= size) hcode -= size; 289 hentry *e = &harray [hcode];
402 e = &harray [hcode]; 290 CONST void *e_key = e->key;
403 e_key = e->key; 291
404 } 292 if (e_key ?
405 while (e_key? 293 KEYS_DIFFER_P (e_key, key, test_function) :
406 KEYS_DIFFER_P (e_key, key, test_function): 294 e->contents == NULL_ENTRY)
407 e->contents == NULL_ENTRY); 295 {
408 } 296 size_t h2 = size - 2;
409 if (e_key) 297 unsigned int incr = 1 + (hcode_initial % h2);
410 { 298 do
411 e->key = 0; 299 {
412 e->contents = NULL_ENTRY; 300 hcode += incr; if (hcode >= size) hcode -= size;
413 /* Note: you can't do fullness-- here, it breaks the world. */ 301 e = &harray [hcode];
302 e_key = e->key;
303 }
304 while (e_key?
305 KEYS_DIFFER_P (e_key, key, test_function):
306 e->contents == NULL_ENTRY);
307 }
308 if (e_key)
309 {
310 e->key = 0;
311 e->contents = NULL_ENTRY;
312 /* Note: you can't do fullness-- here, it breaks the world. */
313 }
414 } 314 }
415 } 315 }
416 316
417 void 317 void
418 maphash (maphash_function mf, struct hash_table *hash_table, void *arg) 318 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)