locale/programs/simple-hash.c

   1 /* Implement simple hashing table with string based keys.
   2    Copyright (C) 1994-1997, 2000, 2001, 2002 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library 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 GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <sys/types.h>
  29
  30 #if HAVE_OBSTACK
  31 # include <obstack.h>
  32 #else
  33 # include "obstack.h"
  34 #endif
  35
  36 #ifdef HAVE_VALUES_H
  37 # include <values.h>
  38 #endif
  39
  40 #include "simple-hash.h"
  41
  42 #define obstack_chunk_alloc malloc
  43 #define obstack_chunk_free free
  44
  45 #ifndef BITSPERBYTE
  46 # define BITSPERBYTE 8
  47 #endif
  48
  49 #ifndef bcopy
  50 # define bcopy(s, d, n) memcpy ((d), (s), (n))
  51 #endif
  52
  53 #include "hashval.h"
  54
  55 extern void *xmalloc (size_t __n);
  56 extern void *xcalloc (size_t __n, size_t __m);
  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 (hash_table *htab, const void *key, size_t keylen,
  70                             unsigned long hval, size_t idx, void *data);
  71 static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
  72                       unsigned long int hval);
  73 static int is_prime (unsigned long int candidate);
  74
  75
  76 int
  77 init_hash (htab, init_size)
  78      hash_table *htab;
  79      unsigned long int init_size;
  80 {
  81   /* We need the size to be a prime.  */
  82   init_size = next_prime (init_size);
  83
  84   /* Initialize the data structure.  */
  85   htab->size = init_size;
  86   htab->filled = 0;
  87   htab->first = NULL;
  88   htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
  89   if (htab->table == NULL)
  90     return -1;
  91
  92   obstack_init (&htab->mem_pool);
  93
  94   return 0;
  95 }
  96
  97
  98 int
  99 delete_hash (htab)
 100      hash_table *htab;
 101 {
 102   free (htab->table);
 103   obstack_free (&htab->mem_pool, NULL);
 104   return 0;
 105 }
 106
 107
 108 int
 109 insert_entry (htab, key, keylen, data)
 110      hash_table *htab;
 111      const void *key;
 112      size_t keylen;
 113      void *data;
 114 {
 115   unsigned long int hval = compute_hashval (key, keylen);
 116   hash_entry *table = (hash_entry *) htab->table;
 117   size_t idx = lookup (htab, key, keylen, hval);
 118
 119   if (table[idx].used)
 120     /* We don't want to overwrite the old value.  */
 121     return -1;
 122   else
 123     {
 124       /* An empty bucket has been found.  */
 125       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 126                       keylen, hval, idx, data);
 127       return 0;
 128     }
 129 }
 130
 131 static void
 132 insert_entry_2 (htab, key, keylen, hval, idx, data)
 133      hash_table *htab;
 134      const void *key;
 135      size_t keylen;
 136      unsigned long int hval;
 137      size_t idx;
 138      void *data;
 139 {
 140   hash_entry *table = (hash_entry *) htab->table;
 141
 142   table[idx].used = hval;
 143   table[idx].key = key;
 144   table[idx].keylen = keylen;
 145   table[idx].data = data;
 146
 147       /* List the new value in the list.  */
 148   if ((hash_entry *) htab->first == NULL)
 149     {
 150       table[idx].next = &table[idx];
 151       *(hash_entry **) &htab->first = &table[idx];
 152     }
 153   else
 154     {
 155       table[idx].next = ((hash_entry *) htab->first)->next;
 156       ((hash_entry *) htab->first)->next = &table[idx];
 157       *(hash_entry **) &htab->first = &table[idx];
 158     }
 159
 160   ++htab->filled;
 161   if (100 * htab->filled > 75 * htab->size)
 162     {
 163       /* Table is filled more than 75%.  Resize the table.
 164          Experiments have shown that for best performance, this threshold
 165          must lie between 40% and 85%.  */
 166       unsigned long int old_size = htab->size;
 167
 168       htab->size = next_prime (htab->size * 2);
 169       htab->filled = 0;
 170       htab->first = NULL;
 171       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
 172
 173       for (idx = 1; idx <= old_size; ++idx)
 174         if (table[idx].used)
 175           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 176                           table[idx].used,
 177                           lookup (htab, table[idx].key, table[idx].keylen,
 178                                   table[idx].used),
 179                           table[idx].data);
 180
 181       free (table);
 182     }
 183 }
 184
 185
 186 int
 187 find_entry (htab, key, keylen, result)
 188      const hash_table *htab;
 189      const void *key;
 190      size_t keylen;
 191      void **result;
 192 {
 193   hash_entry *table = (hash_entry *) htab->table;
 194   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 195
 196   if (table[idx].used == 0)
 197     return -1;
 198
 199   *result = table[idx].data;
 200   return 0;
 201 }
 202
 203
 204 int
 205 set_entry (htab, key, keylen, newval)
 206      hash_table *htab;
 207      const void *key;
 208      size_t keylen;
 209      void *newval;
 210 {
 211   hash_entry *table = (hash_entry *) htab->table;
 212   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 213
 214   if (table[idx].used == 0)
 215     return -1;
 216
 217   table[idx].data = newval;
 218   return 0;
 219 }
 220
 221
 222 int
 223 iterate_table (htab, ptr, key, keylen, data)
 224      const hash_table *htab;
 225      void **ptr;
 226      const void **key;
 227      size_t *keylen;
 228      void **data;
 229 {
 230   if (*ptr == NULL)
 231     {
 232       if (htab->first == NULL)
 233         return -1;
 234       *ptr = (void *) ((hash_entry *) htab->first)->next;
 235     }
 236   else
 237     {
 238       if (*ptr == htab->first)
 239         return -1;
 240       *ptr = (void *) (((hash_entry *) *ptr)->next);
 241     }
 242
 243   *key = ((hash_entry *) *ptr)->key;
 244   *keylen = ((hash_entry *) *ptr)->keylen;
 245   *data = ((hash_entry *) *ptr)->data;
 246   return 0;
 247 }
 248
 249
 250 /* References:
 251    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 252    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 253
 254 static size_t
 255 lookup (htab, key, keylen, hval)
 256      const hash_table *htab;
 257      const void *key;
 258      size_t keylen;
 259      unsigned long int hval;
 260 {
 261   unsigned long int hash;
 262   size_t idx;
 263   hash_entry *table = (hash_entry *) htab->table;
 264
 265   /* First hash function: simply take the modul but prevent zero.  */
 266   hash = 1 + hval % htab->size;
 267
 268   idx = hash;
 269
 270   if (table[idx].used)
 271     {
 272       if (table[idx].used == hval && table[idx].keylen == keylen
 273           && memcmp (table[idx].key, key, keylen) == 0)
 274         return idx;
 275
 276       /* Second hash function as suggested in [Knuth].  */
 277       hash = 1 + hval % (htab->size - 2);
 278
 279       do
 280         {
 281           if (idx <= hash)
 282             idx = htab->size + idx - hash;
 283           else
 284             idx -= hash;
 285
 286           /* If entry is found use it.  */
 287           if (table[idx].used == hval && table[idx].keylen == keylen
 288               && memcmp (table[idx].key, key, keylen) == 0)
 289             return idx;
 290         }
 291       while (table[idx].used);
 292     }
 293   return idx;
 294 }
 295
 296
 297 unsigned long int
 298 next_prime (seed)
 299      unsigned long int seed;
 300 {
 301   /* Make it definitely odd.  */
 302   seed |= 1;
 303
 304   while (!is_prime (seed))
 305     seed += 2;
 306
 307   return seed;
 308 }
 309
 310
 311 static int
 312 is_prime (candidate)
 313      unsigned long int candidate;
 314 {
 315   /* No even number and none less than 10 will be passed here.  */
 316   unsigned long int divn = 3;
 317   unsigned long int sq = divn * divn;
 318
 319   while (sq < candidate && candidate % divn != 0)
 320     {
 321       ++divn;
 322       sq += 4 * divn;
 323       ++divn;
 324     }
 325
 326   return candidate % divn != 0;
 327 }