radix.h File Reference

Radix best match tree APIs. More...


Data Structures

struct  rnode_
 A radix node. More...
union  radix_ptr_
 Child pointers in internal structures in a radix tree can in general point either at external nodes or at internal nodes. More...
struct  radix_root_
 The root of the tree. More...
struct  rinode_
 An internal node. More...

Defines

#define RINF_ATTACHED   0x1
 node has attached external rnode
#define RINF_LEXT   0x2
 left pointer points at external
#define RINF_LINVALID   0x4
 left pointer points at attached
#define RINF_LEFT   (RINF_LEXT|RINF_LINVALID)
#define RINF_REXT   0x8
 right pointer points at external
#define RINF_RINVALID   0x10
 right pointer points at attached
#define RINF_RIGHT   (RINF_REXT|RINF_RINVALID)

Typedefs

typedef rnode_ rnode_t
 A radix node.
typedef radix_ptr_ radix_ptr_t
 Child pointers in internal structures in a radix tree can in general point either at external nodes or at internal nodes.
typedef radix_root_ radix_root_t
 The root of the tree.
typedef rinode_ rinode_t
 An internal node.

Functions

radix_root_tradix_init_root (radix_root_t *root)
 Initialize the root structure for the tree.
void radix_delete_root (radix_root_t *root)
 Delete the root data structure which was allocated by radix_init_root().
void radix_node_init (rnode_t *rnode, u_int16_t prefix_len, u_int16_t instance)
 Initializes the prefix_len and instance values in the radix node.
status_t radix_add (radix_root_t *root, rnode_t *rnode_to_add)
 Add an external node to the tree.
void radix_delete (radix_root_t *root, rnode_t *rnode_to_delete)
 Delete an external node from the tree.
rnode_tradix_lookup (radix_root_t *root, u_int8_t *key)
 Given a pointer to the key, lookup and return the node with longest matching prefix.
rnode_tradix_find_next (radix_root_t *root, rnode_t *rnode)
 Given a node in the tree, find the next node which prefix is numerically larger.
rnode_tradix_find_next_instance (radix_root_t *root, rnode_t *rnode)
 Given a node in the tree, find the next node which has the same prefix and a larger instance number.
rnode_tradix_find_prev (radix_root_t *root, rnode_t *rnode)
 Given a node in the tree, find the previous node for which prefix is numerically smaller.
rnode_tradix_find_prev_instance (radix_root_t *root, rnode_t *rnode)
 Given a node in the tree, find the previous node which has the same prefix and a smaller instance number.
rnode_tradix_get (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix)
 Given a key and prefix length, return the node that matches exactly.
rnode_tradix_get_instance (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix, u_int16_t instance)
 Given a key, prefix length, and instance number, return the node that matches exactly.
rnode_tradix_getnext (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix)
 Given a key and prefix lenghth, find the next node which the key is numerically larger.
rnode_tradix_getnext_instance (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix, u_int16_t instance)
 Given a key and prefix length, find the next node that has the same key but a larger instance number.
rnode_tradix_match (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix)
 Given a key and prefix length, return the node with the longest matching prefix.
rnode_tradix_match_instance (radix_root_t *root, u_int16_t prefix_len, u_int8_t *prefix, u_int16_t instance)
 Given a key and prefix length, return the node with the longest matching prefix and the specified instance number.
void radix_sanity (radix_root_t *root, u_int16_t max_prefix_len)
 Given a radix tree root, analize the data structure for inconsistencies.
static u_int8_t radix_bit_test (u_int8_t *key, u_int16_t bit)
 Bit numbers, as used above, number bits with bit 0 being the most significant bit of the prefix.
static u_int16_t radix_find_difference (u_int8_t *p1, u_int8_t *p2, u_int16_t len)
 Find the first bit of difference between two prefixes.
static rnode_tradix_lookup_inline (radix_root_t *root, u_int8_t *key)
 An inline best match lookup routine.

Variables

const u_int8_t radix_bit_index []


Detailed Description

Radix best match tree APIs.

Note:
When using radix.h in conjunction with libmsp-svcs in the same application, you must list ${LIBJUNIPER} before ${LIBMSP-SVCS} in the DPLIBS list.

Typedef Documentation

typedef union radix_ptr_ radix_ptr_t
 

Child pointers in internal structures in a radix tree can in general point either at external nodes or at internal nodes.

The following union is used for such pointers.

typedef struct radix_root_ radix_root_t
 

The root of the tree.

This structure mostly exists so that we have a well-understood place to store the tree root pointer, since this will change as entries are added to and deleted from the tree. We also keep statistics about how much data structure the tree is consuming, mostly for our own edification.

Note that normally the tree root will point at an internal node. Only in the special case that there is a single prefix in the tree will the root point directly at an rnode. We detect this case by looking at the internal_nodes total; the root will only point at an external node directly if there are no internal nodes in the tree.

typedef struct rinode_ rinode_t
 

An internal node.

This is the structure which glues the internals of the tree together. This really should be private to the implementation, and should be treated as such, but is exposed here to avoid the use of void pointers above and to allow inline searches to be written.

It is the case that in normal trees very few internal nodes have attached routes. There is hence a 20% savings of memory to be gained by only allocating the attached pointer when it is actually needed.

typedef struct rnode_ rnode_t
 

A radix node.

This is the structure that gets imbedded in the thing you are storing in the radix tree, the moral equivalent to a patnode_t. In the current incarnation the prefix data needs to immediately follow this in the superstructure, something like

struct foo { ...stuff...; rnode_t rnode; u_int32_t prefix[4]; ...stuff...; };

Note that the tree potentially allows more than one rnode having a particular prefix to be stored in the tree simultaneously, with these being distinguished by the `instance' structure member. Rnodes with the same prefix are chained together through the `next' pointer, and are always sorted by ascending `instance'. If you don't want to store multiple instances of the same prefix in the tree, always specify the instance as zero. If, on the other hand, you wanted to use the instance because you were storing interface destination prefixes in the tree, and there was no guarantee that the same prefix wouldn't be configured on more than one interface (there is no such guarantee) so you needed to differentiate different instances of the same prefix, then using the instance as an ifindex would probably do about the right thing.


Function Documentation

status_t radix_add radix_root_t root,
rnode_t rnode_to_add
 

Add an external node to the tree.

The node's prefix length and instance must have been previously initialized.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode_to_add Pointer to the radix node to add
Returns:
Status code
  • 0 Successfully added node
  • EEXIST Node with a matching prefix/instance is already installed in the tree
  • ENOMEM Out of memory

static u_int8_t radix_bit_test u_int8_t *  key,
u_int16_t  bit
[inline, static]
 

Bit numbers, as used above, number bits with bit 0 being the most significant bit of the prefix.

That is, bit number 17 will be the first bit not covered by a /17 prefix. The following tests a bit in a key given a bit number.

void radix_delete radix_root_t root,
rnode_t rnode_to_delete
 

Delete an external node from the tree.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode_to_delete Pointer to the radix node to delete

void radix_delete_root radix_root_t root  ) 
 

Delete the root data structure which was allocated by radix_init_root().

Note:
The tree must be empty when this function is called.
Parameters:
[in] root Pointer to the root data structure of the tree

rnode_t* radix_find_next radix_root_t root,
rnode_t rnode
 

Given a node in the tree, find the next node which prefix is numerically larger.

If the specified node is NULL, the function returns the node with the smallest prefix.

Note:
The first instance in the chain is always returned, regardless of the number of instances in the tree. in the chain.
Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode Pointer to the node to start at
Returns:
A pointer to the next node on success, NULL on failure

rnode_t* radix_find_next_instance radix_root_t root,
rnode_t rnode
 

Given a node in the tree, find the next node which has the same prefix and a larger instance number.

If the next instance doesn't exist, it will find the next node that has a larger prefix. If the specified node is NULL, the node with the smallest prefix is returned.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode Pointer to the node to start at
Returns:
A pointer to the next node instance on success, NULL on failure

rnode_t* radix_find_prev radix_root_t root,
rnode_t rnode
 

Given a node in the tree, find the previous node for which prefix is numerically smaller.

If the specified node is NULL, the function returns the node with the largest prefix.

Note:
The first instance in the chain is always returned, regardless of the number of instances in the tree.
Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode Pointer to the node to start at
Returns:
A pointer to the previous node on success, NULL on failure

rnode_t* radix_find_prev_instance radix_root_t root,
rnode_t rnode
 

Given a node in the tree, find the previous node which has the same prefix and a smaller instance number.

If the previous instance doesn't exist, it will find the previous node that has a smaller prefix. If the specified node is NULL, the node with the largest prefix is returned.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] rnode Pointer to the node to start at
Returns:
A pointer to the previous node on success, NULL on failure

rnode_t* radix_get radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix
 

Given a key and prefix length, return the node that matches exactly.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the key
Returns:
A pointer to the matching node on success, NULL on failure

rnode_t* radix_get_instance radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix,
u_int16_t  instance
 

Given a key, prefix length, and instance number, return the node that matches exactly.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the key
[in] instance Instance number
Returns:
A pointer to the matching node on success, NULL on failure

rnode_t* radix_getnext radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix
 

Given a key and prefix lenghth, find the next node which the key is numerically larger.

Note:
The first instance in the chain is always returned, regardless of the number of instances in the tree.
Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the key
Returns:
A pointer to the next node instance on success, NULL on failure

rnode_t* radix_getnext_instance radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix,
u_int16_t  instance
 

Given a key and prefix length, find the next node that has the same key but a larger instance number.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the key
[in] instance Instance number
Returns:
A pointer to the larger node instance on success, NULL on failure

radix_root_t* radix_init_root radix_root_t root  ) 
 

Initialize the root structure for the tree.

If root argument is specified as NULL, a structure will be allocated and returned.

Parameters:
[in] root Pointer to the root data structure of the tree
Returns:
A pointer to the root data structure for the tree

rnode_t* radix_lookup radix_root_t root,
u_int8_t *  key
 

Given a pointer to the key, lookup and return the node with longest matching prefix.

The specified key is assumed to be at least as long as the longest matching prefix in the tree, use radix_match() if this might not be true.

Note:
Available as an inline version named radix_lookup_inline().
Parameters:
[in] root Pointer to the root data structure of the tree
[in] key Pointer to the key
Returns:
A pointer to the node on success, NULL on failure
See also:
radix_match, radix_lookup_inline

static rnode_t* radix_lookup_inline radix_root_t root,
u_int8_t *  key
[inline, static]
 

An inline best match lookup routine.

This assumes that the key being searched for is guaranteed to be at least as long as any prefix in the tree. Use radix_match() if this can't be guaranteed. Use radix_match_instance() if you also need to do an instance-sensitive lookup.

rnode_t* radix_match radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix
 

Given a key and prefix length, return the node with the longest matching prefix.

The returned prefix length will always be less than or equal to the specified prefix length.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the prefix
Returns:
A pointer to the matched node on success, NULL on failure

rnode_t* radix_match_instance radix_root_t root,
u_int16_t  prefix_len,
u_int8_t *  prefix,
u_int16_t  instance
 

Given a key and prefix length, return the node with the longest matching prefix and the specified instance number.

The returned prefix length will always be less than or equal to the specified prefix length.

Parameters:
[in] root Pointer to the root data structure of the tree
[in] prefix_len Prefix length
[in] prefix Pointer to the key
[in] instance Instance number
Returns:
A pointer to the matched node on success, NULL on failure

void radix_node_init rnode_t rnode,
u_int16_t  prefix_len,
u_int16_t  instance
 

Initializes the prefix_len and instance values in the radix node.

Parameters:
[in] rnode Pointer to the radix node
[in] prefix_len Prefix length
[in] instance Instance number

void radix_sanity radix_root_t root,
u_int16_t  max_prefix_len
 

Given a radix tree root, analize the data structure for inconsistencies.

The following checks will be performed:

  • making sure all parent pointers in child nodes point at the guy who thinks the node is a child,
  • making sure that flags on internal nodes are sane,
  • making sure that the maximum prefix length expected for the tree is not exceeded,
  • making sure all prefix lengths and prefixes in external node chains are identical, that instances are sorted in ascending order and that parent pointers are identical,
  • making sure that attached external nodes have a prefix length equal to the bit number of the node they are attached to,
  • making sure all child nodes have a bit number/prefix length which is larger than that of their parent,
  • making sure all prefixes match overlapping prefixes higher up in the tree, if any, and
  • making sure a walk of the tree returns prefixes which are consistently numerically increasing.
Note:
If the maximum prefix length is unknown, setting it to zero will do the right thing.
Parameters:
[in] root Pointer to the root data structure of the tree
[in] max_prefix_len Prefix length


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