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