lib/hash.c

   1
   2 /*
   3  * $Id: hash.c,v 1.11 2001/01/12 00:37:12 wessels Exp $
   4  *
   5  * DEBUG: section 0     Hash Tables
   6  * AUTHOR: Harvest Derived
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "config.h"
  37
  38 #if HAVE_STDIO_H
  39 #include <stdio.h>
  40 #endif
  41 #if HAVE_STDLIB_H
  42 #include <stdlib.h>
  43 #endif
  44 #if HAVE_STRING_H
  45 #include <string.h>
  46 #endif
  47 #if HAVE_UNISTD_H
  48 #include <unistd.h>
  49 #endif
  50 #if HAVE_GNUMALLLOC_H
  51 #include <gnumalloc.h>
  52 #elif HAVE_MALLOC_H && !defined(_SQUID_FREEBSD_) && !defined(_SQUID_NEXT_)
  53 #include <malloc.h>
  54 #endif
  55 #if HAVE_ASSERT_H
  56 #include <assert.h>
  57 #endif
  58 #if HAVE_MATH_H
  59 #include <math.h>
  60 #endif
  61
  62 #include "hash.h"
  63 #include "util.h"
  64
  65 static void hash_next_bucket(hash_table * hid);
  66
  67 unsigned int
  68 hash_string(const void *data, unsigned int size)
  69 {
  70     const char *s = data;
  71     unsigned int n = 0;
  72     unsigned int j = 0;
  73     unsigned int i = 0;
  74     while (*s) {
  75         j++;
  76         n ^= 271 * (unsigned) *s++;
  77     }
  78     i = n ^ (j * 271);
  79     return i % size;
  80 }
  81
  82 /* the following function(s) were adapted from
  83  *    usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
  84
  85 /* Hash function from Chris Torek. */
  86 unsigned int
  87 hash4(const void *data, unsigned int size)
  88 {
  89     const char *key = data;
  90     size_t loop;
  91     unsigned int h;
  92     size_t len;
  93
  94 #define HASH4a   h = (h << 5) - h + *key++;
  95 #define HASH4b   h = (h << 5) + h + *key++;
  96 #define HASH4 HASH4b
  97
  98     h = 0;
  99     len = strlen(key);
 100     loop = len >> 3;
 101     switch (len & (8 - 1)) {
 102     case 0:
 103         break;
 104     case 7:
 105         HASH4;
 106         /* FALLTHROUGH */
 107     case 6:
 108         HASH4;
 109         /* FALLTHROUGH */
 110     case 5:
 111         HASH4;
 112         /* FALLTHROUGH */
 113     case 4:
 114         HASH4;
 115         /* FALLTHROUGH */
 116     case 3:
 117         HASH4;
 118         /* FALLTHROUGH */
 119     case 2:
 120         HASH4;
 121         /* FALLTHROUGH */
 122     case 1:
 123         HASH4;
 124     }
 125     while (loop--) {
 126         HASH4;
 127         HASH4;
 128         HASH4;
 129         HASH4;
 130         HASH4;
 131         HASH4;
 132         HASH4;
 133         HASH4;
 134     }
 135     return h % size;
 136 }
 137
 138 /*
 139  *  hash_create - creates a new hash table, uses the cmp_func
 140  *  to compare keys.  Returns the identification for the hash table;
 141  *  otherwise returns a negative number on error.
 142  */
 143 hash_table *
 144 hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
 145 {
 146     hash_table *hid = xcalloc(1, sizeof(hash_table));
 147     if (!hash_sz)
 148         hid->size = (unsigned int) DEFAULT_HASH_SIZE;
 149     else
 150         hid->size = (unsigned int) hash_sz;
 151     /* allocate and null the buckets */
 152     hid->buckets = xcalloc(hid->size, sizeof(hash_link *));
 153     hid->cmp = cmp_func;
 154     hid->hash = hash_func;
 155     hid->next = NULL;
 156     hid->current_slot = 0;
 157     return hid;
 158 }
 159
 160 /*
 161  *  hash_join - joins a hash_link under its key lnk->key
 162  *  into the hash table 'hid'.
 163  *
 164  *  It does not copy any data into the hash table, only links pointers.
 165  */
 166 void
 167 hash_join(hash_table * hid, hash_link * lnk)
 168 {
 169     int i;
 170     i = hid->hash(lnk->key, hid->size);
 171     lnk->next = hid->buckets[i];
 172     hid->buckets[i] = lnk;
 173     hid->count++;
 174 }
 175
 176 /*
 177  *  hash_lookup - locates the item under the key 'k' in the hash table
 178  *  'hid'.  Returns a pointer to the hash bucket on success; otherwise
 179  *  returns NULL.
 180  */
 181 void *
 182 hash_lookup(hash_table * hid, const void *k)
 183 {
 184     hash_link *walker;
 185     int b;
 186     assert(k != NULL);
 187     b = hid->hash(k, hid->size);
 188     for (walker = hid->buckets[b]; walker != NULL; walker = walker->next) {
 189         if ((hid->cmp) (k, walker->key) == 0)
 190             return (walker);
 191         assert(walker != walker->next);
 192     }
 193     return NULL;
 194 }
 195
 196 static void
 197 hash_next_bucket(hash_table * hid)
 198 {
 199     while (hid->next == NULL && ++hid->current_slot < hid->size)
 200         hid->next = hid->buckets[hid->current_slot];
 201 }
 202
 203 /*
 204  *  hash_first - initializes the hash table for the hash_next()
 205  *  function.
 206  */
 207 void
 208 hash_first(hash_table * hid)
 209 {
 210     assert(NULL == hid->next);
 211     hid->current_slot = 0;
 212     hid->next = hid->buckets[hid->current_slot];
 213     if (NULL == hid->next)
 214         hash_next_bucket(hid);
 215 }
 216
 217 /*
 218  *  hash_next - returns the next item in the hash table 'hid'.
 219  *  Otherwise, returns NULL on error or end of list.
 220  *
 221  *  MUST call hash_first() before hash_next().
 222  */
 223 void *
 224 hash_next(hash_table * hid)
 225 {
 226     hash_link *this = hid->next;
 227     if (NULL == this)
 228         return NULL;
 229     hid->next = this->next;
 230     if (NULL == hid->next)
 231         hash_next_bucket(hid);
 232     return this;
 233 }
 234
 235 /*
 236  *  hash_last - resets hash traversal state to NULL
 237  *
 238  */
 239 void
 240 hash_last(hash_table * hid)
 241 {
 242     assert(hid);
 243     hid->next = NULL;
 244     hid->current_slot = 0;
 245 }
 246
 247 /*
 248  *  hash_remove_link - deletes the given hash_link node from the
 249  *  hash table 'hid'.  Does not free the item, only removes it
 250  *  from the list.
 251  *
 252  *  On success, it returns 0 and deletes the link; otherwise,
 253  *  returns non-zero on error.
 254  */
 255 void
 256 hash_remove_link(hash_table * hid, hash_link * hl)
 257 {
 258     hash_link **P;
 259     int i;
 260     assert(hl != NULL);
 261     i = hid->hash(hl->key, hid->size);
 262     for (P = &hid->buckets[i]; *P; P = &(*P)->next) {
 263         if (*P != hl)
 264             continue;
 265         *P = hl->next;
 266         if (hid->next == hl) {
 267             hid->next = hl->next;
 268             if (NULL == hid->next)
 269                 hash_next_bucket(hid);
 270         }
 271         hid->count--;
 272         return;
 273     }
 274     assert(0);
 275 }
 276
 277 /*
 278  *  hash_get_bucket - returns the head item of the bucket
 279  *  in the hash table 'hid'. Otherwise, returns NULL on error.
 280  */
 281 hash_link *
 282 hash_get_bucket(hash_table * hid, unsigned int bucket)
 283 {
 284     if (bucket >= hid->size)
 285         return NULL;
 286     return (hid->buckets[bucket]);
 287 }
 288
 289 void
 290 hashFreeItems(hash_table * hid, HASHFREE * free_func)
 291 {
 292     hash_link *l;
 293     hash_link **list;
 294     int i = 0;
 295     int j;
 296     list = xcalloc(hid->count, sizeof(hash_link *));
 297     hash_first(hid);
 298     while ((l = hash_next(hid)) && i < hid->count) {
 299         *(list + i) = l;
 300         i++;
 301     }
 302     for (j = 0; j < i; j++)
 303         free_func(*(list + j));
 304     xfree(list);
 305 }
 306
 307 void
 308 hashFreeMemory(hash_table * hid)
 309 {
 310     assert(hid);
 311     if (hid->buckets)
 312         xfree(hid->buckets);
 313     xfree(hid);
 314 }
 315
 316 static int hash_primes[] =
 317 {
 318     103,
 319     229,
 320     467,
 321     977,
 322     1979,
 323     4019,
 324     6037,
 325     7951,
 326     12149,
 327     16231,
 328     33493,
 329     65357
 330 };
 331
 332 int
 333 hashPrime(int n)
 334 {
 335     int I = sizeof(hash_primes) / sizeof(int);
 336     int i;
 337     int best_prime = hash_primes[0];
 338     double min = fabs(log((double) n) - log((double) hash_primes[0]));
 339     double d;
 340     for (i = 0; i < I; i++) {
 341         d = fabs(log((double) n) - log((double) hash_primes[i]));
 342         if (d > min)
 343             continue;
 344         min = d;
 345         best_prime = hash_primes[i];
 346     }
 347     return best_prime;
 348 }
 349
 350 /*
 351  * return the key of a hash_link as a const string
 352  */
 353 const char *
 354 hashKeyStr(hash_link * hl)
 355 {
 356     return (const char *) hl->key;
 357 }
 358
 359
 360 #ifdef USE_HASH_DRIVER
 361 /*
 362  *  hash-driver - Run with a big file as stdin to insert each line into the
 363  *  hash table, then prints the whole hash table, then deletes a random item,
 364  *  and prints the table again...
 365  */
 366 int
 367 main(void)
 368 {
 369     hash_table *hid;
 370     int i;
 371     LOCAL_ARRAY(char, buf, BUFSIZ);
 372     LOCAL_ARRAY(char, todelete, BUFSIZ);
 373     hash_link *walker = NULL;
 374
 375     todelete[0] = '\0';
 376     printf("init\n");
 377
 378     printf("creating hash table\n");
 379     if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
 380         printf("hash_create error.\n");
 381         exit(1);
 382     }
 383     printf("done creating hash table: %d\n", hid);
 384
 385     while (fgets(buf, BUFSIZ, stdin)) {
 386         buf[strlen(buf) - 1] = '\0';
 387         printf("Inserting '%s' for item %p to hash table: %d\n",
 388             buf, buf, hid);
 389         hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
 390         if (random() % 17 == 0)
 391             strcpy(todelete, buf);
 392     }
 393
 394     printf("walking hash table...\n");
 395     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
 396         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
 397             walker->item);
 398     }
 399     printf("done walking hash table...\n");
 400
 401     if (todelete[0]) {
 402         printf("deleting %s from %d\n", todelete, hid);
 403         if (hash_delete(hid, todelete))
 404             printf("hash_delete error\n");
 405     }
 406     printf("walking hash table...\n");
 407     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
 408         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
 409             walker->item);
 410     }
 411     printf("done walking hash table...\n");
 412
 413
 414     printf("driver finished.\n");
 415     exit(0);
 416 }
 417 #endif