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 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
  74 /* Return a suitable size for a hash table, with at least SIZE slots. */
  75 static size_t
  76 hash_table_size (size_t requested_size)
  77 {
  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
  80      enough that the list below will be too short... */
  81   static const size_t primes [] =
  82   {
  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,
  85     19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
  86     204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
  87     1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
  88     10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
  89     50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
  90     243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
  91     1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
  92   };
  93   /* We've heard of binary search. */
  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] < requested_size)
 100         low = mid;
 101       else
 102         high = mid;
 103     }
 104   return primes [high];
 105 }
 106
 107 const void *
 108 gethash (const void *key, struct hash_table *hash_table, const void **ret_value)
 109 {
 110   if (!key)
 111     {
 112       *ret_value = hash_table->zero_entry;
 113       return (void *) hash_table->zero_set;
 114     }
 115   else
 116     {
 117       hentry *harray = hash_table->harray;
 118       hash_table_test_function test_function = hash_table->test_function;
 119       hash_size_t size = hash_table->size;
 120       unsigned int hcode_initial =
 121         hash_table->hash_function ?
 122         hash_table->hash_function (key) :
 123         (unsigned long) key;
 124       unsigned int hcode = hcode_initial % size;
 125       hentry *e = &harray [hcode];
 126       const void *e_key = e->key;
 127
 128       if (e_key ?
 129           KEYS_DIFFER_P (e_key, key, test_function) :
 130           e->contents == NULL_ENTRY)
 131         {
 132           size_t h2 = size - 2;
 133           unsigned int incr = 1 + (hcode_initial % h2);
 134           do
 135             {
 136               hcode += incr; if (hcode >= size) hcode -= size;
 137               e = &harray [hcode];
 138               e_key = e->key;
 139             }
 140           while (e_key ?
 141                  KEYS_DIFFER_P (e_key, key, test_function) :
 142                  e->contents == NULL_ENTRY);
 143         }
 144
 145       *ret_value = e->contents;
 146       return e->key;
 147     }
 148 }
 149
 150 void
 151 clrhash (struct hash_table *hash_table)
 152 {
 153   memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
 154   hash_table->zero_entry = 0;
 155   hash_table->zero_set   = 0;
 156   hash_table->fullness   = 0;
 157 }
 158
 159 void
 160 free_hash_table (struct hash_table *hash_table)
 161 {
 162   xfree (hash_table->harray);
 163   xfree (hash_table);
 164 }
 165
 166 struct hash_table*
 167 make_hash_table (hash_size_t size)
 168 {
 169   struct hash_table *hash_table = xnew_and_zero (struct hash_table);
 170   hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
 171   hash_table->harray = xnew_array (hentry, hash_table->size);
 172   clrhash (hash_table);
 173   return hash_table;
 174 }
 175
 176 struct hash_table *
 177 make_general_hash_table (hash_size_t size,
 178                         hash_table_hash_function hash_function,
 179                         hash_table_test_function test_function)
 180 {
 181   struct hash_table* hash_table = make_hash_table (size);
 182   hash_table->hash_function = hash_function;
 183   hash_table->test_function = test_function;
 184   return hash_table;
 185 }
 186
 187 static void
 188 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
 189 {
 190   hash_size_t old_size   = hash_table->size;
 191   hentry     *old_harray = hash_table->harray;
 192
 193   hash_table->size   = hash_table_size (new_size);
 194   hash_table->harray = xnew_array (hentry, hash_table->size);
 195
 196   /* do the rehash on the "grown" table */
 197   {
 198     long old_zero_set    = hash_table->zero_set;
 199     void *old_zero_entry = hash_table->zero_entry;
 200     clrhash (hash_table);
 201     hash_table->zero_set   = old_zero_set;
 202     hash_table->zero_entry = old_zero_entry;
 203     rehash (old_harray, hash_table, old_size);
 204   }
 205
 206   xfree (old_harray);
 207 }
 208
 209 void
 210 puthash (const void *key, void *contents, struct hash_table *hash_table)
 211 {
 212   if (!key)
 213     {
 214       hash_table->zero_entry = contents;
 215       hash_table->zero_set = 1;
 216     }
 217   else
 218     {
 219       hash_table_test_function test_function = hash_table->test_function;
 220       hash_size_t size = hash_table->size;
 221       hentry *harray   = hash_table->harray;
 222       unsigned int hcode_initial =
 223         hash_table->hash_function ?
 224         hash_table->hash_function (key) :
 225         (unsigned long) key;
 226       unsigned int hcode = hcode_initial % size;
 227       size_t h2 = size - 2;
 228       unsigned int incr = 1 + (hcode_initial % h2);
 229       const void *e_key = harray [hcode].key;
 230       const void *oldcontents;
 231
 232       if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
 233         {
 234           do
 235             {
 236               hcode += incr; if (hcode >= size) hcode -= size;
 237               e_key = harray [hcode].key;
 238             }
 239           while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
 240         }
 241       oldcontents = harray [hcode].contents;
 242       harray [hcode].key = key;
 243       harray [hcode].contents = contents;
 244       /* If the entry that we used was a deleted entry,
 245          check for a non deleted entry of the same key,
 246          then delete it. */
 247       if (!e_key && oldcontents == NULL_ENTRY)
 248         {
 249           hentry *e;
 250
 251           do
 252             {
 253               hcode += incr; if (hcode >= size) hcode -= size;
 254               e = &harray [hcode];
 255               e_key = e->key;
 256             }
 257           while (e_key ?
 258                  KEYS_DIFFER_P (e_key, key, test_function):
 259                  e->contents == NULL_ENTRY);
 260
 261           if (e_key)
 262             {
 263               e->key = 0;
 264               e->contents = NULL_ENTRY;
 265             }
 266         }
 267
 268       /* only increment the fullness when we used up a new hentry */
 269       if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
 270         {
 271           hash_size_t comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
 272           if (hash_table->size < comfortable_size)
 273             grow_hash_table (hash_table, comfortable_size + 1);
 274         }
 275     }
 276 }
 277
 278 static void
 279 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
 280 {
 281   hentry *limit = harray + size;
 282   hentry *e;
 283   for (e = harray; e < limit; e++)
 284     {
 285       if (e->key)
 286         puthash (e->key, e->contents, hash_table);
 287     }
 288 }
 289
 290 void
 291 remhash (const void *key, struct hash_table *hash_table)
 292 {
 293   if (!key)
 294     {
 295       hash_table->zero_entry = 0;
 296       hash_table->zero_set = 0;
 297     }
 298   else
 299     {
 300       hentry *harray = hash_table->harray;
 301       hash_table_test_function test_function = hash_table->test_function;
 302       hash_size_t size = hash_table->size;
 303       unsigned int hcode_initial =
 304         (hash_table->hash_function) ?
 305         (hash_table->hash_function (key)) :
 306         ((unsigned long) key);
 307       unsigned int hcode = hcode_initial % size;
 308       hentry *e = &harray [hcode];
 309       const void *e_key = e->key;
 310
 311       if (e_key ?
 312           KEYS_DIFFER_P (e_key, key, test_function) :
 313           e->contents == NULL_ENTRY)
 314         {
 315           size_t h2 = size - 2;
 316           unsigned int incr = 1 + (hcode_initial % h2);
 317           do
 318             {
 319               hcode += incr; if (hcode >= size) hcode -= size;
 320               e = &harray [hcode];
 321               e_key = e->key;
 322             }
 323           while (e_key?
 324                  KEYS_DIFFER_P (e_key, key, test_function):
 325                  e->contents == NULL_ENTRY);
 326         }
 327       if (e_key)
 328         {
 329           e->key = 0;
 330           e->contents = NULL_ENTRY;
 331           /* Note: you can't do fullness-- here, it breaks the world. */
 332         }
 333     }
 334 }
 335
 336 void
 337 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
 338 {
 339   hentry *e;
 340   hentry *limit;
 341
 342   if (hash_table->zero_set)
 343     {
 344       if (mf (0, hash_table->zero_entry, arg))
 345         return;
 346     }
 347
 348   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 349     {
 350       if (e->key && mf (e->key, e->contents, arg))
 351         return;
 352     }
 353 }
 354
 355 void
 356 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
 357 {
 358   hentry *e;
 359   hentry *limit;
 360
 361   if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
 362     {
 363       hash_table->zero_set = 0;
 364       hash_table->zero_entry = 0;
 365     }
 366
 367   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
 368     if (predicate (e->key, e->contents, arg))
 369       {
 370         e->key = 0;
 371         e->contents = NULL_ENTRY;
 372       }
 373 }