428
+ − 1 /* Hash tables.
+ − 2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
2515
+ − 3 Copyright (C) 2003, 2004 Ben Wing.
428
+ − 4
+ − 5 This file is part of XEmacs.
+ − 6
+ − 7 XEmacs is free software; you can redistribute it and/or modify it
+ − 8 under the terms of the GNU General Public License as published by the
+ − 9 Free Software Foundation; either version 2, or (at your option) any
+ − 10 later version.
+ − 11
+ − 12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
+ − 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ − 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ − 15 for more details.
+ − 16
+ − 17 You should have received a copy of the GNU General Public License
+ − 18 along with XEmacs; see the file COPYING. If not, write to
+ − 19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ − 20 Boston, MA 02111-1307, USA. */
+ − 21
+ − 22 /* Synched up with: Not in FSF. */
+ − 23
1292
+ − 24 /* Author: Lost in the mists of history. At least back to Lucid 19.3,
+ − 25 circa Sep 1992. */
+ − 26
428
+ − 27 #include <config.h>
+ − 28 #include "lisp.h"
+ − 29 #include "hash.h"
+ − 30
1204
+ − 31 #define NULL_ENTRY ((void *) 0xdeadbeef) /* -559038737 base 10 */
428
+ − 32
+ − 33 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
+ − 34
3025
+ − 35 #define KEYS_DIFFER_P(old, new_, testfun) \
+ − 36 (((old) != (new_)) && (!(testfun) || !(testfun) ((old),(new_))))
428
+ − 37
665
+ − 38 static void rehash (hentry *harray, struct hash_table *ht, Elemcount size);
428
+ − 39
665
+ − 40 Hashcode
+ − 41 memory_hash (const void *xv, Bytecount size)
428
+ − 42 {
665
+ − 43 Hashcode h = 0;
442
+ − 44 unsigned const char *x = (unsigned const char *) xv;
428
+ − 45
+ − 46 if (!x) return 0;
+ − 47
+ − 48 while (size--)
+ − 49 {
665
+ − 50 Hashcode g;
428
+ − 51 h = (h << 4) + *x++;
+ − 52 if ((g = h & 0xf0000000) != 0)
+ − 53 h = (h ^ (g >> 24)) ^ g;
+ − 54 }
+ − 55
+ − 56 return h;
+ − 57 }
+ − 58
2515
+ − 59 static int
+ − 60 string_equal (const void *st1, const void *st2)
+ − 61 {
+ − 62 if (!st1)
+ − 63 return st2 ? 0 : 1;
+ − 64 else if (!st2)
+ − 65 return 0;
+ − 66 else
+ − 67 return !strcmp ((const char *) st1, (const char *) st2);
+ − 68 }
+ − 69
+ − 70 static Hashcode
+ − 71 string_hash (const void *xv)
442
+ − 72 {
665
+ − 73 Hashcode h = 0;
442
+ − 74 unsigned const char *x = (unsigned const char *) xv;
+ − 75
+ − 76 if (!x) return 0;
+ − 77
+ − 78 while (*x)
+ − 79 {
665
+ − 80 Hashcode g;
442
+ − 81 h = (h << 4) + *x++;
+ − 82 if ((g = h & 0xf0000000) != 0)
+ − 83 h = (h ^ (g >> 24)) ^ g;
+ − 84 }
+ − 85
+ − 86 return h;
+ − 87 }
+ − 88
428
+ − 89 /* Return a suitable size for a hash table, with at least SIZE slots. */
665
+ − 90 static Elemcount
+ − 91 hash_table_size (Elemcount requested_size)
428
+ − 92 {
+ − 93 /* Return some prime near, but greater than or equal to, SIZE.
+ − 94 Decades from the time of writing, someone will have a system large
+ − 95 enough that the list below will be too short... */
665
+ − 96 static const Elemcount primes [] =
428
+ − 97 {
+ − 98 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
+ − 99 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
+ − 100 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
+ − 101 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
+ − 102 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
+ − 103 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
+ − 104 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
+ − 105 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
647
+ − 106 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */
428
+ − 107 };
+ − 108 /* We've heard of binary search. */
+ − 109 int low, high;
+ − 110 for (low = 0, high = countof (primes) - 1; high - low > 1;)
+ − 111 {
+ − 112 /* Loop Invariant: size < primes [high] */
+ − 113 int mid = (low + high) / 2;
+ − 114 if (primes [mid] < requested_size)
+ − 115 low = mid;
+ − 116 else
+ − 117 high = mid;
+ − 118 }
+ − 119 return primes [high];
+ − 120 }
+ − 121
442
+ − 122 const void *
+ − 123 gethash (const void *key, struct hash_table *hash_table, const void **ret_value)
428
+ − 124 {
+ − 125 if (!key)
+ − 126 {
+ − 127 *ret_value = hash_table->zero_entry;
+ − 128 return (void *) hash_table->zero_set;
+ − 129 }
+ − 130 else
+ − 131 {
+ − 132 hentry *harray = hash_table->harray;
+ − 133 hash_table_test_function test_function = hash_table->test_function;
665
+ − 134 Elemcount size = hash_table->size;
+ − 135 Hashcode hcode_initial =
428
+ − 136 hash_table->hash_function ?
+ − 137 hash_table->hash_function (key) :
665
+ − 138 (Hashcode) key;
+ − 139 Elemcount hcode = (Elemcount) (hcode_initial % size);
428
+ − 140 hentry *e = &harray [hcode];
442
+ − 141 const void *e_key = e->key;
428
+ − 142
+ − 143 if (e_key ?
+ − 144 KEYS_DIFFER_P (e_key, key, test_function) :
+ − 145 e->contents == NULL_ENTRY)
+ − 146 {
665
+ − 147 Elemcount h2 = size - 2;
+ − 148 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2));
428
+ − 149 do
+ − 150 {
+ − 151 hcode += incr; if (hcode >= size) hcode -= size;
+ − 152 e = &harray [hcode];
+ − 153 e_key = e->key;
+ − 154 }
+ − 155 while (e_key ?
+ − 156 KEYS_DIFFER_P (e_key, key, test_function) :
+ − 157 e->contents == NULL_ENTRY);
+ − 158 }
+ − 159
+ − 160 *ret_value = e->contents;
+ − 161 return e->key;
+ − 162 }
+ − 163 }
+ − 164
+ − 165 void
+ − 166 clrhash (struct hash_table *hash_table)
+ − 167 {
+ − 168 memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
+ − 169 hash_table->zero_entry = 0;
+ − 170 hash_table->zero_set = 0;
+ − 171 hash_table->fullness = 0;
+ − 172 }
+ − 173
+ − 174 void
+ − 175 free_hash_table (struct hash_table *hash_table)
+ − 176 {
1726
+ − 177 xfree (hash_table->harray, hentry *);
+ − 178 xfree (hash_table, struct hash_table *);
428
+ − 179 }
+ − 180
2515
+ − 181 struct hash_table *
665
+ − 182 make_hash_table (Elemcount size)
428
+ − 183 {
+ − 184 struct hash_table *hash_table = xnew_and_zero (struct hash_table);
+ − 185 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
+ − 186 hash_table->harray = xnew_array (hentry, hash_table->size);
+ − 187 clrhash (hash_table);
+ − 188 return hash_table;
+ − 189 }
+ − 190
+ − 191 struct hash_table *
2515
+ − 192 make_string_hash_table (Elemcount size)
+ − 193 {
+ − 194 return make_general_hash_table (size, string_hash, string_equal);
+ − 195 }
+ − 196
+ − 197 struct hash_table *
665
+ − 198 make_general_hash_table (Elemcount size,
428
+ − 199 hash_table_hash_function hash_function,
+ − 200 hash_table_test_function test_function)
+ − 201 {
+ − 202 struct hash_table* hash_table = make_hash_table (size);
+ − 203 hash_table->hash_function = hash_function;
+ − 204 hash_table->test_function = test_function;
+ − 205 return hash_table;
+ − 206 }
+ − 207
+ − 208 static void
665
+ − 209 grow_hash_table (struct hash_table *hash_table, Elemcount new_size)
428
+ − 210 {
665
+ − 211 Elemcount old_size = hash_table->size;
428
+ − 212 hentry *old_harray = hash_table->harray;
+ − 213
+ − 214 hash_table->size = hash_table_size (new_size);
+ − 215 hash_table->harray = xnew_array (hentry, hash_table->size);
+ − 216
+ − 217 /* do the rehash on the "grown" table */
+ − 218 {
+ − 219 long old_zero_set = hash_table->zero_set;
+ − 220 void *old_zero_entry = hash_table->zero_entry;
+ − 221 clrhash (hash_table);
+ − 222 hash_table->zero_set = old_zero_set;
+ − 223 hash_table->zero_entry = old_zero_entry;
+ − 224 rehash (old_harray, hash_table, old_size);
+ − 225 }
+ − 226
1726
+ − 227 xfree (old_harray, hentry *);
428
+ − 228 }
+ − 229
+ − 230 void
1292
+ − 231 pregrow_hash_table_if_necessary (struct hash_table *hash_table,
+ − 232 Elemcount breathing_room)
+ − 233 {
+ − 234 Elemcount comfortable_size = COMFORTABLE_SIZE (hash_table->fullness);
+ − 235 if (hash_table->size < comfortable_size - breathing_room)
+ − 236 grow_hash_table (hash_table, comfortable_size + 1);
+ − 237 }
+ − 238
+ − 239 void
442
+ − 240 puthash (const void *key, void *contents, struct hash_table *hash_table)
428
+ − 241 {
+ − 242 if (!key)
+ − 243 {
+ − 244 hash_table->zero_entry = contents;
+ − 245 hash_table->zero_set = 1;
+ − 246 }
+ − 247 else
+ − 248 {
+ − 249 hash_table_test_function test_function = hash_table->test_function;
665
+ − 250 Elemcount size = hash_table->size;
428
+ − 251 hentry *harray = hash_table->harray;
665
+ − 252 Hashcode hcode_initial =
428
+ − 253 hash_table->hash_function ?
+ − 254 hash_table->hash_function (key) :
665
+ − 255 (Hashcode) key;
+ − 256 Elemcount hcode = (Elemcount) (hcode_initial % size);
+ − 257 Elemcount h2 = size - 2;
+ − 258 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2));
442
+ − 259 const void *e_key = harray [hcode].key;
+ − 260 const void *oldcontents;
428
+ − 261
+ − 262 if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
+ − 263 {
+ − 264 do
+ − 265 {
+ − 266 hcode += incr; if (hcode >= size) hcode -= size;
+ − 267 e_key = harray [hcode].key;
+ − 268 }
+ − 269 while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
+ − 270 }
+ − 271 oldcontents = harray [hcode].contents;
+ − 272 harray [hcode].key = key;
+ − 273 harray [hcode].contents = contents;
+ − 274 /* If the entry that we used was a deleted entry,
+ − 275 check for a non deleted entry of the same key,
+ − 276 then delete it. */
+ − 277 if (!e_key && oldcontents == NULL_ENTRY)
+ − 278 {
+ − 279 hentry *e;
+ − 280
+ − 281 do
+ − 282 {
+ − 283 hcode += incr; if (hcode >= size) hcode -= size;
+ − 284 e = &harray [hcode];
+ − 285 e_key = e->key;
+ − 286 }
+ − 287 while (e_key ?
+ − 288 KEYS_DIFFER_P (e_key, key, test_function):
+ − 289 e->contents == NULL_ENTRY);
+ − 290
+ − 291 if (e_key)
+ − 292 {
+ − 293 e->key = 0;
+ − 294 e->contents = NULL_ENTRY;
+ − 295 }
+ − 296 }
+ − 297
+ − 298 /* only increment the fullness when we used up a new hentry */
+ − 299 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
+ − 300 {
665
+ − 301 Elemcount comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
428
+ − 302 if (hash_table->size < comfortable_size)
+ − 303 grow_hash_table (hash_table, comfortable_size + 1);
+ − 304 }
+ − 305 }
+ − 306 }
+ − 307
+ − 308 static void
665
+ − 309 rehash (hentry *harray, struct hash_table *hash_table, Elemcount size)
428
+ − 310 {
+ − 311 hentry *limit = harray + size;
+ − 312 hentry *e;
+ − 313 for (e = harray; e < limit; e++)
+ − 314 {
+ − 315 if (e->key)
+ − 316 puthash (e->key, e->contents, hash_table);
+ − 317 }
+ − 318 }
+ − 319
+ − 320 void
442
+ − 321 remhash (const void *key, struct hash_table *hash_table)
428
+ − 322 {
+ − 323 if (!key)
+ − 324 {
+ − 325 hash_table->zero_entry = 0;
+ − 326 hash_table->zero_set = 0;
+ − 327 }
+ − 328 else
+ − 329 {
+ − 330 hentry *harray = hash_table->harray;
+ − 331 hash_table_test_function test_function = hash_table->test_function;
665
+ − 332 Elemcount size = hash_table->size;
+ − 333 Hashcode hcode_initial =
428
+ − 334 (hash_table->hash_function) ?
+ − 335 (hash_table->hash_function (key)) :
665
+ − 336 ((Hashcode) key);
+ − 337 Elemcount hcode = (Elemcount) (hcode_initial % size);
428
+ − 338 hentry *e = &harray [hcode];
442
+ − 339 const void *e_key = e->key;
428
+ − 340
+ − 341 if (e_key ?
+ − 342 KEYS_DIFFER_P (e_key, key, test_function) :
+ − 343 e->contents == NULL_ENTRY)
+ − 344 {
665
+ − 345 Elemcount h2 = size - 2;
+ − 346 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2));
428
+ − 347 do
+ − 348 {
+ − 349 hcode += incr; if (hcode >= size) hcode -= size;
+ − 350 e = &harray [hcode];
+ − 351 e_key = e->key;
+ − 352 }
+ − 353 while (e_key?
+ − 354 KEYS_DIFFER_P (e_key, key, test_function):
+ − 355 e->contents == NULL_ENTRY);
+ − 356 }
+ − 357 if (e_key)
+ − 358 {
+ − 359 e->key = 0;
+ − 360 e->contents = NULL_ENTRY;
+ − 361 /* Note: you can't do fullness-- here, it breaks the world. */
+ − 362 }
+ − 363 }
+ − 364 }
+ − 365
+ − 366 void
+ − 367 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
+ − 368 {
+ − 369 hentry *e;
+ − 370 hentry *limit;
+ − 371
+ − 372 if (hash_table->zero_set)
+ − 373 {
+ − 374 if (mf (0, hash_table->zero_entry, arg))
+ − 375 return;
+ − 376 }
+ − 377
+ − 378 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
+ − 379 {
+ − 380 if (e->key && mf (e->key, e->contents, arg))
+ − 381 return;
+ − 382 }
+ − 383 }
+ − 384
+ − 385 void
+ − 386 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
+ − 387 {
+ − 388 hentry *e;
+ − 389 hentry *limit;
+ − 390
+ − 391 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
+ − 392 {
+ − 393 hash_table->zero_set = 0;
+ − 394 hash_table->zero_entry = 0;
+ − 395 }
+ − 396
+ − 397 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
+ − 398 if (predicate (e->key, e->contents, arg))
+ − 399 {
+ − 400 e->key = 0;
+ − 401 e->contents = NULL_ENTRY;
+ − 402 }
+ − 403 }