Elektra
0.9.5
|
The Order Preserving Minimal Perfect Hash Map. More...
#include <kdbassert.h>
#include <kdbconfig.h>
#include <kdbhelper.h>
#include <kdblogger.h>
#include <kdbmacros.h>
#include <kdbopmphm.h>
#include <kdbprivate.h>
#include <kdbrand.h>
#include <string.h>
Functions | |
size_t | opmphmLookup (Opmphm *opmphm, size_t n, const void *name) |
Looks up a element in the OPMPHM. More... | |
int | opmphmAssignment (Opmphm *opmphm, OpmphmGraph *graph, size_t n, int defaultOrder) |
Assigns the vertices of the r-uniform r-partite hypergraph. More... | |
int | opmphmMapping (Opmphm *opmphm, OpmphmGraph *graph, OpmphmInit *init, size_t n) |
Maps the elements to edges in the r-uniform r-partite hypergraph. More... | |
double | opmphmMinC (uint8_t r) |
Provides the minimal c value for a given r 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) |
Allocates and initializes the OpmphmGraph. More... | |
void | opmphmGraphClear (const Opmphm *opmphm, OpmphmGraph *graph) |
Clears the OpmphmGraph. More... | |
void | opmphmGraphDel (OpmphmGraph *graph) |
Deletes the OpmphmGraph. More... | |
Opmphm * | opmphmNew (void) |
Allocates and initializes the OPMPHM. More... | |
int | opmphmCopy (Opmphm *dest, const Opmphm *source) |
Copies OPMPHM from source to destination. More... | |
int | opmphmIsBuild (const Opmphm *opmphm) |
OPMPHM is build. More... | |
void | opmphmDel (Opmphm *opmphm) |
Deletes the OPMPHM. More... | |
void | opmphmClear (Opmphm *opmphm) |
Clears the OPMPHM. More... | |
ELEKTRA_NO_SANITIZE_UNDEFINED ELEKTRA_NO_SANITIZE_INTEGER ELEKTRA_NO_SANITIZE_ADDRESS 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. | |
The Order Preserving Minimal Perfect Hash Map.
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
.
opmphm | the OPMPHM |
graph | the OpmphmGraph |
n | the number of elements |
defaultOrder | boolean flag |
0 | on success |
-1 | on memory error |
void opmphmClear | ( | Opmphm * | opmphm | ) |
Copies OPMPHM from source to destination.
Clears the dest and copies memory and values from source.
dest | the OPMPHM destination |
source | the OPMPHM source |
0 | on success |
-1 | on memory error |
void opmphmDel | ( | Opmphm * | opmphm | ) |
void opmphmGraphClear | ( | const Opmphm * | opmphm, |
OpmphmGraph * | graph | ||
) |
Clears the OpmphmGraph.
Sets all vertices to 0.
opmphm | the OPMPHM |
graph | the OpmphmGraph |
void opmphmGraphDel | ( | OpmphmGraph * | graph | ) |
Deletes the OpmphmGraph.
graph | the OpmphmGraph |
OpmphmGraph* opmphmGraphNew | ( | Opmphm * | opmphm, |
uint8_t | r, | ||
size_t | n, | ||
double | c | ||
) |
Allocates and initializes the OpmphmGraph.
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.
opmphm | the OPMPHM |
r | the rUniPar |
n | the number of elements |
c | space influencing parameter |
OpmphmGraph | * success |
NULL | memory error |
int opmphmIsBuild | ( | const Opmphm * | opmphm | ) |
OPMPHM is build.
opmphm | the OPMPHM |
0 | on false |
-1 | on true or NULL |
size_t opmphmLookup | ( | Opmphm * | opmphm, |
size_t | n, | ||
const void * | name | ||
) |
Looks up a element in the OPMPHM.
Lookup functions.
opmphm | the OPMPHM |
n | the number of elements |
name | the name of the element |
size_t | the order of the element. |
int opmphmMapping | ( | Opmphm * | opmphm, |
OpmphmGraph * | graph, | ||
OpmphmInit * | init, | ||
size_t | n | ||
) |
Maps the elements to edges in the r-uniform r-partite hypergraph.
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
opmphm | the OPMPHM |
graph | the OpmphmGraph |
init | the OpmphmInit |
n | the number of elements |
0 | on success |
-1 | mapping not possible |
double opmphmMinC | ( | uint8_t | r | ) |
Provides the minimal c
value for a given r
Functions providing r
and c
This minimal values come from Fabiano Cupertino Botelho, Near-Optimal Space Perfect Hashing Algorithms, 2008.
r | the rUniPar |
c | the minimal c value |
Opmphm* opmphmNew | ( | void | ) |
Allocates and initializes the OPMPHM.
Basic functions.
Opmphm | * success |
NULL | memory error |
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.
n | the number of elements to hash |
c | the optimal c value |
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.
n | the number of elements to hash |
r | the optimal rUniPar |