Try to merge recent changes in v3.9 to image branch...

[libucw.git] / lib / hashtable.h

diff --git a/lib/hashtable.h b/lib/hashtable.h
index 65931b6764895789c099ab4a114770e6549ebc0f..c96f0a61c687bd501cbbfe80d2e19ca2795426be 100644 (file)
--- a/lib/hashtable.h
+++ b/lib/hashtable.h
@@ -2,7 +2,7 @@
  *     UCW Library -- Universal Hash Table
  *
  *     (c) 2002--2004 Martin Mares <mj@ucw.cz>
  *     UCW Library -- Universal Hash Table
  *
  *     (c) 2002--2004 Martin Mares <mj@ucw.cz>

- *     (c) 2002 Robert Spalek <robert@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.
  *
  *     This software may be freely distributed and used according to the terms
  *     of the GNU Lesser General Public License.


@@ -39,6 +39,9 @@
  *                     That is, `type1 k1, type2 k2, ... typen kn'.
  *                     With complex keys, HASH_GIVE_HASHFN and HASH_GIVE_EQ
  *                     are mandatory.
  *                     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):
  *
  *  Then specify what operations you request (all names are automatically
  *  prefixed by calling HASH_PREFIX):


@@ -90,6 +93,7 @@
  *                     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.
  *                     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
  *  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


@@ -151,6 +155,9 @@ struct P(table) {
   uns hash_size;
   uns hash_count, hash_max, hash_min, hash_hard_max;
   P(bucket) **ht;
   uns hash_size;
   uns hash_count, hash_max, hash_min, hash_hard_max;
   P(bucket) **ht;

+#if defined(HASH_AUTO_POOL) || defined(HASH_PARAM_POOL)
+  struct mempool *pool;
+#endif

 };
 
 #ifdef HASH_TABLE_DYNAMIC
 };
 
 #ifdef HASH_TABLE_DYNAMIC


@@ -201,6 +208,30 @@ struct P(table) P(table);
    { HASH_KEY(n->) = k; }
 #endif
 
    { HASH_KEY(n->) = k; }
 #endif
 

+#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)
 
 #ifdef HASH_KEY_STRING
 #elif defined(HASH_KEY_STRING) || defined(HASH_KEY_ENDSTRING)
 
 #ifdef HASH_KEY_STRING


@@ -287,8 +318,6 @@ static inline void P(init_data) (TAUC P(node) *n UNUSED)
 }
 #endif
 
 }
 #endif
 

-#include <stdlib.h>
-

 #ifdef HASH_GIVE_ALLOC
 /* If the caller has requested to use his own allocation functions, do so */
 static inline void P(init_alloc) (TAU) { }
 #ifdef HASH_GIVE_ALLOC
 /* If the caller has requested to use his own allocation functions, do so */
 static inline void P(init_alloc) (TAU) { }


@@ -302,14 +331,23 @@ static inline void P(free) (TAUC void *x UNUSED) { }
 static inline void P(init_alloc) (TAU) { }
 static inline void P(cleanup_alloc) (TAU) { }
 
 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"
 #elif defined(HASH_AUTO_POOL)
 /* Use our own pools */
 #include "lib/mempool.h"

-static struct mempool *P(pool);
-static inline void * P(alloc) (TAUC unsigned int size) { return mp_alloc_fast(P(pool), size); }
+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(free) (TAUC void *x UNUSED) { }

-static inline void P(init_alloc) (TAU) { P(pool) = mp_new(HASH_AUTO_POOL); }
-static inline void P(cleanup_alloc) (TAU) { mp_delete(P(pool)); }
+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
 /* The default allocation method */
 
 #else
 /* The default allocation method */


@@ -351,7 +389,7 @@ static inline void * P(new_bucket)(TAUC uns size) { return P(alloc)(TTC size); }
 
 static void P(alloc_table) (TAU)
 {
 
 static void P(alloc_table) (TAU)
 {

-  T.hash_size = nextprime(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.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)


@@ -364,7 +402,11 @@ static void P(alloc_table) (TAU)
     T.hash_min = 0;
 }
 
     T.hash_min = 0;
 }
 

+#ifndef HASH_PARAM_POOL

 static void P(init) (TA)
 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;
 {
   T.hash_count = 0;
   T.hash_size = HASH_DEFAULT_SIZE;


@@ -374,6 +416,9 @@ static void P(init) (TA)
   T.hash_hard_max = 1 << 28;
 #endif
   P(alloc_table)(TT);
   T.hash_hard_max = 1 << 28;
 #endif
   P(alloc_table)(TT);

+#ifdef HASH_PARAM_POOL
+  T.pool = pool;
+#endif

   P(init_alloc)(TT);
 }
 
   P(init_alloc)(TT);
 }
 


@@ -621,6 +666,7 @@ do {                                                                                        \
 #undef HASH_PREFIX
 #undef HASH_USE_POOL
 #undef HASH_AUTO_POOL
 #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_CLEANUP
 #undef HASH_WANT_DELETE
 #undef HASH_WANT_FIND