Elektra  0.8.26
Classes | Macros | Typedefs | Functions
kdbopmphm.h File Reference

Defines for the Order Preserving Minimal Perfect Hash Map. More...

#include <stdint.h>
#include <stdlib.h>
Include dependency graph for kdbopmphm.h:
This graph shows which files directly or indirectly include this file:

Classes

struct  OpmphmEdge
 The r-uniform r-partite hypergraph. More...
 
struct  Opmphm
 The opmphm. More...
 

Macros

#define KDB_OPMPHM_MAX_N   795364313
 Order Preserving Minimal Perfect Hash Map. More...
 
#define OPMPHM_HASHFUNCTION_ROT(x, k)   (((x) << (k)) | ((x) >> (32 - (k))))
 Hash function By Bob Jenkins, May 2006 http://burtleburtle.net/bob/c/lookup3.c.
 

Typedefs

typedef const char *(* opmphmGetName) (void *)
 Only needed for Initialisation.
 

Functions

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...
 
OpmphmopmphmNew (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.
 

Detailed Description

Defines for the Order Preserving Minimal Perfect Hash Map.

Macro Definition Documentation

◆ KDB_OPMPHM_MAX_N

#define KDB_OPMPHM_MAX_N   795364313

Order Preserving Minimal Perfect Hash Map.

Based on the work of

Fabiano C. Botelho and Nivio Ziviani "Near-Optimal Space Perfect Hashing Algorithms"

and

Zbigniew J. Czech, George Havas, and Bohdan S. Majewski "An Optimal Algorithm for Generating Minimal Perfect Hash Functions" In: Information Processing Letters 43 (1992), pp. 257–264

For usage look in /doc/dev/datastructures.md "datastructures.md"

Theoretical limit of elements:

The whole OPMPHM is limited to the opmphmHashfunction (...) that returns a uint32_t. The limit of elements is than ((2^32) - 1) * r / c, since (2^32) - 1 is the maximum component size of the r-uniform r-partite hypergraph.

To save space the limit of elements is set to (2^32) - 1.

Function Documentation

◆ 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
opmphmthe OPMPHM
graphthe OpmphmGraph
nthe number of elements
defaultOrderboolean flag
Return values
0on success
-1on 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
opmphmthe OPMPHM

◆ opmphmCopy()

int opmphmCopy ( Opmphm dest,
const Opmphm source 
)

Copies OPMPHM from source to destination.

Clears the dest and copies memory and values from source.

Parameters
destthe OPMPHM destination
sourcethe OPMPHM source
Return values
0on success
-1on memory error

◆ opmphmDel()

void opmphmDel ( Opmphm opmphm)

Deletes the OPMPHM.

Clears and frees all memory in Opmphm.

Parameters
opmphmthe OPMPHM

◆ opmphmGraphClear()

void opmphmGraphClear ( const Opmphm opmphm,
OpmphmGraph *  graph 
)

Clears the OpmphmGraph.

Sets all vertices to 0.

Parameters
opmphmthe OPMPHM
graphthe OpmphmGraph

◆ opmphmGraphDel()

void opmphmGraphDel ( OpmphmGraph *  graph)

Deletes the OpmphmGraph.

Parameters
graphthe OpmphmGraph

◆ 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
opmphmthe OPMPHM
rthe rUniPar
nthe number of elements
cspace influencing parameter
Return values
OpmphmGraph* success
NULLmemory error

◆ opmphmIsBuild()

int opmphmIsBuild ( const Opmphm opmphm)

OPMPHM is build.

Parameters
opmphmthe OPMPHM
Return values
0on false
-1on true or NULL

◆ opmphmLookup()

size_t opmphmLookup ( Opmphm opmphm,
size_t  n,
const void *  name 
)

Lookup functions.

Lookup functions.

Parameters
opmphmthe OPMPHM
nthe number of elements
namethe name of the element
Return values
size_tthe 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
opmphmthe OPMPHM
graphthe OpmphmGraph
initthe OpmphmInit
nthe number of elements
Return values
0on success
-1mapping 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
rthe rUniPar
Return values
cthe minimal c value

◆ opmphmNew()

Opmphm* opmphmNew ( void  )

Basic functions.

Basic functions.

Return values
Opmphm* success
NULLmemory 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
nthe number of elements to hash
Return values
cthe optimal c value

◆ 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
nthe number of elements to hash
Return values
rthe optimal rUniPar