locale/programs/simple-hash.c

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