\hypertarget{kdbopmphmpredictor_8h}{}\section{kdbopmphmpredictor.\+h File Reference}
\label{kdbopmphmpredictor_8h}\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}


Defines for the Order Preserving Minimal Perfect Hash Map Predictor.  


{\ttfamily \#include $<$stdint.\+h$>$}\newline
Include dependency graph for kdbopmphmpredictor.\+h\+:
\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[width=211pt]{kdbopmphmpredictor_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=211pt]{kdbopmphmpredictor_8h__dep__incl}
\end{center}
\end{figure}
\subsection*{Enumerations}
\begin{DoxyCompactItemize}
\item 
enum \mbox{\hyperlink{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bd}{predictorflag\+\_\+t}} \{ \mbox{\hyperlink{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bda43b895c2c396277d92b83fd7bf1e677b}{O\+P\+M\+P\+H\+M\+\_\+\+P\+R\+E\+D\+I\+C\+T\+O\+R\+\_\+\+F\+L\+A\+G\+\_\+\+M\+M\+A\+P\+\_\+\+S\+T\+R\+U\+CT}} = 1, 
\mbox{\hyperlink{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bdaf20f0c3f39d725965385c6007f734295}{O\+P\+M\+P\+H\+M\+\_\+\+P\+R\+E\+D\+I\+C\+T\+O\+R\+\_\+\+F\+L\+A\+G\+\_\+\+M\+M\+A\+P\+\_\+\+P\+A\+T\+T\+E\+R\+N\+T\+A\+B\+LE}} = 1 $<$$<$ 2
 \}
\begin{DoxyCompactList}\small\item\em Opmphm\+Predictor Flags. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Functions}
\begin{DoxyCompactItemize}
\item 
Opmphm\+Predictor $\ast$ \mbox{\hyperlink{kdbopmphmpredictor_8h_af86a5206b22f957f33aba0f3d5207146}{opmphm\+Predictor\+New}} (void)
\begin{DoxyCompactList}\small\item\em Basic functions. \end{DoxyCompactList}\item 
void \mbox{\hyperlink{kdbopmphmpredictor_8h_a8e2b941eecc192cf894b2490fcfbf2b5}{opmphm\+Predictor\+Del}} (Opmphm\+Predictor $\ast$op)
\begin{DoxyCompactList}\small\item\em Deletes the Opmphm\+Predictor. \end{DoxyCompactList}\item 
void \mbox{\hyperlink{kdbopmphmpredictor_8h_a0fdf217cbfc0c6601113327cfdfc90ee}{opmphm\+Predictor\+Copy}} (Opmphm\+Predictor $\ast$dest, Opmphm\+Predictor $\ast$source)
\begin{DoxyCompactList}\small\item\em Make a copy of the Opmphm\+Predictor. \end{DoxyCompactList}\item 
size\+\_\+t \mbox{\hyperlink{kdbopmphmpredictor_8h_af9c730ba754c0b164555b85e2bf9f097}{opmphm\+Predictor\+Worth\+Opmphm}} (size\+\_\+t n)
\begin{DoxyCompactList}\small\item\em Heuristic function. \end{DoxyCompactList}\item 
int \mbox{\hyperlink{kdbopmphmpredictor_8h_a6dab3e7c921f8adc655bd893cfbfb4cb}{opmphm\+Predictor}} (Opmphm\+Predictor $\ast$op, size\+\_\+t n)
\begin{DoxyCompactList}\small\item\em Predictor functions. \end{DoxyCompactList}\item 
void \mbox{\hyperlink{kdbopmphmpredictor_8h_a31b9dd2f3c89816f5674f2261faf6224}{opmphm\+Predictor\+Inc\+Count\+Opmphm}} (Opmphm\+Predictor $\ast$op)
\begin{DoxyCompactList}\small\item\em Increases the counter when the O\+P\+M\+P\+HM was used for the ks\+Lookup (...) . \end{DoxyCompactList}\item 
int \mbox{\hyperlink{kdbopmphmpredictor_8h_a47e4441629a4de43e45387560052066f}{opmphm\+Predictor\+Inc\+Count\+Binary\+Search}} (Opmphm\+Predictor $\ast$op, size\+\_\+t n)
\begin{DoxyCompactList}\small\item\em Increases the counter when the Binary Search was used for the ks\+Lookup (...) . \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Variables}
\begin{DoxyCompactItemize}
\item 
const uint16\+\_\+t \mbox{\hyperlink{kdbopmphmpredictor_8h_a2609ca09a3d8479b15140795fe915f1e}{opmphm\+Predictor\+History\+Mask}}
\begin{DoxyCompactList}\small\item\em Order Preserving Minimal Perfect Hash Map Predictor. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{kdbopmphmpredictor_8h_aca6e420bdc1b2730db1ed6685cc14519}\label{kdbopmphmpredictor_8h_aca6e420bdc1b2730db1ed6685cc14519}} 
const size\+\_\+t \mbox{\hyperlink{kdbopmphmpredictor_8h_aca6e420bdc1b2730db1ed6685cc14519}{opmphm\+Predictor\+Action\+Limit}}
\begin{DoxyCompactList}\small\item\em The opmphm\+Predictor\+Action\+Limit define the minimum Key\+Set size necessary for predictor actions. \end{DoxyCompactList}\end{DoxyCompactItemize}


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

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


\subsection{Enumeration Type Documentation}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bd}\label{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bd}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!predictorflag\_t@{predictorflag\_t}}
\index{predictorflag\_t@{predictorflag\_t}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{predictorflag\_t}{predictorflag\_t}}
{\footnotesize\ttfamily enum \mbox{\hyperlink{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bd}{predictorflag\+\_\+t}}}



Opmphm\+Predictor Flags. 

\begin{DoxyEnumFields}{Enumerator}
\raisebox{\heightof{T}}[0pt][0pt]{\index{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_STRUCT@{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_STRUCT}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!OPMPHM\_PREDICTOR\_FLAG\_MMAP\_STRUCT@{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_STRUCT}}}\mbox{\Hypertarget{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bda43b895c2c396277d92b83fd7bf1e677b}\label{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bda43b895c2c396277d92b83fd7bf1e677b}} 
O\+P\+M\+P\+H\+M\+\_\+\+P\+R\+E\+D\+I\+C\+T\+O\+R\+\_\+\+F\+L\+A\+G\+\_\+\+M\+M\+A\+P\+\_\+\+S\+T\+R\+U\+CT&Opmphm\+Predictor struct lies inside a mmap region. This flag is set for Opmphm\+Predictor structs inside a mapped region. It prevents erroneous free() calls on these Opmphm\+Predictors. \\
\hline

\raisebox{\heightof{T}}[0pt][0pt]{\index{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_PATTERNTABLE@{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_PATTERNTABLE}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!OPMPHM\_PREDICTOR\_FLAG\_MMAP\_PATTERNTABLE@{OPMPHM\_PREDICTOR\_FLAG\_MMAP\_PATTERNTABLE}}}\mbox{\Hypertarget{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bdaf20f0c3f39d725965385c6007f734295}\label{kdbopmphmpredictor_8h_a7dd4ebe440506fff5d5fc213ec8bb7bdaf20f0c3f39d725965385c6007f734295}} 
O\+P\+M\+P\+H\+M\+\_\+\+P\+R\+E\+D\+I\+C\+T\+O\+R\+\_\+\+F\+L\+A\+G\+\_\+\+M\+M\+A\+P\+\_\+\+P\+A\+T\+T\+E\+R\+N\+T\+A\+B\+LE&Opmphm\+Predictor pattern\+Table lies inside a mmap region. This flag is set for Opmphm\+Predictor pattern\+Tables inside a mapped region. It prevents erroneous free() calls on these pattern\+Tables. \\
\hline

\end{DoxyEnumFields}


\subsection{Function Documentation}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a6dab3e7c921f8adc655bd893cfbfb4cb}\label{kdbopmphmpredictor_8h_a6dab3e7c921f8adc655bd893cfbfb4cb}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictor@{opmphmPredictor}}
\index{opmphmPredictor@{opmphmPredictor}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictor()}{opmphmPredictor()}}
{\footnotesize\ttfamily int opmphm\+Predictor (\begin{DoxyParamCaption}\item[{Opmphm\+Predictor $\ast$}]{op,  }\item[{size\+\_\+t}]{n }\end{DoxyParamCaption})}



Predictor functions. 

Predictor functions.

Uses the opmphm\+Predictor\+Worth\+Opmphm (...) to check if the previous sequence of ks\+Lookup (...) invocations without alteration was worth using the O\+P\+M\+P\+HM. Updates the state with the prediction\+Automata and the worth information of the previous history. Alters the history with the worth information and makes the prediction for the next sequence of ks\+Lookup (...) invocations.


\begin{DoxyParams}{Parameters}
{\em op} & the Predictor \\
\hline
{\em n} & the number of elements in the Key\+Set\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em 1} & it is worth using the O\+P\+M\+P\+HM \\
\hline
{\em 0} & it is not worth using the O\+P\+M\+P\+HM \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a0fdf217cbfc0c6601113327cfdfc90ee}\label{kdbopmphmpredictor_8h_a0fdf217cbfc0c6601113327cfdfc90ee}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorCopy@{opmphmPredictorCopy}}
\index{opmphmPredictorCopy@{opmphmPredictorCopy}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorCopy()}{opmphmPredictorCopy()}}
{\footnotesize\ttfamily void opmphm\+Predictor\+Copy (\begin{DoxyParamCaption}\item[{Opmphm\+Predictor $\ast$}]{dest,  }\item[{Opmphm\+Predictor $\ast$}]{source }\end{DoxyParamCaption})}



Make a copy of the Opmphm\+Predictor. 


\begin{DoxyParams}{Parameters}
{\em source} & the Opmphm\+Predictor source \\
\hline
{\em dest} & the Opmphm\+Predictor destination \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a8e2b941eecc192cf894b2490fcfbf2b5}\label{kdbopmphmpredictor_8h_a8e2b941eecc192cf894b2490fcfbf2b5}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorDel@{opmphmPredictorDel}}
\index{opmphmPredictorDel@{opmphmPredictorDel}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorDel()}{opmphmPredictorDel()}}
{\footnotesize\ttfamily void opmphm\+Predictor\+Del (\begin{DoxyParamCaption}\item[{Opmphm\+Predictor $\ast$}]{op }\end{DoxyParamCaption})}



Deletes the Opmphm\+Predictor. 

Clears and frees all memory in Opmphm\+Predictor.


\begin{DoxyParams}{Parameters}
{\em op} & the Opmphm\+Predictor \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a47e4441629a4de43e45387560052066f}\label{kdbopmphmpredictor_8h_a47e4441629a4de43e45387560052066f}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorIncCountBinarySearch@{opmphmPredictorIncCountBinarySearch}}
\index{opmphmPredictorIncCountBinarySearch@{opmphmPredictorIncCountBinarySearch}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorIncCountBinarySearch()}{opmphmPredictorIncCountBinarySearch()}}
{\footnotesize\ttfamily int opmphm\+Predictor\+Inc\+Count\+Binary\+Search (\begin{DoxyParamCaption}\item[{Opmphm\+Predictor $\ast$}]{op,  }\item[{size\+\_\+t}]{n }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inline]}}



Increases the counter when the Binary Search was used for the ks\+Lookup (...) . 

Prevents also an endless Binary Search usage by a simple heuristic.


\begin{DoxyParams}{Parameters}
{\em op} & the Predictor \\
\hline
{\em n} & the number of elements in the Key\+Set\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em 1} & it is worth using the O\+P\+M\+P\+HM \\
\hline
{\em 0} & it is not worth using the O\+P\+M\+P\+HM \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a31b9dd2f3c89816f5674f2261faf6224}\label{kdbopmphmpredictor_8h_a31b9dd2f3c89816f5674f2261faf6224}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorIncCountOpmphm@{opmphmPredictorIncCountOpmphm}}
\index{opmphmPredictorIncCountOpmphm@{opmphmPredictorIncCountOpmphm}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorIncCountOpmphm()}{opmphmPredictorIncCountOpmphm()}}
{\footnotesize\ttfamily void opmphm\+Predictor\+Inc\+Count\+Opmphm (\begin{DoxyParamCaption}\item[{Opmphm\+Predictor $\ast$}]{op }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inline]}}



Increases the counter when the O\+P\+M\+P\+HM was used for the ks\+Lookup (...) . 


\begin{DoxyParams}{Parameters}
{\em op} & the Predictor \\
\hline
\end{DoxyParams}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_af86a5206b22f957f33aba0f3d5207146}\label{kdbopmphmpredictor_8h_af86a5206b22f957f33aba0f3d5207146}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorNew@{opmphmPredictorNew}}
\index{opmphmPredictorNew@{opmphmPredictorNew}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorNew()}{opmphmPredictorNew()}}
{\footnotesize\ttfamily Opmphm\+Predictor$\ast$ opmphm\+Predictor\+New (\begin{DoxyParamCaption}\item[{void}]{ }\end{DoxyParamCaption})}



Basic functions. 

Basic functions.

Reserves for all possible values of opmphm\+Predictor\+History\+Mask two bits to store all 4 states of the Prediction Automata A2. Sets the initial state to 0.


\begin{DoxyRetVals}{Return values}
{\em Opmphm\+Predictor} & $\ast$ success \\
\hline
{\em N\+U\+LL} & memory error \\
\hline
\end{DoxyRetVals}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_af9c730ba754c0b164555b85e2bf9f097}\label{kdbopmphmpredictor_8h_af9c730ba754c0b164555b85e2bf9f097}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorWorthOpmphm@{opmphmPredictorWorthOpmphm}}
\index{opmphmPredictorWorthOpmphm@{opmphmPredictorWorthOpmphm}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorWorthOpmphm()}{opmphmPredictorWorthOpmphm()}}
{\footnotesize\ttfamily size\+\_\+t opmphm\+Predictor\+Worth\+Opmphm (\begin{DoxyParamCaption}\item[{size\+\_\+t}]{n }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inline]}}



Heuristic function. 

Heuristic function.

This easy and fast computable heuristic function tells how many ks\+Lookup (...) invocations without alteration of the Key\+Set need to be made to justify the O\+P\+M\+P\+HM usage. This heuristic function is developed and measured by benchmarks.


\begin{DoxyParams}{Parameters}
{\em n} & the number of elements in the Key\+Set\\
\hline
\end{DoxyParams}

\begin{DoxyRetVals}{Return values}
{\em size\+\_\+t} & the heuristic value \\
\hline
\end{DoxyRetVals}


\subsection{Variable Documentation}
\mbox{\Hypertarget{kdbopmphmpredictor_8h_a2609ca09a3d8479b15140795fe915f1e}\label{kdbopmphmpredictor_8h_a2609ca09a3d8479b15140795fe915f1e}} 
\index{kdbopmphmpredictor.h@{kdbopmphmpredictor.h}!opmphmPredictorHistoryMask@{opmphmPredictorHistoryMask}}
\index{opmphmPredictorHistoryMask@{opmphmPredictorHistoryMask}!kdbopmphmpredictor.h@{kdbopmphmpredictor.h}}
\subsubsection{\texorpdfstring{opmphmPredictorHistoryMask}{opmphmPredictorHistoryMask}}
{\footnotesize\ttfamily const uint16\+\_\+t opmphm\+Predictor\+History\+Mask}



Order Preserving Minimal Perfect Hash Map Predictor. 

A modified Global History Register and Global Pattern History Table branch prediction algorithm from

Tse-\/\+Yu Yeh and Yale N. Patt \char`\"{}\+Alternative Implementations of Two-\/\+Level Adaptive Branch Prediction\char`\"{} In\+: The 19th Annual International Symposium on Computer Architecture (1992), pp. 124-\/134

Maps the event of branch taken or not to a sequence of ks\+Lookup (...) invocations without Key\+Set alteration that is worth using the O\+P\+M\+P\+HM or not. The predictor looks at past events to predict the future, to keep track of past events the {\ttfamily lookup\+Count} and the {\ttfamily ks\+Size} must be stored.\+opmphm\+Predictor\+History\+Mask defines the length and extraction mask of the global history register interpreted binary it must be a series of 1, with a minimum value of 0x3 and a maximum value of 0x7\+F\+FF.

Order Preserving Minimal Perfect Hash Map Predictor. 