Mercurial > hg > xemacs-beta

comparison src/hash.c @ 647:b39c14581166

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[xemacs-hg @ 2001-08-13 04:45:47 by ben] removal of unsigned, size_t, etc.
author ben
date Mon, 13 Aug 2001 04:46:48 +0000
parents abe6d1db359e
children fdefd0186b75
comparison
equal deleted inserted replaced
646:00c54252fe4f 647:b39c14581166
29 #define COMFORTABLE_SIZE(size) (21 * (size) / 16) 29 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
30 30
31 #define KEYS_DIFFER_P(old, new, testfun) \ 31 #define KEYS_DIFFER_P(old, new, testfun) \
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, Element_Count size);
35 35
36 unsigned long 36 Hash_Code
37 memory_hash (const void *xv, size_t size) 37 memory_hash (const void *xv, Memory_Count size)
38 { 38 {
39 unsigned int h = 0; 39 Hash_Code 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 {
46 unsigned int g; 46 Hash_Code g;
47 h = (h << 4) + *x++; 47 h = (h << 4) + *x++;
48 if ((g = h & 0xf0000000) != 0) 48 if ((g = h & 0xf0000000) != 0)
49 h = (h ^ (g >> 24)) ^ g; 49 h = (h ^ (g >> 24)) ^ g;
50 } 50 }
51 51
52 return h; 52 return h;
53 } 53 }
54 54
55 unsigned long 55 Hash_Code
56 string_hash (const char *xv) 56 string_hash (const char *xv)
57 { 57 {
58 unsigned int h = 0; 58 Hash_Code h = 0;
59 unsigned const char *x = (unsigned const char *) xv; 59 unsigned const char *x = (unsigned const char *) xv;
60 60
61 if (!x) return 0; 61 if (!x) return 0;
62 62
63 while (*x) 63 while (*x)
64 { 64 {
65 unsigned int g; 65 Hash_Code g;
66 h = (h << 4) + *x++; 66 h = (h << 4) + *x++;
67 if ((g = h & 0xf0000000) != 0) 67 if ((g = h & 0xf0000000) != 0)
68 h = (h ^ (g >> 24)) ^ g; 68 h = (h ^ (g >> 24)) ^ g;
69 } 69 }
70 70
71 return h; 71 return h;
72 } 72 }
73 73
74 /* 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. */
75 static size_t 75 static Element_Count
76 hash_table_size (size_t requested_size) 76 hash_table_size (Element_Count requested_size)
77 { 77 {
78 /* Return some prime near, but greater than or equal to, SIZE. 78 /* Return some prime near, but greater than or equal to, SIZE.
79 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
80 enough that the list below will be too short... */ 80 enough that the list below will be too short... */
81 static const size_t primes [] = 81 static const Element_Count primes [] =
82 { 82 {
83 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,
84 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 84 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
85 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, 85 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
86 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, 86 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
87 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, 87 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
88 10445899, 13579681, 17653589, 22949669, 29834603, 38784989, 88 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
89 50420551, 65546729, 85210757, 110774011, 144006217, 187208107, 89 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
90 243370577, 316381771, 411296309, 534685237, 695090819, 903618083, 90 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
91 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL 91 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */
92 }; 92 };
93 /* We've heard of binary search. */ 93 /* We've heard of binary search. */
94 int low, high; 94 int low, high;
95 for (low = 0, high = countof (primes) - 1; high - low > 1;) 95 for (low = 0, high = countof (primes) - 1; high - low > 1;)
96 { 96 {
114 } 114 }
115 else 115 else
116 { 116 {
117 hentry *harray = hash_table->harray; 117 hentry *harray = hash_table->harray;
118 hash_table_test_function test_function = hash_table->test_function; 118 hash_table_test_function test_function = hash_table->test_function;
119 hash_size_t size = hash_table->size; 119 Element_Count size = hash_table->size;
120 unsigned int hcode_initial = 120 Hash_Code hcode_initial =
121 hash_table->hash_function ? 121 hash_table->hash_function ?
122 hash_table->hash_function (key) : 122 hash_table->hash_function (key) :
123 (unsigned long) key; 123 (Hash_Code) key;
124 unsigned int hcode = hcode_initial % size; 124 Element_Count hcode = (Element_Count) (hcode_initial % size);
125 hentry *e = &harray [hcode]; 125 hentry *e = &harray [hcode];
126 const void *e_key = e->key; 126 const void *e_key = e->key;
127 127
128 if (e_key ? 128 if (e_key ?
129 KEYS_DIFFER_P (e_key, key, test_function) : 129 KEYS_DIFFER_P (e_key, key, test_function) :
130 e->contents == NULL_ENTRY) 130 e->contents == NULL_ENTRY)
131 { 131 {
132 size_t h2 = size - 2; 132 Element_Count h2 = size - 2;
133 unsigned int incr = 1 + (hcode_initial % h2); 133 Element_Count incr = (Element_Count) (1 + (hcode_initial % h2));
134 do 134 do
135 { 135 {
136 hcode += incr; if (hcode >= size) hcode -= size; 136 hcode += incr; if (hcode >= size) hcode -= size;
137 e = &harray [hcode]; 137 e = &harray [hcode];
138 e_key = e->key; 138 e_key = e->key;
162 xfree (hash_table->harray); 162 xfree (hash_table->harray);
163 xfree (hash_table); 163 xfree (hash_table);
164 } 164 }
165 165
166 struct hash_table* 166 struct hash_table*
167 make_hash_table (hash_size_t size) 167 make_hash_table (Element_Count size)
168 { 168 {
169 struct hash_table *hash_table = xnew_and_zero (struct hash_table); 169 struct hash_table *hash_table = xnew_and_zero (struct hash_table);
170 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size)); 170 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
171 hash_table->harray = xnew_array (hentry, hash_table->size); 171 hash_table->harray = xnew_array (hentry, hash_table->size);
172 clrhash (hash_table); 172 clrhash (hash_table);
173 return hash_table; 173 return hash_table;
174 } 174 }
175 175
176 struct hash_table * 176 struct hash_table *
177 make_general_hash_table (hash_size_t size, 177 make_general_hash_table (Element_Count size,
178 hash_table_hash_function hash_function, 178 hash_table_hash_function hash_function,
179 hash_table_test_function test_function) 179 hash_table_test_function test_function)
180 { 180 {
181 struct hash_table* hash_table = make_hash_table (size); 181 struct hash_table* hash_table = make_hash_table (size);
182 hash_table->hash_function = hash_function; 182 hash_table->hash_function = hash_function;
183 hash_table->test_function = test_function; 183 hash_table->test_function = test_function;
184 return hash_table; 184 return hash_table;
185 } 185 }
186 186
187 static void 187 static void
188 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size) 188 grow_hash_table (struct hash_table *hash_table, Element_Count new_size)
189 { 189 {
190 hash_size_t old_size = hash_table->size; 190 Element_Count old_size = hash_table->size;
191 hentry *old_harray = hash_table->harray; 191 hentry *old_harray = hash_table->harray;
192 192
193 hash_table->size = hash_table_size (new_size); 193 hash_table->size = hash_table_size (new_size);
194 hash_table->harray = xnew_array (hentry, hash_table->size); 194 hash_table->harray = xnew_array (hentry, hash_table->size);
195 195
215 hash_table->zero_set = 1; 215 hash_table->zero_set = 1;
216 } 216 }
217 else 217 else
218 { 218 {
219 hash_table_test_function test_function = hash_table->test_function; 219 hash_table_test_function test_function = hash_table->test_function;
220 hash_size_t size = hash_table->size; 220 Element_Count size = hash_table->size;
221 hentry *harray = hash_table->harray; 221 hentry *harray = hash_table->harray;
222 unsigned int hcode_initial = 222 Hash_Code hcode_initial =
223 hash_table->hash_function ? 223 hash_table->hash_function ?
224 hash_table->hash_function (key) : 224 hash_table->hash_function (key) :
225 (unsigned long) key; 225 (Hash_Code) key;
226 unsigned int hcode = hcode_initial % size; 226 Element_Count hcode = (Element_Count) (hcode_initial % size);
227 size_t h2 = size - 2; 227 Element_Count h2 = size - 2;
228 unsigned int incr = 1 + (hcode_initial % h2); 228 Element_Count incr = (Element_Count) (1 + (hcode_initial % h2));
229 const void *e_key = harray [hcode].key; 229 const void *e_key = harray [hcode].key;
230 const void *oldcontents; 230 const void *oldcontents;
231 231
232 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) 232 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
233 { 233 {
266 } 266 }
267 267
268 /* only increment the fullness when we used up a new hentry */ 268 /* only increment the fullness when we used up a new hentry */
269 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function)) 269 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
270 { 270 {
271 hash_size_t comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness)); 271 Element_Count comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
272 if (hash_table->size < comfortable_size) 272 if (hash_table->size < comfortable_size)
273 grow_hash_table (hash_table, comfortable_size + 1); 273 grow_hash_table (hash_table, comfortable_size + 1);
274 } 274 }
275 } 275 }
276 } 276 }
277 277
278 static void 278 static void
279 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size) 279 rehash (hentry *harray, struct hash_table *hash_table, Element_Count size)
280 { 280 {
281 hentry *limit = harray + size; 281 hentry *limit = harray + size;
282 hentry *e; 282 hentry *e;
283 for (e = harray; e < limit; e++) 283 for (e = harray; e < limit; e++)
284 { 284 {
297 } 297 }
298 else 298 else
299 { 299 {
300 hentry *harray = hash_table->harray; 300 hentry *harray = hash_table->harray;
301 hash_table_test_function test_function = hash_table->test_function; 301 hash_table_test_function test_function = hash_table->test_function;
302 hash_size_t size = hash_table->size; 302 Element_Count size = hash_table->size;
303 unsigned int hcode_initial = 303 Hash_Code hcode_initial =
304 (hash_table->hash_function) ? 304 (hash_table->hash_function) ?
305 (hash_table->hash_function (key)) : 305 (hash_table->hash_function (key)) :
306 ((unsigned long) key); 306 ((Hash_Code) key);
307 unsigned int hcode = hcode_initial % size; 307 Element_Count hcode = (Element_Count) (hcode_initial % size);
308 hentry *e = &harray [hcode]; 308 hentry *e = &harray [hcode];
309 const void *e_key = e->key; 309 const void *e_key = e->key;
310 310
311 if (e_key ? 311 if (e_key ?
312 KEYS_DIFFER_P (e_key, key, test_function) : 312 KEYS_DIFFER_P (e_key, key, test_function) :
313 e->contents == NULL_ENTRY) 313 e->contents == NULL_ENTRY)
314 { 314 {
315 size_t h2 = size - 2; 315 Element_Count h2 = size - 2;
316 unsigned int incr = 1 + (hcode_initial % h2); 316 Element_Count incr = (Element_Count) (1 + (hcode_initial % h2));
317 do 317 do
318 { 318 {
319 hcode += incr; if (hcode >= size) hcode -= size; 319 hcode += incr; if (hcode >= size) hcode -= size;
320 e = &harray [hcode]; 320 e = &harray [hcode];
321 e_key = e->key; 321 e_key = e->key;