tech-net archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
1st stab at ptree documentation
Here's a stab at a manual for ptree(3). I have adapted it from Matt
Thomas's documentation at <http://www.netbsd.org/~matt/smpnet#ptree>.
With the help of the ptree source code and rmind@'s ptree application in
NPF, I was able to flesh out Matt's documentation a bit.
I have called this a "prefix tree" instead of a "PATRICIA tree"
because that is descriptive and also starts with a 'p'.
(I could have sworn that what we call a PATRICIA tree in the kernel
was a degenerate case of an actual PATRICIA tree! Apparently, I
have been thinking of a suffix tree.)
The DESCRIPTION needs a rewrite.
Dave
***
PTREE(3) NetBSD Library Functions Manual PTREE(3)
NAME
ptree -- prefix tree
LIBRARY
Standard C Library (libc, -lc)
SYNOPSIS
#include <sys/ptree.h>
void ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops,
size_t ptnode_offset, size_t key_offset);
void *ptree_find_filtered_node(pt_tree_t *pt, const void *key,
pt_filter_t filter, void *filter_ctx);
void *ptree_find_node(pt_tree_t *pt, const void *key);
bool ptree_insert_mask_node(pt_tree_t *pt, void *item,
pt_bitlen_t masklen);
bool ptree_insert_node(pt_tree_t *pt, void *item);
void *ptree_iterate(pt_tree_t *pt, const void *node,
pt_direction_t direction);
void ptree_remove_node(pt_tree_t *pt, void *item);
DESCRIPTION
[ random facts about ptree, needs reorganization & rewrite ]
ptree(3) provides a prefix tree suitable for storing and
retrieving items identified by unique bit strings.
A prefix tree is a tree-shaped data structure where each
node corresponds to a particular key. A prefix tree is
different from a binary search tree in that the key
corresponding to each node is not stored at that node, but
the path from the root of the tree to a node uniquely
determines the key.
The children of a ptree node share the same bit prefix.
For k the length of a key, an insertion, deletion, or lookup
in a ptree takes O(k) time. [ more about the properties
and uses of ptree here ]
Items in a ptree are ordered by key. ptree uses a
lexicographical ordering on the bit strings, thus keys 0,
00, 000, 001, 01, 010, 011, 1, 10, 100, 101, 11, 110, 111
are in ascending order according to ptree.
Embedded in each item in a pt_tree_t is a key and a pt_node_t.
The pt_node_t contains the pt_tree_t linkage.
To insert a node into a ptree requires no memory allocation.
Multiple readers and one writer may simultaneously access
a ptree.
TYPES
pt_tree_t
A prefix tree.
typedef bool (*pt_filter_t)(void *, const void *, int);
A prefix-tree node filter. Returns true for matching
nodes, false otherwise. See ptree_find_filter_node(3).
pt_tree_ops_t
Operations encapsulating knowledge of key
representations. See ptree_init(3).
pt_node_t
A node in a ptree. Every item in a ptree must
embed a pt_node_t.
pt_direction_t
Iteration direction, PT_ASCENDING or PT_DESCENDING.
pt_slot_t
Prefix tree branch direction: a ptree branches
left, PT_SLOT_LEFT, on a 0, and right, PT_SLOT_RIGHT,
on a 1.
FUNCTIONS
void ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops,
size_t ptnode_offset, size_t key_offset);
Initialize a ptree. If pt points at an existing ptree,
all knowledge of that ptree will be lost.
`pt' is a pointer to the pt_tree_t to be initialized.
`ops' is a pointer to the pt_tree_ops_t used by the ptree.
The ops encapsulate all knowledge of the key representations
used with this ptree. There are two key representations,
the one that is internal to the tree (embedded in pt_node_t)
and the one that is external (used for lookups by
ptree_find_filtered_node). A pt_tree_ops_t has four members:
bool ptto_matchnode(const void *lnode_key,
const void *rnode_key,
pt_bitoff_t max_bitoff, pt_bitoff_t *bitoffp,
pt_slot_t *slotp);
If not NULL, the `lnode_key' and `rnode_key'
arguments are pointers to key members inside
tree items. If `rnode_key' is NULL, then
treat it like a key consisting entirely of
zero bits.
Return true if both `lnode_key' and `rnode_key'
have the identical string of bits starting
at `*bitoffp' and ending before `max_bitoff'.
In addition to returning true, set `*bitoffp'
to the smaller of `max_bitoff' or the
length, in bits, of the compared bit strings.
ptto_matchnode must ignore bits before
`*bitoffp'.
If the bits are not identical, ptto_matchnode
sets `*bitoffp' to the offset where the
bit difference occurred, sets `*slotp' to
PT_SLOT_LEFT if the value of that bit in
`lnode_key' is 0 (otherwise sets `*slotp'
to PT_SLOT_RIGHT), and returns false.
bool ptto_matchkey(const void *key,
const void *node_key, pt_bitoff_t bitoff,
pt_bitlen_t bitlen);
Return true if both `key' and `node_key'
objects have identical strings of `bitlen'
bits starting at `bitoff'. The key argument
is the same key argument supplied to
ptree_find_filtered_node.
pt_slot_t ptto_testnode(const void *node_key,
pt_bitoff_t bitoff, pt_bitlen_t bitlen);
Returns bitlen bits starting at bitoff from
node_key. The node_key argument is a pointer
to the key members inside a tree object.
pt_slot_t ptto_testkey(const void *key,
pt_bitoff_t bitoff, pt_bitlen_t bitlen);
Returns bitlen bits starting at bitoff from
key. The key argument is the same key
argument supplied to ptree_find_filtered_node.
The ptnode_offset argument contains the offset in bytes
from the beginning of an item to its pt_node_t member.
The key_offset argument contains the offset in bytes from
the beginning of an item to its key data. The key_offset
is used to compute from items the arguments rnode_key,
lnode_key, and node_key that are passed to the ptto_matchnode,
ptto_matchkey, and ptto_testnode operations.
void *ptree_find_filtered_node(pt_tree_t *pt, const void *key,
pt_filter_t filter, void *filter_ctx);
Return the item in `pt' exactly matching `key' and satisfying
`(*filter)(filter_ctx, item, 0)'. If there is no such
match, return the longest matching mask satisfying
`(*filter)(filter_ctx, item, PT_FILTER_MASK)'. If there
is no match, return NULL.
`filter' may be NULL. Every item satisfies the NULL filter.
void *ptree_find_node(pt_tree_t *pt, const void *key);
A synonym for ptree_find_filter_node(pt, key, NULL, NULL).
bool ptree_insert_mask_node(pt_tree_t *pt, void *item, pt_bitlen_t masklen);
Only the first `masklen' bits of the `item's embedded key
may be non-zero. If that condition does not hold,
ptree_insert_mask_node returns false without inserting
`item'.
If a `pt' already contains a node with the same key,
ptree_insert_mask_node returns false without inserting
`item'.
If the item's key meets the above condition, and the key
is not a duplicate, insert `item' in the tree as a mask
node. [ TBD best description for "mask node" ? A
non-leaf/internal node? ]
bool ptree_insert_node(pt_tree_t *pt, void *item);
If there is not already an item in `pt' with the same key
as `item', insert `item' into the tree and return true.
Otherwise, return false.
void *ptree_iterate(pt_tree_t *pt, const void *node, pt_direction_t direction);
ptree_iterate() steps through nodes in a ptree in ascending
or descending order.
direction: one of PT_ASCENDING or PT_DESCENDING.
ptree_iterate() returns NULL if `direction' has any other
value.
ptree_iterate(pt, node, PT_ASCENDING):
return the first ("least" or "leftmost") node in
`pt' if `node' is NULL, or the node following
`node'. If `pt' is empty or if there are no nodes
following `node', return NULL.
ptree_iterate(pt, NULL, PT_DESCENDING):
return the last ("greatest" or "rightmost") node
in `pt' if `node' is NULL, or the node preceding
`node'. If `pt' is empty or if there are no nodes
preceding `node', return NULL.
void ptree_remove_node(pt_tree_t *pt, void *item);
Return `item' from `pt'. If `item' is not present in `pt',
results are undefined.
CODE REFERENCES
The ptree interface is implemented in common/lib/libc/gen/ptree.c.
An example application of ptree is at sys/net/npf/npf_tableset.c
and sys/net/npf/npf_tableset_ptree.c.
SEE ALSO
queue(3), rbtree(3)
HISTORY
The ptree interface first appeared in NetBSD 6.0.
AUTHORS
Matt Thomas <matt%NetBSD.org@localhost> wrote ptree.
David Young <dyoung%NetBSD.org@localhost> wrote the ptree(3) manual
page.
Dave
--
David Young
dyoung%pobox.com@localhost Urbana, IL (217) 721-9981
Home |
Main Index |
Thread Index |
Old Index