Classes¶

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

Macros¶

#define OPMPHMR_PARTITE 3
The Order Preserving Minimal Perfect Hash Map (OPMPHM) maps each element to an edge in an r-partite hypergraph. #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 *(* opmphmGetString) (void *)
Only needed for Initialisation.

Functions¶

double opmphmMinC (void)
Graph functions. OpmphmGraph * opmphmGraphNew (Opmphm *opmphm, size_t n, double c)
Allocates and initializes the OpmphmGraph. void opmphmGraphDel (OpmphmGraph *graph)
Deletes the OpmphmGraph. int opmphmMapping (Opmphm *opmphm, OpmphmGraph *graph, OpmphmInit *init, size_t n)
Build functions. int opmphmAssignment (Opmphm *opmphm, OpmphmGraph *graph, size_t n, int defaultOrder)
Assigns the vertices of the r-partite hypergraph. size_t opmphmLookup (Opmphm *opmphm, const void *name)
Lookup functions. Opmphm * opmphmNew (void)
Basic functions. void opmphmDel (Opmphm *opmphm)
Deletes the OPMPHM. void opmphmClear (Opmphm *opmphm)
Clears the OPMPHM. int opmphmIsEmpty (Opmphm *opmphm)
Determines if the OPMPHM is Empty. 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.

#define OPMPHMR_PARTITE 3¶

The Order Preserving Minimal Perfect Hash Map (OPMPHM) maps each element to an edge in an r-partite hypergraph. The r-partite hypergraph consist of OPMPHMR_PARTITE components, each component has Opmphm->componentSize vertices. An edge connects OPMPHMR_PARTITE vertices, each one in separate components of the r-partite hypergraph. The number of vertices in one component of the r-partite hypergraph (Opmphm->componentSize) is calculated during opmphmGraphNew () the following way:

Opmphm->componentSize = (c * n / OPMPHMR_PARTITE) + 1;

Note that c must have a minimal value in order to generate acyclic r-partite hypergraphs. The minimal value of c depends on OPMPHMR_PARTITE and is provided by the function opmphmMinC ().

The finals size of the opmphm (Opmphm->graph) is: Opmphm->componentSize * OPMPHMR_PARTITE

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:

Return values:

void opmphmClear (Opmphm * opmphm)¶

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

Parameters:

void opmphmDel (Opmphm * opmphm)¶

Deletes the OPMPHM. Clears and frees all memory in Opmphm.

Parameters:

void opmphmGraphDel (OpmphmGraph * graph)¶

Deletes the OpmphmGraph.

Parameters:

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:

Return values:

int opmphmIsEmpty (Opmphm * opmphm)¶

Determines if the OPMPHM is Empty. Empty means opmphm->size is 0.

Parameters:

Return values:

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

Lookup functions. Lookup functions.

Parameters:

Return values:

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-partite hypergraph and checks if the graph contains a cycle.

Parameters:

Return values:

double opmphmMinC (void)¶

Graph functions. Graph functions.

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

Return values:

Opmphm* opmphmNew (void)¶

Basic functions. Basic functions.

The returned OPMPHM instance is Empty.

Return values: