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 UpdatePacket *	lookup (const string &net) const
const UpdatePacket *	lookup (const IPv4Net &net) const
const UpdatePacket *	lookup (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:

uw	The 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:

• /home/greearb/git/xorp.ct.github/xorp/bgp/harness/trie.hh
• /home/greearb/git/xorp.ct.github/xorp/libxorp/trie.hh
• /home/greearb/git/xorp.ct.github/xorp/bgp/harness/trie.cc