lib/hash.c

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 00    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 "squid.h"
  37 #include "hash.h"
  38 #include "profiler/Profiler.h"
  39
  40 #if HAVE_STDIO_H
  41 #include <stdio.h>
  42 #endif
  43 #if HAVE_STDLIB_H
  44 #include <stdlib.h>
  45 #endif
  46 #if HAVE_STRING_H
  47 #include <string.h>
  48 #endif
  49 #if HAVE_UNISTD_H
  50 #include <unistd.h>
  51 #endif
  52 #if HAVE_GNUMALLLOC_H
  53 #include <gnumalloc.h>
  54 #elif HAVE_MALLOC_H
  55 #include <malloc.h>
  56 #endif
  57 #if HAVE_ASSERT_H
  58 #include <assert.h>
  59 #endif
  60 #if HAVE_MATH_H
  61 #include <math.h>
  62 #endif
  63
  64 static void hash_next_bucket(hash_table * hid);
  65
  66 unsigned int
  67 hash_string(const void *data, unsigned int size)
  68 {
  69     const char *s = data;
  70     unsigned int n = 0;
  71     unsigned int j = 0;
  72     unsigned int i = 0;
  73     while (*s) {
  74         j++;
  75         n ^= 271 * (unsigned) *s++;
  76     }
  77     i = n ^ (j * 271);
  78     return i % size;
  79 }
  80
  81 /* the following function(s) were adapted from
  82  *    usr/src/lib/libc/db/hash_func.c, 4.4 BSD lite */
  83
  84 /* Hash function from Chris Torek. */
  85 unsigned int
  86 hash4(const void *data, unsigned int size)
  87 {
  88     const char *key = data;
  89     size_t loop;
  90     unsigned int h;
  91     size_t len;
  92
  93 #define HASH4a   h = (h << 5) - h + *key++;
  94 #define HASH4b   h = (h << 5) + h + *key++;
  95 #define HASH4 HASH4b
  96
  97     h = 0;
  98     len = strlen(key);
  99     loop = len >> 3;
 100     switch (len & (8 - 1)) {
 101     case 0:
 102         break;
 103     case 7:
 104         HASH4;
 105         /* FALLTHROUGH */
 106     case 6:
 107         HASH4;
 108         /* FALLTHROUGH */
 109     case 5:
 110         HASH4;
 111         /* FALLTHROUGH */
 112     case 4:
 113         HASH4;
 114         /* FALLTHROUGH */
 115     case 3:
 116         HASH4;
 117         /* FALLTHROUGH */
 118     case 2:
 119         HASH4;
 120         /* FALLTHROUGH */
 121     case 1:
 122         HASH4;
 123     }
 124     while (loop--) {
 125         HASH4;
 126         HASH4;
 127         HASH4;
 128         HASH4;
 129         HASH4;
 130         HASH4;
 131         HASH4;
 132         HASH4;
 133     }
 134     return h % size;
 135 }
 136
 137 /*
 138  *  hash_create - creates a new hash table, uses the cmp_func
 139  *  to compare keys.  Returns the identification for the hash table;
 140  *  otherwise returns a negative number on error.
 141  */
 142 hash_table *
 143 hash_create(HASHCMP * cmp_func, int hash_sz, HASHHASH * hash_func)
 144 {
 145     hash_table *hid = xcalloc(1, sizeof(hash_table));
 146     if (!hash_sz)
 147         hid->size = (unsigned int) DEFAULT_HASH_SIZE;
 148     else
 149         hid->size = (unsigned int) hash_sz;
 150     /* allocate and null the buckets */
 151     hid->buckets = xcalloc(hid->size, sizeof(hash_link *));
 152     hid->cmp = cmp_func;
 153     hid->hash = hash_func;
 154     hid->next = NULL;
 155     hid->current_slot = 0;
 156     return hid;
 157 }
 158
 159 /*
 160  *  hash_join - joins a hash_link under its key lnk->key
 161  *  into the hash table 'hid'.
 162  *
 163  *  It does not copy any data into the hash table, only links pointers.
 164  */
 165 void
 166 hash_join(hash_table * hid, hash_link * lnk)
 167 {
 168     int i;
 169     i = hid->hash(lnk->key, hid->size);
 170     lnk->next = hid->buckets[i];
 171     hid->buckets[i] = lnk;
 172     hid->count++;
 173 }
 174
 175 /*
 176  *  hash_lookup - locates the item under the key 'k' in the hash table
 177  *  'hid'.  Returns a pointer to the hash bucket on success; otherwise
 178  *  returns NULL.
 179  */
 180 hash_link *
 181 hash_lookup(hash_table * hid, const void *k)
 182 {
 183     hash_link *walker;
 184     int b;
 185     PROF_start(hash_lookup);
 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             PROF_stop(hash_lookup);
 191             return (walker);
 192         }
 193         assert(walker != walker->next);
 194     }
 195     PROF_stop(hash_lookup);
 196     return NULL;
 197 }
 198
 199 static void
 200 hash_next_bucket(hash_table * hid)
 201 {
 202     while (hid->next == NULL && ++hid->current_slot < hid->size)
 203         hid->next = hid->buckets[hid->current_slot];
 204 }
 205
 206 /*
 207  *  hash_first - initializes the hash table for the hash_next()
 208  *  function.
 209  */
 210 void
 211 hash_first(hash_table * hid)
 212 {
 213     assert(NULL == hid->next);
 214     hid->current_slot = 0;
 215     hid->next = hid->buckets[hid->current_slot];
 216     if (NULL == hid->next)
 217         hash_next_bucket(hid);
 218 }
 219
 220 /*
 221  *  hash_next - returns the next item in the hash table 'hid'.
 222  *  Otherwise, returns NULL on error or end of list.
 223  *
 224  *  MUST call hash_first() before hash_next().
 225  */
 226 hash_link *
 227 hash_next(hash_table * hid)
 228 {
 229     hash_link *this = hid->next;
 230     if (NULL == this)
 231         return NULL;
 232     hid->next = this->next;
 233     if (NULL == hid->next)
 234         hash_next_bucket(hid);
 235     return this;
 236 }
 237
 238 /*
 239  *  hash_last - resets hash traversal state to NULL
 240  *
 241  */
 242 void
 243 hash_last(hash_table * hid)
 244 {
 245     assert(hid != NULL);
 246     hid->next = NULL;
 247     hid->current_slot = 0;
 248 }
 249
 250 /*
 251  *  hash_remove_link - deletes the given hash_link node from the
 252  *  hash table 'hid'.  Does not free the item, only removes it
 253  *  from the list.
 254  *
 255  *  An assertion is triggered if the hash_link is not found in the
 256  *  list.
 257  */
 258 void
 259 hash_remove_link(hash_table * hid, hash_link * hl)
 260 {
 261     hash_link **P;
 262     int i;
 263     assert(hl != NULL);
 264     i = hid->hash(hl->key, hid->size);
 265     for (P = &hid->buckets[i]; *P; P = &(*P)->next) {
 266         if (*P != hl)
 267             continue;
 268         *P = hl->next;
 269         if (hid->next == hl) {
 270             hid->next = hl->next;
 271             if (NULL == hid->next)
 272                 hash_next_bucket(hid);
 273         }
 274         hid->count--;
 275         return;
 276     }
 277     assert(0);
 278 }
 279
 280 /*
 281  *  hash_get_bucket - returns the head item of the bucket
 282  *  in the hash table 'hid'. Otherwise, returns NULL on error.
 283  */
 284 hash_link *
 285 hash_get_bucket(hash_table * hid, unsigned int bucket)
 286 {
 287     if (bucket >= hid->size)
 288         return NULL;
 289     return (hid->buckets[bucket]);
 290 }
 291
 292 void
 293 hashFreeItems(hash_table * hid, HASHFREE * free_func)
 294 {
 295     hash_link *l;
 296     hash_link **list;
 297     int i = 0;
 298     int j;
 299     list = xcalloc(hid->count, sizeof(hash_link *));
 300     hash_first(hid);
 301     while ((l = hash_next(hid)) && i < hid->count) {
 302         *(list + i) = l;
 303         i++;
 304     }
 305     for (j = 0; j < i; j++)
 306         free_func(*(list + j));
 307     xfree(list);
 308 }
 309
 310 void
 311 hashFreeMemory(hash_table * hid)
 312 {
 313     if (hid == NULL)
 314         return;
 315     if (hid->buckets)
 316         xfree(hid->buckets);
 317     xfree(hid);
 318 }
 319
 320 static int hash_primes[] = {
 321     103,
 322     229,
 323     467,
 324     977,
 325     1979,
 326     4019,
 327     6037,
 328     7951,
 329     12149,
 330     16231,
 331     33493,
 332     65357
 333 };
 334
 335 int
 336 hashPrime(int n)
 337 {
 338     int I = sizeof(hash_primes) / sizeof(int);
 339     int i;
 340     int best_prime = hash_primes[0];
 341     double min = fabs(log((double) n) - log((double) hash_primes[0]));
 342     double d;
 343     for (i = 0; i < I; i++) {
 344         d = fabs(log((double) n) - log((double) hash_primes[i]));
 345         if (d > min)
 346             continue;
 347         min = d;
 348         best_prime = hash_primes[i];
 349     }
 350     return best_prime;
 351 }
 352
 353 /*
 354  * return the key of a hash_link as a const string
 355  */
 356 const char *
 357 hashKeyStr(hash_link * hl)
 358 {
 359     return (const char *) hl->key;
 360 }
 361
 362
 363 #if USE_HASH_DRIVER
 364 /*
 365  *  hash-driver - Run with a big file as stdin to insert each line into the
 366  *  hash table, then prints the whole hash table, then deletes a random item,
 367  *  and prints the table again...
 368  */
 369 int
 370 main(void)
 371 {
 372     hash_table *hid;
 373     int i;
 374     LOCAL_ARRAY(char, buf, BUFSIZ);
 375     LOCAL_ARRAY(char, todelete, BUFSIZ);
 376     hash_link *walker = NULL;
 377
 378     todelete[0] = '\0';
 379     printf("init\n");
 380
 381     printf("creating hash table\n");
 382     if ((hid = hash_create((HASHCMP *) strcmp, 229, hash4)) < 0) {
 383         printf("hash_create error.\n");
 384         exit(1);
 385     }
 386     printf("done creating hash table: %d\n", hid);
 387
 388     while (fgets(buf, BUFSIZ, stdin)) {
 389         buf[strlen(buf) - 1] = '\0';
 390         printf("Inserting '%s' for item %p to hash table: %d\n",
 391                buf, buf, hid);
 392         hash_insert(hid, xstrdup(buf), (void *) 0x12345678);
 393         if (random() % 17 == 0)
 394             strcpy(todelete, buf);
 395     }
 396
 397     printf("walking hash table...\n");
 398     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
 399         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
 400                walker->item);
 401     }
 402     printf("done walking hash table...\n");
 403
 404     if (todelete[0]) {
 405         printf("deleting %s from %d\n", todelete, hid);
 406         if (hash_delete(hid, todelete))
 407             printf("hash_delete error\n");
 408     }
 409     printf("walking hash table...\n");
 410     for (i = 0, walker = hash_first(hid); walker; walker = hash_next(hid)) {
 411         printf("item %5d: key: '%s' item: %p\n", i++, walker->key,
 412                walker->item);
 413     }
 414     printf("done walking hash table...\n");
 415
 416
 417     printf("driver finished.\n");
 418     exit(0);
 419 }
 420 #endif