class Trie

The Trie itself More...

 
LOGO
 Annotated List  Files  Globals  Hierarchy  Index  Top

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

Node

typedef __Iterator iterator

iterator

 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  unbind_root (iterator i)

unbind_root

[const]

Set root node associated with iterator to the root node of the trie. Needed whilst trie iterators have concept of root nodes find methods return iterators with root bound to key and means they can never continue iteration beyond of root.

Returns: iterator with non-restricted root node.

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 Wed Apr 13 21:52:49 2005, using kdoc $.