MFEM  v3.4
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)
 
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)
 
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)
 
const T * Find (int p1, int p2) const
 
const T * Find (int p1, int p2, int p3, int p4) 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) 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 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)
 
long MemoryUsage () const
 Return total size of allocated memory (tables plus items), in bytes. More...
 
void PrintMemoryDetail () const
 
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 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
 

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

Member Typedef Documentation

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

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

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

Definition at line 216 of file hash.hpp.

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

Definition at line 226 of file hash.hpp.

Member Function Documentation

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

Definition at line 165 of file hash.hpp.

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

Definition at line 168 of file hash.hpp.

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

Definition at line 169 of file hash.hpp.

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

Check table load factor and resize if necessary.

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

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

Definition at line 405 of file hash.hpp.

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

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

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

Definition at line 334 of file hash.hpp.

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

Definition at line 341 of file hash.hpp.

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

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

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

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

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

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

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

Definition at line 295 of file hash.hpp.

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

Definition at line 177 of file hash.hpp.

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

Definition at line 180 of file hash.hpp.

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

Definition at line 184 of file hash.hpp.

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

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

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

Definition at line 428 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 495 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 106 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 103 of file hash.hpp.

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

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

Definition at line 478 of file hash.hpp.

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

Definition at line 369 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 381 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 100 of file hash.hpp.

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

Definition at line 436 of file hash.hpp.

Member Data Documentation

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

Definition at line 173 of file hash.hpp.

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

Definition at line 172 of file hash.hpp.

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

Definition at line 174 of file hash.hpp.


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