lib/hash.cc

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