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?

const Info *	get (const HashItem &h) const
	returns const pointer to Info of HashItem `h` or 0, if item is not found.

const Info &	operator[] (const HashItem &h) const
	references Info of HashItem `h`.

void	add (const HashItem &h, const Info &info)
	adds a new entry to the hash table.

void	remove (const HashItem &h)
	remove HashItem `h` from the DataHashTable.

void	clear ()
	remove all entries from DataHashTable.

void	reMax (int newSize=-1, int newHashSize=0)
	reset size of the DataHashTable.

Debugging
bool	isConsistent () const
	checks whether DataHashTable is consistent

Construction / destruction
	DataHashTable (int(hashfun)(const HashItem ), int maxsize=256, int hashsize=0, Real factor=2.0)
	default constructor.

DataHashTable &	operator= (const DataHashTable &base)
	assignment operator.

	DataHashTable (const DataHashTable &base)
	copy constructor.

Private Types
Types
typedef Element< HashItem, Info >	Elem

Private Member Functions
Helpers
int	autoHashSize () const
	automatically computes a good m_hashsize.

int	index (const HashItem &h) const
	returns hash index of HashItem `h` or -1, if `h` is not present.

Private Attributes
Data
DataArray< Elem >	m_elem
	stores all elements of the hash table

int	m_hashsize
	increment added to hash index, if allready used

int	m_used
	current number of entries in the hash table

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

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

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

Member Typedef Documentation

typedef Element< HashItem, Info > Elem

private

Definition at line 97 of file datahashtable.h.

Constructor & Destructor Documentation

DataHashTable	(	int()(const HashItem )	hashfun,
		int	maxsize = `256`,
		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 266 of file datahashtable.h.

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

copy constructor.

Definition at line 298 of file datahashtable.h.

Member Function Documentation

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

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

int autoHashSize ( ) 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 321 of file datahashtable.h.

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

void clear ( )

remove all entries from DataHashTable.

Definition at line 194 of file datahashtable.h.

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

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

bool has ( const HashItem & h ) const

Is item h present in DataHashTable?

Definition at line 121 of file datahashtable.h.

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

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 363 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().

bool isConsistent ( ) const

checks whether DataHashTable is consistent

Definition at line 226 of file datahashtable.h.

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

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

assignment operator.

Definition at line 284 of file datahashtable.h.

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

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

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

void remove ( const HashItem & h )

remove HashItem h from the DataHashTable.

Definition at line 185 of file datahashtable.h.

Member Data Documentation

DataArray< Elem > m_elem

private

stores all elements of the hash table

Definition at line 104 of file datahashtable.h.

int(* m_hashfun)(const HashItem *)

private

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

Definition at line 110 of file datahashtable.h.

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

int m_hashsize

private

increment added to hash index, if allready used

Definition at line 106 of file datahashtable.h.

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

Real m_memfactor

private

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

Definition at line 112 of file datahashtable.h.

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

int m_used

private

current number of entries in the hash table

Definition at line 108 of file datahashtable.h.

Referenced by DataHashTable< soplex::NameSet::Name, soplex::DataKey >::add(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::clear(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::index(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::isConsistent(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::operator=(), DataHashTable< soplex::NameSet::Name, soplex::DataKey >::reMax(), and DataHashTable< soplex::NameSet::Name, soplex::DataKey >::remove().

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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