This commit was manufactured by cvs2svn to create tag 'BONOBO_0_31'.BONOBO_0_31

svn path=/tags/BONOBO_0_31/; revision=6435

1 files changed, 0 insertions, 859 deletions

diff --git a/libibex/hash.c b/libibex/hash.c
deleted file mode 100644
index f79ee8f55e..0000000000
--- a/libibex/hash.c
+++ /dev/null
@@ -1,859 +0,0 @@
-/* -*- 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 <stdlib.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;
-
-struct _HASHCursor {
-	struct _IBEXCursor cursor;
-
-	hashid_t key;
-	hashid_t block;
-	unsigned int index;
-	unsigned int size;
-};
-
-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);
-static struct _IBEXCursor *hash_get_cursor(struct _IBEXIndex *index);
-
-static struct _IBEXCursor *hash_cursor_create(struct _IBEXIndex *);
-static void hash_cursor_close(struct _IBEXCursor *);
-static guint32 hash_cursor_next(struct _IBEXCursor *);
-static char *hash_cursor_next_key(struct _IBEXCursor *, int *keylenptr);
-
-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,
-	hash_get_cursor,
-};
-
-struct _IBEXCursorClass ibex_hash_cursor_class = {
-	hash_cursor_close,
-	hash_cursor_next,
-	hash_cursor_next_key
-};
-
-/* 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 {
-	unsigned int next:32-BLOCK_BITS;	/* next block, linked list of all key blocks: block number */
-	unsigned int used:BLOCK_BITS;		/* number of 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
-
-/* size of block overhead + 2 key block overhead */
-#define MAX_KEYLEN (BLOCK_SIZE - 4 - 12 - 12)
-
-/* root block for a hash index */
-struct _hashroot {
-	hashid_t free;		/* free list */
-	guint32 size;		/* how big the hash table is */
-	hashid_t keys;		/* linked list of blocks */
-	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)
-{
-#ifdef INDEX_STAT
-	printf("Performed %d lookups, average %f depth\n", index->lookups, (double)index->lookup_total/index->lookups);
-#endif
-	g_free(index);
-	return 0;
-}
-
-/* get an iterator class */
-static struct _IBEXCursor *hash_get_cursor(struct _IBEXIndex *index)
-{
-	return hash_cursor_create(index);
-}
-
-/* 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));
-
-	/* truncate the key to the maximum size */
-	if (keylen > MAX_KEYLEN)
-		keylen = MAX_KEYLEN;
-
-	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];
-
-#ifdef INDEX_STAT
-	index->lookups++;
-#endif
-	/* go down the bucket chain, reading each entry till we are done ... */
-	while (hashbucket != 0) {
-		struct _hashblock *bucket;
-		char *start, *end;
-		int ind;
-
-#ifdef INDEX_STAT
-		index->lookup_total++;
-#endif
-
-		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;
-}
-
-static int
-hash_info(struct _hashblock *bucket, int index)
-{
-	char *start, *end;
-
-	g_assert(index < bucket->used);
-
-	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];
-	}
-
-	return end-start;
-}
-
-
-/* TODO: get rid of hash_compress/remove and just have one a-la the disktail code */
-
-/* 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));
-
-	/* truncate the key to the maximum size */
-	if (keylen > MAX_KEYLEN)
-		keylen = MAX_KEYLEN;
-
-	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);
-
-	/* truncate the key to the maximum size */
-	if (keylen > MAX_KEYLEN)
-		keylen = MAX_KEYLEN;
-
-	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);
-
-	/* link new block into keys list */
-	bucket->next = block_number(hashroot->keys);
-	hashroot->keys = keybucket;
-
-	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);
-}
-
-/* hash cursor functions */
-static struct _IBEXCursor *
-hash_cursor_create(struct _IBEXIndex *idx)
-{
-	struct _HASHCursor *idc;
-	struct _hashroot *hashroot;
-
-	idc = g_malloc(sizeof(*idc));
-	idc->cursor.klass = &ibex_hash_cursor_class;
-	idc->cursor.index = idx;
-	idc->key = 0;
-	idc->index = 0;
-
-	hashroot = (struct _hashroot *)ibex_block_read(idx->blocks, idx->root);
-	idc->size = hashroot->size;
-	idc->block = hashroot->keys;
-	
-	return &idc->cursor;
-}
-
-static void
-hash_cursor_close(struct _IBEXCursor *idc)
-{
-	g_free(idc);
-}
-
-static guint32
-hash_cursor_next(struct _IBEXCursor *idc)
-{
-	struct _HASHCursor *hc = (struct _HASHCursor *)idc;
-	struct _hashblock *bucket;
-
-	while (hc->block != 0) {
-		bucket = (struct _hashblock *)ibex_block_read(idc->index->blocks, hc->block);
-		while (hc->index < bucket->used) {
-			if (hash_info(bucket, hc->index) > 0) {
-				hc->key = HASH_KEY(hc->block, hc->index);
-				hc->index++;
-				if (hc->index == bucket->used) {
-					hc->index = 0;
-					hc->block = block_location(bucket->next);
-				}
-				return hc->key;
-			}
-			hc->index++;
-		}
-		hc->index = 0;
-		hc->block = block_location(bucket->next);
-	}
-
-	return hc->block;
-}
-
-static char *
-hash_cursor_next_key(struct _IBEXCursor *idc, int *keylenptr)
-{
-	/* TODO: this could be made slightly mroe efficient going to the structs direct.
-	   but i'm lazy today */
-	return idc->index->klass->get_key(idc->index, idc->klass->next(idc), keylenptr);
-}
-
-/* debug */
-void ibex_hash_dump(struct _IBEXIndex *index);
-static void ibex_hash_dump_rec(struct _IBEXIndex *index, int *words, int *wordslen);
-
-void ibex_hash_dump(struct _IBEXIndex *index)
-{
-	int words = 0, wordslen=0;
-
-	ibex_hash_dump_rec(index, &words, &wordslen);
-
-	printf("Total words = %d, bytes = %d, ave length = %f\n", words, wordslen, (double)wordslen/(double)words);
-}
-
-
-static void
-ibex_hash_dump_rec(struct _IBEXIndex *index, int *words, int *wordslen)
-{
-	int i;
-	struct _hashtableblock *table;
-	struct _hashblock *bucket;
-	struct _hashroot *hashroot;
-	blockid_t hashtable;
-	hashid_t hashbucket;
-	extern void ibex_diskarray_dump(struct _memcache *blocks, blockid_t head, blockid_t tail);
-
-
-	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;
-
-			*words = *words + 1;
-
-			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);
-
-			*wordslen = *wordslen + len;
-
-			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