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 /* This routine frees the whole tree */
  80 void htable::hash_free()
  81 {
  82    struct h_mem *hmem, *rel;
  83
  84    for (hmem=mem; hmem; ) {
  85       rel = hmem;
  86       hmem = hmem->next;
  87       free(rel);
  88    }
  89 }
  90
  91 #endif
  92
  93 char *htable::hash_malloc(int size)
  94 {
  95 #ifdef BIG_MALLOC
  96    char *buf;
  97    int asize = BALIGN(size);
  98
  99    if (mem->rem < asize) {
 100       uint32_t mb_size;
 101       if (total_size >= 1000000) {
 102          mb_size = 1000000;
 103       } else {
 104          mb_size = 100000;
 105       }
 106       malloc_buf(mb_size);
 107    }
 108    mem->rem -= asize;
 109    buf = mem->mem;
 110    mem->mem += asize;
 111    return buf;
 112 #else
 113    total_size += size;
 114    blocks++;
 115    return (char *)malloc(size);
 116 #endif
 117 }
 118
 119
 120
 121
 122 /*
 123  * Create hash of key, stored in hash then
 124  *  create and return the pseudo random bucket index
 125  */
 126 void htable::hash_index(char *key)
 127 {
 128    hash = 0;
 129    for (char *p=key; *p; p++) {
 130       hash += (hash << 3) + (uint32_t)*p;
 131    }
 132    /* Multiply by large prime number, take top bits, mask for remainder */
 133    index = ((hash * 1103515249) >> rshift) & mask;
 134    Dmsg2(100, "Leave hash_index hash=0x%x index=%d\n", hash, index);
 135 }
 136
 137 /*
 138  * tsize is the estimated number of entries in the hash table
 139  */
 140 htable::htable(void *item, void *link, int tsize)
 141 {
 142    init(item, link, tsize);
 143 }
 144
 145 void htable::init(void *item, void *link, int tsize)
 146 {
 147    int pwr;
 148
 149    if (tsize < 31) {
 150       tsize = 31;
 151    }
 152    tsize >>= 2;
 153    for (pwr=0; tsize; pwr++) {
 154       tsize >>= 1;
 155    }
 156    loffset = (char *)link - (char *)item;
 157    mask = ~((~0)<<pwr);               /* 3 bits => table size = 8 */
 158    rshift = 30 - pwr;                 /* start using bits 28, 29, 30 */
 159    num_items = 0;                     /* number of entries in table */
 160    buckets = 1<<pwr;                  /* hash table size -- power of two */
 161    max_items = buckets * 4;           /* allow average 4 entries per chain */
 162    table = (hlink **)malloc(buckets * sizeof(hlink *));
 163    memset(table, 0, buckets * sizeof(hlink *));
 164    walkptr = NULL;
 165    walk_index = 0;
 166    total_size = 0;
 167    blocks = 0;
 168 #ifdef BIG_MALLOC
 169    mem = NULL;
 170    malloc_buf(1000000);   /* ***FIXME*** need variable or some estimate */
 171 #endif
 172 }
 173
 174 uint32_t htable::size()
 175 {
 176    return num_items;
 177 }
 178
 179 /*
 180  * Take each hash link and walk down the chain of items
 181  *  that hash there counting them (i.e. the hits),
 182  *  then report that number.
 183  * Obiously, the more hits in a chain, the more time
 184  *  it takes to reference them. Empty chains are not so
 185  *  hot either -- as it means unused or wasted space.
 186  */
 187 #define MAX_COUNT 20
 188 void htable::stats()
 189 {
 190    int hits[MAX_COUNT];
 191    int max = 0;
 192    int i, j;
 193    hlink *p;
 194    printf("\n\nNumItems=%d\nTotal buckets=%d\n", num_items, buckets);
 195    printf("Hits/bucket: buckets\n");
 196    for (i=0; i < MAX_COUNT; i++) {
 197       hits[i] = 0;
 198    }
 199    for (i=0; i<(int)buckets; i++) {
 200       p = table[i];
 201       j = 0;
 202       while (p) {
 203          p = (hlink *)(p->next);
 204          j++;
 205       }
 206       if (j > max) {
 207          max = j;
 208       }
 209       if (j < MAX_COUNT) {
 210          hits[j]++;
 211       }
 212    }
 213    for (i=0; i < MAX_COUNT; i++) {
 214       printf("%2d:           %d\n",i, hits[i]);
 215    }
 216    printf("buckets=%d num_items=%d max_items=%d\n", buckets, num_items, max_items);
 217    printf("max hits in a bucket = %d\n", max);
 218 #ifdef BIG_MALLOC
 219    printf("total bytes malloced = %d\n", total_size);
 220    printf("total blocks malloced = %d\n", blocks);
 221 #endif
 222 }
 223
 224 void htable::grow_table()
 225 {
 226    Dmsg1(100, "Grow called old size = %d\n", buckets);
 227    /* Setup a bigger table */
 228    htable *big = (htable *)malloc(sizeof(htable));
 229    big->loffset = loffset;
 230    big->mask = mask<<1 | 1;
 231    big->rshift = rshift - 1;
 232    big->num_items = 0;
 233    big->buckets = buckets * 2;
 234    big->max_items = big->buckets * 4;
 235    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 236    memset(big->table, 0, big->buckets * sizeof(hlink *));
 237    big->walkptr = NULL;
 238    big->walk_index = 0;
 239    /* Insert all the items in the new hash table */
 240    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 241    /*
 242     * We walk through the old smaller tree getting items,
 243     * but since we are overwriting the colision links, we must
 244     * explicitly save the item->next pointer and walk each
 245     * colision chain ourselves.  We do use next() for getting
 246     * to the next bucket.
 247     */
 248    for (void *item=first(); item; ) {
 249       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 250       Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
 251       big->insert(((hlink *)((char *)item+loffset))->key, item);
 252       if (ni) {
 253          item = (void *)((char *)ni-loffset);
 254       } else {
 255          walkptr = NULL;
 256          item = next();
 257       }
 258    }
 259    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 260    if (num_items != big->num_items) {
 261       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 262    }
 263    free(table);
 264    memcpy(this, big, sizeof(htable));  /* move everything across */
 265    free(big);
 266    Dmsg0(100, "Exit grow.\n");
 267 }
 268
 269 bool htable::insert(char *key, void *item)
 270 {
 271    hlink *hp;
 272    if (lookup(key)) {
 273       return false;                   /* already exists */
 274    }
 275    ASSERT(index < buckets);
 276    Dmsg2(100, "Insert: hash=%p index=%d\n", hash, index);
 277    hp = (hlink *)(((char *)item)+loffset);
 278    Dmsg4(100, "Insert hp=%p index=%d item=%p offset=%u\n", hp,
 279       index, item, loffset);
 280    hp->next = table[index];
 281    hp->hash = hash;
 282    hp->key = key;
 283    table[index] = hp;
 284    Dmsg3(100, "Insert hp->next=%p hp->hash=0x%x hp->key=%s\n",
 285       hp->next, hp->hash, hp->key);
 286
 287    if (++num_items >= max_items) {
 288       Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
 289       grow_table();
 290    }
 291    Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 292    return true;
 293 }
 294
 295 void *htable::lookup(char *key)
 296 {
 297    hash_index(key);
 298    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 299 //    Dmsg2(100, "hp=%p key=%s\n", hp, hp->key);
 300       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
 301          Dmsg1(100, "lookup return %p\n", ((char *)hp)-loffset);
 302          return ((char *)hp)-loffset;
 303       }
 304    }
 305    return NULL;
 306 }
 307
 308 void *htable::next()
 309 {
 310    Dmsg1(100, "Enter next: walkptr=%p\n", walkptr);
 311    if (walkptr) {
 312       walkptr = (hlink *)(walkptr->next);
 313    }
 314    while (!walkptr && walk_index < buckets) {
 315       walkptr = table[walk_index++];
 316       if (walkptr) {
 317          Dmsg3(100, "new walkptr=%p next=%p inx=%d\n", walkptr,
 318             walkptr->next, walk_index-1);
 319       }
 320    }
 321    if (walkptr) {
 322       Dmsg2(100, "next: rtn %p walk_index=%d\n",
 323          ((char *)walkptr)-loffset, walk_index);
 324       return ((char *)walkptr)-loffset;
 325    }
 326    Dmsg0(100, "next: return NULL\n");
 327    return NULL;
 328 }
 329
 330 void *htable::first()
 331 {
 332    Dmsg0(100, "Enter first\n");
 333    walkptr = table[0];                /* get first bucket */
 334    walk_index = 1;                    /* Point to next index */
 335    while (!walkptr && walk_index < buckets) {
 336       walkptr = table[walk_index++];  /* go to next bucket */
 337       if (walkptr) {
 338          Dmsg3(100, "first new walkptr=%p next=%p inx=%d\n", walkptr,
 339             walkptr->next, walk_index-1);
 340       }
 341    }
 342    if (walkptr) {
 343       Dmsg1(100, "Leave first walkptr=%p\n", walkptr);
 344       return ((char *)walkptr)-loffset;
 345    }
 346    Dmsg0(100, "Leave first walkptr=NULL\n");
 347    return NULL;
 348 }
 349
 350 /* Destroy the table and its contents */
 351 void htable::destroy()
 352 {
 353 #ifdef BIG_MALLOC
 354    hash_free();
 355 #else
 356    void *ni;
 357    void *li = first();
 358
 359    while (li) {
 360       ni = next();
 361       free(li);
 362       li=ni;
 363    }
 364 #endif
 365
 366    free(table);
 367    table = NULL;
 368    Dmsg0(100, "Done destroy.\n");
 369 }
 370
 371
 372
 373 #ifdef TEST_PROGRAM
 374
 375 struct MYJCR {
 376    char *key;
 377    hlink link;
 378 };
 379
 380 #define NITEMS 5000000
 381
 382 int main()
 383 {
 384    char mkey[30];
 385    htable *jcrtbl;
 386    MYJCR *save_jcr = NULL, *item;
 387    MYJCR *jcr = NULL;
 388    int count = 0;
 389
 390    jcrtbl = (htable *)malloc(sizeof(htable));
 391    jcrtbl->init(jcr, &jcr->link, NITEMS);
 392
 393    Dmsg1(000, "Inserting %d items\n", NITEMS);
 394    for (int i=0; i<NITEMS; i++) {
 395       int len;
 396       len = sprintf(mkey, "This is htable item %d", i) + 1;
 397
 398       jcr = (MYJCR *)jcrtbl->hash_malloc(sizeof(MYJCR));
 399       jcr->key = (char *)jcrtbl->hash_malloc(len);
 400       memcpy(jcr->key, mkey, len);
 401       Dmsg2(100, "link=%p jcr=%p\n", jcr->link, jcr);
 402
 403       jcrtbl->insert(jcr->key, jcr);
 404       if (i == 10) {
 405          save_jcr = jcr;
 406       }
 407    }
 408    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 409       printf("Bad news: %s not found.\n", save_jcr->key);
 410    } else {
 411       printf("Item 10's key is: %s\n", item->key);
 412    }
 413
 414    jcrtbl->stats();
 415    printf("Walk the hash table:\n");
 416    foreach_htable (jcr, jcrtbl) {
 417 //    printf("htable item = %s\n", jcr->key);
 418 #ifndef BIG_MALLOC
 419       free(jcr->key);
 420 #endif
 421       count++;
 422    }
 423    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 424    printf("Calling destroy\n");
 425    jcrtbl->destroy();
 426
 427    free(jcrtbl);
 428    printf("Freed jcrtbl\n");
 429
 430    sm_dump(false);
 431
 432 }
 433 #endif