Othello< keyType > Class Template Reference

Describes the data structure l-Othello. It classifies keys of keyType into 2^L classes. More...

#include <othello.h>

Inheritance diagram for Othello< keyType >:

Collaboration diagram for Othello< keyType >:

Public Member Functions
	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.

Public Attributes
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 Othello< keyType >

Describes the data structure l-Othello. It classifies keys of keyType into 2^L classes.

Note

Query a key of keyType always return uint64_t, however, only the lowest L bits are meaningful.
The array are all stored in an array of uint64_t. There are actually m_a+m_b cells in this array, each of length L.

Constructor & Destructor Documentation

template<class keyType>

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  )

inline

Construct l-Othello.

Parameters

[in]	keyType	*_keys, pointer to array of keys.
[in]	uint32_t	keycount, number of keys, array size must match this.
[in]	bool	_autoclear, clear memory used during construction once completed. Forbid future modification on the structure.
[in]	void	* _values, Optional, pointer to array of values. When *_values* is empty, fill othello values such that the query result classifies keys to 2 sets. See more in notes.
[in]	uint32_t	valuesize, must be specifed when *_values* is not NULL. This indicates the length of a valueType;
[in]	_allowed_conflicts,default	value is 10. during construction, Othello will remove at most this number of keys, instead of rehash.

Note

keycount should not exceed 2^29 for memory consideration.
when *_values* is empty, classify keys into two sets X and Y, defined as follow: for each connected compoenents in G, select a node as the root, mark all edges in this connected compoenent as pointing away from the root. for all edges from U to V, query result is 1 (k in Y), for all edges from V to u, query result is 0 (k in X).

template<class keyType>

Othello< keyType >::Othello ( unsigned char *  v )

inline

load the infomation of the Othello from memory.

Note

info is exported using ExportInro()

Member Function Documentation

template<class keyType>

void Othello< keyType >::exportInfo ( unsigned char *  v )

inline

export the information of the Othello, not including the array, to a memory space.

Note

memory space length = 0x20.
Exported infomation contains:
0x00, 32bit, L;
0x04, 32bit, seedB;
0x08, 32bit, seedA;
0x10, 8bit, hlA; 0x14, 8bit, hlB; seedA, seedB, ma , mb (represented as 1<<hl1 and 1<<hl2).

template<class keyType>

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

inline

load the array from file.

Note

only the arrayA and B are loaded. This must be called after using constructor Othello<keyType>::Othello(unsigned char *)

template<class keyType>

valueType Othello< keyType >::query ( const keyType &  k, uint32_t &  ha, uint32_t &  hb  )

inline

compute the hash value of key and return query value.

Parameters

[in]	keyType	&k key
[out]	uint32_t	&ha computed hash function ha
[out]	uint32_t	&hb computed hash function hb

Return values

valueType

template<class keyType >

void Othello< keyType >::removeOneKey

(

uint32_t

kid

)

remove one key with the particular index from the keylist.

Parameters

[in]

uint32_t

kid.

Note

after this option, the number of keys, mykeycount decrease by 1. The key currently stored in keys[kid] will be replaced by the last key in keys[].
valuesize is the number of bytes of each value.

remember to adjust the value[] array if necessary.

template<class keyType >

void Othello< keyType >::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.

Parameters

[in]

double

ideal. ideal = 1.0 means return 1 with higher probability. ideal = 0.0 means return 1 with loest probability.

Note

This function is usually able to tune the probabilty within 0.2 ~ 0.8.

---

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

• othello.h