|
|
|
simpat Reference Manual | |
|---|---|---|---|---|
#include <patricia.h>
pat_trie;
void (*pat_traverse_func) (pat_prefix *key,
gpointer value,
gpointer ctx);
pat_trie* pat_trie_new (pat_prefix_free_func prefix_free,
gint nodes_per_chunk);
gulong pat_trie_keycount (pat_trie *trie);
gboolean pat_trie_isempty (pat_trie *trie);
void pat_trie_clear (pat_trie *trie,
pat_traverse_func func,
gpointer ctx);
void pat_trie_destroy (pat_trie **trie);
gboolean pat_trie_has_key (pat_trie *trie,
pat_prefix *key);
gboolean pat_trie_search_exact (pat_trie *trie,
pat_prefix *key,
gpointer *pvalue);
gulong pat_trie_search_best (pat_trie *trie,
pat_prefix *key,
pat_prefix **best,
gpointer *pvalue);
gboolean pat_trie_has_prefix (pat_trie *trie,
pat_prefix *prefix);
void pat_trie_foreach (pat_trie *trie,
pat_traverse_func func,
gpointer ctx);
void pat_trie_foreach_prefixed (pat_trie *trie,
pat_prefix *prefix,
pat_traverse_func func,
gpointer ctx);
gint pat_trie_insert (pat_trie *trie,
pat_prefix *key,
gpointer value);
gint pat_trie_update (pat_trie *trie,
pat_prefix *key,
gpointer value);
gint pat_trie_remove (pat_trie *trie,
pat_prefix *key,
gpointer *pvalue);
void pat_trie_dump (pat_trie *trie);
pat_iter* pat_trie_new_iter (pat_trie *trie);
pat_iter* pat_trie_new_iter_with_prefix (pat_trie *trie,
pat_prefix *prefix);
typedef struct _pat_trie pat_trie;
In version 0.20 parent pointers are not used.
Nodes store a skip field instead of an absolute distance.
This field uses two bits to detect upward links.
void (*pat_traverse_func) (pat_prefix *key, gpointer value, gpointer ctx);
Callback type for traversal functions: (key,value) is the
association, and ctx is a supplemental parameter.
key : |
pat_prefix |
value : |
raw pointer |
ctx : |
user-supplied data |
pat_trie* pat_trie_new (pat_prefix_free_func prefix_free, gint nodes_per_chunk);
Create a new, empty pat_trie.
If nodes_per_chunk is zero or less, a default value is assumed.
If nodes_per_chunk is one, nodes are not allocated in chunks.
Otherwise the nodes belong to a singly-linked freelist.
prefix_free : |
deallocation callback for keys |
nodes_per_chunk : |
nodes per chunk (no chunks are managed if nodes_per_chunk==1)
|
| Returns : | new pat_trie |
gulong pat_trie_keycount (pat_trie *trie);
trie : |
a pat_trie |
| Returns : | number of keys in trie
|
gboolean pat_trie_isempty (pat_trie *trie);
Test emptiness
trie : |
a pat_trie |
| Returns : | true iff trie is empty (same as keycount=0)
|
void pat_trie_clear (pat_trie *trie, pat_traverse_func func, gpointer ctx);
Call func for each key if func!=0, then
clear trie (make it empty).
The refcount is decremented for each key.
Nodes are released (returned to a free list if there is one).
trie : |
a pat_trie to empty |
func : |
a pat_traverse_func |
ctx : |
user-supplied parameter to func
|
void pat_trie_destroy (pat_trie **trie);
Call pat_trie_clear() with func=0.
Nullify *trie after destruction.
trie : |
a pat_trie** |
gboolean pat_trie_has_key (pat_trie *trie, pat_prefix *key);
Search for key in trie.
trie : |
a pat_trie |
key : |
a key to search for |
| Returns : | 1 if key exists in trie, 0 otherwise.
|
gboolean pat_trie_search_exact (pat_trie *trie, pat_prefix *key, gpointer *pvalue);
Search for key in trie.
If trie contains key and pvalue!=0, stores associated value in
*pvalue.
trie : |
a pat_trie |
key : |
search key |
pvalue : |
gpointer to store value |
| Returns : | 1 if key exists in trie, 0 otherwise.
|
gulong pat_trie_search_best (pat_trie *trie, pat_prefix *key, pat_prefix **best, gpointer *pvalue);
Search best match for key in trie.
Note that prefix strings are fully compared during the search.
No stack of nodes is involved.
trie : |
a pat_trie |
key : |
a key to find a best match for |
best : |
return address of best-match key:
the longest existing prefix that contains the longest common prefix between key and trie
-- without incrementing (*best)->key->refcount
|
pvalue : |
where to store the value associated with *best (unless pvalue=null)
|
| Returns : | length of longest common prefix between key and any key in trie
(restriction of (*best)->key));
best will point to null if trie is empty;
-1 on bad parameter
|
gboolean pat_trie_has_prefix (pat_trie *trie, pat_prefix *prefix);
trie : |
a pat_trie |
prefix : |
a pat_prefix |
| Returns : | 1 iff some key in trie starts with prefix
|
void pat_trie_foreach (pat_trie *trie, pat_traverse_func func, gpointer ctx);
trie : |
a pat_trie to traverse |
func : |
a pat_traverse_func called at each node |
ctx : |
user-supplied parameter to func
|
void pat_trie_foreach_prefixed (pat_trie *trie, pat_prefix *prefix, pat_traverse_func func, gpointer ctx);
Call func for each key in trie that starts with prefix.
If prefix is empty, the whole trie is traversed.
trie : |
a pat_trie to traverse |
prefix : |
a pat_prefix |
func : |
a pat_traverse_func |
ctx : |
user-supplied parameter |
gint pat_trie_insert (pat_trie *trie, pat_prefix *key, gpointer value);
Insert new key/value association into trie, incrementing
key->refcount -- unless some key in trie starts with key or vice
versa.
trie : |
a pat_trie |
key : |
a pat_prefix |
value : |
a raw value to associate with key
|
| Returns : |
0: success, key->refcount incremented
1: prefix clash, trie unmodified
-1: bad parameter (trie==0||key==0)
-2: node allocation failed
|
gint pat_trie_update (pat_trie *trie, pat_prefix *key, gpointer value);
Replace value associated with key if it exists.
trie : |
a pat_trie |
key : |
pat_prefix to update (used to find key)
|
value : |
pointer to replace value of key
|
| Returns : | 0 if update done; 1 if key is not trie; -1 on error (bad parameter)
|
gint pat_trie_remove (pat_trie *trie, pat_prefix *key, gpointer *pvalue);
Remove key from trie (and decrement key->refcount).
Save value pointer into *pvalue unless pvalue==0
trie : |
a pat_trie |
key : |
pat_prefix to remove |
pvalue : |
pointer to backup value |
| Returns : | 0: success, key->refcount decremented
1: key not found, nothing was done
-1: bad parameter
|
void pat_trie_dump (pat_trie *trie);
Dump -- with printf() -- the bitstrings of trie in pre-order.
Not always available.
trie : |
a pat_trie |
pat_iter* pat_trie_new_iter (pat_trie *trie);
trie : |
a pat_trie |
| Returns : | new iterator (pat_iter) over all key/value pairs in trie
|
pat_iter* pat_trie_new_iter_with_prefix (pat_trie *trie, pat_prefix *prefix);
Create a new iterator over the keys of trie that start with prefix.
If there is no such key, return an iterator whose first step() returns FALSE.
trie : |
a pat_trie |
prefix : |
a pat_prefix (possibly empty) |
| Returns : | a new pat_iter |