\hypertarget{classRefTrie}{
\section{RefTrie$<$ A, Payload $>$ Class Template Reference}
\label{classRefTrie}\index{RefTrie@{RefTrie}}
}


The \hyperlink{classRefTrie}{RefTrie} itself.  




{\ttfamily \#include $<$ref\_\-trie.hh$>$}

\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classRefTrie_affb94bc6f86a3d4eeadd01d350283536}{
typedef \hyperlink{classIPNet}{IPNet}$<$ A $>$ {\bfseries Key}}
\label{classRefTrie_affb94bc6f86a3d4eeadd01d350283536}

\item 
\hypertarget{classRefTrie_a54aa5a18a640951353492e6f6a78f9d1}{
typedef \hyperlink{classRefTrieNode}{RefTrieNode}$<$ A, Payload $>$ {\bfseries Node}}
\label{classRefTrie_a54aa5a18a640951353492e6f6a78f9d1}

\item 
\hypertarget{classRefTrie_a9306ea959901d5ff93e472f94b0e34ef}{
typedef \hyperlink{classRefTriePostOrderIterator}{RefTriePostOrderIterator}$<$ A, Payload $>$ {\bfseries iterator}}
\label{classRefTrie_a9306ea959901d5ff93e472f94b0e34ef}

\item 
\hypertarget{classRefTrie_a1da8e35446103f8e4a375fda8ffc513f}{
typedef \hyperlink{classRefTriePostOrderIterator}{RefTriePostOrderIterator}$<$ A, Payload $>$ {\bfseries PostOrderIterator}}
\label{classRefTrie_a1da8e35446103f8e4a375fda8ffc513f}

\item 
\hypertarget{classRefTrie_ad20b481b52a2cd8312683eac382b3154}{
typedef \hyperlink{classRefTriePreOrderIterator}{RefTriePreOrderIterator}$<$ A, Payload $>$ {\bfseries PreOrderIterator}}
\label{classRefTrie_ad20b481b52a2cd8312683eac382b3154}

\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classRefTrie_ae1d4fd258b2993f2eb65259392899b79}{
\hyperlink{classRefTrie_ae1d4fd258b2993f2eb65259392899b79}{RefTrie} ()}
\label{classRefTrie_ae1d4fd258b2993f2eb65259392899b79}

\begin{DoxyCompactList}\small\item\em stl map interface \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a437f549d8bed0da9b378215a10c5b523}{
void {\bfseries delete\_\-self} ()}
\label{classRefTrie_a437f549d8bed0da9b378215a10c5b523}

\item 
\hypertarget{classRefTrie_a1c6829102bde60cfd48e213e40cd8136}{
void {\bfseries set\_\-root} (\hyperlink{classRefTrieNode}{Node} $\ast$root)}
\label{classRefTrie_a1c6829102bde60cfd48e213e40cd8136}

\item 
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_afc5a2c82168223fc4a272ef5ae56bfeb}{insert} (const \hyperlink{classIPNet}{Key} \&net, const Payload \&p)
\begin{DoxyCompactList}\small\item\em insert a key, payload pair, returns an iterator to \hyperlink{protocolthe-p}{the} newly inserted node. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_ad8dc9340ad324cc5a49e41c9e1b813e9}{
void \hyperlink{classRefTrie_ad8dc9340ad324cc5a49e41c9e1b813e9}{erase} (const \hyperlink{classIPNet}{Key} \&k)}
\label{classRefTrie_ad8dc9340ad324cc5a49e41c9e1b813e9}

\begin{DoxyCompactList}\small\item\em delete \hyperlink{protocolthe-p}{the} node with \hyperlink{protocolthe-p}{the} given key. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a02cb5fef119520c65b8ef183153d8187}{
void \hyperlink{classRefTrie_a02cb5fef119520c65b8ef183153d8187}{erase} (\hyperlink{classRefTriePostOrderIterator}{iterator} i)}
\label{classRefTrie_a02cb5fef119520c65b8ef183153d8187}

\begin{DoxyCompactList}\small\item\em delete \hyperlink{protocolthe-p}{the} node pointed by \hyperlink{protocolthe-p}{the} iterator. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a200d91f2286edf6153237664a40c5793}{
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_a200d91f2286edf6153237664a40c5793}{find} (const \hyperlink{classIPNet}{Key} \&k) const }
\label{classRefTrie_a200d91f2286edf6153237664a40c5793}

\begin{DoxyCompactList}\small\item\em given a key, returns an iterator to \hyperlink{protocolthe-p}{the} entry with \hyperlink{protocolthe-p}{the} longest matching prefix. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a28052613ba99ce129dcc424b1bb3f4d0}{
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_a28052613ba99ce129dcc424b1bb3f4d0}{find} (const A \&a) const }
\label{classRefTrie_a28052613ba99ce129dcc424b1bb3f4d0}

\begin{DoxyCompactList}\small\item\em given an address, returns an iterator to \hyperlink{protocolthe-p}{the} entry with \hyperlink{protocolthe-p}{the} longest matching prefix. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a95b5ad613a8ce1a109903e4a01e7175d}{
\hyperlink{classRefTriePostOrderIterator}{iterator} {\bfseries lower\_\-bound} (const \hyperlink{classIPNet}{Key} \&k) const }
\label{classRefTrie_a95b5ad613a8ce1a109903e4a01e7175d}

\item 
\hypertarget{classRefTrie_ad4fa058c55262bdec85d164ba8301459}{
\hyperlink{classRefTriePostOrderIterator}{iterator} {\bfseries begin} () const }
\label{classRefTrie_ad4fa058c55262bdec85d164ba8301459}

\item 
\hypertarget{classRefTrie_aed8d7a441b5e3d4b44e0e333342b52a1}{
const \hyperlink{classRefTriePostOrderIterator}{iterator} {\bfseries end} () const }
\label{classRefTrie_aed8d7a441b5e3d4b44e0e333342b52a1}

\item 
\hypertarget{classRefTrie_a1ba06d4180897df208bf7a1f45aefab4}{
void {\bfseries delete\_\-all\_\-nodes} ()}
\label{classRefTrie_a1ba06d4180897df208bf7a1f45aefab4}

\item 
\hypertarget{classRefTrie_a41c1acef90e1b0ec93df3667c66852d6}{
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_a41c1acef90e1b0ec93df3667c66852d6}{lookup\_\-node} (const \hyperlink{classIPNet}{Key} \&k) const }
\label{classRefTrie_a41c1acef90e1b0ec93df3667c66852d6}

\begin{DoxyCompactList}\small\item\em lookup a subnet, must return exact match if found, end() if not. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a43c6bd8d7c9e62394e98be4325eb67e3}{
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_a43c6bd8d7c9e62394e98be4325eb67e3}{search\_\-subtree} (const \hyperlink{classIPNet}{Key} \&key) const }
\label{classRefTrie_a43c6bd8d7c9e62394e98be4325eb67e3}

\begin{DoxyCompactList}\small\item\em returns an iterator to \hyperlink{protocolthe-p}{the} subtree rooted at or below \hyperlink{protocolthe-p}{the} key passed as parameter. \item\end{DoxyCompactList}\item 
\hyperlink{classRefTriePostOrderIterator}{iterator} \hyperlink{classRefTrie_a7c17711a74a92d0de938276cd87df54e}{find\_\-less\_\-specific} (const \hyperlink{classIPNet}{Key} \&key) const 
\begin{DoxyCompactList}\small\item\em find\_\-less\_\-specific asks \hyperlink{protocolthe-p}{the} question: if I were to add this net to \hyperlink{protocolthe-p}{the} trie, what would be its parent node? net may or may not already be in \hyperlink{protocolthe-p}{the} trie. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a8b3d75a20d96d877d75c13929f234bd7}{
void \hyperlink{classRefTrie_a8b3d75a20d96d877d75c13929f234bd7}{find\_\-bounds} (const A \&a, A \&lo, A \&hi) const }
\label{classRefTrie_a8b3d75a20d96d877d75c13929f234bd7}

\begin{DoxyCompactList}\small\item\em return \hyperlink{protocolthe-p}{the} lower and higher address in \hyperlink{protocolthe-p}{the} range that contains a and would map to \hyperlink{protocolthe-p}{the} same route. \item\end{DoxyCompactList}\item 
\hypertarget{classRefTrie_a6905460ad7ce39a1c6d900403f1db035}{
int {\bfseries route\_\-count} () const }
\label{classRefTrie_a6905460ad7ce39a1c6d900403f1db035}

\item 
\hypertarget{classRefTrie_a16e4419c26b45c30214052ea3c76e652}{
void {\bfseries print} () const }
\label{classRefTrie_a16e4419c26b45c30214052ea3c76e652}

\item 
\hypertarget{classRefTrie_aa12aff152d289bd6704756082d4a8e3c}{
string {\bfseries str} () const }
\label{classRefTrie_aa12aff152d289bd6704756082d4a8e3c}

\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classRefTrie_a5f2afa99b608022ccc9f62c49af76550}{
void {\bfseries validate} ()}
\label{classRefTrie_a5f2afa99b608022ccc9f62c49af76550}

\end{DoxyCompactItemize}
\subsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classRefTrie_a534252b78b3828f378a08e9d2256b2b7}{
\hyperlink{classRefTrieNode}{Node} $\ast$ {\bfseries \_\-root}}
\label{classRefTrie_a534252b78b3828f378a08e9d2256b2b7}

\item 
\hypertarget{classRefTrie_a94a2e1fbdffb61796c56a8aa8b1e22a5}{
int {\bfseries \_\-payload\_\-count}}
\label{classRefTrie_a94a2e1fbdffb61796c56a8aa8b1e22a5}

\item 
bool \hyperlink{classRefTrie_af16eb7ae16737de8ea2b1def0dceaeaa}{\_\-deleted}
\begin{DoxyCompactList}\small\item\em RefTrie's nodes are reference counted, so it's possible to delete all \hyperlink{protocolthe-p}{the} nodes in \hyperlink{protocolthe-p}{the} trie, and for \hyperlink{protocolthe-p}{the} actually routes to remain around until their reference counts go to zero because iterators still point at a node. \item\end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$class A, class Payload$>$ class RefTrie$<$ A, Payload $>$}

The \hyperlink{classRefTrie}{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. 

\subsection{Member Function Documentation}
\hypertarget{classRefTrie_a7c17711a74a92d0de938276cd87df54e}{
\index{RefTrie@{RefTrie}!find\_\-less\_\-specific@{find\_\-less\_\-specific}}
\index{find\_\-less\_\-specific@{find\_\-less\_\-specific}!RefTrie@{RefTrie}}
\subsubsection[{find\_\-less\_\-specific}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A, class Payload$>$ {\bf iterator} {\bf RefTrie}$<$ A, Payload $>$::find\_\-less\_\-specific (
\begin{DoxyParamCaption}
\item[{const {\bf Key} \&}]{key}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classRefTrie_a7c17711a74a92d0de938276cd87df54e}


find\_\-less\_\-specific asks \hyperlink{protocolthe-p}{the} question: if I were to add this net to \hyperlink{protocolthe-p}{the} trie, what would be its parent node? net may or may not already be in \hyperlink{protocolthe-p}{the} trie. 

Implemented as a \hyperlink{classRefTrie_a200d91f2286edf6153237664a40c5793}{find()} with a less specific key. \hypertarget{classRefTrie_afc5a2c82168223fc4a272ef5ae56bfeb}{
\index{RefTrie@{RefTrie}!insert@{insert}}
\index{insert@{insert}!RefTrie@{RefTrie}}
\subsubsection[{insert}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A, class Payload$>$ {\bf iterator} {\bf RefTrie}$<$ A, Payload $>$::insert (
\begin{DoxyParamCaption}
\item[{const {\bf Key} \&}]{net, }
\item[{const Payload \&}]{p}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classRefTrie_afc5a2c82168223fc4a272ef5ae56bfeb}


insert a key, payload pair, returns an iterator to \hyperlink{protocolthe-p}{the} newly inserted node. 

Prints a warning message if \hyperlink{protocolthe-p}{the} new entry overwrites an existing full node. 

\subsection{Member Data Documentation}
\hypertarget{classRefTrie_af16eb7ae16737de8ea2b1def0dceaeaa}{
\index{RefTrie@{RefTrie}!\_\-deleted@{\_\-deleted}}
\index{\_\-deleted@{\_\-deleted}!RefTrie@{RefTrie}}
\subsubsection[{\_\-deleted}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A, class Payload$>$ bool {\bf RefTrie}$<$ A, Payload $>$::{\bf \_\-deleted}\hspace{0.3cm}{\ttfamily  \mbox{[}private\mbox{]}}}}
\label{classRefTrie_af16eb7ae16737de8ea2b1def0dceaeaa}


RefTrie's nodes are reference counted, so it's possible to delete all \hyperlink{protocolthe-p}{the} nodes in \hyperlink{protocolthe-p}{the} trie, and for \hyperlink{protocolthe-p}{the} actually routes to remain around until their reference counts go to zero because iterators still point at a node. 

If you then delete \hyperlink{protocolthe-p}{the} trie itself, \hyperlink{protocolthe-p}{the} nodes will be deleted but \hyperlink{protocolthe-p}{the} iterator will be invalidated. Instead delete\_\-self() should be called, which sets \_\-deleted, and only finally deletes \hyperlink{protocolthe-p}{the} trie when all \hyperlink{protocolthe-p}{the} nodes themselves have gone away. 

The documentation for this class was generated from the following file:\begin{DoxyCompactItemize}
\item 
/home/greearb/git/xorp.ct.github/xorp/libxorp/ref\_\-trie.hh\end{DoxyCompactItemize}
