aboutsummaryrefslogtreecommitdiffstats
path: root/cmd/ethereum/repl/repl_darwin.go
blob: ba7dae996d679329a1e8079bda93c9a03c0940c7 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package ethrepl

// #cgo darwin CFLAGS: -I/usr/local/opt/readline/include
// #cgo darwin LDFLAGS: -L/usr/local/opt/readline/lib
// #cgo LDFLAGS: -lreadline
// #include <stdio.h>
// #include <stdlib.h>
// #include <readline/readline.h>
// #include <readline/history.h>
import "C"
import (
    "fmt"
    "os"
    "os/signal"
    "strings"
    "syscall"
    "unsafe"
)

func initReadLine() {
    C.rl_catch_sigwinch = 0
    C.rl_catch_signals = 0
    c := make(chan os.Signal, 1)
    signal.Notify(c, syscall.SIGWINCH)
    signal.Notify(c, os.Interrupt)
    go func() {
        for sig := range c {
            switch sig {
            case syscall.SIGWINCH:
                C.rl_resize_terminal()

            case os.Interrupt:
                C.rl_cleanup_after_signal()
            default:

            }
        }
    }()
}

func readLine(prompt *string) *string {
    var p *C.char

    //readline allows an empty prompt(NULL)
    if prompt != nil {
        p = C.CString(*prompt)
    }

    ret := C.readline(p)

    if p != nil {
        C.free(unsafe.Pointer(p))
    }

    if ret == nil {
        return nil
    } //EOF

    s := C.GoString(ret)
    C.free(unsafe.Pointer(ret))
    return &s
}

func addHistory(s string) {
    p := C.CString(s)
    C.add_history(p)
    C.free(unsafe.Pointer(p))
}

var indentCount = 0
var str = ""

func (self *JSRepl) setIndent() {
    open := strings.Count(str, "{")
    open += strings.Count(str, "(")
    closed := strings.Count(str, "}")
    closed += strings.Count(str, ")")
    indentCount = open - closed
    if indentCount <= 0 {
        self.prompt = "> "
    } else {
        self.prompt = strings.Join(make([]string, indentCount*2), "..")
        self.prompt += " "
    }
}

func (self *JSRepl) read() {
    initReadLine()
L:
    for {
        switch result := readLine(&self.prompt); true {
        case result == nil:
            break L

        case *result != "":
            str += *result + "\n"

            self.setIndent()

            if indentCount <= 0 {
                if *result == "exit" {
                    self.Stop()
                    break L
                }

                hist := str[:len(str)-1]
                addHistory(hist) //allow user to recall this line
                self.history.WriteString(str)

                self.parseInput(str)

                str = ""
            }
        }
    }
}

func (self *JSRepl) PrintValue(v interface{}) {
    method, _ := self.re.Vm.Get("prettyPrint")
    v, err := self.re.Vm.ToValue(v)
    if err == nil {
        val, err := method.Call(method, v)
        if err == nil {
            fmt.Printf("%v", val)
        }
    }
}
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859
/* -*- 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