A lock-free hash table that can be used in multi-thread or multi-process programs. More...

#include <atomic_hash_table.hh>

Public Types
typedef Key	key_type

typedef size_t	size_type

typedef EqualKey< key_type >	key_equal

typedef HashKey< typename COmitCV< key_type >::result_type >	hasher

Public Member Functions
	CAtomicHashTable ()
	Prepare an uninitialized object. More...

	CAtomicHashTable (char *buf, size_t sz)
	Attach to an existing hash table hosted in a memory buffer. More...

	CAtomicHashTable (char *buf, size_t sz, size_t capacity, int row, size_t valueLen, bool create=false)
	Attach to or create a hash table in a memory buffer. More...

bool	init (char *buf, size_t sz)
	Attach to an existing hash table hosted in a memory buffer. More...

bool	init (char *buf, size_t sz, size_t capacity, int row, size_t valueLen, bool create=false)
	Attach to or create a hash table in a memory buffer. More...

void	uninit ()
	Reset current object. More...

bool	valid () const
	Test if current object is initialized. More...

Capacity
int	rowSize () const
	Get number of rows in hash table. More...

size_t	capacityOfRow (int row) const
	Get capacity of a row in hash table. More...

size_t	capacity () const
	Get capacity of the hash table. More...

size_t	sizeOfRow (int row) const
	Get number of key-value pairs in a row. More...

size_t	size () const
	Get number of key-value pair in the hash table. More...

bool	empty () const
	Test if the hash table is empty. More...

Brief Info
time_t	createTime () const
	Get creation time of the hash table. More...

time_t	updateTime () const
	Get latest updating time of the hash table. More...

time_t	upgradeTime () const
	Get latest upgrading time of the hash table. More...

std::string	toString () const
	Get a description of the hash table. More...

Data Access
bool	insert (const key_type &key, const char *value, size_t len)
	Insert a key-value pair into the hash table. More...

bool	insert (const key_type &key, const std::string &value)
	Insert a key-value pair into the hash table. More...

bool	get (const key_type &key, char *value, size_t &len) const
	Obtain value of a key. More...

bool	get (const key_type &key, std::string &value) const
	Obtain value of a key. More...

bool	has (const key_type &key) const
	Test if a key exists in the hash table. More...

bool	update (const key_type &key, const char *value, size_t len)
	Update value of a key. More...

bool	update (const key_type &key, const std::string &value)
	Update value of a key. More...

size_t	remove (const key_type &key)
	Remove a key and its value. More...

void	clear ()
	Clear all data in the hash table. More...

Static Public Member Functions
static size_t	CalcBufSize (size_t capacity, int row, size_t valueLen)
	Compute memory size needed for a hash table. More...

Static Public Attributes
static const size_t	kValueLenMax = (1UL << 24)
	The maximum size of Key plus Value, i.e. 16MB.

Detailed Description

template<typename Key, template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>
class CAtomicHashTable< Key, HashKey, EqualKey >

A lock-free hash table that can be used in multi-thread or multi-process programs.

A common usage of CAtomicHashTable is for multiple threads or processes to operate on the same hash table efficiently.
It must reside in continuous memory pre-allocated by the user. Hence, key and value types must be trivially copyable, i.e. can be copied using std::memcpy.

Multi-Thread/Process Safety Guide

	Same Key	Different Keys
Read	Safe	Safe
Write	Unsafe	Safe

Multiple Rows Hash Table: CAtomicHashTable resolves key hash collisions by adding multiple rows. A row is a one-dimension hash table.
If a key collides with another key in a row, CAtomicHashTable will search in the next row, and so on until it finds a room.
The more number of rows, the less chance of failure when hash table capacity is about to reach. The less number of rows, the better performance it can get.

Template Parameters

Key	Type of keys, must be POD or C struct compatible types
HashKey	Hash function of Key, should implement: size_t operator ()(const Key & key) const; // compute hash value of key
EqualKey	Equal predictor of Key, should implement: bool operator ()(const Key & key1, const Key & key2) const; // predict if key1 == key2

Value: Value type is std::string or char array.

Note: Size limitation of Key and Value is defined by kValueLenMax.

Constructor & Destructor Documentation

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

CAtomicHashTable< Key, HashKey, EqualKey >::CAtomicHashTable ( )

inline

Prepare an uninitialized object.

You cannot use the object until it is initialized by init.

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

CAtomicHashTable< Key, HashKey, EqualKey >::CAtomicHashTable	(	char *	buf,
		size_t	sz
	)

inline

Attach to an existing hash table hosted in a memory buffer.

See also: init(char * buf, size_t sz)

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

CAtomicHashTable< Key, HashKey, EqualKey >::CAtomicHashTable	(	char *	buf,
		size_t	sz,
		size_t	capacity,
		int	row,
		size_t	valueLen,
		bool	create = `false`
	)

inline

Attach to or create a hash table in a memory buffer.

See also: init(char * buf, size_t sz, size_t capacity, int row, size_t valueLen, bool create)

Member Function Documentation

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

static size_t CAtomicHashTable< Key, HashKey, EqualKey >::CalcBufSize	(	size_t	capacity,
		int	row,
		size_t	valueLen
	)

inlinestatic

Compute memory size needed for a hash table.

This function pre-computes the size of pre-allocated memory buffer needed for a hash table.

Parameters

capacity	The maximum number of key-value pairs the hash table wishes to hold
row	Number of rows the hash table wants to have
valueLen	Estimated byte size of key plus value, e.g. average size. This needs NOT to be the maximum.

Returns

Number of bytes needed for a memory buffer to hold the hash table
Or 0 if such requirement is unable to meet

Note: CAtomicHashTable stores data (key and value) in blocks of size valueLen. If the block size is too large, there will be a lot of wasted spaces inside each block. Otherwise, if the block size is too small, a data may spread to many blocks, which will impact access performance.

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

size_t CAtomicHashTable< Key, HashKey, EqualKey >::capacity ( ) const

inline

Get capacity of the hash table.

Returns

Number of key-value pairs that this hash table can hold at most
Or 0 if current object is NOT initialized

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

size_t CAtomicHashTable< Key, HashKey, EqualKey >::capacityOfRow ( int row ) const

inline

Get capacity of a row in hash table.

Parameters

row	Index of row, ranging from 0 to rowSize() - 1

Returns: Number of key-value pairs that this row can hold at most

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

void CAtomicHashTable< Key, HashKey, EqualKey >::clear ( )

inline

Clear all data in the hash table.

Warning: This function is NOT thread-safe. Do NOT call it while other threads or processes are accessing the hash table.

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

time_t CAtomicHashTable< Key, HashKey, EqualKey >::createTime ( ) const

inline

Get creation time of the hash table.

Returns

Creation time of this hash table
Or 0 if current object is NOT initialized

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::empty ( ) const

inline

Test if the hash table is empty.

Returns: true if this hash table is empty; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::get	(	const key_type &	key,
		char *	value,
		size_t &	len
	)		const

inline

Obtain value of a key.

Parameters

[in]	key	Key to search for
[in]	value	Pointer to memory buffer that receives the value data
[in,out]	len	Passed in as bytes size of `value` buffer; and passed out as actual bytes size of the data copied

Returns

true, if succeeded
false, otherwise, e.g. key doesn't exists, value buffer is insufficient

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::get	(	const key_type &	key,
		std::string &	value
	)		const

inline

Obtain value of a key.

Parameters

[in]	key	Key to search for
[out]	value	String bytes to receive the value data

Returns: true if succeeded; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::has ( const key_type & key ) const

inline

Test if a key exists in the hash table.

Parameters

key	Key to search for

Returns: true if key exists in this hash table; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::init	(	char *	buf,
		size_t	sz
	)

inline

Attach to an existing hash table hosted in a memory buffer.

There must be an initialized hash table in the memory buffer. This function tries to attach to the existing hash table to a local object. If failed, it won't modify the content of the memory buffer.

Parameters

buf	Pointer to the memory buffer
sz	Byte size of the memory buffer

Returns: true if succeeded; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::init	(	char *	buf,
		size_t	sz,
		size_t	capacity,
		int	row,
		size_t	valueLen,
		bool	create = `false`
	)

inline

Attach to or create a hash table in a memory buffer.

if create = false, this function tries to attach to an existing hash table in the memory buffer to a local object, just like init(char * buf, size_t sz), except that it will also validate capacity, row and valueLen parameters if they are not 0;
if create = true, this function will create a new hash table in the memory buffer, and erase any data existing. In this case, sz should be the return value of CalcBufSize, otherwise this function may fail.

Parameters

buf	Pointer to the memory buffer
sz	Byte size of the memory buffer
capacity	The maximum number of key-value pairs the hash table wishes to hold
row	Number of rows the hash table wants to have
valueLen	Estimated byte size of key plus value, e.g. average size. This needs NOT to be the maximum.
create	`false` if attached to an existing hash table; `true` if create a new one

Returns: true if succeeded; otherwise false

See also: CalcBufSize

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::insert	(	const key_type &	key,
		const char *	value,
		size_t	len
	)

inline

Insert a key-value pair into the hash table.

If key already exists, this function may result in multiple instances of key in the hash table.

Parameters

key	Key to insert into the hash table
value	Pointer to bytes of value to insert into the hash table
len	Byte size of value

Returns: true if succeeded; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::insert	(	const key_type &	key,
		const std::string &	value
	)

inline

Insert a key-value pair into the hash table.

If key already exists, this function may result in multiple instances of key in the hash table.

Parameters

key	Key to insert into the hash table
value	Bytes of value to insert into the hash table

Returns: true if succeeded; otherwise false

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

size_t CAtomicHashTable< Key, HashKey, EqualKey >::remove ( const key_type & key )

inline

Remove a key and its value.

If there are multiple instances of key, only one will be removed.

Parameters

key	Key to remove from this hash table

Returns: Number of data blocks released; Or 0 if key doesn't exist

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

int CAtomicHashTable< Key, HashKey, EqualKey >::rowSize ( ) const

inline

Get number of rows in hash table.

Returns

Number of rows
Or 0 if current object is NOT initialized

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

size_t CAtomicHashTable< Key, HashKey, EqualKey >::size ( ) const

inline

Get number of key-value pair in the hash table.

Returns: Number of key-value pairs in this hash table

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

size_t CAtomicHashTable< Key, HashKey, EqualKey >::sizeOfRow ( int row ) const

inline

Get number of key-value pairs in a row.

Parameters

row	Index of row, ranging from 0 to rowSize() - 1

Returns: Number of key-value pairs hosted in this row

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

std::string CAtomicHashTable< Key, HashKey, EqualKey >::toString ( ) const

inline

Get a description of the hash table.

Returns: A human readable description of this hash table

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

void CAtomicHashTable< Key, HashKey, EqualKey >::uninit ( )

inline

Reset current object.

This function won't affect data in the real hash table memory buffer. After reset, the local object could be reused by init.

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::update	(	const key_type &	key,
		const char *	value,
		size_t	len
	)

inline

Update value of a key.

If key doesn't exist, then insert a new key-value pair.

Parameters

key	Key to search for
value	Pointer to bytes of value to update for
len	Byte size of value

Returns: true if succeeded; otherwise false

See also: insert

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::update	(	const key_type &	key,
		const std::string &	value
	)

inline

Update value of a key.

If key doesn't exist, then insert a new key-value pair.

Parameters

key	Key to search for
value	Bytes of value to update for

Returns: true if succeeded; otherwise false

See also: insert

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

time_t CAtomicHashTable< Key, HashKey, EqualKey >::updateTime ( ) const

inline

Get latest updating time of the hash table.

Returns

Latest updating time of this hash table
Or 0 if current object is NOT initialized

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

time_t CAtomicHashTable< Key, HashKey, EqualKey >::upgradeTime ( ) const

inline

Get latest upgrading time of the hash table.

Returns

Latest upgrading time of this hash table
Or 0 if current object is NOT initialized

template<typename Key , template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>

bool CAtomicHashTable< Key, HashKey, EqualKey >::valid ( ) const

inline

Test if current object is initialized.

Returns: true if current object is initialized; otherwise false

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

atomic_hash_table.hh

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

template<typename Key, template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to> class CAtomicHashTable< Key, HashKey, EqualKey >

Constructor & Destructor Documentation

Member Function Documentation

template<typename Key, template< typename >class HashKey = CHashFn, template< typename >class EqualKey = std::equal_to>
class CAtomicHashTable< Key, HashKey, EqualKey >