epk_hashtab.h File Reference

Hash table data structure. More...


Data Structures

struct  EpkHashEntry
 Data structure representing key/value pairs stored in the hash table. More...

Typedefs

typedef struct EpkHashTab_struct EpkHashTab
 Opaque data structure representing a hash table.
typedef struct EpkHashIter_struct EpkHashIter
 Opaque data structure representing a hash table iterator.
typedef size_t(* epk_ht_hash_f )(const void *key)
 Pointer-to-function type describing hashing functions.
typedef int(* epk_ht_kcmp_f )(const void *key, const void *item_key)
 Pointer-to-function type describing key comparison functions.
typedef void(* epk_ht_proc_f )(EpkHashEntry *entry)
 Pointer-to-function type describing unary processing functions that can be used with epk_hashtab_foreach().

Functions

Hash table functions
EXTERN EpkHashTabepk_hashtab_create_size (size_t size, epk_ht_hash_f hashfunc, epk_ht_kcmp_f kcmpfunc)
 Creates and returns an instance of EpkHashTab.
EXTERN void epk_hashtab_free (EpkHashTab *instance)
 Destroys the given instance of EpkHashTab and releases the allocated memory.
EXTERN size_t epk_hashtab_size (const EpkHashTab *instance)
 Returns the actual number of elements stored in the given EpkHashTab instance.
EXTERN int epk_hashtab_empty (const EpkHashTab *instance)
 Returns whether the given EpkHashTab instance is empty.
EXTERN void epk_hashtab_insert (EpkHashTab *instance, void *key, void *value, size_t *index)
 Inserts the given (key,value) pair into the EpkHashTab instance.
EXTERN EpkHashEntryepk_hashtab_find (const EpkHashTab *instance, const void *key, size_t *index)
 Searches for the an hash table entry with the specified key in the given EpkHashTab instance, using the binary key comparison function cmpfunc (see epk_ht_kcmp_f for implementation details).
EXTERN void epk_hashtab_foreach (const EpkHashTab *instance, epk_ht_proc_f procfunc)
 Calls the unary processing function procfunc for each element of the given EpkHashTab instance.
Iterator functions
EXTERN EpkHashIterepk_hashiter_create (const EpkHashTab *hashtab)
 Creates and returns an iterator for the given EpkHashTab instance.
EXTERN void epk_hashiter_free (EpkHashIter *instance)
 Destroys the given instance of EpkHashIter and releases the allocated memory.
EXTERN EpkHashEntryepk_hashiter_first (EpkHashIter *instance)
 Returns a pointer to the first entry of the hash table which is associated to the given iterator instance.
EXTERN EpkHashEntryepk_hashiter_next (EpkHashIter *instance)
 Returns a pointer to the next entry of the hash table which is associated to the given iterator instance.


Detailed Description

This file provides type definitions and function prototypes for a generic hash table data structure. The elements of such a hash table are stored in no particular order as a key/value pair, where both items are represented by void pointers (see EpkHashEntry).

In addition, this module defines an associated iterator data type EpkHashIter, which allows convenient traversal of all entries stored in the hash table.

The epk_hashtab module follows an object-oriented style. That is, each function (except the two create functions) takes a pointer to an instance of either type EpkHashTab or EpkHashIter as their first argument, which is the object (i.e., the data structure) they operate on.

Note:
This module uses the assert() macro to check various conditions (especially the values of given parameters) at runtime, which can cause a performance penalty.

Typedef Documentation

typedef size_t(* epk_ht_hash_f)(const void *key)

The function has to compute an integral index value for the given key. If the computed index is larger than the size of the hash table, it will be automatically adjusted using modulo arithmetics.

Parameters:
key Key value
Returns:
entry Computed hash table index

typedef int(* epk_ht_kcmp_f)(const void *key, const void *item_key)

It has to return 0 if the given key equals the key of the current item (item_key) or a non-zero value otherwise.

Parameters:
key Key value to compare
item_key Key value of the current item

typedef void(* epk_ht_proc_f)(EpkHashEntry *entry)

Here, the current key/value pair will be passed as parameter entry.

Parameters:
Hash table entry

typedef struct EpkHashIter_struct EpkHashIter

typedef struct EpkHashTab_struct EpkHashTab


Function Documentation

EXTERN EpkHashIter* epk_hashiter_create ( const EpkHashTab hashtab  ) 

If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Returns:
Pointer to new instance

EXTERN EpkHashEntry* epk_hashiter_first ( EpkHashIter instance  ) 

If the hash table is empty, NULL is returned.

Parameters:
instance Iterator object
Returns:
Pointer to first entry of the hash table or NULL if empty

EXTERN void epk_hashiter_free ( EpkHashIter instance  ) 

Parameters:
instance Object to be freed

EXTERN EpkHashEntry* epk_hashiter_next ( EpkHashIter instance  ) 

If no next entry is available, NULL is returned.

Parameters:
instance Iterator object
Returns:
Pointer to next entry of the hash table or NULL if unavailable

EXTERN EpkHashTab* epk_hashtab_create_size ( size_t  size,
epk_ht_hash_f  hashfunc,
epk_ht_kcmp_f  kcmpfunc 
)

Besides the size of the hash table, pointers to a hashing function as well as a key comparison function have to be provided. If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Parameters:
size Size of the hash table
hashfunc Hashing function
kcmpfunc Key comparison function
Returns:
Pointer to new instance

EXTERN int epk_hashtab_empty ( const EpkHashTab instance  ) 

Parameters:
instance Queried object
Returns:
Non-zero value if instance if empty; zero otherwise

EXTERN EpkHashEntry* epk_hashtab_find ( const EpkHashTab instance,
const void *  key,
size_t *  index 
)

If a matching item could be found, a pointer to the key/value pair is returned. In addition, if index is non-NULL, the hash table index is stored in the memory location pointed to by index, which can be used as an index hint for an subsequent call to epk_hashtab_insert(). Otherwise, i.e., if no matching item could be found, this function returns NULL.

Parameters:
instance Object in which the item is searched
key Unique key to search for
index Memory location where index of matching item is stored (ignored if NULL)
Returns:
Pointer to hash table entry if matching item cound be found; NULL otherwise

EXTERN void epk_hashtab_foreach ( const EpkHashTab instance,
epk_ht_proc_f  procfunc 
)

Parameters:
instance Object whose entries should be processed
procfunc Unary processing function

EXTERN void epk_hashtab_free ( EpkHashTab instance  ) 

Note:
Similar to the EpkVector data structure, this call does not free the memory occupied by the elements, i.e., keys and values, since only pointers are stored. This has to be done separately.
Parameters:
instance Object to be freed

EXTERN void epk_hashtab_insert ( EpkHashTab instance,
void *  key,
void *  value,
size_t *  index 
)

In addition, an index hint (e.g., returned by a preceding call of epk_hashtab_find()) can be specified. If the index should be (re-)calculated instead, NULL can be passed.

This function also has to allocate memory for internal data structures. If this memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Parameters:
instance Object in which the key/value pair should be inserted
key Unique key
value Associated value
index Memory location where an index hint is stored (ignored if NULL)

EXTERN size_t epk_hashtab_size ( const EpkHashTab instance  ) 

Parameters:
instance Queried object
Returns:
Number of elements stored


SCALASCA    Copyright © 1998–2010 Forschungszentrum Jülich, Jülich Supercomputing Centre