git.chise.org Git - chise/xemacs-chise.git.1/blob - src/hash.c

   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 "hash.h"
  36
  37 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
  38
  39 /* Knuth volume 3, hash functions */
  40 #define WORD_HASH_4(word) (0x9c406b55 * (word))
  41 #define WORD_HASH_8(word) (0x9c406b549c406b55 * (word))
  42
  43 static CONST hash_size_t
  44 primes [] =
  45 {
  46   13,
  47   29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,
  48   761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
  49   8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361,
  50   62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449,
  51   389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
  52   2009191, 2411033, 2893249
  53 };
  54
  55 #if 0
  56 static CONST hash_size_t
  57 primes [] =
  58 {
  59  29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, 1361,
  60  1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 19219, 24989,
  61  32491, 42257, 54941, 71429, 92861, 120721, 156941, 204047, 265271,
  62  344857, 448321, 582821, 757693, 985003, 1280519, 1664681, 2164111,
  63  2813353, 3657361, 4754591, 6180989, 8035301, 10445899, 13579681,
  64  17653589, 22949669, 29834603, 38784989, 50420551, 65546729, 85210757,
  65  110774011, 144006217, 187208107, 243370577, 316381771, 411296309,
  66  534685237, 695090819, 903618083, 1174703521, 1527114613, 1985248999,
  67  2580823717, 3355070839, 4361592119
  68 };
  69 #endif
  70
  71 unsigned long
  72 memory_hash (CONST void *xv, size_t size)
  73 {
  74   unsigned int h = 0;
  75   unsigned CONST char *x = (unsigned CONST char *) xv;
  76
  77   if (!x) return 0;
  78
  79   while (size--)
  80     {
  81       unsigned int g;
  82       h = (h << 4) + *x++;
  83       if ((g = h & 0xf0000000) != 0)
  84         h = (h ^ (g >> 24)) ^ g;
  85     }
  86
  87   return h;
  88 }
  89
  90 /* We've heard of binary search. */
  91 static hash_size_t
  92 prime_size (hash_size_t size)
  93 {
  94   int low, high;
  95   for (low = 0, high = countof (primes) - 1; high - low > 1;)
  96     {
  97       /* Loop Invariant: size < primes [high] */
  98       int mid = (low + high) / 2;
  99       if (primes [mid] < size)
 100         low = mid;
 101       else
 102         high = mid;
 103     }
 104   return primes [high];
 105 }
 106
 107 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
 108
 109 #define KEYS_DIFFER_P(old, new, testfun) \
 110   (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
 111
 112 CONST void *
 113 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value)
 114 {
 115   hentry *harray = hash_table->harray;
 116   hash_table_test_function test_function = hash_table->test_function;
 117   hash_size_t size = hash_table->size;
 118   unsigned int hcode_initial =
 119     hash_table->hash_function ?
 120     hash_table->hash_function (key) :
 121     (unsigned long) key;
 122   unsigned int hcode = hcode_initial % size;
 123   hentry *e = &harray [hcode];
 124   CONST void *e_key = e->key;
 125
 126   if (!key)
 127     {
 128       *ret_value = hash_table->zero_entry;
 129       return (void *) hash_table->zero_set;
 130     }
 131
 132   if (e_key ?
 133       KEYS_DIFFER_P (e_key, key, test_function) :
 134       e->contents == NULL_ENTRY)
 135     {
 136       size_t h2 = size - 2;
 137       unsigned int incr = 1 + (hcode_initial % h2);
 138       do
 139         {
 140           hcode += incr; if (hcode >= size) hcode -= size;
 141           e = &harray [hcode];
 142           e_key = e->key;
 143         }
 144       while (e_key ?
 145              KEYS_DIFFER_P (e_key, key, test_function) :
 146              e->contents == NULL_ENTRY);
 147     }
 148
 149   *ret_value = e->contents;
 150   return e->key;
 151 }
 152
 153 void
 154 clrhash (struct hash_table *hash_table)
 155 {
 156   memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
 157   hash_table->zero_entry = 0;
 158   hash_table->zero_set   = 0;
 159   hash_table->fullness   = 0;
 160 }
 161
 162 void
 163 free_hash_table (struct hash_table *hash_table)
 164 {
 165   xfree (hash_table->harray);
 166   xfree (hash_table);
 167 }
 168
 169 struct hash_table*
 170 make_hash_table (hash_size_t size)
 171 {
 172   struct hash_table *hash_table = xnew_and_zero (struct hash_table);
 173   hash_table->size = prime_size (COMFORTABLE_SIZE (size));
 174   hash_table->harray = xnew_array (hentry, hash_table->size);
 175   clrhash (hash_table);
 176   return hash_table;
 177 }
 178
 179 struct hash_table *
 180 make_general_hash_table (hash_size_t size,
 181                         hash_table_hash_function hash_function,
 182                         hash_table_test_function test_function)
 183 {
 184   struct hash_table* hash_table = make_hash_table (size);
 185   hash_table->hash_function = hash_function;
 186   hash_table->test_function = test_function;
 187   return hash_table;
 188 }
 189
 190 #if 0 /* unused strings code */
 191 struct hash_table *
 192 make_strings_hash_table (hash_size_t size)
 193 {
 194   return make_general_hash_table (size, string_hash, string_eq);
 195 }
 196
 197 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
 198 unsigned long
 199 string_hash (CONST void *xv)
 200 {
 201   unsigned int h = 0;
 202   unsigned CONST char *x = (unsigned CONST char *) xv;
 203
 204   if (!x) return 0;
 205
 206   while (*x != 0)
 207     {
 208       unsigned int g;
 209       h = (h << 4) + *x++;
 210       if ((g = h & 0xf0000000) != 0)
 211         h = (h ^ (g >> 24)) ^ g;
 212     }
 213
 214   return h;
 215 }
 216
 217 static int
 218 string_eq (CONST void *s1, CONST void *s2)
 219 {
 220   return s1 && s2 ? !strcmp ((CONST char *) s1, (CONST char *) s2) : s1 == s2;
 221 }
 222 #endif /* unused strings code */
 223
 224 void
 225 copy_hash (struct hash_table *dest, struct hash_table *src)
 226 {
 227   if (dest->size != src->size)
 228     {
 229       xfree (dest->harray);
 230
 231       dest->size = src->size;
 232       dest->harray = xnew_array (hentry, dest->size);
 233     }
 234   dest->fullness      = src->fullness;
 235   dest->zero_entry    = src->zero_entry;
 236   dest->zero_set      = src->zero_set;
 237   dest->hash_function = src->hash_function;
 238   dest->test_function = src->test_function;
 239   memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
 240 }
 241
 242 static void
 243 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
 244 {
 245   hash_size_t old_size   = hash_table->size;
 246   hentry     *old_harray = hash_table->harray;
 247   hentry     *new_harray;
 248
 249   new_size = prime_size (new_size);
 250
 251   new_harray = xnew_array (hentry, new_size);
 252
 253   hash_table->size   = new_size;
 254   hash_table->harray = new_harray;
 255
 256   /* do the rehash on the "grown" table */
 257   {
 258     long old_zero_set    = hash_table->zero_set;
 259     void *old_zero_entry = hash_table->zero_entry;
 260     clrhash (hash_table);
 261     hash_table->zero_set   = old_zero_set;
 262     hash_table->zero_entry = old_zero_entry;
 263     rehash (old_harray, hash_table, old_size);
 264   }
 265
 266   xfree (old_harray);
 267 }
 268
 269 void
 270 expand_hash_table (struct hash_table *hash_table, hash_size_t needed_size)
 271 {
 272   hash_size_t size = hash_table->size;
 273   hash_size_t comfortable_size = COMFORTABLE_SIZE (needed_size);
 274   if (size < comfortable_size)
 275     grow_hash_table (hash_table, comfortable_size + 1);
 276 }
 277
 278 void
 279 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
 280 {
 281   hash_table_test_function test_function = hash_table->test_function;
 282   hash_size_t size     = hash_table->size;
 283   hash_size_t fullness = hash_table->fullness;
 284   hentry *harray;
 285   CONST void *e_key;
 286   hentry *e;
 287   unsigned int hcode_initial =
 288     hash_table->hash_function ?
 289     hash_table->hash_function (key) :
 290     (unsigned long) key;
 291   unsigned int hcode;
 292   unsigned int incr = 0;
 293   size_t h2;
 294   CONST void *oldcontents;
 295
 296   if (!key)
 297     {
 298       hash_table->zero_entry = contents;
 299       hash_table->zero_set = 1;
 300       return;
 301     }
 302
 303   if (size < (1 + COMFORTABLE_SIZE (fullness)))
 304     {
 305       grow_hash_table (hash_table, size + 1);
 306       size = hash_table->size;
 307       fullness = hash_table->fullness;
 308     }
 309
 310   harray= hash_table->harray;
 311   h2 = size - 2;
 312
 313   hcode = hcode_initial % size;
 314
 315   e_key = harray [hcode].key;
 316   if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
 317     {
 318       h2 = size - 2;
 319       incr = 1 + (hcode_initial % h2);
 320       do
 321         {
 322           hcode += incr;
 323           if (hcode >= size) hcode -= size;
 324           e_key = harray [hcode].key;
 325         }
 326       while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
 327     }
 328   oldcontents = harray [hcode].contents;
 329   harray [hcode].key = key;
 330   harray [hcode].contents = contents;
 331   /* If the entry that we used was a deleted entry,
 332      check for a non deleted entry of the same key,
 333      then delete it. */
 334   if (!e_key && oldcontents == NULL_ENTRY)
 335     {
 336       if (!incr) incr = 1 + ((unsigned long) key % h2);
 337
 338       do
 339         {
 340           hcode += incr; if (hcode >= size) hcode -= size;
 341           e = &harray [hcode];
 342           e_key = e->key;
 343         }
 344       while (e_key ?
 345              KEYS_DIFFER_P (e_key, key, test_function):
 346              e->contents == NULL_ENTRY);
 347
 348       if (e_key)
 349         {
 350           e->key = 0;
 351           e->contents = NULL_ENTRY;
 352         }
 353     }
 354
 355   /* only increment the fullness when we used up a new hentry */
 356   if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
 357     hash_table->fullness++;
 358 }
 359
 360 static void
 361 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
 362 {
 363   hentry *limit = harray + size;
 364   hentry *e;
 365   for (e = harray; e < limit; e++)
 366     {
 367       if (e->key)
 368         puthash (e->key, e->contents, hash_table);
 369     }
 370 }
 371
 372 void
 373 remhash (CONST void *key, struct hash_table *hash_table)
 374 {
 375   hentry *harray = hash_table->harray;
 376   hash_table_test_function test_function = hash_table->test_function;
 377   hash_size_t size = hash_table->size;
 378   unsigned int hcode_initial =
 379     (hash_table->hash_function) ?
 380     (hash_table->hash_function (key)) :
 381     ((unsigned long) key);
 382   unsigned int hcode = hcode_initial % size;
 383   hentry *e = &harray [hcode];
 384   CONST void *e_key = e->key;
 385
 386   if (!key)
 387     {
 388       hash_table->zero_entry = 0;
 389       hash_table->zero_set = 0;
 390       return;
 391     }
 392
 393   if (e_key ?
 394       KEYS_DIFFER_P (e_key, key, test_function) :
 395       e->contents == NULL_ENTRY)
 396     {
 397       size_t h2 = size - 2;
 398       unsigned int incr = 1 + (hcode_initial % h2);
 399       do
 400         {
 401           hcode += incr; if (hcode >= size) hcode -= size;
 402           e = &harray [hcode];
 403           e_key = e->key;
 404         }
 405       while (e_key?
 406              KEYS_DIFFER_P (e_key, key, test_function):
 407              e->contents == NULL_ENTRY);
 408     }
 409   if (e_key)
 410     {
 411       e->key = 0;
 412       e->contents = NULL_ENTRY;
 413       /* Note: you can't do fullness-- here, it breaks the world. */
 414     }
 415 }
 416
 417 void
 418 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
 419 {
 420   hentry *e;
 421   hentry *limit;
 422
 423   if (hash_table->zero_set)
 424     {
 425       if (mf (0, hash_table->zero_entry, arg))
 426         return;
 427     }
 428
 429   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 430     {
 431       if (e->key && mf (e->key, e->contents, arg))
 432         return;
 433     }
 434 }
 435
 436 void
 437 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
 438 {
 439   hentry *e;
 440   hentry *limit;
 441
 442   if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
 443     {
 444       hash_table->zero_set = 0;
 445       hash_table->zero_entry = 0;
 446     }
 447
 448   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 449     if (predicate (e->key, e->contents, arg))
 450       {
 451         e->key = 0;
 452         e->contents = NULL_ENTRY;
 453       }
 454 }