xorp

Trie< A, Payload, __Iterator > Class Template Reference

The trie stores BGP update packets the trie index is the NLRI. More...

#include <trie.hh>

List of all members.

Public Types

typedef RealTrie< IPv4 >
::TreeWalker 
TreeWalker_ipv4
typedef RealTrie< IPv6 >
::TreeWalker 
TreeWalker_ipv6
typedef XorpCallback2< void,
const UpdatePacket *, const
TimeVal & >::RefPtr 
ReplayWalker
typedef IPNet< A > Key
typedef TrieNode< A, Payload > Node
typedef __Iterator iterator

Public Member Functions

const UpdatePacketlookup (const string &net) const
const UpdatePacketlookup (const IPv4Net &net) const
const UpdatePacketlookup (const IPv6Net &net) const
void process_update_packet (const TimeVal &tv, const uint8_t *buf, size_t len, const BGPPeerData *peerdata)
void tree_walk_table (const TreeWalker_ipv4 &tw) const
void tree_walk_table (const TreeWalker_ipv6 &tw) const
void replay_walk (const ReplayWalker uw, const BGPPeerData *peerdata) const
 Generate the set of update packets that would totally populate this trie.
uint32_t update_count ()
uint32_t changes ()
void set_warning (bool warning)
 Trie ()
 stl map interface
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 unbind_root (iterator i) const
 Set root node associated with iterator to the root node of the trie.
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
template<>
void get_heads (RealTrie< IPv4 > *&head, RealTrie< IPv4 > *&del)
template<>
void get_heads (RealTrie< IPv6 > *&head, RealTrie< IPv6 > *&del)

Private Member Functions

template<class A >
void add (IPNet< A > net, TriePayload &)
template<class A >
void del (IPNet< A > net, TriePayload &)
template<class A >
void get_heads (RealTrie< A > *&, RealTrie< A > *&)
void validate ()

Private Attributes

RealTrie< IPv4_head_ipv4
RealTrie< IPv4_head_ipv4_del
RealTrie< IPv6_head_ipv6
RealTrie< IPv6_head_ipv6_del
TrieData_first
TrieData_last
uint32_t _update_cnt
uint32_t _changes
bool _warning
Node_root
int _payload_count

Detailed Description

template<class A, class Payload, class __Iterator = TriePostOrderIterator<A,Payload>>
class Trie< A, Payload, __Iterator >

The trie stores BGP update packets the trie index is the NLRI.

The Trie itself.

A BGP update packet can contain multiple NLRI's. To save the overhead of storing an update packet multiple times in the trie a single copy of the update packet is kept. The Payload is a reference to this single copy. Each update packet is chained together on a linked list. New update packets are added to the end of the list. In theory this ordered chained list structure should make is very simple to print out the current update packets that constitute the routing table. The ordering is important if the same NLRI is contained in two packets then the later one should be used.

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, class __Iterator = TriePostOrderIterator<A,Payload>>
iterator Trie< A, Payload, __Iterator >::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, class __Iterator = TriePostOrderIterator<A,Payload>>
iterator Trie< A, Payload, __Iterator >::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.

template<class A, class Payload, class __Iterator = TriePostOrderIterator<A,Payload>>
void Trie< A, Payload, __Iterator >::replay_walk ( const ReplayWalker  uw,
const BGPPeerData peerdata 
) const

Generate the set of update packets that would totally populate this trie.

Parameters:
uwThe callback function that is called.
template<class A, class Payload, class __Iterator = TriePostOrderIterator<A,Payload>>
iterator Trie< A, Payload, __Iterator >::unbind_root ( iterator  i) const [inline]

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.

The documentation for this class was generated from the following files:
 All Classes Namespaces Functions Variables Typedefs Enumerations