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 providing
   8  *    the hashing. In this program, the hash table can grow when
   9  *    it gets too full, so the table is a binary number. The
  10  *    hashing is provided using an idea from Tcl where the initial
  11  *    hash code is then "randomized" a simple calculation from
  12  *    a random number generator that multiplies by a big number
  13  *    then shifts the results down and does the binary division
  14  *    by masking.  Increasing the size of the hash table is simple
  15  *    simply create a new larger table, walk the old table and
  16  *    insert each entry into the new table.
  17  *
  18  *
  19  *   Kern Sibbald, July MMIII
  20  *
  21  *   Version $Id$
  22  *
  23  */
  24 /*
  25    Copyright (C) 2000-2003 Kern Sibbald and John Walker
  26
  27    This program is free software; you can redistribute it and/or
  28    modify it under the terms of the GNU General Public License as
  29    published by the Free Software Foundation; either version 2 of
  30    the License, or (at your option) any later version.
  31
  32    This program is distributed in the hope that it will be useful,
  33    but WITHOUT ANY WARRANTY; without even the implied warranty of
  34    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  35    General Public License for more details.
  36
  37    You should have received a copy of the GNU General Public
  38    License along with this program; if not, write to the Free
  39    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  40    MA 02111-1307, USA.
  41
  42  */
  43
  44 #include "bacula.h"
  45
  46 #include "htable.h"
  47
  48 /* ===================================================================
  49  *    htable
  50  */
  51
  52 /*
  53  * Create hash of key, stored in hash then
  54  *  create and return the pseudo random bucket index
  55  */
  56 void htable::hash_index(char *key)
  57 {
  58    hash = 0;
  59    for (char *p=key; *p; p++) {
  60       hash += (hash << 3) + (uint32_t)*p;
  61    }
  62    /* Multiply by large prime number, take top bits, mask for remainder */
  63    index = ((hash * 1103515249) >> rshift) & mask;
  64    Dmsg2(100, "Leave hash_index hash=0x%x index=%d\n", hash, index);
  65    return;
  66 }
  67
  68 htable::htable(void *item, void *link)
  69 {
  70    init(item, link);
  71 }
  72
  73 void htable::init(void *item, void *link)
  74 {
  75    loffset = (char *)link - (char *)item;
  76    mask = 7;                          /* 3 bits => table size = 8 */
  77    rshift = 27;                       /* start using bits 28, 29, 30 */
  78    num_items = 0;                     /* number of entries in table */
  79    buckets = 8;                       /* hash table size -- power of two */
  80    max_items = buckets * 4;           /* allow average 4 entries per chain */
  81    table = (hlink **)malloc(buckets * sizeof(hlink *));
  82    memset(table, 0, buckets * sizeof(hlink *));
  83    walkptr = NULL;
  84    walk_index = 0;
  85 }
  86
  87 void htable::grow_table()
  88 {
  89    Dmsg1(000, "Grow called old size = %d\n", buckets);
  90    /* Setup a bigger table */
  91    htable *big = (htable *)malloc(sizeof(htable));
  92    big->loffset = loffset;
  93    big->mask = mask<<1 | 1;
  94    big->rshift = rshift - 1;
  95    big->num_items = 0;
  96    big->buckets = buckets * 2;
  97    big->max_items = big->buckets * 4;
  98    big->table = (hlink **)malloc(big->buckets * sizeof(hlink *));
  99    memset(big->table, 0, big->buckets * sizeof(hlink *));
 100    big->walkptr = NULL;
 101    big->walk_index = 0;
 102    /* Insert all the items in the new hash table */
 103    Dmsg1(100, "Before copy num_items=%d\n", num_items);
 104    /*
 105     * We walk through the old smaller tree getting items,
 106     * but since we are overwriting the colision links, we must
 107     * explicitly save the item->next pointer and walk each
 108     * colision chain ourselves.  We do use next() for getting
 109     * to the next bucket.
 110     */
 111    for (void *item=first(); item; ) {
 112       void *ni = ((hlink *)((char *)item+loffset))->next;  /* save link overwritten by insert */
 113       Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
 114       big->insert(((hlink *)((char *)item+loffset))->key, item);
 115       if (ni) {
 116          item = (void *)((char *)ni-loffset);
 117       } else {
 118          walkptr = NULL;
 119          item = next();
 120       }
 121    }
 122    Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
 123    if (num_items != big->num_items) {
 124       Dmsg0(000, "****** Big problems num_items mismatch ******\n");
 125    }
 126    free(table);
 127    memcpy(this, big, sizeof(htable));  /* move everything across */
 128    free(big);
 129    Dmsg0(100, "Exit grow.\n");
 130 }
 131
 132 bool htable::insert(char *key, void *item)
 133 {
 134    hlink *hp;
 135    if (lookup(key)) {
 136       return false;                   /* already exists */
 137    }
 138    sm_check(__FILE__, __LINE__, False);
 139    ASSERT(index < buckets);
 140    Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
 141    hp = (hlink *)(((char *)item)+loffset);
 142    Dmsg4(100, "Insert hp=0x%x index=%d item=0x%x offset=%u\n", (unsigned)hp,
 143       index, (unsigned)item, loffset);
 144    hp->next = table[index];
 145    hp->hash = hash;
 146    hp->key = key;
 147    table[index] = hp;
 148    Dmsg3(100, "Insert hp->next=0x%x hp->hash=0x%x hp->key=%s\n",
 149       (unsigned)hp->next, hp->hash, hp->key);
 150
 151    if (++num_items >= max_items) {
 152       Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
 153       grow_table();
 154    }
 155    sm_check(__FILE__, __LINE__, False);
 156    Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
 157    return true;
 158 }
 159
 160 void *htable::lookup(char *key)
 161 {
 162    hash_index(key);
 163    for (hlink *hp=table[index]; hp; hp=(hlink *)hp->next) {
 164 //    Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
 165       if (hash == hp->hash && strcmp(key, hp->key) == 0) {
 166          Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
 167          return ((char *)hp)-loffset;
 168       }
 169    }
 170    return NULL;
 171 }
 172
 173 void *htable::next()
 174 {
 175    Dmsg1(100, "Enter next: walkptr=0x%x\n", (unsigned)walkptr);
 176    if (walkptr) {
 177       walkptr = (hlink *)(walkptr->next);
 178    }
 179    while (!walkptr && walk_index < buckets) {
 180       walkptr = table[walk_index++];
 181       if (walkptr) {
 182          Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 183             (unsigned)(walkptr->next), walk_index-1);
 184       }
 185    }
 186    if (walkptr) {
 187       Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
 188          (unsigned)(((char *)walkptr)-loffset), walk_index);
 189       return ((char *)walkptr)-loffset;
 190    }
 191    Dmsg0(100, "next: return NULL\n");
 192    return NULL;
 193 }
 194
 195 void *htable::first()
 196 {
 197    Dmsg0(100, "Enter first\n");
 198    walkptr = table[0];                /* get first bucket */
 199    walk_index = 1;                    /* Point to next index */
 200    while (!walkptr && walk_index < buckets) {
 201       walkptr = table[walk_index++];  /* go to next bucket */
 202       if (walkptr) {
 203          Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
 204             (unsigned)(walkptr->next), walk_index-1);
 205       }
 206    }
 207    if (walkptr) {
 208       Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
 209       return ((char *)walkptr)-loffset;
 210    }
 211    Dmsg0(100, "Leave first walkptr=NULL\n");
 212    return NULL;
 213 }
 214
 215 /* Destroy the table and its contents */
 216 void htable::destroy()
 217 {
 218    void *ni;
 219    void *li = first();
 220    do {
 221       ni = next();
 222       free(li);
 223       li = ni;
 224    } while (ni);
 225
 226    free(table);
 227    table = NULL;
 228    Dmsg0(100, "Done destroy.\n");
 229 }
 230
 231
 232
 233 #ifdef TEST_PROGRAM
 234
 235 struct MYJCR {
 236    char *key;
 237    hlink link;
 238 };
 239
 240 #define NITEMS 10000
 241
 242 int main()
 243 {
 244    char mkey[30];
 245    htable *jcrtbl;
 246    MYJCR *save_jcr = NULL, *item;
 247    MYJCR *jcr = NULL;
 248    int count = 0;
 249
 250    jcrtbl = (htable *)malloc(sizeof(htable));
 251    jcrtbl->init(jcr, &jcr->link);
 252
 253    Dmsg0(000, "Insert NITEMS items 0-19\n");
 254    for (int i=0; i<NITEMS; i++) {
 255       sprintf(mkey, "This is htable item %d", i);
 256       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 257       Dmsg2(100, "link=0x%x jcr=0x%x\n", (unsigned)&jcr->link, (unsigned)jcr);
 258       jcr->key = bstrdup(mkey);
 259
 260       jcrtbl->insert(jcr->key, jcr);
 261       if (i == 10) {
 262          save_jcr = jcr;
 263       }
 264    }
 265    if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
 266       printf("Bad news: %s not found.\n", save_jcr->key);
 267    } else {
 268       printf("Item 10's key is: %s\n", item->key);
 269    }
 270
 271    printf("Walk the hash table:\n");
 272    for (MYJCR *jcr=(MYJCR *)jcrtbl->first(); jcr; jcr=(MYJCR *)jcrtbl->next() ) {
 273       printf("htable item = %s\n", jcr->key);
 274       free(jcr->key);
 275       count++;
 276    }
 277    printf("Got %d items -- %s\n", count, count==NITEMS?"OK":"***ERROR***");
 278    printf("Calling destroy\n");
 279    jcrtbl->destroy();
 280
 281    free(jcrtbl);
 282    printf("Freed jcrtbl\n");
 283
 284    sm_dump(False);
 285
 286 }
 287 #endif