src/hash.cc

   1 /*
   2  * Copyright (C) 2004 Jesus Gimenez, Lluis Marquez and Senen Moya
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "hash.h"
  23
  24 /**************************************************/
  25
  26 #define HASH_LIMIT 0.5
  27
  28 /**************************************************/
  29
  30 /*
  31  *  hash() - Hash function returns a hash number for a given key.
  32  *
  33  *  tptr: Pointer to a hash table
  34  *  key: The key to create a hash number for
  35  */
  36 static int hash(const hash_t *tptr, const char *key)
  37 {
  38         int i=0;
  39         int hashvalue;
  40
  41         if (key) while (*key != '\0') i=(i<<3)+(*key++ - '0');
  42
  43         hashvalue = (((i*1103515249)>>tptr->downshift) & tptr->mask);
  44         if (hashvalue < 0) hashvalue = 0;
  45
  46         return hashvalue;
  47 }
  48
  49
  50 /**************************************************/
  51
  52 /*
  53  *  rebuild_table() - Create new hash table when old one fills up.
  54  *
  55  *  tptr: Pointer to a hash table
  56  */
  57 void rebuild_table(hash_t *tptr)
  58 {
  59         hash_node_t **old_bucket, *old_hash, *tmp;
  60         int old_size, h, i;
  61
  62         old_bucket=tptr->bucket;
  63         old_size=tptr->size;
  64
  65         /* create a new table and rehash old buckets */
  66         hash_init(tptr, old_size<<1);
  67         for (i=0; i<old_size; i++)
  68         {
  69                 old_hash=old_bucket[i];
  70                 while(old_hash)
  71                 {
  72                         tmp=old_hash;
  73                         old_hash=old_hash->next;
  74                         h=hash(tptr, tmp->key);
  75                         tmp->next=tptr->bucket[h];
  76                         tptr->bucket[h]=tmp;
  77                         tptr->entries++;
  78                 }                                                /* while */
  79         }                                                        /* for */
  80
  81         /* free memory used by old table */
  82         free(old_bucket);
  83
  84         return;
  85 }
  86
  87
  88 /**************************************************/
  89
  90 /*
  91  *  hash_init() - Initialize a new hash table.
  92  *
  93  *  tptr: Pointer to the hash table to initialize
  94  *  buckets: The number of initial buckets to create
  95  */
  96 void hash_init(hash_t *tptr, int buckets)
  97 {
  98         /* make sure we allocate something */
  99         if (buckets==0) buckets=16;
 100
 101         /* initialize the table */
 102         tptr->entries=0;
 103         tptr->size=2;
 104         tptr->mask=1;
 105         tptr->downshift=29;
 106
 107         /* ensure buckets is a power of 2 */
 108         while (tptr->size<buckets)
 109         {
 110                 tptr->size<<=1;
 111                 tptr->mask=(tptr->mask<<1)+1;
 112                 tptr->downshift--;
 113         }                                                        /* while */
 114
 115         /* allocate memory for table */
 116         tptr->bucket=(hash_node_t **) calloc(tptr->size, sizeof(hash_node_t *));
 117
 118         return;
 119 }
 120
 121
 122 /**************************************************/
 123
 124 /*
 125  *  hash_lookup() - Lookup an entry in the hash table and return a pointer to
 126  *    it or HASH_FAIL if it wasn't found.
 127  *
 128  *  tptr: Pointer to the hash table
 129  *  key: The key to lookup
 130  */
 131 uintptr_t hash_lookup(const hash_t *tptr, const char *key)
 132 {
 133         int h;
 134         hash_node_t *node;
 135
 136         /* find the entry in the hash table */
 137         h=hash(tptr, key);
 138         for (node=tptr->bucket[h]; node!=NULL; node=node->next)
 139         {
 140                 if (!strcmp(node->key, key)) break;
 141         }
 142
 143         /* return the entry if it exists, or HASH_FAIL */
 144         return(node ? node->data : HASH_FAIL);
 145 }
 146
 147
 148 /**************************************************/
 149
 150 /*
 151  *  hash_insert() - Insert an entry into the hash table.  If the entry already
 152  *  exists return a pointer to it, otherwise return HASH_FAIL.
 153  *
 154  *  tptr: A pointer to the hash table
 155  *  key: The key to insert into the hash table
 156  *  data: A pointer to the data to insert into the hash table
 157  */
 158 uintptr_t hash_insert(hash_t *tptr, const char *key, uintptr_t data)
 159 {
 160         uintptr_t tmp;
 161         hash_node_t *node;
 162         int h;
 163
 164         /* check to see if the entry exists */
 165         if ((tmp=hash_lookup(tptr, key)) != HASH_FAIL) return(tmp);
 166
 167         /* expand the table if needed */
 168         while (tptr->entries>=HASH_LIMIT*tptr->size)
 169                 rebuild_table(tptr);
 170
 171         /* insert the new entry */
 172         h=hash(tptr, key);
 173         node=(struct hash_node_t *) malloc(sizeof(hash_node_t));
 174         node->data=data;
 175         node->key=key;
 176         node->next=tptr->bucket[h];
 177         tptr->bucket[h]=node;
 178         tptr->entries++;
 179
 180         return HASH_FAIL;
 181 }
 182
 183
 184 /**************************************************/
 185
 186 /*
 187  *  hash_delete() - Remove an entry from a hash table and return a pointer
 188  *  to its data or HASH_FAIL if it wasn't found.
 189  *
 190  *  tptr: A pointer to the hash table
 191  *  key: The key to remove from the hash table
 192  */
 193 uintptr_t hash_delete(hash_t *tptr, const char *key)
 194 {
 195         hash_node_t *node, *last;
 196         uintptr_t data;
 197         int h;
 198
 199         /* find the node to remove */
 200         h=hash(tptr, key);
 201         for (node=tptr->bucket[h]; node; node=node->next)
 202         {
 203                 if (!strcmp(node->key, key)) break;
 204         }
 205
 206         /* Didn't find anything, return HASH_FAIL */
 207         if (node==NULL) return HASH_FAIL;
 208
 209         /* if node is at head of bucket, we have it easy */
 210         if (node==tptr->bucket[h]) tptr->bucket[h]=node->next;
 211         else
 212         {
 213                 /* find the node before the node we want to remove */
 214                 for (last=tptr->bucket[h]; last && last->next; last=last->next)
 215                 {
 216                         if (last->next==node)
 217                                 break;
 218                 }
 219                 last->next=node->next;
 220         }
 221
 222         /* free memory and return the data */
 223         data=node->data;
 224         free(node);
 225
 226         return(data);
 227 }
 228
 229
 230 /**************************************************/
 231
 232 /*
 233  * hash_destroy() - Delete the entire table, and all remaining entries.
 234  */
 235 void hash_destroy(hash_t *tptr)
 236 {
 237         hash_node_t *node, *last;
 238         int i;
 239
 240         for (i=0; i<tptr->size; i++)
 241         {
 242                 node = tptr->bucket[i];
 243                 while (node != NULL)
 244                 {
 245                         last = node;
 246                         node = node->next;
 247                         free(last);
 248                 }
 249         }
 250
 251         /* free the entire array of buckets */
 252         if (tptr->bucket != NULL)
 253         {
 254                 free(tptr->bucket);
 255                 memset(tptr, 0, sizeof(hash_t));
 256         }
 257 }
 258
 259
 260 /**************************************************/
 261
 262 /*
 263  *  alos() - Find the average length of search.
 264  *
 265  *  tptr: Pointer to a hash table
 266  */
 267 static float alos(hash_t *tptr)
 268 {
 269         int i,j;
 270         float alos=0;
 271         hash_node_t *node;
 272
 273         for (i=0; i<tptr->size; i++)
 274         {
 275                 for (node=tptr->bucket[i], j=0; node!=NULL; node=node->next, j++);
 276                 if (j) alos+=((j*(j+1))>>1);
 277         }                                                        /* for */
 278
 279         return(tptr->entries ? alos/tptr->entries : 0);
 280 }
 281
 282
 283 /**************************************************/
 284
 285 /*
 286  *  hash_stats() - Return a string with stats about a hash table.
 287  *
 288  *  tptr: A pointer to the hash table
 289  */
 290 char * hash_stats(hash_t *tptr)
 291 {
 292         static char buf[1024];
 293
 294         sprintf(buf, "%u slots, %u entries, and %1.2f ALOS",(int)tptr->size, (int)tptr->entries, alos(tptr));
 295
 296         return(buf);
 297 }
 298
 299
 300 /**************************************************/
 301
 302 /*
 303  * hash_print() - Print Keys in FILE *f
 304  *
 305  */
 306 void hash_print(hash_t *tptr,FILE *f)
 307 {
 308         hash_node_t *node, *last;
 309         int i;
 310
 311         for (i=0; i<tptr->size; i++)
 312         {
 313                 node = tptr->bucket[i];
 314                 while (node != NULL)
 315                 {
 316                         last = node;
 317                         node = node->next;
 318                         fprintf(f,"%s\n",last->key);
 319                 }
 320         }
 321 }