Scippy

SoPlex

Sequential object-oriented simPlex

DataHashTable< HashItem, Info > Class Template Reference

Generic hash table for data objects.Class DataHashTable provides a generic hash table for Data Objects, i.e., a map that maps arguments called HashItems to values called Infos. HashItem and Info types are passed as template arguments. HashItems must provide a comparison operator==(). Furthermore, both the HashItem and Info must be data objects in the sense that the assignment operator is equivalent to a memcpy() of the structure and no destructor is required. More...

#include <datahashtable.h>

Classes

class  Element
 template class for elements stored in the hash table More...
 

Public Member Functions

Access / modification
bool has (const HashItem &h) const
 Is item h present in DataHashTable? More...
 
const Info * get (const HashItem &h) const
 returns const pointer to Info of HashItem h or 0, if item is not found. More...
 
const Info & operator[] (const HashItem &h) const
 references Info of HashItem h. More...
 
void add (const HashItem &h, const Info &info)
 adds a new entry to the hash table. More...
 
void remove (const HashItem &h)
 remove HashItem h from the DataHashTable. More...
 
void clear ()
 remove all entries from DataHashTable. More...
 
void reMax (int newSize=-1, int newHashSize=0)
 reset size of the DataHashTable. More...
 
Debugging
bool isConsistent () const
 checks whether DataHashTable is consistent More...
 
Construction / destruction
 DataHashTable (int(*hashfun)(const HashItem *), int maxsize=265, int hashsize=0, Real factor=2.0)
 default constructor. More...
 
DataHashTableoperator= (const DataHashTable &base)
 assignment operator. More...
 
 DataHashTable (const DataHashTable &base)
 copy constructor. More...
 

Private Types

Types
typedef Element< HashItem, Info > Elem
 

Private Member Functions

Helpers
int autoHashSize () const
 determine a good m_hashsize. More...
 
int autoHashSizeold () const
 automatically computes a good m_hashsize. More...
 
int index (const HashItem &h) const
 returns hash index of HashItem h or -1, if h is not present. More...
 

Private Attributes

Data
DataArray< Elemm_elem
 stores all elements of the hash table More...
 
int m_hashsize
 increment added to hash index, if allready used More...
 
int m_used
 current number of entries in the hash table More...
 
int(* m_hashfun )(const HashItem *)
 pointer to hash function (mapping: HashItem -> int) More...
 
Real m_memfactor
 memory is reMax()ed by this factor if a new element does't fit More...
 
int primes [50]
 some prime numbers for fast access More...
 
int nprimes
 number of stored prime numbers More...
 

Detailed Description

template<class HashItem, class Info>
class soplex::DataHashTable< HashItem, Info >

Generic hash table for data objects.

Class DataHashTable provides a generic hash table for Data Objects, i.e., a map that maps arguments called HashItems to values called Infos. HashItem and Info types are passed as template arguments. HashItems must provide a comparison operator==(). Furthermore, both the HashItem and Info must be data objects in the sense that the assignment operator is equivalent to a memcpy() of the structure and no destructor is required.

The construction of a DataHashTable requires a hash function that assigns an integer value to every HashItem. Provided this, pairs of a HashItem and a Info can be added to the DataHashTable. No more than one Info can be assigned to the same HashItem at a time. The Info to a HashItem can be accessed through the subscript operator[]() with the Info object as a subscript.

The maximum number of elemens a DataHashTable can hold can be specified upon construction and may be reset with reMax() later on. Further, a value hash size value is required. This value must be less then the maximum number of elements and must not have a common dominator with the maximum number of elements. If not specified explicitely, it is set automatically to a reasonable value.

The implementation relies on an array of DataHashTable::Elements, from now on referred to as elements. Upon construction, all elements are marked as FREE. When an entry is added to the DataHashTable, the hash value is computed by calling m_hashfun for its HashItem. If this array element is unused, it is taken right away. Otherwise, the array index is incremented by the hash size (modulo the element array size()) until an unused element is found.

Removing elements is simply done by marking it as RELEASED. Hence, when searching for an element, the search loop may not stop, when a RELEASED element is encountered. However, such an element may be reused when adding a new element to the DataHashTable.

Further, memory management with resizing of the element array is straight forward.

Definition at line 76 of file datahashtable.h.

Member Typedef Documentation

◆ Elem

typedef Element< HashItem, Info > Elem
private

Definition at line 100 of file datahashtable.h.

Constructor & Destructor Documentation

◆ DataHashTable() [1/2]

DataHashTable ( int(*)(const HashItem *)  hashfun,
int  maxsize = 265,
int  hashsize = 0,
Real  factor = 2.0 
)
explicit

default constructor.

Allocates a DataHashTable for maxsize entries using hashfun as hash function. If hashsize > 0, m_hashsize is set to the specified value, otherwise a suitable hash size is computed automatically. Parameter factor is used for memory management: If more than maxsize entries are added to the DataHashTable, it will automatically be reMax()ed by a factor of factor.

Parameters
hashfunpointer to hash function.
maxsizemaximum number of hash elements.
hashsizehash size.
factorfactor for increasing data block.

Definition at line 277 of file datahashtable.h.

◆ DataHashTable() [2/2]

DataHashTable ( const DataHashTable< HashItem, Info > &  base)

copy constructor.

Definition at line 356 of file datahashtable.h.

Member Function Documentation

◆ add()

void add ( const HashItem &  h,
const Info &  info 
)

adds a new entry to the hash table.

Adds a new entry consisting of HashItem h and Info info to the DataHashTable. No entry with HashItem h must be in the DataHashTable yet. After completion, info may be accessed via get() or operator[]() with h as parameter. The DataHashTable is reMax()ed if it becomes neccessary.

Definition at line 165 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::reMax().

◆ autoHashSize()

int autoHashSize ( ) const
private

determine a good m_hashsize.

Determine next larger prime number for new m_hashsize

Returns
good value for m_hashsize

Definition at line 379 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::DataHashTable(), and DataHashTable< soplex::NameSet::Name, soplex::DataKey >::reMax().

◆ autoHashSizeold()

int autoHashSizeold ( ) const
private

automatically computes a good m_hashsize.

Computes a good m_hashsize as the product of all prime numbers not divisors of the number of elements that are <= the maximum divisor of the number of elemens.

Returns
good value for m_hashsize

Definition at line 416 of file datahashtable.h.

◆ clear()

◆ get()

const Info* get ( const HashItem &  h) const

returns const pointer to Info of HashItem h or 0, if item is not found.

Returns a pointer to Info component of hash element h or a zero pointer if element h is not in the table.

Definition at line 139 of file datahashtable.h.

Referenced by NameSet::key(), and NameSet::number().

◆ has()

◆ index()

int index ( const HashItem &  h) const
private

returns hash index of HashItem h or -1, if h is not present.

Using the hash function m_hashfun, the hash value of h is calculated. Starting with this hash index, every m_hashsize%-th element is compared with h until h is found or all elements have been checked.

Parameters
hHashItem, for which the hash index should be calculated
Returns
hash index of h or -1, if h is not a member of the hash table

Definition at line 459 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::get(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::has(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator[](), and DataHashTable< soplex::NameSet::Name, soplex::DataKey >::remove().

◆ isConsistent()

◆ operator=()

DataHashTable& operator= ( const DataHashTable< HashItem, Info > &  base)

assignment operator.

Definition at line 340 of file datahashtable.h.

◆ operator[]()

const Info& operator[] ( const HashItem &  h) const

references Info of HashItem h.

Index operator for accessing the Info associated to HashItem h. It is required that h belongs to the DataHashTable, otherwise it core dumps. Methods has() or get() can be used for inquiring wheater h belongs to the DataHashTable or not.

Definition at line 152 of file datahashtable.h.

◆ reMax()

void reMax ( int  newSize = -1,
int  newHashSize = 0 
)

reset size of the DataHashTable.

Reset the maximum number of elements of a DataHashTable to newSize. However, if newSize < m_used, it is resized to m_used only. If newHashSize < 1, a new hash size is computed automatically. Otherwise, the specified value will be taken.

Definition at line 215 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::add().

◆ remove()

void remove ( const HashItem &  h)

remove HashItem h from the DataHashTable.

Definition at line 193 of file datahashtable.h.

Member Data Documentation

◆ m_elem

DataArray< Elem > m_elem
private

stores all elements of the hash table

Definition at line 107 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().

◆ m_hashfun

int(* m_hashfun) (const HashItem *)
private

pointer to hash function (mapping: HashItem -> int)

Definition at line 113 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::add(), and DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().

◆ m_hashsize

◆ m_memfactor

Real m_memfactor
private

memory is reMax()ed by this factor if a new element does't fit

Definition at line 115 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().

◆ m_used

int m_used
private

current number of entries in the hash table

Definition at line 111 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().

◆ nprimes

int nprimes
private

number of stored prime numbers

Definition at line 119 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().

◆ primes

int primes[50]
private

some prime numbers for fast access

Definition at line 117 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=().