\doxysection{rtrlib/pfx/trie/trie\+\_\+private.h File Reference} \hypertarget{trie__private_8h}{}\label{trie__private_8h}\index{rtrlib/pfx/trie/trie\_private.h@{rtrlib/pfx/trie/trie\_private.h}} {\ttfamily \#include "{}rtrlib/lib/ip\+\_\+private.\+h"{}}\newline {\ttfamily \#include "{}rtrlib/lib/log\+\_\+private.\+h"{}}\newline {\ttfamily \#include $<$inttypes.\+h$>$}\newline \doxysubsubsection*{Data Structures} \begin{DoxyCompactItemize} \item struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \begin{DoxyCompactList}\small\item\em \doxylink{structtrie__node}{trie\+\_\+node} \end{DoxyCompactList}\end{DoxyCompactItemize} \doxysubsubsection*{Macros} \begin{DoxyCompactItemize} \item \#define \mbox{\hyperlink{trie__private_8h_a9fc63b95f6dcb6b72f4482cdf87b4e01}{PFX\+\_\+\+DBG1}}(a)~\mbox{\hyperlink{log__private_8h_abb57f299264865eb02379019cfe4df0c}{lrtr\+\_\+dbg}}("{}PFX\+: "{} a) \end{DoxyCompactItemize} \doxysubsubsection*{Functions} \begin{DoxyCompactItemize} \item void \mbox{\hyperlink{trie__private_8h_a1dd8536a8ad980f79e5d56f9b2174e89}{trie\+\_\+insert}} (struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}root, struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}new\+\_\+node, const unsigned int level) \begin{DoxyCompactList}\small\item\em Inserts new\+\_\+node in the tree. \end{DoxyCompactList}\item struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} \mbox{\hyperlink{trie__private_8h_a49ce5b8690dc3e78a88de98aa1ff9117}{trie\+\_\+lookup}} (const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}root\+\_\+node, const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}prefix, const uint8\+\_\+t mask\+\_\+len, unsigned int \texorpdfstring{$\ast$}{*}level) \begin{DoxyCompactList}\small\item\em Searches for a matching node matching the passed ip prefix and prefix length. \end{DoxyCompactList}\item struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} \mbox{\hyperlink{trie__private_8h_a7008a96ba9755bdacc3203cbf3424449}{trie\+\_\+lookup\+\_\+exact}} (struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}root\+\_\+node, const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}prefix, const uint8\+\_\+t mask\+\_\+len, unsigned int \texorpdfstring{$\ast$}{*}level, bool \texorpdfstring{$\ast$}{*}found) \begin{DoxyCompactList}\small\item\em Search for a node with the same prefix and prefix length. \end{DoxyCompactList}\item struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} \mbox{\hyperlink{trie__private_8h_aa74e7bea478ad311be7230f7641913f6}{trie\+\_\+remove}} (struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}root\+\_\+node, const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}prefix, const uint8\+\_\+t mask\+\_\+len, const unsigned int level) \begin{DoxyCompactList}\small\item\em Removes the node with the passed IP prefix and mask\+\_\+len from the tree. \end{DoxyCompactList}\item bool \mbox{\hyperlink{trie__private_8h_a4cd5562aadd06cd6eeaec08972d17bb3}{trie\+\_\+is\+\_\+leaf}} (const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}node) \begin{DoxyCompactList}\small\item\em Detects if a node is a leaf in the tree. \end{DoxyCompactList}\item int \mbox{\hyperlink{trie__private_8h_a35e444f2e47b98f760dca80e354e7870}{trie\+\_\+get\+\_\+children}} (const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}root\+\_\+node, struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}\texorpdfstring{$\ast$}{*}\texorpdfstring{$\ast$}{*}array, unsigned int \texorpdfstring{$\ast$}{*}\mbox{\hyperlink{rtr__pdus_8h_a96bbf959016e4411c9e6b9812a8be60a}{len}}) \end{DoxyCompactItemize} \doxysubsection{Macro Definition Documentation} \Hypertarget{trie__private_8h_a9fc63b95f6dcb6b72f4482cdf87b4e01}\label{trie__private_8h_a9fc63b95f6dcb6b72f4482cdf87b4e01} \index{trie\_private.h@{trie\_private.h}!PFX\_DBG1@{PFX\_DBG1}} \index{PFX\_DBG1@{PFX\_DBG1}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{PFX\_DBG1}{PFX\_DBG1}} {\footnotesize\ttfamily \#define PFX\+\_\+\+DBG1(\begin{DoxyParamCaption}\item[{}]{a }\end{DoxyParamCaption})~\mbox{\hyperlink{log__private_8h_abb57f299264865eb02379019cfe4df0c}{lrtr\+\_\+dbg}}("{}PFX\+: "{} a)} \doxysubsection{Function Documentation} \Hypertarget{trie__private_8h_a35e444f2e47b98f760dca80e354e7870}\label{trie__private_8h_a35e444f2e47b98f760dca80e354e7870} \index{trie\_private.h@{trie\_private.h}!trie\_get\_children@{trie\_get\_children}} \index{trie\_get\_children@{trie\_get\_children}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_get\_children()}{trie\_get\_children()}} {\footnotesize\ttfamily int trie\+\_\+get\+\_\+children (\begin{DoxyParamCaption}\item[{const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{root\+\_\+node, }\item[{struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}\texorpdfstring{$\ast$}{*}\texorpdfstring{$\ast$}{*}}]{array, }\item[{unsigned int \texorpdfstring{$\ast$}{*}}]{len }\end{DoxyParamCaption})} \Hypertarget{trie__private_8h_a1dd8536a8ad980f79e5d56f9b2174e89}\label{trie__private_8h_a1dd8536a8ad980f79e5d56f9b2174e89} \index{trie\_private.h@{trie\_private.h}!trie\_insert@{trie\_insert}} \index{trie\_insert@{trie\_insert}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_insert()}{trie\_insert()}} {\footnotesize\ttfamily void trie\+\_\+insert (\begin{DoxyParamCaption}\item[{struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{root, }\item[{struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{new\+\_\+node, }\item[{const unsigned int}]{level }\end{DoxyParamCaption})} Inserts new\+\_\+node in the tree. \begin{DoxyParams}[1]{Parameters} \mbox{\texttt{ in}} & {\em root} & Root node of the tree for the inserting process. \\ \hline \mbox{\texttt{ in}} & {\em new\+\_\+node} & Node that will be inserted. \\ \hline \mbox{\texttt{ in}} & {\em level} & Level of the the root node in the tree. \\ \hline \end{DoxyParams} \Hypertarget{trie__private_8h_a4cd5562aadd06cd6eeaec08972d17bb3}\label{trie__private_8h_a4cd5562aadd06cd6eeaec08972d17bb3} \index{trie\_private.h@{trie\_private.h}!trie\_is\_leaf@{trie\_is\_leaf}} \index{trie\_is\_leaf@{trie\_is\_leaf}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_is\_leaf()}{trie\_is\_leaf()}} {\footnotesize\ttfamily bool trie\+\_\+is\+\_\+leaf (\begin{DoxyParamCaption}\item[{const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{node }\end{DoxyParamCaption})} Detects if a node is a leaf in the tree. \begin{DoxyParams}[1]{Parameters} \mbox{\texttt{ in}} & {\em node} & \\ \hline \end{DoxyParams} \begin{DoxyReturn}{Returns} true if node is a leaf. false if node isn\textquotesingle{}t a leaf. \end{DoxyReturn} \Hypertarget{trie__private_8h_a49ce5b8690dc3e78a88de98aa1ff9117}\label{trie__private_8h_a49ce5b8690dc3e78a88de98aa1ff9117} \index{trie\_private.h@{trie\_private.h}!trie\_lookup@{trie\_lookup}} \index{trie\_lookup@{trie\_lookup}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_lookup()}{trie\_lookup()}} {\footnotesize\ttfamily struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} trie\+\_\+lookup (\begin{DoxyParamCaption}\item[{const struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{root\+\_\+node, }\item[{const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}}]{prefix, }\item[{const uint8\+\_\+t}]{mask\+\_\+len, }\item[{unsigned int \texorpdfstring{$\ast$}{*}}]{level }\end{DoxyParamCaption})} Searches for a matching node matching the passed ip prefix and prefix length. If multiple matching nodes exist, the one with the shortest prefix is returned. \begin{DoxyParams}[1]{Parameters} \mbox{\texttt{ in}} & {\em root\+\_\+node} & Node were the lookup process starts. \\ \hline \mbox{\texttt{ in}} & {\em \doxylink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} & IP-\/\+Prefix. \\ \hline \mbox{\texttt{ in}} & {\em mask\+\_\+len} & Length of the network mask of the prefix. \\ \hline \mbox{\texttt{ in,out}} & {\em level} & of the the node root in the tree. Is set to the level of the node that is returned. \\ \hline \end{DoxyParams} \begin{DoxyReturn}{Returns} The \doxylink{structtrie__node}{trie\+\_\+node} with the short prefix in the tree matching the passed ip prefix and prefix length. NULL if no node that matches the passed prefix and prefix length could be found. \end{DoxyReturn} \Hypertarget{trie__private_8h_a7008a96ba9755bdacc3203cbf3424449}\label{trie__private_8h_a7008a96ba9755bdacc3203cbf3424449} \index{trie\_private.h@{trie\_private.h}!trie\_lookup\_exact@{trie\_lookup\_exact}} \index{trie\_lookup\_exact@{trie\_lookup\_exact}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_lookup\_exact()}{trie\_lookup\_exact()}} {\footnotesize\ttfamily struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} trie\+\_\+lookup\+\_\+exact (\begin{DoxyParamCaption}\item[{struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{root\+\_\+node, }\item[{const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}}]{prefix, }\item[{const uint8\+\_\+t}]{mask\+\_\+len, }\item[{unsigned int \texorpdfstring{$\ast$}{*}}]{level, }\item[{bool \texorpdfstring{$\ast$}{*}}]{found }\end{DoxyParamCaption})} Search for a node with the same prefix and prefix length. \begin{DoxyParams}[1]{Parameters} \mbox{\texttt{ in}} & {\em root\+\_\+node} & Node were the lookup process starts. \\ \hline \mbox{\texttt{ in}} & {\em \doxylink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} & IP-\/\+Prefix. \\ \hline \mbox{\texttt{ in}} & {\em mask\+\_\+len} & Length of the network mask of the prefix. \\ \hline \mbox{\texttt{ in,out}} & {\em level} & of the the node root in the tree. Is set to the level of the node that is returned. \\ \hline \mbox{\texttt{ in}} & {\em found} & Is true if a node which matches could be found else found is set to false. \\ \hline \end{DoxyParams} \begin{DoxyReturn}{Returns} A node which matches the passed parameter (found==true). The parent of the node where the lookup operation stopped (found==false). NULL if root\+\_\+node is NULL. \end{DoxyReturn} \Hypertarget{trie__private_8h_aa74e7bea478ad311be7230f7641913f6}\label{trie__private_8h_aa74e7bea478ad311be7230f7641913f6} \index{trie\_private.h@{trie\_private.h}!trie\_remove@{trie\_remove}} \index{trie\_remove@{trie\_remove}!trie\_private.h@{trie\_private.h}} \doxysubsubsection{\texorpdfstring{trie\_remove()}{trie\_remove()}} {\footnotesize\ttfamily struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*} trie\+\_\+remove (\begin{DoxyParamCaption}\item[{struct \mbox{\hyperlink{structtrie__node}{trie\+\_\+node}} \texorpdfstring{$\ast$}{*}}]{root\+\_\+node, }\item[{const struct \mbox{\hyperlink{structlrtr__ip__addr}{lrtr\+\_\+ip\+\_\+addr}} \texorpdfstring{$\ast$}{*}}]{prefix, }\item[{const uint8\+\_\+t}]{mask\+\_\+len, }\item[{const unsigned int}]{level }\end{DoxyParamCaption})} Removes the node with the passed IP prefix and mask\+\_\+len from the tree. \begin{DoxyParams}[1]{Parameters} \mbox{\texttt{ in}} & {\em root} & Node were the inserting process starts. \\ \hline \mbox{\texttt{ in}} & {\em prefix} & Prefix that will removed from the tree. \\ \hline \mbox{\texttt{ in}} & {\em mask\+\_\+len} & Length of the network mask of the prefix. \\ \hline \mbox{\texttt{ in}} & {\em level} & Level of the root node in the tree. \\ \hline \end{DoxyParams} \begin{DoxyReturn}{Returns} Node that was removed from the tree. The caller has to free it. NULL If the Prefix couldn\textquotesingle{}t be found in the tree. \end{DoxyReturn}