src/protocols/jabber/genhash.c

   1 /*
   2  *  This program is free software; you can redistribute it and/or modify
   3  *  it under the terms of the GNU General Public License as published by
   4  *  the Free Software Foundation; either version 2 of the License, or
   5  *  (at your option) any later version.
   6  *
   7  *  This program is distributed in the hope that it will be useful,
   8  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  *  GNU General Public License for more details.
  11  *
  12  *  You should have received a copy of the GNU General Public License
  13  *  along with this program; if not, write to the Free Software
  14  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  15  *
  16  *  Jabber
  17  *  Copyright (C) 1998-1999 The Jabber Team http://jabber.org/
  18  */
  19 #include <libxode.h>
  20
  21 /*****************************************************************************
  22  * Internal type definitions
  23  */
  24
  25 typedef struct tagHNODE
  26 {
  27     struct tagHNODE *next;             /* next node in list */
  28     const void *key;                   /* key pointer */
  29     void *value;                       /* value pointer */
  30 } HNODE;
  31
  32 #define SLAB_NUM_NODES     64        /* allocate this many nodes per slab */
  33
  34 typedef struct tagHSLAB
  35 {
  36     struct tagHSLAB *next;             /* next slab pointer */
  37     HNODE nodes[SLAB_NUM_NODES];       /* the actual nodes */
  38 } HSLAB;
  39
  40 #define HASH_NUM_BUCKETS   509       /* should be a prime number; see Knuth */
  41
  42 typedef struct tagHASHTABLE_INTERNAL
  43 {
  44     unsigned long sig1;                /* first signature word */
  45     KEYHASHFUNC hash;                  /* hash function */
  46     KEYCOMPAREFUNC cmp;                /* comparison function */
  47     int count;                         /* table entry count */
  48     int bcount;                        /* bucket count */
  49     HNODE **buckets;                   /* the hash buckets */
  50     unsigned long sig2;                /* second signature word */
  51
  52 } HASHTABLE_INTERNAL;
  53
  54 #define HASH_SIG1      0x68736148UL  /* "Hash" */
  55 #define HASH_SIG2      0x6F627245UL  /* "Erbo" */
  56
  57 #define do_hash(tb,key)     ((*((tb)->hash))(key) % ((tb)->bcount))
  58
  59 static HNODE *s_free_nodes = NULL;   /* free nodes list */
  60 static HSLAB *s_slabs = NULL;        /* node slabs list */
  61
  62 /*****************************************************************************
  63  * Internal functions
  64  */
  65
  66 static HNODE *allocate_node(
  67     const void *key,   /* key pointer for this node */
  68     void *value)       /* value pointer for this node */
  69 /*
  70     allocate_node allocates a new hash node and fills it.  Returns NULL if the
  71     node could not be allocated.
  72 */
  73 {
  74     HNODE *rc;   /* return from this function */
  75
  76     if (!s_free_nodes)
  77     { /* allocate a new slabful of nodes and chain them to make a new free list */
  78         register int i;  /* loop counter */
  79         HSLAB *slab = (HSLAB *)malloc(sizeof(HSLAB));
  80         if (!slab)
  81             return NULL;
  82         memset(slab,0,sizeof(HSLAB));
  83         slab->next = s_slabs;
  84         for (i=0; i<(SLAB_NUM_NODES-1); i++)
  85             slab->nodes[i].next = &(slab->nodes[i+1]);
  86         s_free_nodes = &(slab->nodes[0]);
  87         s_slabs = slab;
  88
  89     } /* end if */
  90
  91     /* grab a node off the fron of the free list and fill it */
  92     rc = s_free_nodes;
  93     s_free_nodes = rc->next;
  94     rc->next = NULL;
  95     rc->key = key;
  96     rc->value = value;
  97     return rc;
  98
  99 } /* end allocate_node */
 100
 101 static void free_node(
 102     HNODE *node)   /* node to be freed */
 103 /*
 104     free_node returns a hash node to the list.
 105 */
 106 {
 107     /* zap the node contents to avoid problems later */
 108     memset(node,0,sizeof(HNODE));
 109
 110     /* chain it onto the free list */
 111     node->next = s_free_nodes;
 112     s_free_nodes = node;
 113
 114 } /* end free_node */
 115
 116 static HNODE *find_node(
 117     HASHTABLE_INTERNAL *tab,  /* pointer to hash table */
 118     const void *key,          /* key value to look up */
 119     int bucket)               /* bucket number (-1 to have function compute it) */
 120 /*
 121     find_node walks a hash bucket to find a node whose key matches the named key value.
 122     Returns the node pointer, or NULL if it's not found.
 123 */
 124 {
 125     register HNODE *p;  /* search pointer/return from this function */
 126
 127     if (bucket<0)  /* compute hash value if we don't know it already */
 128         bucket = do_hash(tab,key);
 129
 130     /* search through the bucket contents */
 131     for (p=tab->buckets[bucket]; p; p=p->next)
 132         if ((*(tab->cmp))(key,p->key)==0)
 133             return p;  /* found! */
 134
 135     return NULL;   /* not found */
 136
 137 } /* end find_node */
 138
 139 static HASHTABLE_INTERNAL *handle2ptr(
 140     HASHTABLE tbl)  /* hash table handle */
 141 /*
 142     handle2ptr converts a hash table handle into a pointer and checks its signatures
 143     to make sure someone's not trying to pull a whizzer on this module.
 144 */
 145 {
 146     register HASHTABLE_INTERNAL *rc = (HASHTABLE_INTERNAL *)tbl;
 147     if ((rc->sig1==HASH_SIG1) && (rc->sig2==HASH_SIG2))
 148         return rc;     /* signatures match */
 149     else
 150         return NULL;   /* yIkes! */
 151 }
 152
 153 /*****************************************************************************
 154  * External functions
 155  */
 156
 157 HASHTABLE ghash_create(int buckets, KEYHASHFUNC hash, KEYCOMPAREFUNC cmp)
 158 /*
 159     Description:
 160         Creates a new hash table.
 161
 162     Input:
 163         Parameters:
 164         buckets - Number of buckets to allocate for the hash table; this value
 165                   should be a prime number for maximum efficiency.
 166         hash - Key hash code function to use.
 167         cmp - Key comparison function to use.
 168
 169     Output:
 170         Returns:
 171         NULL - Table could not be allocated.
 172         Other - Handle to the new hashtable.
 173 */
 174 {
 175     HASHTABLE_INTERNAL *tab;  /* new table structure */
 176     char *allocated;
 177
 178     if (!hash || !cmp)
 179         return NULL;  /* bogus! */
 180
 181     if (buckets<=0)
 182         buckets = HASH_NUM_BUCKETS;
 183
 184     /* allocate a hash table structure */
 185     allocated = malloc(sizeof(HASHTABLE_INTERNAL) + (buckets * sizeof(HNODE *)));
 186     if (!allocated)
 187         return NULL;  /* memory error */
 188
 189     /* fill the fields of the hash table */
 190     tab = (HASHTABLE_INTERNAL *)allocated;
 191     allocated += sizeof(HASHTABLE_INTERNAL);
 192     memset(tab,0,sizeof(HASHTABLE_INTERNAL));
 193     memset(allocated,0,buckets * sizeof(HNODE *));
 194     tab->sig1 = HASH_SIG1;
 195     tab->hash = hash;
 196     tab->cmp = cmp;
 197     tab->bcount = buckets;
 198     tab->buckets = (HNODE **)allocated;
 199     tab->sig2 = HASH_SIG2;
 200
 201     return (HASHTABLE)tab;  /* Qa'pla! */
 202
 203 } /* end ghash_create */
 204
 205 void ghash_destroy(HASHTABLE tbl)
 206 /*
 207     Description:
 208         Destroys a hash table.
 209
 210     Input:
 211         Parameters:
 212         tbl - Table to be destroyed.
 213
 214     Output:
 215         Returns:
 216         Nothing.
 217 */
 218 {
 219     HASHTABLE_INTERNAL *tab;  /* new table structure */
 220     int i;                    /* loop counter */
 221     HNODE *p, *p2;            /* temporary pointers */
 222
 223     if (!tbl)
 224         return;  /* bogus! */
 225
 226     /* Convert the handle to a table pointer. */
 227     tab = handle2ptr(tbl);
 228     if (!tab)
 229         return;
 230
 231     /* Nuke the nodes it contains. */
 232     for (i=0; i<tab->bcount; i++)
 233     { /* free the contents of each bucket */
 234         p = tab->buckets[i];
 235         while (p)
 236         { /* free each node in turn */
 237             p2 = p->next;
 238             free_node(p);
 239             p = p2;
 240
 241         } /* end while */
 242
 243     } /* end for */
 244
 245     free(tab);  /* bye bye now! */
 246
 247 } /* end ghash_destroy */
 248
 249 void *ghash_get(HASHTABLE tbl, const void *key)
 250 /*
 251     Description:
 252         Retrieves a value stored in the hash table.
 253
 254     Input:
 255         Parameters:
 256         tbl - The hash table to look in.
 257         key - The key value to search on.
 258
 259     Output:
 260         Returns:
 261         NULL - Value not found.
 262         Other - Value corresponding to the specified key.
 263 */
 264 {
 265     HASHTABLE_INTERNAL *tab;  /* internal table pointer */
 266     HNODE *node;              /* hash node */
 267     void *rc = NULL;          /* return from this function */
 268
 269     if (!tbl || !key)
 270         return NULL;  /* bogus! */
 271
 272     /* Convert the handle to a table pointer. */
 273     tab = handle2ptr(tbl);
 274     if (!tab)
 275         return NULL;  /* error */
 276
 277     /* Attempt to find the node. */
 278     node = find_node(tab,key,-1);
 279     if (node)
 280         rc = node->value;  /* found it! */
 281
 282     return rc;
 283
 284 } /* end ghash_get */
 285
 286 int ghash_put(HASHTABLE tbl, const void *key, void *value)
 287 /*
 288     Description:
 289         Associates a key with a value in this hash table.
 290
 291     Input:
 292         Parameters:
 293         tbl - Hash table to add.
 294         key - Key to use for the value in the table.
 295         value - Value to add for this key.
 296
 297     Output:
 298         Returns:
 299         1 - Success.
 300         0 - Failure.
 301
 302     Notes:
 303         If the specified key is already in the hashtable, its value will be replaced.
 304 */
 305 {
 306     HASHTABLE_INTERNAL *tab;  /* internal table pointer */
 307     int bucket;               /* bucket value goes into */
 308     HNODE *node;              /* hash node */
 309     int rc = 1;               /* return from this function */
 310
 311     if (!tbl || !key || !value)
 312         return 0;  /* bogus! */
 313
 314     /* Convert the handle to a table pointer. */
 315     tab = handle2ptr(tbl);
 316     if (!tab)
 317         return 0;  /* error */
 318
 319
 320     /* Compute the hash bucket and try to find an existing node. */
 321     bucket = do_hash(tab,key);
 322     node = find_node(tab,key,bucket);
 323     if (!node)
 324     { /* OK, try to allocate a new node. */
 325         node = allocate_node(key,value);
 326         if (node)
 327         { /* Chain the new node into the hash table. */
 328             node->next = tab->buckets[bucket];
 329             tab->buckets[bucket] = node;
 330             tab->count++;
 331
 332         } /* end if */
 333         else  /* allocation error */
 334             rc = 0;
 335
 336     } /* end if */
 337     else  /* already in table - just reassign value */
 338         node->value = value;
 339
 340     return rc;
 341
 342 } /* end ghash_put */
 343
 344 int ghash_remove(HASHTABLE tbl, const void *key)
 345 /*
 346     Description:
 347         Removes an entry from a hash table, given its key.
 348
 349     Input:
 350         Parameters:
 351         tbl - Hash table to remove from.
 352         key - Key of value to remove.
 353
 354     Output:
 355         Returns:
 356         1 - Success.
 357         0 - Failure; key not present in hash table.
 358 */
 359 {
 360     HASHTABLE_INTERNAL *tab;  /* internal table pointer */
 361     int bucket;               /* bucket value goes into */
 362     HNODE *node;              /* hash node */
 363     register HNODE *p;        /* removal pointer */
 364     int rc = 1;               /* return from this function */
 365
 366     if (!tbl || !key)
 367         return 0;  /* bogus! */
 368
 369     /* Convert the handle to a table pointer. */
 370     tab = handle2ptr(tbl);
 371     if (!tab)
 372         return 0;  /* error */
 373
 374
 375     /* Compute the hash bucket and try to find an existing node. */
 376     bucket = do_hash(tab,key);
 377     node = find_node(tab,key,bucket);
 378     if (node)
 379     { /* look to unchain it from the bucket it's in */
 380         if (node==tab->buckets[bucket])
 381             tab->buckets[bucket] = node->next;  /* unchain at head */
 382         else
 383         { /* unchain in middle of list */
 384             for (p=tab->buckets[bucket]; p->next!=node; p=p->next) ;
 385             p->next = node->next;
 386
 387         } /* end else */
 388
 389         free_node(node);  /* bye bye now! */
 390         tab->count--;
 391
 392     } /* end if */
 393     else  /* node not found */
 394         rc = 0;
 395
 396     return rc;
 397
 398 } /* end ghash_remove */
 399
 400 int ghash_walk(HASHTABLE tbl, TABLEWALKFUNC func, void *user_data)
 401 /*
 402     Description:
 403         "Walks" through a hash table, calling a callback function for each element
 404     stored in it.
 405
 406     Input:
 407         Parameters:
 408         tbl - Hash table to walk.
 409         func - Function to be called for each node.  It takes three parameters,
 410                    a user data pointer, a key value pointer, and a data value pointer.
 411            It returns 0 to stop the enumeration or 1 to keep it going.
 412         user_data - Value to use as the first parameter for the callback
 413                     function.
 414
 415     Output:
 416         Returns:
 417         0 - Error occurred.
 418         Other - Number of nodes visited up to and including the one for which
 419                 the callback function returned 0, if it did; ranges from 1
 420             to the number of nodes in the hashtable.
 421 */
 422 {
 423     HASHTABLE_INTERNAL *tab;  /* internal table pointer */
 424     int i;                    /* loop counter */
 425     int running = 1;          /* we're still running */
 426     int count = 0;            /* number of nodes visited before stop node */
 427     register HNODE *p, *p2;   /* loop pointer */
 428
 429     if (!tbl || !func)
 430         return -1;  /* bogus values! */
 431
 432     /* Convert the handle to a table pointer. */
 433     tab = handle2ptr(tbl);
 434     if (!tab)
 435         return -1;  /* error */
 436
 437
 438     for (i=0; running && (i<tab->bcount); i++)
 439     { /* visit the contents of each bucket */
 440         p = tab->buckets[i];
 441         while (running && p)
 442         { /* visit each node in turn */
 443             p2 = p->next;
 444             count++;
 445             running = (*func)(user_data,p->key,p->value);
 446             p = p2;
 447
 448         } /* end while */
 449
 450     } /* end for */
 451
 452     return count;
 453
 454 } /* end ghash_walk */
 455
 456 int str_hash_code(const char *s)
 457 /*
 458     Description:
 459         Generates a hash code for a string.  This function uses the ELF hashing
 460         algorithm as reprinted in Andrew Binstock, "Hashing Rehashed," _Dr.
 461         Dobb's Journal_, April 1996.
 462
 463     Input:
 464         Parameters:
 465             s - The string to be hashed.
 466
 467     Output:
 468         Returns:
 469             A hash code for the string.
 470 */
 471 {
 472     /* ELF hash uses unsigned chars and unsigned arithmetic for portability */
 473     const unsigned char *name = (const unsigned char *)s;
 474     unsigned long h = 0, g;
 475
 476     if (!name)
 477         return 0;  /* anti-NULL guard not in the original */
 478
 479     while (*name)
 480     { /* do some fancy bitwanking on the string */
 481         h = (h << 4) + (unsigned long)(*name++);
 482         if ((g = (h & 0xF0000000UL))!=0)
 483             h ^= (g >> 24);
 484         h &= ~g;
 485
 486     } /* end while */
 487
 488     return (int)h;
 489
 490 }