\label{doc_dev_data-structures_md_md_doc_dev_data_structures}%
\Hypertarget{doc_dev_data-structures_md_md_doc_dev_data_structures}%
 For an introduction, please \mbox{\hyperlink{doc_dev_classes_md}{read first about elektra classes}}. You might want to read \mbox{\hyperlink{doc_dev_architecture_md}{about architecture first}}.\hypertarget{doc_dev_data-structures_md_autotoc_md2122}{}\doxysection{Introduction}\label{doc_dev_data-structures_md_autotoc_md2122}
Data structures define the common layer in Elektra. They are used to transfer configuration between Elektra and applications, but also between plugins.\hypertarget{doc_dev_data-structures_md_autotoc_md2123}{}\doxysubsection{ADT}\label{doc_dev_data-structures_md_autotoc_md2123}
Both the {\ttfamily Key\+Set} and the interface to metadata within a {\ttfamily Key} are actually {\bfseries{ADT}} (abstract data types). The API is designed so that different implementations of the data structures can be used internally.

A {\bfseries{hash}} data structure presents a good candidate as alternative data structure, especially for the metadata interface. It is believed to be much faster on lookup, but considerably slower on sorted enumeration.

An {\bfseries{AVL tree}} also serves as a competitor. AVL trees are expected to be faster for inserting keys at any place, but may be slower for appending because of the needed reorganizations. Their disadvantage is that they need to allocate a large number of small pieces of memory. Further investigations, namely implementation and benchmarks, are required to decide.

A {\bfseries{trie}} could also be used for lookup of key names. It performs well for lookup, but needs more memory allocations.

Currently the {\ttfamily Key\+Set} is implemented as a sorted array. It is fast on appending and iterating, and has nearly no size-\/overhead. To improve the lookup-\/time, an additional {\bfseries{hash}} will be used.\hypertarget{doc_dev_data-structures_md_autotoc_md2124}{}\doxysubsection{ABI compatibility}\label{doc_dev_data-structures_md_autotoc_md2124}
Application binary interface, or ABI, is the interface to all data structures of an application or library directly allocated or accessed by the user.

Special care has been taken in Elektra to support all changes within the data structures without any ABI changes. ABI changes would entail the recompilation of applications and plugins using Elektra. The functions {\ttfamily \mbox{\hyperlink{group__key_gad23c65b44bf48d773759e1f9a4d43b89}{key\+New()}}}, {\ttfamily \mbox{\hyperlink{group__keyset_ga671e1aaee3ae9dc13b4834a4ddbd2c3c}{ks\+New()}}} and {\ttfamily \mbox{\hyperlink{group__kdb_ga844e1299a84c3fbf1d3a905c5c893ba5}{kdb\+Open()}}} allocate the data structures for the applications. The user only gets pointers to them. It is not possible for the user to allocate or access these data structures directly when only using the public header file {\ttfamily $<$kdb.\+h$>$}. The functions {\ttfamily \mbox{\hyperlink{group__key_ga3df95bbc2494e3e6703ece5639be5bb1}{key\+Del()}}}, {\ttfamily \mbox{\hyperlink{group__keyset_ga27e5c16473b02a422238c8d970db7ac8}{ks\+Del()}}} and {\ttfamily \mbox{\hyperlink{group__kdb_gadb54dc9fda17ee07deb9444df745c96f}{kdb\+Close()}}} free the resources after use. Using the C++ binding deallocation is done automatically.\hypertarget{doc_dev_data-structures_md_autotoc_md2125}{}\doxysection{Meta Data}\label{doc_dev_data-structures_md_autotoc_md2125}
Read \mbox{\hyperlink{doc_dev_metadata_md}{here}}.\hypertarget{doc_dev_data-structures_md_autotoc_md2126}{}\doxysection{Key\+Set}\label{doc_dev_data-structures_md_autotoc_md2126}
This subsection describes what has changed between 0.\+7 and 0.\+8 and deals with some general implementation issues.\hypertarget{doc_dev_data-structures_md_autotoc_md2127}{}\doxysubsection{Operations}\label{doc_dev_data-structures_md_autotoc_md2127}
{\ttfamily Key\+Set} resembles the classical mathematical set. Operations like union, intersection or difference are well defined. In mathematics typically every operation yields a new set. Instead, we try to reuse sets in the following ways\+:


\begin{DoxyItemize}
\item A completely new and independent {\ttfamily Key\+Set} as return value would resemble the mathematical ideal closely. This operation would be expensive. Every {\ttfamily Key} needs to be duplicated and inserted into a new {\ttfamily Key\+Set}.

Such a {\bfseries{deep duplication}} was only needed in {\ttfamily \mbox{\hyperlink{group__kdb_ga11436b058408f83d303ca5e996832bcf}{kdb\+Set()}}}.
\item The resulting {\ttfamily Key\+Set} is created during the operation, but only a flat copy is made. This means that the keys in it are actually not duplicated, but only their reference counter is increased. This method is similar to the mathematical model. Compared with a deep copy it can achieve good performance. But all changes to the values of keys in the resulting {\ttfamily Key\+Set} affect the original {\ttfamily Key\+Set}, too.

{\ttfamily \mbox{\hyperlink{group__keyset_gac59e4b328245463f1451f68d5106151c}{ks\+Dup(const Key\+Set $\ast$source)}}} produces a new {\ttfamily Key\+Set}. That way the {\ttfamily source} is not changed as shown by the {\ttfamily const} modifier.
\item The result of the operation is applied to the {\ttfamily Key\+Set} passed as argument directly. This is actually quite common, but for this situation other names of the operations are more suitable.

For example, a union which changes the {\ttfamily Key\+Set} is called {\ttfamily \mbox{\hyperlink{group__keyset_ga21eb9c3a14a604ee3a8bdc779232e7b7}{ks\+Append()}}}.
\item A new {\ttfamily Key\+Set} is created, but the {\ttfamily Key\+Set} passed as parameter is reduced by the keys needed for the new {\ttfamily Key\+Set}. This is useful in situations where many operations have to be applied in a sequence reducing the given {\ttfamily Key\+Set} until no more keys are left. None of the reference pointers change in this situation.

{\ttfamily \mbox{\hyperlink{group__keyset_ga6b00cf82b59af4d883a9bad6cf4a4a4a}{ks\+Cut(\+Key\+Set $\ast$ks, const Key $\ast$cutpoint)}}} works that way. All keys below the {\ttfamily cutpoint} are moved from {\ttfamily ks} to the returned key set.
\end{DoxyItemize}\hypertarget{doc_dev_data-structures_md_autotoc_md2128}{}\doxysubsection{Consistency}\label{doc_dev_data-structures_md_autotoc_md2128}
There are several ways to define consistency relations on key sets. For {\bfseries{strict consistency}} every parent key must exist before the user can append a key to a key set. For example, the key set with the keys


\begin{DoxyCode}{0}
\DoxyCodeLine{system:/}
\DoxyCodeLine{system:/elektra}
\DoxyCodeLine{system:/elektra/mountpoints}

\end{DoxyCode}


would allow the key {\ttfamily system\+:/elektra/mountpoints/tcl} to be added, but not the key {\ttfamily system\+:/apps/abc} because {\ttfamily system\+:/apps} is missing. File systems enforce this kind of consistency.

These semantics are however not useful for configurations. Especially for user configurations often only some keys need to be overwritten. It is not a good idea to copy all parent keys to the users configuration. For this reason we use a less strict definition of consistency supporting such holes.

We also evaluated a form of {\bfseries{weak consistency}}. It avoids adding some unnecessary keys. A constraint is that a key can be added only if it has a parent key. But the constraint does not apply if no other key exists above the key about to be inserted. From that moment it will serve as parent key for other keys. With the current implementation of {\ttfamily Key\+Set}, however, it is not possible to decide this constraint in constant time. Instead its worst-\/case complexity would be \$log(n) $\ast$ x\$ where \$n\$ is the number of keys currently in the key set and \$x\$ is the {\itshape depth} of the key. The depth is the number of {\ttfamily /} in the key name. The worst-\/case of the complexity applies when the inserting works without a parent key. For example, with the keys


\begin{DoxyCode}{0}
\DoxyCodeLine{user:/sw/apps/abc/current/bindings}
\DoxyCodeLine{user:/sw/apps/abc/current/bindings/key1}
\DoxyCodeLine{user:/sw/apps/abc/current/bindings/key2}

\end{DoxyCode}


the weak consistency would allow inserting {\ttfamily user\+:/sw/apps/abc/current/bindings/key3} because it is directly below an existing key. It would also allow adding {\ttfamily user\+:/sw/apps/xyz/current} because it does not have any parent key. But it would not allow {\ttfamily user\+:/sw/apps/abc/current/bindings/dir/key1} to add. The worst-\/case complexity was found to be too expensive, and hence {\ttfamily Key\+Set} has {\bfseries{no consistency}} check at all.

This means any key with a valid key name can be inserted into {\ttfamily Key\+Set}. The {\ttfamily Key\+Set} is changed so that it is now impossible to append keys without a name. {\ttfamily ks\+Append\+Key(ks, Key $\ast$to\+Append)} takes ownership of the key {\ttfamily to\+Append} and will delete the key in that case. The caller does not have to free {\ttfamily to\+Append}\+: either it is in the key set or it is deleted.

Binary search determines the position where to insert a key. The C version of binary search {\ttfamily bsearch()} cannot tell where to insert a key when it is not found. So the algorithm has to be reimplemented. Java\textquotesingle{}s binary search {\ttfamily binary\+Search()} uses a trick to both indicate where a key is found and where to insert it with the same return code by returning the negative value {\ttfamily ((-\/insertion point) -\/ 1)} indicating where the new value should be inserted when the key is not found. Elektra now also uses this trick internally.\hypertarget{doc_dev_data-structures_md_autotoc_md2129}{}\doxysubsection{Internal Cursor}\label{doc_dev_data-structures_md_autotoc_md2129}
{\ttfamily Key\+Set} supports an {\bfseries{external iterator}} with the two functions {\ttfamily \mbox{\hyperlink{group__keyset_gabe793ff51f1728e3429c84a8a9086b70}{ks\+Rewind()}}} to go to the beginning and {\ttfamily \mbox{\hyperlink{group__keyset_ga317321c9065b5a4b3e33fe1c399bcec9}{ks\+Next()}}} to advance the {\itshape internal cursor} to the next key. This side effect is used to indicate a position for operations on a {\ttfamily Key\+Set} without any additional parameter. This technique is comfortable to see which key has caused an error after an unsuccessful key database operation.

Elektra only has some functions to change the cursor of a key set. But these allow the user to compose powerful functions. Plugins do that extensively as we will see later in {\ttfamily ks\+Lookup\+RE()}. The user can additionally write more such functions for his or her own purposes. To change the internal cursor, it is sufficient to iterate over the {\ttfamily Key\+Set} and stop at the wanted key. With this technique, we can, for example, realize lookup by value, by specific metadata and by parts of the name. Without an additional index, it is not possible that such operations perform more efficiently than by a linear iteration key by key. For that reason, Elektra’s core does not provide such functions. The function {\ttfamily \mbox{\hyperlink{group__keyset_gad65d2cdcbb5381194a1688e169af8a83}{ks\+Lookup\+By\+Name()}}}, however, uses the more efficient binary search because the array inside the {\ttfamily Key\+Set} is ordered by name.\hypertarget{doc_dev_data-structures_md_autotoc_md2130}{}\doxysubsection{External Cursor}\label{doc_dev_data-structures_md_autotoc_md2130}
External cursor is an alternative to the approach explained above. Elektra provides a limited {\itshape external cursor} through the interface {\ttfamily \mbox{\hyperlink{group__keyset_gace0444eb8ec958a429794f8586fc72e7}{ks\+Get\+Cursor()}}} and {\ttfamily \mbox{\hyperlink{group__keyset_ga28b2a7d13c620b3c9d4815a0608c738f}{ks\+Set\+Cursor()}}}. It is not possible to advance this cursor. The difference to the internal cursor is that the position is not stored within {\ttfamily Key\+Set}.

We considered providing an external cursor for performance reasons. But we found out that the speed of iteration is mainly limited because of safety checks. The investigated methods become slower proportional to the ease of use and safety. When using null pointers and range checks, the function is noticeably slower than without. With the same amount of checks, using an external cursor is not much faster than {\ttfamily \mbox{\hyperlink{group__keyset_ga317321c9065b5a4b3e33fe1c399bcec9}{ks\+Next()}}}. External cursor with checks is in a benchmark about 10\% faster.

But an external cursor directly accessing the array can be much faster. Using an unchecked external cursor can be about 50\% faster than using the internal cursor with \mbox{\hyperlink{group__keyset_ga317321c9065b5a4b3e33fe1c399bcec9}{ks\+Next()}}. For this endeavour, Elektra’s private header files need to be included. Including private header files, however, should not be done with levity because ABI compatibility will be gone on any changes of the data structures. This fact means the application or plugin needs to be recompiled when any of the internal structures of Elektra are changed. We strongly discourage including these header files.

Nevertheless, the overall performance impact for iteration is minimal and should not matter too much. Even if only a single {\ttfamily \mbox{\hyperlink{group__keymeta_gae1f15546b234ffb6007d8a31178652b9}{key\+Set\+Meta()}}} is used inside the iteration loop, the iteration costs are insignificant. Only for trivial actions such as just changing a variable, counter or marker for every key the iteration costs become the lion\textquotesingle{}s share. In such situations an {\itshape internal iterator} yields better results. For example, {\ttfamily ks\+For\+Each()} applies a user defined function for every key in a {\ttfamily Key\+Set} without having null pointer or out of range problems.\hypertarget{doc_dev_data-structures_md_autotoc_md2131}{}\doxysection{Trie vs. Split}\label{doc_dev_data-structures_md_autotoc_md2131}
Up to now, we have discussed external data structures visible to the user of the library. The application and plugin programmer needs them to access configuration. Last, but not least, we will show two internal data structures. The user will not see them. To understand the algorithm, however, the user needs to understand them as well.\hypertarget{doc_dev_data-structures_md_autotoc_md2132}{}\doxysubsection{Trie}\label{doc_dev_data-structures_md_autotoc_md2132}
A {\itshape Trie} or prefix tree is an ordered tree data structure. In Elektra, it provides the information to decide in which backend a key resides. The algorithm, presented in \mbox{\hyperlink{doc_dev_algorithm_md}{algorithm}}, also needs a list of all backends. The initial approach was to iterate over the {\ttfamily Trie} to get a list of all backends. But the transformation of a {\ttfamily Trie} to a list of backends, contained many bugs caused by corner cases in connection with the default backend and cascading mount points.\hypertarget{doc_dev_data-structures_md_autotoc_md2133}{}\doxysubsection{Split}\label{doc_dev_data-structures_md_autotoc_md2133}
So, instead of transforming the trie to a list of backends, we introduced a new data structure called {\ttfamily Split}. The name {\ttfamily Split} comes from the fact that an initial key set is split into many key sets. These key sets are stored in the {\ttfamily Split} object. {\ttfamily Split} advanced to the central data structure for the algorithm\+:


\begin{DoxyCode}{0}
\DoxyCodeLine{\textcolor{keyword}{typedef} \textcolor{keyword}{struct }\_Split   Split;}
\DoxyCodeLine{}
\DoxyCodeLine{\textcolor{keyword}{struct }\_Split \{}
\DoxyCodeLine{        \textcolor{keywordtype}{size\_t} size;}
\DoxyCodeLine{        \textcolor{keywordtype}{size\_t} alloc;}
\DoxyCodeLine{        KeySet **keysets;}
\DoxyCodeLine{        Backend **handles;}
\DoxyCodeLine{        Key **parents;}
\DoxyCodeLine{        \textcolor{keywordtype}{int} *syncbits;}
\DoxyCodeLine{\};}

\end{DoxyCode}


The data structure {\ttfamily Split} contains the following fields\+:


\begin{DoxyItemize}
\item {\bfseries{size}}\+: contains the number of key sets currently in {\ttfamily Split}.
\item {\bfseries{alloc}}\+: allows us to allocate more items than currently in use.
\item {\bfseries{keysets}} represents a list of key sets. The keys in one of the key sets are known to belong to a specific backend.
\item {\bfseries{handles}}\+: contains a list of handles to backends.
\item {\bfseries{parents}}\+: represents a list of keys. Each {\ttfamily parent\+Key} contains the root key of a backend. No key of the respective key set is above the {\ttfamily parent\+Key}. The key name of {\ttfamily parent\+Key} contains the mount point of a backend. The resolver writes the file name into the value of the {\ttfamily parent\+Key}.
\item {\bfseries{syncbits}}\+: are some bits that can be set for every backend. The algorithm uses the {\ttfamily syncbits} to decide if the key set needs to be synchronized.
\end{DoxyItemize}

Continue reading \mbox{\hyperlink{doc_dev_error-handling_md}{with the error handling}}.\hypertarget{doc_dev_data-structures_md_autotoc_md2134}{}\doxysection{Order Preserving Minimal Perfect Hash Map (aka OPMPHM)}\label{doc_dev_data-structures_md_autotoc_md2134}
The OPMPHM is a non-\/dynamic randomized hash map of the Las Vegas type, that creates an index over the elements, to gain O(1) access.

The elements must be arranged in an array and each element must have a unique name, to identify the elements. The source can be found in \href{/home/jenkins/workspace/libelektra-release/src/include/kdbopmphm.h}{\texttt{ kdbopmphm.\+h}} and \href{/home/jenkins/workspace/libelektra-release/src/libs/elektra/opmphm.c}{\texttt{ opmphm.\+c}} and also works outside of Elektra.

The OPMPHM does not store any buckets, your array of elements are the buckets and the OPMPHM represent an arbitrary index over those. The desired index of an element, also known as the order, is set in {\ttfamily Opmphm\+Graph-\/$>$edges\mbox{[}i\mbox{]}.order}, where {\ttfamily i} is the i-\/th element in your array. When the orders should represent the array indices, the default order can be applied during the assignment step. When the orders are not the default order, {\ttfamily Opmphm\+Graph-\/$>$edges\mbox{[}i\mbox{]}.order} should be set before the assignment step.

Because the OPMPHM is non-\/dynamic, there are no insert and delete operations. The OPMPHM gets build for a static set of elements, once the OPMPHM is build, every\+:


\begin{DoxyItemize}
\item change of at least one indexed element name
\item addition of a new element
\item deletion of an indexed element
\end{DoxyItemize}

leads to an invalid OPMPHM and forces a rebuild. A build consists of two steps the mapping step and the assignment step.

During the mapping step the OPMPHM maps each element to an edge in an random acyclic r-\/uniform r-\/partite hypergraph. In a r-\/uniform r-\/partite hypergraph each edge connects {\ttfamily r} vertices, each vertex in a different component. The probability of being acyclic and the number of mapping step invocations depends on the the following variables\+:


\begin{DoxyItemize}
\item {\ttfamily r}\+: The {\ttfamily r} variable defines the number of components in the random r-\/uniform r-\/partite hypergraph. Use the {\ttfamily opmphm\+OptR (n)} function to get an optimal value for your number of elements ({\ttfamily n}).
\item {\ttfamily c}\+: The {\ttfamily c} variable defines the number of vertices in each component of the random r-\/uniform r-\/partite hypergraph. The number of vertices in one component is defined as {\ttfamily (c $\ast$ n / r) + 1}, where {\ttfamily n} is the number of elements and {\ttfamily r} is the variable from above. The {\ttfamily c} variable must have a minimal value to ensure a success probability, use the {\ttfamily opmphm\+MinC (r)} function, with your {\ttfamily r} from above. The ensure an optimal time until success increment the {\ttfamily c} variable with the value from the {\ttfamily opmphm\+OptC (n)} function, where {\ttfamily n} is the number of elements.
\item {\ttfamily init\+Seed}\+: The initial seed set in {\ttfamily Opmphm\+Init-\/$>$init\+Seed}.
\end{DoxyItemize}

{\ttfamily opmphm\+OptR (n)} and {\ttfamily opmphm\+OptC (n)} are heuristic functions constructed through benchmarks. Optimal is only one mapping step invocation in 99.\+5\% of the observed cases. The benchmarks took arbitrary uniform distributed initial seeds and the heuristic functions are made to work with almost every seed.\hypertarget{doc_dev_data-structures_md_autotoc_md2135}{}\doxysubsection{The Build}\label{doc_dev_data-structures_md_autotoc_md2135}
\hypertarget{doc_dev_data-structures_md_autotoc_md2136}{}\doxysubsubsection{Initialization}\label{doc_dev_data-structures_md_autotoc_md2136}
Use {\ttfamily opmphm\+New ()} and {\ttfamily opmphm\+Graph\+New (...)} to instantiate the needed structures. The function {\ttfamily opmphm\+Graph\+New (...)} takes {\ttfamily r} and {\ttfamily c} as parameter. Use the {\ttfamily opmphm\+OptR (...)} function to get your {\ttfamily r} value, use this {\ttfamily r} also to get your {\ttfamily c} value the following way\+:

{\ttfamily c = opmphm\+MinC (r) + opmphm\+OptC (n)}

To initialize the OPMPHM build the {\ttfamily Opmphm\+Init} must be set with information about your data. Set your data array {\ttfamily Opmphm\+Init-\/$>$data} and the element name extraction function {\ttfamily Opmphm\+Init-\/$>$get\+Name}, which should extract the string from a single data array entry. Provide a good seed in {\ttfamily Opmphm\+Init-\/$>$init\+Seed}, needed in the next step.\hypertarget{doc_dev_data-structures_md_autotoc_md2137}{}\doxysubsubsection{Mapping}\label{doc_dev_data-structures_md_autotoc_md2137}
The function {\ttfamily opmphm\+Mapping} uses your seed (the {\ttfamily Opmphm\+Init-\/$>$seed} will be changed) and tries to construct the random acyclic r-\/uniform r-\/partite hypergraph, this might not succeed, on cycles just call it again.\hypertarget{doc_dev_data-structures_md_autotoc_md2138}{}\doxysubsubsection{Assignment}\label{doc_dev_data-structures_md_autotoc_md2138}
The {\ttfamily opmphm\+Assignment ()} function assigns either your order (set at {\ttfamily Opmphm\+Graph-\/$>$edges\mbox{[}i\mbox{]}.order}) or a default order. The {\ttfamily default\+Order} parameter indicates the behavior.

After the build the Opmphm\+Init and Opmphm\+Graph should be freed. The OPMPHM is now ready for constant lookups with the {\ttfamily opmphm\+Lookup ()}.\hypertarget{doc_dev_data-structures_md_autotoc_md2139}{}\doxysubsection{The Rebuild}\label{doc_dev_data-structures_md_autotoc_md2139}
Once build, follow the steps from the build, just omit the {\ttfamily opmphm\+New ()} invocation. 