Mercurial > hg > xemacs-beta

comparison src/hash.c @ 412:697ef44129c6 r21-2-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-2-14
author cvs
date Mon, 13 Aug 2007 11:20:41 +0200
parents de805c49cfc1
children
comparison
equal deleted inserted replaced
411:12e008d41344 412:697ef44129c6
32 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new)))) 32 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
33 33
34 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size); 34 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
35 35
36 unsigned long 36 unsigned long
37 memory_hash (const void *xv, size_t size) 37 memory_hash (CONST void *xv, size_t size)
38 { 38 {
39 unsigned int h = 0; 39 unsigned int h = 0;
40 unsigned const char *x = (unsigned const char *) xv; 40 unsigned CONST char *x = (unsigned CONST char *) xv;
41 41
42 if (!x) return 0; 42 if (!x) return 0;
43 43
44 while (size--) 44 while (size--)
45 { 45 {
50 } 50 }
51 51
52 return h; 52 return h;
53 } 53 }
54 54
55 unsigned long
56 string_hash (const char *xv)
57 {
58 unsigned int h = 0;
59 unsigned const char *x = (unsigned const char *) xv;
60
61 if (!x) return 0;
62
63 while (*x)
64 {
65 unsigned int g;
66 h = (h << 4) + *x++;
67 if ((g = h & 0xf0000000) != 0)
68 h = (h ^ (g >> 24)) ^ g;
69 }
70
71 return h;
72 }
73
74 /* Return a suitable size for a hash table, with at least SIZE slots. */ 55 /* Return a suitable size for a hash table, with at least SIZE slots. */
75 static size_t 56 static size_t
76 hash_table_size (size_t requested_size) 57 hash_table_size (size_t requested_size)
77 { 58 {
78 /* Return some prime near, but greater than or equal to, SIZE. 59 /* Return some prime near, but greater than or equal to, SIZE.
79 Decades from the time of writing, someone will have a system large 60 Decades from the time of writing, someone will have a system large
80 enough that the list below will be too short... */ 61 enough that the list below will be too short... */
81 static const size_t primes [] = 62 static CONST size_t primes [] =
82 { 63 {
83 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, 64 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
84 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 65 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
85 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, 66 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
86 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, 67 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
102 high = mid; 83 high = mid;
103 } 84 }
104 return primes [high]; 85 return primes [high];
105 } 86 }
106 87
107 const void * 88 CONST void *
108 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)
109 { 90 {
110 if (!key) 91 if (!key)
111 { 92 {
112 *ret_value = hash_table->zero_entry; 93 *ret_value = hash_table->zero_entry;
113 return (void *) hash_table->zero_set; 94 return (void *) hash_table->zero_set;
121 hash_table->hash_function ? 102 hash_table->hash_function ?
122 hash_table->hash_function (key) : 103 hash_table->hash_function (key) :
123 (unsigned long) key; 104 (unsigned long) key;
124 unsigned int hcode = hcode_initial % size; 105 unsigned int hcode = hcode_initial % size;
125 hentry *e = &harray [hcode]; 106 hentry *e = &harray [hcode];
126 const void *e_key = e->key; 107 CONST void *e_key = e->key;
127 108
128 if (e_key ? 109 if (e_key ?
129 KEYS_DIFFER_P (e_key, key, test_function) : 110 KEYS_DIFFER_P (e_key, key, test_function) :
130 e->contents == NULL_ENTRY) 111 e->contents == NULL_ENTRY)
131 { 112 {
205 186
206 xfree (old_harray); 187 xfree (old_harray);
207 } 188 }
208 189
209 void 190 void
210 puthash (const void *key, void *contents, struct hash_table *hash_table) 191 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
211 { 192 {
212 if (!key) 193 if (!key)
213 { 194 {
214 hash_table->zero_entry = contents; 195 hash_table->zero_entry = contents;
215 hash_table->zero_set = 1; 196 hash_table->zero_set = 1;
224 hash_table->hash_function (key) : 205 hash_table->hash_function (key) :
225 (unsigned long) key; 206 (unsigned long) key;
226 unsigned int hcode = hcode_initial % size; 207 unsigned int hcode = hcode_initial % size;
227 size_t h2 = size - 2; 208 size_t h2 = size - 2;
228 unsigned int incr = 1 + (hcode_initial % h2); 209 unsigned int incr = 1 + (hcode_initial % h2);
229 const void *e_key = harray [hcode].key; 210 CONST void *e_key = harray [hcode].key;
230 const void *oldcontents; 211 CONST void *oldcontents;
231 212
232 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) 213 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
233 { 214 {
234 do 215 do
235 { 216 {
286 puthash (e->key, e->contents, hash_table); 267 puthash (e->key, e->contents, hash_table);
287 } 268 }
288 } 269 }
289 270
290 void 271 void
291 remhash (const void *key, struct hash_table *hash_table) 272 remhash (CONST void *key, struct hash_table *hash_table)
292 { 273 {
293 if (!key) 274 if (!key)
294 { 275 {
295 hash_table->zero_entry = 0; 276 hash_table->zero_entry = 0;
296 hash_table->zero_set = 0; 277 hash_table->zero_set = 0;
304 (hash_table->hash_function) ? 285 (hash_table->hash_function) ?
305 (hash_table->hash_function (key)) : 286 (hash_table->hash_function (key)) :
306 ((unsigned long) key); 287 ((unsigned long) key);
307 unsigned int hcode = hcode_initial % size; 288 unsigned int hcode = hcode_initial % size;
308 hentry *e = &harray [hcode]; 289 hentry *e = &harray [hcode];
309 const void *e_key = e->key; 290 CONST void *e_key = e->key;
310 291
311 if (e_key ? 292 if (e_key ?
312 KEYS_DIFFER_P (e_key, key, test_function) : 293 KEYS_DIFFER_P (e_key, key, test_function) :
313 e->contents == NULL_ENTRY) 294 e->contents == NULL_ENTRY)
314 { 295 {