Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::HashingBase Class Referenceabstract

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...
 
HashElementBasefirstElement (HashElementBase ***pList) const
 Returns the first element in the list of all elements in the hash table. More...
 
HashElementBasefirstListElement (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...
 
HashElementBasenextElement (HashElementBase ***pList, HashElementBase *pElement) const
 Returns the successor of pElement in the list of all elements in the hash table. More...
 
HashingBaseoperator= (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 HashElementBasecopy (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 76 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

◆ 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::EdgeElement, PrioritizedQueue< ogdf::EdgeElement, TCap, std::less< TCap >, PairingHeap >::Handle, DefHashFunc< ogdf::EdgeElement > >, ogdf::Hashing< ogdf::List< ogdf::NodeElement >, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::DWMData, ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::SortedNodeListHashFunc >, 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< std::string, ogdf::NodeElement, DefHashFunc< std::string > >, and ogdf::Hashing< int, ogdf::ListIteratorBase< int >, DefHashFunc< int > >.

◆ 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 115 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
pListis 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 122 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
pListis assigned the list containing the first element.
pElementpoints 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 112 of file Hashing.h.

Member Data Documentation

◆ m_count

int ogdf::HashingBase::m_count
protected

The current number of elements.

Definition at line 83 of file Hashing.h.

◆ m_hashMask

int ogdf::HashingBase::m_hashMask
protected

The current table size minus one.

Definition at line 79 of file Hashing.h.

◆ m_minTableSize

int ogdf::HashingBase::m_minTableSize
protected

The minimal table size.

Definition at line 80 of file Hashing.h.

◆ m_table

HashElementBase** ogdf::HashingBase::m_table
protected

The hash table (an array of lists).

Definition at line 84 of file Hashing.h.

◆ m_tableSize

int ogdf::HashingBase::m_tableSize
protected

The current table size.

Definition at line 78 of file Hashing.h.

◆ m_tableSizeHigh

int ogdf::HashingBase::m_tableSizeHigh
protected

The maximal number of elements at this table size.

Definition at line 82 of file Hashing.h.

◆ m_tableSizeLow

int ogdf::HashingBase::m_tableSizeLow
protected

The minimal number of elements at this table size.

Definition at line 81 of file Hashing.h.


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