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