summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/hashtab.h213
-rw-r--r--include/lookupa.h30
-rw-r--r--include/recycle.h69
3 files changed, 312 insertions, 0 deletions
diff --git a/include/hashtab.h b/include/hashtab.h
new file mode 100644
index 0000000..58f5163
--- /dev/null
+++ b/include/hashtab.h
@@ -0,0 +1,213 @@
+/*
+--------------------------------------------------------------------
+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
+
+/* PRIVATE TYPES AND DEFINITIONS */
+
+struct hitem
+{
+ Uint8 *key; /* key that is hashed */
+ Uint32 keyl; /* length of key */
+ void *stuff; /* stuff stored in this hitem */
+ Uint32 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 count; /* how many items in this hash table so far? */
+ Uint32 apos; /* position in the array */
+ struct hitem *ipos; /* current item in the array */
+ struct reroot *space; /* space for the hitems */
+ Uint32 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<<logsize will be the initial table length
+ RETURNS:
+ the new table
+ */
+htab *hcreate(/*_ int logsize _*/);
+
+
+/* hdestroy - destroy a hash table
+ ARGUMENTS:
+ t - the hash table to be destroyed. Note that the items and keys
+ will not be freed, the user created them and must destroy
+ them himself.
+ RETURNS:
+ nothing
+ */
+void hdestroy(/*_ htab *t _*/);
+
+
+/* hcount, hkey, hkeyl, hstuff
+ ARGUMENTS:
+ t - the hash table
+ RETURNS:
+ hcount - (ub4) The number of items in the hash table
+ hkey - (ub1 *) key for the current item
+ hkeyl - (ub4) key length for the current item
+ hstuff - (void *) stuff for the current item
+ NOTE:
+ The current position always has an item as long as there
+ are items in the table, so hexist can be used to test if the
+ table is empty.
+ hkey, hkeyl, and hstuff will crash if hcount returns 0
+ */
+#define hcount(t) ((t)->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, ub1 *key, ub4 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, ub1 *key, ub4 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 */
diff --git a/include/lookupa.h b/include/lookupa.h
new file mode 100644
index 0000000..5f0f385
--- /dev/null
+++ b/include/lookupa.h
@@ -0,0 +1,30 @@
+/*
+------------------------------------------------------------------------------
+By Bob Jenkins, September 1996.
+lookupa.h, a hash function for table lookup, same function as lookup.c.
+Use this code in any way you wish. Public Domain. It has no warranty.
+Source is http://burtleburtle.net/bob/c/lookupa.h
+------------------------------------------------------------------------------
+*/
+
+#ifndef LOOKUPA
+#define LOOKUPA
+
+#include "generic.h"
+
+#define CHECKSTATE 8
+#define hashsize(n) ((ub4)1<<(n))
+#define hashmask(n) (hashsize(n)-1)
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+Uint32 lookup(/*_ ub1 *k, ub4 length, ub4 level _*/);
+void checksum(/*_ ub1 *k, ub4 length, ub4 *state _*/);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* LOOKUPA */
diff --git a/include/recycle.h b/include/recycle.h
new file mode 100644
index 0000000..875eb21
--- /dev/null
+++ b/include/recycle.h
@@ -0,0 +1,69 @@
+/*
+--------------------------------------------------------------------
+By Bob Jenkins, September 1996. recycle.h
+You may use this code in any way you wish, and it is free. No warranty.
+
+This manages memory for commonly-allocated structures.
+It allocates RESTART to REMAX items at a time.
+Timings have shown that, if malloc is used for every new structure,
+ malloc will consume about 90% of the time in a program. This
+ module cuts down the number of mallocs by an order of magnitude.
+This also decreases memory fragmentation, and freeing all structures
+ only requires freeing the root.
+--------------------------------------------------------------------
+*/
+
+#ifndef RECYCLE
+#define RECYCLE
+
+#define RESTART 0
+#define REMAX 32000
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct recycle
+{
+ struct recycle *next;
+};
+typedef struct recycle recycle;
+
+struct reroot
+{
+ struct recycle *list; /* list of malloced blocks */
+ struct recycle *trash; /* list of deleted items */
+ size_t size; /* size of an item */
+ size_t logsize; /* log_2 of number of items in a block */
+ int numleft; /* number of bytes left in this block */
+};
+typedef struct reroot reroot;
+
+/* make a new recycling root */
+reroot *remkroot(size_t mysize);
+
+/* free a recycling root and all the items it has made */
+void refree(struct reroot *r);
+
+/* get a new (cleared) item from the root */
+#define renew(r) ((r)->numleft ? \
+ (((char *)((r)->list+1))+((r)->numleft-=(r)->size)) : renewx(r))
+
+char *renewx(struct reroot *r);
+
+/* delete an item; let the root recycle it */
+/* void redel(/o_ struct reroot *r, struct recycle *item _o/); */
+#define redel(root,item) { \
+ ((recycle *)item)->next=(root)->trash; \
+ (root)->trash=(recycle *)(item); \
+}
+
+/* malloc, but complain to stderr and exit program if no joy */
+/* use plain free() to free memory allocated by remalloc() */
+char *remalloc(size_t len, char *purpose);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* RECYCLE */
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 18:36:41 +0000