cp_trie

Section: libcprops - cp_trie (3)
Updated: OCTOBER 2005
Index Return to Main Contents [view source]
 

NAME

cp_trie - a character trie implementation

 

INTERFACE

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

cp_trie *cp_trie_create(int mode);
cp_trie *cp_trie_create_trie(int mode,
                              cp_copy_fn copy_leaf,
                              cp_destructor_fn delete_leaf);
int cp_trie_destroy(cp_trie *trie);
int cp_trie_add(cp_trie *trie, char *key, void *leaf);
int cp_trie_remove(cp_trie *trie, char *key, void **leaf);
int cp_trie_prefix_match(cp_trie *trie, char *key, void **leaf);
void *cp_trie_exact_match(cp_trie *trie, char *key);
cp_vector *cp_trie_fetch_matches(cp_trie *trie, char *key);

int cp_trie_lock(cp_trie *trie, int type);
int cp_trie_rdlock(cp_trie *trie);
int cp_trie_wrlock(cp_trie *trie);
int cp_trie_unlock(cp_trie *trie);

int cp_trie_get_mode(cp_trie *trie);
int cp_trie_set_mode(cp_trie *trie, int mode);
int cp_trie_unset_mode(cp_trie *trie, int mode);

 

DESCRIPTION

cp_trie is a 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_trie could also be used instead of cp_hashtable for string keys. Tries have some advantages over hashtables in that the worst case performance remains O(1) for tries in contrast to O(n) for hash tables, no hash function is required, and no full scale rehashing or balancing is necessary.

cp_trie_create creates a new trie structure, which should be deallocated by calling cp_trie_destroy. cp_trie_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_trie_add sets the mapping for the given key to leaf. cp_trie_remove removes the mapping for key from the trie and sets leaf to the removed leaf.

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

cp_trie_exact_match returns the leaf mapped to by key uniquely.

cp_trie_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_trie_set_mode and cleared with cp_trie_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_trie_lock and before calling cp_trie_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_trie_lock with type set to COLLECTION_LOCK_WRITE or COLLECTION_LOCK_READ, or equivalently, cp_trie_wrlock or cp_trie_rdlock. When the operation is complete, the lock must be released with cp_trie_unlock.  

RETURN VALUE

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

cp_trie_destroy returns 0 or -1 if trie is NULL.

cp_trie_add and cp_trie_remove returns 0 on success or non-zero if a synchronization operation failed.

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

cp_trie_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.  

EXAMPLE

The following code creates a trie, inserts mappings entered on the standard input, then attempts matches for keys entered on the standard input. 

#include <stdio.h>
#include <string.h>
#include "collection.h"
#include "trie.h"

int main(int argc, char *argv[])
{
        char key[80];
        char val[80];
        char *match;
        cp_trie *t = cp_trie_create(COLLECTION_MODE_NOSYNC);
        int sub;

        printf("enter mappings as [key value], \"next\" or \'n\' when done\n");
        while (1)
        {
                scanf("%s", key);
                if (strcmp(key, "n") == 0 || strcmp(key, "next") == 0) break;
                scanf("%s", val);
                
                printf("adding %s => %s\n", key, val);
                cp_trie_add(t, key, strdup(val));
        }

        printf("enter key to match - \'q\' or \"quit\" to quit\n");
        while (1)
        {
                scanf("%s", key);
                if (strcmp(key, "q") == 0 || strcmp(key, "quit") == 0)
                        break;
                
                sub = cp_trie_prefix_match(t, key, &match);
                printf("match for %s: %s [%d]\n", 
                           key, match ? match : "none", sub);
        }

        cp_trie_destroy(t);

        return 0;
}

for notes on compiling and linking see cprops(3).

 

Index

NAME
INTERFACE
DESCRIPTION
RETURN VALUE
EXAMPLE
This document was created by man2html, using the manual pages.
Time: 12:01:45 GMT, May 23, 2006 		SourceForge.net Logo