Hash table that is implemented as bucket hash table. More...

Collaboration diagram for HASH:

Classes
struct	HASH
Defines
#define	HASH_BUCKET_FOREACH(cur, bucket)
#define	HASH_FOREACH_KEY(cur, hash, key, key_size)
	Macro: iterate over all elements that match a given key (multimap)
#define	HASH_DELETEALL_KEY(cur, hash, key, key_size)
	Macro: unlink al entries that match a given key (for multimap); the user has to free the memory in loop code.
#define	HASH_DELETEALL_KEY_END
#define	HASH_FOREACH(cur, hash)
	Macro: iterate over all elements in hash table.
#define	HASH_FOREACH_END
	Macro: close block opened by HASH_FOREACH.
#define	HASH_DELETEALL(cur, hash)
	Macro: iterate over all elements in hash table and delete them from the table; allow the user to free the memory of each element.
#define	HASH_DELETEALL_END
	Macro: close block opened by HASH_DELETEALL.
Functions
int	HASH_init (HASH *hash, size_t buckets, int ismultimap, HASH_COMPARE_KEY compare_key, HASH_FUNCTION hash_func)
	Object constructor; initialise the hash that allows one entry for a given key.
int	HASH_resize (HASH *hash, size_t buckets)
	resize the hash table
M_INLINE void	HASH_free (HASH *hash)
	Object destructor; frees a hash table.
M_INLINE size_t	HASH_size (HASH *hash)
	returns number of elements in hash table
HASH_Entry *	HASH_find (HASH phash, void key, ssize_t key_size)
	find entry with given key in hash table; for multimaps this will return the first occurence of the key.
HASH_Entry *	HASH_find_next (HASH phash, HASH_Entry prev, void *key, ssize_t key_size)
	for multimaps - find next occurence of key
int	HASH_insert (HASH phash, HASH_Entry entry, void *key, ssize_t key_size)
	insert new entry in hash table
HASH_Entry *	HASH_unlink (HASH hash, void key, ssize_t key_size)
	find first hash table entry and unlink it from its bucket. The caller of this function has to free memory held by hash table entry.
M_INLINE void	HASH_foreach_key (HASH hash, void key, ssize_t key_size, HASH_VISITOR eval_func, void *context)
	iterate over all entries of the hash table that match a given key and invoke callback with those elements.
M_INLINE void	HASH_foreach (HASH hash, HASH_VISITOR eval_func, void context)
	iterate over all entries of the hash table and invoke callback with each element. Equivalent of Lisp foldl,mapcar and friends.
M_INLINE HASH_Entry *	HASH_findif (HASH hash, HASH_VISITOR eval_func, void context, int *retval)
	find an element within the hash. callback is invoked for each element of the list, when the callback returns non zero value the iteration stops as we have found what we searched for.
M_INLINE void	HASH_deleteall (HASH hash, int offset_of_link, HASH_VISITOR on_delete, void context)
	iterate over all entries of the hash table and delete them.
M_INLINE int	HASH_check (HASH *hash)
	check consistency of bucket hash structure.

Detailed Description

Hash table that is implemented as bucket hash table.

Element of has is an user defined entry which embeds HASH_Entry structure.

Define Documentation

#define HASH_BUCKET_FOREACH	(	cur,
		bucket
	)

Value:

for((cur) = (HASH_Entry *) ((bucket)->next);\
                (SRING *) (cur) != (bucket);\
                (cur) = (HASH_Entry *) (cur)->entry.next )

Definition at line 190 of file bhash.h.

#define HASH_DELETEALL	(	cur,
		hash
	)

Value:

{ \
        size_t HASH_delallforeach_i##cur = 0; \
        for(HASH_delallforeach_i##cur = 0; HASH_delallforeach_i##cur < (hash)->buckets_size; HASH_delallforeach_i##cur ++) \
        while( !SRING_isempty( &(hash)->buckets[ HASH_delallforeach_i##cur ]) ) { \
                (cur) = (HASH_Entry *) SRING_unlink_after( &(hash)->buckets[ HASH_delallforeach_i##cur ] );\
                (hash)->elmcount--;

Macro: iterate over all elements in hash table and delete them from the table; allow the user to free the memory of each element.

Parameters:

cur	(type HASH_Entry *)
hash	(type HASH *)

Definition at line 267 of file bhash.h.

#define HASH_DELETEALL_END

Value:

}\
}

Macro: close block opened by HASH_DELETEALL.

Definition at line 278 of file bhash.h.

#define HASH_DELETEALL_KEY	(	cur,
		hash,
		key,
		key_size
	)

Value:

{  \
        HASH_Entry * HASH_DELETEALL_KEY##next = (HASH_Entry *) 0xFFFFFFFF; \
        for( (cur) = HASH_unlink( (hash), (key), (key_size ) ) ; \
                 (cur) && (HASH_DELETEALL_KEY##next); \
                 (HASH_DELETEALL_KEY##next) =  HASH_find_next( (hash), (cur), (key), (key_size) ) ) { \
                 if ((HASH_DELETEALL_KEY##next) != (HASH_Entry *) 0xFFFFFFFF) { \
                         SRING_unlink_after( (SRING *) (cur) ); \
                         (hash)->elmcount--; \
                         (cur) = (HASH_DELETEALL_KEY##next); \
                 }

Macro: unlink al entries that match a given key (for multimap); the user has to free the memory in loop code.

Parameters:

cur	(type HASH_Entry *) current entry
hash	(type HASH *) the object
key	(type void *) the key
key_size	(type size_t) length of key

Definition at line 226 of file bhash.h.

#define HASH_DELETEALL_KEY_END

Value:

} \
}

Definition at line 238 of file bhash.h.

#define HASH_FOREACH	(	cur,
		hash
	)

Value:

{ \
        size_t HASH_foreach_i##cur = 0; \
        for(HASH_foreach_i##cur = 0; HASH_foreach_i##cur < (hash)->buckets_size; HASH_foreach_i##cur ++) \
                HASH_BUCKET_FOREACH( cur, &(hash)->buckets[ HASH_foreach_i##cur ] ) {

Macro: iterate over all elements in hash table.

Parameters:

cur	(type HASH_Entry *)
hash	(type HASH *)

Definition at line 248 of file bhash.h.

#define HASH_FOREACH_END

Value:

}\
}

Macro: close block opened by HASH_FOREACH.

Definition at line 258 of file bhash.h.

#define HASH_FOREACH_KEY	(	cur,
		hash,
		key,
		key_size
	)

Value:

for( (cur) = HASH_find( (hash), (key), (key_size ) ) ; \
                  (cur); \
                  (cur) =  HASH_find_next( (hash), (cur), (key), (key_size) ) )

Macro: iterate over all elements that match a given key (multimap)

Usage: HASH_Entry *cur;

HASH_FOREACH_KEY(cur,hash) { =do something with cur - don't delete it= }

Parameters:

cur	(type HASH_Entry *) current entry
hash	(type HASH *) the object
key	(type void *) the key
key_size	(type size_t) length of key

Definition at line 211 of file bhash.h.

Function Documentation

M_INLINE int HASH_check ( HASH * hash )

check consistency of bucket hash structure.

Definition at line 386 of file bhash.h.

{
        size_t  i,nbuck = hash->buckets_size;
        size_t  count_of_elem = 0;
        HASH_Entry  *cur;
        
        for(i=0; i < nbuck; i++) {
                if (!SRING_check(hash->buckets + i)) {
                   return 0;
                }
        }

        HASH_FOREACH(cur,hash)
                count_of_elem++;
        HASH_FOREACH_END
        
        if (count_of_elem != hash->elmcount) {
                return 0;
        }

        return 1;
}

M_INLINE void HASH_deleteall	(	HASH *	hash,
		int	offset_of_link,
		HASH_VISITOR	on_delete,
		void *	context
	)

iterate over all entries of the hash table and delete them.

Parameters:

hash	(in) the object
on_delete	(in) optional callback, call prior to freing object.
offset_of_link	(in) offset of HASH_Entry in embedded structure.

Definition at line 370 of file bhash.h.

{
        HASH_Entry *cur;

        HASH_DELETEALL(cur,hash);
                if (on_delete) {
                        on_delete(cur,context);
                } 
                free( _MEMBEROF(cur,offset_of_link) );
        HASH_DELETEALL_END
}

HASH_Entry* HASH_find	(	HASH *	phash,
		void *	key,
		ssize_t	key_size
	)

find entry with given key in hash table; for multimaps this will return the first occurence of the key.

Parameters:

phash	(in) the object
key	(in) pointer to key
key_size	(in) size of key

Returns:: pointer to entry if found; NULL if not found

Definition at line 119 of file bhash.c.

{
        HASH_VALUE hash = phash->hash_func( key, key_size );
        int             bucket =   ADJUST_HASH(hash, phash->buckets_size);
        SRING   *abucket = &phash->buckets[ bucket ];   
        
        return HASH_find_in_bucket( abucket, hash, phash->compare_key, key, key_size );
}

HASH_Entry* HASH_find_next	(	HASH *	phash,
		HASH_Entry *	prev,
		void *	key,
		ssize_t	key_size
	)

for multimaps - find next occurence of key

Usage to retrive all occurences of a key

HASH_Entry * entry; for( entry = HASH_find(hash, key, sizeof(key) ) ; entry; entry = HASH_find_next(hash, entry, key, sizeof(key) ) {

}

Parameters:

phash	(in) the object
prev	(in) value returned by first invocation of VBUCKETHASH_find or previous invocation of VBUCKETHASH_find_next
key	(in) pointer to key
key_size	(in) size of key. If key is a null terminated string then pass VHASH_STRING as value.

Returns:: pointer to entry if found; NULL if not found

Definition at line 128 of file bhash.c.

{
        HASH_Entry *next;

        if (!phash->ismultimap) {
                return 0;
        }

        next = (HASH_Entry *) prev->entry.next;
        if (!next) {
                return 0;
        }
        if (next->hash != prev->hash) {
                return 0;
        }
        if (phash->compare_key( next, key, key_size ) != 0) {
                return 0;
        }
        return next;
}

M_INLINE HASH_Entry* HASH_findif	(	HASH *	hash,
		HASH_VISITOR	eval_func,
		void *	context,
		int *	retval
	)

find an element within the hash. callback is invoked for each element of the list, when the callback returns non zero value the iteration stops as we have found what we searched for.

Parameters:

hash	(in) the object.
eval_func	(in) callback that is called to visit each set (or cleared) bit.
context	(in) pointer that is passed as context on each invocation of callback.
retval	(out) optional - the first non zero value returned by eval callback, if NULL then ignored.

Returns:: the list element that has matched (i.e. element that has been found).

Definition at line 339 of file bhash.h.

{
        size_t i;
        SRING *cur;
        int ret;        

        if (!eval_func) {
                return 0;
        }

        for(i=0; i<hash->buckets_size; i++) {
                        SRING_FOREACH( cur, &hash->buckets[i] ) {
                                        ret = eval_func( (HASH_Entry*) cur, context);
                                        if (ret) {
                                                if (retval) {
                                                        *retval = ret;
                                                }
                                                return (HASH_Entry *) cur;
                                        }               
                        }
        }       

        return 0;
}

M_INLINE void HASH_foreach	(	HASH *	hash,
		HASH_VISITOR	eval_func,
		void *	context
	)

iterate over all entries of the hash table and invoke callback with each element. Equivalent of Lisp foldl,mapcar and friends.

Parameters:

hash
eval_func	function invoked for every element in hash table.
context	data pointer passed to every invocation of eval_func

Definition at line 315 of file bhash.h.

{
        HASH_Entry *cur;

        if (!eval_func) {
                return;
        }

        HASH_FOREACH(cur,hash)
                eval_func( cur, context);
        HASH_FOREACH_END
}

M_INLINE void HASH_foreach_key	(	HASH *	hash,
		void *	key,
		ssize_t	key_size,
		HASH_VISITOR	eval_func,
		void *	context
	)

iterate over all entries of the hash table that match a given key and invoke callback with those elements.

Parameters:

hash	(in) the object
key	(in) key
key_size	(in) size of key
eval_func	(in) function invoked for every element in hash table.
context	(in) data pointer passed to every invocation of eval_func

Definition at line 295 of file bhash.h.

{
        HASH_Entry *cur;

        if (!eval_func) {
                return;
        }
        HASH_FOREACH_KEY(cur,hash,key,key_size) {
                eval_func( cur, context);
        }
}

M_INLINE void HASH_free ( HASH * hash )

Object destructor; frees a hash table.

All elements currently contained in hash table will remain in memory.

Parameters:

hash	(in out) the object

Definition at line 119 of file bhash.h.

{
   if (hash->buckets) {
        free(hash->buckets);
                hash->buckets = 0;
   }
}

int HASH_init	(	HASH *	hash,
		size_t	buckets,
		int	ismultimap,
		HASH_COMPARE_KEY	compare_key,
		HASH_FUNCTION	hash_func
	)

Object constructor; initialise the hash that allows one entry for a given key.

Parameters:

hash	(out) the object.
buckets	(in) number of buckets - will be rounded to closes power of two (i.e. number of arrays of linked lists structures, each separate list holds elements with same hash number).
hash_func	(in) pointer to hash function
compare	(in) pointer to compare function; compares if two keys are equal, (called when hash value of two entries is equal)

Returns:: 0 if ok

Definition at line 13 of file bhash.c.

{
        size_t i;

        buckets = UTIL_round_to_power_of_n( buckets );


        hash->elmcount = 0;

        if (!hash_func) {
          hash->hash_func = HASHFUNCTION_Bob_Jenkins_one_at_a_time;
        } else {
          hash->hash_func = hash_func;
        }
        hash->compare_key = compare_key;

        hash->ismultimap = ismultimap;

        hash->buckets = (SRING *) malloc( sizeof(SRING) * buckets );
        if (!hash->buckets) {
                return -1;
        }
        hash->buckets_size = buckets;
        
        for(i=0;i<buckets;i++) {
          SRING_init(  &hash->buckets[i] );
        }


        hash->mult_load_factor = 2;
        hash->div_load_factor = 3;

        hash->resize_threshold = (buckets * hash->mult_load_factor) / hash->div_load_factor;

        return 0;
}

int HASH_insert	(	HASH *	phash,
		HASH_Entry *	entry,
		void *	key,
		ssize_t	key_size
	)

insert new entry in hash table

Parameters:

hash	(in) the object
key	(in) key
size	(in) size of key. If key is a null terminated string then pass VHASH_STRING as value.

Definition at line 149 of file bhash.c.

{
        HASH_VALUE hash;
        int             bucket;
        SRING   *abucket,*fnd;

        if ((phash->elmcount + 1) >= phash->resize_threshold) {

           if (HASH_resize(phash, 2 * phash->buckets_size)) {
             return -1;
           }
        }

        hash = phash->hash_func( key, key_size );       
        entry->hash = hash;

        bucket =   ADJUST_HASH(hash, phash->buckets_size);
        abucket = &phash->buckets[ bucket ];   
        
        
        fnd = (SRING *) HASH_find_in_bucket( abucket, hash, phash->compare_key, key, key_size );

        /* multimap allows only one entry with the given key */
        if (!phash->ismultimap && fnd) {
                return -1;
        }

        if (fnd) {
                SRING_insert_after( fnd, &entry->entry );
        } else {
                SRING_push_front( abucket,  &entry->entry );
        }
        phash->elmcount++;

        return 0;
}

int HASH_resize	(	HASH *	hash,
		size_t	buckets
	)

resize the hash table

Change number of buckets in hash table. The function pass over each element in the hash table and insert it into the resized table.

Parameters:

hash	(in out) the object
buckets	(in) new number of buckets

Definition at line 60 of file bhash.c.

{
        SRING *pbuckets;
        size_t i;
        HASH_Entry *cur;
        size_t elmcount;

        buckets = UTIL_round_to_power_of_n( buckets );

        pbuckets = malloc( sizeof(SRING) * buckets);
        if (!pbuckets) {
                return -1;
        }
        for(i=0;i<buckets;i++) {
                SRING_init( pbuckets + i );
        }

        elmcount = hash->elmcount;

        HASH_DELETEALL(cur,hash)
                i = ADJUST_HASH(  cur->hash, buckets);
                SRING_push_front( pbuckets + i, (SRING *) cur);
        HASH_DELETEALL_END

        free( hash->buckets );

        hash->buckets = pbuckets;
        hash->buckets_size = buckets;
        hash->elmcount = elmcount;


        hash->resize_threshold = (buckets * hash->mult_load_factor) / hash->div_load_factor;

        return 0;

}

M_INLINE size_t HASH_size ( HASH * hash )

returns number of elements in hash table

Definition at line 132 of file bhash.h.

{
        return hash->elmcount;
}

HASH_Entry* HASH_unlink	(	HASH *	hash,
		void *	key,
		ssize_t	key_size
	)

find first hash table entry and unlink it from its bucket. The caller of this function has to free memory held by hash table entry.

Parameters:

hash
key
size

Returns:: if entry with given keys exists - pointer to hash table entry.

Definition at line 186 of file bhash.c.

{
        HASH_VALUE hash;
        int             bucket;
        SRING   *abucket;
        SRING   *pos,*prev;
        HASH_Entry *ret = 0;


        hash =  phash->hash_func( key, key_size );      
        bucket =   ADJUST_HASH(hash, phash->buckets_size);
        abucket = &phash->buckets[ bucket ];   

        prev = abucket;
        SRING_FOREACH(pos, abucket) {
                HASH_Entry *entry = (HASH_Entry *) pos;

                if (entry->hash == hash) {
                  
                        if (phash->compare_key( entry, key, key_size ) == 0) {
                                ret = (HASH_Entry *) SRING_unlink_after(prev);
                                phash->elmcount--;      
                                return ret;
                        }
                }
                prev = pos;
        }

        return 0;
}

Classes

Defines

Functions

Detailed Description

Define Documentation

Function Documentation