locale/hash.c

   1 /* Copyright (C) 1995 Free Software Foundation, Inc.
   2
   3 The GNU C Library is free software; you can redistribute it and/or
   4 modify it under the terms of the GNU Library General Public License as
   5 published by the Free Software Foundation; either version 2 of the
   6 License, or (at your option) any later version.
   7
   8 The GNU C Library is distributed in the hope that it will be useful,
   9 but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 Library General Public License for more details.
  12
  13 You should have received a copy of the GNU Library General Public
  14 License along with the GNU C Library; see the file COPYING.LIB.  If
  15 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  16 Cambridge, MA 02139, USA.  */
  17
  18 #include <obstack.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <values.h>
  22
  23 #include "hash.h"
  24
  25 #define obstack_chunk_alloc xmalloc
  26 #define obstack_chunk_free free
  27
  28 void *xmalloc (size_t n);
  29
  30 typedef struct hash_entry
  31   {
  32     int used;
  33     char *key;
  34     void *data;
  35     struct hash_entry *next;
  36   }
  37 hash_entry;
  38
  39 /* Prototypes for local functions.  */
  40 static size_t lookup (hash_table *htab, const char *key, size_t keylen,
  41                       unsigned long hval);
  42 static unsigned long compute_hashval(const char *key, size_t keylen);
  43 static unsigned long next_prime(unsigned long seed);
  44 static int is_prime(unsigned long candidate);
  45
  46
  47 int
  48 init_hash(hash_table *htab, unsigned long init_size)
  49 {
  50   /* We need the size to be a prime.  */
  51   init_size = next_prime (init_size);
  52
  53   /* Initialize the data structure.  */
  54   htab->size = init_size;
  55   htab->filled = 0;
  56   htab->first = NULL;
  57   htab->table = calloc (init_size + 1, sizeof (hash_entry));
  58   obstack_init (&htab->mem_pool);
  59
  60   return htab->table == NULL;
  61 }
  62
  63
  64 int
  65 delete_hash(hash_table *htab)
  66 {
  67   free (htab->table);
  68   obstack_free (&htab->mem_pool, NULL);
  69   return 0;
  70 }
  71
  72
  73 int
  74 insert_entry (hash_table *htab, const char *key, size_t keylen, void *data)
  75 {
  76   unsigned long hval = compute_hashval (key, keylen);
  77   hash_entry *table = (hash_entry *) htab->table;
  78   size_t idx = lookup (htab, key, keylen, hval);
  79
  80   if (table[idx].used)
  81     /* We don't want to overwrite the old value.  */
  82     return 1;
  83   else
  84     {
  85       hash_entry **p;
  86
  87       /* An empty bucket has been found.  */
  88       table[idx].used = hval;
  89       table[idx].key = obstack_copy0 (&htab->mem_pool, key, keylen);
  90       table[idx].data = data;
  91
  92       /* List the new value in the ordered list.  */
  93       for (p = (hash_entry **) &htab->first; *p != NULL && (*p)->data < data;
  94            p = &(*p)->next);
  95       if (*p == NULL || (*p)->data > data)
  96         /* Insert new value in the list.  */
  97         {
  98           table[idx].next = *p;
  99           *p = &table[idx];
 100         }
 101
 102       ++htab->filled;
 103       if (100 * htab->filled > 90 * htab->size)
 104         {
 105           /* Resize the table.  */
 106           unsigned long old_size = htab->size;
 107
 108           htab->size = next_prime (htab->size * 2);
 109           htab->filled = 0;
 110           htab->first = NULL;
 111           htab->table = calloc (htab->size, sizeof (hash_entry));
 112
 113           for (idx = 1; idx <= old_size; ++idx)
 114             if (table[idx].used)
 115               insert_entry (htab, table[idx].key, strlen(table[idx].key),
 116                             table[idx].data);
 117
 118           free (table);
 119         }
 120       return 0;
 121     }
 122   /* NOTREACHED */
 123 }
 124
 125
 126 int
 127 find_entry (hash_table *htab, const char *key, size_t keylen, void **result)
 128 {
 129   hash_entry *table = (hash_entry *) htab->table;
 130   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
 131   int retval;
 132
 133   retval = table[idx].used;
 134   *result = retval ? table[idx].data : NULL;
 135
 136   return retval;
 137 }
 138
 139
 140 int
 141 iterate_table (hash_table *htab, void **ptr, void **result)
 142 {
 143   if (*ptr == NULL)
 144     *ptr = (void *) htab->first;
 145   else
 146     {
 147       *ptr = (void *) (((hash_entry *) *ptr)->next);
 148       if (*ptr == NULL)
 149         return 0;
 150     }
 151
 152   *result = ((hash_entry *) *ptr)->data;
 153   return 1;
 154 }
 155
 156
 157 static size_t
 158 lookup (hash_table *htab, const char *key, size_t keylen, unsigned long hval)
 159 {
 160   unsigned long hash;
 161   size_t idx;
 162   hash_entry *table = (hash_entry *) htab->table;
 163
 164   /* First hash function: simply take the modul but prevent zero.  */
 165   hash = 1 + hval % htab->size;
 166
 167   idx = hash;
 168
 169   if (table[idx].used)
 170     {
 171       if (table[idx].used == hval && table[idx].key[keylen] == '\0'
 172           && strncmp (key, table[idx].key, keylen) == 0)
 173         return idx;
 174
 175       /* Second hash function as suggested in [Knuth].  */
 176       hash = 1 + hash % (htab->size - 2);
 177
 178       do
 179         {
 180           if (idx <= hash)
 181             idx = htab->size + idx - hash;
 182           else
 183             idx -= hash;
 184
 185           /* If entry is found use it.  */
 186           if (table[idx].used == hval && table[idx].key[keylen] == '\0'
 187               && strncmp (key, table[idx].key, keylen) == 0)
 188             return idx;
 189         }
 190       while (table[idx].used);
 191     }
 192   return idx;
 193 }
 194
 195
 196 static unsigned long
 197 compute_hashval(const char *key, size_t keylen)
 198 {
 199   size_t cnt;
 200   unsigned long hval, g;
 201   /* Compute the hash value for the given string.  */
 202   cnt = 0;
 203   hval = keylen;
 204   while (cnt < keylen)
 205     {
 206       hval <<= 4;
 207       hval += key[cnt++];
 208       g = hval & (0xf << (LONGBITS - 4));
 209       if (g != 0)
 210         {
 211           hval ^= g >> (LONGBITS - 8);
 212           hval ^= g;
 213         }
 214     }
 215   return hval;
 216 }
 217
 218
 219 static unsigned long
 220 next_prime(unsigned long seed)
 221 {
 222   /* Make it definitely odd.  */
 223   seed |= 1;
 224
 225   while (!is_prime (seed))
 226     seed += 2;
 227
 228   return seed;
 229 }
 230
 231
 232 static int
 233 is_prime(unsigned long candidate)
 234 {
 235   /* No even number and none less than 10 will be passwd here.  */
 236   unsigned long div = 3;
 237   unsigned long sq = div * div;
 238
 239   while (sq < candidate && candidate % div != 0)
 240     {
 241       ++div;
 242       sq += 4 * div;
 243       ++div;
 244     }
 245
 246   return candidate % div != 0;
 247 }
 248
 249 /*
 250  * Local Variables:
 251  *  mode:c
 252  *  c-basic-offset:2
 253  * End:
 254  */