RefTrie< A, Payload > Class Template Reference

The RefTrie itself. More...

#include <ref_trie.hh>

List of all members.

Public Types
typedef IPNet< A >	Key
typedef RefTrieNode< A, Payload >	Node
typedef RefTriePostOrderIterator< A, Payload >	iterator
typedef RefTriePostOrderIterator< A, Payload >	PostOrderIterator
typedef RefTriePreOrderIterator< A, Payload >	PreOrderIterator
Public Member Functions
	RefTrie ()
	stl map interface
void	delete_self ()
void	set_root (Node *root)
iterator	insert (const Key &net, const Payload &p)
	insert a key, payload pair, returns an iterator to the newly inserted node.
void	erase (const Key &k)
	delete the node with the given key.
void	erase (iterator i)
	delete the node pointed by the iterator.
iterator	find (const Key &k) const
	given a key, returns an iterator to the entry with the longest matching prefix.
iterator	find (const A &a) const
	given an address, returns an iterator to the entry with the longest matching prefix.
iterator	lower_bound (const Key &k) const
iterator	begin () const
const iterator	end () const
void	delete_all_nodes ()
iterator	lookup_node (const Key &k) const
	lookup a subnet, must return exact match if found, end() if not.
iterator	search_subtree (const Key &key) const
	returns an iterator to the subtree rooted at or below the key passed as parameter.
iterator	find_less_specific (const Key &key) const
	find_less_specific asks the question: if I were to add this net to the trie, what would be its parent node? net may or may not already be in the trie.
void	find_bounds (const A &a, A &lo, A &hi) const
	return the lower and higher address in the range that contains a and would map to the same route.
int	route_count () const
void	print () const
string	str () const
Private Member Functions
void	validate ()
Private Attributes
Node *	_root
int	_payload_count
bool	_deleted
	RefTrie's nodes are reference counted, so it's possible to delete all the nodes in the trie, and for the actually routes to remain around until their reference counts go to zero because iterators still point at a node.

---

Detailed Description

template<class A, class Payload>
class RefTrie< A, Payload >

The RefTrie itself.

The trie support insertion and deletion of Key,Payload pairs, and lookup by Key (which can be an address or a subnet).

Additional methods are supported to provide access via iterators.

---

Member Function Documentation

template<class A, class Payload>

iterator RefTrie< A, Payload >::find_less_specific

(

const Key &

key

)

const [inline]

find_less_specific asks the question: if I were to add this net to the trie, what would be its parent node? net may or may not already be in the trie.

Implemented as a find() with a less specific key.

template<class A, class Payload>

iterator RefTrie< A, Payload >::insert	(	const Key &	net,
		const Payload &	p
	)		[inline]

insert a key, payload pair, returns an iterator to the newly inserted node.

Prints a warning message if the new entry overwrites an existing full node.

---

Member Data Documentation

template<class A, class Payload>

bool RefTrie< A, Payload >::_deleted [private]

RefTrie's nodes are reference counted, so it's possible to delete all the nodes in the trie, and for the actually routes to remain around until their reference counts go to zero because iterators still point at a node.

If you then delete the trie itself, the nodes will be deleted but the iterator will be invalidated. Instead delete_self() should be called, which sets _deleted, and only finally deletes the trie when all the nodes themselves have gone away.

---

The documentation for this class was generated from the following file:

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