class Trie

The Trie itself More...

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

Public Types

Public Methods


Detailed Description

The Trie 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.

typedef IPNet<A> Key

Key

typedef TrieIterator<A,Payload> iterator

iterator

typedef TrieNode<A,Payload> Node

Node

 Trie ()

Trie

stl map interface

 ~Trie ()

~Trie

iterator  insert (const Key & net, const Payload& p)

insert

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.

void  erase (const Key &k)

erase

delete the node with the given key.

void  erase (iterator i)

erase

delete the node pointed by the iterator.

iterator  find (const Key &k)

find

[const]

given a key, returns an iterator to the entry with the longest matching prefix.

iterator  find (const A& a)

find

[const]

given an address, returns an iterator to the entry with the longest matching prefix.

iterator  lower_bound (const Key &k)

lower_bound

[const]

iterator  begin ()

begin

[const]

const iterator  end ()

end

[const]

void  delete_all_nodes ()

delete_all_nodes

iterator  lookup_node (const Key & k)

lookup_node

[const]

lookup a subnet, must return exact match if found, end() if not.

iterator  search_subtree (const Key &key)

search_subtree

[const]

returns an iterator to the subtree rooted at or below the key passed as parameter.

iterator  find_less_specific (const Key &key)

find_less_specific

[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. Implemented as a find() with a less specific key.

void  find_bounds (const A& a, A &lo, A &hi)

find_bounds

[const]

return the lower and higher address in the range that contains a and would map to the same route.

A  find_lower_bound (const A a)

find_lower_bound

[const]

A  find_higher_bound (const A a)

find_higher_bound

[const]

int  route_count ()

route_count

[const]

void  print ()

print

[const]


Generated by: pavlin on possum.icir.org on Mon Mar 10 19:34:43 2003, using kdoc 2.0a54+XORP.