xorp

RefTrieNode< A, Payload > Class Template Reference

RefTrieNode definition. More...

#include <ref_trie.hh>

List of all members.

Public Types

typedef IPNet< A > Key
typedef MiniTraits< Payload >
::NonConst 
PPayload

Public Member Functions

 RefTrieNode ()
 Constructors.
 RefTrieNode (const Key &key, const Payload &p, RefTrieNode *up=0)
 RefTrieNode (const Key &key, RefTrieNode *up=0)
RefTrieNodeerase ()
 erase current node, replumb.
RefTrieNodefind (const Key &key)
 main search routine.
const RefTrieNodeconst_find (const Key &key) const
RefTrieNodefind_subtree (const Key &key)
 aux search routine.
RefTrieNodelower_bound (const Key &key)
 Given a key, find the node with that key and a payload.
RefTrieNodeget_left ()
RefTrieNodeget_right ()
RefTrieNodeget_parent ()
bool has_payload () const
bool has_active_payload () const
const Payload & const_p () const
Payload & p ()
void set_payload (const Payload &p)
uint32_t references () const
void incr_refcount ()
void decr_refcount ()
bool deleted () const
const Keyk () const
void print (int indent, const char *msg) const
string str () const
void delete_subtree ()
 helper function to delete an entire subtree (including the root).
void validate (const RefTrieNode *parent) const
 debugging, validates a node by checking pointers and Key invariants.
bool is_left () const
RefTrieNodeleftmost ()
void find_bounds (const A &a, A &lo, A &hi) const
low () const
high () const

Static Public Member Functions

static RefTrieNodeinsert (RefTrieNode **root, const Key &key, const Payload &p, bool &replaced)
 add a node to a subtree

Private Member Functions

void delete_payload (Payload *p)
void dump (const char *msg) const
template<>
void delete_payload (const ChainedSubnetRoute< IPv4 > *p)
template<>
void delete_payload (const ChainedSubnetRoute< IPv6 > *p)
template<>
void delete_payload (const SubnetRoute< IPv4 > *p)
template<>
void delete_payload (const SubnetRoute< IPv6 > *p)

Private Attributes

RefTrieNode_up
RefTrieNode_left
RefTrieNode_right
Key _k
PPayload * _p
uint32_t _references

Detailed Description

template<class A, class Payload>
class RefTrieNode< A, Payload >

RefTrieNode definition.

RefTrieNode's are the elements of a RefTrie. Each node is associated to a Key and possibly a Payload. Nodes with a Payload ("full") can have 0, 1 or 2 children. Nodes without a Payload ("empty") can only be internal nodes, and MUST have 2 children (or they have no reason to exist).

Children have a Key which is strictly contained in their parent's Key -- more precisely, they are in either the left or the right half of the parent's Key. The branch to which a child is attached (left or right) is defined accordingly.


Member Function Documentation

template<class A , class Payload >
RefTrieNode< A, Payload > * RefTrieNode< A, Payload >::erase ( )

erase current node, replumb.

Remove this node, cleanup useless internal nodes.

Returns the new root.

Returns:
a pointer to the root of the trie.
template<class A , class Payload >
RefTrieNode< A, Payload > * RefTrieNode< A, Payload >::find ( const Key key)

main search routine.

Finds the most specific entry in the subtree rooted at r that contains the desired key and has a Payload.

Given a key, returns a node.

template<class A , class Payload >
void RefTrieNode< A, Payload >::find_bounds ( const A &  a,
A &  lo,
A &  hi 
) const [inline]
Returns:
the boundaries ("lo" and "hi") of the largest range that contains 'a' and maps to the same route entry.

Algorithm:

		n = find(a);
 		if we have no route (hence no default), provide a fake 0/0;
		set lo and hi to the boundaries of the current node.
 if n.is_a_leaf() we are done (results are the extremes of the entry)
 Otherwise: we are in an intermediate node, and a can be in positions
 1..5 if the node has 2 children, or 1'..3' if it has 1 child.
	n:		|---------------.----------------|
  a:                1    2        3      4     5
                       |--X--|         |--Y--|
  a:                1'    2'        3'
                       |--X--|
 Behaviour is the following:
  case 1 and 1':	lo already set, hi = (lowest address in X)-1
  case 2 and 2': set n = X and repeat
  case 3: lo = (highest addr in X)+1, hi = (lowest addr in Y)-1
  case 3': lo = (highest addr in X)+1, hi is already set
  case 4: set n = Y and repeat
  case 5:	lo = (highest addr in Y)+1, hi is already set
 
template<class A , class Payload >
RefTrieNode< A, Payload > * RefTrieNode< A, Payload >::find_subtree ( const Key key)

aux search routine.

Finds the subtree of key.

Given a key, returns a subtree contained in the key, irrespective of the presence of a payload in the node.

template<class A , class Payload >
A RefTrieNode< A, Payload >::high ( ) const [inline]
Returns:
the highest address in a subtree which has a route. Search starting from right or left until a full node is found.
template<class A , class Payload >
RefTrieNode< A, Payload > * RefTrieNode< A, Payload >::insert ( RefTrieNode< A, Payload > **  root,
const Key x,
const Payload &  p,
bool &  replaced 
) [static]

add a node to a subtree

add subnet/payload to the tree at *root.

Returns:
a pointer to the node.
a pointer to the newly inserted node.
template<class A , class Payload >
bool RefTrieNode< A, Payload >::is_left ( ) const [inline]
Returns:
the leftmost node under this node
template<class A , class Payload >
A RefTrieNode< A, Payload >::low ( ) const [inline]
Returns:
the lowest address in a subtree which has a route. Search starting from left or right until a full node is found.
template<class A , class Payload >
RefTrieNode< A, Payload > * RefTrieNode< A, Payload >::lower_bound ( const Key key)

Given a key, find the node with that key and a payload.

See the comment in the class definition.

If the next doesn't exist or does not have a payload, find the next node in the iterator sequence. XXX check the description.


The documentation for this class was generated from the following file:
 All Classes Namespaces Functions Variables Typedefs Enumerations