cp_sorted_hash

Section: libcprops - cp_sorted_hash (3)
Updated: SEPTEMBER 2006
Index Return to Main Contents

NAME

cp_sorted_hash_create, cp_sorted_hash_create_by_option, cp_sorted_hash_destroy, cp_sorted_hash_destroy_custom - sorted hash constructor/ destructor functions

SYNOPSIS

#include <cprops/sorted_hash.h>

cp_sorted_hash *cp_sorted_hash_create(cp_hashfunction hash,
                                       cp_compare_fn cmp_key,
                                       cp_mapping_cmp_fn cmp_mapping);
cp_sorted_hash *
      cp_sorted_hash_create_by_option(int mode,
                                      unsigned long size_hint,
                                      cp_hashfunction hash,
                                      cp_compare_fn cmp_key,
                                      cp_mapping_cmp_fn cmp_mapping,
                                      cp_copy_fn key_copy,
                                      cp_destructor_fn key_dtr,
                                      cp_copy_fn val_copy,
                                      cp_destructor_fn val_dtr);

void cp_sorted_hash_destroy(cp_sorted_hash *table);
void cp_sorted_hash_destroy_custom(cp_sorted_hash *table,
cp_destructor_fn key_dtr,
cp_destructor_fn val_dtr);

DESCRIPTION

cp_sorted_hash_create creates a sorted hash using the given hash and comparison functions for key lookups and the given mapping comparison function for ordering. This allows performing lookups by key while preserving an ordering based on the key, value or both. As a special case if a NULL mapping comparison function is specified the collection is ordered by key ordering. This results in a data structure supporting both ordering and lookups in amortized O(1) time, at the price of slower insertion and removal operations and a larger memory overhead per item.
The prototypes for hash, key compare and mapping comparison functions are as follows:

unsigned long hash_fn(void *key);
int compare_fn(void *key1, void *key2);
int mapping_cmp_fn(cp_mapping *mapping1, cp_mapping *mapping2);

The key compare function should follow this prototype:

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

and return 0 for matching keys, > 0 if a > b and < 0 if a < b (strcmp semantics). The created tree is not synchronized (COLLECTION_MODE_NOSYNC mode bit is set).

cp_mapping structure is defined as follows:

typedef struct _cp_mapping
{
    void *key;
    void *value;
} cp_mapping;

The following macros may be used to obtain key and value from a cp_mapping object:

void *cp_mapping_key(cp_mapping *m);
void *cp_mapping_value(cp_mapping *m);

cp_sorted_hash_create_by_option allows specifying an initial operation mode. Note that unless COLLECTION_MODE_NOSYNC is set on the mode parameter, tree operations are synchronized. The key_copy and value_copy functions are used on insertion if COLLECTION_MODE_COPY is set. If COLLECTION_MODE_COPY is set and either of these is NULL, inserted keys and / or values are inserted directly rather than copies.
The key_dtr and value_dtr functions are used on item removal or tree destruction if COLLECTION_MODE_DEEP is set. If COLLECTION_MODE_DEEP is set and either of these is NULL, no cleanup is performed on keys and / or values. This makes it possible to apply the copy/ deep mechanism to keys or values only.

cp_sorted_hash_destroy deallocates the mapping structure using the current mode settings. cp_sorted_hash_destroy_custom sets the COLLECTION_MODE_DEEP mode bit and destroys the collection using the given key and value destructor functions. Specifying a NULL destructor function or functions precludes key deallocation, value deallocation or both.

RETURN VALUE

cp_sorted_hash_create and cp_sorted_hash_create_by_option return a newly allocated cp_sorted_hash object on success or NULL on failure.