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


cp_rtrie - a bit sequence radix trie implementation



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

cp_rtrie *cp_rtrie_create(int mode);
cp_rtrie *cp_rtrie_create_trie(int mode,
                              cp_copy_fn copy_leaf,
                              cp_destructor_fn delete_leaf);
int cp_rtrie_destroy(cp_rtrie *trie);
int cp_rtrie_add(cp_rtrie *trie, cp_bstr *key, void *leaf);
int cp_rtrie_remove(cp_rtrie *trie, cp_bstr *key, void **leaf);
int cp_rtrie_prefix_match(cp_rtrie *trie, cp_bstr *key, void **leaf);
void *cp_rtrie_exact_match(cp_rtrie *trie, cp_bstr *key);
cp_vector *cp_rtrie_fetch_matches(cp_rtrie *trie, cp_bstr *key);

int cp_rtrie_lock(cp_rtrie *trie, int type);
int cp_rtrie_rdlock(cp_rtrie *trie);
int cp_rtrie_wrlock(cp_rtrie *trie);
int cp_rtrie_unlock(cp_rtrie *trie);

int cp_rtrie_get_mode(cp_rtrie *trie);
int cp_rtrie_set_mode(cp_rtrie *trie, int mode);
int cp_rtrie_unset_mode(cp_rtrie *trie, int mode);



cp_rtrie is a bit string radix tree implementation. The trie data sructure allows efficient prefix matching. Lookup time is O(m) = O(1) where m is the length of the key being matched.

cp_rtrie_create creates a new trie structure, which should be deallocated by calling cp_rtrie_destroy. cp_rtrie_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_rtrie_add sets the mapping for the given key to leaf. cp_rtrie_remove removes the mapping for key from the trie and sets leaf to the removed leaf.

cp_rtrie_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 "0" => "XXX" and "010" => "YYY", a search for "01010" would return "YYY".

cp_rtrie_exact_match returns the leaf mapped to by key uniquely.

cp_rtrie_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_rtrie_set_mode and cleared with cp_rtrie_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_rtrie_lock and before calling cp_rtrie_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_rtrie_lock with type set to COLLECTION_LOCK_WRITE or COLLECTION_LOCK_READ, or equivalently, cp_rtrie_wrlock or cp_rtrie_rdlock. When the operation is complete, the lock must be released with cp_rtrie_unlock.  


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

cp_rtrie_destroy returns 0 or -1 if trie is NULL.

cp_rtrie_add and cp_rtrie_remove returns 0 on success or non-zero if a synchronization operation failed.

cp_rtrie_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_rtrie_exact_match returns the leaf mapped to key or NULL if no such mapping exists.

cp_rtrie_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