MFEM  v4.4.0
Finite element discretization library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
Classes | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
mfem::HashTable< T > Class Template Reference

#include <hash.hpp>

Inheritance diagram for mfem::HashTable< T >:
[legend]
Collaboration diagram for mfem::HashTable< T >:
[legend]

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...
 
HashTableoperator= (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)
 
BlockArrayoperator= (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.

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_sizeThe size of the storage blocks of the underlying BlockArray<T>.
[in]init_hash_sizeThe 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]idIndex of the item in the underlying BlockArray<T>.
[in]p1First part of the key.
[in]p2Second 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]idxThe 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]idIndex 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third part of the key.
[in]p4Fourth 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third part of the key.
[in]p4Fourth 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third part of the key.
[in]p4Fourth 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third part of the key.
[in]p4Fourth 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third part of the key.
[in]p4Fourth 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]p1First part of the key.
[in]p2Second 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]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third 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]idIndex 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]idxThe bin/bucket index.
[in]idThe index of the item in the BlockArray<T>.
[in]itemThe 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]idIndex of the item in the underlying BlockArray<T>.
[in]new_p1First part of the new key.
[in]new_p2Second 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]idIndex of the item in the underlying BlockArray<T>.
[in]new_p1First part of the new key.
[in]new_p2Second part of the new key.
[in]new_p3Third part of the new key.
[in]new_p4Fourth 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]idIndex of the item in the underlying BlockArray<T>.
[in]p1First part of the key.
[in]p2Second 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]idIndex of the item in the underlying BlockArray<T>.
[in]p1First part of the key.
[in]p2Second part of the key.
[in]p3Third 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]idxThe bin/bucket index.
[in]idThe 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: