* the randomness. In this program, the hash table can grow when
* it gets too full, so the table size here is a binary number. The
* hashing is provided using an idea from Tcl where the initial
- * hash code is then "randomized" using a simple calculation from
+ * hash code is "randomized" using a simple calculation from
* a random number generator that multiplies by a big number
* (I multiply by a prime number, while Tcl did not)
- * then shifts the results down and does the binary division
+ * then shifts the result down and does the binary division
* by masking. Increasing the size of the hash table is simple.
* Just create a new larger table, walk the old table and
* re-hash insert each entry into the new table.
*
- *
+ *
* Kern Sibbald, July MMIII
*
* Version $Id$
*
*/
/*
- Copyright (C) 2000-2003 Kern Sibbald and John Walker
+ Bacula® - The Network Backup Solution
+
+ Copyright (C) 2003-2006 Free Software Foundation Europe e.V.
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of
- the License, or (at your option) any later version.
+ The main author of Bacula is Kern Sibbald, with contributions from
+ many others, a complete list can be found in the file AUTHORS.
+ This program is Free Software; you can redistribute it and/or
+ modify it under the terms of version two of the GNU General Public
+ License as published by the Free Software Foundation plus additions
+ that are listed in the file LICENSE.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
- You should have received a copy of the GNU General Public
- License along with this program; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- MA 02111-1307, USA.
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
- */
+ Bacula® is a registered trademark of John Walker.
+ The licensor of Bacula is the Free Software Foundation Europe
+ (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
+ Switzerland, email:ftf@fsfeurope.org.
+*/
#include "bacula.h"
tsize >>= 1;
}
loffset = (char *)link - (char *)item;
- mask = ~((~0)<<pwr); /* 3 bits => table size = 8 */
- rshift = 30 - pwr; /* start using bits 28, 29, 30 */
- num_items = 0; /* number of entries in table */
- buckets = 1<<pwr; /* hash table size -- power of two */
- max_items = buckets * 4; /* allow average 4 entries per chain */
+ mask = ~((~0)<<pwr); /* 3 bits => table size = 8 */
+ rshift = 30 - pwr; /* start using bits 28, 29, 30 */
+ num_items = 0; /* number of entries in table */
+ buckets = 1<<pwr; /* hash table size -- power of two */
+ max_items = buckets * 4; /* allow average 4 entries per chain */
table = (hlink **)malloc(buckets * sizeof(hlink *));
memset(table, 0, buckets * sizeof(hlink *));
walkptr = NULL;
walk_index = 0;
}
-void * htable::operator new(size_t)
-{
- return malloc(sizeof(htable));
-}
-
-void htable::operator delete(void *tbl)
-{
- ((htable *)tbl)->destroy();
- free(tbl);
-}
-
uint32_t htable::size()
{
return num_items;
}
-void htable::stats()
+/*
+ * Take each hash link and walk down the chain of items
+ * that hash there counting them (i.e. the hits),
+ * then report that number.
+ * Obiously, the more hits in a chain, the more time
+ * it takes to reference them. Empty chains are not so
+ * hot either -- as it means unused or wasted space.
+ */
+#define MAX_COUNT 20
+void htable::stats()
{
- int count[10];
+ int hits[MAX_COUNT];
int max = 0;
int i, j;
hlink *p;
- printf("\n\nNumItems=%d\nBuckets=%d\n", num_items, buckets);
- for (i=0; i<10; i++) {
- count[i] = 0;
+ printf("\n\nNumItems=%d\nTotal buckets=%d\n", num_items, buckets);
+ printf("Hits/bucket: buckets\n");
+ for (i=0; i < MAX_COUNT; i++) {
+ hits[i] = 0;
}
for (i=0; i<(int)buckets; i++) {
p = table[i];
- j = 0;
+ j = 0;
while (p) {
- p = (hlink *)(p->next);
- j++;
+ p = (hlink *)(p->next);
+ j++;
}
if (j > max) {
- max = j;
+ max = j;
}
- if (j < 10) {
- count[j]++;
+ if (j < MAX_COUNT) {
+ hits[j]++;
}
}
- for (i=0; i<10; i++) {
- printf("%2d: %d\n",i, count[i]);
+ for (i=0; i < MAX_COUNT; i++) {
+ printf("%2d: %d\n",i, hits[i]);
}
- printf("max = %d\n", max);
+ printf("max hits in a bucket = %d\n", max);
}
void htable::grow_table()
{
- Dmsg1(000, "Grow called old size = %d\n", buckets);
+ Dmsg1(100, "Grow called old size = %d\n", buckets);
/* Setup a bigger table */
htable *big = (htable *)malloc(sizeof(htable));
big->loffset = loffset;
big->walk_index = 0;
/* Insert all the items in the new hash table */
Dmsg1(100, "Before copy num_items=%d\n", num_items);
- /*
+ /*
* We walk through the old smaller tree getting items,
* but since we are overwriting the colision links, we must
* explicitly save the item->next pointer and walk each
Dmsg1(100, "Grow insert: %s\n", ((hlink *)((char *)item+loffset))->key);
big->insert(((hlink *)((char *)item+loffset))->key, item);
if (ni) {
- item = (void *)((char *)ni-loffset);
+ item = (void *)((char *)ni-loffset);
} else {
- walkptr = NULL;
- item = next();
+ walkptr = NULL;
+ item = next();
}
}
Dmsg1(100, "After copy new num_items=%d\n", big->num_items);
{
hlink *hp;
if (lookup(key)) {
- return false; /* already exists */
+ return false; /* already exists */
}
- sm_check(__FILE__, __LINE__, False);
+ sm_check(__FILE__, __LINE__, false);
ASSERT(index < buckets);
Dmsg2(100, "Insert: hash=0x%x index=%d\n", (unsigned)hash, index);
hp = (hlink *)(((char *)item)+loffset);
Dmsg2(100, "num_items=%d max_items=%d\n", num_items, max_items);
grow_table();
}
- sm_check(__FILE__, __LINE__, False);
+ sm_check(__FILE__, __LINE__, false);
Dmsg3(100, "Leave insert index=%d num_items=%d key=%s\n", index, num_items, key);
return true;
}
// Dmsg2(100, "hp=0x%x key=%s\n", (long)hp, hp->key);
if (hash == hp->hash && strcmp(key, hp->key) == 0) {
Dmsg1(100, "lookup return %x\n", ((char *)hp)-loffset);
- return ((char *)hp)-loffset;
+ return ((char *)hp)-loffset;
}
}
return NULL;
walkptr = table[walk_index++];
if (walkptr) {
Dmsg3(100, "new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
- (unsigned)(walkptr->next), walk_index-1);
+ (unsigned)(walkptr->next), walk_index-1);
}
}
if (walkptr) {
- Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
- (unsigned)(((char *)walkptr)-loffset), walk_index);
+ Dmsg2(100, "next: rtn 0x%x walk_index=%d\n",
+ (unsigned)(((char *)walkptr)-loffset), walk_index);
return ((char *)walkptr)-loffset;
- }
+ }
Dmsg0(100, "next: return NULL\n");
return NULL;
}
void *htable::first()
{
Dmsg0(100, "Enter first\n");
- walkptr = table[0]; /* get first bucket */
- walk_index = 1; /* Point to next index */
+ walkptr = table[0]; /* get first bucket */
+ walk_index = 1; /* Point to next index */
while (!walkptr && walk_index < buckets) {
walkptr = table[walk_index++]; /* go to next bucket */
if (walkptr) {
Dmsg3(100, "first new walkptr=0x%x next=0x%x inx=%d\n", (unsigned)walkptr,
- (unsigned)(walkptr->next), walk_index-1);
+ (unsigned)(walkptr->next), walk_index-1);
}
}
if (walkptr) {
Dmsg1(100, "Leave first walkptr=0x%x\n", (unsigned)walkptr);
return ((char *)walkptr)-loffset;
- }
+ }
Dmsg0(100, "Leave first walkptr=NULL\n");
return NULL;
}
MYJCR *save_jcr = NULL, *item;
MYJCR *jcr = NULL;
int count = 0;
-
+
jcrtbl = (htable *)malloc(sizeof(htable));
jcrtbl->init(jcr, &jcr->link, NITEMS);
-
+
Dmsg1(000, "Inserting %d items\n", NITEMS);
for (int i=0; i<NITEMS; i++) {
sprintf(mkey, "This is htable item %d", i);
jcrtbl->insert(jcr->key, jcr);
if (i == 10) {
- save_jcr = jcr;
+ save_jcr = jcr;
}
}
if (!(item = (MYJCR *)jcrtbl->lookup(save_jcr->key))) {
jcrtbl->stats();
printf("Walk the hash table:\n");
- for (MYJCR *jcr=(MYJCR *)jcrtbl->first(); jcr; jcr=(MYJCR *)jcrtbl->next() ) {
+ foreach_htable (jcr, jcrtbl) {
// printf("htable item = %s\n", jcr->key);
free(jcr->key);
count++;
free(jcrtbl);
printf("Freed jcrtbl\n");
- sm_dump(False);
+ sm_dump(false);
}
#endif
projects / bacula / bacula / blobdiff