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 #include <config.h>
  24 #include "lisp.h"
  25 #include "hash.h"
  26
  27 #define NULL_ENTRY ((void *) 0xdeadbeef)
  28
  29 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
  30
  31 #define KEYS_DIFFER_P(old, new, testfun) \
  32   (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
  33
  34 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
  35
  36 unsigned long
  37 memory_hash (CONST void *xv, size_t size)
  38 {
  39   unsigned int h = 0;
  40   unsigned CONST char *x = (unsigned CONST char *) xv;
  41
  42   if (!x) return 0;
  43
  44   while (size--)
  45     {
  46       unsigned int g;
  47       h = (h << 4) + *x++;
  48       if ((g = h & 0xf0000000) != 0)
  49         h = (h ^ (g >> 24)) ^ g;
  50     }
  51
  52   return h;
  53 }
  54
  55 /* Return a suitable size for a hash table, with at least SIZE slots. */
  56 static size_t
  57 hash_table_size (size_t requested_size)
  58 {
  59   /* Return some prime near, but greater than or equal to, SIZE.
  60      Decades from the time of writing, someone will have a system large
  61      enough that the list below will be too short... */
  62   static CONST size_t primes [] =
  63   {
  64     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,
  66     19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
  67     204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
  68     1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
  69     10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
  70     50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
  71     243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
  72     1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
  73   };
  74   /* We've heard of binary search. */
  75   int low, high;
  76   for (low = 0, high = countof (primes) - 1; high - low > 1;)
  77     {
  78       /* Loop Invariant: size < primes [high] */
  79       int mid = (low + high) / 2;
  80       if (primes [mid] < requested_size)
  81         low = mid;
  82       else
  83         high = mid;
  84     }
  85   return primes [high];
  86 }
  87
  88 CONST void *
  89 gethash (CONST void *key, struct hash_table *hash_table, CONST void **ret_value)
  90 {
  91   if (!key)
  92     {
  93       *ret_value = hash_table->zero_entry;
  94       return (void *) hash_table->zero_set;
  95     }
  96   else
  97     {
  98       hentry *harray = hash_table->harray;
  99       hash_table_test_function test_function = hash_table->test_function;
 100       hash_size_t size = hash_table->size;
 101       unsigned int hcode_initial =
 102         hash_table->hash_function ?
 103         hash_table->hash_function (key) :
 104         (unsigned long) key;
 105       unsigned int hcode = hcode_initial % size;
 106       hentry *e = &harray [hcode];
 107       CONST void *e_key = e->key;
 108
 109       if (e_key ?
 110           KEYS_DIFFER_P (e_key, key, test_function) :
 111           e->contents == NULL_ENTRY)
 112         {
 113           size_t h2 = size - 2;
 114           unsigned int incr = 1 + (hcode_initial % h2);
 115           do
 116             {
 117               hcode += incr; if (hcode >= size) hcode -= size;
 118               e = &harray [hcode];
 119               e_key = e->key;
 120             }
 121           while (e_key ?
 122                  KEYS_DIFFER_P (e_key, key, test_function) :
 123                  e->contents == NULL_ENTRY);
 124         }
 125
 126       *ret_value = e->contents;
 127       return e->key;
 128     }
 129 }
 130
 131 void
 132 clrhash (struct hash_table *hash_table)
 133 {
 134   memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
 135   hash_table->zero_entry = 0;
 136   hash_table->zero_set   = 0;
 137   hash_table->fullness   = 0;
 138 }
 139
 140 void
 141 free_hash_table (struct hash_table *hash_table)
 142 {
 143   xfree (hash_table->harray);
 144   xfree (hash_table);
 145 }
 146
 147 struct hash_table*
 148 make_hash_table (hash_size_t size)
 149 {
 150   struct hash_table *hash_table = xnew_and_zero (struct hash_table);
 151   hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
 152   hash_table->harray = xnew_array (hentry, hash_table->size);
 153   clrhash (hash_table);
 154   return hash_table;
 155 }
 156
 157 struct hash_table *
 158 make_general_hash_table (hash_size_t size,
 159                         hash_table_hash_function hash_function,
 160                         hash_table_test_function test_function)
 161 {
 162   struct hash_table* hash_table = make_hash_table (size);
 163   hash_table->hash_function = hash_function;
 164   hash_table->test_function = test_function;
 165   return hash_table;
 166 }
 167
 168 static void
 169 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
 170 {
 171   hash_size_t old_size   = hash_table->size;
 172   hentry     *old_harray = hash_table->harray;
 173
 174   hash_table->size   = hash_table_size (new_size);
 175   hash_table->harray = xnew_array (hentry, hash_table->size);
 176
 177   /* do the rehash on the "grown" table */
 178   {
 179     long old_zero_set    = hash_table->zero_set;
 180     void *old_zero_entry = hash_table->zero_entry;
 181     clrhash (hash_table);
 182     hash_table->zero_set   = old_zero_set;
 183     hash_table->zero_entry = old_zero_entry;
 184     rehash (old_harray, hash_table, old_size);
 185   }
 186
 187   xfree (old_harray);
 188 }
 189
 190 void
 191 puthash (CONST void *key, void *contents, struct hash_table *hash_table)
 192 {
 193   if (!key)
 194     {
 195       hash_table->zero_entry = contents;
 196       hash_table->zero_set = 1;
 197     }
 198   else
 199     {
 200       hash_table_test_function test_function = hash_table->test_function;
 201       hash_size_t size = hash_table->size;
 202       hentry *harray   = hash_table->harray;
 203       unsigned int hcode_initial =
 204         hash_table->hash_function ?
 205         hash_table->hash_function (key) :
 206         (unsigned long) key;
 207       unsigned int hcode = hcode_initial % size;
 208       size_t h2 = size - 2;
 209       unsigned int incr = 1 + (hcode_initial % h2);
 210       CONST void *e_key = harray [hcode].key;
 211       CONST void *oldcontents;
 212
 213       if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
 214         {
 215           do
 216             {
 217               hcode += incr; if (hcode >= size) hcode -= size;
 218               e_key = harray [hcode].key;
 219             }
 220           while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
 221         }
 222       oldcontents = harray [hcode].contents;
 223       harray [hcode].key = key;
 224       harray [hcode].contents = contents;
 225       /* If the entry that we used was a deleted entry,
 226          check for a non deleted entry of the same key,
 227          then delete it. */
 228       if (!e_key && oldcontents == NULL_ENTRY)
 229         {
 230           hentry *e;
 231
 232           do
 233             {
 234               hcode += incr; if (hcode >= size) hcode -= size;
 235               e = &harray [hcode];
 236               e_key = e->key;
 237             }
 238           while (e_key ?
 239                  KEYS_DIFFER_P (e_key, key, test_function):
 240                  e->contents == NULL_ENTRY);
 241
 242           if (e_key)
 243             {
 244               e->key = 0;
 245               e->contents = NULL_ENTRY;
 246             }
 247         }
 248
 249       /* only increment the fullness when we used up a new hentry */
 250       if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
 251         {
 252           hash_size_t comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
 253           if (hash_table->size < comfortable_size)
 254             grow_hash_table (hash_table, comfortable_size + 1);
 255         }
 256     }
 257 }
 258
 259 static void
 260 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
 261 {
 262   hentry *limit = harray + size;
 263   hentry *e;
 264   for (e = harray; e < limit; e++)
 265     {
 266       if (e->key)
 267         puthash (e->key, e->contents, hash_table);
 268     }
 269 }
 270
 271 void
 272 remhash (CONST void *key, struct hash_table *hash_table)
 273 {
 274   if (!key)
 275     {
 276       hash_table->zero_entry = 0;
 277       hash_table->zero_set = 0;
 278     }
 279   else
 280     {
 281       hentry *harray = hash_table->harray;
 282       hash_table_test_function test_function = hash_table->test_function;
 283       hash_size_t size = hash_table->size;
 284       unsigned int hcode_initial =
 285         (hash_table->hash_function) ?
 286         (hash_table->hash_function (key)) :
 287         ((unsigned long) key);
 288       unsigned int hcode = hcode_initial % size;
 289       hentry *e = &harray [hcode];
 290       CONST void *e_key = e->key;
 291
 292       if (e_key ?
 293           KEYS_DIFFER_P (e_key, key, test_function) :
 294           e->contents == NULL_ENTRY)
 295         {
 296           size_t h2 = size - 2;
 297           unsigned int incr = 1 + (hcode_initial % h2);
 298           do
 299             {
 300               hcode += incr; if (hcode >= size) hcode -= size;
 301               e = &harray [hcode];
 302               e_key = e->key;
 303             }
 304           while (e_key?
 305                  KEYS_DIFFER_P (e_key, key, test_function):
 306                  e->contents == NULL_ENTRY);
 307         }
 308       if (e_key)
 309         {
 310           e->key = 0;
 311           e->contents = NULL_ENTRY;
 312           /* Note: you can't do fullness-- here, it breaks the world. */
 313         }
 314     }
 315 }
 316
 317 void
 318 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
 319 {
 320   hentry *e;
 321   hentry *limit;
 322
 323   if (hash_table->zero_set)
 324     {
 325       if (mf (0, hash_table->zero_entry, arg))
 326         return;
 327     }
 328
 329   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 330     {
 331       if (e->key && mf (e->key, e->contents, arg))
 332         return;
 333     }
 334 }
 335
 336 void
 337 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
 338 {
 339   hentry *e;
 340   hentry *limit;
 341
 342   if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
 343     {
 344       hash_table->zero_set = 0;
 345       hash_table->zero_entry = 0;
 346     }
 347
 348   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 349     if (predicate (e->key, e->contents, arg))
 350       {
 351         e->key = 0;
 352         e->contents = NULL_ENTRY;
 353       }
 354 }