cgit.sxemacs.org Git - sxemacs/blob - src/hash.c

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