locale/programs/simple-hash.c

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