ogdf::HashingBase Class Reference

Base class for hashing with chaining and table doubling. More...

#include <ogdf/basic/Hashing.h>

Inheritance diagram for ogdf::HashingBase:

Public Member Functions
	HashingBase (const HashingBase &H)
	Copy constructor. More...
	HashingBase (int minTableSize)
	Creates a hash table with minimum table size minTableSize. More...
virtual	~HashingBase ()
	Destruction. More...
void	clear ()
	Removes all elements from the hash table. More...
void	del (HashElementBase *pElement)
	Removes the element pElement from the hash table. More...
int	empty () const
	Returns if the hash table is empty. More...
HashElementBase *	firstElement (HashElementBase ***pList) const
	Returns the first element in the list of all elements in the hash table. More...
HashElementBase *	firstListElement (size_t hashValue) const
	Returns the first element in the list for elements with hash value hashValue. More...
void	insert (HashElementBase *pElement)
	Inserts a new element pElement into the hash table. More...
HashElementBase *	nextElement (HashElementBase ***pList, HashElementBase *pElement) const
	Returns the successor of pElement in the list of all elements in the hash table. More...
HashingBase &	operator= (const HashingBase &H)
	Assignment operator. More...
void	resize (int newTableSize)
	Resizes the hash table to newTableSize. More...
int	size () const
	Returns the number of elements in the hash table. More...

Protected Member Functions
virtual HashElementBase *	copy (HashElementBase *pElement) const =0
	Called to create a copy of the element pElement. More...
virtual void	destroy (HashElementBase *pElement)=0
	Called to delete hash element. More...
void	destroyAll ()
	Deletes all elements in hash table (but does not free m_table!). More...

Protected Attributes
int	m_count
	The current number of elements. More...
int	m_hashMask
	The current table size minus one. More...
int	m_minTableSize
	The minimal table size. More...
HashElementBase **	m_table
	The hash table (an array of lists). More...
int	m_tableSize
	The current table size. More...
int	m_tableSizeHigh
	The maximal number of elements at this table size. More...
int	m_tableSizeLow
	The minimal number of elements at this table size. More...

Private Member Functions
void	copyAll (const HashingBase &H)
	Copies all elements from H to this hash table. More...
void	init (int tableSize)
	Initializes the table for given table size. More...

Detailed Description

Base class for hashing with chaining and table doubling.

The actual hashing is provided by the parameterized class Hashing<K,I> which derives from HashingBase.

Definition at line 77 of file Hashing.h.

Constructor & Destructor Documentation

HashingBase() [1/2]

ogdf::HashingBase::HashingBase ( int  minTableSize )

explicit

Creates a hash table with minimum table size minTableSize.

HashingBase() [2/2]

ogdf::HashingBase::HashingBase

(

const HashingBase &

H

)

Copy constructor.

~HashingBase()

virtual ogdf::HashingBase::~HashingBase ( )

virtual

Destruction.

Member Function Documentation

clear()

void ogdf::HashingBase::clear

(

)

Removes all elements from the hash table.

copy()

virtual HashElementBase* ogdf::HashingBase::copy ( HashElementBase *  pElement ) const

protectedpure virtual

Called to create a copy of the element pElement.

Implemented in ogdf::Hashing< K, I, H >, ogdf::Hashing< Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > >, ogdf::Hashing< int, ogdf::ClusterElement, DefHashFunc< int > >, ogdf::Hashing< ogdf::List< ogdf::NodeElement >, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::DWMData, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::SortedNodeListHashFunc >, ogdf::Hashing< ogdf::EdgeElement, PrioritizedQueue< ogdf::EdgeElement, TCap, std::less< TCap >, PairingHeap >::Handle, DefHashFunc< ogdf::EdgeElement > >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, DefHashFunc< I1_ >, DefHashFunc< I2_ > > >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< I, E, DefHashFunc< I > >, ogdf::Hashing< K, I, DefHashFunc< K > >, ogdf::Hashing< ogdf::List< ogdf::NodeElement >, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner::DWMData, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner::SortedNodeListHashFunc >, ogdf::Hashing< Tuple2< I1, I2 >, E, HashFuncTuple< I1, I2, DefHashFunc< I1 >, DefHashFunc< I2 > > >, ogdf::Hashing< int, ogdf::ListIteratorBase< int >, DefHashFunc< int > >, and ogdf::Hashing< std::string, ogdf::NodeElement, DefHashFunc< std::string > >.

copyAll()

void ogdf::HashingBase::copyAll ( const HashingBase &  H )

private

Copies all elements from H to this hash table.

del()

void ogdf::HashingBase::del

(

HashElementBase *

pElement

)

Removes the element pElement from the hash table.

destroy()

virtual void ogdf::HashingBase::destroy ( HashElementBase *  pElement )

protectedpure virtual

Called to delete hash element.

This must be done in Hashing<K,I> since only this class knows the actual element type; alternatively, HashElementBase could have a virtual destructor.

Implemented in ogdf::Hashing< K, I, H >, ogdf::Hashing< Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< E, PrioritizedQueue< E, P, std::less< P >, PairingHeap >::Handle, DefHashFunc< E > >, ogdf::Hashing< int, ogdf::ClusterElement, DefHashFunc< int > >, ogdf::Hashing< ogdf::List< ogdf::NodeElement >, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::DWMData, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::SortedNodeListHashFunc >, ogdf::Hashing< ogdf::EdgeElement, PrioritizedQueue< ogdf::EdgeElement, TCap, std::less< TCap >, PairingHeap >::Handle, DefHashFunc< ogdf::EdgeElement > >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, DefHashFunc< I1_ >, DefHashFunc< I2_ > > >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< I, E, DefHashFunc< I > >, ogdf::Hashing< K, I, DefHashFunc< K > >, ogdf::Hashing< ogdf::List< ogdf::NodeElement >, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner::DWMData, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner::SortedNodeListHashFunc >, ogdf::Hashing< Tuple2< I1, I2 >, E, HashFuncTuple< I1, I2, DefHashFunc< I1 >, DefHashFunc< I2 > > >, ogdf::Hashing< int, ogdf::ListIteratorBase< int >, DefHashFunc< int > >, and ogdf::Hashing< std::string, ogdf::NodeElement, DefHashFunc< std::string > >.

destroyAll()

void ogdf::HashingBase::destroyAll ( )

protected

Deletes all elements in hash table (but does not free m_table!).

empty()

int ogdf::HashingBase::empty ( ) const

inline

Returns if the hash table is empty.

Definition at line 116 of file Hashing.h.

firstElement()

HashElementBase* ogdf::HashingBase::firstElement

(

HashElementBase ***

pList

)

const

Returns the first element in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters

pList

is assigned the list containing the first element.

Returns

a pointer to the first element or nullptr if hash table is empty.

firstListElement()

HashElementBase* ogdf::HashingBase::firstListElement ( size_t  hashValue ) const

inline

Returns the first element in the list for elements with hash value hashValue.

This is the list m_table[\ hashValue & m_hashMask].

Definition at line 123 of file Hashing.h.

init()

void ogdf::HashingBase::init ( int  tableSize )

private

Initializes the table for given table size.

insert()

void ogdf::HashingBase::insert

(

HashElementBase *

pElement

)

Inserts a new element pElement into the hash table.

nextElement()

HashElementBase* ogdf::HashingBase::nextElement	(	HashElementBase ***	pList,
		HashElementBase *	pElement
	)		const

Returns the successor of pElement in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters

pList	is assigned the list containing the first element.
pElement	points to an element in the has table.

Returns

a pointer to the first element or nullptr if hash table is empty.

operator=()

HashingBase& ogdf::HashingBase::operator=

(

const HashingBase &

H

)

Assignment operator.

resize()

void ogdf::HashingBase::resize

(

int

newTableSize

)

Resizes the hash table to newTableSize.

size()

int ogdf::HashingBase::size ( ) const

inline

Returns the number of elements in the hash table.

Definition at line 113 of file Hashing.h.

Member Data Documentation

m_count

int ogdf::HashingBase::m_count

protected

The current number of elements.

Definition at line 84 of file Hashing.h.

m_hashMask

int ogdf::HashingBase::m_hashMask

protected

The current table size minus one.

Definition at line 80 of file Hashing.h.

m_minTableSize

int ogdf::HashingBase::m_minTableSize

protected

The minimal table size.

Definition at line 81 of file Hashing.h.

m_table

HashElementBase** ogdf::HashingBase::m_table

protected

The hash table (an array of lists).

Definition at line 85 of file Hashing.h.

m_tableSize

int ogdf::HashingBase::m_tableSize

protected

The current table size.

Definition at line 79 of file Hashing.h.

m_tableSizeHigh

int ogdf::HashingBase::m_tableSizeHigh

protected

The maximal number of elements at this table size.

Definition at line 83 of file Hashing.h.

m_tableSizeLow

int ogdf::HashingBase::m_tableSizeLow

protected

The minimal number of elements at this table size.

Definition at line 82 of file Hashing.h.

---

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

• include/ogdf/basic/Hashing.h