/*
- * Sherlock Library -- Universal Hash Table
+ * UCW Library -- Universal Hash Table
*
- * (c) 2002 Martin Mares <mj@ucw.cz>
- * (c) 2002 Robert Spalek <robert@ucw.cz>
+ * (c) 2002--2004 Martin Mares <mj@ucw.cz>
+ * (c) 2002--2005 Robert Spalek <robert@ucw.cz>
*
* This software may be freely distributed and used according to the terms
* of the GNU Lesser General Public License.
* That is, `type1 k1, type2 k2, ... typen kn'.
* With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
* are mandatory.
+ * | HASH_KEY_MEMORY=f use node->f as a raw data key, compared using
+ * memcmp
+ * HASH_KEY_SIZE the length of the key block
*
* Then specify what operations you request (all names are automatically
* prefixed by calling HASH_PREFIX):
* HASH_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
* newly created node. Very useful for lookup operations.
* HASH_GIVE_ALLOC void *alloc(unsigned int size) -- allocate space for
- * a node. Default is either normal or pooled allocation
- * depending on whether we want deletions.
+ * a node. Default is xmalloc() or pooled allocation, depending
+ * on HASH_USE_POOL and HASH_AUTO_POOL switches.
* void free(void *) -- the converse.
*
* ... and a couple of extra parameters:
*
- * HASH_NOCASE string comparisons should be case-insensitive.
- * HASH_DEFAULT_SIZE=n initially, use hash table of approx. `n' entries.
- * HASH_CONSERVE_SPACE use as little space as possible.
+ * HASH_NOCASE String comparisons should be case-insensitive.
+ * HASH_DEFAULT_SIZE=n Initially, use hash table of approx. `n' entries.
+ * HASH_CONSERVE_SPACE Use as little space as possible.
* HASH_FN_BITS=n The hash function gives only `n' significant bits.
* HASH_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
- * HASH_USE_POOL=pool Allocate all nodes from given mempool.
- * Collides with delete/remove functions.
+ * HASH_USE_POOL=pool Allocate all nodes from given mempool. Note, however, that
+ * deallocation is not supported by mempools, so delete/remove
+ * will leak pool memory.
+ * HASH_AUTO_POOL=size Create a pool of the given block size automatically.
+ * HASH_PARAM_POOL Allocate all nodes from mempool given as a parameter to init().
+ * HASH_ZERO_FILL New entries should be initialized to all zeroes.
+ * HASH_TABLE_ALLOC The hash table itself will be allocated and freed using
+ * the same allocation functions as the nodes instead of
+ * the default xmalloc().
+ * HASH_TABLE_DYNAMIC Support multiple hash tables; the first parameter of all
+ * hash table operations is struct HASH_PREFIX(table) *.
*
* You also get a iterator macro at no extra charge:
*
* }
* HASH_END_FOR;
*
+ * (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
+ *
* Then include "lib/hashtable.h" and voila, you have a hash table
* suiting all your needs (at least those which you've revealed :) ).
*
* undef'd.
*/
-#ifndef _SHERLOCK_HASHFUNC_H
+#ifndef _UCW_HASHFUNC_H
#include "lib/hashfunc.h"
#endif
#include <string.h>
+/* Initial setup of parameters */
+
#if !defined(HASH_NODE) || !defined(HASH_PREFIX)
#error Some of the mandatory configuration macros are missing.
#endif
+#if defined(HASH_KEY_ATOMIC) && !defined(HASH_CONSERVE_SPACE)
+#define HASH_CONSERVE_SPACE
+#endif
+
#define P(x) HASH_PREFIX(x)
/* Declare buckets and the hash table */
uns hash_size;
uns hash_count, hash_max, hash_min, hash_hard_max;
P(bucket) **ht;
-} P(table);
-
+#if defined(HASH_AUTO_POOL) || defined(HASH_PARAM_POOL)
+ struct mempool *pool;
+#endif
+};
+
+#ifdef HASH_TABLE_DYNAMIC
+#define T (*table)
+#define TA struct P(table) *table
+#define TAC TA,
+#define TAU TA UNUSED
+#define TAUC TA UNUSED,
+#define TT table
+#define TTC table,
+#else
+struct P(table) P(table);
#define T P(table)
+#define TA void
+#define TAC
+#define TAU void
+#define TAUC
+#define TT
+#define TTC
+#endif
/* Preset parameters */
#ifndef HASH_GIVE_HASHFN
# define HASH_GIVE_HASHFN
- static inline int P(hash) (HASH_ATOMIC_TYPE x)
- { return hash_int(x); }
+ static inline int P(hash) (TAUC HASH_ATOMIC_TYPE x)
+ { return ((sizeof(x) <= 4) ? hash_u32(x) : hash_u64(x)); }
#endif
#ifndef HASH_GIVE_EQ
# define HASH_GIVE_EQ
- static inline int P(eq) (HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
+ static inline int P(eq) (TAUC HASH_ATOMIC_TYPE x, HASH_ATOMIC_TYPE y)
{ return x == y; }
#endif
#ifndef HASH_GIVE_INIT_KEY
# define HASH_GIVE_INIT_KEY
- static inline void P(init_key) (P(node) *n, HASH_ATOMIC_TYPE k)
+ static inline void P(init_key) (TAUC P(node) *n, HASH_ATOMIC_TYPE k)
{ HASH_KEY(n->) = k; }
#endif
-#ifndef HASH_CONSERVE_SPACE
-#define HASH_CONSERVE_SPACE
+#elif defined(HASH_KEY_MEMORY)
+
+#define HASH_KEY(x) x HASH_KEY_MEMORY
+
+#define HASH_KEY_DECL byte HASH_KEY( )[HASH_KEY_SIZE]
+
+#ifndef HASH_GIVE_HASHFN
+# define HASH_GIVE_HASHFN
+ static inline int P(hash) (TAUC byte *x)
+ { return hash_block(x, HASH_KEY_SIZE); }
+#endif
+
+#ifndef HASH_GIVE_EQ
+# define HASH_GIVE_EQ
+ static inline int P(eq) (TAUC byte *x, byte *y)
+ { return !memcmp(x, y, HASH_KEY_SIZE); }
+#endif
+
+#ifndef HASH_GIVE_INIT_KEY
+# define HASH_GIVE_INIT_KEY
+ static inline void P(init_key) (TAUC P(node) *n, byte *k)
+ { memcpy(HASH_KEY(n->), k, HASH_KEY_SIZE); }
#endif
#elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
# define HASH_KEY(x) x HASH_KEY_STRING
# ifndef HASH_GIVE_INIT_KEY
# define HASH_GIVE_INIT_KEY
- static inline void P(init_key) (P(node) *n, char *k)
+ static inline void P(init_key) (TAUC P(node) *n, char *k)
{ HASH_KEY(n->) = k; }
# endif
#else
# define HASH_KEY(x) x HASH_KEY_ENDSTRING
# define HASH_GIVE_EXTRA_SIZE
- static inline int P(extra_size) (char *k)
+ static inline int P(extra_size) (TAUC char *k)
{ return strlen(k); }
# ifndef HASH_GIVE_INIT_KEY
# define HASH_GIVE_INIT_KEY
- static inline void P(init_key) (P(node) *n, char *k)
+ static inline void P(init_key) (TAUC P(node) *n, char *k)
{ strcpy(HASH_KEY(n->), k); }
# endif
#endif
#ifndef HASH_GIVE_HASHFN
#define HASH_GIVE_HASHFN
- static inline uns P(hash) (char *k)
+ static inline uns P(hash) (TAUC char *k)
{
# ifdef HASH_NOCASE
return hash_string_nocase(k);
#ifndef HASH_GIVE_EQ
# define HASH_GIVE_EQ
- static inline int P(eq) (char *x, char *y)
+ static inline int P(eq) (TAUC char *x, char *y)
{
# ifdef HASH_NOCASE
return !strcasecmp(x,y);
#ifdef HASH_GIVE_EXTRA_SIZE
/* This trickery is needed to avoid `unused parameter' warnings */
-#define HASH_EXTRA_SIZE P(extra_size)
+#define HASH_EXTRA_SIZE(x) P(extra_size)(TTC x)
#else
/*
* Beware, C macros are expanded iteratively, not recursively,
#endif
#ifndef HASH_GIVE_INIT_DATA
-static inline void P(init_data) (P(node) *n UNUSED)
+static inline void P(init_data) (TAUC P(node) *n UNUSED)
{
}
#endif
-#include <stdlib.h>
-
-#ifndef HASH_GIVE_ALLOC
-#ifdef HASH_USE_POOL
-
-static inline void * P(alloc) (unsigned int size)
-{ return mp_alloc_fast(HASH_USE_POOL, size); }
+#ifdef HASH_GIVE_ALLOC
+/* If the caller has requested to use his own allocation functions, do so */
+static inline void P(init_alloc) (TAU) { }
+static inline void P(cleanup_alloc) (TAU) { }
+
+#elif defined(HASH_USE_POOL)
+/* If the caller has requested to use his mempool, do so */
+#include "lib/mempool.h"
+static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
+static inline void P(free) (TAUC void *x UNUSED) { }
+static inline void P(init_alloc) (TAU) { }
+static inline void P(cleanup_alloc) (TAU) { }
+
+#elif defined(HASH_PARAM_POOL)
+/* Use mempools given as a parameter to init() */
+#include "lib/mempool.h"
+static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); }
+static inline void P(free) (TAUC void *x UNUSED) { }
+static inline void P(init_alloc) (TAU) { }
+static inline void P(cleanup_alloc) (TAU) { }
+#define HASH_USE_POOL
+
+#elif defined(HASH_AUTO_POOL)
+/* Use our own pools */
+#include "lib/mempool.h"
+static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(T.pool, size); }
+static inline void P(free) (TAUC void *x UNUSED) { }
+static inline void P(init_alloc) (TAU) { T.pool = mp_new(HASH_AUTO_POOL); }
+static inline void P(cleanup_alloc) (TAU) { mp_delete(T.pool); }
+#define HASH_USE_POOL
#else
-
-static inline void * P(alloc) (unsigned int size)
-{ return xmalloc(size); }
-
-static inline void P(free) (void *x)
-{ xfree(x); }
+/* The default allocation method */
+static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
+static inline void P(free) (TAUC void *x) { xfree(x); }
+static inline void P(init_alloc) (TAU) { }
+static inline void P(cleanup_alloc) (TAU) { }
#endif
+
+#ifdef HASH_TABLE_ALLOC
+static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(size); }
+static inline void P(table_free) (TAUC void *x) { P(free)(x); }
+#else
+static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(size); }
+static inline void P(table_free) (TAUC void *x) { xfree(x); }
#endif
#ifndef HASH_DEFAULT_SIZE
#define HASH_FN_BITS 32
#endif
+#ifdef HASH_ZERO_FILL
+static inline void * P(new_bucket)(TAUC uns size)
+{
+ byte *buck = P(alloc)(TTC size);
+ bzero(buck, size);
+ return buck;
+}
+#else
+static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
+#endif
+
/* Now the operations */
-static void P(alloc_table) (void)
+static void P(alloc_table) (TAU)
{
- T.hash_size = nextprime(T.hash_size);
- T.ht = xmalloc(sizeof(void *) * T.hash_size);
+ T.hash_size = next_table_prime(T.hash_size);
+ T.ht = P(table_alloc)(TTC sizeof(void *) * T.hash_size);
bzero(T.ht, sizeof(void *) * T.hash_size);
if (2*T.hash_size < T.hash_hard_max)
T.hash_max = 2*T.hash_size;
T.hash_min = 0;
}
-static void P(init) (void)
+#ifndef HASH_PARAM_POOL
+static void P(init) (TA)
+#else
+static void P(init) (TAC struct mempool *pool)
+#endif
{
T.hash_count = 0;
T.hash_size = HASH_DEFAULT_SIZE;
#else
T.hash_hard_max = 1 << 28;
#endif
- P(alloc_table)();
+ P(alloc_table)(TT);
+#ifdef HASH_PARAM_POOL
+ T.pool = pool;
+#endif
+ P(init_alloc)(TT);
}
#ifdef HASH_WANT_CLEANUP
-static void P(cleanup) (void)
+static void P(cleanup) (TA)
{
#ifndef HASH_USE_POOL
uns i;
for (b=T.ht[i]; b; b=bb)
{
bb = b->next;
- P(free)(b);
+ P(free)(TTC b);
}
#endif
- xfree(T.ht);
+ P(cleanup_alloc)(TT);
+ P(table_free)(TTC T.ht);
}
#endif
-static inline uns P(bucket_hash) (P(bucket) *b)
+static inline uns P(bucket_hash) (TAUC P(bucket) *b)
{
#ifdef HASH_CONSERVE_SPACE
- return P(hash)(HASH_KEY(b->n.));
+ return P(hash)(TTC HASH_KEY(b->n.));
#else
return b->hash;
#endif
}
-static void P(rehash) (uns size)
+static void P(rehash) (TAC uns size)
{
P(bucket) *b, *nb;
P(bucket) **oldt = T.ht, **newt;
uns oldsize = T.hash_size;
uns i, h;
- // log(L_DEBUG, "Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
+ DBG("Rehashing %d->%d at count %d", oldsize, size, T.hash_count);
T.hash_size = size;
- P(alloc_table)();
+ P(alloc_table)(TT);
newt = T.ht;
for (i=0; i<oldsize; i++)
{
while (b)
{
nb = b->next;
- h = P(bucket_hash)(b) % T.hash_size;
+ h = P(bucket_hash)(TTC b) % T.hash_size;
b->next = newt[h];
newt[h] = b;
b = nb;
}
}
- xfree(oldt);
+ P(table_free)(TTC oldt);
}
#ifdef HASH_WANT_FIND
-static P(node) * P(find) (HASH_KEY_DECL)
+static P(node) * P(find) (TAC HASH_KEY_DECL)
{
- uns h0 = P(hash) (HASH_KEY( ));
+ uns h0 = P(hash) (TTC HASH_KEY( ));
uns h = h0 % T.hash_size;
P(bucket) *b;
#ifndef HASH_CONSERVE_SPACE
b->hash == h0 &&
#endif
- P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
+ P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
return &b->n;
}
return NULL;
#endif
#ifdef HASH_WANT_FIND_NEXT
-static P(node) * P(find_next) (P(node) *start)
+static P(node) * P(find_next) (TAC P(node) *start)
{
#ifndef HASH_CONSERVE_SPACE
- uns h0 = P(hash) (HASH_KEY(start->));
+ uns h0 = P(hash) (TTC HASH_KEY(start->));
#endif
P(bucket) *b = SKIP_BACK(P(bucket), n, start);
#ifndef HASH_CONSERVE_SPACE
b->hash == h0 &&
#endif
- P(eq)(HASH_KEY(start->), HASH_KEY(b->n.)))
+ P(eq)(TTC HASH_KEY(start->), HASH_KEY(b->n.)))
return &b->n;
}
return NULL;
#endif
#ifdef HASH_WANT_NEW
-static P(node) * P(new) (HASH_KEY_DECL)
+static P(node) * P(new) (TAC HASH_KEY_DECL)
{
uns h0, h;
P(bucket) *b;
- h0 = P(hash) (HASH_KEY( ));
+ h0 = P(hash) (TTC HASH_KEY( ));
h = h0 % T.hash_size;
- b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
+ b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
b->next = T.ht[h];
T.ht[h] = b;
#ifndef HASH_CONSERVE_SPACE
b->hash = h0;
#endif
- P(init_key)(&b->n, HASH_KEY( ));
- P(init_data)(&b->n);
+ P(init_key)(TTC &b->n, HASH_KEY( ));
+ P(init_data)(TTC &b->n);
if (T.hash_count++ >= T.hash_max)
- P(rehash)(2*T.hash_size);
+ P(rehash)(TTC 2*T.hash_size);
return &b->n;
}
#endif
#ifdef HASH_WANT_LOOKUP
-static P(node) * P(lookup) (HASH_KEY_DECL)
+static P(node) * P(lookup) (TAC HASH_KEY_DECL)
{
- uns h0 = P(hash) (HASH_KEY( ));
+ uns h0 = P(hash) (TTC HASH_KEY( ));
uns h = h0 % T.hash_size;
P(bucket) *b;
#ifndef HASH_CONSERVE_SPACE
b->hash == h0 &&
#endif
- P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
+ P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
return &b->n;
}
- b = P(alloc) (sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
+ b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( )));
b->next = T.ht[h];
T.ht[h] = b;
#ifndef HASH_CONSERVE_SPACE
b->hash = h0;
#endif
- P(init_key)(&b->n, HASH_KEY( ));
- P(init_data)(&b->n);
+ P(init_key)(TTC &b->n, HASH_KEY( ));
+ P(init_data)(TTC &b->n);
if (T.hash_count++ >= T.hash_max)
- P(rehash)(2*T.hash_size);
+ P(rehash)(TTC 2*T.hash_size);
return &b->n;
}
#endif
#ifdef HASH_WANT_DELETE
-static int P(delete) (HASH_KEY_DECL)
+static int P(delete) (TAC HASH_KEY_DECL)
{
- uns h0 = P(hash) (HASH_KEY( ));
+ uns h0 = P(hash) (TTC HASH_KEY( ));
uns h = h0 % T.hash_size;
P(bucket) *b, **bb;
#ifndef HASH_CONSERVE_SPACE
b->hash == h0 &&
#endif
- P(eq)(HASH_KEY( ), HASH_KEY(b->n.)))
+ P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.)))
{
*bb = b->next;
- P(free)(b);
+ P(free)(TTC b);
if (--T.hash_count < T.hash_min)
- P(rehash)(T.hash_size/2);
+ P(rehash)(TTC T.hash_size/2);
return 1;
}
}
#endif
#ifdef HASH_WANT_REMOVE
-static void P(remove) (P(node) *n)
+static void P(remove) (TAC P(node) *n)
{
P(bucket) *x = SKIP_BACK(struct P(bucket), n, n);
- uns h0 = P(bucket_hash)(x);
+ uns h0 = P(bucket_hash)(TTC x);
uns h = h0 % T.hash_size;
P(bucket) *b, **bb;
;
ASSERT(b);
*bb = b->next;
- P(free)(b);
+ P(free)(TTC b);
if (--T.hash_count < T.hash_min)
- P(rehash)(T.hash_size/2);
+ P(rehash)(TTC T.hash_size/2);
}
#endif
#ifndef HASH_FOR_ALL
-#define HASH_FOR_ALL(h_px, h_var) \
+#define HASH_FOR_ALL_DYNAMIC(h_px, h_table, h_var) \
do { \
uns h_slot; \
- struct HASH_GLUE(h_px,bucket) *h_buck; \
- for (h_slot=0; h_slot < HASH_GLUE(h_px,table).hash_size; h_slot++) \
- for (h_buck = HASH_GLUE(h_px,table).ht[h_slot]; h_buck; h_buck = h_buck->next) \
+ struct GLUE_(h_px,bucket) *h_buck; \
+ for (h_slot=0; h_slot < (h_table)->hash_size; h_slot++) \
+ for (h_buck = (h_table)->ht[h_slot]; h_buck; h_buck = h_buck->next) \
{ \
- HASH_GLUE(h_px,node) *h_var = &h_buck->n;
+ GLUE_(h_px,node) *h_var = &h_buck->n;
+#define HASH_FOR_ALL(h_px, h_var) HASH_FOR_ALL_DYNAMIC(h_px, &GLUE_(h_px,table), h_var)
#define HASH_END_FOR } } while(0)
#define HASH_BREAK
#define HASH_CONTINUE continue
-#define HASH_GLUE(x,y) x##_##y
#endif
#undef P
#undef T
+#undef TA
+#undef TAC
+#undef TAU
+#undef TAUC
+#undef TT
+#undef TTC
#undef HASH_ATOMIC_TYPE
#undef HASH_CONSERVE_SPACE
#undef HASH_NODE
#undef HASH_PREFIX
#undef HASH_USE_POOL
+#undef HASH_AUTO_POOL
+#undef HASH_PARAM_POOL
#undef HASH_WANT_CLEANUP
#undef HASH_WANT_DELETE
#undef HASH_WANT_FIND
#undef HASH_WANT_LOOKUP
#undef HASH_WANT_NEW
#undef HASH_WANT_REMOVE
+#undef HASH_TABLE_ALLOC
+#undef HASH_TABLE_DYNAMIC
+#undef HASH_ZERO_FILL
projects / libucw.git / blobdiff