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


\hyperlink{classTrieNode}{TrieNode} definition.  




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

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

\item 
\hypertarget{classTrieNode_afd2840c1d1a4a22af23b6902457b8b5d}{
typedef \hyperlink{classMiniTraits}{MiniTraits}$<$ Payload $>$::NonConst {\bfseries PPayload}}
\label{classTrieNode_afd2840c1d1a4a22af23b6902457b8b5d}

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

\begin{DoxyCompactList}\small\item\em Constructors. \item\end{DoxyCompactList}\item 
\hypertarget{classTrieNode_ac565af04a7eaf515d514ac812434bc03}{
{\bfseries TrieNode} (const \hyperlink{classIPNet}{Key} \&key, const Payload \&p, \hyperlink{classTrieNode}{TrieNode} $\ast$up=0)}
\label{classTrieNode_ac565af04a7eaf515d514ac812434bc03}

\item 
\hypertarget{classTrieNode_a55ed235ec75caf665102b9d47d6a51a6}{
{\bfseries TrieNode} (const \hyperlink{classIPNet}{Key} \&key, \hyperlink{classTrieNode}{TrieNode} $\ast$up=0)}
\label{classTrieNode_a55ed235ec75caf665102b9d47d6a51a6}

\item 
\hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_aed5f733ea376bda10f78d4fb213a31f7}{erase} ()
\begin{DoxyCompactList}\small\item\em erase current node, replumb. \item\end{DoxyCompactList}\item 
\hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_a07ee67d0139c6bca2483b3e2aff374af}{find} (const \hyperlink{classIPNet}{Key} \&key)
\begin{DoxyCompactList}\small\item\em main search routine. \item\end{DoxyCompactList}\item 
\hypertarget{classTrieNode_a4ae0b9cef9ba8ceb1ed32071906c7265}{
const \hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries const\_\-find} (const \hyperlink{classIPNet}{Key} \&key) const }
\label{classTrieNode_a4ae0b9cef9ba8ceb1ed32071906c7265}

\item 
\hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_a45916ddcd0a82e0094031d8dbf9ea6ef}{find\_\-subtree} (const \hyperlink{classIPNet}{Key} \&key)
\begin{DoxyCompactList}\small\item\em aux search routine. \item\end{DoxyCompactList}\item 
\hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_aa124cbb4c64cb8addc753661e0e39063}{lower\_\-bound} (const \hyperlink{classIPNet}{Key} \&key)
\begin{DoxyCompactList}\small\item\em Given a key, find \hyperlink{protocolthe-p}{the} node with that key and a payload. \item\end{DoxyCompactList}\item 
\hypertarget{classTrieNode_af79eb27e96b060b5acf3aa5ab59cec1f}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries get\_\-left} ()}
\label{classTrieNode_af79eb27e96b060b5acf3aa5ab59cec1f}

\item 
\hypertarget{classTrieNode_ac05e5cdd0ac7799211e99b8150da84b2}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries get\_\-right} ()}
\label{classTrieNode_ac05e5cdd0ac7799211e99b8150da84b2}

\item 
\hypertarget{classTrieNode_a51d599b7fc0dde4d25fad28163390ddb}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries get\_\-parent} ()}
\label{classTrieNode_a51d599b7fc0dde4d25fad28163390ddb}

\item 
\hypertarget{classTrieNode_a5cfb43aa57aa158a25867e96c1b5ce2f}{
bool {\bfseries has\_\-payload} () const }
\label{classTrieNode_a5cfb43aa57aa158a25867e96c1b5ce2f}

\item 
\hypertarget{classTrieNode_a513c49fd8412cb7faf8d2dd5197dce07}{
const Payload \& {\bfseries const\_\-p} () const }
\label{classTrieNode_a513c49fd8412cb7faf8d2dd5197dce07}

\item 
\hypertarget{classTrieNode_aff1751a3ac5682e5251e04c0fa4f3adf}{
Payload \& {\bfseries p} ()}
\label{classTrieNode_aff1751a3ac5682e5251e04c0fa4f3adf}

\item 
\hypertarget{classTrieNode_ac16bb9a1913ae86e634d5a0f3bb7d45c}{
void {\bfseries set\_\-payload} (const Payload \&p)}
\label{classTrieNode_ac16bb9a1913ae86e634d5a0f3bb7d45c}

\item 
\hypertarget{classTrieNode_a07c8056b74c7f03246f75973dbba503a}{
const \hyperlink{classIPNet}{Key} \& {\bfseries k} () const }
\label{classTrieNode_a07c8056b74c7f03246f75973dbba503a}

\item 
\hypertarget{classTrieNode_a9bdf55f1a08cf852df719e5ae025b988}{
void {\bfseries print} (int indent, const char $\ast$msg) const }
\label{classTrieNode_a9bdf55f1a08cf852df719e5ae025b988}

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

\item 
\hypertarget{classTrieNode_aca7d3811b16d76ceb3f609ecb0ecb5d8}{
void \hyperlink{classTrieNode_aca7d3811b16d76ceb3f609ecb0ecb5d8}{delete\_\-subtree} ()}
\label{classTrieNode_aca7d3811b16d76ceb3f609ecb0ecb5d8}

\begin{DoxyCompactList}\small\item\em helper function to delete an entire subtree (including \hyperlink{protocolthe-p}{the} root). \item\end{DoxyCompactList}\item 
\hypertarget{classTrieNode_a64c915b122d7bb5fb2cd1aa472b4eb4b}{
void \hyperlink{classTrieNode_a64c915b122d7bb5fb2cd1aa472b4eb4b}{validate} (const \hyperlink{classTrieNode}{TrieNode} $\ast$parent) const }
\label{classTrieNode_a64c915b122d7bb5fb2cd1aa472b4eb4b}

\begin{DoxyCompactList}\small\item\em debugging, validates a node by checking pointers and Key invariants. \item\end{DoxyCompactList}\item 
\hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_a12db7c1038580482167699f585d24a82}{leftmost} ()
\item 
void \hyperlink{classTrieNode_acf7a4097ed36c498a9a3ba8e63e752ad}{find\_\-bounds} (const A \&a, A \&lo, A \&hi) const 
\item 
A \hyperlink{classTrieNode_a1844affe6d66f557b918604817fe0b82}{low} () const 
\item 
A \hyperlink{classTrieNode_a0df93910d6565999b55bdf59e3a35643}{high} () const 
\end{DoxyCompactItemize}
\subsection*{Static Public Member Functions}
\begin{DoxyCompactItemize}
\item 
static \hyperlink{classTrieNode}{TrieNode} $\ast$ \hyperlink{classTrieNode_aba2cd9a30dab4f38d02eeabba5e0bdb0}{insert} (\hyperlink{classTrieNode}{TrieNode} $\ast$$\ast$root, const \hyperlink{classIPNet}{Key} \&key, const Payload \&p, bool \&replaced)
\begin{DoxyCompactList}\small\item\em add a node to a subtree \item\end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classTrieNode_a26dc06259088956198b46e22b2368c14}{
void {\bfseries delete\_\-payload} (Payload $\ast$p)}
\label{classTrieNode_a26dc06259088956198b46e22b2368c14}

\item 
\hypertarget{classTrieNode_a9eebcc906e0736aad89a91a1569a2019}{
void {\bfseries dump} (const char $\ast$msg) const }
\label{classTrieNode_a9eebcc906e0736aad89a91a1569a2019}

\end{DoxyCompactItemize}
\subsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\hypertarget{classTrieNode_a81df2f1eb81625dca88e1912f34091fe}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries \_\-up}}
\label{classTrieNode_a81df2f1eb81625dca88e1912f34091fe}

\item 
\hypertarget{classTrieNode_aa28fe004f1e53b2aba7b6b170799c647}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries \_\-left}}
\label{classTrieNode_aa28fe004f1e53b2aba7b6b170799c647}

\item 
\hypertarget{classTrieNode_a37925e3be57450b1950e81d89344f5e4}{
\hyperlink{classTrieNode}{TrieNode} $\ast$ {\bfseries \_\-right}}
\label{classTrieNode_a37925e3be57450b1950e81d89344f5e4}

\item 
\hypertarget{classTrieNode_ac70098d134e92949689273177292b4c7}{
\hyperlink{classIPNet}{Key} {\bfseries \_\-k}}
\label{classTrieNode_ac70098d134e92949689273177292b4c7}

\item 
\hypertarget{classTrieNode_a99272b035025088c32917bcc04eb27eb}{
PPayload $\ast$ {\bfseries \_\-p}}
\label{classTrieNode_a99272b035025088c32917bcc04eb27eb}

\end{DoxyCompactItemize}


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

\hyperlink{classTrieNode}{TrieNode} definition. TrieNode's are \hyperlink{protocolthe-p}{the} elements of a \hyperlink{classTrie}{Trie}. Each node is associated to a Key and possibly a Payload. \hyperlink{classNodes}{Nodes} with a Payload (\char`\"{}full\char`\"{}) can have 0, 1 or 2 children. \hyperlink{classNodes}{Nodes} without a Payload (\char`\"{}empty\char`\"{}) can only be internal nodes, and MUST have 2 children (or they have no reason to exist).

Children have a Key which is strictly contained in their parent's Key -\/-\/ more precisely, they are in either \hyperlink{protocolthe-p}{the} left or \hyperlink{protocolthe-p}{the} right half of \hyperlink{protocolthe-p}{the} parent's Key. The branch to which a child is attached (left or right) is defined accordingly. 

\subsection{Member Function Documentation}
\hypertarget{classTrieNode_aed5f733ea376bda10f78d4fb213a31f7}{
\index{TrieNode@{TrieNode}!erase@{erase}}
\index{erase@{erase}!TrieNode@{TrieNode}}
\subsubsection[{erase}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$<$ A, Payload $>$ $\ast$ {\bf TrieNode}$<$ A, Payload $>$::erase (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)}}
\label{classTrieNode_aed5f733ea376bda10f78d4fb213a31f7}


erase current node, replumb. 

Remove this node, cleanup useless internal nodes.

Returns \hyperlink{protocolthe-p}{the} new root.

\begin{DoxyReturn}{Returns}
a pointer to \hyperlink{protocolthe-p}{the} root of \hyperlink{protocolthe-p}{the} trie. 
\end{DoxyReturn}
\hypertarget{classTrieNode_a07ee67d0139c6bca2483b3e2aff374af}{
\index{TrieNode@{TrieNode}!find@{find}}
\index{find@{find}!TrieNode@{TrieNode}}
\subsubsection[{find}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$<$ A, Payload $>$ $\ast$ {\bf TrieNode}$<$ A, Payload $>$::find (
\begin{DoxyParamCaption}
\item[{const {\bf Key} \&}]{key}
\end{DoxyParamCaption}
)}}
\label{classTrieNode_a07ee67d0139c6bca2483b3e2aff374af}


main search routine. 

Finds \hyperlink{protocolthe-p}{the} most specific entry in \hyperlink{protocolthe-p}{the} subtree rooted at r that contains \hyperlink{protocolthe-p}{the} desired key and has a Payload.

Given a key, returns a node. \hypertarget{classTrieNode_acf7a4097ed36c498a9a3ba8e63e752ad}{
\index{TrieNode@{TrieNode}!find\_\-bounds@{find\_\-bounds}}
\index{find\_\-bounds@{find\_\-bounds}!TrieNode@{TrieNode}}
\subsubsection[{find\_\-bounds}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ void {\bf TrieNode}$<$ A, Payload $>$::find\_\-bounds (
\begin{DoxyParamCaption}
\item[{const A \&}]{a, }
\item[{A \&}]{lo, }
\item[{A \&}]{hi}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classTrieNode_acf7a4097ed36c498a9a3ba8e63e752ad}
\begin{DoxyReturn}{Returns}
\hyperlink{protocolthe-p}{the} boundaries (\char`\"{}lo\char`\"{} and \char`\"{}hi\char`\"{}) of \hyperlink{protocolthe-p}{the} largest range that contains 'a' and maps to \hyperlink{protocolthe-p}{the} same route entry.
\end{DoxyReturn}
Algorithm: 
\begin{DoxyPre}
		n = find(a);
 		if we have no route (hence no default), provide a fake 0/0;
		set lo and hi to \hyperlink{protocolthe-p}{the} boundaries of \hyperlink{protocolthe-p}{the} current node.\end{DoxyPre}



\begin{DoxyPre} if n.is\_a\_leaf() we are done (results are \hyperlink{protocolthe-p}{the} extremes of \hyperlink{protocolthe-p}{the} entry)
 Otherwise: we are in an intermediate node, and a can be in positions
 1..5 if \hyperlink{protocolthe-p}{the} node has 2 children, or 1'..3' if it has 1 child.\end{DoxyPre}



\begin{DoxyPre}	n:		|---------------.----------------|
  a:                1    2        3      4     5
                       |--X--|         |--Y--|\end{DoxyPre}



\begin{DoxyPre}  a:                1'    2'        3'
                       |--X--|\end{DoxyPre}



\begin{DoxyPre} Behaviour is \hyperlink{protocolthe-p}{the} following:
  case 1 and 1':	lo already set, hi = (lowest address in X)-1
  case 2 and 2': set n = X and repeat
  case 3: lo = (highest addr in X)+1, hi = (lowest addr in Y)-1
  case 3': lo = (highest addr in X)+1, hi is already set
  case 4: set n = Y and repeat
  case 5:	lo = (highest addr in Y)+1, hi is already set
 \end{DoxyPre}
 \hypertarget{classTrieNode_a45916ddcd0a82e0094031d8dbf9ea6ef}{
\index{TrieNode@{TrieNode}!find\_\-subtree@{find\_\-subtree}}
\index{find\_\-subtree@{find\_\-subtree}!TrieNode@{TrieNode}}
\subsubsection[{find\_\-subtree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$<$ A, Payload $>$ $\ast$ {\bf TrieNode}$<$ A, Payload $>$::find\_\-subtree (
\begin{DoxyParamCaption}
\item[{const {\bf Key} \&}]{key}
\end{DoxyParamCaption}
)}}
\label{classTrieNode_a45916ddcd0a82e0094031d8dbf9ea6ef}


aux search routine. 

Finds \hyperlink{protocolthe-p}{the} subtree of key.

Given a key, returns a subtree contained in \hyperlink{protocolthe-p}{the} key, irrespective of \hyperlink{protocolthe-p}{the} presence of a payload in \hyperlink{protocolthe-p}{the} node. \hypertarget{classTrieNode_a0df93910d6565999b55bdf59e3a35643}{
\index{TrieNode@{TrieNode}!high@{high}}
\index{high@{high}!TrieNode@{TrieNode}}
\subsubsection[{high}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ A {\bf TrieNode}$<$ A, Payload $>$::high (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classTrieNode_a0df93910d6565999b55bdf59e3a35643}
\begin{DoxyReturn}{Returns}
\hyperlink{protocolthe-p}{the} highest address in a subtree which has a route. Search starting from right or left until a full node is found. 
\end{DoxyReturn}
\hypertarget{classTrieNode_aba2cd9a30dab4f38d02eeabba5e0bdb0}{
\index{TrieNode@{TrieNode}!insert@{insert}}
\index{insert@{insert}!TrieNode@{TrieNode}}
\subsubsection[{insert}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$<$ A, Payload $>$ $\ast$ {\bf TrieNode}$<$ A, Payload $>$::insert (
\begin{DoxyParamCaption}
\item[{{\bf TrieNode}$<$ A, Payload $>$ $\ast$$\ast$}]{root, }
\item[{const {\bf Key} \&}]{x, }
\item[{const Payload \&}]{p, }
\item[{bool \&}]{replaced}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily  \mbox{[}static\mbox{]}}}}
\label{classTrieNode_aba2cd9a30dab4f38d02eeabba5e0bdb0}


add a node to a subtree 

add subnet/payload to \hyperlink{protocolthe-p}{the} tree at $\ast$root.

\begin{DoxyReturn}{Returns}
a pointer to \hyperlink{protocolthe-p}{the} node.

a pointer to \hyperlink{protocolthe-p}{the} newly inserted node. 
\end{DoxyReturn}
\hypertarget{classTrieNode_a12db7c1038580482167699f585d24a82}{
\index{TrieNode@{TrieNode}!leftmost@{leftmost}}
\index{leftmost@{leftmost}!TrieNode@{TrieNode}}
\subsubsection[{leftmost}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$\ast$ {\bf TrieNode}$<$ A, Payload $>$::leftmost (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classTrieNode_a12db7c1038580482167699f585d24a82}
\begin{DoxyReturn}{Returns}
\hyperlink{protocolthe-p}{the} leftmost node under this node 
\end{DoxyReturn}
\hypertarget{classTrieNode_a1844affe6d66f557b918604817fe0b82}{
\index{TrieNode@{TrieNode}!low@{low}}
\index{low@{low}!TrieNode@{TrieNode}}
\subsubsection[{low}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ A {\bf TrieNode}$<$ A, Payload $>$::low (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily  \mbox{[}inline\mbox{]}}}}
\label{classTrieNode_a1844affe6d66f557b918604817fe0b82}
\begin{DoxyReturn}{Returns}
\hyperlink{protocolthe-p}{the} lowest address in a subtree which has a route. Search starting from left or right until a full node is found. 
\end{DoxyReturn}
\hypertarget{classTrieNode_aa124cbb4c64cb8addc753661e0e39063}{
\index{TrieNode@{TrieNode}!lower\_\-bound@{lower\_\-bound}}
\index{lower\_\-bound@{lower\_\-bound}!TrieNode@{TrieNode}}
\subsubsection[{lower\_\-bound}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class A , class Payload $>$ {\bf TrieNode}$<$ A, Payload $>$ $\ast$ {\bf TrieNode}$<$ A, Payload $>$::lower\_\-bound (
\begin{DoxyParamCaption}
\item[{const {\bf Key} \&}]{key}
\end{DoxyParamCaption}
)}}
\label{classTrieNode_aa124cbb4c64cb8addc753661e0e39063}


Given a key, find \hyperlink{protocolthe-p}{the} node with that key and a payload. 

See \hyperlink{protocolthe-p}{the} comment in \hyperlink{protocolthe-p}{the} class definition.

If \hyperlink{protocolthe-p}{the} next doesn't exist or does not have a payload, find \hyperlink{protocolthe-p}{the} next node in \hyperlink{protocolthe-p}{the} iterator sequence. XXX check \hyperlink{protocolthe-p}{the} description. 

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