Defines for the Order Preserving Minimal Perfect Hash Map.
More...
#include <stdint.h>
#include <stdlib.h>
#include <kdbtypes.h>
|
typedef const char *(* | opmphmGetName) (void *) |
| Only needed for Initialisation.
|
|
|
double | opmphmMinC (uint8_t r) |
| Functions providing r and c More...
|
|
uint8_t | opmphmOptR (size_t n) |
| Provides the optimal r value for a given n More...
|
|
double | opmphmOptC (size_t n) |
| Provides the optimal c value for a given n More...
|
|
OpmphmGraph * | opmphmGraphNew (Opmphm *opmphm, uint8_t r, size_t n, double c) |
| Graph functions. More...
|
|
void | opmphmGraphClear (const Opmphm *opmphm, OpmphmGraph *graph) |
| Clears the OpmphmGraph. More...
|
|
void | opmphmGraphDel (OpmphmGraph *graph) |
| Deletes the OpmphmGraph. More...
|
|
int | opmphmMapping (Opmphm *opmphm, OpmphmGraph *graph, OpmphmInit *init, size_t n) |
| Build functions. More...
|
|
int | opmphmAssignment (Opmphm *opmphm, OpmphmGraph *graph, size_t n, int defaultOrder) |
| Assigns the vertices of the r-uniform r-partite hypergraph. More...
|
|
size_t | opmphmLookup (Opmphm *opmphm, size_t n, const void *name) |
| Lookup functions. More...
|
|
Opmphm * | opmphmNew (void) |
| Basic functions. More...
|
|
void | opmphmDel (Opmphm *opmphm) |
| Deletes the OPMPHM. More...
|
|
int | opmphmIsBuild (const Opmphm *opmphm) |
| OPMPHM is build. More...
|
|
int | opmphmCopy (Opmphm *dest, const Opmphm *source) |
| Copies OPMPHM from source to destination. More...
|
|
void | opmphmClear (Opmphm *opmphm) |
| Clears the OPMPHM. More...
|
|
uint32_t | opmphmHashfunction (const void *key, size_t length, uint32_t initval) |
| Hash function By Bob Jenkins, May 2006 http://burtleburtle.net/bob/c/lookup3.c Original name: hashlitte.
|
|
Defines for the Order Preserving Minimal Perfect Hash Map.
- Copyright
- BSD License (see doc/COPYING or https://www.libelektra.org)
◆ opmphmflag_t
Opmphm Flags.
Enumerator |
---|
OPMPHM_FLAG_MMAP_STRUCT | Opmphm struct lies inside a mmap region. This flag is set for Opmphm structs inside a mapped region. It prevents erroneous free() calls on these Opmphm structs.
|
OPMPHM_FLAG_MMAP_HASHFUNCTIONSEEDS | Opmphm hashFunctionSeeds lies inside a mmap region. This flag is set for Opmphm hashFunctionSeeds inside a mapped region. It prevents erroneous free() calls on these hashFunctionSeeds.
|
OPMPHM_FLAG_MMAP_GRAPH | Opmphm graph lies inside a mmap region. This flag is set for Opmphm graphs inside a mapped region. It prevents erroneous free() calls on these graphs.
|
◆ opmphmAssignment()
int opmphmAssignment |
( |
Opmphm * |
opmphm, |
|
|
OpmphmGraph * |
graph, |
|
|
size_t |
n, |
|
|
int |
defaultOrder |
|
) |
| |
Assigns the vertices of the r-uniform r-partite hypergraph.
Allocs the memory for the final OPMPHM Opmphm->graph
. Uses the remove sequence OpmphmGraph->removeSequence
, generated during cycle check, to assign each vertex. Either with OpmphmEdge->order
or the default order, default is the order of OpmphmInit->data
.
- Parameters
-
opmphm | the OPMPHM |
graph | the OpmphmGraph |
n | the number of elements |
defaultOrder | boolean flag |
- Return values
-
0 | on success |
-1 | on memory error |
◆ opmphmClear()
void opmphmClear |
( |
Opmphm * |
opmphm | ) |
|
Clears the OPMPHM.
The OPMPHM must be successfully created with opmphmNew ()
. Clears and frees all internal memory of Opmphm, but not Opmphm->hashFunctionSeeds
and the Opmphm instance.
- Parameters
-
◆ opmphmCopy()
Copies OPMPHM from source to destination.
Clears the dest and copies memory and values from source.
- Parameters
-
dest | the OPMPHM destination |
source | the OPMPHM source |
- Return values
-
0 | on success |
-1 | on memory error |
◆ opmphmDel()
void opmphmDel |
( |
Opmphm * |
opmphm | ) |
|
Deletes the OPMPHM.
Clears and frees all memory in Opmphm.
- Parameters
-
◆ opmphmGraphClear()
void opmphmGraphClear |
( |
const Opmphm * |
opmphm, |
|
|
OpmphmGraph * |
graph |
|
) |
| |
Clears the OpmphmGraph.
Sets all vertices to 0.
- Parameters
-
opmphm | the OPMPHM |
graph | the OpmphmGraph |
◆ opmphmGraphDel()
void opmphmGraphDel |
( |
OpmphmGraph * |
graph | ) |
|
Deletes the OpmphmGraph.
- Parameters
-
◆ opmphmGraphNew()
OpmphmGraph* opmphmGraphNew |
( |
Opmphm * |
opmphm, |
|
|
uint8_t |
r, |
|
|
size_t |
n, |
|
|
double |
c |
|
) |
| |
Graph functions.
Graph functions.
The OpmphmGraph represents a r-uniform r-partite hypergraph. Lazy initializes the opmphm->hashFunctionSeeds
with r. Calculates also the size of one partition in the r-uniform r-partite hypergraph and stores it in opmphm->componentSize
. Allocates all memory for the OpmphmGraph.
- Parameters
-
opmphm | the OPMPHM |
r | the rUniPar |
n | the number of elements |
c | space influencing parameter |
- Return values
-
OpmphmGraph | * success |
NULL | memory error |
◆ opmphmIsBuild()
int opmphmIsBuild |
( |
const Opmphm * |
opmphm | ) |
|
OPMPHM is build.
- Parameters
-
- Return values
-
0 | on false |
-1 | on true or NULL |
◆ opmphmLookup()
size_t opmphmLookup |
( |
Opmphm * |
opmphm, |
|
|
size_t |
n, |
|
|
const void * |
name |
|
) |
| |
Lookup functions.
Lookup functions.
- Parameters
-
opmphm | the OPMPHM |
n | the number of elements |
name | the name of the element |
- Return values
-
size_t | the order of the element. |
◆ opmphmMapping()
int opmphmMapping |
( |
Opmphm * |
opmphm, |
|
|
OpmphmGraph * |
graph, |
|
|
OpmphmInit * |
init, |
|
|
size_t |
n |
|
) |
| |
Build functions.
Build functions.
Sets the seeds for the opmphmHashfunctions, OpmphmInit->initSeed
will be changed. Inserts each element as edge in the r-uniform r-partite hypergraph and checks if the graph contains a cycle. If there are cycles the graph
will be cleaned
- Parameters
-
opmphm | the OPMPHM |
graph | the OpmphmGraph |
init | the OpmphmInit |
n | the number of elements |
- Return values
-
0 | on success |
-1 | mapping not possible |
◆ opmphmMinC()
double opmphmMinC |
( |
uint8_t |
r | ) |
|
Functions providing r
and c
Functions providing r
and c
This minimal values come from Fabiano Cupertino Botelho, Near-Optimal Space Perfect Hashing Algorithms, 2008.
- Parameters
-
- Return values
-
◆ opmphmNew()
Basic functions.
Basic functions.
- Return values
-
Opmphm | * success |
NULL | memory error |
◆ opmphmOptC()
double opmphmOptC |
( |
size_t |
n | ) |
|
Provides the optimal c
value for a given n
This is a heuristic, the return values follow from the mapping benchmark.
- Parameters
-
n | the number of elements to hash |
- Return values
-
◆ opmphmOptR()
uint8_t opmphmOptR |
( |
size_t |
n | ) |
|
Provides the optimal r
value for a given n
This is a heuristic, the return values follow from the mapping benchmark.
- Parameters
-
n | the number of elements to hash |
- Return values
-