Generic hash table for data objects. 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...

DataHashTable &	operator= (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
Array< Elem >	m_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 88 of file datahashtable.h.

Member Typedef Documentation

◆ Elem

typedef Element< HashItem, Info > Elem

private

Definition at line 112 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

hashfun	pointer to hash function.
maxsize	maximum number of hash elements.
hashsize	hash size.
factor	factor for increasing data block.

Definition at line 293 of file datahashtable.h.

References DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::nprimes, and DataHashTable< HashItem, Info >::primes.

◆ DataHashTable() [2/2]

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

copy constructor.

Definition at line 372 of file datahashtable.h.

References DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_memfactor, and DataHashTable< HashItem, Info >::primes.

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 177 of file datahashtable.h.

References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashfun, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::m_used, DataHashTable< HashItem, Info >::reMax(), SOPLEX_HASHTABLE_FILLFACTOR, and DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::USED.

Referenced by DataHashTable< HashItem, Info >::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 395 of file datahashtable.h.

References DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::nprimes, and DataHashTable< HashItem, Info >::primes.

Referenced by DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::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 432 of file datahashtable.h.

References DataHashTable< HashItem, Info >::m_elem.

◆ clear()

void clear ( )

remove all entries from DataHashTable.

Definition at line 218 of file datahashtable.h.

References DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::FREE, DataHashTable< HashItem, Info >::m_elem, and DataHashTable< HashItem, Info >::m_used.

Referenced by DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::reMax().

◆ 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 151 of file datahashtable.h.

References DataHashTable< HashItem, Info >::index(), and DataHashTable< HashItem, Info >::m_elem.

◆ has()

bool has ( const HashItem & h ) const

Is item h present in DataHashTable?

Definition at line 141 of file datahashtable.h.

References DataHashTable< HashItem, Info >::index().

Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::operator[](), and DataHashTable< HashItem, Info >::remove().

◆ 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

h	HashItem, 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 475 of file datahashtable.h.

References DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::FREE, DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_used, and DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::USED.

Referenced by DataHashTable< HashItem, Info >::get(), DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::operator[](), and DataHashTable< HashItem, Info >::remove().

◆ isConsistent()

bool isConsistent ( ) const

checks whether DataHashTable is consistent

Definition at line 251 of file datahashtable.h.

References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_used, SPX_MSG_INCONSISTENT, and DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::USED.

Referenced by DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=().

◆ operator=()

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

assignment operator.

Definition at line 356 of file datahashtable.h.

References DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashfun, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::m_used, DataHashTable< HashItem, Info >::nprimes, and DataHashTable< HashItem, Info >::primes.

◆ 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 164 of file datahashtable.h.

References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::index(), and DataHashTable< HashItem, Info >::m_elem.

◆ 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 231 of file datahashtable.h.

References DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_used, Array< T >::size(), and DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::USED.

Referenced by DataHashTable< HashItem, Info >::add().

◆ remove()

void remove ( const HashItem & h )

remove HashItem h from the DataHashTable.

Definition at line 205 of file datahashtable.h.

References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_used, and DataHashTable< HashItem, Info >::Element< ElemHashItem, ElemInfo >::RELEASED.

Member Data Documentation

◆ m_elem

Array< Elem > m_elem

private

stores all elements of the hash table

Definition at line 119 of file datahashtable.h.

◆ m_hashfun

int(* m_hashfun) (const HashItem *)

private

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

Definition at line 125 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::add(), and DataHashTable< HashItem, Info >::operator=().

◆ m_hashsize

int m_hashsize

private

increment added to hash index, if allready used

Definition at line 121 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::DataHashTable(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::operator=(), and DataHashTable< HashItem, Info >::reMax().

◆ m_memfactor

Real m_memfactor

private

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

Definition at line 127 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=().

◆ m_used

int m_used

private

current number of entries in the hash table

Definition at line 123 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::operator=(), DataHashTable< HashItem, Info >::reMax(), and DataHashTable< HashItem, Info >::remove().

◆ nprimes

int nprimes

private

number of stored prime numbers

Definition at line 131 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=().

◆ primes

int primes[50]

private

some prime numbers for fast access

Definition at line 129 of file datahashtable.h.

Referenced by DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=().

SoPlex

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Elem

Constructor & Destructor Documentation

◆ DataHashTable() [1/2]

◆ DataHashTable() [2/2]

Member Function Documentation

◆ add()

◆ autoHashSize()

◆ autoHashSizeold()

◆ clear()

◆ get()

◆ has()

◆ index()

◆ isConsistent()

◆ operator=()

◆ operator[]()

◆ reMax()

◆ remove()

Member Data Documentation

◆ m_elem

◆ m_hashfun

◆ m_hashsize

◆ m_memfactor

◆ m_used

◆ nprimes

◆ primes