X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=ucw%2Fhashtable.h;h=cabe1bc3b34f785355a97e6ffbe42277c51e278a;hb=5453cb799a65190b348028302249af928c58cee4;hp=622f071aa7a663151ab79bc5d3fee36d6268b7cb;hpb=5f81280e4ec7a5517e94f1c1f53e42fba537fbd8;p=libucw.git diff --git a/ucw/hashtable.h b/ucw/hashtable.h index 622f071a..cabe1bc3 100644 --- a/ucw/hashtable.h +++ b/ucw/hashtable.h @@ -4,6 +4,7 @@ * (c) 2002--2004 Martin Mares * (c) 2002--2005 Robert Spalek * (c) 2010 Pavel Charvat + * (c) 2012 Tomas Valla * * This software may be freely distributed and used according to the terms * of the GNU Lesser General Public License. @@ -58,6 +59,8 @@ * HASH_WANT_LOOKUP node *lookup(key) -- find node with given key, * if it doesn't exist, create it. Defining * HASH_GIVE_INIT_DATA is strongly recommended. + * Use HASH_LOOKUP_DETECT_NEW if you want to know + * whether the node was newly created or not. * HASH_WANT_DELETE int delete(key) -- delete and deallocate node * with given key. Returns success. * HASH_WANT_REMOVE remove(node *) -- delete and deallocate given node. @@ -82,7 +85,7 @@ * a node. Default is xmalloc() or pooled allocation, depending * 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 *) + * 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. * @@ -107,6 +110,10 @@ * 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 + * HASH_LOOKUP_DETECT_NEW + * the prototype for lookup is changed to node *lookup(key, int *new_item) + * new_item must not be NULL and returns 1 whether lookup + * just created a new item in the hashtable or 0 otherwise. * * You also get a iterator macro at no extra charge: * @@ -121,7 +128,7 @@ * * (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 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 @@ -129,10 +136,10 @@ */ #ifndef _UCW_HASHFUNC_H -#include "ucw/hashfunc.h" +#include #endif -#include "ucw/prime.h" +#include #include @@ -340,7 +347,7 @@ static inline void P(cleanup_alloc) (TAU) { } #elif defined(HASH_USE_POOL) /* If the caller has requested to use his mempool, do so */ -#include "ucw/mempool.h" +#include 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) { } @@ -348,7 +355,7 @@ static inline void P(cleanup_alloc) (TAU) { } #elif defined(HASH_AUTO_POOL) /* Use our own pools */ -#include "ucw/mempool.h" +#include 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); } @@ -357,7 +364,7 @@ static inline void P(cleanup_alloc) (TAU) { mp_delete(T.pool); } #elif defined(HASH_USE_ELTPOOL) /* If the caller has requested to use his eltpool, do so */ -#include "ucw/eltpool.h" +#include 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) { } @@ -365,7 +372,7 @@ static inline void P(cleanup_alloc) (TAU) { } #elif defined(HASH_AUTO_ELTPOOL) /* Use our own eltpools */ -#include "ucw/eltpool.h" +#include 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); } @@ -595,13 +602,18 @@ static HASH_NODE * HASH_PREFIX(new)(TAC HASH_KEY_DECL) #endif #ifdef HASH_WANT_LOOKUP +#ifdef HASH_LOOKUP_DETECT_NEW /** * Finds a node with a given key. If it does not exist, a new one is created. * It is strongly recommended to use <>. * * This one is enabled by the <> macro. + * The @new_item argument is available only if <> was given. **/ +static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL, int *new_item) +#else static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL) +#endif { uns h0 = P(hash) (TTC HASH_KEY( )); uns h = h0 % T.hash_size; @@ -613,8 +625,12 @@ static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL) #ifndef HASH_CONSERVE_SPACE b->hash == h0 && #endif - P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.))) + P(eq)(TTC HASH_KEY( ), HASH_KEY(b->n.))) { +#ifdef HASH_LOOKUP_DETECT_NEW + *new_item = 0; +#endif return &b->n; + } } b = P(new_bucket) (TTC sizeof(struct P(bucket)) + HASH_EXTRA_SIZE(HASH_KEY( ))); @@ -627,6 +643,9 @@ static HASH_NODE* HASH_PREFIX(lookup)(TAC HASH_KEY_DECL) P(init_data)(TTC &b->n); if (T.hash_count++ >= T.hash_max) P(rehash)(TTC 2*T.hash_size); +#ifdef HASH_LOOKUP_DETECT_NEW + *new_item = 1; +#endif return &b->n; } #endif @@ -764,3 +783,4 @@ do { \ #undef HASH_TABLE_DYNAMIC #undef HASH_TABLE_VARS #undef HASH_ZERO_FILL +#undef HASH_LOOKUP_DETECT_NEW