class TrieNode TrieNode definition. More... Definition #include <trie.hh> Template form TrieNode<class A, class Payload> List of all Methods

Annotated List Files Globals Hierarchy Index

Public Types

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

Public Methods

•  TrieNode ()
•  TrieNode (const Key& key, const Payload& p, TrieNode* up = 0)
• explicit  TrieNode (const Key& key, TrieNode* up = 0)
•  ~TrieNode ()
• TrieNode * erase ()
• TrieNode * find (const Key& key)
• const TrieNode * const_find (const Key& key) const
• TrieNode * find_subtree (const Key &key)
• TrieNode*  lower_bound (const Key &key)
• TrieNode*  get_left ()
• TrieNode*  get_right ()
• TrieNode*  get_parent ()
• bool  has_payload () const
• const Payload & const_p () const
• Payload & p ()
• void  set_payload (const Payload& p)
• const Key & k () const
• void  print (int indent, const char *msg) const
• string  str () const
• void  delete_subtree ()
• void  validate (const TrieNode *parent) const
• TrieNode *  leftmost ()
• void  find_bounds (const A& a, A &lo, A &hi) const
• A  low () const
• A  high () const

Public Static Methods

• static TrieNode * insert (TrieNode **root, const Key& key, const Payload& p, bool& replaced)

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.

Constructors

[static]

add a node to a subtree

Returns: a pointer to the node.

erase current node, replumb. Returns the new root.

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

[const]

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

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.

[const]

[const]

[const]

[const]

[const]

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

[const]

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

Returns: the leftmost node under this node

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

[const]

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

[const]

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