OthelloIndex< keyType > Class Template Reference

OthelloIndex is a data structure that stores a minimum perfect hash function.
For n keys, the query value of keys range in [0..n-1] Query always returns uint32_t. More...

#include <othelloindex.h>

Inheritance diagram for OthelloIndex< keyType >:

Collaboration diagram for OthelloIndex< keyType >:

Public Member Functions
	OthelloIndex (keyType *_keys, uint32_t keycount)
	Construct OthelloIndex More...
	OthelloIndex (unsigned char *v)
uint32_t	query (const keyType &k)
	return the index of key k, in range [0..n-1] More...
void	loadDataFromBinaryFile (FILE *pF)
	load the array from file. More...
void	writeDataToBinaryFile (FILE *pF)
	write array to binary file.
Public Member Functions inherited from Othello< keyType >
	Othello (uint8_t _L, keyType *_keys, uint32_t keycount, bool _autoclear=true, void *_values=NULL, size_t _valuesize=0, int32_t _allowed_conflicts=-1)
	Construct l-Othello. More...
template<typename VT >
	Othello (uint8_t _L, vector< keyType > &keys, vector< VT > &values, bool _autoclear=true, int32_t allowed_conflicts=-1)
	Construct othello with vectors.
void	finishBuild ()
	release memory space used during construction and forbid future modification of arrayA and arrayB.
void	exportInfo (unsigned char *v)
	export the information of the Othello, not including the array, to a memory space. More...
	Othello (unsigned char *v)
	load the infomation of the Othello from memory. More...
void	addkeys (int newkeys, void *values, uint32_t valuesize)
	after putting some keys into keys, call this function to add keys into Othello. values shall be stored in the array *values
uint64_t	queryInt (const keyType &k)
	returns a 64-bit integer query value for a key.
void	printValueTSize ()
vector< uint32_t >	getCnt ()
	returns vector, length = 2L. position x: the number of 1s on the x-th lowest bit, for array A, if x<L; otherwise, for arrayB.
vector< double >	getRatio ()
	returns vector, length = L. position x: the probability that query return 1 on the x-th lowest bit.
void	randomflip ()
	adjust the array so that for random alien query, returns 0 or 1 with equal probability on each bit.
void	setAlienPreference (double ideal=1.0)
	adjust the array so that for random alien query, return 1 with probability that is close to the ideal value. More...
valueType	query (const keyType &k, uint32_t &ha, uint32_t &hb)
	compute the hash value of key and return query value. More...
void	get_hash_2 (const keyType &v, uint32_t &ret1)
void	get_hash (const keyType &v, uint32_t &ret1, uint32_t &ret2)
void	loadDataFromBinaryFile (FILE *pF)
	load the array from file. More...
void	writeDataToBinaryFile (FILE *pF)
	write array to binary file.
void	removeOneKey (uint32_t kid)
	remove one key with the particular index from the keylist. More...
void	updatevalue (uint32_t kid, void *values, uint32_t valuesize)
	update the value for one particular key.

Additional Inherited Members
Public Attributes inherited from Othello< keyType >
vector< valueType >	mem
	actual memory space for arrayA and arrayB.
uint32_t	L
	the length of return value.
uint32_t	ma
	length of arrayA.
uint32_t	mb
	length of arrayB
Hasher32< keyType >	Ha
Hasher32< keyType >	Hb
bool	build = false
	true if Othello is successfully built.
uint32_t	trycount = 0
	number of rehash before a valid hash pair is found.
DisjointSet	disj
	Disjoint Set data structure that helps to test the acyclicity.
vector< uint32_t >	fillcount
	Enabled only when the values of the query is not pre-defined. This supports othelloIndex query. fillcount[x]==1 if and only if there is an edge pointed to x,.
uint32_t	mykeycount
uint32_t	allowed_conflicts
	The number of keys that can be skipped during construction.
vector< keyType >	removedKeys
	The list of removed keys.

Detailed Description

template<class keyType>
class OthelloIndex< keyType >

OthelloIndex is a data structure that stores a minimum perfect hash function.
For n keys, the query value of keys range in [0..n-1] Query always returns uint32_t.

Note

n should not exceed 2^29 for memory consideration. For even larger n, use the grouped version MulOthIndex.
For better performance, the we use POPCNT instructions, which is supported by most mordern CPUs.
The index of a key k is either Sum {cntfill[0..Ha(k)-1]} or Sum {cntfill[0..Hb(k)-1]}. This is decided by query result on oth.

Constructor & Destructor Documentation

template<class keyType>

OthelloIndex< keyType >::OthelloIndex ( keyType *  _keys, uint32_t  keycount  )

inline

Construct OthelloIndex

Parameters

[in]	keyType	* keys, pointer to array of keys.
[in]	uint32_t	keycount, number of keys.

Note

For n keys, the query value of keys range in [0..n-1]

Member Function Documentation

template<class keyType>

void OthelloIndex< keyType >::loadDataFromBinaryFile ( FILE *  pF )

inline

load the array from file.

Note

the arrayA and B are loaded, in addition, read the array fillcount and array offset. This must be called after using constructor Othello<keyType>::Othello(unsigned char *)

template<class keyType>

uint32_t OthelloIndex< keyType >::query ( const keyType &  k )

inline

return the index of key k, in range [0..n-1]

Parameters

[in]

keyType

k

Return values

uint32_t

index

---

The documentation for this class was generated from the following file:

• othelloindex.h