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