TrieNode< A, Payload > Class Template Reference

TrieNode definition. More...

#include <trie.hh>

List of all members.

Public Types
typedef IPNet< A >	Key
typedef MiniTraits< Payload > ::NonConst	PPayload
Public Member Functions
	TrieNode ()
	Constructors.
	TrieNode (const Key &key, const Payload &p, TrieNode *up=0)
	TrieNode (const Key &key, TrieNode *up=0)
TrieNode *	erase ()
	erase current node, replumb.
TrieNode *	find (const Key &key)
	main search routine.
const TrieNode *	const_find (const Key &key) const
TrieNode *	find_subtree (const Key &key)
	aux search routine.
TrieNode *	lower_bound (const Key &key)
	Given a key, find the node with that key and a payload.
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 ()
	helper function to delete an entire subtree (including the root).
void	validate (const TrieNode *parent) const
	debugging, validates a node by checking pointers and Key invariants.
TrieNode *	leftmost ()
void	find_bounds (const A &a, A &lo, A &hi) const
A	low () const
A	high () const
Static Public Member Functions
static TrieNode *	insert (TrieNode **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
Private Attributes
TrieNode *	_up
TrieNode *	_left
TrieNode *	_right
Key	_k
PPayload *	_p

---

Detailed Description

template<class A, class Payload>
class TrieNode< A, Payload >

TrieNode definition.

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.

---

Member Function Documentation

template<class A , class Payload >

TrieNode< A, Payload > * TrieNode< 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 >

TrieNode< A, Payload > * TrieNode< 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 TrieNode< 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 >

TrieNode< A, Payload > * TrieNode< 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 TrieNode< 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 >

TrieNode< A, Payload > * TrieNode< A, Payload >::insert	(	TrieNode< 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 >

TrieNode* TrieNode< A, Payload >::leftmost

(

)

[inline]

Returns:

the leftmost node under this node

template<class A , class Payload >

A TrieNode< 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 >

TrieNode< A, Payload > * TrieNode< 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:

• /home/greearb/git/xorp.ct.github/xorp/libxorp/trie.hh