/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- * * Copyright (C) 2000 Ximian, Inc. * * Authors: Michael Zucchi * * 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 #include #include #include #include #include #include #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;itable[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;iused;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;iused;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;iused;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;isize;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 tr> * The GNU Ada compiler system built from GCC 4.4.0.glarkin2009-11-117-0/+397 * Update to the 20091108 snapshot of GCC 4.3.5.gerald2009-11-102-19/+19 * - Update to snapshot r6215.tdb2009-11-092-4/+4 * Add option for UTF8 supportarved2009-11-091-0/+8 * - Fix installation of hs-ghc-paths as slave port when build is launched inpgj2009-11-091-4/+4 * - Mark BROKEN: does not compilepav2009-11-071-0/+2 * Update to the 20091105 snapshot of GCC 4.5.0.gerald2009-11-0710-95/+95 * Update to the 20091103 snapshot of GCC 4.4.3.gerald2009-11-062-19/+19 * Fix script "use.perl": correctly check variables 'need_*'.skv2009-11-065-35/+35 * - Fix build on 9.0amdmi32009-11-051-0/+11 * Fix plist (missing DATADIR).brooks2009-11-054-14/+20 * - Take maintainership of caudium12 and pike72 at maintainer's requestjohans2009-11-051-1/+1 * - Fix build on 9.0amdmi32009-11-052-0/+12 * - Update to 2.7.7miwi2009-11-042-4/+4 * - Fix behaviour of USE_PERL option when it is "off"skv2009-11-0310-25/+60 * Fix build error on -CURRENT (result of a parsing fix in /bin/sh)johans2009-10-311-2/+2 * Update to the 20091029 snapshot of GCC 4.5.0.gerald2009-10-3110-95/+95 * Fix pkg-plisterwin2009-10-312-0/+2 * Update to the 20091027 snapshot of GCC 4.4.3.gerald2009-10-302-19/+19 * Improve Emacs indentation code (the try/after clause is now handled correctly.)olgeni2009-10-274-0/+416 * - fix build unter FreeBSD 9dinoex2009-10-262-9/+45 * - Add sparc64 support (untested).stas2009-10-262-5/+8 * Add a port of the clang C, Objective-C, and (soon) C++ compiler versionbrooks2009-10-2510-0/+364 * Update to the 20091022 snapshot of GCC 4.5.0.gerald2009-10-2510-95/+95 * Update to the 20091020 snapshot of GCC 4.4.3 which is pretty much thegerald2009-10-252-19/+19 * - Fix issue when the handle of tempfile become closed when the filestas2009-10-241-0/+10 * - Add port for lang/stalin, an aggressive optimizing Scheme compiler, whichstas2009-10-246-0/+92 * Also mark BROKEN on 7.xerwin2009-10-231-1/+1 * - Update to 5.2.1yzlin2009-10-203-24/+4 * Update to 2.15.tobez2009-10-202-5/+4 * - Mark broken on FreeBSD 6.xjohans2009-10-201-0/+4 * Update to the 20091015 snapshot of GCC 4.5.0.gerald2009-10-1710-95/+95 * - Update bootstrap binaries to the latest version.stas2009-10-162-19/+19 * - Fix previous updateanray2009-10-161-1/+1 * - Fix buildanray2009-10-161-1/+1 * - Update to 0.90.2anray2009-10-164-24/+14 * - Update to 1.0.31.stas2009-10-153-7/+32 * - Fix SIGINT signal handling.stas2009-10-121-0/+21 * - Update ruby 1.9.1 to patchlevel 243.stas2009-10-122-7/+3 * - Don't build ruby with threads support on FreeBSD versions before 7.2stas2009-10-123-18/+150 * Fix sockets.ale2009-10-124-2/+24 * Update to the 20091008 snapshot of GCC 4.5.0. Add math/mpc as agerald2009-10-1110-100/+105 * - Remove dependency on security/nettle in preparation of nettle upgradejohans2009-10-091-4/+4 * Update to 3.1johans2009-10-094-211/+238 * Update to 7.8.352johans2009-10-093-57/+53 * Update to the 20091006 snapshot of GCC 4.4.2.gerald2009-10-092-19/+19 * Update to the 20091004 snapshot of GCC 4.3.5.gerald2009-10-082-20/+20 * Update to the 20091001 snapshot of GCC 4.5.0.gerald2009-10-0310-95/+95 * Update to the 20090929 snapshot of GCC 4.4.2.gerald2009-10-032-28/+19 * Update to 0.74.tobez2009-10-012-4/+4 * Update to the 20090922 snapshot of GCC 4.4.2.gerald2009-09-302-19/+19 * - Update to 0.11.3wen2009-09-273-6/+5 * For GCC 4.5 libgcj has been broken up such compilation no longer requiresgerald2009-09-275-45/+0 * - Update to 10.1.5.stas2009-09-273-4/+5 * Update to the 20090924 snapshot of GCC 4.5.0.gerald2009-09-2610-95/+95 * Unbreak: make it fetchable again.mva2009-09-261-4/+4 * - Update to 090922pav2009-09-234-6/+19 * Upgrade to version R13B02.olgeni2009-09-2217-466/+382 * Update to 5.2.11 release.ale2009-09-2212-96/+54 * - Add missing testsuitemiwi2009-09-201-0/+3 * - Update to 20090718miwi2009-09-194-4/+12 * Update to the 20090917 snapshot of GCC 4.5.0.gerald2009-09-1910-95/+95 * Over to new volunteer.linimon2009-09-181-1/+1 * Update to the 20090915 snapshot of GCC 4.4.2.gerald2009-09-182-19/+19 * - Update WWWpav2009-09-171-1/+1 * Reset ports@mcdermottroe.com at his request due to lack of time at thelinimon2009-09-171-1/+1 * - Mark BROKEN: does not buildpav2009-09-171-0/+2 * Fix build if POSIX semaphore enabled ismiwi2009-09-164-4/+16 * - Update to 4.172tabthorpe2009-09-163-5/+6 * Update to the 20090913 snapshot of GCC 4.3.5.gerald2009-09-142-19/+19 * Bump PORTREVISION for everything that sets USE_FORTRAN=yes which nowgerald2009-09-131-1/+1 * - Fix build on FreeBSD 6.Xmiwi2009-09-132-0/+8 * - Add support for FreeBSD 9.0miwi2009-09-1110-30/+76 * Update to the 20090910 snapshot of GCC 4.5.0.gerald2009-09-1110-95/+95 * Update to 5.10.1skv2009-09-1188-2336/+1276 * Update to 0.25_02 - to unbreak on Perl 5.10.1lth2009-09-112-4/+4 * Update to the 20090908 snapshot of GCC 4.4.2.gerald2009-09-102-19/+19 * - Update to 2009-09-06miwi2009-09-093-6/+9 * - Fix build in 6.X.araujo2009-09-092-2/+1 * - Don't use UNZIP_CMD in a DEPENDS line. A user may redefine UNZIP_CMD to bewxs2009-09-091-1/+1 * - Update to 4.171avl2009-09-083-5/+5 * Boo is a new, object-oriented, statically-typed programming language for theglewis2009-09-087-0/+224 * - Update to version 4.1.0.alepulver2009-09-077-196/+154 * Add "buildplt" target to Makefile. When invoked, it builds a fullolgeni2009-09-062-0/+18 * Remove NOPRECIOUSMAKEVARS; when ARCH is i386, set ARCH=x86 in MAKE_ARGS.olgeni2009-09-062-2/+8 * Use "+=" rather than "=" when modifying CONFIGURE_ENV.olgeni2009-09-062-2/+2 * Update to the 20090827 snapshot of GCC 4.5.0.gerald2009-09-0410-95/+95 * - Update to 3.0.1.araujo2009-09-043-7/+6 * Update to the 20090901 snapshot of GCC 4.4.2.gerald2009-09-042-19/+19 * Update to 0.02.tobez2009-09-032-4/+4 * - Update GHC and Haskell ports to 6.10.4 (for both i386 and amd64), bumppgj2009-09-0214-1611/+2598 * - Retire MASTER_SITE_SOURCEFORGE_EXTENDED, it's no longer needed - all mirror...amdmi32009-09-022-4/+2 * Add lang/p5-Try-Tiny 0.01, a Perl module thattobez2009-09-025-0/+37 * Update the PHP documentation to 2009-09-01edwin2009-09-012-34/+40 * Mark BROKEN: does not builderwin2009-09-011-0/+2 * . create empty directories needed for dependent ports (those directoriesbsam2009-08-312-1/+4 * Layout of the MASTER_SITE changed. Adjust URLsarved2009-08-312-2/+3 * Readd DIST_SUBDIR to fix fetchingerwin2009-08-301-0/+1 * Reset chinsan@FreeBSD.org due to numerous maintainer-timeouts and nolinimon2009-08-291-1/+1 * - Update to 4.170pgj2009-08-283-7/+7 * - Fix some more SF URLs, including ones in PATCH_SITES and comments (for cons...amdmi32009-08-283-4/+3 * Update to the 20090825 snapshot of GCC 4.4.2.gerald2009-08-282-19/+19 * - Remove remaining SFP references (switch these ports to SF)amdmi32009-08-272-3/+2 * Update to the 20090823 snapshot of GCC 4.3.5.gerald2009-08-272-19/+19 * - Update to 05_20090816gahr2009-08-252-5/+5 * Update to 1.69.01skv2009-08-242-4/+4 * Remove BROKEN, probably an error on the cluster.erwin2009-08-231-2/+0 * Update to the 20090820 snapshot of GCC 4.5.0.gerald2009-08-2210-95/+95 * - Update lang/python31 to Python 3.1.1lwhsu2009-08-226-14/+14 * - Fix broken makefiles introduced with translation to new SF File Release Systemamdmi32009-08-221-2/+1 * - Switch SourceForge ports to the new File Release System: categories startin...amdmi32009-08-2240-75/+43 * Mark BROKEN on 8.x: does not builderwin2009-08-211-0/+4 * Mark BROKEN: does not builderwin2009-08-211-0/+2 * Mark BROKEN on 8.x: does not support FreeBSD 8.xerwin2009-08-211-0/+4 * - add experimetal support for new archsdinoex2009-08-215-5/+89 * Update to the 20090818 snapshot of GCC 4.4.2.gerald2009-08-212-19/+19 * Remove lang/gcc42-withgcjawt which basically is just lang/gcc42 withgerald2009-08-204-124/+0 * - Update to 3b2pav2009-08-204-15/+13 * - Update to 1.9.90gahr2009-08-183-23/+23 * Revert unmarking BROKEN, still dumps core during build.erwin2009-08-181-0/+4 * - Fix build on amd64gahr2009-08-181-4/+5 * - Fix pkg-listacm2009-08-171-0/+9 * - Add missing dependenciesacm2009-08-172-6/+11 * - Update to 7.4damdmi32009-08-172-8/+9 * - Mark BROKEN on amd64: does not linkpav2009-08-171-1/+7 * - Mark all gambas-gb-db-* ports broken, they do not installpav2009-08-171-0/+6 * Mark as broken on sparc64: fails to link.linimon2009-08-161-1/+7 * Mark BROKEN on 8.x: does not builderwin2009-08-161-1/+3 * Mark BROKEN: does not fetcherwin2009-08-151-0/+2 * Mark as broken on amd64 (leaves files behind on deinstall), and sparc64linimon2009-08-151-2/+10 * Update to the 20090813 snapshot of GCC 4.5.0.gerald2009-08-1410-95/+95 * - Use dirrmtry in lib-old dir to fix some plist leftloversmiwi2009-08-134-4/+4 * - Fix fetchmiwi2009-08-131-4/+1 * Update to the 20090809 snapshot of GCC 4.3.5.gerald2009-08-132-19/+19 * - Mark MAKE_JOBS_UNSAFE (when forced jobs, fails with "cd: can't cd to src/rtt")amdmi32009-08-121-0/+1 * Update to the 20090811 snapshot of GCC 4.4.2.gerald2009-08-122-19/+19 * - Update to 10.1.1.stas2009-08-113-6/+18 * Fix the build.danfe2009-08-112-7/+7 * Update for 1.8.1daichi2009-08-114-54/+24 * - Update to 20090808amdmi32009-08-113-4/+5 * - Update to 2.8.araujo2009-08-103-5/+5 * - Update lang/mono to 2.4.2.3.flz2009-08-106-83/+40 * - Register CONFLICTS for lang/pike* ports (binaries + manuals in same place)johans2009-08-093-0/+6 * - Update to 1.0.30.stas2009-08-095-83/+46 * 2009-07-28 lang/tinycobol: no longer being developed; consider using lang/ope...erwin2009-08-089-148/+0 * The port maintainer says that this works on amd64 for him, but pointyhatrnoland2009-08-081-1/+1 * - Update to 5e6miwi2009-08-085-82/+79 * - Really is MAKE_JOBS_UNSAFEpav2009-08-071-1/+1 * Update to the 20090806 snapshot of GCC 4.5.0.gerald2009-08-0710-95/+95 * Update to the 20090804 snapshot of GCC 4.4.2.gerald2009-08-062-19/+19 * Remove BROKEN and allow amd64 ARCHrnoland2009-08-061-5/+1 * - Update to 3b1amdmi32009-08-053-9/+13 * Add lang/p5-signatures 0.06, a Perl module that brings subroutinetobez2009-08-045-0/+42 * follow convention and send the ruby- ports to ruby@pgollucci2009-08-041-1/+1 * - Update to snapshot of 2009-08-03gahr2009-08-033-131/+157 * - Update to 2.15.2acm2009-08-036-12/+9 * - Fix fetch problemsacm2009-08-032-0/+2 * -Repocopy devel/libtool15 -> libtool22 and libltdl15 -> libltdl22.mezz2009-08-0333-35/+37 * Mark BROKEN on i386 6.x: does not compile.erwin2009-08-022-2/+2 * - Fix build with WITH_SEM but ${OSVERSION} < 701106 (mark IGNORE correctly)lwhsu2009-08-022-2/+0 * Reset maintainer per his request in private email.linimon2009-08-021-1/+1 * Update to the 20090730 snapshot of GCC 4.5.0.gerald2009-08-0110-95/+95 * Update to the 20090726 snapshot of GCC 4.3.4.gerald2009-08-012-19/+19 * - bump all port that indirectly depends on libjpeg and have not yet been bump...dinoex2009-07-3127-18/+27 * Update to the 20090728 snapshot of GCC 4.4.2.gerald2009-07-312-19/+19 * Utilize %%SITE_PERL%% and %%PERL_ARCH%% in pkg-plistspgollucci2009-07-311-2/+2 * Update to 1.9.0johans2009-07-314-16/+27 * - Mark MAKE_JOBS_UNSAFEamdmi32009-07-301-2/+3 * - Update to snapshot of 20090624gahr2009-07-302-4/+4 * - Fix installation (missing binary)gahr2009-07-301-1/+2 * Mark broken on FreeBSD-8johans2009-07-301-0/+4 * - Update URL of my distfile mirror in 87 portsamdmi32009-07-292-2/+2 * - Update to 2.15.0acm2009-07-288-23/+15 * Update to 0.24lth2009-07-272-4/+4 * Fix JUN OPTIONarved2009-07-252-1/+5 * Update to the 20090723 snapshot of GCC 4.5.0.gerald2009-07-2510-95/+95 * Fix CONFLICTSarved2009-07-252-3/+6 * Development previewpgollucci2009-07-244-11/+14 * Update to the 20090721 snapshot of GCC 4.4.1, which basically coincidesgerald2009-07-232-19/+19 * - lang/perl5.6 is dead, remove PERL_LEVEL/PERL_VERSION < 500801 checkspgollucci2009-07-232-17/+4 * Fix build (broken due to recent autoconf changes).shaun2009-07-221-1/+24 * Update to 1.4.0skv2009-07-223-7/+8 * - Update to 2.2.3pgollucci2009-07-212-4/+4 * - Add ${PTHREAD_LIBS} to LDFLAGS in threaded build. This fixes the issuestas2009-07-201-0/+1 * Mark this as only for i386.deischen2009-07-191-0/+2 * Forgot a file in the last commit.deischen2009-07-191-0/+10 * Update to the 2009 gpl edition.deischen2009-07-1916-3164/+156 * Remove lang/gcc-ooo which is no longer used by the OpenOffice ports andgerald2009-07-198-234/+0 * Update to the 20090716 snapshot of GCC 4.5.0.gerald2009-07-1810-95/+95 * - update to jpeg7dinoex2009-07-1812-18/+20 * Update to the 20090714 snapshot of GCC 4.4.1.gerald2009-07-182-19/+19 * Remove -D_GNU_SOURCE from CPPFLAGS as it causes segfault in strerror_r.flz2009-07-172-1/+2 * - Update lang/mono to 2.4.2.2flz2009-07-17