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    Copyright (C) 2003-2005 Kern Sibbald
  27
  28    This program is free software; you can redistribute it and/or
  29    modify it under the terms of the GNU General Public License
  30    version 2 as amended with additional clauses defined in the
  31    file LICENSE in the main source directory.
  32
  33    This program is distributed in the hope that it will be useful,
  34    but WITHOUT ANY WARRANTY; without even the implied warranty of
  35    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  36    the file LICENSE for additional details.
  37
  38  */
  39
  40 #include "bacula.h"
  41
  42 #include "htable.h"
  43
  44 /* ===================================================================
  45  *    htable
  46  */
  47
  48 /*
  49  * Create hash of key, stored in hash then
  50  *  create and return the pseudo random bucket index
  51  */
  52 void htable::hash_index(char *key)
  53 {
  54    hash = 0;
  55    for (char *p=key; *p; p++) {
  56       hash += (hash << 3) + (uint32_t)*p;
  57    }
  58    /* Multiply by large prime number, take top bits, mask for remainder */
  59    index = ((hash * 1103515249) >> rshift) & mask;
  60    Dmsg2(100, "Leave hash_index hash=0x%x index=%d\n", hash, index);
  61    return;
  62 }
  63
  64 htable::htable(void *item, void *link, int tsize)
  65 {
  66    init(item, link, tsize);
  67 }
  68
  69 void htable::init(void *item, void *link, int tsize)
  70 {
  71    int pwr;
  72    tsize >>= 2;
  73    for (pwr=0; tsize; pwr++) {
  74       tsize >>= 1;
  75    }
  76    loffset = (char *)link - (char *)item;
  77    mask = ~((~0)<<pwr);               /* 3 bits => table size = 8 */
  78    rshift = 30 - pwr;                 /* start using bits 28, 29, 30 */
  79    num_items = 0;                     /* number of entries in table */
  80    buckets = 1<<pwr;                  /* hash table size -- power of two */
  81    max_items = buckets * 4;           /* allow average 4 entries per chain */
  82    table = (hlink **)malloc(buckets * sizeof(hlink *));
  83    memset(table, 0, buckets * sizeof(hlink *));
  84    walkptr = NULL;
  85    walk_index = 0;
  86 }
  87
  88 uint32_t htable::size()
  89 {
  90    return num_items;
  91 }
  92
  93 /*
  94  * Take each hash link and walk down the chain of items
  95  *  that hash there counting them (i.e. the hits),
  96  *  then report that number.
  97  *  Obiously, the more hits in a chain, the more time
  98  *  it takes to reference them. Empty chains are not so
  99  *  hot either -- as it means unused or wasted space.
 100  */
 101 #define MAX_COUNT 20
 102 void htable::stats()
 103 {
 104    int hits[MAX_COUNT];
 105    int max = 0;
 106    int i, j;
 107    hlink *p;
 108    printf("\n\nNumItems=%d\nTotal buckets=%d\n", num_items, buckets);
 109    printf("Hits/bucket: buckets\n");
 110    for (i=0; i < MAX_COUNT; i++) {
 111       hits[i] = 0;
 112    }
 113    for (i=0; i<(int)buckets; i++) {
 114       p = table[i];
 115       j = 0;
 116       while (p) {
 117          p = (hlink *)(p->next);
 118          j++;
 119       }
 120       if (j > max) {
 121          max = j;
 122       }
 123       if (j < MAX_COUNT) {
 124          hits[j]++;
 125       }
 126    }
 127    for (i=0; i < MAX_COUNT; i++) {
 128       printf("%2d:           %d\n",i, hits[i]);
 129    }
 130    printf("max hits in a bucket = %d\n", max);
 131 }
 132
 133 void htable::grow_table()
 134 {
 135    Dmsg1(100, "Grow called old size = %d\n", buckets);
 136    /* Setup a bigger table */
 137    htable *big = (htable *)malloc(sizeof(htable));
 138    big->loffset = loffset;
 139    big->mask = mask<<1 | 1;
 140    big->rshift = rshift - 1;
 141    big->num_items = 0;
 142    big->buckets = buckets * 2;
 143    big->max_items = big->buckets * 4;
 144    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 145    memset(big->table, 0, big->buckets * sizeof(hlink *));
 146    big->walkptr = NULL;
 147    big->walk_index = 0;
 148    /* Insert all the items in the new hash table */
 149    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 150    /*
 151     * We walk through the old smaller tree getting items,
 152     * but since we are overwriting the colision links, we must
 153     * explicitly save the item->next pointer and walk each
 154     * colision chain ourselves.  We do use next() for getting
 155     * to the next bucket.
 156     */
 157    for (void *item=first(); item; ) {
 158       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 159       Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
 160       big->insert(((hlink *)((char *)item+loffset))->key, item);
 161       if (ni) {
 162          item = (void *)((char *)ni-loffset);
 163       } else {
 164          walkptr = NULL;
 165          item = next();
 166       }
 167    }
 168    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 169    if (num_items != big->num_items) {
 170       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 171    }
 172    free(table);
 173    memcpy(this, big, sizeof(htable));  /* move everything across */
 174    free(big);
 175    Dmsg0(100, "Exit grow.\n");
 176 }
 177
 178 bool htable::insert(char *key, void *item)
 179 {
 180    hlink *hp;
 181    if (lookup(key)) {
 182       return false;                   /* already exists */
 183    }
 184    sm_check(__FILE__, __LINE__, false);
 185    ASSERT(index < buckets);
 186    Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
 187    hp = (hlink *)(((char *)item)+loffset);
 188    Dmsg4(100, "Insert hp=0x%x index=%d item=0x%x offset=%u\n", (unsigned)hp,
 189       index, (unsigned)item, loffset);
 190    hp->next = table[index];
 191    hp->hash = hash;
 192    hp->key = key;
 193    table[index] = hp;
 194    Dmsg3(100, "Insert hp->next=0x%x hp->hash=0x%x hp->key=%s\n",
 195       (unsigned)hp->next, hp->hash, hp->key);
 196
 197    if (++num_items >= max_items) {
 198       Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
 199       grow_table();
 200    }
 201    sm_check(__FILE__, __LINE__, false);
 202    Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 203    return true;
 204 }
 205
 206 void *htable::lookup(char *key)
 207 {
 208    hash_index(key);
 209    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 210 //    Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
 211       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
 212          Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
 213          return ((char *)hp)-loffset;
 214       }
 215    }
 216    return NULL;
 217 }
 218
 219 void *htable::next()
 220 {
 221    Dmsg1(100, "Enter next: walkptr=0x%x\n", (unsigned)walkptr);
 222    if (walkptr) {
 223       walkptr = (hlink *)(walkptr->next);
 224    }
 225    while (!walkptr && walk_index < buckets) {
 226       walkptr = table[walk_index++];
 227       if (walkptr) {
 228          Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 229             (unsigned)(walkptr->next), walk_index-1);
 230       }
 231    }
 232    if (walkptr) {
 233       Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
 234          (unsigned)(((char *)walkptr)-loffset), walk_index);
 235       return ((char *)walkptr)-loffset;
 236    }
 237    Dmsg0(100, "next: return NULL\n");
 238    return NULL;
 239 }
 240
 241 void *htable::first()
 242 {
 243    Dmsg0(100, "Enter first\n");
 244    walkptr = table[0];                /* get first bucket */
 245    walk_index = 1;                    /* Point to next index */
 246    while (!walkptr && walk_index < buckets) {
 247       walkptr = table[walk_index++];  /* go to next bucket */
 248       if (walkptr) {
 249          Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 250             (unsigned)(walkptr->next), walk_index-1);
 251       }
 252    }
 253    if (walkptr) {
 254       Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
 255       return ((char *)walkptr)-loffset;
 256    }
 257    Dmsg0(100, "Leave first walkptr=NULL\n");
 258    return NULL;
 259 }
 260
 261 /* Destroy the table and its contents */
 262 void htable::destroy()
 263 {
 264    void *ni;
 265    void *li = first();
 266    do {
 267       ni = next();
 268       free(li);
 269       li = ni;
 270    } while (ni);
 271
 272    free(table);
 273    table = NULL;
 274    Dmsg0(100, "Done destroy.\n");
 275 }
 276
 277
 278
 279 #ifdef TEST_PROGRAM
 280
 281 struct MYJCR {
 282    char *key;
 283    hlink link;
 284 };
 285
 286 #define NITEMS 10000
 287
 288 int main()
 289 {
 290    char mkey[30];
 291    htable *jcrtbl;
 292    MYJCR *save_jcr = NULL, *item;
 293    MYJCR *jcr = NULL;
 294    int count = 0;
 295
 296    jcrtbl = (htable *)malloc(sizeof(htable));
 297    jcrtbl->init(jcr, &jcr->link, NITEMS);
 298
 299    Dmsg1(000, "Inserting %d items\n", NITEMS);
 300    for (int i=0; i<NITEMS; i++) {
 301       sprintf(mkey, "This is htable item %d", i);
 302       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 303       Dmsg2(100, "link=0x%x jcr=0x%x\n", (unsigned)&jcr->link, (unsigned)jcr);
 304       jcr->key = bstrdup(mkey);
 305
 306       jcrtbl->insert(jcr->key, jcr);
 307       if (i == 10) {
 308          save_jcr = jcr;
 309       }
 310    }
 311    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 312       printf("Bad news: %s not found.\n", save_jcr->key);
 313    } else {
 314       printf("Item 10's key is: %s\n", item->key);
 315    }
 316
 317    jcrtbl->stats();
 318    printf("Walk the hash table:\n");
 319    foreach_htable (jcr, jcrtbl) {
 320 //    printf("htable item = %s\n", jcr->key);
 321       free(jcr->key);
 322       count++;
 323    }
 324    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 325    printf("Calling destroy\n");
 326    jcrtbl->destroy();
 327
 328    free(jcrtbl);
 329    printf("Freed jcrtbl\n");
 330
 331    sm_dump(false);
 332
 333 }
 334 #endif