X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fhashtable.h;h=1c40ea9d6729f3f7b61a75838fd9015d5e5852f1;hb=0d56b467cc2184f00a4e390f95596704d819dfa3;hp=17b6d08e1799d43a7ced814da9653e9b37215e2d;hpb=4a220521e7b46263b156a6c784856a996997df76;p=libucw.git

diff --git a/lib/hashtable.h b/lib/hashtable.h
index 17b6d08e..1c40ea9d 100644
--- a/lib/hashtable.h
+++ b/lib/hashtable.h
@@ -1,7 +1,11 @@
 /*
  *	Sherlock Library -- Universal Hash Table
  *
- *	(c) 2002 Martin Mares <mj@ucw.cz>
+ *	(c) 2002--2004 Martin Mares <mj@ucw.cz>
+ *	(c) 2002 Robert Spalek <robert@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
  */
 
 /*
@@ -41,8 +45,10 @@
  *
  *  <always defined>	init() -- initialize the hash table.
  *  HASH_WANT_CLEANUP	cleanup() -- deallocate the hash table.
- *  HASH_WANT_FIND	node *find(key) -- find node with the specified
+ *  HASH_WANT_FIND	node *find(key) -- find first node with the specified
  *			key, return NULL if no such node exists.
+ *  HASH_WANT_FIND_NEXT	node *find(node *start) -- find next node with the
+ *			specified key, return NULL if no such node exists.
  *  HASH_WANT_NEW	node *new(key) -- create new node with given key.
  *			Doesn't check whether it already exists.
  *  HASH_WANT_LOOKUP	node *lookup(key) -- find node with given key,
@@ -82,6 +88,7 @@
  *  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_AUTO_POOL=size	Create a pool of the given block size automatically.
  *
  *  You also get a iterator macro at no extra charge:
  *
@@ -94,7 +101,7 @@
  *    }
  *  HASH_END_FOR;
  *
- *  Then include <lib/hashtable.h> and voila, you have a hash table
+ *  Then include "lib/hashtable.h" and voila, you have a hash table
  *  suiting all your needs (at least those which you've revealed :) ).
  *
  *  After including this file, all parameter macros are automatically
@@ -254,21 +261,33 @@ static inline void P(init_data) (P(node) *n UNUSED)
 
 #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) (void) { }
+static inline void P(cleanup_alloc) (void) { }
+
+#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) (unsigned int size) { return mp_alloc_fast(HASH_USE_POOL, size); }
+static inline void P(init_alloc) (void) { }
+static inline void P(cleanup_alloc) (void) { }
+
+#elif defined(HASH_AUTO_POOL)
+/* Use our own pools */
+#include "lib/mempool.h"
+static struct mempool *P(pool);
+static inline void * P(alloc) (unsigned int size) { return mp_alloc_fast(P(pool), size); }
+static inline void P(init_alloc) (void) { P(pool) = mp_new(HASH_AUTO_POOL); }
+static inline void P(cleanup_alloc) (void) { mp_delete(P(pool)); }
 
 #else
+/* The default allocation method */
+static inline void * P(alloc) (unsigned int size) { return xmalloc(size); }
+static inline void P(free) (void *x) { xfree(x); }
+static inline void P(init_alloc) (void) { }
+static inline void P(cleanup_alloc) (void) { }
 
-static inline void * P(alloc) (unsigned int size)
-{ return xmalloc(size); }
-
-static inline void P(free) (void *x)
-{ xfree(x); }
-
-#endif
 #endif
 
 #ifndef HASH_DEFAULT_SIZE
@@ -306,6 +325,7 @@ static void P(init) (void)
   T.hash_hard_max = 1 << 28;
 #endif
   P(alloc_table)();
+  P(init_alloc)();
 }
 
 #ifdef HASH_WANT_CLEANUP
@@ -322,6 +342,7 @@ static void P(cleanup) (void)
 	P(free)(b);
       }
 #endif
+  P(cleanup_alloc)();
   xfree(T.ht);
 }
 #endif
@@ -381,6 +402,27 @@ static P(node) * P(find) (HASH_KEY_DECL)
 }
 #endif
 
+#ifdef HASH_WANT_FIND_NEXT
+static P(node) * P(find_next) (P(node) *start)
+{
+#ifndef HASH_CONSERVE_SPACE
+  uns h0 = P(hash) (HASH_KEY(start->));
+#endif
+  P(bucket) *b = SKIP_BACK(P(bucket), n, start);
+
+  for (b=b->next; b; b=b->next)
+    {
+      if (
+#ifndef HASH_CONSERVE_SPACE
+	  b->hash == h0 &&
+#endif
+	  P(eq)(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)
 {
@@ -485,15 +527,14 @@ static void P(remove) (P(node) *n)
 #define HASH_FOR_ALL(h_px, 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 < GLUE_(h_px,table).hash_size; h_slot++)			\
+    for (h_buck = GLUE_(h_px,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_END_FOR } } while(0)
 #define HASH_BREAK 
 #define HASH_CONTINUE continue
-#define HASH_GLUE(x,y) x##_##y
 
 #endif
 
@@ -523,9 +564,11 @@ do {											\
 #undef HASH_NODE
 #undef HASH_PREFIX
 #undef HASH_USE_POOL
+#undef HASH_AUTO_POOL
 #undef HASH_WANT_CLEANUP
 #undef HASH_WANT_DELETE
 #undef HASH_WANT_FIND
+#undef HASH_WANT_FIND_NEXT
 #undef HASH_WANT_LOOKUP
 #undef HASH_WANT_NEW
 #undef HASH_WANT_REMOVE