tech-net archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

2nd stab at ptree documentation

Here's another stab at a manual for ptree(3).  This is the same as the
previous one except that I have mentioned the context pointer that's
passed to each of the ptree ops, and I corrected the ptto_testkey and
ptto_testnode definitions (or tried).

The DESCRIPTION still needs a rewrite.



PTREE(3)                NetBSD Library Functions Manual              PTREE(3)

        ptree -- prefix tree

        Standard C Library (libc, -lc)

        #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);


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



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


                Operations encapsulating knowledge of key
                representations.  See ptree_init(3).


                A node in a ptree.  Every item in a ptree must
                embed a pt_node_t.


                Iteration direction, PT_ASCENDING or PT_DESCENDING.


                Prefix tree branch direction: a ptree branches
                left, PT_SLOT_LEFT, on a 0, and right, PT_SLOT_RIGHT,
                on a 1.


void ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops, void *ctx,
    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, void *ctx);

                        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

                        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, void *ctx);

                        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

                pt_slot_t ptto_testnode(const void *node_key,
                    pt_bitoff_t bitoff, pt_bitlen_t bitlen, void *ctx);

                        Examine the bit at offset `bitoff' from
                        the most significant bit of `node_key',
                        and return PT_SLOT_LEFT if the bit is 0 or
                        PT_SLOT_RIGHT if the bit is 1.

                        The `node_key' argument is a pointer to
                        the key member inside a tree object.

                        [ bitlen is always 1 ? ]

                pt_slot_t ptto_testkey(const void *key,
                    pt_bitoff_t bitoff, pt_bitlen_t bitlen, void *ctx);

                        Examine the bit at offset `bitoff' from
                        the most significant bit of `key', and
                        return PT_SLOT_LEFT if the bit is 0 or
                        PT_SLOT_RIGHT if the bit is 1.

                        The key argument is a pointer to an external
                        key, that is, a key argument for

                        [ bitlen is always 1 ? ]

        `ctx' is a context pointer passed to each of the ptree
        `ops' in their last argument.

        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);

        Insert `item' in the tree as a mask node.  [ TBD best
        description for "mask node" ?  A non-leaf/internal node? ]

        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

        If a `pt' already contains a node with the same key,
        ptree_insert_mask_node returns false without inserting

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

        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.


        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.

     queue(3), rbtree(3)

     The ptree interface first appeared in NetBSD 6.0.

     Matt Thomas <> wrote ptree.

     David Young <> wrote the ptree(3) manual


David Young    Urbana, IL    (217) 721-9981

Home | Main Index | Thread Index | Old Index