Mercurial > hg > xemacs-beta

comparison src/hash.c @ 0:376386a54a3c r19-14

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