patricia.h File Reference

Patricia tree APIs. More...


Data Structures

struct  patnode_
 Patricia tree node. More...
struct  patroot_
 Patricia tree root. More...

Defines

#define PAT_MAXKEY   256
 The maximum length of a key, in bytes.
#define PATRICIA_LEN_TO_BIT(len)   ((u_int16_t) ((((len) - 1) << 8) | 0xff))
 A macro to initialize the `length' in a patnode at compile time given the length of a key.
#define PAT_NOBIT   (0)
 Bit number when no external node.
#define STRUCT_SIZEOF(_structure, _element)   (sizeof(((_structure*)0)->_element))
 Returns the sizeof for an element in a structure.
#define STRUCT_OFFSET(_structure, _elt1, _elt2)
 Returns the offset of _elt2 from the END of _elt1 within structure.
#define PATNODE_TO_STRUCT(procname, structname, fieldname)
 Macro to define an inline to map from a patnode entry back to the containing data structure.
#define PATNODE_TO_CONS_STRUCT(procname, structname, fieldname)
 Constant version of the macro to define an inline to map from a patnode entry back to the containing data structure.
#define PATRICIA_ROOT_INIT(_rootptr, _bool_key_is_ptr, _nodestruct, _nodeelement, _keyelt)
 Initialize a patricia root with a little more compile-time checking.

Typedefs

typedef patnode_ patnode
 Patricia tree node.
typedef patroot_ patroot
 Patricia tree root.
typedef patroot *(* patricia_root_alloc_fn )(void)
 Typedef for user-specified patroot allocation function.
typedef void(* patricia_root_free_fn )(patroot *)
 Typedef for user-specified patroot free function.

Functions

patrootpatricia_root_init (patroot *root, boolean key_is_ptr, u_int16_t key_bytes, u_int8_t key_offset)
 Initializes a patricia tree root.
void patricia_root_delete (patroot *root)
 Deletes a patricia tree root.
void patricia_node_init_length (patnode *node, u_int16_t key_bytes)
 Initializes a patricia tree node using the key length specified by key_bytes.
boolean patricia_add (patroot *root, patnode *node)
 Adds a new node to the tree.
boolean patricia_delete (patroot *root, patnode *node)
 Deletes a node from the tree.
patnodepatricia_find_next (patroot *root, patnode *node)
 Given a node in the tree, find the node with the next numerically larger key.
patnodepatricia_find_prev (patroot *root, patnode *node)
 Given a node in the tree, find the node with the next numerically smaller key.
patnodepatricia_subtree_match (patroot *root, u_int16_t prefix_len, const void *prefix)
 Given a prefix and a prefix length in bits, find the node with the numerically smallest key in the tree which includes this prefix.
patnodepatricia_subtree_next (patroot *root, patnode *node, u_int16_t prefix_len)
 Given a node in the tree, and a prefix length in bits, return the next numerically larger node in the tree which shares a prefix with the node specified.
patnodepatricia_get (patroot *root, u_int16_t key_bytes, const void *key)
 Looks up a node having the specified key and key length in bytes.
patnodepatricia_getnext (patroot *root, u_int16_t key_bytes, const void *key, boolean return_eq)
 Given a key and key length in bytes, return a node in the tree which is at least as large as the key specified.
boolean patricia_node_in_tree (const patnode *node)
 Determines if a patricia tree node is contained within a tree.
int patricia_compare_nodes (patroot *root, patnode *left, patnode *right)
 Given two patricia tree nodes, determine if the first has a key which is numerically lesser, equal, or greater than the key of the second.
void patricia_set_allocator (patricia_root_alloc_fn my_alloc, patricia_root_free_fn my_free)
 Sets allocation and free routines for patricia tree root structures.
const patnodepatricia_cons_get (const patroot *root, const u_int16_t key_bytes, const void *key)
 Constant tree form of patricia_get().
const patnodepatricia_cons_find_next (const patroot *root, const patnode *node)
 Constant tree form of patricia_find_next().
const patnodepatricia_cons_find_prev (const patroot *root, const patnode *node)
 Constant tree form of patricia_find_prev().
const patnodepatricia_cons_subtree_match (const patroot *root, const u_int16_t prefix_len, const void *prefix)
 Constant tree form of patricia_subtree_match().
const patnodepatricia_cons_subtree_next (const patroot *root, const patnode *node, const u_int16_t prefix_len)
 Constant tree form of patricia_subtree_next().
static void patricia_node_init (patnode *node)
 Initializes a patricia tree node using the the key length specified during root initialization (patricia_root_init).
static const u_int8_t * patricia_key (patroot *root, patnode *node)
 Obtains a pointer to the start of the key material for a patricia node.
static u_int8_t pat_key_test (const u_int8_t *key, u_int16_t bit)
 Performs a bit test on a key.
static u_int16_t patricia_length (patnode *node)
 Given a node, determines the key length in bytes.
static u_int16_t patricia_length_to_bit (u_int16_t length)
 Given the length of a key in bytes, converts it to patricia bit format.
static patnodepatricia_get_inline (patroot *root, u_int16_t key_bytes, const void *v_key)
 Finds an exact match for the specified key and key length.
static u_int8_t patricia_isempty (patroot *root)
 Determines if a patricia tree is empty.


Detailed Description

Patricia tree APIs.

This file contains the public data structures for the patricia tree package. This package is applicable to searching a non-overlapping keyspace of pseudo-random data with fixed size keys. The patricia tree is not balanced, so this package is NOT appropriate for highly skewed data. The package can deal with variable length (in byte increments) keys, but only when it can be guaranteed that no key in the tree is a prefix of another (null-terminated strings have this property if you include the '\0' in the key).

This package supports keys up to 256 bytes in length. For random data, all operations are O(log n). There are two necessary data structures: one is the root of a tree (type patroot), and the contents of this are hidden from you. The other is a node (type patnode). The contents of this data structure are (unfortunately) public to make the compiler happy.

To use this package: First imbed the patnode structure in your data structure. You have two choices for the key. The first is to embed the key into the data structure immediately following the patnode stucture, as in:

                struct foobar {
                    ...;
                    patnode patricia;
                    u_char  key[KEYSIZE];
                    ...;
                }

The other choice is to embed a pointer to the key material immediately following the data structure, as in

                struct blech {
                    ...;
                    patnode patricia;
                    sockaddr_un *key_ptr;
                    ...;
                }

In either case you can also specify an offset to the actual key material. The choice of key location and offset, and the length of keys stored in the tree if this is fixed, is specified in a call to patricia_root_init(). If no patroot pointer is passed in one is allocated and returned, otherwise the specified root pointer is filled in.

If you want to use your own allocate & free routines for patroots, set them using patricia_set_allocator().

For each node that you wish to add to the tree, you must first initialize the node with a call to patricia_node_init_length() with the node and the length of the associated key, in bytes. You can also call patricia_node_init() if the key length was fixed at root initialization. Then, once the key is installed in the node, you may call patricia_add(). Note that after calling patricia_add(), you may NOT change the key. You should also note that the entire key field to the length specified to patricia_length() (or all the way to `KEYSIZE' if the tree is built with fixed-length keys) may be examined.

Once the tree is initialized you can use the following functions:

patricia_add() patricia_delete() patricia_get() patricia_getnext() patricia_find_next() patricia_find_prev() patricia_subtree_match() patricia_subtree_next()

When you're done with the tree, you can call patricia_root_delete() on an empty tree to get rid of the root information if the root was allocated at initialization time.

Generally you will not want to deal with the patricia structure directly, so it's helpful to be able to be able to get back to the primary structure. This can be done with the PATNODE_TO_STRUCT() macro. Using this, you can then easily define functions which completely hide the patricia structure from the rest of your code. This is STRONGLY recommended.


Define Documentation

#define PATNODE_TO_CONS_STRUCT procname,
structname,
fieldname   ) 
 

Value:

static inline const structname *                                     \
procname (patnode *ptr)                                              \
{                                                                    \
    assert(STRUCT_SIZEOF(structname, fieldname) == sizeof(patnode)); \
    if (ptr) {                                                       \
        return ((const structname *) ((uchar *) ptr) -               \
            offsetof(structname, fieldname));                        \
    }                                                                \
    return NULL;                                                     \
}
Constant version of the macro to define an inline to map from a patnode entry back to the containing data structure.

#define PATNODE_TO_STRUCT procname,
structname,
fieldname   ) 
 

Value:

static inline structname * procname (patnode *ptr)\
    {\
        assert(STRUCT_SIZEOF(structname, fieldname) == sizeof(patnode));\
        if (ptr)\
            return(QUIET_CAST(structname *, ((u_char *) ptr) - \
                                    offsetof(structname, fieldname))); \
        return(NULL); \
     }
Macro to define an inline to map from a patnode entry back to the containing data structure.

This is just a handy way of defining the inline, which will return NULL if the patnode pointer is NULL, or the enclosing structure if not.

The assert() will be removed by the compiler unless your code is broken -- this is quite useful as a way to validate that you've given the right field for fieldname (a common mistake is to give the KEY field instead of the NODE field). It's harmless.

#define PATRICIA_LEN_TO_BIT len   )     ((u_int16_t) ((((len) - 1) << 8) | 0xff))
 

A macro to initialize the `length' in a patnode at compile time given the length of a key.

Good for the keyword tree. Note the length must be greater than zero.

#define PATRICIA_ROOT_INIT _rootptr,
_bool_key_is_ptr,
_nodestruct,
_nodeelement,
_keyelt   ) 
 

Value:

patricia_root_init(_rootptr, _bool_key_is_ptr,              \
                      STRUCT_SIZEOF(_nodestruct, _keyelt),             \
                      STRUCT_OFFSET(_nodestruct, _nodeelement, _keyelt))
Initialize a patricia root with a little more compile-time checking.

#define STRUCT_OFFSET _structure,
_elt1,
_elt2   ) 
 

Value:

(offsetof(_structure, _elt2) - (offsetof(_structure, _elt1) + \
                                      STRUCT_SIZEOF(_structure, _elt1)))
Returns the offset of _elt2 from the END of _elt1 within structure.


Typedef Documentation

typedef patroot*(* patricia_root_alloc_fn)(void)
 

Typedef for user-specified patroot allocation function.

See also:
patricia_set_allocator

typedef void(* patricia_root_free_fn)(patroot *)
 

Typedef for user-specified patroot free function.

See also:
patricia_set_allocator


Function Documentation

static u_int8_t pat_key_test const u_int8_t *  key,
u_int16_t  bit
[inline, static]
 

Performs a bit test on a key.

Parameters:
[in] key Pointer to key material
[in] bit Bit number to test
Returns:
1 if the bit was set, 0 otherwise.

boolean patricia_add patroot root,
patnode node
 

Adds a new node to the tree.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is successfully added; FALSE if the key you are adding is the same as, or overlaps with (variable length keys), something already in the tree.

int patricia_compare_nodes patroot root,
patnode left,
patnode right
 

Given two patricia tree nodes, determine if the first has a key which is numerically lesser, equal, or greater than the key of the second.

Parameters:
[in] root Pointer to patricia tree root
[in] left Pointer to patricia tree node
[in] right Pointer to patricia tree node
Returns:
Result of the comparison:
  • -1 if the key of the left node is numerically lesser than the right
  • 0 if the keys match
  • 1 if the left key is numerically greater than the right

const patnode* patricia_cons_find_next const patroot root,
const patnode node
 

Constant tree form of patricia_find_next().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if a match is not found; Otherwise a const pointer to the next patricia tree node.
See also:
patricia_find_next

const patnode* patricia_cons_find_prev const patroot root,
const patnode node
 

Constant tree form of patricia_find_prev().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if a match is not found; Otherwise a const pointer to the previous patricia tree node.
See also:
patricia_find_prev

const patnode* patricia_cons_get const patroot root,
const u_int16_t  key_bytes,
const void *  key
 

Constant tree form of patricia_get().

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
Returns:
NULL if a match is not found; Otherwise a const pointer to the matching patricia tree node.
See also:
patricia_get

const patnode* patricia_cons_subtree_match const patroot root,
const u_int16_t  prefix_len,
const void *  prefix
 

Constant tree form of patricia_subtree_match().

Parameters:
[in] root Pointer to patricia tree root
[in] prefix_len Length of prefix, in bits
[in] prefix Pointer to prefix
Returns:
NULL if no node in the tree has the prefix; Otherwise a pointer to the patricia tree node with the numerically smallest key which includes the prefix.
See also:
patricia_subtree_match

const patnode* patricia_cons_subtree_next const patroot root,
const patnode node,
const u_int16_t  prefix_len
 

Constant tree form of patricia_subtree_next().

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
[in] prefix_len Length of prefix, in bits
Returns:
A const pointer to next numerically larger patricia tree node.
See also:
patricia_subtree_next

boolean patricia_delete patroot root,
patnode node
 

Deletes a node from the tree.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is successfully deleted; FALSE if the specified node is not in the tree.

patnode* patricia_find_next patroot root,
patnode node
 

Given a node in the tree, find the node with the next numerically larger key.

If the given node is NULL, the numerically smallest node in the tree will be returned.

Note:
Good for tree walks.
Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if the specified node is already the largest; otherwise a pointer to the node with the next numerically larger key.

patnode* patricia_find_prev patroot root,
patnode node
 

Given a node in the tree, find the node with the next numerically smaller key.

If the given node is NULL, returns the numerically largest node in the tree.

Note:
The definitions of patricia_find_next() and patricia_find_prev() are such that
 node == patricia_find_prev(root, patricia_find_next(root, node));

will always be TRUE for any node in the tree or NULL.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
NULL if the specified node was the smallest; otherwise a pointer to the patricia tree node with next numerically smaller key.

patnode* patricia_get patroot root,
u_int16_t  key_bytes,
const void *  key
 

Looks up a node having the specified key and key length in bytes.

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
Returns:
NULL if a match is not found; otherwise a pointer to the matching patricia tree node

static patnode* patricia_get_inline patroot root,
u_int16_t  key_bytes,
const void *  v_key
[inline, static]
 

Finds an exact match for the specified key and key length.

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Length of the key in bytes
[in] v_key Key to match
Returns:
A pointer to the patnode containing the matching key; NULL if not found

patnode* patricia_getnext patroot root,
u_int16_t  key_bytes,
const void *  key,
boolean  return_eq
 

Given a key and key length in bytes, return a node in the tree which is at least as large as the key specified.

The call has a parameter which modifies its behaviour when an exact match is found in the tree; you can either choose to have it return the exact match, if there is one, or you can have it always return a node with a larger key (a la SNMP getnext).

Parameters:
[in] root Pointer to patricia tree root
[in] key_bytes Number of bytes in key
[in] key Pointer to key value
[in] return_eq FALSE for classic getnext
Returns:
A pointer to patricia tree node.

static u_int8_t patricia_isempty patroot root  )  [inline, static]
 

Determines if a patricia tree is empty.

Parameters:
[in] root Pointer to patricia tree root
Returns:
1 if the tree is empty, 0 otherwise.

static const u_int8_t* patricia_key patroot root,
patnode node
[inline, static]
 

Obtains a pointer to the start of the key material for a patricia node.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
Returns:
A pointer to the start of node key.

static u_int16_t patricia_length patnode node  )  [inline, static]
 

Given a node, determines the key length in bytes.

Parameters:
[in] node Pointer to patricia tree node
Returns:
The key length, in bytes.

static u_int16_t patricia_length_to_bit u_int16_t  length  )  [inline, static]
 

Given the length of a key in bytes, converts it to patricia bit format.

Parameters:
[in] length Length of a key, in bytes
Returns:
Patricia bit format or PAT_NOBIT if length is 0.

boolean patricia_node_in_tree const patnode node  ) 
 

Determines if a patricia tree node is contained within a tree.

Parameters:
[in] node Pointer to patricia tree node
Returns:
TRUE if the node is in the tree; FALSE otherwise.

static void patricia_node_init patnode node  )  [inline, static]
 

Initializes a patricia tree node using the the key length specified during root initialization (patricia_root_init).

Parameters:
[in] node Pointer to patricia tree node

void patricia_node_init_length patnode node,
u_int16_t  key_bytes
 

Initializes a patricia tree node using the key length specified by key_bytes.

If key_bytes is zero, then it falls back to the length specified during root initialization (patricia_root_init).

Parameters:
[in] node Pointer to patricia tree node
[in] key_bytes Length of the key, in bytes

void patricia_root_delete patroot root  ) 
 

Deletes a patricia tree root.

Note:
An assertion failure will occur if the tree is not empty when this function is called.
Parameters:
[in] root Pointer to patricia tree root

patroot* patricia_root_init patroot root,
boolean  key_is_ptr,
u_int16_t  key_bytes,
u_int8_t  key_offset
 

Initializes a patricia tree root.

Parameters:
[in] root Pointer to patricia tree root
[in] key_is_ptr Indicator that the key located at the offset is actually a pointer or not
[in] key_bytes Number of bytes in the key
[in] key_offset Offset to the key from the end of the patricia tree node structure
Returns:
A pointer to the patricia tree root.

void patricia_set_allocator patricia_root_alloc_fn  my_alloc,
patricia_root_free_fn  my_free
 

Sets allocation and free routines for patricia tree root structures.

Note:
The initialization APIs contained in libjunos-sdk or libmp-sdk may use Patricia tree functionality. Therefore, if you intend to change the allocator, this function should be called before any libjunos-sdk or libmp-sdk APIs are used in the JUNOS SDK application.
Parameters:
[in] my_alloc Function to call when patricia tree root is allocated
[in] my_free Function to call when patricia tree root is freed

patnode* patricia_subtree_match patroot root,
u_int16_t  prefix_len,
const void *  prefix
 

Given a prefix and a prefix length in bits, find the node with the numerically smallest key in the tree which includes this prefix.

Parameters:
[in] root Pointer to patricia tree root
[in] prefix_len Length of prefix, in bits
[in] prefix Pointer to prefix
Returns:
NULL if no node in the tree has the prefix; otherwise a pointer to the patricia tree node with the numerically smallest key which includes the prefix.

patnode* patricia_subtree_next patroot root,
patnode node,
u_int16_t  prefix_len
 

Given a node in the tree, and a prefix length in bits, return the next numerically larger node in the tree which shares a prefix with the node specified.

Parameters:
[in] root Pointer to patricia tree root
[in] node Pointer to patricia tree node
[in] prefix_len Length of prefix, in bits
Returns:
A pointer to next numerically larger patricia tree node.


2007-2009 Juniper Networks, Inc. All rights reserved. The information contained herein is confidential information of Juniper Networks, Inc., and may not be used, disclosed, distributed, modified, or copied without the prior written consent of Juniper Networks, Inc. in an express license. This information is subject to change by Juniper Networks, Inc. Juniper Networks, the Juniper Networks logo, and JUNOS are registered trademarks of Juniper Networks, Inc. in the United States and other countries. All other trademarks, service marks, registered trademarks, or registered service marks are the property of their respective owners.
Generated on Sun May 30 20:24:32 2010 for libjuniper by Doxygen 1.4.5