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

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