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 <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 bcopy
  49 # define bcopy(s, d, n) memcpy ((d), (s), (n))
  50 #endif
  51
  52 #include "hashval.h"
  53
  54 extern void *xmalloc (size_t __n);
  55 extern void *xcalloc (size_t __n, size_t __m);
  56
  57 typedef struct hash_entry
  58 {
  59   unsigned long used;
  60   const void *key;
  61   size_t keylen;
  62   void *data;
  63   struct hash_entry *next;
  64 }
  65 hash_entry;
  66
  67 /* Prototypes for local functions.  */
  68 static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
  69                             unsigned long hval, size_t idx, void *data);
  70 static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
  71                       unsigned long int hval);
  72 static int is_prime (unsigned long int candidate);
  73
  74
  75 int
  76 init_hash (htab, init_size)
  77      hash_table *htab;
  78      unsigned long int init_size;
  79 {
  80   /* We need the size to be a prime.  */
  81   init_size = next_prime (init_size);
  82
  83   /* Initialize the data structure.  */
  84   htab->size = init_size;
  85   htab->filled = 0;
  86   htab->first = NULL;
  87   htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
  88   if (htab->table == NULL)
  89     return -1;
  90
  91   obstack_init (&htab->mem_pool);
  92
  93   return 0;
  94 }
  95
  96
  97 int
  98 delete_hash (htab)
  99      hash_table *htab;
 100 {
 101   free (htab->table);
 102   obstack_free (&htab->mem_pool, NULL);
 103   return 0;
 104 }
 105
 106
 107 int
 108 insert_entry (htab, key, keylen, data)
 109      hash_table *htab;
 110      const void *key;
 111      size_t keylen;
 112      void *data;
 113 {
 114   unsigned long int hval = compute_hashval (key, keylen);
 115   hash_entry *table = (hash_entry *) htab->table;
 116   size_t idx = lookup (htab, key, keylen, hval);
 117
 118   if (table[idx].used)
 119     /* We don't want to overwrite the old value.  */
 120     return -1;
 121   else
 122     {
 123       /* An empty bucket has been found.  */
 124       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 125                       keylen, hval, idx, data);
 126       return 0;
 127     }
 128 }
 129
 130 static void
 131 insert_entry_2 (htab, key, keylen, hval, idx, data)
 132      hash_table *htab;
 133      const void *key;
 134      size_t keylen;
 135      unsigned long int hval;
 136      size_t idx;
 137      void *data;
 138 {
 139   hash_entry *table = (hash_entry *) htab->table;
 140
 141   table[idx].used = hval;
 142   table[idx].key = key;
 143   table[idx].keylen = keylen;
 144   table[idx].data = data;
 145
 146       /* List the new value in the list.  */
 147   if ((hash_entry *) htab->first == NULL)
 148     {
 149       table[idx].next = &table[idx];
 150       htab->first = &table[idx];
 151     }
 152   else
 153     {
 154       table[idx].next = ((hash_entry *) htab->first)->next;
 155       ((hash_entry *) htab->first)->next = &table[idx];
 156       htab->first = &table[idx];
 157     }
 158
 159   ++htab->filled;
 160   if (100 * htab->filled > 75 * htab->size)
 161     {
 162       /* Table is filled more than 75%.  Resize the table.
 163          Experiments have shown that for best performance, this threshold
 164          must lie between 40% and 85%.  */
 165       unsigned long int old_size = htab->size;
 166
 167       htab->size = next_prime (htab->size * 2);
 168       htab->filled = 0;
 169       htab->first = NULL;
 170       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
 171
 172       for (idx = 1; idx <= old_size; ++idx)
 173         if (table[idx].used)
 174           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 175                           table[idx].used,
 176                           lookup (htab, table[idx].key, table[idx].keylen,
 177                                   table[idx].used),
 178                           table[idx].data);
 179
 180       free (table);
 181     }
 182 }
 183
 184
 185 int
 186 find_entry (htab, key, keylen, result)
 187      const hash_table *htab;
 188      const void *key;
 189      size_t keylen;
 190      void **result;
 191 {
 192   hash_entry *table = (hash_entry *) htab->table;
 193   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 194
 195   if (table[idx].used == 0)
 196     return -1;
 197
 198   *result = table[idx].data;
 199   return 0;
 200 }
 201
 202
 203 int
 204 set_entry (htab, key, keylen, newval)
 205      hash_table *htab;
 206      const void *key;
 207      size_t keylen;
 208      void *newval;
 209 {
 210   hash_entry *table = (hash_entry *) htab->table;
 211   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 212
 213   if (table[idx].used == 0)
 214     return -1;
 215
 216   table[idx].data = newval;
 217   return 0;
 218 }
 219
 220
 221 int
 222 iterate_table (htab, ptr, key, keylen, data)
 223      const hash_table *htab;
 224      void **ptr;
 225      const void **key;
 226      size_t *keylen;
 227      void **data;
 228 {
 229   if (*ptr == NULL)
 230     {
 231       if (htab->first == NULL)
 232         return -1;
 233       *ptr = (void *) ((hash_entry *) htab->first)->next;
 234     }
 235   else
 236     {
 237       if (*ptr == htab->first)
 238         return -1;
 239       *ptr = (void *) (((hash_entry *) *ptr)->next);
 240     }
 241
 242   *key = ((hash_entry *) *ptr)->key;
 243   *keylen = ((hash_entry *) *ptr)->keylen;
 244   *data = ((hash_entry *) *ptr)->data;
 245   return 0;
 246 }
 247
 248
 249 /* References:
 250    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 251    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 252
 253 static size_t
 254 lookup (htab, key, keylen, hval)
 255      const hash_table *htab;
 256      const void *key;
 257      size_t keylen;
 258      unsigned long int hval;
 259 {
 260   unsigned long int hash;
 261   size_t idx;
 262   hash_entry *table = (hash_entry *) htab->table;
 263
 264   /* First hash function: simply take the modul but prevent zero.  */
 265   hash = 1 + hval % htab->size;
 266
 267   idx = hash;
 268
 269   if (table[idx].used)
 270     {
 271       if (table[idx].used == hval && table[idx].keylen == keylen
 272           && memcmp (table[idx].key, key, keylen) == 0)
 273         return idx;
 274
 275       /* Second hash function as suggested in [Knuth].  */
 276       hash = 1 + hval % (htab->size - 2);
 277
 278       do
 279         {
 280           if (idx <= hash)
 281             idx = htab->size + idx - hash;
 282           else
 283             idx -= hash;
 284
 285           /* If entry is found use it.  */
 286           if (table[idx].used == hval && table[idx].keylen == keylen
 287               && memcmp (table[idx].key, key, keylen) == 0)
 288             return idx;
 289         }
 290       while (table[idx].used);
 291     }
 292   return idx;
 293 }
 294
 295
 296 unsigned long int
 297 next_prime (seed)
 298      unsigned long int seed;
 299 {
 300   /* Make it definitely odd.  */
 301   seed |= 1;
 302
 303   while (!is_prime (seed))
 304     seed += 2;
 305
 306   return seed;
 307 }
 308
 309
 310 static int
 311 is_prime (candidate)
 312      unsigned long int candidate;
 313 {
 314   /* No even number and none less than 10 will be passed here.  */
 315   unsigned long int divn = 3;
 316   unsigned long int sq = divn * divn;
 317
 318   while (sq < candidate && candidate % divn != 0)
 319     {
 320       ++divn;
 321       sq += 4 * divn;
 322       ++divn;
 323     }
 324
 325   return candidate % divn != 0;
 326 }