class TrieNode

TrieNode definition. More...

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

Public Types

Public Methods

Public Static Methods


Detailed Description

TrieNode's are the elements of a Trie. 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

 TrieNode ()

TrieNode

Constructors

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

TrieNode

explicit  TrieNode (const Key& key, TrieNode* up = 0)

TrieNode

 ~TrieNode ()

~TrieNode

TrieNodeinsert (TrieNode **root, const Key& key, const Payload& p, bool& replaced)

insert

[static]

add a node to a subtree

Returns: a pointer to the node.

TrieNodeerase ()

erase

erase current node, replumb. Returns the new root.

TrieNodefind (const Key& key)

find

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

const TrieNodeconst_find (const Key& key)

const_find

[const]

TrieNodefind_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.

TrieNode*  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.

TrieNode*  get_left ()

get_left

TrieNode*  get_right ()

get_right

TrieNode*  get_parent ()

get_parent

bool  has_payload ()

has_payload

[const]

const Payload & const_p ()

const_p

[const]

Payload & p ()

p

void  set_payload (const Payload& p)

set_payload

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 TrieNode *parent)

validate

[const]

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

TrieNode *  leftmost ()

leftmost

Returns: the leftmost node under this node

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 Thu Aug 28 12:51:57 2003, using kdoc 2.0a54+XORP.