aboutsummaryrefslogtreecommitdiffstats
path: root/libibex/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'libibex/hash.c')
-rw-r--r--libibex/hash.c701
1 files changed, 701 insertions, 0 deletions
diff --git a/libibex/hash.c b/libibex/hash.c
new file mode 100644
index 0000000000..02e01a1ae0
--- /dev/null
+++ b/libibex/hash.c
@@ -0,0 +1,701 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*-
+ *
+ * Copyright (C) 2000 Helix Code, Inc.
+ *
+ * Authors: Michael Zucchi <notzed@helixcode.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public License
+ * as published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with the Gnome Library; see the file COPYING.LIB. If not,
+ * write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/* hash based index mechanism */
+
+#include <stdio.h>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+
+#include "block.h"
+#include "index.h"
+
+#define d(x)
+
+#define HASH_SIZE (1024)
+#define KEY_THRESHOLD (sizeof(struct _hashkey) + 4) /* minimum number of free bytes we worry about
+ maintaining free blocks for */
+#define ARRAY_LEN(a) (sizeof(a)/sizeof(a[0]))
+
+typedef guint32 hashid_t;
+
+static struct _IBEXIndex *hash_create(struct _memcache *bc, int size);
+static struct _IBEXIndex *hash_open(struct _memcache *bc, blockid_t root);
+static int hash_sync(struct _IBEXIndex *index);
+static int hash_close(struct _IBEXIndex *index);
+
+static hashid_t hash_find(struct _IBEXIndex *index, const char *key, int keylen);
+static void hash_remove(struct _IBEXIndex *index, const char *key, int keylen);
+static hashid_t hash_insert(struct _IBEXIndex *index, const char *key, int keylen);
+static char *hash_get_key(struct _IBEXIndex *index, hashid_t hashbucket, int *len);
+static void hash_set_data_block(struct _IBEXIndex *index, hashid_t keyid, blockid_t blockid, blockid_t tail);
+static blockid_t hash_get_data_block(struct _IBEXIndex *index, hashid_t keyid, blockid_t *tail);
+
+struct _IBEXIndexClass ibex_hash_class = {
+ hash_create, hash_open,
+ hash_sync, hash_close,
+ hash_find,
+ hash_remove,
+ hash_insert,
+ hash_get_key,
+ hash_set_data_block,
+ hash_get_data_block,
+};
+
+/* the reason we have the tail here is that otherwise we need to
+ have a 32 bit blockid for the root node; which would make this
+ structure the same size anyway, with about 24 wasted bits */
+struct _hashkey {
+ blockid_t next; /* next in hash chain */
+ blockid_t tail;
+ unsigned int root:32-BLOCK_BITS;
+ unsigned int keyoffset:BLOCK_BITS;
+};
+
+struct _hashblock {
+ /*blockid_t next;*/ /* all key blocks linked together? */
+ guint32 used; /* elements used */
+ union {
+ struct _hashkey keys[(BLOCK_SIZE-4)/sizeof(struct _hashkey)];
+ char keydata[BLOCK_SIZE-4];
+ } hashblock_u;
+};
+#define hb_keys hashblock_u.keys
+#define hb_keydata hashblock_u.keydata
+
+/* root block for a hash index */
+struct _hashroot {
+ hashid_t free; /* free list */
+ guint32 size; /* how big the hash table is */
+ hashid_t table[(BLOCK_SIZE-8)/sizeof(hashid_t)]; /* pointers to blocks of pointers */
+};
+
+struct _hashtableblock {
+ hashid_t buckets[BLOCK_SIZE/sizeof(hashid_t)];
+};
+
+/* map a hash index to a block index */
+#define HASH_INDEX(b) ((b) & (BLOCK_SIZE-1))
+/* map a hash index to a block number */
+#define HASH_BLOCK(b) ((b) & ~(BLOCK_SIZE-1))
+/* map a block + index to a hash key */
+#define HASH_KEY(b, i) (((b) & ~(BLOCK_SIZE-1)) | ((i) & (BLOCK_SIZE-1)))
+
+/* taken from tdb/gdbm */
+static unsigned int hash_key(const unsigned char *key, int keylen)
+{
+ char *newkey;
+ newkey = alloca(keylen+1);
+ memcpy(newkey, key, keylen);
+ newkey[keylen]=0;
+ return g_str_hash(newkey);
+#if 0
+ unsigned int value; /* Used to compute the hash value. */
+ unsigned int i; /* Used to cycle through random values. */
+
+ /* Set the initial value from the key size. */
+ value = 0x238F13AF * keylen;
+ for (i=0; i < keylen; i++) {
+ value = (value + (key[i] << (i*5 % 24)));
+ }
+
+ value = (1103515243 * value + 12345);
+
+ return value;
+#endif
+}
+
+/* create a new hash table, return a pointer to its root block */
+static struct _IBEXIndex *
+hash_create(struct _memcache *bc, int size)
+{
+ blockid_t root, block;
+ struct _hashroot *hashroot;
+ int i;
+ struct _hashtableblock *table;
+ struct _IBEXIndex *index;
+
+ g_assert(size<=10240);
+
+ d(printf("initialising hash table, size = %d\n", size));
+
+ index = g_malloc0(sizeof(*index));
+ index->blocks = bc;
+ index->klass = &ibex_hash_class;
+ root = ibex_block_get(bc);
+ index->root = root;
+ d(printf(" root = %d\n", root));
+ hashroot = (struct _hashroot *)ibex_block_read(bc, root);
+ hashroot->free = 0;
+ hashroot->size = size;
+ ibex_block_dirty((struct _block *)hashroot);
+ for (i=0;i<size/(BLOCK_SIZE/sizeof(blockid_t));i++) {
+ d(printf("initialising hash table index block %d\n", i));
+ block = hashroot->table[i] = ibex_block_get(bc);
+ table = (struct _hashtableblock *)ibex_block_read(bc, block);
+ memset(table, 0, sizeof(table));
+ ibex_block_dirty((struct _block *)table);
+ }
+
+ return index;
+}
+
+static struct _IBEXIndex *
+hash_open(struct _memcache *bc, blockid_t root)
+{
+ struct _IBEXIndex *index;
+
+ /* FIXME: check a 'magic', and the root for validity */
+
+ index = g_malloc0(sizeof(*index));
+ index->blocks = bc;
+ index->root = root;
+ index->klass = &ibex_hash_class;
+
+ return index;
+}
+
+
+static int hash_sync(struct _IBEXIndex *index)
+{
+ /* nop, index always synced on disk (at least, to blocks) */
+ return 0;
+}
+
+static int hash_close(struct _IBEXIndex *index)
+{
+ g_free(index);
+ return 0;
+}
+
+/* convert a hashbucket id into a name */
+static char *
+hash_get_key(struct _IBEXIndex *index, hashid_t hashbucket, int *len)
+{
+ struct _hashblock *bucket;
+ int ind;
+ char *ret, *start, *end;
+
+ if (hashbucket == 0) {
+ if (len)
+ *len = 0;
+ return g_strdup("");
+ }
+
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashbucket));
+ ind = HASH_INDEX(hashbucket);
+
+ g_assert(ind < bucket->used);
+
+ start = &bucket->hb_keydata[bucket->hb_keys[ind].keyoffset];
+ if (ind == 0) {
+ end = &bucket->hb_keydata[sizeof(bucket->hb_keydata)/sizeof(bucket->hb_keydata[0])];
+ } else {
+ end = &bucket->hb_keydata[bucket->hb_keys[ind-1].keyoffset];
+ }
+
+ ret = g_malloc(end-start+1);
+ memcpy(ret, start, end-start);
+ ret[end-start]=0;
+ if (len)
+ *len = end-start;
+ return ret;
+}
+
+/* sigh, this is fnugly code ... */
+static hashid_t
+hash_find(struct _IBEXIndex *index, const char *key, int keylen)
+{
+ struct _hashroot *hashroot;
+ guint32 hash;
+ int hashentry;
+ blockid_t hashtable;
+ hashid_t hashbucket;
+ struct _hashtableblock *table;
+
+ g_assert(index != 0);
+ g_assert(index->root != 0);
+
+ d(printf("finding hash %.*s\n", keylen, key));
+
+ hashroot = (struct _hashroot *)ibex_block_read(index->blocks, index->root);
+
+ /* find the table containing this entry */
+ hash = hash_key(key, keylen) % hashroot->size;
+ hashtable = hashroot->table[hash / (BLOCK_SIZE/sizeof(blockid_t))];
+ g_assert(hashtable != 0);
+ table = (struct _hashtableblock *)ibex_block_read(index->blocks, hashtable);
+ hashentry = hash % (BLOCK_SIZE/sizeof(blockid_t));
+ /* and its bucket */
+ hashbucket = table->buckets[hashentry];
+
+ /* go down the bucket chain, reading each entry till we are done ... */
+ while (hashbucket != 0) {
+ struct _hashblock *bucket;
+ char *start, *end;
+ int ind;
+
+ d(printf(" checking bucket %d\n", hashbucket));
+
+ /* get the real bucket id from the hashbucket id */
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashbucket));
+ /* and get the key number within the block */
+ ind = HASH_INDEX(hashbucket);
+
+ g_assert(ind < bucket->used);
+
+ start = &bucket->hb_keydata[bucket->hb_keys[ind].keyoffset];
+ if (ind == 0) {
+ end = &bucket->hb_keydata[sizeof(bucket->hb_keydata)/sizeof(bucket->hb_keydata[0])];
+ } else {
+ end = &bucket->hb_keydata[bucket->hb_keys[ind-1].keyoffset];
+ }
+ if ( (end-start) == keylen
+ && memcmp(start, key, keylen) == 0) {
+ return hashbucket;
+ }
+ hashbucket = bucket->hb_keys[ind].next;
+ }
+ return 0;
+}
+
+/* compresses the bucket 'bucket', removing data
+ at index 'index' */
+static void
+hash_compress(struct _hashblock *bucket, int index)
+{
+ int i;
+ char *start, *end, *newstart;
+
+ /* get start/end of area to zap */
+ start = &bucket->hb_keydata[bucket->hb_keys[index].keyoffset];
+ if (index == 0) {
+ end = &bucket->hb_keydata[sizeof(bucket->hb_keydata)/sizeof(bucket->hb_keydata[0])];
+ } else {
+ end = &bucket->hb_keydata[bucket->hb_keys[index-1].keyoffset];
+ }
+
+ if (start == end)
+ return;
+
+ /* fixup data */
+ newstart = &bucket->hb_keydata[bucket->hb_keys[bucket->used-1].keyoffset];
+ memmove(newstart+(end-start), newstart, start-newstart);
+
+ /* fixup key pointers */
+ for (i=index;i<bucket->used;i++) {
+ bucket->hb_keys[i].keyoffset += (end-start);
+ }
+ ibex_block_dirty((struct _block *)bucket);
+}
+
+/* make room 'len' for the key 'index' */
+/* assumes key 'index' is already empty (0 length) */
+static void
+hash_expand(struct _hashblock *bucket, int index, int len)
+{
+ int i;
+ char *end, *newstart;
+
+ /* get start/end of area to zap */
+ if (index == 0) {
+ end = &bucket->hb_keydata[sizeof(bucket->hb_keydata)/sizeof(bucket->hb_keydata[0])];
+ } else {
+ end = &bucket->hb_keydata[bucket->hb_keys[index-1].keyoffset];
+ }
+
+ /* fixup data */
+ newstart = &bucket->hb_keydata[bucket->hb_keys[bucket->used-1].keyoffset];
+ memmove(newstart-len, newstart, end-newstart);
+
+ /* fixup key pointers */
+ for (i=index;i<bucket->used;i++) {
+ bucket->hb_keys[i].keyoffset -= len;
+ }
+ ibex_block_dirty((struct _block *)bucket);
+}
+
+static void
+hash_remove(struct _IBEXIndex *index, const char *key, int keylen)
+{
+ struct _hashroot *hashroot;
+ guint32 hash;
+ int hashentry;
+ blockid_t hashtable;
+ hashid_t hashbucket, hashprev;
+ struct _hashtableblock *table;
+
+ g_assert(index != 0);
+ g_assert(index->root != 0);
+
+ d(printf("removing hash %.*s\n", keylen, key));
+
+ hashroot = (struct _hashroot *)ibex_block_read(index->blocks, index->root);
+
+ /* find the table containing this entry */
+ hash = hash_key(key, keylen) % hashroot->size;
+ hashtable = hashroot->table[hash / (BLOCK_SIZE/sizeof(blockid_t))];
+ table = (struct _hashtableblock *)ibex_block_read(index->blocks, hashtable);
+ hashentry = hash % (BLOCK_SIZE/sizeof(blockid_t));
+ /* and its bucket */
+ hashbucket = table->buckets[hashentry];
+
+ /* go down the bucket chain, reading each entry till we are done ... */
+ hashprev = 0;
+ while (hashbucket != 0) {
+ struct _hashblock *bucket;
+ char *start, *end;
+ int ind;
+
+ d(printf(" checking bucket %d\n", hashbucket));
+
+ /* get the real bucket id from the hashbucket id */
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashbucket));
+ /* and get the key number within the block */
+ ind = HASH_INDEX(hashbucket);
+
+ g_assert(ind < bucket->used);
+
+ start = &bucket->hb_keydata[bucket->hb_keys[ind].keyoffset];
+ if (ind == 0) {
+ end = &bucket->hb_keydata[sizeof(bucket->hb_keydata)/sizeof(bucket->hb_keydata[0])];
+ } else {
+ end = &bucket->hb_keydata[bucket->hb_keys[ind-1].keyoffset];
+ }
+ if ( (end-start) == keylen
+ && memcmp(start, key, keylen) == 0) {
+ struct _hashblock *prevbucket;
+
+ if (hashprev == 0) {
+ /* unlink from hash chain */
+ table->buckets[hashentry] = bucket->hb_keys[HASH_INDEX(hashbucket)].next;
+ /* link into free list */
+ bucket->hb_keys[HASH_INDEX(hashbucket)].next = hashroot->free;
+ hashroot->free = hashbucket;
+ /* compress away data */
+ hash_compress(bucket, HASH_INDEX(hashbucket));
+ ibex_block_dirty((struct _block *)bucket);
+ ibex_block_dirty((struct _block *)table);
+ ibex_block_dirty((struct _block *)hashroot);
+ } else {
+ prevbucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashprev));
+ prevbucket->hb_keys[HASH_INDEX(hashprev)].next =
+ bucket->hb_keys[ind].next;
+ /* link into free list */
+ bucket->hb_keys[ind].next = hashroot->free;
+ hashroot->free = hashbucket;
+ /* compress entry */
+ hash_compress(bucket, ind);
+ ibex_block_dirty((struct _block *)bucket);
+ ibex_block_dirty((struct _block *)prevbucket);
+ ibex_block_dirty((struct _block *)hashroot);
+ }
+ return;
+ }
+ hashprev = hashbucket;
+ hashbucket = bucket->hb_keys[ind].next;
+ }
+}
+
+/* set where the datablock is located */
+static void
+hash_set_data_block(struct _IBEXIndex *index, hashid_t keyid, blockid_t blockid, blockid_t tail)
+{
+ struct _hashblock *bucket;
+
+ d(printf("setting data block hash %d to %d tail %d\n", keyid, blockid, tail));
+
+ /* map to a block number */
+ g_assert((blockid & (BLOCK_SIZE-1)) == 0);
+ blockid >>= BLOCK_BITS;
+
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(keyid));
+ if (bucket->hb_keys[HASH_INDEX(keyid)].root != blockid
+ || bucket->hb_keys[HASH_INDEX(keyid)].tail != tail) {
+ bucket->hb_keys[HASH_INDEX(keyid)].tail = tail;
+ bucket->hb_keys[HASH_INDEX(keyid)].root = blockid;
+ ibex_block_dirty((struct _block *)bucket);
+ }
+}
+
+static blockid_t
+hash_get_data_block(struct _IBEXIndex *index, hashid_t keyid, blockid_t *tail)
+{
+ struct _hashblock *bucket;
+
+ d(printf("getting data block hash %d\n", keyid));
+
+ if (keyid == 0) {
+ if (tail)
+ *tail = 0;
+ return 0;
+ }
+
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(keyid));
+ if (tail)
+ *tail = bucket->hb_keys[HASH_INDEX(keyid)].tail;
+ return bucket->hb_keys[HASH_INDEX(keyid)].root << BLOCK_BITS;
+}
+
+static hashid_t
+hash_insert(struct _IBEXIndex *index, const char *key, int keylen)
+{
+ struct _hashroot *hashroot;
+ guint32 hash;
+ int hashentry;
+ blockid_t hashtable;
+ hashid_t hashbucket, keybucket, keyprev, keyfree;
+ struct _hashtableblock *table;
+ struct _hashblock *bucket;
+ int count;
+
+ g_assert(index != 0);
+ g_assert(index->root != 0);
+
+ d(printf("inserting hash %.*s\n", keylen, key));
+
+ hashroot = (struct _hashroot *)ibex_block_read(index->blocks, index->root);
+
+ /* find the table containing this entry */
+ hash = hash_key(key, keylen) % hashroot->size;
+ hashtable = hashroot->table[hash / (BLOCK_SIZE/sizeof(blockid_t))];
+ table = (struct _hashtableblock *)ibex_block_read(index->blocks, hashtable);
+ hashentry = hash % (BLOCK_SIZE/sizeof(blockid_t));
+ /* and its bucket */
+ hashbucket = table->buckets[hashentry];
+
+ /* now look for a free slot, first try the free list */
+ /* but dont try too hard if our key is just too long ... so just scan upto
+ 4 blocks, but if we dont find a space, tough ... */
+ keybucket = hashroot->free;
+ keyprev = 0;
+ count = 0;
+ while (keybucket && count<4) {
+ int space;
+
+ d(printf(" checking free %d\n", keybucket));
+
+ /* read the bucket containing this free key */
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(keybucket));
+
+ /* check if there is enough space for the key */
+ space = &bucket->hb_keydata[bucket->hb_keys[bucket->used-1].keyoffset]
+ - (char *)&bucket->hb_keys[bucket->used];
+ if (space >= keylen) {
+ hash_expand(bucket, HASH_INDEX(keybucket), keylen);
+ memcpy(&bucket->hb_keydata[bucket->hb_keys[HASH_INDEX(keybucket)].keyoffset],
+ key, keylen);
+
+ /* check if there is free space still in this node, and there are no other empty blocks */
+ keyfree = bucket->hb_keys[HASH_INDEX(keybucket)].next;
+ if ((space-keylen) >= KEY_THRESHOLD) {
+ int i;
+ int head = ARRAY_LEN(bucket->hb_keydata);
+ int found = FALSE;
+
+ for (i=0;i<bucket->used;i++) {
+ if (bucket->hb_keys[i].keyoffset == head) {
+ /* already have a free slot in this block, leave it */
+ found = TRUE;
+ break;
+ }
+ head = bucket->hb_keys[i].keyoffset;
+ }
+ if (!found) {
+ /* we should link in a new free slot for this node */
+ bucket->hb_keys[bucket->used].next = bucket->hb_keys[HASH_INDEX(keybucket)].next;
+ bucket->hb_keys[bucket->used].keyoffset = bucket->hb_keys[bucket->used-1].keyoffset;
+ keyfree = HASH_KEY(HASH_BLOCK(keybucket), bucket->used);
+ bucket->used++;
+ }
+ }
+ /* link 'keyfree' back to the parent ... */
+ if (keyprev == 0) {
+ hashroot->free = keyfree;
+ ibex_block_dirty((struct _block *)hashroot);
+ } else {
+ struct _hashblock *prevbucket;
+ prevbucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(keyprev));
+ prevbucket->hb_keys[HASH_INDEX(keyprev)].next = keyfree;
+ ibex_block_dirty((struct _block *)prevbucket);
+ }
+
+ /* link into the hash chain */
+ bucket->hb_keys[HASH_INDEX(keybucket)].next = hashbucket;
+ bucket->hb_keys[HASH_INDEX(keybucket)].root = 0;
+ bucket->hb_keys[HASH_INDEX(keybucket)].tail = 0;
+ table->buckets[hashentry] = keybucket;
+ ibex_block_dirty((struct _block *)table);
+ ibex_block_dirty((struct _block *)bucket);
+
+ d(printf(" new key id %d\n", keybucket));
+ d(printf(" new free id %d\n", hashroot->free));
+
+ return keybucket;
+ }
+
+ count++;
+ keyprev = keybucket;
+ keybucket = bucket->hb_keys[HASH_INDEX(keybucket)].next;
+ }
+
+ /* else create a new block ... */
+ keybucket = ibex_block_get(index->blocks);
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, keybucket);
+
+ d(printf("creating new key bucket %d\n", keybucket));
+
+ memset(bucket, 0, sizeof(*bucket));
+
+ bucket->used = 2;
+ /* first block, is the new key */
+ bucket->hb_keys[0].keyoffset = ARRAY_LEN(bucket->hb_keydata) - keylen;
+ memcpy(&bucket->hb_keydata[bucket->hb_keys[0].keyoffset], key, keylen);
+ bucket->hb_keys[0].next = hashbucket;
+ bucket->hb_keys[0].root = 0;
+ bucket->hb_keys[0].tail = 0;
+
+ table->buckets[hashentry] = HASH_KEY(keybucket, 0);
+
+ /* next block is a free block, link into free list */
+ bucket->hb_keys[1].keyoffset = bucket->hb_keys[0].keyoffset;
+ bucket->hb_keys[1].next = hashroot->free;
+ hashroot->free = HASH_KEY(keybucket, 1);
+
+ ibex_block_dirty((struct _block *)hashroot);
+ ibex_block_dirty((struct _block *)table);
+ ibex_block_dirty((struct _block *)bucket);
+
+ d(printf(" new key id %d\n", HASH_KEY(keybucket, 0)));
+ d(printf(" new free id %d\n", hashroot->free));
+
+ return HASH_KEY(keybucket, 0);
+}
+
+/* debug */
+void ibex_hash_dump(struct _IBEXIndex *index);
+
+void
+ibex_hash_dump(struct _IBEXIndex *index)
+{
+ int i;
+ struct _hashtableblock *table;
+ struct _hashblock *bucket;
+ struct _hashroot *hashroot;
+ blockid_t hashtable;
+ hashid_t hashbucket;
+
+ printf("Walking hash tree:\n");
+ hashroot = (struct _hashroot *)ibex_block_read(index->blocks, index->root);
+ for (i=0;i<hashroot->size;i++) {
+ printf("Hash table chain: %d\n", i);
+ hashtable = hashroot->table[i / (BLOCK_SIZE/sizeof(blockid_t))];
+ table = (struct _hashtableblock *)ibex_block_read(index->blocks, hashtable);
+ hashbucket = table->buckets[i % (BLOCK_SIZE/sizeof(blockid_t))];
+ while (hashbucket) {
+ int len;
+
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashbucket));
+ printf(" bucket %d: [used %d]", hashbucket, bucket->used);
+ if (HASH_INDEX(hashbucket) == 0) {
+ len = ARRAY_LEN(bucket->hb_keydata) -
+ bucket->hb_keys[HASH_INDEX(hashbucket)].keyoffset;
+ } else {
+ len = bucket->hb_keys[HASH_INDEX(hashbucket)-1].keyoffset -
+ bucket->hb_keys[HASH_INDEX(hashbucket)].keyoffset;
+ }
+ printf("'%.*s' = %d next=%d\n", len, &bucket->hb_keydata[bucket->hb_keys[HASH_INDEX(hashbucket)].keyoffset],
+ bucket->hb_keys[HASH_INDEX(hashbucket)].root,
+ bucket->hb_keys[HASH_INDEX(hashbucket)].next);
+ ibex_diskarray_dump(index->blocks,
+ bucket->hb_keys[HASH_INDEX(hashbucket)].root << BLOCK_BITS,
+ bucket->hb_keys[HASH_INDEX(hashbucket)].tail);
+
+ hashbucket = bucket->hb_keys[HASH_INDEX(hashbucket)].next;
+ }
+ /* make sure its still in the cache */
+ hashroot = (struct _hashroot *)ibex_block_read(index->blocks, index->root);
+ }
+
+ hashbucket = hashroot->free;
+ printf("Dumping free lists ..\n");
+ while (hashbucket) {
+ printf(" %d", hashbucket);
+ bucket = (struct _hashblock *)ibex_block_read(index->blocks, HASH_BLOCK(hashbucket));
+ hashbucket = bucket->hb_keys[HASH_INDEX(hashbucket)].next;
+ }
+ printf("\n");
+}
+
+#if 0
+int main(int argc, char **argv)
+{
+ struct _memcache *bc;
+ struct _IBEXIndex *hash;
+ int i;
+
+ bc = ibex_block_cache_open("index.db", O_CREAT|O_RDWR, 0600);
+ hash = ibex_hash_class.create(bc, 1024);
+ for (i=0;i<10000;i++) {
+ char key[16];
+ sprintf(key, "key %d", i);
+ ibex_hash_class.insert(hash, key, strlen(key));
+ }
+
+ for (i=500;i<1000;i++) {
+ char key[16];
+ sprintf(key, "key %d", i);
+ ibex_hash_class.remove(hash, key, strlen(key));
+ }
+
+ for (i=500;i<1000;i++) {
+ char key[16];
+ sprintf(key, "key %d", i);
+ ibex_hash_class.insert(hash, key, strlen(key));
+ }
+
+
+ ibex_hash_dump(hash);
+
+ for (i=0;i<2000;i++) {
+ char key[16], *lookup;
+ hashid_t keyid;
+ blockid_t root, tail;
+
+ sprintf(key, "key %d", i);
+ keyid = ibex_hash_class.find(hash, key, strlen(key));
+ lookup = ibex_hash_class.get_key(hash, keyid, 0);
+ root = ibex_hash_class.get_data(hash, keyid, &tail);
+ printf("key %s = %d = '%s' root:%d tail:%d \n", key, keyid, lookup, root, tail);
+ g_free(lookup);
+ }
+
+ ibex_hash_class.close(hash);
+ ibex_block_cache_close(bc);
+ return 0;
+}
+
+#endif
generated by cgit (git 2.34.1) at 2024-12-03 21:13:12 +0800