\hypertarget{kdbopmphm_8h}{}\section{kdbopmphm.\+h File Reference}
\label{kdbopmphm_8h}\index{kdbopmphm.\+h@{kdbopmphm.\+h}}


Defines for the Order Preserving Minimal Perfect Hash Map.  


{\ttfamily \#include $<$stdint.\+h$>$}\newline
{\ttfamily \#include $<$stdlib.\+h$>$}\newline
Include dependency graph for kdbopmphm.\+h\+:
\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=196pt]{kdbopmphm_8h__incl}
\end{center}
\end{figure}
This graph shows which files directly or indirectly include this file\+:
\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=158pt]{kdbopmphm_8h__dep__incl}
\end{center}
\end{figure}
\subsection*{Classes}
\begin{DoxyCompactItemize}
\item 
struct \hyperlink{structOpmphmEdge}{Opmphm\+Edge}
\begin{DoxyCompactList}\small\item\em The r-\/partite hypergraph. \end{DoxyCompactList}\item 
struct \hyperlink{structOpmphm}{Opmphm}
\begin{DoxyCompactList}\small\item\em The opmphm. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Macros}
\begin{DoxyCompactItemize}
\item 
\#define \hyperlink{kdbopmphm_8h_ad241eace4050c6fcdab0da1919a79d93}{O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE}~3
\begin{DoxyCompactList}\small\item\em The Order Preserving Minimal Perfect Hash Map (O\+P\+M\+P\+HM) maps each element to an edge in an r-\/partite hypergraph. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{kdbopmphm_8h_a68a6a4cea9cd724457115e974bd02499}\label{kdbopmphm_8h_a68a6a4cea9cd724457115e974bd02499}} 
\#define \hyperlink{kdbopmphm_8h_a68a6a4cea9cd724457115e974bd02499}{O\+P\+M\+P\+H\+M\+\_\+\+H\+A\+S\+H\+F\+U\+N\+C\+T\+I\+O\+N\+\_\+\+R\+OT}(x,  k)~(((x) $<$$<$ (k)) $\vert$ ((x) $>$$>$ (32 -\/ (k))))
\begin{DoxyCompactList}\small\item\em Hash function By Bob Jenkins, May 2006 \href{http://burtleburtle.net/bob/c/lookup3.c}{\tt http\+://burtleburtle.\+net/bob/c/lookup3.\+c}. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Typedefs}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{kdbopmphm_8h_a5913478714c964adfe1dcdee48f31ce9}\label{kdbopmphm_8h_a5913478714c964adfe1dcdee48f31ce9}} 
typedef const char $\ast$($\ast$ \hyperlink{kdbopmphm_8h_a5913478714c964adfe1dcdee48f31ce9}{opmphm\+Get\+String}) (void $\ast$)
\begin{DoxyCompactList}\small\item\em Only needed for Initialisation. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Functions}
\begin{DoxyCompactItemize}
\item 
double \hyperlink{kdbopmphm_8h_ad6b70f700b4e2552b128917b5c1074af}{opmphm\+MinC} (void)
\begin{DoxyCompactList}\small\item\em Graph functions. \end{DoxyCompactList}\item 
Opmphm\+Graph $\ast$ \hyperlink{kdbopmphm_8h_abb60c552d370e227774d6eac740aaa85}{opmphm\+Graph\+New} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm, size\+\_\+t n, double c)
\begin{DoxyCompactList}\small\item\em Allocates and initializes the Opmphm\+Graph. \end{DoxyCompactList}\item 
void \hyperlink{kdbopmphm_8h_a8028ab6baf6d67246685cc341548df0d}{opmphm\+Graph\+Del} (Opmphm\+Graph $\ast$graph)
\begin{DoxyCompactList}\small\item\em Deletes the Opmphm\+Graph. \end{DoxyCompactList}\item 
int \hyperlink{kdbopmphm_8h_aac350c6406d4fdf71e6832900e47a79b}{opmphm\+Mapping} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm, Opmphm\+Graph $\ast$graph, Opmphm\+Init $\ast$init, size\+\_\+t n)
\begin{DoxyCompactList}\small\item\em Build functions. \end{DoxyCompactList}\item 
int \hyperlink{kdbopmphm_8h_add187b2f5ceecdeecb57c8dd4a445edf}{opmphm\+Assignment} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm, Opmphm\+Graph $\ast$graph, size\+\_\+t n, int default\+Order)
\begin{DoxyCompactList}\small\item\em Assigns the vertices of the r-\/partite hypergraph. \end{DoxyCompactList}\item 
size\+\_\+t \hyperlink{kdbopmphm_8h_a24fe857fb60d0d3bb85568f1b73fb77b}{opmphm\+Lookup} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm, const void $\ast$name)
\begin{DoxyCompactList}\small\item\em Lookup functions. \end{DoxyCompactList}\item 
\hyperlink{structOpmphm}{Opmphm} $\ast$ \hyperlink{kdbopmphm_8h_a9cd39724926a210dd21d7fcc351e5300}{opmphm\+New} (void)
\begin{DoxyCompactList}\small\item\em Basic functions. \end{DoxyCompactList}\item 
void \hyperlink{kdbopmphm_8h_a62b8f6cae587a7c8cd12709899e5bade}{opmphm\+Del} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm)
\begin{DoxyCompactList}\small\item\em Deletes the O\+P\+M\+P\+HM. \end{DoxyCompactList}\item 
void \hyperlink{kdbopmphm_8h_a9f5fb16dfe4472e9b44597653cc80a8c}{opmphm\+Clear} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm)
\begin{DoxyCompactList}\small\item\em Clears the O\+P\+M\+P\+HM. \end{DoxyCompactList}\item 
int \hyperlink{kdbopmphm_8h_aa75546e6b30698cbdbed23bc7eddf359}{opmphm\+Is\+Empty} (\hyperlink{structOpmphm}{Opmphm} $\ast$opmphm)
\begin{DoxyCompactList}\small\item\em Determines if the O\+P\+M\+P\+HM is Empty. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{kdbopmphm_8h_a6225cedb78ca850b9494b950ff3e24f4}\label{kdbopmphm_8h_a6225cedb78ca850b9494b950ff3e24f4}} 
uint32\+\_\+t \hyperlink{kdbopmphm_8h_a6225cedb78ca850b9494b950ff3e24f4}{opmphm\+Hashfunction} (const void $\ast$key, size\+\_\+t length, uint32\+\_\+t initval)
\begin{DoxyCompactList}\small\item\em Hash function By Bob Jenkins, May 2006 \href{http://burtleburtle.net/bob/c/lookup3.c}{\tt http\+://burtleburtle.\+net/bob/c/lookup3.\+c} Original name\+: hashlitte. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
Defines for the Order Preserving Minimal Perfect Hash Map. 

\begin{DoxyCopyright}{Copyright}
B\+SD License (see doc/\+C\+O\+P\+Y\+I\+NG or \href{https://www.libelektra.org}{\tt https\+://www.\+libelektra.\+org}) 
\end{DoxyCopyright}


\subsection{Macro Definition Documentation}
\mbox{\Hypertarget{kdbopmphm_8h_ad241eace4050c6fcdab0da1919a79d93}\label{kdbopmphm_8h_ad241eace4050c6fcdab0da1919a79d93}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE@{O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE}}
\index{O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE@{O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE}{OPMPHMR\_PARTITE}}
{\footnotesize\ttfamily \#define O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE~3}



The Order Preserving Minimal Perfect Hash Map (O\+P\+M\+P\+HM) maps each element to an edge in an r-\/partite hypergraph. 

The r-\/partite hypergraph consist of {\ttfamily O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE} components, each component has {\ttfamily Opmphm-\/$>$component\+Size} vertices. An edge connects {\ttfamily O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE} vertices, each one in separate components of the r-\/partite hypergraph. The number of vertices in one component of the r-\/partite hypergraph ({\ttfamily Opmphm-\/$>$component\+Size}) is calculated during {\ttfamily opmphm\+Graph\+New ()} the following way\+:


\begin{DoxyCode}
\hyperlink{structOpmphm}{Opmphm}->\hyperlink{structOpmphm_a01441fc04bd56fd6253ca4265364d39c}{componentSize} = (c * n / \hyperlink{kdbopmphm_8h_ad241eace4050c6fcdab0da1919a79d93}{OPMPHMR\_PARTITE}) + 1;
\end{DoxyCode}


Note that {\ttfamily c} must have a minimal value in order to generate acyclic r-\/partite hypergraphs. The minimal value of {\ttfamily c} depends on {\ttfamily O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE} and is provided by the function {\ttfamily opmphm\+MinC ()}.

The finals size of the opmphm ({\ttfamily Opmphm-\/$>$graph}) is\+: {\ttfamily Opmphm-\/$>$component\+Size $\ast$ O\+P\+M\+P\+H\+M\+R\+\_\+\+P\+A\+R\+T\+I\+TE} 

\subsection{Function Documentation}
\mbox{\Hypertarget{kdbopmphm_8h_add187b2f5ceecdeecb57c8dd4a445edf}\label{kdbopmphm_8h_add187b2f5ceecdeecb57c8dd4a445edf}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Assignment@{opmphm\+Assignment}}
\index{opmphm\+Assignment@{opmphm\+Assignment}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Assignment()}{opmphmAssignment()}}
{\footnotesize\ttfamily int opmphm\+Assignment (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm,  }\item[{Opmphm\+Graph $\ast$}]{graph,  }\item[{size\+\_\+t}]{n,  }\item[{int}]{default\+Order }\end{DoxyParamCaption})}



Assigns the vertices of the r-\/partite hypergraph. 

Allocs the memory for the final O\+P\+M\+P\+HM {\ttfamily Opmphm-\/$>$graph}. Uses the remove sequence {\ttfamily Opmphm\+Graph-\/$>$remove\+Order}, generated during cycle check, to assign each vertex. Either with {\ttfamily Opmphm\+Edge-\/$>$order} or the default order, default is the order of {\ttfamily Opmphm\+Init-\/$>$data}.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
{\em graph} & the Opmphm\+Graph \\
\hline
{\em n} & the number of elements \\
\hline
{\em default\+Order} & boolean flag\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em 0} & on success \\
\hline
{\em -\/1} & on memory error \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_a9f5fb16dfe4472e9b44597653cc80a8c}\label{kdbopmphm_8h_a9f5fb16dfe4472e9b44597653cc80a8c}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Clear@{opmphm\+Clear}}
\index{opmphm\+Clear@{opmphm\+Clear}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Clear()}{opmphmClear()}}
{\footnotesize\ttfamily void opmphm\+Clear (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm }\end{DoxyParamCaption})}



Clears the O\+P\+M\+P\+HM. 

Clears and frees all internal memory of \hyperlink{structOpmphm}{Opmphm}, but not the \hyperlink{structOpmphm}{Opmphm} instance.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphm_8h_a62b8f6cae587a7c8cd12709899e5bade}\label{kdbopmphm_8h_a62b8f6cae587a7c8cd12709899e5bade}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Del@{opmphm\+Del}}
\index{opmphm\+Del@{opmphm\+Del}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Del()}{opmphmDel()}}
{\footnotesize\ttfamily void opmphm\+Del (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm }\end{DoxyParamCaption})}



Deletes the O\+P\+M\+P\+HM. 

Clears and frees all memory in \hyperlink{structOpmphm}{Opmphm}.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphm_8h_a8028ab6baf6d67246685cc341548df0d}\label{kdbopmphm_8h_a8028ab6baf6d67246685cc341548df0d}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Graph\+Del@{opmphm\+Graph\+Del}}
\index{opmphm\+Graph\+Del@{opmphm\+Graph\+Del}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Graph\+Del()}{opmphmGraphDel()}}
{\footnotesize\ttfamily void opmphm\+Graph\+Del (\begin{DoxyParamCaption}\item[{Opmphm\+Graph $\ast$}]{graph }\end{DoxyParamCaption})}



Deletes the Opmphm\+Graph. 


\begin{DoxyParams}{Parameters}
{\em graph} & the Opmphm\+Graph \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphm_8h_abb60c552d370e227774d6eac740aaa85}\label{kdbopmphm_8h_abb60c552d370e227774d6eac740aaa85}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Graph\+New@{opmphm\+Graph\+New}}
\index{opmphm\+Graph\+New@{opmphm\+Graph\+New}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Graph\+New()}{opmphmGraphNew()}}
{\footnotesize\ttfamily Opmphm\+Graph$\ast$ opmphm\+Graph\+New (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm,  }\item[{size\+\_\+t}]{n,  }\item[{double}]{c }\end{DoxyParamCaption})}



Allocates and initializes the Opmphm\+Graph. 

The Opmphm\+Graph represents a r-\/partite hypergraph. Calculates also the size of one partition in the r-\/partite hypergraph and stores it in {\ttfamily opmphm-\/$>$component\+Size}.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
{\em n} & the number of elements \\
\hline
{\em c} & space influencing parameter\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em Opmphm\+Graph} & $\ast$ success \\
\hline
{\em N\+U\+LL} & memory error \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_aa75546e6b30698cbdbed23bc7eddf359}\label{kdbopmphm_8h_aa75546e6b30698cbdbed23bc7eddf359}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Is\+Empty@{opmphm\+Is\+Empty}}
\index{opmphm\+Is\+Empty@{opmphm\+Is\+Empty}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Is\+Empty()}{opmphmIsEmpty()}}
{\footnotesize\ttfamily int opmphm\+Is\+Empty (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm }\end{DoxyParamCaption})}



Determines if the O\+P\+M\+P\+HM is Empty. 

Empty means opmphm-\/$>$size is 0.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em true} & empty \\
\hline
{\em false} & non empty \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_a24fe857fb60d0d3bb85568f1b73fb77b}\label{kdbopmphm_8h_a24fe857fb60d0d3bb85568f1b73fb77b}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Lookup@{opmphm\+Lookup}}
\index{opmphm\+Lookup@{opmphm\+Lookup}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Lookup()}{opmphmLookup()}}
{\footnotesize\ttfamily size\+\_\+t opmphm\+Lookup (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm,  }\item[{const void $\ast$}]{name }\end{DoxyParamCaption})}



Lookup functions. 

Lookup functions.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
{\em name} & the name of the element\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em size\+\_\+t} & the order of the element. \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_aac350c6406d4fdf71e6832900e47a79b}\label{kdbopmphm_8h_aac350c6406d4fdf71e6832900e47a79b}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+Mapping@{opmphm\+Mapping}}
\index{opmphm\+Mapping@{opmphm\+Mapping}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Mapping()}{opmphmMapping()}}
{\footnotesize\ttfamily int opmphm\+Mapping (\begin{DoxyParamCaption}\item[{\hyperlink{structOpmphm}{Opmphm} $\ast$}]{opmphm,  }\item[{Opmphm\+Graph $\ast$}]{graph,  }\item[{Opmphm\+Init $\ast$}]{init,  }\item[{size\+\_\+t}]{n }\end{DoxyParamCaption})}



Build functions. 

Build functions.

Sets the seeds for the opmphm\+Hashfunctions, {\ttfamily Opmphm\+Init-\/$>$init\+Seed} will be changed. Inserts each element as edge in the r-\/partite hypergraph and checks if the graph contains a cycle.


\begin{DoxyParams}{Parameters}
{\em opmphm} & the O\+P\+M\+P\+HM \\
\hline
{\em graph} & the Opmphm\+Graph \\
\hline
{\em init} & the Opmphm\+Init \\
\hline
{\em n} & the number of elements\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em 0} & on success \\
\hline
{\em -\/1} & mapping not possible \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_ad6b70f700b4e2552b128917b5c1074af}\label{kdbopmphm_8h_ad6b70f700b4e2552b128917b5c1074af}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+MinC@{opmphm\+MinC}}
\index{opmphm\+MinC@{opmphm\+MinC}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+Min\+C()}{opmphmMinC()}}
{\footnotesize\ttfamily double opmphm\+MinC (\begin{DoxyParamCaption}\item[{void}]{ }\end{DoxyParamCaption})}



Graph functions. 

Graph functions.

This minimal values come from Fabiano Cupertino Botelho, Near-\/\+Optimal Space Perfect Hashing Algorithms, 2008.


\begin{DoxyRetVals}{Return values}
{\em c} & the minimal c value \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphm_8h_a9cd39724926a210dd21d7fcc351e5300}\label{kdbopmphm_8h_a9cd39724926a210dd21d7fcc351e5300}} 
\index{kdbopmphm.\+h@{kdbopmphm.\+h}!opmphm\+New@{opmphm\+New}}
\index{opmphm\+New@{opmphm\+New}!kdbopmphm.\+h@{kdbopmphm.\+h}}
\subsubsection{\texorpdfstring{opmphm\+New()}{opmphmNew()}}
{\footnotesize\ttfamily \hyperlink{structOpmphm}{Opmphm}$\ast$ opmphm\+New (\begin{DoxyParamCaption}\item[{void}]{ }\end{DoxyParamCaption})}



Basic functions. 

Basic functions.

The returned O\+P\+M\+P\+HM instance is Empty.


\begin{DoxyRetVals}{Return values}
{\em \hyperlink{structOpmphm}{Opmphm}} & $\ast$ success \\
\hline
{\em N\+U\+LL} & memory error \\
\hline
\end{DoxyRetVals}
