Mercurial > hg > xemacs-beta

comparison src/hash.c @ 442:abe6d1db359e r21-2-36

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