test-suite/hash.c

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