Back to index

glibc  2.9
simple-hash.c
Go to the documentation of this file.
00001 /* Implement simple hashing table with string based keys.
00002    Copyright (C) 1994-1997,2000,2001,2002,2005 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004    Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
00005 
00006    This program is free software; you can redistribute it and/or modify
00007    it under the terms of the GNU General Public License as published
00008    by the Free Software Foundation; version 2 of the License, or
00009    (at your option) any later version.
00010 
00011    This program is distributed in the hope that it will be useful,
00012    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014    GNU General Public License for more details.
00015 
00016    You should have received a copy of the GNU General Public License
00017    along with this program; if not, write to the Free Software Foundation,
00018    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00019 
00020 #ifdef HAVE_CONFIG_H
00021 # include <config.h>
00022 #endif
00023 
00024 #include <stdio.h>
00025 #include <stdlib.h>
00026 #include <string.h>
00027 #include <sys/types.h>
00028 
00029 #if HAVE_OBSTACK
00030 # include <obstack.h>
00031 #else
00032 # include "obstack.h"
00033 #endif
00034 
00035 #ifdef HAVE_VALUES_H
00036 # include <values.h>
00037 #endif
00038 
00039 #include "simple-hash.h"
00040 
00041 #define obstack_chunk_alloc malloc
00042 #define obstack_chunk_free free
00043 
00044 #ifndef BITSPERBYTE
00045 # define BITSPERBYTE 8
00046 #endif
00047 
00048 #ifndef bcopy
00049 # define bcopy(s, d, n)     memcpy ((d), (s), (n))
00050 #endif
00051 
00052 #include "hashval.h"
00053 
00054 extern void *xmalloc (size_t __n);
00055 extern void *xcalloc (size_t __n, size_t __m);
00056 
00057 typedef struct hash_entry
00058 {
00059   unsigned long used;
00060   const void *key;
00061   size_t keylen;
00062   void *data;
00063   struct hash_entry *next;
00064 }
00065 hash_entry;
00066 
00067 /* Prototypes for local functions.  */
00068 static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
00069                          unsigned long hval, size_t idx, void *data);
00070 static size_t lookup (const hash_table *htab, const void *key, size_t keylen,
00071                     unsigned long int hval);
00072 static int is_prime (unsigned long int candidate);
00073 
00074 
00075 int
00076 init_hash (htab, init_size)
00077      hash_table *htab;
00078      unsigned long int init_size;
00079 {
00080   /* We need the size to be a prime.  */
00081   init_size = next_prime (init_size);
00082 
00083   /* Initialize the data structure.  */
00084   htab->size = init_size;
00085   htab->filled = 0;
00086   htab->first = NULL;
00087   htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
00088   if (htab->table == NULL)
00089     return -1;
00090 
00091   obstack_init (&htab->mem_pool);
00092 
00093   return 0;
00094 }
00095 
00096 
00097 int
00098 delete_hash (htab)
00099      hash_table *htab;
00100 {
00101   free (htab->table);
00102   obstack_free (&htab->mem_pool, NULL);
00103   return 0;
00104 }
00105 
00106 
00107 int
00108 insert_entry (htab, key, keylen, data)
00109      hash_table *htab;
00110      const void *key;
00111      size_t keylen;
00112      void *data;
00113 {
00114   unsigned long int hval = compute_hashval (key, keylen);
00115   hash_entry *table = (hash_entry *) htab->table;
00116   size_t idx = lookup (htab, key, keylen, hval);
00117 
00118   if (table[idx].used)
00119     /* We don't want to overwrite the old value.  */
00120     return -1;
00121   else
00122     {
00123       /* An empty bucket has been found.  */
00124       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
00125                     keylen, hval, idx, data);
00126       return 0;
00127     }
00128 }
00129 
00130 static void
00131 insert_entry_2 (htab, key, keylen, hval, idx, data)
00132      hash_table *htab;
00133      const void *key;
00134      size_t keylen;
00135      unsigned long int hval;
00136      size_t idx;
00137      void *data;
00138 {
00139   hash_entry *table = (hash_entry *) htab->table;
00140 
00141   table[idx].used = hval;
00142   table[idx].key = key;
00143   table[idx].keylen = keylen;
00144   table[idx].data = data;
00145 
00146       /* List the new value in the list.  */
00147   if ((hash_entry *) htab->first == NULL)
00148     {
00149       table[idx].next = &table[idx];
00150       htab->first = &table[idx];
00151     }
00152   else
00153     {
00154       table[idx].next = ((hash_entry *) htab->first)->next;
00155       ((hash_entry *) htab->first)->next = &table[idx];
00156       htab->first = &table[idx];
00157     }
00158 
00159   ++htab->filled;
00160   if (100 * htab->filled > 75 * htab->size)
00161     {
00162       /* Table is filled more than 75%.  Resize the table.
00163         Experiments have shown that for best performance, this threshold
00164         must lie between 40% and 85%.  */
00165       unsigned long int old_size = htab->size;
00166 
00167       htab->size = next_prime (htab->size * 2);
00168       htab->filled = 0;
00169       htab->first = NULL;
00170       htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
00171 
00172       for (idx = 1; idx <= old_size; ++idx)
00173        if (table[idx].used)
00174          insert_entry_2 (htab, table[idx].key, table[idx].keylen,
00175                        table[idx].used,
00176                        lookup (htab, table[idx].key, table[idx].keylen,
00177                               table[idx].used),
00178                        table[idx].data);
00179 
00180       free (table);
00181     }
00182 }
00183 
00184 
00185 int
00186 find_entry (htab, key, keylen, result)
00187      const hash_table *htab;
00188      const void *key;
00189      size_t keylen;
00190      void **result;
00191 {
00192   hash_entry *table = (hash_entry *) htab->table;
00193   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
00194 
00195   if (table[idx].used == 0)
00196     return -1;
00197 
00198   *result = table[idx].data;
00199   return 0;
00200 }
00201 
00202 
00203 int
00204 set_entry (htab, key, keylen, newval)
00205      hash_table *htab;
00206      const void *key;
00207      size_t keylen;
00208      void *newval;
00209 {
00210   hash_entry *table = (hash_entry *) htab->table;
00211   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
00212 
00213   if (table[idx].used == 0)
00214     return -1;
00215 
00216   table[idx].data = newval;
00217   return 0;
00218 }
00219 
00220 
00221 int
00222 iterate_table (htab, ptr, key, keylen, data)
00223      const hash_table *htab;
00224      void **ptr;
00225      const void **key;
00226      size_t *keylen;
00227      void **data;
00228 {
00229   if (*ptr == NULL)
00230     {
00231       if (htab->first == NULL)
00232        return -1;
00233       *ptr = (void *) ((hash_entry *) htab->first)->next;
00234     }
00235   else
00236     {
00237       if (*ptr == htab->first)
00238        return -1;
00239       *ptr = (void *) (((hash_entry *) *ptr)->next);
00240     }
00241 
00242   *key = ((hash_entry *) *ptr)->key;
00243   *keylen = ((hash_entry *) *ptr)->keylen;
00244   *data = ((hash_entry *) *ptr)->data;
00245   return 0;
00246 }
00247 
00248 
00249 /* References:
00250    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
00251    [Knuth]          The Art of Computer Programming, part3 (6.4) */
00252 
00253 static size_t
00254 lookup (htab, key, keylen, hval)
00255      const hash_table *htab;
00256      const void *key;
00257      size_t keylen;
00258      unsigned long int hval;
00259 {
00260   unsigned long int hash;
00261   size_t idx;
00262   hash_entry *table = (hash_entry *) htab->table;
00263 
00264   /* First hash function: simply take the modul but prevent zero.  */
00265   hash = 1 + hval % htab->size;
00266 
00267   idx = hash;
00268 
00269   if (table[idx].used)
00270     {
00271       if (table[idx].used == hval && table[idx].keylen == keylen
00272          && memcmp (table[idx].key, key, keylen) == 0)
00273        return idx;
00274 
00275       /* Second hash function as suggested in [Knuth].  */
00276       hash = 1 + hval % (htab->size - 2);
00277 
00278       do
00279        {
00280          if (idx <= hash)
00281            idx = htab->size + idx - hash;
00282          else
00283            idx -= hash;
00284 
00285          /* If entry is found use it.  */
00286          if (table[idx].used == hval && table[idx].keylen == keylen
00287              && memcmp (table[idx].key, key, keylen) == 0)
00288            return idx;
00289        }
00290       while (table[idx].used);
00291     }
00292   return idx;
00293 }
00294 
00295 
00296 unsigned long int
00297 next_prime (seed)
00298      unsigned long int seed;
00299 {
00300   /* Make it definitely odd.  */
00301   seed |= 1;
00302 
00303   while (!is_prime (seed))
00304     seed += 2;
00305 
00306   return seed;
00307 }
00308 
00309 
00310 static int
00311 is_prime (candidate)
00312      unsigned long int candidate;
00313 {
00314   /* No even number and none less than 10 will be passed here.  */
00315   unsigned long int divn = 3;
00316   unsigned long int sq = divn * divn;
00317 
00318   while (sq < candidate && candidate % divn != 0)
00319     {
00320       ++divn;
00321       sq += 4 * divn;
00322       ++divn;
00323     }
00324 
00325   return candidate % divn != 0;
00326 }