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_LEXTRINF_LINVALID) 
#define  RINF_REXT 0x8 
right pointer points at external  
#define  RINF_RINVALID 0x10 
right pointer points at attached  
#define  RINF_RIGHT (RINF_REXTRINF_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_t *  radix_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_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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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_t *  radix_lookup_inline (radix_root_t *root, u_int8_t *key) 
An inline best match lookup routine.  
Variables  
const u_int8_t  radix_bit_index [] 
${LIBJUNIPER}
before ${LIBMSPSVCS}
in the DPLIBS
list.

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. 

The root of the tree. This structure mostly exists so that we have a wellunderstood 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. 

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. 

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. 

Add an external node to the tree. The node's prefix length and instance must have been previously initialized.


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. 

Delete an external node from the tree.


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


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


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


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


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


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


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


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


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


Initialize the root structure for the tree.
If root argument is specified as


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.


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 instancesensitive lookup. 

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.


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.


Initializes the prefix_len and instance values in the radix node.


Given a radix tree root, analize the data structure for inconsistencies. The following checks will be performed:
