xorp

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:
 All Classes Namespaces Functions Variables Typedefs Enumerations