locale/programs/simple-hash.c

   1 /* Implement simple hashing table with string based keys.
   2    Copyright (C) 1994, 1995, 1996, 1997, 2000 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 extern void *xmalloc (size_t __n);
  57 extern void *xcalloc (size_t __n, size_t __m);
  58
  59 typedef struct hash_entry
  60 {
  61   unsigned long used;
  62   const void *key;
  63   size_t keylen;
  64   void *data;
  65   struct hash_entry *next;
  66 }
  67 hash_entry;
  68
  69 /* Prototypes for local functions.  */
  70 static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
  71                             unsigned long hval, size_t idx, void *data);
  72 static size_t lookup (hash_table *htab, const void *key, size_t keylen,
  73                       unsigned long int hval);
  74 static size_t lookup_2 (hash_table *htab, const void *key, size_t keylen,
  75                         unsigned long int hval);
  76 static unsigned long compute_hashval (const void *key, size_t keylen);
  77 static int is_prime (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 *) xcalloc (init_size + 1, sizeof (hash_entry));
  93   if (htab->table == NULL)
  94     return -1;
  95
  96   obstack_init (&htab->mem_pool);
  97
  98   return 0;
  99 }
 100
 101
 102 int
 103 delete_hash (htab)
 104      hash_table *htab;
 105 {
 106   free (htab->table);
 107   obstack_free (&htab->mem_pool, NULL);
 108   return 0;
 109 }
 110
 111
 112 int
 113 insert_entry (htab, key, keylen, data)
 114      hash_table *htab;
 115      const void *key;
 116      size_t keylen;
 117      void *data;
 118 {
 119   unsigned long int hval = compute_hashval (key, keylen);
 120   hash_entry *table = (hash_entry *) htab->table;
 121   size_t idx = lookup (htab, key, keylen, hval);
 122
 123   if (table[idx].used)
 124     /* We don't want to overwrite the old value.  */
 125     return -1;
 126   else
 127     {
 128       /* An empty bucket has been found.  */
 129       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 130                       keylen, hval, idx, data);
 131       return 0;
 132     }
 133 }
 134
 135 static void
 136 insert_entry_2 (htab, key, keylen, hval, idx, data)
 137      hash_table *htab;
 138      const void *key;
 139      size_t keylen;
 140      unsigned long int hval;
 141      size_t idx;
 142      void *data;
 143 {
 144   hash_entry *table = (hash_entry *) htab->table;
 145
 146   table[idx].used = hval;
 147   table[idx].key = key;
 148   table[idx].keylen = keylen;
 149   table[idx].data = data;
 150
 151       /* List the new value in the list.  */
 152   if ((hash_entry *) htab->first == NULL)
 153     {
 154       table[idx].next = &table[idx];
 155       *(hash_entry **) &htab->first = &table[idx];
 156     }
 157   else
 158     {
 159       table[idx].next = ((hash_entry *) htab->first)->next;
 160       ((hash_entry *) htab->first)->next = &table[idx];
 161       *(hash_entry **) &htab->first = &table[idx];
 162     }
 163
 164   ++htab->filled;
 165   if (100 * htab->filled > 90 * htab->size)
 166     {
 167       /* Table is filled more than 90%.  Resize the table.  */
 168       unsigned long int old_size = htab->size;
 169
 170       htab->size = next_prime (htab->size * 2);
 171       htab->filled = 0;
 172       htab->first = NULL;
 173       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
 174
 175       for (idx = 1; idx <= old_size; ++idx)
 176         if (table[idx].used)
 177           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 178                           table[idx].used,
 179                           lookup_2 (htab, table[idx].key, table[idx].keylen,
 180                                     table[idx].used),
 181                           table[idx].data);
 182
 183       free (table);
 184     }
 185 }
 186
 187
 188 int
 189 find_entry (htab, key, keylen, result)
 190      hash_table *htab;
 191      const void *key;
 192      size_t keylen;
 193      void **result;
 194 {
 195   hash_entry *table = (hash_entry *) htab->table;
 196   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 197
 198   if (table[idx].used == 0)
 199     return -1;
 200
 201   *result = table[idx].data;
 202   return 0;
 203 }
 204
 205
 206 int
 207 set_entry (htab, key, keylen, newval)
 208      hash_table *htab;
 209      const void *key;
 210      size_t keylen;
 211      void *newval;
 212 {
 213   hash_entry *table = (hash_entry *) htab->table;
 214   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 215
 216   if (table[idx].used == 0)
 217     return -1;
 218
 219   table[idx].data = newval;
 220   return 0;
 221 }
 222
 223
 224 int
 225 iterate_table (htab, ptr, key, keylen, data)
 226      hash_table *htab;
 227      void **ptr;
 228      const void **key;
 229      size_t *keylen;
 230      void **data;
 231 {
 232   if (*ptr == NULL)
 233     {
 234       if (htab->first == NULL)
 235         return -1;
 236       *ptr = (void *) ((hash_entry *) htab->first)->next;
 237     }
 238   else
 239     {
 240       if (*ptr == htab->first)
 241         return -1;
 242       *ptr = (void *) (((hash_entry *) *ptr)->next);
 243     }
 244
 245   *key = ((hash_entry *) *ptr)->key;
 246   *keylen = ((hash_entry *) *ptr)->keylen;
 247   *data = ((hash_entry *) *ptr)->data;
 248   return 0;
 249 }
 250
 251
 252 static size_t
 253 lookup (htab, key, keylen, hval)
 254      hash_table *htab;
 255      const void *key;
 256      size_t keylen;
 257      unsigned long hval;
 258 {
 259   unsigned long hash;
 260   size_t idx;
 261   hash_entry *table = (hash_entry *) htab->table;
 262
 263   /* First hash function: simply take the modul but prevent zero.  */
 264   hash = 1 + hval % htab->size;
 265
 266   idx = hash;
 267
 268   if (table[idx].used)
 269     {
 270       if (table[idx].used == hval && table[idx].keylen == keylen
 271           && memcmp (key, table[idx].key, keylen) == 0)
 272         return idx;
 273
 274       /* Second hash function as suggested in [Knuth].  */
 275       hash = 1 + hval % (htab->size - 2);
 276
 277       do
 278         {
 279           if (idx <= hash)
 280             idx = htab->size + idx - hash;
 281           else
 282             idx -= hash;
 283
 284           /* If entry is found use it.  */
 285           if (table[idx].used == hval && table[idx].keylen == keylen
 286               && memcmp (key, table[idx].key, keylen) == 0)
 287             return idx;
 288         }
 289       while (table[idx].used);
 290     }
 291   return idx;
 292 }
 293
 294
 295 /* References:
 296    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 297    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 298
 299 static size_t
 300 lookup_2 (htab, key, keylen, hval)
 301      hash_table *htab;
 302      const void *key;
 303      size_t keylen;
 304      unsigned long int hval;
 305 {
 306   unsigned long int hash;
 307   size_t idx;
 308   hash_entry *table = (hash_entry *) htab->table;
 309
 310   /* First hash function: simply take the modul but prevent zero.  */
 311   hash = 1 + hval % htab->size;
 312
 313   idx = hash;
 314
 315   if (table[idx].used)
 316     {
 317       if (table[idx].used == hval && table[idx].keylen == keylen
 318           && memcmp (table[idx].key, key, keylen) == 0)
 319         return idx;
 320
 321       /* Second hash function as suggested in [Knuth].  */
 322       hash = 1 + hval % (htab->size - 2);
 323
 324       do
 325         {
 326           if (idx <= hash)
 327             idx = htab->size + idx - hash;
 328           else
 329             idx -= hash;
 330
 331           /* If entry is found use it.  */
 332           if (table[idx].used == hval && table[idx].keylen == keylen
 333               && memcmp (table[idx].key, key, keylen) == 0)
 334             return idx;
 335         }
 336       while (table[idx].used);
 337     }
 338   return idx;
 339 }
 340
 341
 342 static unsigned long
 343 compute_hashval (key, keylen)
 344      const void *key;
 345      size_t keylen;
 346 {
 347   size_t cnt;
 348   unsigned long int hval, g;
 349
 350   /* Compute the hash value for the given string.  The algorithm
 351      is taken from [Aho,Sethi,Ullman].  */
 352   cnt = 0;
 353   hval = keylen;
 354   while (cnt < keylen)
 355     {
 356       hval <<= 4;
 357       hval += (unsigned long int) *(((char *) key) + cnt++);
 358       g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
 359       if (g != 0)
 360         {
 361           hval ^= g >> (LONGBITS - 8);
 362           hval ^= g;
 363         }
 364     }
 365   return hval != 0 ? hval : ~((unsigned long) 0);
 366 }
 367
 368
 369 unsigned long
 370 next_prime (seed)
 371      unsigned long int seed;
 372 {
 373   /* Make it definitely odd.  */
 374   seed |= 1;
 375
 376   while (!is_prime (seed))
 377     seed += 2;
 378
 379   return seed;
 380 }
 381
 382
 383 static int
 384 is_prime (candidate)
 385      unsigned long int candidate;
 386 {
 387   /* No even number and none less than 10 will be passed here.  */
 388   unsigned long int divn = 3;
 389   unsigned long int sq = divn * divn;
 390
 391   while (sq < candidate && candidate % divn != 0)
 392     {
 393       ++divn;
 394       sq += 4 * divn;
 395       ++divn;
 396     }
 397
 398   return candidate % divn != 0;
 399 }