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 #include "elhash.h"
  37
  38 static CONST unsigned int
  39 primes []={
  40   13,
  41   29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,
  42   761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
  43   8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361,
  44   62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449,
  45   389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319,
  46   2009191, 2411033, 2893249
  47 };
  48
  49 /* strings code */
  50
  51 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
  52 unsigned long
  53 string_hash (CONST void *xv)
  54 {
  55   unsigned int h = 0;
  56   unsigned CONST char *x = (unsigned CONST char *) xv;
  57
  58   if (!x) return 0;
  59
  60   while (*x != 0)
  61     {
  62       unsigned int g;
  63       h = (h << 4) + *x++;
  64       if ((g = h & 0xf0000000) != 0)
  65         h = (h ^ (g >> 24)) ^ g;
  66     }
  67
  68   return h;
  69 }
  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 > 0)
  80     {
  81       unsigned int g;
  82       h = (h << 4) + *x++;
  83       if ((g = h & 0xf0000000) != 0)
  84         h = (h ^ (g >> 24)) ^ g;
  85       size--;
  86     }
  87
  88   return h;
  89 }
  90
  91 static int
  92 string_eq (CONST void *st1, CONST void *st2)
  93 {
  94   if (!st1)
  95     return st2 ? 0 : 1;
  96   else if (!st2)
  97     return 0;
  98   else
  99     return !strcmp ( (CONST char *) st1, (CONST char *) st2);
 100 }
 101
 102
 103 /* ### Ever heard of binary search? */
 104 static unsigned int
 105 prime_size (unsigned int size)
 106 {
 107   int i;
 108   for (i = 0; i < countof (primes); i++)
 109     if (size <= primes [i])
 110       return primes [i];
 111   return primes [countof (primes) - 1];
 112 }
 113
 114 static void rehash (hentry *harray, c_hashtable ht, unsigned int size);
 115
 116 #define KEYS_DIFFER_P(old, new, testfun) \
 117   ((testfun)?(((old) == (new))?0:(!(testfun ((old), new)))):((old) != (new)))
 118
 119 CONST void *
 120 gethash (CONST void *key, c_hashtable hash, CONST void **ret_value)
 121 {
 122   hentry *harray = hash->harray;
 123   int (*test_function) (CONST void *, CONST void *) = hash->test_function;
 124   unsigned int hsize = hash->size;
 125   unsigned int hcode_initial =
 126     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
 127   unsigned int hcode = hcode_initial % hsize;
 128   hentry *e = &harray [hcode];
 129   CONST void *e_key = e->key;
 130
 131   if (!key)
 132     {
 133       *ret_value = hash->zero_entry;
 134       return (void *) hash->zero_set;
 135     }
 136
 137   if ((e_key)?
 138       (KEYS_DIFFER_P (e_key, key, test_function)):
 139       (e->contents == NULL_ENTRY))
 140     {
 141       unsigned int h2 = hsize - 2;
 142       unsigned int incr = 1 + (hcode_initial % h2);
 143       do
 144         {
 145           hcode = hcode + incr;
 146           if (hcode >= hsize) hcode = hcode - hsize;
 147           e = &harray [hcode];
 148           e_key = e->key;
 149         }
 150       while ((e_key)?
 151              (KEYS_DIFFER_P (e_key, key, test_function)):
 152              (e->contents == NULL_ENTRY));
 153     }
 154
 155   *ret_value = e->contents;
 156   return e->key;
 157 }
 158
 159 void
 160 clrhash (c_hashtable hash)
 161 {
 162   memset (hash->harray, 0, sizeof (hentry) * hash->size);
 163   hash->zero_entry = 0;
 164   hash->zero_set = 0;
 165   hash->fullness = 0;
 166 }
 167
 168 void
 169 free_hashtable (c_hashtable hash)
 170 {
 171 #ifdef emacs
 172   if (!NILP (hash->elisp_table))
 173     return;
 174 #endif
 175   xfree (hash->harray);
 176   xfree (hash);
 177 }
 178
 179 c_hashtable
 180 make_hashtable (unsigned int hsize)
 181 {
 182   c_hashtable res = xnew_and_zero (struct _C_hashtable);
 183   res->size = prime_size ((13 * hsize) / 10);
 184   res->harray = xnew_array (hentry, res->size);
 185 #ifdef emacs
 186   res->elisp_table = Qnil;
 187 #endif
 188   clrhash (res);
 189   return res;
 190 }
 191
 192 c_hashtable
 193 make_general_hashtable (unsigned int hsize,
 194                         unsigned long (*hash_function) (CONST void *),
 195                         int (*test_function) (CONST void *, CONST void *))
 196 {
 197   c_hashtable res = xnew_and_zero (struct _C_hashtable);
 198   res->size = prime_size ((13 * hsize) / 10);
 199   res->harray = xnew_array (hentry, res->size);
 200   res->hash_function = hash_function;
 201   res->test_function = test_function;
 202 #ifdef emacs
 203   res->elisp_table = Qnil;
 204 #endif
 205   clrhash (res);
 206   return res;
 207 }
 208
 209 c_hashtable
 210 make_strings_hashtable (unsigned int hsize)
 211 {
 212   return make_general_hashtable (hsize, string_hash, string_eq);
 213 }
 214
 215 #ifdef emacs
 216 unsigned int
 217 compute_harray_size (unsigned int hsize)
 218 {
 219   return prime_size ((13 * hsize) / 10);
 220 }
 221 #endif
 222
 223 void
 224 copy_hash (c_hashtable dest, c_hashtable src)
 225 {
 226 #ifdef emacs
 227   /* if these are not the same, then we are losing here */
 228   if ((NILP (dest->elisp_table)) != (NILP (src->elisp_table)))
 229     {
 230       error ("Incompatible hashtable types to copy_hash.");
 231       return;
 232     }
 233 #endif
 234
 235   if (dest->size != src->size)
 236     {
 237 #ifdef emacs
 238       if (!NILP (dest->elisp_table))
 239         elisp_hvector_free (dest->harray, dest->elisp_table);
 240       else
 241 #endif
 242         xfree (dest->harray);
 243
 244       dest->size = src->size;
 245 #ifdef emacs
 246       if (!NILP (dest->elisp_table))
 247         dest->harray = (hentry *)
 248           elisp_hvector_malloc (sizeof (hentry) * dest->size,
 249                                 dest->elisp_table);
 250       else
 251 #endif
 252         dest->harray = xnew_array (hentry, dest->size);
 253     }
 254   dest->fullness = src->fullness;
 255   dest->zero_entry = src->zero_entry;
 256   dest->zero_set = src->zero_set;
 257   dest->hash_function = src->hash_function;
 258   dest->test_function = src->test_function;
 259   memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size);
 260 }
 261
 262 static void
 263 grow_hashtable (c_hashtable hash, unsigned int new_size)
 264 {
 265   unsigned int old_hsize = hash->size;
 266   hentry *old_harray = hash->harray;
 267   unsigned int new_hsize = prime_size (new_size);
 268   hentry *new_harray;
 269
 270 #ifdef emacs
 271   /* We test for Qzero to facilitate free-hook.c.  That module creates
 272      a hashtable very very early, at which point Qnil has not yet
 273      been set and is thus all zeroes.  Qzero is "automatically"
 274      initialized at startup because its correct value is also all
 275      zeroes. */
 276   if (!EQ (hash->elisp_table, Qnull_pointer) &&
 277       !NILP (hash->elisp_table) &&
 278       !ZEROP (hash->elisp_table))
 279     new_harray = (hentry *) elisp_hvector_malloc (sizeof (hentry) * new_hsize,
 280                                                   hash->elisp_table);
 281   else
 282 #endif
 283     new_harray = (hentry *) xmalloc (sizeof (hentry) * new_hsize);
 284
 285   hash->size = new_hsize;
 286   hash->harray = new_harray;
 287
 288   /* do the rehash on the "grown" table */
 289   {
 290     long old_zero_set = hash->zero_set;
 291     void *old_zero_entry = hash->zero_entry;
 292     clrhash (hash);
 293     hash->zero_set = old_zero_set;
 294     hash->zero_entry = old_zero_entry;
 295     rehash (old_harray, hash, old_hsize);
 296   }
 297
 298 #ifdef emacs
 299   if (!EQ (hash->elisp_table, Qnull_pointer) &&
 300       !NILP (hash->elisp_table) &&
 301       !ZEROP (hash->elisp_table))
 302     elisp_hvector_free (old_harray, hash->elisp_table);
 303   else
 304 #endif
 305     xfree (old_harray);
 306 }
 307
 308 void
 309 expand_hashtable (c_hashtable hash, unsigned int needed_size)
 310 {
 311   size_t hsize = hash->size;
 312   size_t comfortable_size = (13 * needed_size) / 10;
 313   if (hsize < comfortable_size)
 314     grow_hashtable (hash, comfortable_size + 1);
 315 }
 316
 317 void
 318 puthash (CONST void *key, void *cont, c_hashtable hash)
 319 {
 320   unsigned int hsize = hash->size;
 321   int (*test_function) (CONST void *, CONST void *) = hash->test_function;
 322   unsigned int fullness = hash->fullness;
 323   hentry *harray;
 324   CONST void *e_key;
 325   hentry *e;
 326   unsigned int hcode_initial =
 327     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
 328   unsigned int hcode;
 329   unsigned int incr = 0;
 330   unsigned int h2;
 331   CONST void *oldcontents;
 332
 333   if (!key)
 334     {
 335       hash->zero_entry = cont;
 336       hash->zero_set = 1;
 337       return;
 338     }
 339
 340   if (hsize < (1 + ((13 * fullness) / 10)))
 341     {
 342       grow_hashtable (hash, hsize + 1);
 343       hsize = hash->size;
 344       fullness = hash->fullness;
 345     }
 346
 347   harray= hash->harray;
 348   h2 = hsize - 2;
 349
 350   hcode = hcode_initial % hsize;
 351
 352   e_key = harray [hcode].key;
 353   if (e_key && (KEYS_DIFFER_P (e_key, key, test_function)))
 354     {
 355       h2 = hsize - 2;
 356       incr = 1 + (hcode_initial % h2);
 357       do
 358         {
 359           hcode = hcode + incr;
 360           if (hcode >= hsize) hcode = hcode - hsize;
 361           e_key = harray [hcode].key;
 362         }
 363       while (e_key && (KEYS_DIFFER_P (e_key, key, test_function)));
 364     }
 365   oldcontents = harray [hcode].contents;
 366   harray [hcode].key = key;
 367   harray [hcode].contents = cont;
 368   /* if the entry that we used was a deleted entry,
 369      check for a non deleted entry of the same key,
 370      then delete it */
 371   if (!e_key && (oldcontents == NULL_ENTRY))
 372     {
 373       if (!incr) incr = 1 + ((unsigned long) key % h2);
 374
 375       do
 376         {
 377           hcode = hcode + incr;
 378           if (hcode >= hsize) hcode = hcode - hsize;
 379           e = &harray [hcode];
 380           e_key = e->key;
 381         }
 382       while ((e_key)?
 383              (KEYS_DIFFER_P (e_key, key, test_function)):
 384              (e->contents == NULL_ENTRY));
 385
 386       if (e_key)
 387         {
 388           e->key = 0;
 389           e->contents = NULL_ENTRY;
 390         }
 391     }
 392
 393   /* only increment the fullness when we used up a new hentry */
 394   if (!e_key || (KEYS_DIFFER_P (e_key, key, test_function)))
 395     hash->fullness++;
 396 }
 397
 398 static void
 399 rehash (hentry *harray, c_hashtable hash, unsigned int size)
 400 {
 401   hentry *limit = harray + size;
 402   hentry *e;
 403   for (e = harray; e < limit; e++)
 404     {
 405       if (e->key)
 406         puthash (e->key, e->contents, hash);
 407     }
 408 }
 409
 410 void
 411 remhash (CONST void *key, c_hashtable hash)
 412 {
 413   hentry *harray = hash->harray;
 414   int (*test_function) (CONST void*, CONST void*) = hash->test_function;
 415   unsigned int hsize = hash->size;
 416   unsigned int hcode_initial =
 417     (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key);
 418   unsigned int hcode = hcode_initial % hsize;
 419   hentry *e = &harray [hcode];
 420   CONST void *e_key = e->key;
 421
 422   if (!key)
 423     {
 424       hash->zero_entry = 0;
 425       hash->zero_set = 0;
 426       return;
 427     }
 428
 429   if ((e_key)?
 430       (KEYS_DIFFER_P (e_key, key, test_function)):
 431       (e->contents == NULL_ENTRY))
 432     {
 433       unsigned int h2 = hsize - 2;
 434       unsigned int incr = 1 + (hcode_initial % h2);
 435       do
 436         {
 437           hcode = hcode + incr;
 438           if (hcode >= hsize) hcode = hcode - hsize;
 439           e = &harray [hcode];
 440           e_key = e->key;
 441         }
 442       while ((e_key)?
 443              (KEYS_DIFFER_P (e_key, key, test_function)):
 444              (e->contents == NULL_ENTRY));
 445     }
 446   if (e_key)
 447     {
 448       e->key = 0;
 449       e->contents = NULL_ENTRY;
 450       /* Note: you can't do fullness-- here, it breaks the world. */
 451     }
 452 }
 453
 454 void
 455 maphash (maphash_function mf, c_hashtable hash, void *arg)
 456 {
 457   hentry *e;
 458   hentry *limit;
 459
 460   if (hash->zero_set)
 461     {
 462       if (((*mf) (0, hash->zero_entry, arg)))
 463         return;
 464     }
 465
 466   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
 467     {
 468       if (e->key)
 469         {
 470           if (((*mf) (e->key, e->contents, arg)))
 471             return;
 472         }
 473     }
 474 }
 475
 476 void
 477 map_remhash (remhash_predicate predicate, c_hashtable hash, void *arg)
 478 {
 479   hentry *e;
 480   hentry *limit;
 481
 482   if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg)))
 483     {
 484       hash->zero_set = 0;
 485       hash->zero_entry = 0;
 486     }
 487
 488   for (e = hash->harray, limit = e + hash->size; e < limit; e++)
 489     if ((*predicate) (e->key, e->contents, arg))
 490       {
 491         e->key = 0;
 492         e->contents = NULL_ENTRY;
 493       }
 494 }