src/libs/elektra/opmphm.c
/** The first phase of the order preserving minimal perfect hash map build. */
The first phase of the order preserving minimal perfect hash map build.
The first phase of the order preserving minimal perfect hash map build .
int opmphmMapping (OPMPHM * opmphm, Vertex * vertices, Edge * edges, OPMPHMinit * init, size_t n)
{
	for (int i = 0; i < 3; ++i)
	{
		opmphm->opmphmHashFunctionSeeds[i] = opmphmRandom (&(init->seed));
	}
	size_t r = opmphmRatio * n;
	ELEKTRA_LOG ("OPMPHM: Mapping: r=%lu seed[0]=%u seed[1]=%u seed[2]=%u\n", r, opmphm->opmphmHashFunctionSeeds[0],
		     opmphm->opmphmHashFunctionSeeds[1], opmphm->opmphmHashFunctionSeeds[2]);
	for (size_t i = 0; i < r * 2; ++i)
	{
		vertices[i].degree = 0;
		vertices[i].firstEdge = -1;
	}
	ELEKTRA_LOG_DEBUG ("OPMPHM: Mapping: Keys:\n");
	for (size_t i = 0; i < n; ++i)
	{
		const char * name = init->getString (init->data[i]);
		ELEKTRA_LOG_DEBUG ("%s\n", name);
#ifndef OPMPHM_TEST
		edges[i].h[0] = opmphmHashfunction ((const uint32_t *)name, strlen (name), opmphm->opmphmHashFunctionSeeds[0]) % n;
		edges[i].h[1] = opmphmHashfunction ((const uint32_t *)name, strlen (name), opmphm->opmphmHashFunctionSeeds[1]) % r;
		edges[i].h[2] = (opmphmHashfunction ((const uint32_t *)name, strlen (name), opmphm->opmphmHashFunctionSeeds[2]) % r) + r;
#endif
		edges[i].nextEdge[0] = vertices[edges[i].h[1]].firstEdge;
		vertices[edges[i].h[1]].firstEdge = i;
		++vertices[edges[i].h[1]].degree;
		edges[i].nextEdge[1] = vertices[edges[i].h[2]].firstEdge;
		vertices[edges[i].h[2]].firstEdge = i;
		++vertices[edges[i].h[2]].degree;
	}
	for (size_t i = 0; i < r; ++i)
	{
		for (int e0 = vertices[i].firstEdge; e0 != -1; e0 = edges[e0].nextEdge[0])
		{
			for (int e1 = edges[e0].nextEdge[0]; e1 != -1; e1 = edges[e1].nextEdge[0])
			{
				if (edges[e0].h[0] == edges[e1].h[0] && edges[e0].h[2] == edges[e1].h[2])
				{
					return 1;
				}
			}
		}
	}
	return 0;
}
int opmphmMapping ( OPMPHM * opmphm , Vertex * vertices , Edge * edges , OPMPHMinit * init , size_t n ) { for ( int i = 0 ; i < 3 ; ++ i ) { opmphm -> opmphmHashFunctionSeeds [ i ] = opmphmRandom ( & ( init -> seed ) ) ; } size_t r = opmphmRatio * n ; ELEKTRA_LOG ( " \n " , r , opmphm -> opmphmHashFunctionSeeds [ 0 ] , opmphm -> opmphmHashFunctionSeeds [ 1 ] , opmphm -> opmphmHashFunctionSeeds [ 2 ] ) ; for ( size_t i = 0 ; i < r * 2 ; ++ i ) { vertices [ i ] . degree = 0 ; vertices [ i ] . firstEdge = -1 ; } ELEKTRA_LOG_DEBUG ( " \n " ) ; for ( size_t i = 0 ; i < n ; ++ i ) { const char * name = init -> getString ( init -> data [ i ] ) ; ELEKTRA_LOG_DEBUG ( " \n " , name ) ; #ifndef OPMPHM_TEST edges [ i ] . h [ 0 ] = opmphmHashfunction ( ( const uint32_t * ) name , strlen ( name ) , opmphm -> opmphmHashFunctionSeeds [ 0 ] ) % n ; edges [ i ] . h [ 1 ] = opmphmHashfunction ( ( const uint32_t * ) name , strlen ( name ) , opmphm -> opmphmHashFunctionSeeds [ 1 ] ) % r ; edges [ i ] . h [ 2 ] = ( opmphmHashfunction ( ( const uint32_t * ) name , strlen ( name ) , opmphm -> opmphmHashFunctionSeeds [ 2 ] ) % r ) + r ; #endif edges [ i ] . nextEdge [ 0 ] = vertices [ edges [ i ] . h [ 1 ] ] . firstEdge ; vertices [ edges [ i ] . h [ 1 ] ] . firstEdge = i ; ++ vertices [ edges [ i ] . h [ 1 ] ] . degree ; edges [ i ] . nextEdge [ 1 ] = vertices [ edges [ i ] . h [ 2 ] ] . firstEdge ; vertices [ edges [ i ] . h [ 2 ] ] . firstEdge = i ; ++ vertices [ edges [ i ] . h [ 2 ] ] . degree ; } for ( size_t i = 0 ; i < r ; ++ i ) { for ( int e0 = vertices [ i ] . firstEdge ; e0 != -1 ; e0 = edges [ e0 ] . nextEdge [ 0 ] ) { for ( int e1 = edges [ e0 ] . nextEdge [ 0 ] ; e1 != -1 ; e1 = edges [ e1 ] . nextEdge [ 0 ] ) { if ( edges [ e0 ] . h [ 0 ] == edges [ e1 ] . h [ 0 ] && edges [ e0 ] . h [ 2 ] == edges [ e1 ] . h [ 2 ] ) { return 1 ; } } } } return 0 ; }
The first phase of the order preserving minimal perfect hash map build.
The first phase of the order preserving minimal perfect hash map build .
// set the seeds, for the hash function // init used values // set the resulting hash values for each key // add each key to both lists // verify that all triples are disjunct, if not this function will be called again