cp_hashtable

Section: libcprops - cp_hashtable (3)
Updated: OCTOBER 2005
Index Return to Main Contents
 

NAME

cp_hashtable_create, cp_hashtable_create_by_mode, cp_hashtable_create_copy_mode, cp_hashtable_create_by_option - hashtable constructor functions  

SYNOPSIS

#include <cprops/hashtable.h>

cp_hashtable *cp_hashtable_create(long initial_size,
                                   cp_hashfunction hash_fn,
                                   cp_compare_fn compare_fn);
cp_hashtable *cp_hashtable_create_by_mode(int mode,
                                           int initial_size,
                                           cp_hashfunction hash_fn,
                                           cp_compare_fn compare_fn);
cp_hashtable *
      cp_hashtable_create_copy_mode(long initial_size,
                                    cp_hashfunction cp_hashfn,
                                    cp_compare_fn compare_fn,
                                    cp_copy_fn copy_key,
                                    cp_destructor_fn free_key);
                                    cp_copy_fn copy_value
                                    cp_destructor_fn free_value);
cp_hashtable *
      cp_hashtable_create_by_option(int mode,
                                    long initial_size,
                                    cp_hashfunction hash_fn,
                                    cp_compare_fn compare_fn,
                                    cp_copy_fn copy_key,
                                    cp_destructor_fn free_key);
                                    cp_copy_fn copy_value
                                    cp_destructor_fn free_value);

 

DESCRIPTION

cp_hashtable_create creates a hashtable using initial_size as an estimate for the required table size. Items are indexed using the specified hash_fn. The hash function should be defined as

long hash_fn(void *key);

and ideally return evenly distributed values in the lower bits for different key values. The hash function's return value for a particular key is known as the hash code for this key and this number taken modulo the internal table size determines the index for the given key. Since the hash function is not known in advance and the table size is kept on the order of the number of entries, this index is not necessarily unique. Therefore a comparison function defined as

int hash_compare(void *a, void *b);

is needed to identify the requested key upon retrieval if multiple keys map to the same index. The comparison function should return 0 for matching items, non-zero otherwise (``strcmp semantics''). A frequent error is to write the comparison function so that it returns 1 'for a successful match', leading to unexpected behavior - typically, on low fill factors, items 'disappear', on higher fill factors, false matches are returned.

Tables created with the default mode (0) synchronize all table operations (item insertion, retrieval and removal, table resizing and deleting) and perform no memory management - keys and values are neither copied nor deallocated. Different behavior can also be specified by calling cp_hashtable_create_by_mode and specifying a non-zero mode value, e.g. COLLECTION_MODE_NOSYNC where table access is done in a single thread or is synchronized externally. cp_hashtable_create_copy_mode creates a table with the COLLECTION_MODE_COPY and COLLECTION_MODE_DEEP bits set. If non-null copy_key and copy_value functions are specified, they are used to insert copies of the keys and values given in insertion functions respectively. Likewise, the free_key and free_value functions will, if not null, be called upon key and value respectively when removing an entry from the table. Both functions' prototypes should follow

void *copy_function(void *item);

cp_hashtable_create_by_option is simillar to cp_hashtable_create_copy_mode but allows specifying any mode. Note that copy functions will only be called if COLLECTION_MODE_COPY is set and finalization functions will only be called if COLLECTION_MODE_DEEP is set.

By default tables will resize on insertion when the number of entries in the table exceeds 70% of the internal table size, and on removal when the number of entries goes below 5% of the internal table size. Resizing is a potentially unpleasant affair, requiring the remapping of all entries in the table. A dedicated thread is kicked up to do this unless the mode bit COLLECTION_MODE_NOSYNC is set, in which case resizing is done synchronouosly. Resizing can be suppressed by setting COLLECTION_MODE_NORESIZE. Upper and lower fill factors may be set with cp_hashtable_set_max_fill_factor and cp_hashtable_set_min_fill_factor respectively. The table will not be resized below min_size which is set to initial_size on initialization and can be changed with cp_hashtable_set_min_size.

All mode bits can be set or reset after creation time by calling cp_hashtable_set_mode and cp_hashtable_unset_mode. Note that tables constructed with COLLECTION_MODE_NOSYNC set do not initialize the synchronization features, and subsequent attempts to perform thread safe operations may behave unpredictably. If a hashtable may be accessed by multiple threads at any point, it should not be initialized with COLLECTION_MODE_NOSYNC.

 

RETURN VALUE

all constructor functions return a pointer to a newly allocated hashtable instance on success, or NULL on failure.

 

ERRORS

ENOMEM an internal memory allocation failed.

EINVAL a negative initial_size was requested.

 

SEE ALSO

cp_hashtable(3), cp_hashtable_set_mode(3), cp_hashtable_set_max_fill_factor(3), cp_hashlist(3)


 

Index

NAME
SYNOPSIS
DESCRIPTION
RETURN VALUE
ERRORS
SEE ALSO

This document was created by man2html, using the manual pages.
Time: 18:37:21 GMT, December 27, 2005
SourceForge.net Logo