MFEM  v4.3.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)
 
 HashTable (const HashTable &other)
 
 ~HashTable ()
 
T * Get (int p1, int p2)
 Get item whose parents are 'p1', 'p2'... Create it if it doesn't exist. More...
 
T * Get (int p1, int p2, int p3, int p4=-1)
 
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)
 
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)
 
const T * Find (int p1, int p2) const
 
const T * Find (int p1, int p2, int p3, int p4=-1) const
 
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
 
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)
 Make an item hashed under different parent IDs. More...
 
void Reparent (int id, int new_p1, int new_p2, int new_p3, int new_p4=-1)
 
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...
 
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 ()
 
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 (int p1, int p2) const
 
int Hash (int p1, int p2, int p3) const
 
int Hash (const Hashed2 &item) const
 
int Hash (const Hashed4 &item) const
 
int SearchList (int id, int p1, int p2) const
 
int SearchList (int id, int p1, int p2, int p3) const
 
void Insert (int idx, int id, T &item)
 
void Unlink (int idx, int id)
 
void CheckRehash ()
 Check table load factor and resize if necessary. More...
 
void DoRehash ()
 
- 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.

Definition at line 71 of file hash.hpp.

Member Typedef Documentation

template<typename T>
typedef BlockArray<T> mfem::HashTable< T >::Base
protected

Definition at line 74 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 
)

Definition at line 297 of file hash.hpp.

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

Definition at line 311 of file hash.hpp.

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

Definition at line 321 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.

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 578 of file hash.hpp.

template<typename T>
iterator mfem::HashTable< T >::begin ( )
inline

Definition at line 179 of file hash.hpp.

template<typename T>
const_iterator mfem::HashTable< T >::cbegin ( ) const
inline

Definition at line 182 of file hash.hpp.

template<typename T>
const_iterator mfem::HashTable< T >::cend ( ) const
inline

Definition at line 183 of file hash.hpp.

template<typename T >
void mfem::HashTable< T >::CheckRehash ( )
inlineprotected

Check table load factor and resize if necessary.

Definition at line 500 of file hash.hpp.

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

Remove an item from the hash table.

Its id will be reused by newly added items.

Definition at line 561 of file hash.hpp.

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

Remove all items.

Definition at line 570 of file hash.hpp.

template<typename T >
void mfem::HashTable< T >::DoRehash ( )
protected

Definition at line 512 of file hash.hpp.

template<typename T>
iterator mfem::HashTable< T >::end ( )
inline

Definition at line 180 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.

Definition at line 434 of file hash.hpp.

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

Definition at line 441 of file hash.hpp.

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

Definition at line 448 of file hash.hpp.

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

Definition at line 455 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.

Definition at line 462 of file hash.hpp.

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

Definition at line 469 of file hash.hpp.

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

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

Definition at line 359 of file hash.hpp.

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

Definition at line 365 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.

Definition at line 371 of file hash.hpp.

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

Definition at line 402 of file hash.hpp.

template<typename T>
int mfem::HashTable< T >::Hash ( int  p1,
int  p2 
) const
inlineprotected

Definition at line 191 of file hash.hpp.

template<typename T>
int mfem::HashTable< T >::Hash ( int  p1,
int  p2,
int  p3 
) const
inlineprotected

Definition at line 194 of file hash.hpp.

template<typename T>
int mfem::HashTable< T >::Hash ( const Hashed2 item) const
inlineprotected

Definition at line 198 of file hash.hpp.

template<typename T>
int mfem::HashTable< T >::Hash ( const Hashed4 item) const
inlineprotected

Definition at line 201 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.

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

Definition at line 111 of file hash.hpp.

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

Definition at line 535 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 640 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 107 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 104 of file hash.hpp.

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

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

Definition at line 646 of file hash.hpp.

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

Make an item hashed under different parent IDs.

Definition at line 608 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 
)

Definition at line 623 of file hash.hpp.

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

Definition at line 476 of file hash.hpp.

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

Definition at line 488 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 101 of file hash.hpp.

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

Definition at line 543 of file hash.hpp.

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

Reinitialize the internal list of unallocated items.

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

Definition at line 598 of file hash.hpp.

Member Data Documentation

template<typename T>
int mfem::HashTable< T >::mask
protected

Definition at line 187 of file hash.hpp.

template<typename T>
int* mfem::HashTable< T >::table
protected

Definition at line 186 of file hash.hpp.

template<typename T>
Array<int> mfem::HashTable< T >::unused
protected

Definition at line 188 of file hash.hpp.


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