Section: libcprops - cp_wtrie (3)
Updated: DECEMBER 2011
Index Return to Main Contents


cp_wtrie - a wide character trie implementation



the following is a summary of functions provided by <cprops/wtrie.h>.

cp_wtrie *cp_wtrie_create(int mode);
cp_wtrie *cp_wtrie_create_trie(int mode,
                              cp_copy_fn copy_leaf,
                              cp_destructor_fn delete_leaf);
int cp_wtrie_destroy(cp_wtrie *trie);
int cp_wtrie_add(cp_wtrie *trie, char *key, void *leaf);
int cp_wtrie_remove(cp_wtrie *trie, char *key, void **leaf);
int cp_wtrie_prefix_match(cp_wtrie *trie, char *key, void **leaf);
void *cp_wtrie_exact_match(cp_wtrie *trie, char *key);
cp_vector *cp_wtrie_fetch_matches(cp_wtrie *trie, char *key);

int cp_wtrie_lock(cp_wtrie *trie, int type);
int cp_wtrie_rdlock(cp_wtrie *trie);
int cp_wtrie_wrlock(cp_wtrie *trie);
int cp_wtrie_unlock(cp_wtrie *trie);

int cp_wtrie_get_mode(cp_wtrie *trie);
int cp_wtrie_set_mode(cp_wtrie *trie, int mode);
int cp_wtrie_unset_mode(cp_wtrie *trie, int mode);



cp_wtrie is a wide character Patricia tree implementation. The trie data sructure allows efficient string prefix matching. Lookup time is O(m) = O(1) where m is the length of the key being matched. cp_wtrie could also be used instead of cp_hashtable for string keys.

cp_wtrie_create creates a new trie structure, which should be deallocated by calling cp_wtrie_destroy. cp_wtrie_create_trie also allows setting a copy_leaf function which is used when adding leaves if mode has the COLLECTION_MODE_COPY set and a delete_leaf function which is used when removing leaves or deleting the trie if mode has the COLLECTION_MODE_DEEP bit set.

cp_wtrie_add sets the mapping for the given key to leaf. cp_wtrie_remove removes the mapping for key from the trie and sets leaf to the removed leaf.

cp_wtrie_prefix_match returns the leaf matched by the longest prefix of key mapped by the trie. Eg having constructed a trie containing only the mappings "a" => "XXX" and "abc" => "YYY", a search for "abcde" would return "YYY".

cp_wtrie_exact_match returns the leaf mapped to by key uniquely.

cp_wtrie_fetch_matches returns a vector containing all values along the path represented by key including the exact match if it exists.

Collection mode bits may be set with cp_wtrie_set_mode and cleared with cp_wtrie_unset_mode. Note that the COLLECTION_MODE_NOSYNC bit may not be set while the calling thread owns the collection lock (ie after calling cp_wtrie_lock and before calling cp_wtrie_unlock).

Unless COLLECTION_MODE_NOSYNC is set, single trie operations are synchronized. Applications that require transaction-like operations should perform locking explicitly by calling cp_wtrie_lock with type set to COLLECTION_LOCK_WRITE or COLLECTION_LOCK_READ, or equivalently, cp_wtrie_wrlock or cp_wtrie_rdlock. When the operation is complete, the lock must be released with cp_wtrie_unlock.  


cp_wtrie_create returns a new trie structure or NULL if a memory allocation failed.

cp_wtrie_destroy returns 0 or -1 if trie is NULL.

cp_wtrie_add and cp_wtrie_remove returns 0 on success or non-zero if a synchronization operation failed.

cp_wtrie_prefix_match returns the number of prefices mapping to leaves found on the way to the longest prefix, or zero if no match was found.

cp_wtrie_exact_match returns the leaf mapped to key or NULL if no such mapping exists.

cp_wtrie_fetch_matches returns all leaves along the path described by key or NULL if no matches exist or on memory allocation failure.

Retrieval and insertion functions may return NULL if locking fails. This however should not normally occur unless accessing the trie lock directly rather than performing synchronization through the api functions.




This document was created by man2html, using the manual pages.
Time: 23:05:24 GMT, December 05, 2011