#include <hash.hpp>

Inheritance diagram for mfem::HashTable< T >:

Collaboration diagram for mfem::HashTable< T >:

Classes
class	const_iterator

class	iterator

Public Member Functions
	HashTable (int block_size=16 1024, int init_hash_size=32 1024)
	Main constructor of the HashTable class. More...

	HashTable (const HashTable &other)
	Deep copy. More...

HashTable &	operator= (const HashTable &)=delete
	Copy assignment not supported. More...

	~HashTable ()

T *	Get (int p1, int p2)
	Item accessor with key (or parents) the pair 'p1', 'p2'. Default construct an item of type T if no value correspond to the requested key. More...

T *	Get (int p1, int p2, int p3, int p4=-1)
	Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Default construct an item of type T if no value corresponds to the requested key. More...

int	GetId (int p1, int p2)
	Get id of item whose parents are p1, p2... Create it if it doesn't exist. More...

int	GetId (int p1, int p2, int p3, int p4=-1)
	Get the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value correspond to the requested key. More...

T *	Find (int p1, int p2)
	Find item whose parents are p1, p2... Return NULL if it doesn't exist. More...

T *	Find (int p1, int p2, int p3, int p4=-1)
	Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value correspond to the requested key. More...

const T *	Find (int p1, int p2) const
	Item const accessor with key (or parents) the pair 'p1', 'p2'. Return nullptr if no value correspond to the requested key. More...

const T *	Find (int p1, int p2, int p3, int p4=-1) const
	Item const accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value correspond to the requested key. More...

int	FindId (int p1, int p2) const
	Find id of item whose parents are p1, p2... Return -1 if it doesn't exist. More...

int	FindId (int p1, int p2, int p3, int p4=-1) const
	Find the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value correspond to the requested key. More...

int	Size () const
	Return the number of elements currently stored in the HashTable. More...

int	NumIds () const
	Return the total number of ids (used and unused) in the HashTable. More...

int	NumFreeIds () const
	Return the number of free/unused ids in the HashTable. More...

bool	IdExists (int id) const
	Return true if item 'id' exists in (is used by) the container. More...

void	Delete (int id)
	Remove an item from the hash table. More...

void	DeleteAll ()
	Remove all items. More...

void	Alloc (int id, int p1, int p2)
	Allocate an item at 'id'. Enlarge the underlying BlockArray if necessary. More...

void	UpdateUnused ()
	Reinitialize the internal list of unallocated items. More...

void	Reparent (int id, int new_p1, int new_p2)
	Change the key associated with an item. More...

void	Reparent (int id, int new_p1, int new_p2, int new_p3, int new_p4=-1)
	Change the key associated with an item. More...

long	MemoryUsage () const
	Return total size of allocated memory (tables plus items), in bytes. More...

void	PrintMemoryDetail () const
	Write details of the memory usage to the mfem output stream. More...

void	PrintStats () const
	Print a histogram of bin sizes for debugging purposes. More...

iterator	begin ()

iterator	end ()

const_iterator	cbegin () const

const_iterator	cend () const

Public Member Functions inherited from mfem::BlockArray< T >
	BlockArray (int block_size=16 *1024)

	BlockArray (const BlockArray< T > &other)

BlockArray &	operator= (const BlockArray &)=delete

	~BlockArray ()

int	Append ()
	Allocate and construct a new item in the array, return its index. More...

int	Append (const T &item)
	Allocate and copy-construct a new item in the array, return its index. More...

T &	At (int index)
	Access item of the array. More...

const T &	At (int index) const

T &	operator[] (int index)
	Access item of the array. More...

const T &	operator[] (int index) const

int	Size () const
	Return the number of items actually stored. More...

int	Capacity () const
	Return the current capacity of the BlockArray. More...

void	DeleteAll ()
	Destroy all items, set size to zero. More...

void	Swap (BlockArray< T > &other)

long	MemoryUsage () const

iterator	begin ()

iterator	end ()

const_iterator	cbegin () const

const_iterator	cend () const

Protected Types
typedef BlockArray< T >	Base

Protected Member Functions
int	Hash (size_t p1, size_t p2) const
	hash function for Hashed2 items. More...

int	Hash (size_t p1, size_t p2, size_t p3) const
	hash function for Hashed4 items. More...

int	Hash (const Hashed2 &item) const
	Hash function for items of type T that inherit from Hashed2. More...

int	Hash (const Hashed4 &item) const
	Hash function for items of type T that inherit from Hashed4. More...

int	SearchList (int id, int p1, int p2) const
	Search the index of the item associated to the key (p1,p2) starting from the item with index id. More...

int	SearchList (int id, int p1, int p2, int p3) const
	Search the index of the item associated to the key (p1,p2,p3,(p4)) starting from the item with index id. More...

void	Insert (int idx, int id, T &item)
	Insert the item 'id' into bin 'idx'. More...

void	Unlink (int idx, int id)
	Unlink an item id from the linked list of bin idx. More...

void	CheckRehash ()
	Check table fill factor and resize if necessary. More...

void	DoRehash ()
	Double the size of the hash table (i.e., double the number of bins) and reinsert all items into the new bins. More...

int	BinSize (int idx) const
	Return the size of the bin "idx". More...

Protected Member Functions inherited from mfem::BlockArray< T >
int	Alloc ()

void	CheckIndex (int index) const

void	Destroy ()

Protected Attributes
int *	table

int	mask

Array< int >	unused

Protected Attributes inherited from mfem::BlockArray< T >
Array< T * >	blocks

int	size

int	shift

int	mask

Detailed Description

template<typename T>
class mfem::HashTable< T >

HashTable is a container for items that require associative access through pairs (or quadruples) of indices:

(p1, p2) -> item (p1, p2, p3, p4) -> item

An example of this are edges and faces in a mesh. Each edge is uniquely identified by two parent vertices and so can be easily accessed from different elements using this class. Similarly for faces.

The order of the p1, p2, ... indices is not relevant as they are sorted each time this class is invoked.

There are two main methods this class provides. The Get(...) methods always return an item given the two or four indices. If the item didn't previously exist, the methods creates a new one. The Find(...) methods, on the other hand, just return NULL or -1 if the item doesn't exist.

Each new item is automatically assigned a unique ID - the index of the item inside the BlockArray. The IDs may (but need not) be used as p1, p2, ... of other items.

The item type (T) needs to follow either the Hashed2 or the Hashed4 concept. It is easiest to just inherit from these structs.

All items in the container can also be accessed sequentially using the provided iterator.

Notes: The data structure and implementation is based on a BlockArray<T> which provides an efficient item storage that avoids heap fragmentation, and index-based item access. The hash table implemented on top of the BlockArray provides fast associative (key -> value) access by grouping items into bins (buckets) of O(1) size.

"id" denotes the index of an item in the underlying BlockArray<T>,
"idx" denotes the index of a bin, determined by hashing a key with the function Hash.

Definition at line 81 of file hash.hpp.

Member Typedef Documentation

template<typename T>

typedef BlockArray<T> mfem::HashTable< T >::Base

protected

Definition at line 84 of file hash.hpp.

Constructor & Destructor Documentation

template<typename T >

mfem::HashTable< T >::HashTable	(	int	block_size = `16*1024`,
		int	init_hash_size = `32*1024`
	)

Main constructor of the HashTable class.

Parameters

[in]	block_size	The size of the storage blocks of the underlying BlockArray<T>.
[in]	init_hash_size	The initial size of the hash table. Must be a power of 2.

Definition at line 534 of file hash.hpp.

template<typename T >

mfem::HashTable< T >::HashTable ( const HashTable< T > & other )

Deep copy.

Definition at line 548 of file hash.hpp.

template<typename T >

mfem::HashTable< T >::~HashTable ( )

Definition at line 558 of file hash.hpp.

Member Function Documentation

template<typename T >

void mfem::HashTable< T >::Alloc	(	int	id,
		int	p1,
		int	p2
	)

Allocate an item at 'id'. Enlarge the underlying BlockArray if necessary.

Parameters

[in]	id	Index of the item in the underlying BlockArray<T>.
[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Warning: This is a special purpose method used when loading data from a file. Does nothing if the slot 'id' has already been allocated.

Definition at line 815 of file hash.hpp.

template<typename T>

iterator mfem::HashTable< T >::begin ( )

inline

Definition at line 335 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::BinSize ( int idx ) const

protected

Return the size of the bin "idx".

Parameters

[in] idx The index of the bin.

Returns: The size of the bin.

Definition at line 891 of file hash.hpp.

template<typename T>

const_iterator mfem::HashTable< T >::cbegin ( ) const

inline

Definition at line 338 of file hash.hpp.

template<typename T>

const_iterator mfem::HashTable< T >::cend ( ) const

inline

Definition at line 339 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::CheckRehash ( )

inlineprotected

Check table fill factor and resize if necessary.

The method checks the average size of the bins (i.e., the fill factor). If the fill factor is > 2, the table is enlarged (see DoRehash()).

Definition at line 737 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::Delete ( int id )

Remove an item from the hash table.

Parameters

[in] id Index of the item in the underlying BlockArray<T>.

Warning: Its id will be reused by newly added items.

Definition at line 798 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::DeleteAll ( )

Remove all items.

Definition at line 807 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::DoRehash ( )

protected

Double the size of the hash table (i.e., double the number of bins) and reinsert all items into the new bins.

NOTE: Rehashing is computationally expensive (O(N) in the number of items), but since it is only done rarely (when the number of items doubles), the amortized complexity of inserting an item is still O(1).

Definition at line 749 of file hash.hpp.

template<typename T>

iterator mfem::HashTable< T >::end ( )

inline

Definition at line 336 of file hash.hpp.

template<typename T >

T * mfem::HashTable< T >::Find	(	int	p1,
		int	p2
	)

inline

Find item whose parents are p1, p2... Return NULL if it doesn't exist.

Item accessor with key (or parents) the pair 'p1', 'p2'. Return nullptr if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The item associated to the key (p1,p2).

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 671 of file hash.hpp.

template<typename T >

T * mfem::HashTable< T >::Find	(	int	p1,
		int	p2,
		int	p3,
		int	p4 = `-1`
	)

inline

Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.
[in]	p4	Fourth part of the key (optional).

Returns: The item associated to the key (p1,p2,p3,p4).

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 678 of file hash.hpp.

template<typename T >

const T * mfem::HashTable< T >::Find	(	int	p1,
		int	p2
	)		const

inline

Item const accessor with key (or parents) the pair 'p1', 'p2'. Return nullptr if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The item associated to the key (p1,p2).

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 685 of file hash.hpp.

template<typename T >

const T * mfem::HashTable< T >::Find	(	int	p1,
		int	p2,
		int	p3,
		int	p4 = `-1`
	)		const

inline

Item const accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Return nullptr if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.
[in]	p4	Fourth part of the key (optional).

Returns: The item associated to the key (p1,p2,p3,p4).

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 692 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::FindId	(	int	p1,
		int	p2
	)		const

Find id of item whose parents are p1, p2... Return -1 if it doesn't exist.

Find the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 699 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::FindId	(	int	p1,
		int	p2,
		int	p3,
		int	p4 = `-1`
	)		const

Find the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.
[in]	p4	Fourth part of the key (optional).

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 706 of file hash.hpp.

template<typename T >

T * mfem::HashTable< T >::Get	(	int	p1,
		int	p2
	)

inline

Item accessor with key (or parents) the pair 'p1', 'p2'. Default construct an item of type T if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 596 of file hash.hpp.

template<typename T >

T * mfem::HashTable< T >::Get	(	int	p1,
		int	p2,
		int	p3,
		int	p4 = `-1`
	)

inline

Item accessor with key (or parents) the quadruplet 'p1', 'p2', 'p3', 'p4'. The key 'p4' is optional. Default construct an item of type T if no value corresponds to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.
[in]	p4	Fourth part of the key (optional).

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 602 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::GetId	(	int	p1,
		int	p2
	)

Get id of item whose parents are p1, p2... Create it if it doesn't exist.

Get the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value corresponds to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 608 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::GetId	(	int	p1,
		int	p2,
		int	p3,
		int	p4 = `-1`
	)

Get the "id" of an item, this "id" corresponding to the index of the item in the underlying BlockArray<T> object. Default construct an item and id if no value correspond to the requested key.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.
[in]	p4	Fourth part of the key (optional).

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 639 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::Hash	(	size_t	p1,
		size_t	p2
	)		const

inlineprotected

hash function for Hashed2 items.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The hash key "idx" identifying a bin/bucket.

NOTE: the constants are arbitrary

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 364 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::Hash	(	size_t	p1,
		size_t	p2,
		size_t	p3
	)		const

inlineprotected

hash function for Hashed4 items.

Parameters

[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.

Returns: The hash key "idx" identifying a bin/bucket.

NOTE: The constants are arbitrary. NOTE: p4 is not hashed nor stored as p1, p2, p3 identify a face uniquely.

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 377 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::Hash ( const Hashed2 & item ) const

inlineprotected

Hash function for items of type T that inherit from Hashed2.

Definition at line 382 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::Hash ( const Hashed4 & item ) const

inlineprotected

Hash function for items of type T that inherit from Hashed4.

Definition at line 386 of file hash.hpp.

template<typename T>

bool mfem::HashTable< T >::IdExists ( int id ) const

inline

Return true if item 'id' exists in (is used by) the container.

Parameters

[in] id Index of the item in the underlying BlockArray<T>.

Warning: It is assumed that 0 <= id < NumIds().

Definition at line 234 of file hash.hpp.

template<typename T>

void mfem::HashTable< T >::Insert	(	int	idx,
		int	id,
		T &	item
	)

inlineprotected

Insert the item 'id' into bin 'idx'.

Parameters

[in]	idx	The bin/bucket index.
[in]	id	The index of the item in the BlockArray<T>.
[in]	item	The item to insert at the beginning of the linked list.

Warning: The method only works with bin 'idx' and does not check the overall fill factor of the hash table. If appropriate, use CheckRehash() for that.

Definition at line 772 of file hash.hpp.

template<typename T >

long mfem::HashTable< T >::MemoryUsage ( ) const

Return total size of allocated memory (tables plus items), in bytes.

Definition at line 878 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::NumFreeIds ( ) const

inline

Return the number of free/unused ids in the HashTable.

Definition at line 227 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::NumIds ( ) const

inline

Return the total number of ids (used and unused) in the HashTable.

Definition at line 224 of file hash.hpp.

template<typename T>

HashTable& mfem::HashTable< T >::operator= ( const HashTable< T > & )

delete

Copy assignment not supported.

template<typename T >

void mfem::HashTable< T >::PrintMemoryDetail ( ) const

Write details of the memory usage to the mfem output stream.

Definition at line 884 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::PrintStats ( ) const

Print a histogram of bin sizes for debugging purposes.

Definition at line 905 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::Reparent	(	int	id,
		int	new_p1,
		int	new_p2
	)

Change the key associated with an item.

In other words, makes an item hashed under different parent IDs.

Parameters

[in]	id	Index of the item in the underlying BlockArray<T>.
[in]	new_p1	First part of the new key.
[in]	new_p2	Second part of the new key.

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 846 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::Reparent	(	int	id,
		int	new_p1,
		int	new_p2,
		int	new_p3,
		int	new_p4 = `-1`
	)

Change the key associated with an item.

In other words, makes an item hashed under different parent IDs.

Parameters

[in]	id	Index of the item in the underlying BlockArray<T>.
[in]	new_p1	First part of the new key.
[in]	new_p2	Second part of the new key.
[in]	new_p3	Third part of the new key.
[in]	new_p4	Fourth part of the new key (optional).

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 861 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::SearchList	(	int	id,
		int	p1,
		int	p2
	)		const

protected

Search the index of the item associated to the key (p1,p2) starting from the item with index id.

Parameters

[in]	id	Index of the item in the underlying BlockArray<T>.
[in]	p1	First part of the key.
[in]	p2	Second part of the key.

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed2.

Definition at line 713 of file hash.hpp.

template<typename T >

int mfem::HashTable< T >::SearchList	(	int	id,
		int	p1,
		int	p2,
		int	p3
	)		const

protected

Search the index of the item associated to the key (p1,p2,p3,(p4)) starting from the item with index id.

Parameters

[in]	id	Index of the item in the underlying BlockArray<T>.
[in]	p1	First part of the key.
[in]	p2	Second part of the key.
[in]	p3	Third part of the key.

Returns: The index "id" of the key in the BlockArray<T>.

Warning: This method should only be called if T inherits from Hashed4.

Definition at line 725 of file hash.hpp.

template<typename T>

int mfem::HashTable< T >::Size ( ) const

inline

Return the number of elements currently stored in the HashTable.

Definition at line 221 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::Unlink	(	int	idx,
		int	id
	)

protected

Unlink an item id from the linked list of bin idx.

Parameters

[in]	idx	The bin/bucket index.
[in]	id	The index of the item in the BlockArray<T>.

Warning: The method aborts if the item is not found.

Definition at line 780 of file hash.hpp.

template<typename T >

void mfem::HashTable< T >::UpdateUnused ( )

Reinitialize the internal list of unallocated items.

Warning: This is a special purpose method used when loading data from a file.

Definition at line 836 of file hash.hpp.

Member Data Documentation

template<typename T>

int mfem::HashTable< T >::mask

protected

mask = table_size-1. Used for fast modulo operation in Hash(), to wrap the raw hashed index around the current table size (which must be a power of two).

Definition at line 350 of file hash.hpp.

template<typename T>

int* mfem::HashTable< T >::table

protected

The hash table: each bin is a linked list of items. For each non-empty bin, this arrays stores the 'id' of the first item in the list, or -1 if the bin is empty.

Definition at line 345 of file hash.hpp.

template<typename T>

Array<int> mfem::HashTable< T >::unused

protected

List of deleted items in the BlockArray<T>. New items are created with these ids first, before they are appended to the block array.

Definition at line 354 of file hash.hpp.

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

general/hash.hpp

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<typename T> class mfem::HashTable< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class mfem::HashTable< T >