Updated zlib, adding hashing functions, and introducing first bits of a new sliding window generic algorithm.

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