/* -*- 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
