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 #ifdef xxx
  94 void * htable::operator new(size_t)
  95 {
  96    return malloc(sizeof(htable));
  97 }
  98
  99 void htable::operator delete(void *tbl)
 100 {
 101    ((htable *)tbl)->destroy();
 102    free(tbl);
 103 }
 104 #endif
 105
 106 uint32_t htable::size()
 107 {
 108    return num_items;
 109 }
 110
 111 void htable::stats()
 112 {
 113    int count[10];
 114    int max = 0;
 115    int i, j;
 116    hlink *p;
 117    printf("\n\nNumItems=%d\nBuckets=%d\n", num_items, buckets);
 118    for (i=0; i<10; i++) {
 119       count[i] = 0;
 120    }
 121    for (i=0; i<(int)buckets; i++) {
 122       p = table[i];
 123       j = 0;
 124       while (p) {
 125          p = (hlink *)(p->next);
 126          j++;
 127       }
 128       if (j > max) {
 129          max = j;
 130       }
 131       if (j < 10) {
 132          count[j]++;
 133       }
 134    }
 135    for (i=0; i<10; i++) {
 136       printf("%2d: %d\n",i, count[i]);
 137    }
 138    printf("max = %d\n", max);
 139 }
 140
 141 void htable::grow_table()
 142 {
 143    Dmsg1(100, "Grow called old size = %d\n", buckets);
 144    /* Setup a bigger table */
 145    htable *big = (htable *)malloc(sizeof(htable));
 146    big->loffset = loffset;
 147    big->mask = mask<<1 | 1;
 148    big->rshift = rshift - 1;
 149    big->num_items = 0;
 150    big->buckets = buckets * 2;
 151    big->max_items = big->buckets * 4;
 152    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
 153    memset(big->table, 0, big->buckets * sizeof(hlink *));
 154    big->walkptr = NULL;
 155    big->walk_index = 0;
 156    /* Insert all the items in the new hash table */
 157    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 158    /*
 159     * We walk through the old smaller tree getting items,
 160     * but since we are overwriting the colision links, we must
 161     * explicitly save the item->next pointer and walk each
 162     * colision chain ourselves.  We do use next() for getting
 163     * to the next bucket.
 164     */
 165    for (void *item=first(); item; ) {
 166       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 167       Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
 168       big->insert(((hlink *)((char *)item+loffset))->key, item);
 169       if (ni) {
 170          item = (void *)((char *)ni-loffset);
 171       } else {
 172          walkptr = NULL;
 173          item = next();
 174       }
 175    }
 176    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 177    if (num_items != big->num_items) {
 178       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 179    }
 180    free(table);
 181    memcpy(this, big, sizeof(htable));  /* move everything across */
 182    free(big);
 183    Dmsg0(100, "Exit grow.\n");
 184 }
 185
 186 bool htable::insert(char *key, void *item)
 187 {
 188    hlink *hp;
 189    if (lookup(key)) {
 190       return false;                   /* already exists */
 191    }
 192    sm_check(__FILE__, __LINE__, false);
 193    ASSERT(index < buckets);
 194    Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
 195    hp = (hlink *)(((char *)item)+loffset);
 196    Dmsg4(100, "Insert hp=0x%x index=%d item=0x%x offset=%u\n", (unsigned)hp,
 197       index, (unsigned)item, loffset);
 198    hp->next = table[index];
 199    hp->hash = hash;
 200    hp->key = key;
 201    table[index] = hp;
 202    Dmsg3(100, "Insert hp->next=0x%x hp->hash=0x%x hp->key=%s\n",
 203       (unsigned)hp->next, hp->hash, hp->key);
 204
 205    if (++num_items >= max_items) {
 206       Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
 207       grow_table();
 208    }
 209    sm_check(__FILE__, __LINE__, false);
 210    Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 211    return true;
 212 }
 213
 214 void *htable::lookup(char *key)
 215 {
 216    hash_index(key);
 217    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 218 //    Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
 219       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
 220          Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
 221          return ((char *)hp)-loffset;
 222       }
 223    }
 224    return NULL;
 225 }
 226
 227 void *htable::next()
 228 {
 229    Dmsg1(100, "Enter next: walkptr=0x%x\n", (unsigned)walkptr);
 230    if (walkptr) {
 231       walkptr = (hlink *)(walkptr->next);
 232    }
 233    while (!walkptr && walk_index < buckets) {
 234       walkptr = table[walk_index++];
 235       if (walkptr) {
 236          Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 237             (unsigned)(walkptr->next), walk_index-1);
 238       }
 239    }
 240    if (walkptr) {
 241       Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
 242          (unsigned)(((char *)walkptr)-loffset), walk_index);
 243       return ((char *)walkptr)-loffset;
 244    }
 245    Dmsg0(100, "next: return NULL\n");
 246    return NULL;
 247 }
 248
 249 void *htable::first()
 250 {
 251    Dmsg0(100, "Enter first\n");
 252    walkptr = table[0];                /* get first bucket */
 253    walk_index = 1;                    /* Point to next index */
 254    while (!walkptr && walk_index < buckets) {
 255       walkptr = table[walk_index++];  /* go to next bucket */
 256       if (walkptr) {
 257          Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 258             (unsigned)(walkptr->next), walk_index-1);
 259       }
 260    }
 261    if (walkptr) {
 262       Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
 263       return ((char *)walkptr)-loffset;
 264    }
 265    Dmsg0(100, "Leave first walkptr=NULL\n");
 266    return NULL;
 267 }
 268
 269 /* Destroy the table and its contents */
 270 void htable::destroy()
 271 {
 272    void *ni;
 273    void *li = first();
 274    do {
 275       ni = next();
 276       free(li);
 277       li = ni;
 278    } while (ni);
 279
 280    free(table);
 281    table = NULL;
 282    Dmsg0(100, "Done destroy.\n");
 283 }
 284
 285
 286
 287 #ifdef TEST_PROGRAM
 288
 289 struct MYJCR {
 290    char *key;
 291    hlink link;
 292 };
 293
 294 #define NITEMS 10000
 295
 296 int main()
 297 {
 298    char mkey[30];
 299    htable *jcrtbl;
 300    MYJCR *save_jcr = NULL, *item;
 301    MYJCR *jcr = NULL;
 302    int count = 0;
 303
 304    jcrtbl = (htable *)malloc(sizeof(htable));
 305    jcrtbl->init(jcr, &jcr->link, NITEMS);
 306
 307    Dmsg1(000, "Inserting %d items\n", NITEMS);
 308    for (int i=0; i<NITEMS; i++) {
 309       sprintf(mkey, "This is htable item %d", i);
 310       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 311       Dmsg2(100, "link=0x%x jcr=0x%x\n", (unsigned)&jcr->link, (unsigned)jcr);
 312       jcr->key = bstrdup(mkey);
 313
 314       jcrtbl->insert(jcr->key, jcr);
 315       if (i == 10) {
 316          save_jcr = jcr;
 317       }
 318    }
 319    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 320       printf("Bad news: %s not found.\n", save_jcr->key);
 321    } else {
 322       printf("Item 10's key is: %s\n", item->key);
 323    }
 324
 325    jcrtbl->stats();
 326    printf("Walk the hash table:\n");
 327    foreach_htable (jcr, jcrtbl) {
 328 //    printf("htable item = %s\n", jcr->key);
 329       free(jcr->key);
 330       count++;
 331    }
 332    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 333    printf("Calling destroy\n");
 334    jcrtbl->destroy();
 335
 336    free(jcrtbl);
 337    printf("Freed jcrtbl\n");
 338
 339    sm_dump(false);
 340
 341 }
 342 #endif