From 7ecf94d4b339bc2197f449f0f1538f2915313087 Mon Sep 17 00:00:00 2001 From: pixel Date: Mon, 28 Jan 2008 12:49:06 +0000 Subject: Trying with a hashtable instead of a dumb structure. --- hashtab.h | 216 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 216 insertions(+) create mode 100644 hashtab.h (limited to 'hashtab.h') diff --git a/hashtab.h b/hashtab.h new file mode 100644 index 0000000..2f8b22c --- /dev/null +++ b/hashtab.h @@ -0,0 +1,216 @@ +/* +-------------------------------------------------------------------- +By Bob Jenkins, 1996. hash.h. Public Domain. + +This implements a hash table. +* Keys are unique. Adding an item fails if the key is already there. +* Keys and items are pointed at, not copied. If you change the value + of the key after it is inserted then hfind will not be able to find it. +* The hash table maintains a position that can be set and queried. +* The table length doubles dynamically and never shrinks. The insert + that causes table doubling may take a long time. +* The table length splits when the table length equals the number of items + Comparisons usually take 7 instructions. + Computing a hash value takes 35+6n instructions for an n-byte key. + + hcreate - create a hash table + hdestroy - destroy a hash table + hcount - The number of items in the hash table + hkey - key at the current position + hkeyl - key length at the current position + hstuff - stuff at the current position + hfind - find an item in the table + hadd - insert an item into the table + hdel - delete an item from the table + hstat - print statistics about the table + hfirst - position at the first item in the table + hnext - move the position to the next item in the table +-------------------------------------------------------------------- +*/ + +#ifndef HASHTAB +#define HASHTAB + +#include +#include + +/* PRIVATE TYPES AND DEFINITIONS */ + +struct hitem +{ + uint8_t *key; /* key that is hashed */ + uint32_t keyl; /* length of key */ + void *stuff; /* stuff stored in this hitem */ + uint32_t hval; /* hash value */ + struct hitem *next; /* next hitem in list */ +}; +typedef struct hitem hitem; + + +struct htab +{ + struct hitem **table; /* hash table, array of size 2^logsize */ + int logsize; /* log of size of table */ + size_t mask; /* (hashval & mask) is position in table */ + uint32_t count; /* how many items in this hash table so far? */ + uint32_t apos; /* position in the array */ + struct hitem *ipos; /* current item in the array */ + struct reroot *space; /* space for the hitems */ + uint32_t bcount; /* # hitems useable in current block */ +}; +typedef struct htab htab; + +#ifdef __cplusplus +extern "C" { +#endif + +/* PUBLIC FUNCTIONS */ + +/* hcreate - create a hash table + ARGUMENTS: + logsize - 1<count) +#define hkey(t) ((t)->ipos->key) +#define hkeyl(t) ((t)->ipos->keyl) +#define hstuff(t) ((t)->ipos->stuff) + + + +/* hfind - move the current position to a given key + ARGUMENTS: + t - the hash table + key - the key to look for + keyl - length of the key + RETURNS: + TRUE if the item exists, FALSE if it does not. + If the item exists, moves the current position to that item. + */ +int hfind(htab *t, uint8_t *key, uint32_t keyl); + + +/* hadd - add a new item to the hash table + change the position to point at the item with the key + ARGUMENTS: + t - the hash table + key - the key to look for + keyl - length of the key + stuff - other stuff to be stored in this item + RETURNS: + FALSE if the operation fails (because that key is already there). + */ +int hadd(htab *t, uint8_t *key, uint32_t keyl, void *stuff); + + +/* hdel - delete the item at the current position + change the position to the following item + ARGUMENTS: + t - the hash table + RETURNS: + FALSE if there is no current item (meaning the table is empty) + NOTE: + This frees the item, but not the key or stuff stored in the item. + If you want these then deal with them first. For example: + if (hfind(tab, key, keyl)) + { + free(hkey(tab)); + free(hstuff(tab)); + hdel(tab); + } + */ +int hdel(htab *t); + + +/* hfirst - move position to the first item in the table + ARGUMENTS: + t - the hash table + RETURNS: + FALSE if there is no current item (meaning the table is empty) + NOTE: + */ +int hfirst(htab *t); + + +/* hnext - move position to the next item in the table + ARGUMENTS: + t - the hash table + RETURNS: + FALSE if the position wraps around to the beginning of the table + NOTE: + To see every item in the table, do + if (hfirst(t)) do + { + key = hkey(t); + stuff = hstuff(t); + } + while (hnext(t)); + */ +/* int hnext(/o_ htab *t _o/); */ +#define hnext(t) \ + ((!(t)->ipos) ? FALSE : \ + ((t)->ipos=(t)->ipos->next) ? TRUE : hnbucket(t)) + +/* hnbucket - PRIVATE - move to first item in the next nonempty bucket + ARGUMENTS: + t - the hash table + RETURNS: + FALSE if the position wraps around to the beginning of the table + NOTE: + This is private to hashtab; do not use it externally. + */ +int hnbucket(htab *t); + + +/* hstat - print statistics about the hash table + ARGUMENTS: + t - the hash table + NOTE: + items <0>: <#buckets with zero items> buckets + items <1>: <#buckets with 1 item> buckets + ... + buckets: #buckets items: #items existing: x + ( x is the average length of the list when you look for an + item that exists. When the item does not exists, the average + length is #items/#buckets. ) + + If you put n items into n buckets, expect 1/(n!)e buckets to + have n items. That is, .3678 0, .3678 1, .1839 2, ... + Also expect "existing" to be about 2. + */ +void hstat(htab *t); + +#ifdef __cplusplus +} +#endif + +#endif /* HASHTAB */ -- cgit v1.2.3