gnu/dist/gettext/gettext-tools/lib/hash.c

   1 /* hash - implement simple hashing table with string based keys.
   2    Copyright (C) 1994-1995, 2000-2004 Free Software Foundation, Inc.
   3    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   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 #if HAVE_CONFIG_H
  20 # include <config.h>
  21 #endif
  22
  23 /* Specification.  */
  24 #include "hash.h"
  25
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <stdio.h>
  29 #include <limits.h>
  30 #include <sys/types.h>
  31
  32 #include <obstack.h>
  33
  34 #include "xalloc.h"
  35
  36 #define obstack_chunk_alloc xmalloc
  37 #define obstack_chunk_free free
  38
  39 typedef struct hash_entry
  40 {
  41   unsigned long used;
  42   const void *key;
  43   size_t keylen;
  44   void *data;
  45   struct hash_entry *next;
  46 }
  47 hash_entry;
  48
  49 /* Forward declaration of local functions.  */
  50 static void insert_entry_2 (hash_table *htab,
  51                             const void *key, size_t keylen,
  52                             unsigned long int hval, size_t idx, void *data);
  53 static size_t lookup (hash_table *htab,
  54                       const void *key, size_t keylen,
  55                       unsigned long int hval);
  56 static unsigned long compute_hashval (const void *key, size_t keylen);
  57 static int is_prime (unsigned long int candidate);
  58
  59
  60 int
  61 init_hash (hash_table *htab, unsigned long int init_size)
  62 {
  63   /* We need the size to be a prime.  */
  64   init_size = next_prime (init_size);
  65
  66   /* Initialize the data structure.  */
  67   htab->size = init_size;
  68   htab->filled = 0;
  69   htab->first = NULL;
  70   htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
  71
  72   obstack_init (&htab->mem_pool);
  73
  74   return 0;
  75 }
  76
  77
  78 int
  79 delete_hash (hash_table *htab)
  80 {
  81   free (htab->table);
  82   obstack_free (&htab->mem_pool, NULL);
  83   return 0;
  84 }
  85
  86
  87 int
  88 insert_entry (hash_table *htab, const void *key, size_t keylen, void *data)
  89 {
  90   unsigned long int hval = compute_hashval (key, keylen);
  91   hash_entry *table = (hash_entry *) htab->table;
  92   size_t idx = lookup (htab, key, keylen, hval);
  93
  94   if (table[idx].used)
  95     /* We don't want to overwrite the old value.  */
  96     return -1;
  97   else
  98     {
  99       /* An empty bucket has been found.  */
 100       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
 101                       keylen, hval, idx, data);
 102       return 0;
 103     }
 104 }
 105
 106 static void
 107 insert_entry_2 (hash_table *htab,
 108                 const void *key, size_t keylen,
 109                 unsigned long int hval, size_t idx, void *data)
 110 {
 111   hash_entry *table = (hash_entry *) htab->table;
 112
 113   table[idx].used = hval;
 114   table[idx].key = key;
 115   table[idx].keylen = keylen;
 116   table[idx].data = data;
 117
 118   /* List the new value in the list.  */
 119   if ((hash_entry *) htab->first == NULL)
 120     {
 121       table[idx].next = &table[idx];
 122       *(hash_entry **) &htab->first = &table[idx];
 123     }
 124   else
 125     {
 126       table[idx].next = ((hash_entry *) htab->first)->next;
 127       ((hash_entry *) htab->first)->next = &table[idx];
 128       *(hash_entry **) &htab->first = &table[idx];
 129     }
 130
 131   ++htab->filled;
 132   if (100 * htab->filled > 75 * htab->size)
 133     {
 134       /* Table is filled more than 75%.  Resize the table.  */
 135       unsigned long int old_size = htab->size;
 136
 137       htab->size = next_prime (htab->size * 2);
 138       htab->filled = 0;
 139       htab->first = NULL;
 140       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
 141
 142       for (idx = 1; idx <= old_size; ++idx)
 143         if (table[idx].used)
 144           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
 145                           table[idx].used,
 146                           lookup (htab, table[idx].key, table[idx].keylen,
 147                                   table[idx].used),
 148                           table[idx].data);
 149
 150       free (table);
 151     }
 152 }
 153
 154
 155 int
 156 find_entry (hash_table *htab, const void *key, size_t keylen, void **result)
 157 {
 158   hash_entry *table = (hash_entry *) htab->table;
 159   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 160
 161   if (table[idx].used == 0)
 162     return -1;
 163
 164   *result = table[idx].data;
 165   return 0;
 166 }
 167
 168
 169 int
 170 iterate_table (hash_table *htab, void **ptr, const void **key, size_t *keylen,
 171                void **data)
 172 {
 173   if (*ptr == NULL)
 174     {
 175       if (htab->first == NULL)
 176         return -1;
 177       *ptr = (void *) ((hash_entry *) htab->first)->next;
 178     }
 179   else
 180     {
 181       if (*ptr == htab->first)
 182         return -1;
 183       *ptr = (void *) (((hash_entry *) *ptr)->next);
 184     }
 185
 186   *key = ((hash_entry *) *ptr)->key;
 187   *keylen = ((hash_entry *) *ptr)->keylen;
 188   *data = ((hash_entry *) *ptr)->data;
 189   return 0;
 190 }
 191
 192
 193 /* References:
 194    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
 195    [Knuth]            The Art of Computer Programming, part3 (6.4) */
 196
 197 static size_t
 198 lookup (hash_table *htab,
 199         const void *key, size_t keylen,
 200         unsigned long int hval)
 201 {
 202   unsigned long int hash;
 203   size_t idx;
 204   hash_entry *table = (hash_entry *) htab->table;
 205
 206   /* First hash function: simply take the modul but prevent zero.  */
 207   hash = 1 + hval % htab->size;
 208
 209   idx = hash;
 210
 211   if (table[idx].used)
 212     {
 213       if (table[idx].used == hval && table[idx].keylen == keylen
 214           && memcmp (table[idx].key, key, keylen) == 0)
 215         return idx;
 216
 217       /* Second hash function as suggested in [Knuth].  */
 218       hash = 1 + hval % (htab->size - 2);
 219
 220       do
 221         {
 222           if (idx <= hash)
 223             idx = htab->size + idx - hash;
 224           else
 225             idx -= hash;
 226
 227           /* If entry is found use it.  */
 228           if (table[idx].used == hval && table[idx].keylen == keylen
 229               && memcmp (table[idx].key, key, keylen) == 0)
 230             return idx;
 231         }
 232       while (table[idx].used);
 233     }
 234   return idx;
 235 }
 236
 237
 238 static unsigned long
 239 compute_hashval (const void *key, size_t keylen)
 240 {
 241   size_t cnt;
 242   unsigned long int hval;
 243
 244   /* Compute the hash value for the given string.  The algorithm
 245      is taken from [Aho,Sethi,Ullman].  */
 246   cnt = 0;
 247   hval = keylen;
 248   while (cnt < keylen)
 249     {
 250       hval = (hval << 9) | (hval >> (sizeof (unsigned long) * CHAR_BIT - 9));
 251       hval += (unsigned long int) *(((const char *) key) + cnt++);
 252     }
 253   return hval != 0 ? hval : ~((unsigned long) 0);
 254 }
 255
 256
 257 unsigned long
 258 next_prime (unsigned long int seed)
 259 {
 260   /* Make it definitely odd.  */
 261   seed |= 1;
 262
 263   while (!is_prime (seed))
 264     seed += 2;
 265
 266   return seed;
 267 }
 268
 269
 270 static int
 271 is_prime (unsigned long int candidate)
 272 {
 273   /* No even number and none less than 10 will be passed here.  */
 274   unsigned long int divn = 3;
 275   unsigned long int sq = divn * divn;
 276
 277   while (sq < candidate && candidate % divn != 0)
 278     {
 279       ++divn;
 280       sq += 4 * divn;
 281       ++divn;
 282     }
 283
 284   return candidate % divn != 0;
 285 }