Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
Hashing.h
Go to the documentation of this file.
1
35#pragma once
36
37#include <ogdf/basic/basic.h>
38#include <ogdf/basic/memory.h>
39
40namespace ogdf {
41
42class HashingBase;
43
45
50 friend class HashingBase;
51
53 size_t m_hashValue;
54
55public:
57 explicit HashElementBase(size_t hashValue) : m_next(nullptr), m_hashValue(hashValue) { }
58
60 HashElementBase* next() const { return m_next; }
61
63 size_t hashValue() const { return m_hashValue; }
64
66};
67
75protected:
81 int m_count;
83
84public:
87
90
92 virtual ~HashingBase();
93
96
99
102
104 void clear();
105
108
110 int size() const { return m_count; }
111
113 int empty() const { return m_count == 0; }
114
120 HashElementBase* firstListElement(size_t hashValue) const {
121 return *(m_table + (hashValue & m_hashMask));
122 }
123
133
144
145protected:
148
155 virtual void destroy(HashElementBase* pElement) = 0;
156
159
160private:
162 void init(int tableSize);
163
165 void copyAll(const HashingBase& H);
166};
167
175template<class K, class I>
179
180public:
182 HashElement(size_t hashValue, const K& key, const I& info)
184
187
189 const K& key() const { return m_key; }
190
192 const I& info() const { return m_info; }
193
195 I& info() { return m_info; }
196
198};
199
200
201template<class K, class I, class H>
202class HashConstIterator;
203
212template<class K>
214public:
216 size_t hash(const K& key) const { return size_t(key); }
217};
218
220template<>
222public:
223 size_t hash(const void*& key) const { return size_t(key && 0xffffffff); }
224};
225
227template<>
229public:
230 size_t hash(const double& key) const {
231 int dummy;
232 return (size_t)((double)std::numeric_limits<size_t>::max() * frexp(key, &dummy));
233 }
234};
235
237template<>
238class DefHashFunc<string> {
239public:
240 size_t hash(const string& key) const;
241};
242
244
260template<class K, class I, class H = DefHashFunc<K>>
261class Hashing : private HashingBase {
262 friend class HashConstIterator<K, I, H>;
264
265public:
268
270 explicit Hashing(int minTableSize = 256, const H& hashFunc = H())
272
274 Hashing(const Hashing<K, I, H>& h) = default;
275
278
280 int size() const { return HashingBase::size(); }
281
283 bool empty() const { return HashingBase::size() == 0; }
284
286 bool member(const K& key) const { return lookup(key) != nullptr; }
287
290
292 HashElement<K, I>* lookup(const K& key) const {
294 for (; pElement; pElement = pElement->next()) {
295 if (pElement->key() == key) {
296 return pElement;
297 }
298 }
299
300 return nullptr;
301 }
302
304 Hashing<K, I, H>& operator=(const Hashing<K, I, H>& hashing) = default;
305
313 HashElement<K, I>* insert(const K& key, const I& info) {
315
316 if (pElement) {
317 pElement->info() = info;
318 } else {
319 HashingBase::insert(pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info));
320 }
321
322 return pElement;
323 }
324
332 HashElement<K, I>* insertByNeed(const K& key, const I& info) {
334
335 if (!pElement) {
336 HashingBase::insert(pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info));
337 }
338
339 return pElement;
340 }
341
348 HashElement<K, I>* fastInsert(const K& key, const I& info) {
349 HashElement<K, I>* pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info);
351 return pElement;
352 }
353
355 void del(const K& key) {
357 if (pElement) {
359 delete pElement;
360 }
361 }
362
365
366protected:
378
391
392private:
394 virtual void destroy(HashElementBase* pElement) override {
395 delete (HashElement<K, I>*)(pElement);
396 }
397
399 virtual HashElementBase* copy(HashElementBase* pElement) const override {
401 return new HashElement<K, I>(pX->hashValue(), pX->key(), pX->info());
402 }
403};
404
428template<class K, class I, class H = DefHashFunc<K>>
433
434public:
437
442
446
450 m_pList = it.m_pList;
452 return *this;
453 }
454
456 bool valid() const { return m_pElement != nullptr; }
457
459 const K& key() const { return m_pElement->key(); }
460
462 const I& info() const { return m_pElement->info(); }
463
467 return it1.m_pElement == it2.m_pElement;
468 }
469
473 return it1.m_pElement != it2.m_pElement;
474 }
475
478 m_pElement = m_pHashing->nextElement(&m_pList, m_pElement);
479 return *this;
480 }
481};
482
483template<class K, class I, class H>
489
490}
Basic declarations, included by all source files.
size_t hash(const double &key) const
Definition Hashing.h:230
size_t hash(const string &key) const
size_t hash(const void *&key) const
Definition Hashing.h:223
Default hash functions.
Definition Hashing.h:213
size_t hash(const K &key) const
Returns the hash value of key.
Definition Hashing.h:216
Iterators for hash tables.
Definition Hashing.h:429
HashConstIterator(const HashConstIterator< K, I, H > &it)
Copy constructor.
Definition Hashing.h:444
HashConstIterator< K, I, H > & operator++()
Moves this hash iterator to the next element (iterator gets invalid if no more elements).
Definition Hashing.h:477
HashConstIterator & operator=(const HashConstIterator< K, I, H > &it)
Assignment operator.
Definition Hashing.h:448
bool valid() const
Returns true if the hash iterator points to an element.
Definition Hashing.h:456
HashConstIterator()
Creates a hash iterator pointing to no element.
Definition Hashing.h:436
const K & key() const
Returns the key of the hash element pointed to.
Definition Hashing.h:459
HashElement< K, I > * m_pElement
The hash element to which the iterator points.
Definition Hashing.h:430
friend bool operator==(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Equality operator.
Definition Hashing.h:465
HashElement< K, I > ** m_pList
The list containg the hash element.
Definition Hashing.h:431
const I & info() const
Returns the information of the hash element pointed to.
Definition Hashing.h:462
friend bool operator!=(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Inequality operator.
Definition Hashing.h:471
const Hashing< K, I, H > * m_pHashing
The associated hash table.
Definition Hashing.h:432
HashConstIterator(HashElement< K, I > *pElement, HashElement< K, I > **pList, const Hashing< K, I, H > *pHashing)
Creates a hash iterator pointing to element pElement in list pList of hash table pHashing.
Definition Hashing.h:439
Base class for elements within a hash table.
Definition Hashing.h:49
size_t m_hashValue
The hash value.
Definition Hashing.h:53
size_t hashValue() const
Returns the hash value of this element.
Definition Hashing.h:63
HashElementBase(size_t hashValue)
Creates a hash element with hash value hashValue.
Definition Hashing.h:57
HashElementBase * next() const
Returns the successor to this element in the list.
Definition Hashing.h:60
HashElementBase * m_next
The successor in the list.
Definition Hashing.h:52
Representation of elements in a hash table.
Definition Hashing.h:176
HashElement< K, I > * next() const
Returns the successor element in the list.
Definition Hashing.h:186
const K & key() const
Returns the key value.
Definition Hashing.h:189
HashElement(size_t hashValue, const K &key, const I &info)
Creates a hash element with given hash value, key, and information.
Definition Hashing.h:182
const I & info() const
Returns the information value.
Definition Hashing.h:192
K m_key
The key value.
Definition Hashing.h:177
I & info()
Returns a refeence to the information value.
Definition Hashing.h:195
I m_info
The information value.
Definition Hashing.h:178
Base class for hashing with chaining and table doubling.
Definition Hashing.h:74
void init(int tableSize)
Initializes the table for given table size.
HashElementBase ** m_table
The hash table (an array of lists).
Definition Hashing.h:82
void del(HashElementBase *pElement)
Removes the element pElement from the hash table.
virtual ~HashingBase()
Destruction.
HashElementBase * nextElement(HashElementBase ***pList, HashElementBase *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
HashingBase & operator=(const HashingBase &H)
Assignment operator.
HashElementBase * firstElement(HashElementBase ***pList) const
Returns the first element in the list of all elements in the hash table.
int m_tableSizeHigh
The maximal number of elements at this table size.
Definition Hashing.h:80
HashingBase(int minTableSize)
Creates a hash table with minimum table size minTableSize.
int m_count
The current number of elements.
Definition Hashing.h:81
void clear()
Removes all elements from the hash table.
void resize(int newTableSize)
Resizes the hash table to newTableSize.
int m_minTableSize
The minimal table size.
Definition Hashing.h:78
virtual void destroy(HashElementBase *pElement)=0
Called to delete hash element.
int size() const
Returns the number of elements in the hash table.
Definition Hashing.h:110
virtual HashElementBase * copy(HashElementBase *pElement) const =0
Called to create a copy of the element pElement.
int m_tableSize
The current table size.
Definition Hashing.h:76
int m_tableSizeLow
The minimal number of elements at this table size.
Definition Hashing.h:79
HashingBase(const HashingBase &H)
Copy constructor.
void insert(HashElementBase *pElement)
Inserts a new element pElement into the hash table.
int m_hashMask
The current table size minus one.
Definition Hashing.h:77
void copyAll(const HashingBase &H)
Copies all elements from H to this hash table.
void destroyAll()
Deletes all elements in hash table (but does not free m_table!).
int empty() const
Returns if the hash table is empty.
Definition Hashing.h:113
HashElementBase * firstListElement(size_t hashValue) const
Returns the first element in the list for elements with hash value hashValue.
Definition Hashing.h:120
Hashing with chaining and table doubling.
Definition Hashing.h:261
HashElement< K, I > * insert(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
Definition Hashing.h:313
void del(const K &key)
Removes the element with key key from the hash table (does nothing if no such element).
Definition Hashing.h:355
Hashing(int minTableSize=256, const H &hashFunc=H())
Creates a hash table for given initial table size minTableSize.
Definition Hashing.h:270
~Hashing()
Destruction.
Definition Hashing.h:277
Hashing(const Hashing< K, I, H > &h)=default
Copy constructor.
virtual void destroy(HashElementBase *pElement) override
Deletes hash element pElement.
Definition Hashing.h:394
virtual HashElementBase * copy(HashElementBase *pElement) const override
Returns a copy of hash element pElement.
Definition Hashing.h:399
HashConstIterator< K, I, H > begin() const
Returns an hash iterator to the first element in the list of all elements.
Definition Hashing.h:484
void clear()
Removes all elements from the hash table.
Definition Hashing.h:364
HashElement< K, I > * fastInsert(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
Definition Hashing.h:348
bool empty() const
Returns true iff the table is empty, i.e., contains no elements.
Definition Hashing.h:283
H m_hashFunc
The hash function.
Definition Hashing.h:263
Hashing< K, I, H > & operator=(const Hashing< K, I, H > &hashing)=default
Assignment operator.
HashElement< K, I > * insertByNeed(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
Definition Hashing.h:332
int size() const
Returns the number of elements in the hash table.
Definition Hashing.h:280
bool member(const K &key) const
Returns true iff the hash table contains an element with key key.
Definition Hashing.h:286
HashElement< K, I > * firstElement(HashElement< K, I > ***pList) const
Returns the first element in the list of all elements in the hash table.
Definition Hashing.h:375
HashElement< K, I > * lookup(const K &key) const
Returns the hash element with key key in the hash table; returns nullptr if no such element exists.
Definition Hashing.h:292
HashElement< K, I > * nextElement(HashElement< K, I > ***pList, HashElement< K, I > *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
Definition Hashing.h:388
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
Declaration of memory manager for allocating small pieces of memory.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.