Elektra  0.8.20
Functions
opmphm.c File Reference

The Order Preserving Minimal Perfect Hash Map. More...

#include <kdbassert.h>
#include <kdbhelper.h>
#include <kdblogger.h>
#include <kdbopmphm.h>
#include <kdbrand.h>
#include <string.h>
Include dependency graph for opmphm.c:

Functions

size_t opmphmLookup (Opmphm *opmphm, 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-partite hypergraph. More...
 
int opmphmMapping (Opmphm *opmphm, OpmphmGraph *graph, OpmphmInit *init, size_t n)
 Maps the elements to edges in a r-partite hypergraph. More...
 
double opmphmMinC (void)
 Provides the minimal c value. More...
 
OpmphmGraph * opmphmGraphNew (Opmphm *opmphm, size_t n, double c)
 Allocates and initializes the OpmphmGraph. More...
 
void opmphmGraphDel (OpmphmGraph *graph)
 Deletes the OpmphmGraph. More...
 
OpmphmopmphmNew (void)
 Allocates and initializes the OPMPHM. More...
 
void opmphmDel (Opmphm *opmphm)
 Deletes the OPMPHM. More...
 
void opmphmClear (Opmphm *opmphm)
 Clears the OPMPHM. More...
 
int opmphmIsEmpty (Opmphm *opmphm)
 Determines if the OPMPHM is Empty. 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

The Order Preserving Minimal Perfect Hash Map.

Function Documentation

◆ opmphmAssignment()

int opmphmAssignment ( Opmphm opmphm,
OpmphmGraph *  graph,
size_t  n,
int  defaultOrder 
)

Assigns the vertices of the r-partite hypergraph.

Allocs the memory for the final OPMPHM Opmphm->graph. Uses the remove sequence OpmphmGraph->removeOrder, 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.

Clears and frees all internal memory of Opmphm, but not the Opmphm instance.

Parameters
opmphmthe OPMPHM

◆ opmphmDel()

void opmphmDel ( Opmphm opmphm)

Deletes the OPMPHM.

Clears and frees all memory in Opmphm.

Parameters
opmphmthe OPMPHM

◆ opmphmGraphDel()

void opmphmGraphDel ( OpmphmGraph *  graph)

Deletes the OpmphmGraph.

Parameters
graphthe OpmphmGraph

◆ opmphmGraphNew()

OpmphmGraph* opmphmGraphNew ( Opmphm opmphm,
size_t  n,
double  c 
)

Allocates and initializes the OpmphmGraph.

The OpmphmGraph represents a r-partite hypergraph. Calculates also the size of one partition in the r-partite hypergraph and stores it in opmphm->componentSize.

Parameters
opmphmthe OPMPHM
nthe number of elements
cspace influencing parameter
Return values
OpmphmGraph* success
NULLmemory error

◆ opmphmIsEmpty()

int opmphmIsEmpty ( Opmphm opmphm)

Determines if the OPMPHM is Empty.

Empty means opmphm->size is 0.

Parameters
opmphmthe OPMPHM
Return values
trueempty
falsenon empty

◆ opmphmLookup()

size_t opmphmLookup ( Opmphm opmphm,
const void *  name 
)

Looks up a element in the OPMPHM.

Lookup functions.

Parameters
opmphmthe OPMPHM
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 
)

Maps the elements to edges in a r-partite hypergraph.

Build functions.

Sets the seeds for the opmphmHashfunctions, OpmphmInit->initSeed will be changed. Inserts each element as edge in the r-partite hypergraph and checks if the graph contains a cycle.

Parameters
opmphmthe OPMPHM
graphthe OpmphmGraph
initthe OpmphmInit
nthe number of elements
Return values
0on success
-1mapping not possible

◆ opmphmMinC()

double opmphmMinC ( void  )

Provides the minimal c value.

Graph functions.

This minimal values come from Fabiano Cupertino Botelho, Near-Optimal Space Perfect Hashing Algorithms, 2008.

Return values
cthe minimal c value

◆ opmphmNew()

Opmphm* opmphmNew ( void  )

Allocates and initializes the OPMPHM.

Basic functions.

The returned OPMPHM instance is Empty.

Return values
Opmphm* success
NULLmemory error