epk_hashtab.h File Reference

Hash table data structure. More...


Data Structures

struct  EpkHashEntry

Typedefs

typedef struct EpkHashTab_struct EpkHashTab
typedef struct EpkHashIter_struct EpkHashIter
typedef size_t(* epk_ht_hash_f )(const void *key)
typedef int(* epk_ht_kcmp_f )(const void *key, const void *item_key)
typedef void(* epk_ht_proc_f )(EpkHashEntry *entry)

Functions

Hash table functions
EpkHashTabepk_hashtab_create_size (size_t size, epk_ht_hash_f hashfunc, epk_ht_kcmp_f kcmpfunc)
void epk_hashtab_free (EpkHashTab *instance)
size_t epk_hashtab_size (const EpkHashTab *instance)
int epk_hashtab_empty (const EpkHashTab *instance)
void epk_hashtab_insert (EpkHashTab *instance, void *key, void *value, size_t *index)
EpkHashEntryepk_hashtab_find (const EpkHashTab *instance, const void *key, size_t *index)
void epk_hashtab_foreach (const EpkHashTab *instance, epk_ht_proc_f procfunc)
Iterator functions
EpkHashIterepk_hashiter_create (const EpkHashTab *hashtab)
void epk_hashiter_free (EpkHashIter *instance)
EpkHashEntryepk_hashiter_first (EpkHashIter *instance)
EpkHashEntryepk_hashiter_next (EpkHashIter *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)

Pointer-to-function type describing hashing functions. 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)

Pointer-to-function type describing key comparison functions. 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)

Pointer-to-function type describing unary processing functions that can be used with epk_hashtab_foreach(). Here, the current key/value pair will be passed as parameter entry.

Parameters:
Hash table entry

typedef struct EpkHashIter_struct EpkHashIter

Opaque data structure representing an hash table iterator.

typedef struct EpkHashTab_struct EpkHashTab

Opaque data structure representing an hash table.


Function Documentation

EpkHashIter* epk_hashiter_create ( const EpkHashTab hashtab  ) 

Creates and returns an iterator for the given EpkHashTab instance. If the memory allocation request can not be fulfilled, an error message is printed and the program is aborted.

Returns:
Pointer to new instance

EpkHashEntry* epk_hashiter_first ( EpkHashIter instance  ) 

Returns a pointer to the first entry of the hash table which is associated to the given iterator 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

void epk_hashiter_free ( EpkHashIter instance  ) 

Destroys the given instance of EpkHashIter and releases the allocated memory.

Parameters:
instance Object to be freed

EpkHashEntry* epk_hashiter_next ( EpkHashIter instance  ) 

Returns a pointer to the next entry of the hash table which is associated to the given iterator 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

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

Creates and returns an instance of EpkHashTab. 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

int epk_hashtab_empty ( const EpkHashTab instance  ) 

Returns whether the given EpkHashTab instance is empty.

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

EpkHashEntry* epk_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). 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

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.

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

void epk_hashtab_free ( EpkHashTab instance  ) 

Destroys the given instance of EpkHashTab and releases the allocated memory.

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

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

Inserts the given (key,value) pair into the EpkHashTab instance. In addition, an index hint (e.g., returned by a predeeding 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 fo rinternal 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)

size_t epk_hashtab_size ( const EpkHashTab instance  ) 

Returns the actual number of elements stored in the given EpkHashTab instance.

Parameters:
instance Queried object
Returns:
Number of elements stored


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