locale/programs/simple-hash.c

   1 /* Implement simple hashing table with string based keys.
   2    Copyright (C) 1994-1997,2000,2001,2002,2005 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    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published
   8    by the Free Software Foundation; version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program 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, write to the Free Software Foundation,
  18    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  19
  20 #ifdef HAVE_CONFIG_H
  21 # include <config.h>
  22 #endif
  23
  24 #include <inttypes.h>
  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 #define hashval_t uint32_t
  54 #include "hashval.h"
  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 (const hash_table *htab, const void *key, size_t keylen,
  73                       unsigned long int hval);
  74 static int is_prime (unsigned long int candidate);
  75
  76
  77 int
  78 init_hash (htab, init_size)
  79      hash_table *htab;
  80      unsigned long int init_size;
  81 {
  82   /* We need the size to be a prime.  */
  83   init_size = next_prime (init_size);
  84
  85   /* Initialize the data structure.  */
  86   htab->size = init_size;
  87   htab->filled = 0;
  88   htab->first = NULL;
  89   htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
  90   if (htab->table == NULL)
  91     return -1;
  92
  93   obstack_init (&htab->mem_pool);
  94
  95   return 0;
  96 }
  97
  98
  99 int
 100 delete_hash (htab)
 101      hash_table *htab;
 102 {
 103   free (htab->table);
 104   obstack_free (&htab->mem_pool, NULL);
 105   return 0;
 106 }
 107
 108
 109 int
 110 insert_entry (htab, key, keylen, data)
 111      hash_table *htab;
 112      const void *key;
 113      size_t keylen;
 114      void *data;
 115 {
 116   unsigned long int hval = compute_hashval (key, keylen);
 117   hash_entry *table = (hash_entry *) htab->table;
 118   size_t idx = lookup (htab, key, keylen, hval);
 119
 120   if (table[idx].used)
 121     /* We don't want to overwrite the old value.  */
 122     return -1;
 123   else
 124     {
 125       /* An empty bucket has been found.  */
 126       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 127                       keylen, hval, idx, data);
 128       return 0;
 129     }
 130 }
 131
 132 static void
 133 insert_entry_2 (htab, key, keylen, hval, idx, data)
 134      hash_table *htab;
 135      const void *key;
 136      size_t keylen;
 137      unsigned long int hval;
 138      size_t idx;
 139      void *data;
 140 {
 141   hash_entry *table = (hash_entry *) htab->table;
 142
 143   table[idx].used = hval;
 144   table[idx].key = key;
 145   table[idx].keylen = keylen;
 146   table[idx].data = data;
 147
 148       /* List the new value in the list.  */
 149   if ((hash_entry *) htab->first == NULL)
 150     {
 151       table[idx].next = &table[idx];
 152       htab->first = &table[idx];
 153     }
 154   else
 155     {
 156       table[idx].next = ((hash_entry *) htab->first)->next;
 157       ((hash_entry *) htab->first)->next = &table[idx];
 158       htab->first = &table[idx];
 159     }
 160
 161   ++htab->filled;
 162   if (100 * htab->filled > 75 * htab->size)
 163     {
 164       /* Table is filled more than 75%.  Resize the table.
 165          Experiments have shown that for best performance, this threshold
 166          must lie between 40% and 85%.  */
 167       unsigned long int old_size = htab->size;
 168
 169       htab->size = next_prime (htab->size * 2);
 170       htab->filled = 0;
 171       htab->first = NULL;
 172       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
 173
 174       for (idx = 1; idx <= old_size; ++idx)
 175         if (table[idx].used)
 176           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 177                           table[idx].used,
 178                           lookup (htab, table[idx].key, table[idx].keylen,
 179                                   table[idx].used),
 180                           table[idx].data);
 181
 182       free (table);
 183     }
 184 }
 185
 186
 187 int
 188 find_entry (htab, key, keylen, result)
 189      const hash_table *htab;
 190      const void *key;
 191      size_t keylen;
 192      void **result;
 193 {
 194   hash_entry *table = (hash_entry *) htab->table;
 195   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 196
 197   if (table[idx].used == 0)
 198     return -1;
 199
 200   *result = table[idx].data;
 201   return 0;
 202 }
 203
 204
 205 int
 206 set_entry (htab, key, keylen, newval)
 207      hash_table *htab;
 208      const void *key;
 209      size_t keylen;
 210      void *newval;
 211 {
 212   hash_entry *table = (hash_entry *) htab->table;
 213   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 214
 215   if (table[idx].used == 0)
 216     return -1;
 217
 218   table[idx].data = newval;
 219   return 0;
 220 }
 221
 222
 223 int
 224 iterate_table (htab, ptr, key, keylen, data)
 225      const hash_table *htab;
 226      void **ptr;
 227      const void **key;
 228      size_t *keylen;
 229      void **data;
 230 {
 231   if (*ptr == NULL)
 232     {
 233       if (htab->first == NULL)
 234         return -1;
 235       *ptr = (void *) ((hash_entry *) htab->first)->next;
 236     }
 237   else
 238     {
 239       if (*ptr == htab->first)
 240         return -1;
 241       *ptr = (void *) (((hash_entry *) *ptr)->next);
 242     }
 243
 244   *key = ((hash_entry *) *ptr)->key;
 245   *keylen = ((hash_entry *) *ptr)->keylen;
 246   *data = ((hash_entry *) *ptr)->data;
 247   return 0;
 248 }
 249
 250
 251 /* References:
 252    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 253    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 254
 255 static size_t
 256 lookup (htab, key, keylen, hval)
 257      const hash_table *htab;
 258      const void *key;
 259      size_t keylen;
 260      unsigned long int hval;
 261 {
 262   unsigned long int 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 (table[idx].key, 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 (table[idx].key, key, keylen) == 0)
 290             return idx;
 291         }
 292       while (table[idx].used);
 293     }
 294   return idx;
 295 }
 296
 297
 298 unsigned long int
 299 next_prime (seed)
 300      unsigned long int seed;
 301 {
 302   /* Make it definitely odd.  */
 303   seed |= 1;
 304
 305   while (!is_prime (seed))
 306     seed += 2;
 307
 308   return seed;
 309 }
 310
 311
 312 static int
 313 is_prime (candidate)
 314      unsigned long int candidate;
 315 {
 316   /* No even number and none less than 10 will be passed here.  */
 317   unsigned long int divn = 3;
 318   unsigned long int sq = divn * divn;
 319
 320   while (sq < candidate && candidate % divn != 0)
 321     {
 322       ++divn;
 323       sq += 4 * divn;
 324       ++divn;
 325     }
 326
 327   return candidate % divn != 0;
 328 }