Trie(LOUDS) class. More...

#include <trie.hpp>

Data Structures
struct	Result

Public Types
typedef uint64_t	id_t
	ID of leaf-node. More...

typedef struct hsds::Trie::Result	Result

Public Member Functions
	Trie ()
	Constructor. More...

virtual	~Trie ()
	Destructor. More...

void	build (std::vector< std::string > &keyList, bool useTailTrie=false)
	Build louds trie. More...

id_t	exactMatchSearch (const char *str, size_t len) const
	Searches key exact match with query string. More...

void	commonPrefixSearch (const char *str, size_t len, std::vector< id_t > &retIDs, uint64_t limit=DEFAULT_LIMIT_VALUE) const
	Searches keys from the possible prefixes of a query string. More...

void	commonPrefixSearch (const char *str, size_t len, std::vector< Result > &results, uint64_t limit=DEFAULT_LIMIT_VALUE) const
	Searches keys from the possible prefixes of a query string. More...

void	predictiveSearch (const char *str, size_t len, std::vector< id_t > &retIDs, uint64_t limit=DEFAULT_LIMIT_VALUE) const
	Searches keys starting with a query string. More...

id_t	traverse (const char *str, size_t len, uint64_t &nodePos, uint64_t &zeros, size_t &keyPos) const
	Traverse the node of the trie. More...

void	decodeKey (id_t id, std::string &key) const
	Get key string corresponding to the ID. More...

void	swap (Trie &x)
	Exchanges the content of the instance. More...

void	clear ()
	Clear trie. More...

size_t	size () const
	Return the number of keys in the dictionary. More...

void	save (std::ostream &os) const throw (hsds::Exception)
	Save the current status to a stream. More...

void	load (std::istream &is) throw (hsds::Exception)
	Load the current status from a stream. More...

uint64_t	map (void *ptr, uint64_t mapSize) throw (hsds::Exception)
	Mapping pointer to the Trie. More...

Static Public Attributes
static const id_t	NOT_FOUND = ~(0ULL)
	data not found More...

static const id_t	CAN_NOT_TRAVERSE = ~(0ULL) - 1
	Can't traverse the next node. More...

Detailed Description

Trie(LOUDS) class.

Definition at line 22 of file trie.hpp.

Member Typedef Documentation

typedef uint64_t hsds::Trie::id_t

ID of leaf-node.

Definition at line 24 of file trie.hpp.

typedef struct hsds::Trie::Result hsds::Trie::Result

Constructor & Destructor Documentation

hsds::Trie::Trie ( )

Constructor.

virtual hsds::Trie::~Trie ( )

virtual

Destructor.

Member Function Documentation

void hsds::Trie::build	(	std::vector< std::string > &	keyList,
		bool	useTailTrie = `false`
	)

Build louds trie.

Parameters

[in]	keyList	source data of trie
[in]	useTailTrie	use tail compression

void hsds::Trie::clear ( )

Clear trie.

void hsds::Trie::commonPrefixSearch	(	const char *	str,
		size_t	len,
		std::vector< id_t > &	retIDs,
		uint64_t	limit = `DEFAULT_LIMIT_VALUE`
	)		const

Searches keys from the possible prefixes of a query string.

Parameters

[in]	str	query string
[in]	len	length of str
[out]	retIDs	IDs of keys
[in]	limit	the upper limit of the ID number to retrieve

void hsds::Trie::commonPrefixSearch	(	const char *	str,
		size_t	len,
		std::vector< Result > &	results,
		uint64_t	limit = `DEFAULT_LIMIT_VALUE`
	)		const

Searches keys from the possible prefixes of a query string.

Parameters

[in]	str	query string
[in]	len	length of str
[out]	results	search results
[in]	limit	the upper limit of the ID number to retrieve

void hsds::Trie::decodeKey	(	id_t	id,
		std::string &	key
	)		const

Get key string corresponding to the ID.

Parameters

[in]	id	ID of key.
[out]	key

id_t hsds::Trie::exactMatchSearch	(	const char *	str,
		size_t	len
	)		const

Searches key exact match with query string.

Parameters

[in]	str	query string
[in]	len	length of str

Return values

Trie::NOT_FOUND Key does not found in the trie

Returns: ID of the key.

void hsds::Trie::load ( std::istream & is ) throw (hsds::Exception)

Load the current status from a stream.

Parameters

[in] is The input stream where the status is saved

Exceptions

hsds::Exception When failed to load.

uint64_t hsds::Trie::map	(	void *	ptr,
		uint64_t	mapSize
	)		throw (hsds::Exception)

Mapping pointer to the Trie.

Parameters

[in]	ptr	The pointer of the mmaped file
[in]	mapSize	The size of mmaped file

Returns: Actually mapped size(byte size of offset from ptr).

Exceptions

hsds::Exception When failed to load.

void hsds::Trie::predictiveSearch	(	const char *	str,
		size_t	len,
		std::vector< id_t > &	retIDs,
		uint64_t	limit = `DEFAULT_LIMIT_VALUE`
	)		const

Searches keys starting with a query string.

Parameters

[in]	str	query string
[in]	len	length of str
[out]	retIDs	IDs of keys
[in]	limit	the upper limit of the ID number to retrieve

void hsds::Trie::save ( std::ostream & os ) const throw (hsds::Exception)

Save the current status to a stream.

Parameters

[out] os The output stream where the data is saved

Exceptions

hsds::Exception When failed to save.

size_t hsds::Trie::size ( ) const

Return the number of keys in the dictionary.

Returns: the number of keys in the dictionary

void hsds::Trie::swap ( Trie & x )

Exchanges the content of the instance.

Parameters

[in,out] x Another Trie instance

id_t hsds::Trie::traverse	(	const char *	str,
		size_t	len,
		uint64_t &	nodePos,
		uint64_t &	zeros,
		size_t &	keyPos
	)		const

Traverse the node of the trie.

Parameters

[in]	str	query string
[in]	len	length of str
[in,out]	nodePos	current position in trie
[in,out]	zeros
[in,out]	keyPos	current position in key

Return values

Trie::CAN_NOT_TRAVERSE
Trie::NOT_FOUND

Returns: ID of the leaf-node

Field Documentation

const id_t hsds::Trie::CAN_NOT_TRAVERSE = ~(0ULL) - 1

static

Can't traverse the next node.

Definition at line 26 of file trie.hpp.

const id_t hsds::Trie::NOT_FOUND = ~(0ULL)

static

data not found

Definition at line 25 of file trie.hpp.

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

include/hsds/trie.hpp

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation