strtonum: Added small bits of documentation

[libucw.git] / ucw / hashtable.h

diff --git a/ucw/hashtable.h b/ucw/hashtable.h
index 88fd0977f400fbccd2f326cb1c6d42970bfeab26..8dff51c2d5a9f6450cebfdfa99a855d77337e2d6 100644 (file)
--- a/ucw/hashtable.h
+++ b/ucw/hashtable.h
@@ -3,6 +3,7 @@
  *
  *     (c) 2002--2004 Martin Mares <mj@ucw.cz>
  *     (c) 2002--2005 Robert Spalek <robert@ucw.cz>
  *
  *     (c) 2002--2004 Martin Mares <mj@ucw.cz>
  *     (c) 2002--2005 Robert Spalek <robert@ucw.cz>

+ *     (c) 2010 Pavel Charvat <pchar@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.


@@ -79,8 +80,11 @@
  *                     newly created node. Very useful for lookup operations.
  *  HASH_GIVE_ALLOC    void *alloc(unsigned int size) -- allocate space for
  *                     a node. Default is xmalloc() or pooled allocation, depending
  *                     newly created node. Very useful for lookup operations.
  *  HASH_GIVE_ALLOC    void *alloc(unsigned int size) -- allocate space for
  *                     a node. Default is xmalloc() or pooled allocation, depending

- *                     on HASH_USE_POOL and HASH_AUTO_POOL switches.
- *                     void free(void *) -- the converse.
+ *                     on HASH_USE_POOL, HASH_AUTO_POOL, HASH_USE_ELTPOOL
+ *                     and HASH_AUTO_ELTPOOL switches. void free(void *) -- the converse.
+ * HASH_GIVE_TABLE_ALLOC void *table_alloc(unsigned int size), void *table_free(void *)
+ *                     Allocate or free space for the table itself. Default is xmalloc()
+ *                     or the functions defined by HASH_GIVE_ALLOC if HASH_TABLE_ALLOC is set.

  *
  *  ... and a couple of extra parameters:
  *
  *
  *  ... and a couple of extra parameters:
  *


@@ -93,12 +97,16 @@
  *                     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_USE_ELTPOOL=pool Allocate all nodes from given eltpool.
+ *  HASH_AUTO_ELTPOOL=count Create an eltpool of the given number of elements in each chunk.

  *  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_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_GROWING Never decrease the size of the hash table itself

  *  HASH_TABLE_DYNAMIC Support multiple hash tables; the first parameter of all
  *                     hash table operations is struct HASH_PREFIX(table) *.
  *  HASH_TABLE_DYNAMIC Support multiple hash tables; the first parameter of all
  *                     hash table operations is struct HASH_PREFIX(table) *.

+ *  HASH_TABLE_VARS    Extra variables to be defined in table structure

  *
  *  You also get a iterator macro at no extra charge:
  *
  *
  *  You also get a iterator macro at no extra charge:
  *


@@ -113,7 +121,7 @@
  *
  *  (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
  *
  *
  *  (For dynamic tables, use HASH_FOR_ALL_DYNAMIC(hash_prefix, hash_table, variable) instead.)
  *

- *  Then include "ucw/hashtable.h" and voila, you have a hash table
+ *  Then include <ucw/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
  *  suiting all your needs (at least those which you've revealed :) ).
  *
  *  After including this file, all parameter macros are automatically


@@ -121,10 +129,10 @@
  */
 
 #ifndef _UCW_HASHFUNC_H
  */
 
 #ifndef _UCW_HASHFUNC_H

-#include "ucw/hashfunc.h"
+#include <ucw/hashfunc.h>

 #endif
 
 #endif
 

-#include "ucw/prime.h"
+#include <ucw/prime.h>

 
 #include <string.h>
 
 
 #include <string.h>
 


@@ -153,12 +161,18 @@ typedef struct P(bucket) {
 } P(bucket);
 
 struct P(table) {
 } P(bucket);
 
 struct P(table) {

+#ifdef HASH_TABLE_VARS
+  HASH_TABLE_VARS
+#endif

   uns hash_size;
   uns hash_count, hash_max, hash_min, hash_hard_max;
   P(bucket) **ht;
 #ifdef HASH_AUTO_POOL
   struct mempool *pool;
 #endif
   uns hash_size;
   uns hash_count, hash_max, hash_min, hash_hard_max;
   P(bucket) **ht;
 #ifdef HASH_AUTO_POOL
   struct mempool *pool;
 #endif

+#ifdef HASH_AUTO_ELTPOOL
+  struct eltpool *eltpool;
+#endif

 };
 
 #ifdef HASH_TABLE_DYNAMIC
 };
 
 #ifdef HASH_TABLE_DYNAMIC


@@ -326,7 +340,7 @@ static inline void P(cleanup_alloc) (TAU) { }
 
 #elif defined(HASH_USE_POOL)
 /* If the caller has requested to use his mempool, do so */
 
 #elif defined(HASH_USE_POOL)
 /* If the caller has requested to use his mempool, do so */

-#include "ucw/mempool.h"
+#include <ucw/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(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) { }


@@ -334,13 +348,30 @@ static inline void P(cleanup_alloc) (TAU) { }
 
 #elif defined(HASH_AUTO_POOL)
 /* Use our own pools */
 
 #elif defined(HASH_AUTO_POOL)
 /* Use our own pools */

-#include "ucw/mempool.h"
+#include <ucw/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
 
 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
 

+#elif defined(HASH_USE_ELTPOOL)
+/* If the caller has requested to use his eltpool, do so */
+#include <ucw/eltpool.h>
+static inline void * P(alloc) (TAUC unsigned int size UNUSED) { ASSERT(size <= (HASH_USE_ELTPOOL)->elt_size); return ep_alloc(HASH_USE_ELTPOOL); }
+static inline void P(free) (TAUC void *x) { ep_free(HASH_USE_ELTPOOL, x); }
+static inline void P(init_alloc) (TAU) { }
+static inline void P(cleanup_alloc) (TAU) { }
+
+#elif defined(HASH_AUTO_ELTPOOL)
+/* Use our own eltpools */
+#include <ucw/eltpool.h>
+static inline void * P(alloc) (TAUC unsigned int size UNUSED) { return ep_alloc(T.eltpool); }
+static inline void P(free) (TAUC void *x) { ep_free(T.eltpool, x); }
+static inline void P(init_alloc) (TAU) { T.eltpool = ep_new(sizeof(P(bucket)), HASH_AUTO_ELTPOOL); }
+static inline void P(cleanup_alloc) (TAU) { ep_delete(T.eltpool); }
+#define HASH_USE_ELTPOOL
+

 #else
 /* The default allocation method */
 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }
 #else
 /* The default allocation method */
 static inline void * P(alloc) (TAUC unsigned int size) { return xmalloc(size); }


@@ -350,7 +381,16 @@ static inline void P(cleanup_alloc) (TAU) { }
 
 #endif
 
 
 #endif
 

-#ifdef HASH_TABLE_ALLOC
+#if defined(HASH_USE_ELTPOOL) && defined(HASH_GIVE_EXTRA_SIZE)
+#error Eltpools not supported in combination with variable-sized nodes
+#endif
+
+#ifdef HASH_GIVE_TABLE_ALLOC
+/* If the caller has requested to use his own allocation functions, do so */
+#elif defined(HASH_TABLE_ALLOC)
+#ifdef HASH_USE_ELTPOOL
+#error HASH_TABLE_ALLOC not supported in combination with eltpools
+#endif

 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(TTC size); }
 static inline void P(table_free) (TAUC void *x) { P(free)(TTC x); }
 #else
 static inline void * P(table_alloc) (TAUC unsigned int size) { return P(alloc)(TTC size); }
 static inline void P(table_free) (TAUC void *x) { P(free)(TTC x); }
 #else


@@ -358,6 +398,10 @@ static inline void * P(table_alloc) (TAUC unsigned int size) { return xmalloc(si
 static inline void P(table_free) (TAUC void *x) { xfree(x); }
 #endif
 
 static inline void P(table_free) (TAUC void *x) { xfree(x); }
 #endif
 

+#if defined(HASH_USE_POOL) && defined(HASH_TABLE_ALLOC) && !defined(HASH_TABLE_GROWING)
+#define HASH_TABLE_GROWING
+#endif
+

 #ifndef HASH_DEFAULT_SIZE
 #define HASH_DEFAULT_SIZE 32
 #endif
 #ifndef HASH_DEFAULT_SIZE
 #define HASH_DEFAULT_SIZE 32
 #endif


@@ -388,9 +432,11 @@ static void P(alloc_table) (TAU)
     T.hash_max = 2*T.hash_size;
   else
     T.hash_max = ~0U;
     T.hash_max = 2*T.hash_size;
   else
     T.hash_max = ~0U;

+#ifndef HASH_TABLE_GROWING

   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
     T.hash_min = T.hash_size/4;
   else
   if (T.hash_size/2 > HASH_DEFAULT_SIZE)
     T.hash_min = T.hash_size/4;
   else

+#endif

     T.hash_min = 0;
 }
 
     T.hash_min = 0;
 }
 


@@ -609,8 +655,11 @@ static int HASH_PREFIX(delete)(TAC HASH_KEY_DECL)
        {
          *bb = b->next;
          P(free)(TTC b);
        {
          *bb = b->next;
          P(free)(TTC b);

-         if (--T.hash_count < T.hash_min)
+         T.hash_count--;
+#ifndef HASH_TABLE_GROWING
+         if (T.hash_count < T.hash_min)

            P(rehash)(TTC T.hash_size/2);
            P(rehash)(TTC T.hash_size/2);

+#endif

          return 1;
        }
     }
          return 1;
        }
     }


@@ -638,8 +687,11 @@ static void HASH_PREFIX(remove)(TAC HASH_NODE *n)
   ASSERT(b);
   *bb = b->next;
   P(free)(TTC b);
   ASSERT(b);
   *bb = b->next;
   P(free)(TTC b);

-  if (--T.hash_count < T.hash_min)
+  T.hash_count--;
+#ifndef HASH_TABLE_GROWING
+  if (T.hash_count < T.hash_min)

     P(rehash)(TTC T.hash_size/2);
     P(rehash)(TTC T.hash_size/2);

+#endif

 }
 #endif
 
 }
 #endif
 


@@ -679,6 +731,7 @@ do {                                                                                        \
 #undef HASH_EXTRA_SIZE
 #undef HASH_FN_BITS
 #undef HASH_GIVE_ALLOC
 #undef HASH_EXTRA_SIZE
 #undef HASH_FN_BITS
 #undef HASH_GIVE_ALLOC

+#undef HASH_GIVE_TABLE_ALLOC

 #undef HASH_GIVE_EQ
 #undef HASH_GIVE_EXTRA_SIZE
 #undef HASH_GIVE_HASHFN
 #undef HASH_GIVE_EQ
 #undef HASH_GIVE_EXTRA_SIZE
 #undef HASH_GIVE_HASHFN


@@ -697,6 +750,8 @@ 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_USE_ELTPOOL
+#undef HASH_AUTO_ELTPOOL

 #undef HASH_WANT_CLEANUP
 #undef HASH_WANT_DELETE
 #undef HASH_WANT_FIND
 #undef HASH_WANT_CLEANUP
 #undef HASH_WANT_DELETE
 #undef HASH_WANT_FIND


@@ -705,5 +760,7 @@ do {                                                                                        \
 #undef HASH_WANT_NEW
 #undef HASH_WANT_REMOVE
 #undef HASH_TABLE_ALLOC
 #undef HASH_WANT_NEW
 #undef HASH_WANT_REMOVE
 #undef HASH_TABLE_ALLOC

+#undef HASH_TABLE_GROWING

 #undef HASH_TABLE_DYNAMIC
 #undef HASH_TABLE_DYNAMIC

+#undef HASH_TABLE_VARS

 #undef HASH_ZERO_FILL
 #undef HASH_ZERO_FILL