locale/programs/simple-hash.c

   1 /* Implement simple hashing table with string based keys.
   2    Copyright (C) 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
   3    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #ifdef HAVE_CONFIG_H
  21 # include <config.h>
  22 #endif
  23
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <sys/types.h>
  28
  29 #if HAVE_OBSTACK
  30 # include <obstack.h>
  31 #else
  32 # include "obstack.h"
  33 #endif
  34
  35 #ifdef HAVE_VALUES_H
  36 # include <values.h>
  37 #endif
  38
  39 #include "simple-hash.h"
  40
  41 #define obstack_chunk_alloc malloc
  42 #define obstack_chunk_free free
  43
  44 #ifndef BITSPERBYTE
  45 # define BITSPERBYTE 8
  46 #endif
  47
  48 #ifndef LONGBITS
  49 # define LONGBITS (sizeof (long) * BITSPERBYTE)
  50 #endif
  51
  52 #ifndef bcopy
  53 # define bcopy(s, d, n) memcpy ((d), (s), (n))
  54 #endif
  55
  56 void *xmalloc __P ((size_t __n));
  57
  58 typedef struct hash_entry
  59 {
  60   unsigned long used;
  61   const void *key;
  62   size_t keylen;
  63   void *data;
  64   struct hash_entry *next;
  65 }
  66 hash_entry;
  67
  68 /* Prototypes for local functions.  */
  69 static void insert_entry_2 __P ((hash_table *htab, const void *key,
  70                                  size_t keylen, unsigned long hval,
  71                                  size_t idx, void *data));
  72 static size_t lookup __P ((hash_table *htab, const void *key, size_t keylen,
  73                            unsigned long int hval));
  74 static size_t lookup_2 __P ((hash_table *htab, const void *key,
  75                              size_t keylen, unsigned long int hval));
  76 static unsigned long compute_hashval __P ((const void *key, size_t keylen));
  77 static int is_prime __P ((unsigned long int candidate));
  78
  79
  80 int
  81 init_hash (htab, init_size)
  82      hash_table *htab;
  83      unsigned long int init_size;
  84 {
  85   /* We need the size to be a prime.  */
  86   init_size = next_prime (init_size);
  87
  88   /* Initialize the data structure.  */
  89   htab->size = init_size;
  90   htab->filled = 0;
  91   htab->first = NULL;
  92   htab->table = (void *) xmalloc ((init_size + 1) * sizeof (hash_entry));
  93   if (htab->table == NULL)
  94     return -1;
  95
  96   memset (htab->table, '\0', (init_size + 1) * sizeof (hash_entry));
  97   obstack_init (&htab->mem_pool);
  98
  99   return 0;
 100 }
 101
 102
 103 int
 104 delete_hash (htab)
 105      hash_table *htab;
 106 {
 107   free (htab->table);
 108   obstack_free (&htab->mem_pool, NULL);
 109   return 0;
 110 }
 111
 112
 113 int
 114 insert_entry (htab, key, keylen, data)
 115      hash_table *htab;
 116      const void *key;
 117      size_t keylen;
 118      void *data;
 119 {
 120   unsigned long int hval = compute_hashval (key, keylen);
 121   hash_entry *table = (hash_entry *) htab->table;
 122   size_t idx = lookup (htab, key, keylen, hval);
 123
 124   if (table[idx].used)
 125     /* We don't want to overwrite the old value.  */
 126     return -1;
 127   else
 128     {
 129       /* An empty bucket has been found.  */
 130       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 131                       keylen, hval, idx, data);
 132       return 0;
 133     }
 134 }
 135
 136 static void
 137 insert_entry_2 (htab, key, keylen, hval, idx, data)
 138      hash_table *htab;
 139      const void *key;
 140      size_t keylen;
 141      unsigned long int hval;
 142      size_t idx;
 143      void *data;
 144 {
 145   hash_entry *table = (hash_entry *) htab->table;
 146
 147   table[idx].used = hval;
 148   table[idx].key = key;
 149   table[idx].keylen = keylen;
 150   table[idx].data = data;
 151
 152       /* List the new value in the list.  */
 153   if ((hash_entry *) htab->first == NULL)
 154     {
 155       table[idx].next = &table[idx];
 156       *(hash_entry **) &htab->first = &table[idx];
 157     }
 158   else
 159     {
 160       table[idx].next = ((hash_entry *) htab->first)->next;
 161       ((hash_entry *) htab->first)->next = &table[idx];
 162       *(hash_entry **) &htab->first = &table[idx];
 163     }
 164
 165   ++htab->filled;
 166   if (100 * htab->filled > 90 * htab->size)
 167     {
 168       /* Table is filled more than 90%.  Resize the table.  */
 169       unsigned long int old_size = htab->size;
 170
 171       htab->size = next_prime (htab->size * 2);
 172       htab->filled = 0;
 173       htab->first = NULL;
 174       htab->table = (void *) xmalloc ((1 + htab->size)
 175                                       * sizeof (hash_entry));
 176       memset (htab->table, '\0', (1 + htab->size) * sizeof (hash_entry));
 177
 178       for (idx = 1; idx <= old_size; ++idx)
 179         if (table[idx].used)
 180           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 181                           table[idx].used,
 182                           lookup_2 (htab, table[idx].key, table[idx].keylen,
 183                                     table[idx].used),
 184                           table[idx].data);
 185
 186       free (table);
 187     }
 188 }
 189
 190
 191 int
 192 find_entry (htab, key, keylen, result)
 193      hash_table *htab;
 194      const void *key;
 195      size_t keylen;
 196      void **result;
 197 {
 198   hash_entry *table = (hash_entry *) htab->table;
 199   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 200
 201   if (table[idx].used == 0)
 202     return -1;
 203
 204   *result = table[idx].data;
 205   return 0;
 206 }
 207
 208
 209 int
 210 set_entry (htab, key, keylen, newval)
 211      hash_table *htab;
 212      const void *key;
 213      size_t keylen;
 214      void *newval;
 215 {
 216   hash_entry *table = (hash_entry *) htab->table;
 217   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 218
 219   if (table[idx].used == 0)
 220     return -1;
 221
 222   table[idx].data = newval;
 223   return 0;
 224 }
 225
 226
 227 int
 228 iterate_table (htab, ptr, key, keylen, data)
 229      hash_table *htab;
 230      void **ptr;
 231      const void **key;
 232      size_t *keylen;
 233      void **data;
 234 {
 235   if (*ptr == NULL)
 236     {
 237       if (htab->first == NULL)
 238         return -1;
 239       *ptr = (void *) ((hash_entry *) htab->first)->next;
 240     }
 241   else
 242     {
 243       if (*ptr == htab->first)
 244         return -1;
 245       *ptr = (void *) (((hash_entry *) *ptr)->next);
 246     }
 247
 248   *key = ((hash_entry *) *ptr)->key;
 249   *keylen = ((hash_entry *) *ptr)->keylen;
 250   *data = ((hash_entry *) *ptr)->data;
 251   return 0;
 252 }
 253
 254
 255 static size_t
 256 lookup (htab, key, keylen, hval)
 257      hash_table *htab;
 258      const void *key;
 259      size_t keylen;
 260      unsigned long hval;
 261 {
 262   unsigned long hash;
 263   size_t idx;
 264   hash_entry *table = (hash_entry *) htab->table;
 265
 266   /* First hash function: simply take the modul but prevent zero.  */
 267   hash = 1 + hval % htab->size;
 268
 269   idx = hash;
 270
 271   if (table[idx].used)
 272     {
 273       if (table[idx].used == hval && table[idx].keylen == keylen
 274           && memcmp (key, table[idx].key, keylen) == 0)
 275         return idx;
 276
 277       /* Second hash function as suggested in [Knuth].  */
 278       hash = 1 + hval % (htab->size - 2);
 279
 280       do
 281         {
 282           if (idx <= hash)
 283             idx = htab->size + idx - hash;
 284           else
 285             idx -= hash;
 286
 287           /* If entry is found use it.  */
 288           if (table[idx].used == hval && table[idx].keylen == keylen
 289               && memcmp (key, table[idx].key, keylen) == 0)
 290             return idx;
 291         }
 292       while (table[idx].used);
 293     }
 294   return idx;
 295 }
 296
 297
 298 /* References:
 299    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 300    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 301
 302 static size_t
 303 lookup_2 (htab, key, keylen, hval)
 304      hash_table *htab;
 305      const void *key;
 306      size_t keylen;
 307      unsigned long int hval;
 308 {
 309   unsigned long int hash;
 310   size_t idx;
 311   hash_entry *table = (hash_entry *) htab->table;
 312
 313   /* First hash function: simply take the modul but prevent zero.  */
 314   hash = 1 + hval % htab->size;
 315
 316   idx = hash;
 317
 318   if (table[idx].used)
 319     {
 320       if (table[idx].used == hval && table[idx].keylen == keylen
 321           && memcmp (table[idx].key, key, keylen) == 0)
 322         return idx;
 323
 324       /* Second hash function as suggested in [Knuth].  */
 325       hash = 1 + hval % (htab->size - 2);
 326
 327       do
 328         {
 329           if (idx <= hash)
 330             idx = htab->size + idx - hash;
 331           else
 332             idx -= hash;
 333
 334           /* If entry is found use it.  */
 335           if (table[idx].used == hval && table[idx].keylen == keylen
 336               && memcmp (table[idx].key, key, keylen) == 0)
 337             return idx;
 338         }
 339       while (table[idx].used);
 340     }
 341   return idx;
 342 }
 343
 344
 345 static unsigned long
 346 compute_hashval (key, keylen)
 347      const void *key;
 348      size_t keylen;
 349 {
 350   size_t cnt;
 351   unsigned long int hval, g;
 352
 353   /* Compute the hash value for the given string.  The algorithm
 354      is taken from [Aho,Sethi,Ullman].  */
 355   cnt = 0;
 356   hval = keylen;
 357   while (cnt < keylen)
 358     {
 359       hval <<= 4;
 360       hval += (unsigned long int) *(((char *) key) + cnt++);
 361       g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
 362       if (g != 0)
 363         {
 364           hval ^= g >> (LONGBITS - 8);
 365           hval ^= g;
 366         }
 367     }
 368   return hval != 0 ? hval : ~((unsigned long) 0);
 369 }
 370
 371
 372 unsigned long
 373 next_prime (seed)
 374      unsigned long int seed;
 375 {
 376   /* Make it definitely odd.  */
 377   seed |= 1;
 378
 379   while (!is_prime (seed))
 380     seed += 2;
 381
 382   return seed;
 383 }
 384
 385
 386 static int
 387 is_prime (candidate)
 388      unsigned long int candidate;
 389 {
 390   /* No even number and none less than 10 will be passed here.  */
 391   unsigned long int divn = 3;
 392   unsigned long int sq = divn * divn;
 393
 394   while (sq < candidate && candidate % divn != 0)
 395     {
 396       ++divn;
 397       sq += 4 * divn;
 398       ++divn;
 399     }
 400
 401   return candidate % divn != 0;
 402 }