class RefTrieNode

RefTrieNode definition. More...

Definition#include <ref_trie.hh>
Template formRefTrieNode<class A, class Payload>
List of all Methods
Annotated List
Files
Globals
Hierarchy
Index

Public Types

Public Methods

Public Static Methods


Detailed Description

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.

typedef IPNet<A> Key

Key

typedef MiniTraits<Payload>::NonConst PPayload

PPayload

 RefTrieNode ()

RefTrieNode

Constructors

 RefTrieNode (const Key& key, const Payload& p, RefTrieNode* up = 0)

RefTrieNode

 RefTrieNode (const Key& key, RefTrieNode* up = 0)

RefTrieNode

 ~RefTrieNode ()

~RefTrieNode

RefTrieNodeinsert (RefTrieNode **root, const Key& key, const Payload& p, bool& replaced)

insert

[static]

add a node to a subtree

Returns: a pointer to the node.

RefTrieNodeerase ()

erase

erase current node, replumb. Returns the new root.

RefTrieNodefind (const Key& key)

find

main search routine. Given a key, returns a node.

const RefTrieNodeconst_find (const Key& key)

const_find

[const]

RefTrieNodefind_subtree (const Key &key)

find_subtree

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

RefTrieNode*  lower_bound (const Key &key)

lower_bound

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

bool  has_payload ()

has_payload

[const]

bool  has_active_payload ()

has_active_payload

[const]

const Payload & const_p ()

const_p

[const]

Payload & p ()

p

void  set_payload (const Payload& p)

set_payload

uint32_t  references ()

references

[const]

void  incr_refcount ()

incr_refcount

void  decr_refcount ()

decr_refcount

bool  deleted ()

deleted

[const]

const Key & k ()

k

[const]

void  print (int indent, const char *msg)

print

[const]

string  str ()

str

[const]

void  delete_subtree ()

delete_subtree

helper function to delete an entire subtree (including the root).

void  validate (const RefTrieNode *parent)

validate

[const]

debugging, validates a node by checking pointers and Key invariants.

bool  is_left ()

is_left

[const]

helper methods for iterators. Visit order: start from the leaves and then go up. begin() moves to the first node we want to explore, which is the leftmost node in the subtree. next() finds the 'next' node in the visit order. Invariant for next(): being on _cur means that we have visited its subtrees (and the node itself, of course, which is the current one).

RefTrieNodeleftmost ()

leftmost

RefTrieNodebegin ()

begin

RefTrieNodenext (const Key &root)

next

void  find_bounds (const A& a, A &lo, A &hi)

find_bounds

[const]

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

Returns: the boundaries ("lo" and "hi") of the largest range that contains 'a' and maps to the same route entry.

A  low ()

low

[const]

Returns: the lowest address in a subtree which has a route. Search starting from left or right until a full node is found.

A  high ()

high

[const]

Returns: the highest address in a subtree which has a route. Search starting from right or left until a full node is found.


Generated by: pavlin on possum.icir.org on Mon Jun 9 13:23:43 2003, using kdoc 2.0a54+XORP.