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...
Opmphm *	opmphmNew (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.

Copyright

BSD License (see LICENSE.md or https://www.libelektra.org)

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

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.

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

Parameters

opmphm

the OPMPHM

opmphmDel()

void opmphmDel

(

Opmphm *

opmphm

)

Deletes the OPMPHM.

Clears and frees all memory in Opmphm.

Parameters

opmphm

the OPMPHM

opmphmGraphDel()

void opmphmGraphDel

(

OpmphmGraph *

graph

)

Deletes the OpmphmGraph.

Parameters

graph

the 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

opmphm	the OPMPHM
n	the number of elements
c	space influencing parameter

Return values

OpmphmGraph	* success
NULL	memory error

opmphmIsEmpty()

int opmphmIsEmpty

(

Opmphm *

opmphm

)

Determines if the OPMPHM is Empty.

Empty means opmphm->size is 0.

Parameters

opmphm

the OPMPHM

Return values

true	empty
false	non empty

opmphmLookup()

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

Looks up a element in the OPMPHM.

Lookup functions.

Parameters

opmphm	the OPMPHM
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
	)

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

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

(

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

c	the minimal c value

opmphmNew()

Opmphm* opmphmNew

(

void

)

Allocates and initializes the OPMPHM.

Basic functions.

The returned OPMPHM instance is Empty.

Return values

Opmphm	* success
NULL	memory error