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