lib/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  *  rebuild_table() - Create new hash table when old one fills up.
  53  *
  54  *  tptr: Pointer to a hash table
  55  */
  56 void rebuild_table(hash_t *tptr)
  57 {
  58         hash_node_t **old_bucket, *old_hash, *tmp;
  59         int old_size, h, i;
  60
  61         old_bucket=tptr->bucket;
  62         old_size=tptr->size;
  63
  64         /* create a new table and rehash old buckets */
  65         hash_init(tptr, old_size<<1);
  66         for (i=0; i<old_size; i++)
  67         {
  68                 old_hash=old_bucket[i];
  69                 while(old_hash)
  70                 {
  71                         tmp=old_hash;
  72                         old_hash=old_hash->next;
  73                         h=hash(tptr, tmp->key);
  74                         tmp->next=tptr->bucket[h];
  75                         tptr->bucket[h]=tmp;
  76                         tptr->entries++;
  77                 } /* while */
  78         } /* for */
  79
  80         /* free memory used by old table */
  81         free(old_bucket);
  82
  83         return;
  84 }
  85
  86 /**************************************************/
  87
  88 /*
  89  *  hash_init() - Initialize a new hash table.
  90  *
  91  *  tptr: Pointer to the hash table to initialize
  92  *  buckets: The number of initial buckets to create
  93  */
  94 void hash_init(hash_t *tptr, int buckets)
  95 {
  96         /* make sure we allocate something */
  97         if (buckets==0) buckets=16;
  98
  99         /* initialize the table */
 100         tptr->entries=0;
 101         tptr->size=2;
 102         tptr->mask=1;
 103         tptr->downshift=29;
 104
 105         /* ensure buckets is a power of 2 */
 106         while (tptr->size<buckets)
 107         {
 108                 tptr->size<<=1;
 109                 tptr->mask=(tptr->mask<<1)+1;
 110                 tptr->downshift--;
 111         } /* while */
 112
 113         /* allocate memory for table */
 114         tptr->bucket=(hash_node_t **) calloc(tptr->size, sizeof(hash_node_t *));
 115
 116         return;
 117 }
 118
 119 /**************************************************/
 120
 121 /*
 122  *  hash_lookup() - Lookup an entry in the hash table and return a pointer to
 123  *    it or HASH_FAIL if it wasn't found.
 124  *
 125  *  tptr: Pointer to the hash table
 126  *  key: The key to lookup
 127  */
 128 uintptr_t hash_lookup(const hash_t *tptr, const char *key)
 129 {
 130         int h;
 131         hash_node_t *node;
 132
 133         /* find the entry in the hash table */
 134         h=hash(tptr, key);
 135         for (node=tptr->bucket[h]; node!=NULL; node=node->next)
 136         {
 137                 if (!strcmp(node->key, key)) break;
 138         }
 139
 140         /* return the entry if it exists, or HASH_FAIL */
 141         return(node ? node->data : HASH_FAIL);
 142 }
 143
 144 /**************************************************/
 145
 146 /*
 147  *  hash_insert() - Insert an entry into the hash table.  If the entry already
 148  *  exists return a pointer to it, otherwise return HASH_FAIL.
 149  *
 150  *  tptr: A pointer to the hash table
 151  *  key: The key to insert into the hash table
 152  *  data: A pointer to the data to insert into the hash table
 153  */
 154 uintptr_t hash_insert(hash_t *tptr, const char *key, uintptr_t data)
 155 {
 156         uintptr_t tmp;
 157         hash_node_t *node;
 158         int h;
 159
 160         /* check to see if the entry exists */
 161         if ((tmp=hash_lookup(tptr, key)) != HASH_FAIL) return(tmp);
 162
 163         /* expand the table if needed */
 164         while (tptr->entries>=HASH_LIMIT*tptr->size)
 165         rebuild_table(tptr);
 166
 167         /* insert the new entry */
 168         h=hash(tptr, key);
 169         node=(struct hash_node_t *) malloc(sizeof(hash_node_t));
 170         node->data=data;
 171         node->key=key;
 172         node->next=tptr->bucket[h];
 173         tptr->bucket[h]=node;
 174         tptr->entries++;
 175
 176         return HASH_FAIL;
 177 }
 178
 179 /**************************************************/
 180
 181 /*
 182  *  hash_delete() - Remove an entry from a hash table and return a pointer
 183  *  to its data or HASH_FAIL if it wasn't found.
 184  *
 185  *  tptr: A pointer to the hash table
 186  *  key: The key to remove from the hash table
 187  */
 188 uintptr_t hash_delete(hash_t *tptr, const char *key)
 189 {
 190         hash_node_t *node, *last;
 191         uintptr_t data;
 192         int h;
 193
 194         /* find the node to remove */
 195         h=hash(tptr, key);
 196         for (node=tptr->bucket[h]; node; node=node->next)
 197         {
 198                 if (!strcmp(node->key, key)) break;
 199         }
 200
 201         /* Didn't find anything, return HASH_FAIL */
 202         if (node==NULL) return HASH_FAIL;
 203
 204         /* if node is at head of bucket, we have it easy */
 205         if (node==tptr->bucket[h]) tptr->bucket[h]=node->next;
 206         else
 207         {
 208                 /* find the node before the node we want to remove */
 209                 for (last=tptr->bucket[h]; last && last->next; last=last->next)
 210                 {
 211                         if (last->next==node)
 212                         break;
 213                 }
 214                 last->next=node->next;
 215         }
 216
 217         /* free memory and return the data */
 218         data=node->data;
 219         free(node);
 220
 221         return(data);
 222 }
 223
 224 /**************************************************/
 225
 226 /*
 227  * hash_destroy() - Delete the entire table, and all remaining entries.
 228  */
 229 void hash_destroy(hash_t *tptr)
 230 {
 231         hash_node_t *node, *last;
 232         int i;
 233
 234         for (i=0; i<tptr->size; i++)
 235         {
 236                 node = tptr->bucket[i];
 237                 while (node != NULL)
 238                 {
 239                         last = node;
 240                         node = node->next;
 241                         free(last);
 242                 }
 243         }
 244
 245         /* free the entire array of buckets */
 246         if (tptr->bucket != NULL)
 247         {
 248                 free(tptr->bucket);
 249                 memset(tptr, 0, sizeof(hash_t));
 250         }
 251 }
 252
 253 /**************************************************/
 254
 255 /*
 256  *  alos() - Find the average length of search.
 257  *
 258  *  tptr: Pointer to a hash table
 259  */
 260 static float alos(hash_t *tptr)
 261 {
 262         int i,j;
 263         float alos=0;
 264         hash_node_t *node;
 265
 266         for (i=0; i<tptr->size; i++)
 267         {
 268                 for (node=tptr->bucket[i], j=0; node!=NULL; node=node->next, j++);
 269                 if (j) alos+=((j*(j+1))>>1);
 270         } /* for */
 271
 272         return(tptr->entries ? alos/tptr->entries : 0);
 273 }
 274
 275 /**************************************************/
 276
 277 /*
 278  *  hash_stats() - Return a string with stats about a hash table.
 279  *
 280  *  tptr: A pointer to the hash table
 281  */
 282 char * hash_stats(hash_t *tptr)
 283 {
 284         static char buf[1024];
 285
 286         sprintf(buf, "%u slots, %u entries, and %1.2f ALOS",(int)tptr->size, (int)tptr->entries, alos(tptr));
 287
 288         return(buf);
 289 }
 290
 291 /**************************************************/
 292
 293 /*
 294  * hash_print() - Print Keys in FILE *f
 295  *
 296  */
 297 void hash_print(hash_t *tptr,FILE *f)
 298 {
 299         hash_node_t *node, *last;
 300         int i;
 301
 302         for (i=0; i<tptr->size; i++)
 303         {
 304                 node = tptr->bucket[i];
 305                 while (node != NULL)
 306                 {
 307                         last = node;
 308                         node = node->next;
 309                         fprintf(f,"%s\n",last->key);
 310                 }
 311         }
 312 }
 313
 314