git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/htable.c

   1 /*
   2  *  Bacula hash table routines
   3  *
   4  *  htable is a hash table of items (pointers). This code is
   5  *    adapted and enhanced from code I wrote in 1982 for a
   6  *    relocatable linker.  At that time, the hash table size
   7  *    was fixed and a primary number, which essentially provides
   8  *    the randomness. In this program, the hash table can grow when
   9  *    it gets too full, so the table size here is a binary number. The
  10  *    hashing is provided using an idea from Tcl where the initial
  11  *    hash code is "randomized" using a simple calculation from
  12  *    a random number generator that multiplies by a big number
  13  *    (I multiply by a prime number, while Tcl did not)
  14  *    then shifts the result down and does the binary division
  15  *    by masking.  Increasing the size of the hash table is simple.
  16  *    Just create a new larger table, walk the old table and
  17  *    re-hash insert each entry into the new table.
  18  *
  19  *
  20  *   Kern Sibbald, July MMIII
  21  *
  22  *   Version $Id$
  23  *
  24  */
  25 /*
  26    Bacula® - The Network Backup Solution
  27
  28    Copyright (C) 2003-2006 Free Software Foundation Europe e.V.
  29
  30    The main author of Bacula is Kern Sibbald, with contributions from
  31    many others, a complete list can be found in the file AUTHORS.
  32    This program is Free Software; you can redistribute it and/or
  33    modify it under the terms of version two of the GNU General Public
  34    License as published by the Free Software Foundation plus additions
  35    that are listed in the file LICENSE.
  36
  37    This program is distributed in the hope that it will be useful, but
  38    WITHOUT ANY WARRANTY; without even the implied warranty of
  39    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  40    General Public License for more details.
  41
  42    You should have received a copy of the GNU General Public License
  43    along with this program; if not, write to the Free Software
  44    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  45    02110-1301, USA.
  46
  47    Bacula® is a registered trademark of John Walker.
  48    The licensor of Bacula is the Free Software Foundation Europe
  49    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  50    Switzerland, email:ftf@fsfeurope.org.
  51 */
  52
  53 #include "bacula.h"
  54
  55 #include "htable.h"
  56
  57 /* ===================================================================
  58  *    htable
  59  */
  60
  61 /*
  62  * Create hash of key, stored in hash then
  63  *  create and return the pseudo random bucket index
  64  */
  65 void htable::hash_index(char *key)
  66 {
  67    hash = 0;
  68    for (char *p=key; *p; p++) {
  69       hash += (hash << 3) + (uint32_t)*p;
  70    }
  71    /* Multiply by large prime number, take top bits, mask for remainder */
  72    index = ((hash * 1103515249) >> rshift) & mask;
  73    Dmsg2(100, "Leave hash_index hash=0x%x index=%d\n", hash, index);
  74    return;
  75 }
  76
  77 htable::htable(void *item, void *link, int tsize)
  78 {
  79    init(item, link, tsize);
  80 }
  81
  82 void htable::init(void *item, void *link, int tsize)
  83 {
  84    int pwr;
  85    tsize >>= 2;
  86    for (pwr=0; tsize; pwr++) {
  87       tsize >>= 1;
  88    }
  89    loffset = (char *)link - (char *)item;
  90    mask = ~((~0)<<pwr);               /* 3 bits => table size = 8 */
  91    rshift = 30 - pwr;                 /* start using bits 28, 29, 30 */
  92    num_items = 0;                     /* number of entries in table */
  93    buckets = 1<<pwr;                  /* hash table size -- power of two */
  94    max_items = buckets * 4;           /* allow average 4 entries per chain */
  95    table = (hlink **)malloc(buckets * sizeof(hlink *));
  96    memset(table, 0, buckets * sizeof(hlink *));
  97    walkptr = NULL;
  98    walk_index = 0;
  99 }
 100
 101 uint32_t htable::size()
 102 {
 103    return num_items;
 104 }
 105
 106 /*
 107  * Take each hash link and walk down the chain of items
 108  *  that hash there counting them (i.e. the hits),
 109  *  then report that number.
 110  *  Obiously, the more hits in a chain, the more time
 111  *  it takes to reference them. Empty chains are not so
 112  *  hot either -- as it means unused or wasted space.
 113  */
 114 #define MAX_COUNT 20
 115 void htable::stats()
 116 {
 117    int hits[MAX_COUNT];
 118    int max = 0;
 119    int i, j;
 120    hlink *p;
 121    printf("\n\nNumItems=%d\nTotal buckets=%d\n", num_items, buckets);
 122    printf("Hits/bucket: buckets\n");
 123    for (i=0; i < MAX_COUNT; i++) {
 124       hits[i] = 0;
 125    }
 126    for (i=0; i<(int)buckets; i++) {
 127       p = table[i];
 128       j = 0;
 129       while (p) {
 130          p = (hlink *)(p->next);
 131          j++;
 132       }
 133       if (j > max) {
 134          max = j;
 135       }
 136       if (j < MAX_COUNT) {
 137          hits[j]++;
 138       }
 139    }
 140    for (i=0; i < MAX_COUNT; i++) {
 141       printf("%2d:           %d\n",i, hits[i]);
 142    }
 143    printf("max hits in a bucket = %d\n", max);
 144 }
 145
 146 void htable::grow_table()
 147 {
 148    Dmsg1(100, "Grow called old size = %d\n", buckets);
 149    /* Setup a bigger table */
 150    htable *big = (htable *)malloc(sizeof(htable));
 151    big->loffset = loffset;
 152    big->mask = mask<<1 | 1;
 153    big->rshift = rshift - 1;
 154    big->num_items = 0;
 155    big->buckets = buckets * 2;
 156    big->max_items = big->buckets * 4;
 157    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 158    memset(big->table, 0, big->buckets * sizeof(hlink *));
 159    big->walkptr = NULL;
 160    big->walk_index = 0;
 161    /* Insert all the items in the new hash table */
 162    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 163    /*
 164     * We walk through the old smaller tree getting items,
 165     * but since we are overwriting the colision links, we must
 166     * explicitly save the item->next pointer and walk each
 167     * colision chain ourselves.  We do use next() for getting
 168     * to the next bucket.
 169     */
 170    for (void *item=first(); item; ) {
 171       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 172       Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
 173       big->insert(((hlink *)((char *)item+loffset))->key, item);
 174       if (ni) {
 175          item = (void *)((char *)ni-loffset);
 176       } else {
 177          walkptr = NULL;
 178          item = next();
 179       }
 180    }
 181    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 182    if (num_items != big->num_items) {
 183       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 184    }
 185    free(table);
 186    memcpy(this, big, sizeof(htable));  /* move everything across */
 187    free(big);
 188    Dmsg0(100, "Exit grow.\n");
 189 }
 190
 191 bool htable::insert(char *key, void *item)
 192 {
 193    hlink *hp;
 194    if (lookup(key)) {
 195       return false;                   /* already exists */
 196    }
 197    sm_check(__FILE__, __LINE__, false);
 198    ASSERT(index < buckets);
 199    Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
 200    hp = (hlink *)(((char *)item)+loffset);
 201    Dmsg4(100, "Insert hp=0x%x index=%d item=0x%x offset=%u\n", (unsigned)hp,
 202       index, (unsigned)item, loffset);
 203    hp->next = table[index];
 204    hp->hash = hash;
 205    hp->key = key;
 206    table[index] = hp;
 207    Dmsg3(100, "Insert hp->next=0x%x hp->hash=0x%x hp->key=%s\n",
 208       (unsigned)hp->next, hp->hash, hp->key);
 209
 210    if (++num_items >= max_items) {
 211       Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
 212       grow_table();
 213    }
 214    sm_check(__FILE__, __LINE__, false);
 215    Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 216    return true;
 217 }
 218
 219 void *htable::lookup(char *key)
 220 {
 221    hash_index(key);
 222    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 223 //    Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
 224       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
 225          Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
 226          return ((char *)hp)-loffset;
 227       }
 228    }
 229    return NULL;
 230 }
 231
 232 void *htable::next()
 233 {
 234    Dmsg1(100, "Enter next: walkptr=0x%x\n", (unsigned)walkptr);
 235    if (walkptr) {
 236       walkptr = (hlink *)(walkptr->next);
 237    }
 238    while (!walkptr && walk_index < buckets) {
 239       walkptr = table[walk_index++];
 240       if (walkptr) {
 241          Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 242             (unsigned)(walkptr->next), walk_index-1);
 243       }
 244    }
 245    if (walkptr) {
 246       Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
 247          (unsigned)(((char *)walkptr)-loffset), walk_index);
 248       return ((char *)walkptr)-loffset;
 249    }
 250    Dmsg0(100, "next: return NULL\n");
 251    return NULL;
 252 }
 253
 254 void *htable::first()
 255 {
 256    Dmsg0(100, "Enter first\n");
 257    walkptr = table[0];                /* get first bucket */
 258    walk_index = 1;                    /* Point to next index */
 259    while (!walkptr && walk_index < buckets) {
 260       walkptr = table[walk_index++];  /* go to next bucket */
 261       if (walkptr) {
 262          Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 263             (unsigned)(walkptr->next), walk_index-1);
 264       }
 265    }
 266    if (walkptr) {
 267       Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
 268       return ((char *)walkptr)-loffset;
 269    }
 270    Dmsg0(100, "Leave first walkptr=NULL\n");
 271    return NULL;
 272 }
 273
 274 /* Destroy the table and its contents */
 275 void htable::destroy()
 276 {
 277    void *ni;
 278    void *li = first();
 279    do {
 280       ni = next();
 281       free(li);
 282       li = ni;
 283    } while (ni);
 284
 285    free(table);
 286    table = NULL;
 287    Dmsg0(100, "Done destroy.\n");
 288 }
 289
 290
 291
 292 #ifdef TEST_PROGRAM
 293
 294 struct MYJCR {
 295    char *key;
 296    hlink link;
 297 };
 298
 299 #define NITEMS 10000
 300
 301 int main()
 302 {
 303    char mkey[30];
 304    htable *jcrtbl;
 305    MYJCR *save_jcr = NULL, *item;
 306    MYJCR *jcr = NULL;
 307    int count = 0;
 308
 309    jcrtbl = (htable *)malloc(sizeof(htable));
 310    jcrtbl->init(jcr, &jcr->link, NITEMS);
 311
 312    Dmsg1(000, "Inserting %d items\n", NITEMS);
 313    for (int i=0; i<NITEMS; i++) {
 314       sprintf(mkey, "This is htable item %d", i);
 315       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 316       Dmsg2(100, "link=0x%x jcr=0x%x\n", (unsigned)&jcr->link, (unsigned)jcr);
 317       jcr->key = bstrdup(mkey);
 318
 319       jcrtbl->insert(jcr->key, jcr);
 320       if (i == 10) {
 321          save_jcr = jcr;
 322       }
 323    }
 324    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 325       printf("Bad news: %s not found.\n", save_jcr->key);
 326    } else {
 327       printf("Item 10's key is: %s\n", item->key);
 328    }
 329
 330    jcrtbl->stats();
 331    printf("Walk the hash table:\n");
 332    foreach_htable (jcr, jcrtbl) {
 333 //    printf("htable item = %s\n", jcr->key);
 334       free(jcr->key);
 335       count++;
 336    }
 337    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 338    printf("Calling destroy\n");
 339    jcrtbl->destroy();
 340
 341    free(jcrtbl);
 342    printf("Freed jcrtbl\n");
 343
 344    sm_dump(false);
 345
 346 }
 347 #endif