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

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

Copyright: BSD License (see doc/COPYING or https://www.libelektra.org)

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

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.

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

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

dest	the OPMPHM destination
source	the OPMPHM source

Return values

0	on success
-1	on memory error

◆ opmphmDel()

void opmphmDel ( Opmphm * opmphm )

Deletes the OPMPHM.

Clears and frees all memory in Opmphm.

Parameters

opmphm the OPMPHM

◆ opmphmGraphClear()

void opmphmGraphClear	(	const Opmphm *	opmphm,
		OpmphmGraph *	graph
	)

Clears the OpmphmGraph.

Sets all vertices to 0.

Parameters

opmphm	the OPMPHM
graph	the OpmphmGraph

◆ opmphmGraphDel()

void opmphmGraphDel ( OpmphmGraph * graph )

Deletes the OpmphmGraph.

Parameters

graph the OpmphmGraph

◆ opmphmGraphNew()

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

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

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

Return values

OpmphmGraph	* success
NULL	memory error

◆ opmphmIsBuild()

int opmphmIsBuild ( const Opmphm * opmphm )

OPMPHM is build.

Parameters

opmphm the OPMPHM

Return values

0	on false
-1	on true or NULL

◆ opmphmLookup()

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

Lookup functions.

Parameters

opmphm	the OPMPHM
n	the number of elements
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
	)

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

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 ( uint8_t r )

Functions providing r and c

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

Parameters

r	the rUniPar

Return values

c	the minimal c value

◆ opmphmNew()

Opmphm* opmphmNew ( void )

Basic functions.

Return values

Opmphm	* success
NULL	memory 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

n	the number of elements to hash

Return values

c	the 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

n	the number of elements to hash

Return values

r	the optimal rUniPar

Classes

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ KDB_OPMPHM_MAX_N

Function Documentation

◆ opmphmAssignment()

◆ opmphmClear()

◆ opmphmCopy()

◆ opmphmDel()

◆ opmphmGraphClear()

◆ opmphmGraphDel()

◆ opmphmGraphNew()

◆ opmphmIsBuild()

◆ opmphmLookup()

◆ opmphmMapping()

◆ opmphmMinC()

◆ opmphmNew()

◆ opmphmOptC()

◆ opmphmOptR()