Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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 
40 
41 namespace ogdf {
42 
43 class HashingBase;
44 
46 
51  friend class HashingBase;
52 
54  size_t m_hashValue;
55 
56 public:
58  explicit HashElementBase(size_t hashValue) : m_next(nullptr), m_hashValue(hashValue) { }
59 
61  HashElementBase *next() const { return m_next; }
62 
64  size_t hashValue() const { return m_hashValue; }
65 
67 };
68 
69 
77 protected:
79  int m_hashMask;
83  int m_count;
85 
86 public:
88  explicit HashingBase(int minTableSize);
89 
91  HashingBase(const HashingBase &H);
92 
94  virtual ~HashingBase();
95 
97  void resize(int newTableSize);
98 
100  void insert(HashElementBase *pElement);
101 
103  void del(HashElementBase *pElement);
104 
106  void clear();
107 
109  HashingBase &operator=(const HashingBase &H);
110 
112  int size() const { return m_count; }
113 
115  int empty() const { return m_count==0; }
116 
122  HashElementBase *firstListElement(size_t hashValue) const {
123  return *(m_table + (hashValue & m_hashMask));
124  }
125 
134  HashElementBase *firstElement(HashElementBase ***pList) const;
135 
145  HashElementBase *nextElement(HashElementBase ***pList,
146  HashElementBase *pElement) const;
147 
148 protected:
150  void destroyAll();
151 
158  virtual void destroy(HashElementBase *pElement) = 0;
159 
161  virtual HashElementBase *copy(HashElementBase *pElement) const = 0;
162 
163 private:
165  void init(int tableSize);
166 
168  void copyAll(const HashingBase &H);
169 };
170 
171 
179 template<class K, class I>
181 {
182  K m_key;
183  I m_info;
184 
185 public:
187  HashElement(size_t hashValue, const K &key, const I &info) :
189 
193  }
194 
196  const K &key() const { return m_key; }
197 
199  const I &info() const { return m_info; }
200 
202  I &info() { return m_info; }
203 
205 };
206 
207 
208 template<class K, class I, class H> class HashConstIterator;
209 
218 template<class K> class DefHashFunc {
219 public:
221  size_t hash(const K &key) const { return size_t(key); }
222 };
223 
225 template<> class DefHashFunc<void *> {
226 public:
227  size_t hash(const void * &key) const { return size_t(key && 0xffffffff); }
228 };
229 
231 template<> class DefHashFunc<double> {
232 public:
233  size_t hash(const double &key) const {
234  int dummy;
235  return (size_t)((double)std::numeric_limits<size_t>::max() * frexp(key,&dummy));
236  }
237 };
238 
240 template<> class DefHashFunc<string> {
241 public:
242  size_t hash(const string &key) const;
243 };
244 
245 
247 
263 template<class K, class I, class H = DefHashFunc<K> >
264 class Hashing : private HashingBase
265 {
266  friend class HashConstIterator<K,I,H>;
268 
269 public:
272 
274  explicit Hashing(int minTableSize = 256, const H &hashFunc = H())
275  : HashingBase(minTableSize), m_hashFunc(hashFunc) { }
276 
278  Hashing(const Hashing<K,I,H> &h) = default;
279 
282 
284  int size() const { return HashingBase::size(); }
285 
287  bool empty() const { return HashingBase::size() == 0; }
288 
290  bool member(const K &key) const { return lookup(key) != nullptr; }
291 
294 
296  HashElement<K,I> *lookup(const K &key) const {
297  HashElement<K,I> *pElement =
299  for (; pElement; pElement = pElement->next())
300  if (pElement->key() == key) return pElement;
301 
302  return nullptr;
303  }
304 
306  Hashing<K,I,H> &operator=(const Hashing<K,I,H> &hashing) = default;
307 
315  HashElement<K,I> *insert(const K &key, const I &info) {
316  HashElement<K,I> *pElement = lookup(key);
317 
318  if (pElement)
319  pElement->info() = info;
320  else
321  HashingBase::insert(pElement =
322  new HashElement<K,I>(m_hashFunc.hash(key),key,info));
323 
324  return pElement;
325  }
326 
334  HashElement<K,I> *insertByNeed(const K &key, const I &info) {
335  HashElement<K,I> *pElement = lookup(key);
336 
337  if (!pElement)
338  HashingBase::insert(pElement = new HashElement<K,I>(m_hashFunc.hash(key),key,info));
339 
340  return pElement;
341  }
342 
349  HashElement<K,I> *fastInsert(const K &key, const I &info) {
350  HashElement<K,I> *pElement = new HashElement<K,I>(m_hashFunc.hash(key),key,info);
351  HashingBase::insert(pElement);
352  return pElement;
353  }
354 
356  void del(const K &key) {
357  HashElement<K,I> *pElement = lookup(key);
358  if (pElement) {
359  HashingBase::del(pElement);
360  delete pElement;
361  }
362  }
363 
365  void clear() { HashingBase::clear(); }
366 
367 protected:
378  }
379 
390  HashElement<K,I> *pElement) const
391  {
393  (HashElementBase ***)pList,pElement));
394  }
395 
396 private:
398  virtual void destroy(HashElementBase *pElement) override {
399  delete (HashElement<K,I> *)(pElement);
400  }
401 
403  virtual HashElementBase *copy(HashElementBase *pElement) const override {
404  HashElement<K,I> *pX = (HashElement<K,I> *)(pElement);
405  return new HashElement<K,I>(pX->hashValue(),pX->key(),pX->info());
406  }
407 };
408 
409 
433 template<class K, class I, class H = DefHashFunc<K> >
434 class HashConstIterator {
438 
439 public:
441  HashConstIterator() : m_pElement(nullptr), m_pList(nullptr), m_pHashing(nullptr) { }
442 
445  const Hashing<K,I,H> *pHashing) : m_pElement(pElement), m_pList(pList),
446  m_pHashing(pHashing) { }
447 
450  m_pList(it.m_pList), m_pHashing(it.m_pHashing) { }
451 
454  m_pElement = it.m_pElement;
455  m_pList = it.m_pList;
456  m_pHashing = it.m_pHashing;
457  return *this;
458  }
459 
461  bool valid() const { return m_pElement != nullptr; }
462 
464  const K &key() const { return m_pElement->key(); }
465 
467  const I &info() const { return m_pElement->info(); }
468 
470  friend bool operator==(const HashConstIterator<K,I,H> &it1,
471  const HashConstIterator<K,I,H> &it2) { return it1.m_pElement == it2.m_pElement; }
472 
474  friend bool operator!=(const HashConstIterator<K,I,H> &it1,
475  const HashConstIterator<K,I,H> &it2) { return it1.m_pElement != it2.m_pElement; }
476 
479  m_pElement = m_pHashing->nextElement(&m_pList,m_pElement);
480  return *this;
481  }
482 };
483 
484 
485 template<class K, class I, class H>
487 {
488  HashElement<K,I> *pElement, **pList;
489  pElement = firstElement(&pList);
490  return HashConstIterator<K,I,H>(pElement,pList,this);
491 }
492 
493 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::Hashing::begin
HashConstIterator< K, I, H > begin() const
Returns an hash iterator to the first element in the list of all elements.
Definition: Hashing.h:486
ogdf::DefHashFunc
Default hash functions.
Definition: Hashing.h:218
ogdf::HashConstIterator::operator!=
friend bool operator!=(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Inequality operator.
Definition: Hashing.h:474
ogdf::HashingBase::empty
int empty() const
Returns if the hash table is empty.
Definition: Hashing.h:115
ogdf::Hashing::m_hashFunc
H m_hashFunc
The hash function.
Definition: Hashing.h:267
ogdf::HashingBase::firstListElement
HashElementBase * firstListElement(size_t hashValue) const
Returns the first element in the list for elements with hash value hashValue.
Definition: Hashing.h:122
ogdf::HashingBase::del
void del(HashElementBase *pElement)
Removes the element pElement from the hash table.
ogdf::HashElement::next
HashElement< K, I > * next() const
Returns the successor element in the list.
Definition: Hashing.h:191
ogdf::Hashing::Hashing
Hashing(int minTableSize=256, const H &hashFunc=H())
Creates a hash table for given initial table size minTableSize.
Definition: Hashing.h:274
ogdf::Hashing::operator=
Hashing< K, I, H > & operator=(const Hashing< K, I, H > &hashing)=default
Assignment operator.
ogdf::HashingBase::m_tableSizeHigh
int m_tableSizeHigh
The maximal number of elements at this table size.
Definition: Hashing.h:82
ogdf::HashElementBase::m_hashValue
size_t m_hashValue
The hash value.
Definition: Hashing.h:54
ogdf::Hashing
Hashing with chaining and table doubling.
Definition: Hashing.h:264
ogdf::HashConstIterator::HashConstIterator
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:444
ogdf::HashElementBase::next
HashElementBase * next() const
Returns the successor to this element in the list.
Definition: Hashing.h:61
ogdf::Hashing::insertByNeed
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:334
ogdf::HashingBase::firstElement
HashElementBase * firstElement(HashElementBase ***pList) const
Returns the first element in the list of all elements in the hash table.
ogdf::Hashing::copy
virtual HashElementBase * copy(HashElementBase *pElement) const override
Returns a copy of hash element pElement.
Definition: Hashing.h:403
ogdf::HashElement::m_info
I m_info
The information value.
Definition: Hashing.h:183
ogdf::Hashing::~Hashing
~Hashing()
Destruction.
Definition: Hashing.h:281
ogdf::Hashing::fastInsert
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:349
ogdf::HashConstIterator::operator==
friend bool operator==(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Equality operator.
Definition: Hashing.h:470
ogdf::HashingBase::size
int size() const
Returns the number of elements in the hash table.
Definition: Hashing.h:112
ogdf::HashingBase::m_count
int m_count
The current number of elements.
Definition: Hashing.h:83
ogdf::Hashing::destroy
virtual void destroy(HashElementBase *pElement) override
Deletes hash element pElement.
Definition: Hashing.h:398
ogdf::HashingBase::insert
void insert(HashElementBase *pElement)
Inserts a new element pElement into the hash table.
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::Hashing::firstElement
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:376
ogdf::DefHashFunc::hash
size_t hash(const K &key) const
Returns the hash value of key.
Definition: Hashing.h:221
ogdf::HashConstIterator::HashConstIterator
HashConstIterator()
Creates a hash iterator pointing to no element.
Definition: Hashing.h:441
ogdf::Hashing::lookup
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:296
ogdf::DefHashFunc< double >::hash
size_t hash(const double &key) const
Definition: Hashing.h:233
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::HashingBase::m_minTableSize
int m_minTableSize
The minimal table size.
Definition: Hashing.h:80
ogdf::HashingBase::m_hashMask
int m_hashMask
The current table size minus one.
Definition: Hashing.h:79
ogdf::HashConstIterator::valid
bool valid() const
Returns true if the hash iterator points to an element.
Definition: Hashing.h:461
ogdf::HashingBase::m_tableSizeLow
int m_tableSizeLow
The minimal number of elements at this table size.
Definition: Hashing.h:81
ogdf::HashElement::key
const K & key() const
Returns the key value.
Definition: Hashing.h:196
ogdf::Hashing::clear
void clear()
Removes all elements from the hash table.
Definition: Hashing.h:365
ogdf::DefHashFunc< void * >::hash
size_t hash(const void *&key) const
Definition: Hashing.h:227
ogdf::Hashing::size
int size() const
Returns the number of elements in the hash table.
Definition: Hashing.h:284
ogdf::HashingBase::destroyAll
void destroyAll()
Deletes all elements in hash table (but does not free m_table!).
ogdf::HashingBase::m_tableSize
int m_tableSize
The current table size.
Definition: Hashing.h:78
ogdf::Hashing::del
void del(const K &key)
Removes the element with key key from the hash table (does nothing if no such element).
Definition: Hashing.h:356
ogdf::HashConstIterator::key
const K & key() const
Returns the key of the hash element pointed to.
Definition: Hashing.h:464
ogdf::Hashing::member
bool member(const K &key) const
Returns true iff the hash table contains an element with key key.
Definition: Hashing.h:290
ogdf::HashConstIterator::m_pList
HashElement< K, I > ** m_pList
The list containg the hash element.
Definition: Hashing.h:436
ogdf::HashConstIterator
Iterators for hash tables.
Definition: Hashing.h:208
ogdf::Hashing::empty
bool empty() const
Returns true iff the table is empty, i.e., contains no elements.
Definition: Hashing.h:287
ogdf::HashElementBase::m_next
HashElementBase * m_next
The successor in the list.
Definition: Hashing.h:53
ogdf::HashConstIterator::HashConstIterator
HashConstIterator(const HashConstIterator< K, I, H > &it)
Copy constructor.
Definition: Hashing.h:449
ogdf::Hashing::insert
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:315
ogdf::HashConstIterator::m_pElement
HashElement< K, I > * m_pElement
The hash element to which the iterator points.
Definition: Hashing.h:435
ogdf::HashConstIterator::info
const I & info() const
Returns the information of the hash element pointed to.
Definition: Hashing.h:467
ogdf::HashConstIterator::m_pHashing
const Hashing< K, I, H > * m_pHashing
The associated hash table.
Definition: Hashing.h:437
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::HashingBase::m_table
HashElementBase ** m_table
The hash table (an array of lists).
Definition: Hashing.h:84
basic.h
Basic declarations, included by all source files.
ogdf::HashElement::HashElement
HashElement(size_t hashValue, const K &key, const I &info)
Creates a hash element with given hash value, key, and information.
Definition: Hashing.h:187
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::HashElement::m_key
K m_key
The key value.
Definition: Hashing.h:182
ogdf::Hashing::nextElement
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:389
ogdf::HashElementBase::hashValue
size_t hashValue() const
Returns the hash value of this element.
Definition: Hashing.h:64
ogdf::HashingBase::clear
void clear()
Removes all elements from the hash table.
ogdf::HashElement
Representation of elements in a hash table.
Definition: Hashing.h:180
ogdf::HashElement::info
const I & info() const
Returns the information value.
Definition: Hashing.h:199
ogdf::HashConstIterator::operator=
HashConstIterator & operator=(const HashConstIterator< K, I, H > &it)
Assignment operator.
Definition: Hashing.h:453
ogdf::HashElementBase
Base class for elements within a hash table.
Definition: Hashing.h:50
ogdf::HashingBase::nextElement
HashElementBase * nextElement(HashElementBase ***pList, HashElementBase *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
ogdf::HashingBase
Base class for hashing with chaining and table doubling.
Definition: Hashing.h:76
ogdf::HashConstIterator::operator++
HashConstIterator< K, I, H > & operator++()
Moves this hash iterator to the next element (iterator gets invalid if no more elements).
Definition: Hashing.h:478
memory.h
Declaration of memory manager for allocating small pieces of memory.
ogdf::HashElementBase::HashElementBase
HashElementBase(size_t hashValue)
Creates a hash element with hash value hashValue.
Definition: Hashing.h:58
ogdf::HashElement::info
I & info()
Returns a refeence to the information value.
Definition: Hashing.h:202