aGrUM  0.20.3
a C++ library for (probabilistic) graphical models
hashTable_tpl.h
Go to the documentation of this file.
1 /**
2  *
3  * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
4  * info_at_agrum_dot_org
5  *
6  * This library is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Implementation of the HashTable
25  *
26  * @author Christophe GONZALES(@AMU) and Pierre-Henri WUILLEMIN(@LIP6)
27  */
28 #include <iostream>
29 #include <sstream>
30 #include <string>
31 
32 // to help IDE parser
33 #include <agrum/tools/core/hashTable.h>
34 
35 namespace gum {
36 
37 
38  // ===========================================================================
39  // === IMPLEMENTATION OF THE CHAINED LISTS USED IN THE HASH TABLES ===
40  // ===========================================================================
41 
42  template < typename Key, typename Val, typename Alloc >
43  template < typename OtherAlloc >
44  void HashTableList< Key, Val, Alloc >::_copy_(const HashTableList< Key, Val, OtherAlloc >& from) {
45  Bucket *ptr, *old_ptr{nullptr}, *new_elt{nullptr};
46  // set the defaults
47  _deb_list_ = nullptr;
48 
49  // copy from's list
50  try {
51  for (ptr = from._deb_list_; ptr != nullptr; ptr = ptr->next) {
52  // copy the current from's bucket (may throw an exception either because
53  // new cannot allocate the bucket or because the copy constructor of Val
54  // throws an exception)
55  new_elt = _alloc_bucket_->allocate(1);
56 
57  try {
58  _alloc_bucket_->construct(new_elt, *ptr);
59  } catch (...) {
60  _alloc_bucket_->deallocate(new_elt, 1);
61  throw;
62  }
63 
64  // rechain properly the new list
65  new_elt->prev = old_ptr;
66 
67  if (old_ptr != nullptr)
68  old_ptr->next = new_elt;
69  else
70  _deb_list_ = new_elt;
71 
72  old_ptr = new_elt;
73  }
74 
75  if (old_ptr != nullptr) old_ptr->next = nullptr;
76 
77  // update the number of elements stored into the list and the end of the
78  // list
79  _nb_elements_ = from._nb_elements_;
80  _end_list_ = new_elt;
81  } catch (...) {
82  // problem: we could not allocate an element in the list => we delete
83  // the elements created so far and we throw an exception
84  for (; _deb_list_ != nullptr; _deb_list_ = new_elt) {
85  new_elt = _deb_list_->next;
86  _alloc_bucket_->destroy(_deb_list_);
87  _alloc_bucket_->deallocate(_deb_list_, 1);
88  }
89 
90  _nb_elements_ = 0;
91  _end_list_ = nullptr;
92 
93  throw;
94  }
95  }
96 
97  template < typename Key, typename Val, typename Alloc >
98  INLINE HashTableBucket< Key, Val >*
99  HashTableList< Key, Val, Alloc >::bucket(const Key& key) const {
100  for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
101  if (ptr->key() == key) return ptr;
102 
103  return nullptr;
104  }
105 
106  template < typename Key, typename Val, typename Alloc >
107  INLINE void HashTableList< Key, Val, Alloc >::erase(HashTableBucket< Key, Val >* ptr) {
108  // check that the pointer is not nullptr
109  if (ptr == nullptr) { GUM_ERROR(NullElement, "trying to erase a nullptr bucket") }
110 
111  // relink properly the doubly chained list
112  if (ptr->prev != nullptr)
113  ptr->prev->next = ptr->next;
114  else
115  _deb_list_ = ptr->next;
116 
117  if (ptr->next != nullptr)
118  ptr->next->prev = ptr->prev;
119  else
120  _end_list_ = ptr->prev;
121 
122  // remove the current element from the list
123  _alloc_bucket_->destroy(ptr);
124  _alloc_bucket_->deallocate(ptr, 1);
125 
126  --_nb_elements_;
127  }
128 
129  template < typename Key, typename Val, typename Alloc >
130  INLINE HashTableList< Key, Val, Alloc >::HashTableList(
131  typename HashTableList< Key, Val, Alloc >::BucketAllocator* allocator) noexcept :
132  _alloc_bucket_{allocator} {}
133 
134  template < typename Key, typename Val, typename Alloc >
135  INLINE
136  HashTableList< Key, Val, Alloc >::HashTableList(const HashTableList< Key, Val, Alloc >& from) :
137  _alloc_bucket_{from._alloc_bucket_} {
138  _copy_(from);
139  }
140 
141  template < typename Key, typename Val, typename Alloc >
142  INLINE HashTableList< Key, Val, Alloc >::HashTableList(
143  HashTableList< Key, Val, Alloc >&& from) noexcept :
144  _deb_list_{from._deb_list_},
145  _end_list_{from._end_list_}, _nb_elements_{from._nb_elements_}, _alloc_bucket_{
146  from._alloc_bucket_} {
147  from._deb_list_ = nullptr;
148  }
149 
150  template < typename Key, typename Val, typename Alloc >
151  INLINE HashTableList< Key, Val, Alloc >::~HashTableList() {
152  for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
153  next_ptr = ptr->next;
154  _alloc_bucket_->destroy(ptr);
155  _alloc_bucket_->deallocate(ptr, 1);
156  }
157  }
158 
159  template < typename Key, typename Val, typename Alloc >
160  INLINE void HashTableList< Key, Val, Alloc >::clear() {
161  for (Bucket *next_ptr, *ptr = _deb_list_; ptr != nullptr; ptr = next_ptr) {
162  next_ptr = ptr->next;
163  _alloc_bucket_->destroy(ptr);
164  _alloc_bucket_->deallocate(ptr, 1);
165  }
166 
167  _nb_elements_ = Size(0);
168  _deb_list_ = nullptr;
169  _end_list_ = nullptr;
170  }
171 
172  template < typename Key, typename Val, typename Alloc >
173  INLINE HashTableList< Key, Val, Alloc >&
174  HashTableList< Key, Val, Alloc >::operator=(const HashTableList< Key, Val, Alloc >& from) {
175  // avoid self assignment
176  if (this != &from) {
177  clear();
178  _copy_(from);
179  }
180 
181  return *this;
182  }
183 
184  template < typename Key, typename Val, typename Alloc >
185  template < typename OtherAlloc >
186  INLINE HashTableList< Key, Val, Alloc >& HashTableList< Key, Val, Alloc >::operator=(
187  const HashTableList< Key, Val, OtherAlloc >& from) {
188  // avoid self assignment
189  if (this != reinterpret_cast< const HashTableList< Key, Val, Alloc >* >(&from)) {
190  clear();
191  _copy_(from);
192  }
193 
194  return *this;
195  }
196 
197  template < typename Key, typename Val, typename Alloc >
198  INLINE HashTableList< Key, Val, Alloc >&
199  HashTableList< Key, Val, Alloc >::operator=(HashTableList< Key, Val, Alloc >&& from) noexcept {
200  // avoid self assignment
201  if (this != &from) {
202  _deb_list_ = from._deb_list_;
203  _end_list_ = from._end_list_;
204  _nb_elements_ = from._nb_elements_;
205  from._deb_list_ = nullptr;
206  }
207 
208  return *this;
209  }
210 
211  template < typename Key, typename Val, typename Alloc >
212  INLINE void HashTableList< Key, Val, Alloc >::setAllocator(
213  typename HashTableList< Key, Val, Alloc >::BucketAllocator& alloc) {
214  _alloc_bucket_ = &alloc;
215  }
216 
217  template < typename Key, typename Val, typename Alloc >
218  INLINE typename HashTableList< Key, Val, Alloc >::value_type&
219  HashTableList< Key, Val, Alloc >::at(Size i) {
220  if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
221 
222  Bucket* ptr;
223 
224  for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
225 
226  return ptr->elt();
227  }
228 
229  template < typename Key, typename Val, typename Alloc >
230  INLINE const typename HashTableList< Key, Val, Alloc >::value_type&
231  HashTableList< Key, Val, Alloc >::at(Size i) const {
232  if (i >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the chained list") }
233 
234  Bucket* ptr;
235 
236  for (ptr = _deb_list_; i; --i, ptr = ptr->next) {}
237 
238  return ptr->elt();
239  }
240 
241  template < typename Key, typename Val, typename Alloc >
242  INLINE const typename HashTableList< Key, Val, Alloc >::mapped_type&
243  HashTableList< Key, Val, Alloc >::operator[](const Key& key) const {
244  for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
245  if (ptr->key() == key) return ptr->val();
246 
247  GUM_ERROR(NotFound, "No element with the key <" << key << ">")
248  }
249 
250  template < typename Key, typename Val, typename Alloc >
251  INLINE typename HashTableList< Key, Val, Alloc >::mapped_type&
252  HashTableList< Key, Val, Alloc >::operator[](const Key& key) {
253  for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next)
254  if (ptr->key() == key) return ptr->val();
255 
256  GUM_ERROR(NotFound, "No element with the key <" << key << ">")
257  }
258 
259  template < typename Key, typename Val, typename Alloc >
260  INLINE bool HashTableList< Key, Val, Alloc >::exists(const Key& key) const {
261  for (Bucket* ptr = _deb_list_; ptr != nullptr; ptr = ptr->next) {
262  if (ptr->key() == key) { return true; }
263  }
264 
265  return false;
266  }
267 
268  template < typename Key, typename Val, typename Alloc >
269  INLINE bool HashTableList< Key, Val, Alloc >::empty() const noexcept {
270  return (_nb_elements_ == Size(0));
271  }
272 
273  template < typename Key, typename Val, typename Alloc >
274  INLINE void
275  HashTableList< Key, Val, Alloc >::insert(HashTableBucket< Key, Val >* new_elt) noexcept {
276  // place the bucket at the beginning of the list
277  new_elt->prev = nullptr;
278  new_elt->next = _deb_list_;
279 
280  if (_deb_list_ != nullptr)
281  _deb_list_->prev = new_elt;
282  else
283  _end_list_ = new_elt;
284 
285  _deb_list_ = new_elt;
286 
287  ++_nb_elements_;
288  }
289 
290  // ===========================================================================
291  // === GENERIC HASH TABLE IMPLEMENTATION ===
292  // ===========================================================================
293 
294  template < typename Key, typename Val, typename Alloc >
295  template < typename OtherAlloc >
296  void HashTable< Key, Val, Alloc >::_copy_(const HashTable< Key, Val, OtherAlloc >& table) {
297  // in debug mode, check that this and table have ' __nodes' arrays of the
298  // same size
299  GUM_ASSERT(table._size_ == _size_);
300 
301  // try to fill the array of chained lists
302  for (Size i = 0; i < table._size_; ++i) {
303  try {
304  _nodes_[i] = table._nodes_[i];
305  } catch (...) {
306  // here we could allocate the _nodes_[j], j=0..i-1, so we should
307  // deallocate them
308  for (Size j = 0; j < _size_; ++j)
309  _nodes_[j].clear();
310 
311  _nb_elements_ = Size(0);
312 
313  // propagate the exception
314  throw;
315  }
316  }
317 
318  _nb_elements_ = table._nb_elements_;
319  }
320 
321  template < typename Key, typename Val, typename Alloc >
322  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
323  HashTable< Key, Val, Alloc >::end4Statics() {
324  return *(reinterpret_cast< const iterator* >(HashTableIteratorStaticEnd::end4Statics()));
325  }
326 
327  template < typename Key, typename Val, typename Alloc >
328  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
329  HashTable< Key, Val, Alloc >::constEnd4Statics() {
330  return *(
331  reinterpret_cast< const const_iterator* >(HashTableIteratorStaticEnd::constEnd4Statics()));
332  }
333 
334  template < typename Key, typename Val, typename Alloc >
335  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
336  HashTable< Key, Val, Alloc >::endSafe4Statics() {
337  return *(
338  reinterpret_cast< const iterator_safe* >(HashTableIteratorStaticEnd::endSafe4Statics()));
339  }
340 
341  template < typename Key, typename Val, typename Alloc >
342  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator_safe&
343  HashTable< Key, Val, Alloc >::constEndSafe4Statics() {
344  return *(reinterpret_cast< const const_iterator_safe* >(
345  HashTableIteratorStaticEnd::constEndSafe4Statics()));
346  }
347 
348  template < typename Key, typename Val, typename Alloc >
349  INLINE void HashTable< Key, Val, Alloc >::_create_(Size size) {
350  // setup the _nodes_ vector (contains only empty lists)
351  _nodes_.resize(size);
352 
353  for (auto& list: _nodes_) {
354  list.setAllocator(_alloc_);
355  }
356 
357  // set up properly the hash function
358  _hash_func_.resize(size);
359 
360  // make sure the end() iterator is constructed properly
361  end4Statics();
362  endSafe4Statics();
363  }
364 
365  template < typename Key, typename Val, typename Alloc >
366  HashTable< Key, Val, Alloc >::HashTable(Size size_param,
367  bool resize_pol,
368  bool key_uniqueness_pol) :
369  // size must be >= 2 else we lose all the bits of the hash function
370  _size_{Size(1) << _hashTableLog2_(std::max(Size(2), size_param))},
371  _resize_policy_{resize_pol}, _key_uniqueness_policy_{key_uniqueness_pol} {
372  // for debugging purposes
373  GUM_CONSTRUCTOR(HashTable);
374 
375  // finalize the creation
376  _create_(_size_);
377  }
378 
379  template < typename Key, typename Val, typename Alloc >
380  HashTable< Key, Val, Alloc >::HashTable(std::initializer_list< std::pair< Key, Val > > list) :
381  // size must be >= 2 else we lose all the bits of the hash function
382  _size_{Size(1) << _hashTableLog2_(std::max< Size >(Size(2), Size(list.size()) / 2))} {
383  // for debugging purposes
384  GUM_CONSTRUCTOR(HashTable);
385 
386  // setup the _nodes_ vector (contains only empty lists)
387  _create_(_size_);
388 
389  // insert all the elements
390  for (const auto& elt: list) {
391  insert(elt);
392  }
393  }
394 
395  template < typename Key, typename Val, typename Alloc >
396  HashTable< Key, Val, Alloc >::HashTable(const HashTable< Key, Val, Alloc >& table) :
397  _size_{table._size_}, _resize_policy_{table._resize_policy_},
398  _key_uniqueness_policy_{table._key_uniqueness_policy_}, _begin_index_{table._begin_index_} {
399  // for debugging purposes
400  GUM_CONS_CPY(HashTable);
401 
402  // setup the _nodes_ vector (contains only empty lists)
403  _create_(_size_);
404 
405  // fill with the content of table
406  _copy_(table);
407  }
408 
409  template < typename Key, typename Val, typename Alloc >
410  template < typename OtherAlloc >
411  HashTable< Key, Val, Alloc >::HashTable(const HashTable< Key, Val, OtherAlloc >& table) :
412  _size_{table._size_}, _resize_policy_{table._resize_policy_},
413  _key_uniqueness_policy_{table._key_uniqueness_policy_}, _begin_index_{table._begin_index_} {
414  // for debugging purposes
415  GUM_CONS_CPY(HashTable);
416 
417  // setup the _nodes_ vector (contains only empty lists)
418  _create_(_size_);
419 
420  // fill with the content of table
421  _copy_(table);
422  }
423 
424  template < typename Key, typename Val, typename Alloc >
425  HashTable< Key, Val, Alloc >::HashTable(HashTable< Key, Val, Alloc >&& table) :
426  _nodes_(std::move(table._nodes_)), _size_{table._size_}, _nb_elements_{table._nb_elements_},
427  _hash_func_{table._hash_func_}, _resize_policy_{table._resize_policy_},
428  _key_uniqueness_policy_{table._key_uniqueness_policy_}, _begin_index_{table._begin_index_},
429  _safe_iterators_(std::move(table._safe_iterators_)), _alloc_(std::move(table._alloc_)) {
430  // for debugging purposes
431  table._size_ = 0;
432  GUM_CONS_MOV(HashTable);
433  }
434 
435  template < typename Key, typename Val, typename Alloc >
436  INLINE void HashTable< Key, Val, Alloc >::_clearIterators_() {
437  const Size len = _safe_iterators_.size();
438  for (Size i = Size(0); i < len; ++i)
439  _safe_iterators_[i]->clear();
440  }
441 
442  template < typename Key, typename Val, typename Alloc >
443  INLINE void HashTable< Key, Val, Alloc >::clear() {
444  // update all the registered iterators: they should now point to nullptr
445  // and they are positioned to the end of the hashtable.
446  _clearIterators_();
447 
448  // remove the buckets
449  for (Size i = Size(0); i < _size_; ++i)
450  _nodes_[i].clear();
451 
452  _nb_elements_ = Size(0);
453  _begin_index_ = std::numeric_limits< Size >::max();
454  }
455 
456  template < typename Key, typename Val, typename Alloc >
457  INLINE HashTable< Key, Val, Alloc >::~HashTable() {
458  // for debugging purposes
459  GUM_DESTRUCTOR(HashTable);
460 
461  // update all the registered iterators: they should now point to nullptr
462  // and their hashtable should be set to nullptr
463  _clearIterators_();
464  }
465 
466  template < typename Key, typename Val, typename Alloc >
467  HashTable< Key, Val, Alloc >&
468  HashTable< Key, Val, Alloc >::operator=(const HashTable< Key, Val, Alloc >& from) {
469  // avoid self assignment
470  if (this != &from) {
471  // for debugging purposes
472  GUM_OP_CPY(HashTable);
473 
474  // first remove the current content of the hashtable and make
475  // the iterators point to end
476  clear();
477 
478  // if sizes of from's and this' _nodes_ vectors are not the same,
479  // we need to remove the current _nodes_' array and to create a
480  // new array with the correct size
481  if (_size_ != from._size_) {
482  _nodes_.resize(from._size_);
483 
484  for (Size i = Size(0); i < from._size_; ++i) {
485  _nodes_[i].setAllocator(_alloc_);
486  }
487 
488  _size_ = from._size_;
489 
490  // update the hash function : this is important as the computation of
491  // the hash values heavily depends on the size of the hash table
492  _hash_func_.resize(_size_);
493  }
494 
495  _resize_policy_ = from._resize_policy_;
496  _key_uniqueness_policy_ = from._key_uniqueness_policy_;
497  _begin_index_ = from._begin_index_;
498 
499  // perform the copy
500  _copy_(from);
501  }
502 
503  return *this;
504  }
505 
506  template < typename Key, typename Val, typename Alloc >
507  template < typename OtherAlloc >
508  HashTable< Key, Val, Alloc >&
509  HashTable< Key, Val, Alloc >::operator=(const HashTable< Key, Val, OtherAlloc >& from) {
510  // avoid self assignment
511  if (this != reinterpret_cast< const HashTable< Key, Val, Alloc >* >(&from)) {
512  // for debugging purposes
513  GUM_OP_CPY(HashTable);
514 
515  // first remove the current content of the hashtable and make
516  // the iterators point to end
517  clear();
518 
519  // if sizes of from's and this' _nodes_ vectors are not the same,
520  // we need to remove the current _nodes_' array and to create a
521  // new array with the correct size
522  if (_size_ != from._size_) {
523  _nodes_.resize(from._size_);
524 
525  for (Size i = 0; i < from._size_; ++i) {
526  _nodes_[i].setAllocator(_alloc_);
527  }
528 
529  _size_ = from._size_;
530 
531  // update the hash function : this is important as the computation of
532  // the hash values heavily depends on the size of the hash table
533  _hash_func_.resize(_size_);
534  }
535 
536  _resize_policy_ = from._resize_policy_;
537  _key_uniqueness_policy_ = from._key_uniqueness_policy_;
538  _begin_index_ = from._begin_index_;
539 
540  // perform the copy
541  _copy_(from);
542  }
543 
544  return *this;
545  }
546 
547  template < typename Key, typename Val, typename Alloc >
548  HashTable< Key, Val, Alloc >&
549  HashTable< Key, Val, Alloc >::operator=(HashTable< Key, Val, Alloc >&& table) {
550  // avoid self assignment
551  if (this != &table) {
552  // for debugging purposes
553  GUM_OP_MOV(HashTable);
554 
555  // first remove the current content of the hashtable and make
556  // the iterators point to end
557  clear();
558 
559  _nodes_ = std::move(table._nodes_);
560  _safe_iterators_ = std::move(table._safe_iterators_);
561  _alloc_ = std::move(table._alloc_);
562  _size_ = table._size_;
563  _nb_elements_ = table._nb_elements_;
564  _hash_func_ = table._hash_func_;
565  _resize_policy_ = table._resize_policy_;
566  _key_uniqueness_policy_ = table._key_uniqueness_policy_;
567  _begin_index_ = table._begin_index_;
568 
569  table._size_ = 0; // necessary if we wish to perform moves iteratively,
570  // i.e. x = std::move ( y ); y = std::move ( z ); ...
571  }
572 
573  return *this;
574  }
575 
576  template < typename Key, typename Val, typename Alloc >
577  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
578  HashTable< Key, Val, Alloc >::end() noexcept {
579  // note that, here, we know for sure that HashTableIterEnd has been properly
580  // initialized as it is initialized by end4Statics, which is called by
581  // all hashtables' constructors
582  return *(reinterpret_cast< const iterator* >(HashTableIteratorStaticEnd::_HashTableIterEnd_));
583  }
584 
585  template < typename Key, typename Val, typename Alloc >
586  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
587  HashTable< Key, Val, Alloc >::end() const noexcept {
588  // note that, here, we know for sure that HashTableIterEnd has been properly
589  // initialized as it is initialized by end4Statics, which is called by
590  // all hashtables' constructors
591  return *(
592  reinterpret_cast< const const_iterator* >(HashTableIteratorStaticEnd::_HashTableIterEnd_));
593  }
594 
595  template < typename Key, typename Val, typename Alloc >
596  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
597  HashTable< Key, Val, Alloc >::cend() const noexcept {
598  // note that, here, we know for sure that HashTableIterEnd has been properly
599  // initialized as it is initialized by end4Statics, which is called by
600  // all hashtables' constructors
601  return *(
602  reinterpret_cast< const const_iterator* >(HashTableIteratorStaticEnd::_HashTableIterEnd_));
603  }
604 
605  template < typename Key, typename Val, typename Alloc >
606  INLINE typename HashTable< Key, Val, Alloc >::iterator HashTable< Key, Val, Alloc >::begin() {
607  // if the table is empty, make the begin and end point to the same element
608  if (_nb_elements_ == Size(0))
609  return iterator{end()};
610  else
611  return iterator{*this};
612  }
613 
614  template < typename Key, typename Val, typename Alloc >
615  INLINE typename HashTable< Key, Val, Alloc >::const_iterator
616  HashTable< Key, Val, Alloc >::begin() const {
617  // if the table is empty, make the begin and end point to the same element
618  if (_nb_elements_ == Size(0))
619  return const_iterator{end()};
620  else
621  return const_iterator{*this};
622  }
623 
624  template < typename Key, typename Val, typename Alloc >
625  INLINE typename HashTable< Key, Val, Alloc >::const_iterator
626  HashTable< Key, Val, Alloc >::cbegin() const {
627  // if the table is empty, make the begin and end point to the same element
628  if (_nb_elements_ == Size(0))
629  return const_iterator{cend()};
630  else
631  return const_iterator{*this};
632  }
633 
634  template < typename Key, typename Val, typename Alloc >
635  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
636  HashTable< Key, Val, Alloc >::endSafe() noexcept {
637  // note that, here, we know for sure that HashTableIterEnd has been properly
638  // initialized as it is initialized by end4Statics, which is called by
639  // all hashtables' constructors
640  return *(reinterpret_cast< const iterator_safe* >(
641  HashTableIteratorStaticEnd::_HashTableIterEndSafe_));
642  }
643 
644  template < typename Key, typename Val, typename Alloc >
645  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator_safe&
646  HashTable< Key, Val, Alloc >::endSafe() const noexcept {
647  // note that, here, we know for sure that HashTableIterEnd has been properly
648  // initialized as it is initialized by end4Statics, which is called by
649  // all hashtables' constructors
650  return *(reinterpret_cast< const const_iterator_safe* >(
651  HashTableIteratorStaticEnd::_HashTableIterEndSafe_));
652  }
653 
654  template < typename Key, typename Val, typename Alloc >
655  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator_safe&
656  HashTable< Key, Val, Alloc >::cendSafe() const noexcept {
657  // note that, here, we know for sure that HashTableIterEnd has been properly
658  // initialized as it is initialized by end4Statics, which is called by
659  // all hashtables' constructors
660  return *(reinterpret_cast< const const_iterator_safe* >(
661  HashTableIteratorStaticEnd::_HashTableIterEndSafe_));
662  }
663 
664  template < typename Key, typename Val, typename Alloc >
665  INLINE typename HashTable< Key, Val, Alloc >::iterator_safe
666  HashTable< Key, Val, Alloc >::beginSafe() {
667  // if the table is empty, make the begin and end point to the same element
668  if (_nb_elements_ == Size(0))
669  return iterator_safe{endSafe()};
670  else
671  return iterator_safe{*this};
672  }
673 
674  template < typename Key, typename Val, typename Alloc >
675  INLINE typename HashTable< Key, Val, Alloc >::const_iterator_safe
676  HashTable< Key, Val, Alloc >::beginSafe() const {
677  // if the table is empty, make the begin and end point to the same element
678  if (_nb_elements_ == Size(0))
679  return const_iterator_safe{endSafe()};
680  else
681  return const_iterator_safe{*this};
682  }
683 
684  template < typename Key, typename Val, typename Alloc >
685  INLINE typename HashTable< Key, Val, Alloc >::const_iterator_safe
686  HashTable< Key, Val, Alloc >::cbeginSafe() const {
687  // if the table is empty, make the begin and end point to the same element
688  if (_nb_elements_ == Size(0))
689  return const_iterator_safe{cendSafe()};
690  else
691  return const_iterator_safe{*this};
692  }
693 
694  template < typename Key, typename Val, typename Alloc >
695  INLINE Val& HashTable< Key, Val, Alloc >::operator[](const Key& key) {
696  return _nodes_[_hash_func_(key)][key];
697  }
698 
699  template < typename Key, typename Val, typename Alloc >
700  INLINE const Val& HashTable< Key, Val, Alloc >::operator[](const Key& key) const {
701  return _nodes_[_hash_func_(key)][key];
702  }
703 
704  template < typename Key, typename Val, typename Alloc >
705  INLINE Size HashTable< Key, Val, Alloc >::size() const noexcept {
706  return _nb_elements_;
707  }
708 
709  template < typename Key, typename Val, typename Alloc >
710  INLINE Size HashTable< Key, Val, Alloc >::capacity() const noexcept {
711  return _size_;
712  }
713 
714  template < typename Key, typename Val, typename Alloc >
715  INLINE bool HashTable< Key, Val, Alloc >::exists(const Key& key) const {
716  return _nodes_[_hash_func_(key)].exists(key);
717  }
718 
719  template < typename Key, typename Val, typename Alloc >
720  INLINE void HashTable< Key, Val, Alloc >::setResizePolicy(const bool new_policy) noexcept {
721  _resize_policy_ = new_policy;
722  }
723 
724  template < typename Key, typename Val, typename Alloc >
725  INLINE bool HashTable< Key, Val, Alloc >::resizePolicy() const noexcept {
726  return _resize_policy_;
727  }
728 
729  template < typename Key, typename Val, typename Alloc >
730  INLINE void HashTable< Key, Val, Alloc >::setKeyUniquenessPolicy(const bool new_policy) noexcept {
731  _key_uniqueness_policy_ = new_policy;
732  }
733 
734  template < typename Key, typename Val, typename Alloc >
735  INLINE bool HashTable< Key, Val, Alloc >::keyUniquenessPolicy() const noexcept {
736  return _key_uniqueness_policy_;
737  }
738 
739  template < typename Key, typename Val, typename Alloc >
740  void HashTable< Key, Val, Alloc >::resize(Size new_size) {
741  // new_size must be >= 2 else all the bits of the hash function are lost
742  new_size = std::max(Size(2), new_size);
743 
744  // find the real size for allocation (the smallest power of 2 greater
745  // than or equal to new_size) and get its base-2 logarithm
746  int log_size = _hashTableLog2_(new_size);
747  new_size = Size(1) << log_size;
748 
749  // check if the new size is different from the actual size
750  // if not, nothing else need be done
751 
752  if (new_size != _size_) {
753  // under automatic resize policy, check if the new size leaves
754  // enough space for storing all the current elements
755  if (!_resize_policy_
756  || (_nb_elements_ <= new_size * HashTableConst::default_mean_val_by_slot)) {
757  // create a new array of _nodes_ to store the elements
758  std::vector< HashTableList< Key, Val, Alloc > > new_nodes(new_size);
759 
760  for (auto& list: new_nodes) {
761  list.setAllocator(_alloc_);
762  }
763 
764  // set the new hash function
765  _hash_func_.resize(new_size);
766 
767  // put all the elements of the current _nodes_ array into the new one
768  Bucket* bucket;
769  Size new_hashed_key;
770 
771  for (Size i = Size(0); i < _size_; ++i) {
772  while ((bucket = _nodes_[i]._deb_list_) != nullptr) {
773  // compute the new hashed key
774  new_hashed_key = _hash_func_(bucket->key());
775 
776  // remove the bucket from the list of buckets of the current
777  // node vector
778  _nodes_[i]._deb_list_ = bucket->next;
779 
780  // put the bucket into the new _nodes_ vector
781  new_nodes[new_hashed_key].insert(bucket);
782  }
783  }
784 
785  // update the size of the hash table
786  _size_ = new_size;
787  _begin_index_ = std::numeric_limits< Size >::max();
788 
789  // substitute the current _nodes_ array by the new one
790  std::swap(_nodes_, new_nodes);
791 
792  // update the iterators
793  for (auto iter: _safe_iterators_) {
794  if (iter->_bucket_)
795  iter->_index_ = _hash_func_(iter->_bucket_->key());
796  else {
797  iter->_next_bucket_ = nullptr;
798  iter->_index_ = 0;
799  }
800  }
801  }
802  }
803  }
804 
805  template < typename Key, typename Val, typename Alloc >
806  void HashTable< Key, Val, Alloc >::_insert_(HashTableBucket< Key, Val >* bucket) {
807  Size hash_key = _hash_func_(bucket->key());
808 
809  // check that there does not already exist an element with the same key
810  if (_key_uniqueness_policy_ && _nodes_[hash_key].exists(bucket->key())) {
811  // remove the bucket from memory
812  Key k = bucket->key();
813  _alloc_.destroy(bucket);
814  _alloc_.deallocate(bucket, 1);
815  GUM_ERROR(DuplicateElement,
816  "the hashtable contains an element with the same key (" << k << ")");
817  }
818 
819  // check whether there is sufficient space to insert the new pair
820  // if not, resize the current hashtable
821  if (_resize_policy_ && (_nb_elements_ >= _size_ * HashTableConst::default_mean_val_by_slot)) {
822  resize(_size_ << 1);
823  hash_key = _hash_func_(bucket->key());
824  }
825 
826  // add the new pair
827  _nodes_[hash_key].insert(bucket);
828  ++_nb_elements_;
829 
830  // recompute the index of the beginning of the hashtable if possible
831  // WARNING: if _begin_index_ = std::numeric_limits<Size>::max (), we CANNOT
832  // recompute the index because we cannot know whether the current index is
833  // equal to max because there was no element in the hashtable or whether a
834  // previous _erase_() has set the index to max.
835  if (_begin_index_ < hash_key) { _begin_index_ = hash_key; }
836  }
837 
838  template < typename Key, typename Val, typename Alloc >
839  INLINE typename HashTable< Key, Val, Alloc >::value_type&
840  HashTable< Key, Val, Alloc >::insert(const Key& thekey, const Val& theval) {
841  Bucket* bucket = _alloc_.allocate(1);
842 
843  try {
844  _alloc_.construct(bucket, thekey, theval);
845  } catch (...) {
846  _alloc_.deallocate(bucket, 1);
847  throw;
848  }
849 
850  _insert_(bucket);
851  return bucket->elt();
852  }
853 
854  template < typename Key, typename Val, typename Alloc >
855  INLINE typename HashTable< Key, Val, Alloc >::value_type&
856  HashTable< Key, Val, Alloc >::insert(Key&& thekey, Val&& theval) {
857  Bucket* bucket = _alloc_.allocate(1);
858 
859  try {
860  _alloc_.construct(bucket, std::move(thekey), std::move(theval));
861  } catch (...) {
862  _alloc_.deallocate(bucket, 1);
863  throw;
864  }
865 
866  _insert_(bucket);
867  return bucket->elt();
868  }
869 
870  template < typename Key, typename Val, typename Alloc >
871  INLINE typename HashTable< Key, Val, Alloc >::value_type&
872  HashTable< Key, Val, Alloc >::insert(const std::pair< Key, Val >& elt) {
873  Bucket* bucket = _alloc_.allocate(1);
874 
875  try {
876  _alloc_.construct(bucket, reinterpret_cast< const value_type& >(elt));
877  } catch (...) {
878  _alloc_.deallocate(bucket, 1);
879  throw;
880  }
881 
882  _insert_(bucket);
883  return bucket->elt();
884  }
885 
886  template < typename Key, typename Val, typename Alloc >
887  INLINE typename HashTable< Key, Val, Alloc >::value_type&
888  HashTable< Key, Val, Alloc >::insert(std::pair< Key, Val >&& elt) {
889  Bucket* bucket = _alloc_.allocate(1);
890 
891  try {
892  _alloc_.construct(bucket, std::move(reinterpret_cast< value_type& >(elt)));
893  } catch (...) {
894  _alloc_.deallocate(bucket, 1);
895  throw;
896  }
897 
898  _insert_(bucket);
899  return bucket->elt();
900  }
901 
902  template < typename Key, typename Val, typename Alloc >
903  template < typename... Args >
904  INLINE typename HashTable< Key, Val, Alloc >::value_type&
905  HashTable< Key, Val, Alloc >::emplace(Args&&... args) {
906  Bucket* bucket = _alloc_.allocate(1);
907 
908  try {
909  _alloc_.construct(bucket,
910  HashTableBucket< Key, Val >::Emplace::EMPLACE,
911  std::forward< Args >(args)...);
912  } catch (...) {
913  _alloc_.deallocate(bucket, 1);
914  throw;
915  }
916 
917  _insert_(bucket);
918  return bucket->elt();
919  }
920 
921  template < typename Key, typename Val, typename Alloc >
922  INLINE typename HashTable< Key, Val, Alloc >::mapped_type&
923  HashTable< Key, Val, Alloc >::getWithDefault(const Key& key, const Val& default_value) {
924  Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
925 
926  if (bucket == nullptr)
927  return insert(key, default_value).second;
928  else
929  return bucket->val();
930  }
931 
932  template < typename Key, typename Val, typename Alloc >
933  INLINE typename HashTable< Key, Val, Alloc >::mapped_type&
934  HashTable< Key, Val, Alloc >::getWithDefault(Key&& key, Val&& default_value) {
935  Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
936 
937  if (bucket == nullptr)
938  return insert(std::move(key), std::move(default_value)).second;
939  else
940  return bucket->val();
941  }
942 
943  template < typename Key, typename Val, typename Alloc >
944  INLINE void HashTable< Key, Val, Alloc >::set(const Key& key, const Val& value) {
945  Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
946 
947  if (bucket == nullptr)
948  insert(key, value);
949  else
950  bucket->val() = value;
951  }
952 
953  template < typename Key, typename Val, typename Alloc >
954  void HashTable< Key, Val, Alloc >::_erase_(HashTableBucket< Key, Val >* bucket, Size index) {
955  if (bucket == nullptr) return;
956 
957  // update the registered iterators pointing to this bucket
958  for (auto iter: _safe_iterators_) {
959  if (iter->_bucket_ == bucket) {
960  iter->operator++();
961  iter->_next_bucket_ = iter->_bucket_;
962  iter->_bucket_ = nullptr;
963  } else if (iter->_next_bucket_ == bucket) {
964  iter->_bucket_ = bucket;
965  iter->operator++();
966  iter->_next_bucket_ = iter->_bucket_;
967  iter->_bucket_ = nullptr;
968  }
969  }
970 
971  // remove the element from the _nodes_ vector
972  _nodes_[index].erase(bucket);
973 
974  --_nb_elements_;
975 
976  if ((index == _begin_index_) && _nodes_[index].empty()) {
977  _begin_index_ = std::numeric_limits< Size >::max();
978  }
979  }
980 
981  template < typename Key, typename Val, typename Alloc >
982  INLINE void HashTable< Key, Val, Alloc >::erase(const Key& key) {
983  // get the hashed key
984  Size hash = _hash_func_(key);
985 
986  // get the bucket containing the element to erase
987  HashTableBucket< Key, Val >* bucket = _nodes_[hash].bucket(key);
988 
989  _erase_(bucket, hash);
990  }
991 
992  template < typename Key, typename Val, typename Alloc >
993  INLINE void HashTable< Key, Val, Alloc >::erase(const iterator_safe& iter) {
994  _erase_(iter._getBucket_(), iter._getIndex_());
995  }
996 
997  template < typename Key, typename Val, typename Alloc >
998  INLINE void HashTable< Key, Val, Alloc >::erase(const const_iterator_safe& iter) {
999  _erase_(iter._getBucket_(), iter._getIndex_());
1000  }
1001 
1002  template < typename Key, typename Val, typename Alloc >
1003  INLINE void HashTable< Key, Val, Alloc >::eraseByVal(const Val& val) {
1004  for (auto iter = cbegin(); iter != cend(); ++iter)
1005  if (iter._bucket_->val() == val) {
1006  _erase_(iter._getBucket_(), iter._getIndex_());
1007  return;
1008  }
1009  }
1010 
1011  template < typename Key, typename Val, typename Alloc >
1012  INLINE void HashTable< Key, Val, Alloc >::reset(const Key& key) {
1013  erase(key);
1014  }
1015 
1016  template < typename Key, typename Val, typename Alloc >
1017  INLINE const Key& HashTable< Key, Val, Alloc >::keyByVal(const Val& val) const {
1018  for (auto iter = begin(); iter != end(); ++iter)
1019  if (iter._bucket_->val() == val) return iter.key();
1020 
1021  GUM_ERROR(NotFound, "not enough elements in the chained list")
1022  }
1023 
1024  template < typename Key, typename Val, typename Alloc >
1025  INLINE const Key& HashTable< Key, Val, Alloc >::key(const Key& key) const {
1026  // get the bucket corresponding to the key
1027  Bucket* bucket = _nodes_[_hash_func_(key)].bucket(key);
1028 
1029  if (bucket == nullptr) { GUM_ERROR(NotFound, "key does not belong to the hashtable") }
1030 
1031  return bucket->key();
1032  }
1033 
1034  template < typename Key, typename Val, typename Alloc >
1035  void HashTable< Key, Val, Alloc >::eraseAllVal(const Val& val) {
1036  for (auto iterAll = cbeginSafe(); iterAll != cendSafe(); ++iterAll) {
1037  if (iterAll._bucket_->val() == val) { _erase_(iterAll._bucket_, iterAll._index_); }
1038  }
1039  }
1040 
1041  template < typename Key, typename Val, typename Alloc >
1042  INLINE bool HashTable< Key, Val, Alloc >::empty() const noexcept {
1043  return (_nb_elements_ == Size(0));
1044  }
1045 
1046  template < typename Key, typename Val, typename Alloc >
1047  template < typename Mount, typename OtherAlloc >
1048  HashTable< Key, Mount, OtherAlloc >
1049  INLINE HashTable< Key, Val, Alloc >::map(Mount (*f)(Val),
1050  Size size,
1051  bool resize_pol,
1052  bool key_uniqueness_pol) const {
1053  // determine the proper size of the hashtable
1054  // by default, the size of the table is set so that the table does not take
1055  // too much space while allowing to add a few elements without needing to
1056  // resize in autmatic resizing mode
1057  if (size == 0) size = std::max(Size(2), _nb_elements_ / 2);
1058 
1059  // create a new table
1060  HashTable< Key, Mount, OtherAlloc > table(size, resize_pol, key_uniqueness_pol);
1061 
1062  // fill the new hash table
1063  for (auto iter = begin(); iter != end(); ++iter) {
1064  table.insert(iter.key(), f(iter.val()));
1065  }
1066 
1067  return table;
1068  }
1069 
1070  template < typename Key, typename Val, typename Alloc >
1071  template < typename Mount, typename OtherAlloc >
1072  HashTable< Key, Mount, OtherAlloc >
1073  INLINE HashTable< Key, Val, Alloc >::map(Mount (*f)(Val&),
1074  Size size,
1075  bool resize_pol,
1076  bool key_uniqueness_pol) const {
1077  // determine the proper size of the hashtable
1078  // by default, the size of the table is set so that the table does not take
1079  // too much space while allowing to add a few elements without needing to
1080  // resize in autmatic resizing mode
1081  if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
1082 
1083  // create a new table
1084  HashTable< Key, Mount, OtherAlloc > table(size, resize_pol, key_uniqueness_pol);
1085 
1086  // fill the new hash table
1087  for (auto iter = begin(); iter != end(); ++iter) {
1088  table.insert(iter.key(), f(const_cast< Val& >(iter.val())));
1089  }
1090 
1091  return table;
1092  }
1093 
1094  template < typename Key, typename Val, typename Alloc >
1095  template < typename Mount, typename OtherAlloc >
1096  HashTable< Key, Mount, OtherAlloc >
1097  INLINE HashTable< Key, Val, Alloc >::map(Mount (*f)(const Val&),
1098  Size size,
1099  bool resize_pol,
1100  bool key_uniqueness_pol) const {
1101  // determine the proper size of the hashtable
1102  // by default, the size of the table is set so that the table does not take
1103  // too much space while allowing to add a few elements without needing to
1104  // resize in autmatic resizing mode
1105  if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
1106 
1107  // create a new table
1108  HashTable< Key, Mount, OtherAlloc > table(size, resize_pol, key_uniqueness_pol);
1109 
1110  // fill the new hash table
1111  for (auto iter = begin(); iter != end(); ++iter) {
1112  table.insert(iter.key(), f(iter.val()));
1113  }
1114 
1115  return table;
1116  }
1117 
1118  template < typename Key, typename Val, typename Alloc >
1119  template < typename Mount, typename OtherAlloc >
1120  HashTable< Key, Mount, OtherAlloc >
1121  INLINE HashTable< Key, Val, Alloc >::map(const Mount& val,
1122  Size size,
1123  bool resize_pol,
1124  bool key_uniqueness_pol) const {
1125  // determine the proper size of the hashtable
1126  // by default, the size of the table is set so that the table does not take
1127  // too much space while allowing to add a few elements without needing to
1128  // resize in autmatic resizing mode
1129  if (size == Size(0)) size = std::max(Size(2), _nb_elements_ / 2);
1130 
1131  // create a new table
1132  HashTable< Key, Mount, OtherAlloc > table(size, resize_pol, key_uniqueness_pol);
1133 
1134  // fill the new hash table
1135  for (auto iter = begin(); iter != end(); ++iter) {
1136  table.insert(iter.key(), val);
1137  }
1138 
1139  return table;
1140  }
1141 
1142  template < typename Key, typename Val, typename Alloc >
1143  template < typename OtherAlloc >
1144  bool
1145  HashTable< Key, Val, Alloc >::operator==(const HashTable< Key, Val, OtherAlloc >& from) const {
1146  // checks whether the two hashtables contain the same number of elements
1147  if (from._nb_elements_ != _nb_elements_) return false;
1148 
1149  // parse this and check that each element also belongs to from
1150  for (auto iter = begin(); iter != end(); ++iter) {
1151  try {
1152  if (iter.val() != from[iter.key()]) return false;
1153  } catch (NotFound&) { return false; }
1154  }
1155 
1156  return true;
1157  }
1158 
1159  template < typename Key, typename Val, typename Alloc >
1160  template < typename OtherAlloc >
1161  INLINE bool
1162  HashTable< Key, Val, Alloc >::operator!=(const HashTable< Key, Val, OtherAlloc >& from) const {
1163  return !operator==(from);
1164  }
1165 
1166  template < typename Key, typename Val, typename Alloc >
1167  std::ostream& operator<<(std::ostream& stream, const HashTableList< Key, Val, Alloc >& list) {
1168  bool deja = false;
1169  stream << "[";
1170 
1171  for (HashTableBucket< Key, Val >* ptr = list._deb_list_; ptr;
1172  ptr = ptr->list.next, deja = true) {
1173  if (deja) stream << " , ";
1174 
1175  stream << ptr->key() << "=>" << ptr->val();
1176  }
1177 
1178  stream << "]";
1179 
1180  return stream;
1181  }
1182 
1183  template < typename Key, typename Val, typename Alloc >
1184  std::ostream& operator<<(std::ostream& stream, const HashTableList< Key*, Val, Alloc >& list) {
1185  bool deja = false;
1186  stream << "[";
1187 
1188  for (HashTableBucket< Key, Val >* ptr = list._deb_list_; ptr;
1189  ptr = ptr->list.next, deja = true) {
1190  if (deja) stream << " , ";
1191 
1192  stream << ptr->key() << "=>" << ptr->val();
1193  }
1194 
1195  stream << "]";
1196 
1197  return stream;
1198  }
1199 
1200  template < typename Key, typename Val, typename Alloc >
1201  std::ostream& operator<<(std::ostream& stream, const HashTable< Key, Val, Alloc >& table) {
1202  bool deja = false;
1203  stream << "{";
1204 
1205  for (Size i = Size(0); i < table._size_; ++i)
1206  for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
1207  if (deja) stream << " , ";
1208 
1209  stream << ptr->key() << "=>" << ptr->val();
1210 
1211  deja = true;
1212  }
1213 
1214  stream << "}";
1215 
1216  return stream;
1217  }
1218 
1219  template < typename Key, typename Val, typename Alloc >
1220  std::ostream& operator<<(std::ostream& stream, const HashTable< Key*, Val, Alloc >& table) {
1221  bool deja = false;
1222  stream << "{";
1223 
1224  for (Size i = Size(0); i < table._size_; ++i)
1225  for (auto ptr = table._nodes_[i]._deb_list_; ptr; ptr = ptr->next) {
1226  if (deja) stream << " , ";
1227 
1228  stream << ptr->key() << "=>" << ptr->val();
1229 
1230  deja = true;
1231  }
1232 
1233  stream << "}";
1234 
1235  return stream;
1236  }
1237 
1238  // ===========================================================================
1239  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1240  // ===========================================================================
1241 
1242  template < typename Key, typename Val >
1243  INLINE void HashTableConstIteratorSafe< Key, Val >::_insertIntoSafeList_() const {
1244  _table_->_safe_iterators_.push_back(
1245  const_cast< HashTableConstIteratorSafe< Key, Val >* >(this));
1246  }
1247 
1248  template < typename Key, typename Val >
1249  INLINE void HashTableConstIteratorSafe< Key, Val >::_removeFromSafeList_() const {
1250  if (_table_ == nullptr) return;
1251 
1252  // find where the iterator is
1253  std::vector< HashTableConstIteratorSafe< Key, Val >* >& iter_vect = _table_->_safe_iterators_;
1254 
1255  auto len = iter_vect.size();
1256  for (Size i = Size(0); i < len; ++i) {
1257  if (iter_vect[i] == this) {
1258  iter_vect.erase(iter_vect.begin() + i);
1259  break;
1260  }
1261  }
1262  }
1263 
1264  template < typename Key, typename Val >
1265  INLINE HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe() {
1266  // for debugging purposes
1267  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1268  }
1269 
1270  template < typename Key, typename Val >
1271  template < typename Alloc >
1272  INLINE HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(
1273  const HashTable< Key, Val, Alloc >& tab) :
1274  _table_{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1275  // for debugging purposes
1276  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1277 
1278  // make the hashtable keep track of this iterator
1279  _insertIntoSafeList_();
1280 
1281  if (_table_->_nb_elements_) {
1282  if (_table_->_begin_index_ != std::numeric_limits< Size >::max()) {
1283  _index_ = _table_->_begin_index_;
1284  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1285  } else {
1286  // find the element we shall point to from the start of the hashtable
1287  for (Size i = _table_->_size_ - Size(1);; --i) { // no test on i since
1288  // _nb_elements_ != 0
1289  if (_table_->_nodes_[i]._nb_elements_) {
1290  _index_ = i;
1291  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1292  _table_->_begin_index_ = _index_;
1293  break;
1294  }
1295  }
1296  }
1297  }
1298  }
1299 
1300  template < typename Key, typename Val >
1301  template < typename Alloc >
1302  HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(
1303  const HashTable< Key, Val, Alloc >& tab,
1304  Size ind_elt) :
1305  _table_{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1306  Size i;
1307 
1308  // check if we are looking for a begin() and we know for sure its index
1309  if ((ind_elt == Size(0)) && (_table_->_begin_index_ != std::numeric_limits< Size >::max())) {
1310  _index_ = _table_->_begin_index_;
1311  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1312  } else {
1313  // check if it is faster to find the ind_eltth element from the start or
1314  // from the end of the hashtable
1315  if (ind_elt < (_table_->_nb_elements_ >> 1)) {
1316  // find the element we shall point to from the start of the hashtable
1317  for (i = _table_->_size_ - 1;; --i) { // no test on i since
1318  // ind_elt < table_-> _nb_elements_
1319  if (_table_->_nodes_[i]._nb_elements_) {
1320  if (ind_elt >= _table_->_nodes_[i]._nb_elements_)
1321  ind_elt -= _table_->_nodes_[i]._nb_elements_;
1322  else {
1323  for (_bucket_ = _table_->_nodes_[i]._end_list_; ind_elt;
1324  --ind_elt, _bucket_ = _bucket_->prev) {}
1325 
1326  _index_ = i;
1327  break;
1328  }
1329  }
1330  }
1331  } else {
1332  // ind_elt = the index of the element we should point to
1333  // check if the index passed as parameter is valid
1334  if (ind_elt >= _table_->_nb_elements_) {
1335  GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the hashtable")
1336  }
1337 
1338  // find the element we shall point to from the end of the hashtable
1339  for (i = 0, ind_elt = _table_->_nb_elements_ - ind_elt - 1;; ++i) {
1340  if (_table_->_nodes_[i]._nb_elements_) {
1341  if (ind_elt >= _table_->_nodes_[i]._nb_elements_)
1342  ind_elt -= _table_->_nodes_[i]._nb_elements_;
1343  else {
1344  for (_bucket_ = _table_->_nodes_[i]._deb_list_; ind_elt;
1345  --ind_elt, _bucket_ = _bucket_->next) {}
1346 
1347  _index_ = i;
1348  break;
1349  }
1350  }
1351  }
1352  }
1353  }
1354 
1355  // for debugging purposes
1356  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1357 
1358  // make the hashtable keep track of this iterator
1359  _insertIntoSafeList_();
1360  }
1361 
1362  template < typename Key, typename Val >
1363  INLINE HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(
1364  const HashTableConstIteratorSafe< Key, Val >& from) :
1365  _table_{from._table_},
1366  _index_{from._index_}, _bucket_{from._bucket_}, _next_bucket_{from._next_bucket_} {
1367  // make the hashtable keep track of this iterator
1368  if (_table_ != nullptr) { _insertIntoSafeList_(); }
1369 
1370  // for debugging purposes
1371  GUM_CONS_CPY(HashTableConstIteratorSafe);
1372  }
1373 
1374  template < typename Key, typename Val >
1375  INLINE HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(
1376  const HashTableConstIterator< Key, Val >& from) :
1377  _table_{from._table_},
1378  _index_{from._index_}, _bucket_{from._bucket_} {
1379  // make the hashtable keep track of this iterator
1380  if (_table_ != nullptr) { _insertIntoSafeList_(); }
1381 
1382  // for debugging purposes
1383  GUM_CONS_CPY(HashTableConstIteratorSafe);
1384  }
1385 
1386  template < typename Key, typename Val >
1387  INLINE HashTableConstIteratorSafe< Key, Val >::HashTableConstIteratorSafe(
1388  HashTableConstIteratorSafe< Key, Val >&& from) :
1389  _table_{from._table_},
1390  _index_{from._index_}, _bucket_{from._bucket_}, _next_bucket_{from._next_bucket_} {
1391  GUM_CONS_MOV(HashTableConstIteratorSafe);
1392 
1393  // find "from" in the hashtable's list of safe iterators and substitute
1394  // it by this
1395  if (_table_ != nullptr) {
1396  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect = _table_->_safe_iterators_;
1397 
1398  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1399  if (*ptr == &from) {
1400  *ptr = this;
1401  from._table_ = nullptr;
1402  break;
1403  }
1404  }
1405  }
1406  }
1407 
1408  template < typename Key, typename Val >
1409  INLINE HashTableConstIteratorSafe< Key, Val >::~HashTableConstIteratorSafe() noexcept {
1410  // for debugging purposes
1411  GUM_DESTRUCTOR(HashTableConstIteratorSafe);
1412 
1413  // remove the iterator from the table's iterator list
1414  _removeFromSafeList_();
1415  }
1416 
1417  template < typename Key, typename Val >
1418  HashTableConstIteratorSafe< Key, Val >& HashTableConstIteratorSafe< Key, Val >::operator=(
1419  const HashTableConstIteratorSafe< Key, Val >& from) {
1420  // here, no need to avoid self assignment: this would slow down normal
1421  // assignments and, in any case, this would not result in an iterator in
1422  // an incoherent state
1423  // check if the current hashtable is different from that of "from". In such
1424  // a case, we shall remove the iterator from its current hashtable
1425  // iterator's
1426  // list and add it to the new hashtable iterator's list
1427  if (_table_ != from._table_) {
1428  // remove the iterator from its hashtable iterator's list'
1429  _removeFromSafeList_();
1430 
1431  _table_ = from._table_;
1432 
1433  // add to the new table
1434  if (_table_) { _insertIntoSafeList_(); }
1435  }
1436 
1437  _index_ = from._index_;
1438  _bucket_ = from._bucket_;
1439  _next_bucket_ = from._next_bucket_;
1440 
1441  return *this;
1442  }
1443 
1444  template < typename Key, typename Val >
1445  HashTableConstIteratorSafe< Key, Val >& HashTableConstIteratorSafe< Key, Val >::operator=(
1446  const HashTableConstIterator< Key, Val >& from) {
1447  // here, no need to avoid self assignment: this would slow down normal
1448  // assignments and, in any case, this would not result in an iterator in
1449  // an incoherent state
1450  // check if the current hashtable is different from that of "from". In such
1451  // a case, we shall remove the iterator from its current hashtable
1452  // iterator's
1453  // list and add it to the new hashtable iterator's list
1454  if (_table_ != from._table_) {
1455  // remove the iterator from its hashtable iterator's list'
1456  _removeFromSafeList_();
1457 
1458  _table_ = from._table_;
1459 
1460  // add to the new table
1461  if (_table_) { _insertIntoSafeList_(); }
1462  }
1463 
1464  _index_ = from._index_;
1465  _bucket_ = from._bucket_;
1466  _next_bucket_ = nullptr;
1467 
1468  return *this;
1469  }
1470 
1471  template < typename Key, typename Val >
1472  INLINE HashTableConstIteratorSafe< Key, Val >& HashTableConstIteratorSafe< Key, Val >::operator=(
1473  HashTableConstIteratorSafe< Key, Val >&& from) noexcept {
1474  // here, no need to avoid self assignment: this would slow down normal
1475  // assignments and, in any case, this would not result in an iterator in
1476  // an incoherent state
1477  // check if the current hashtable is different from that of "from". In such
1478  // a case, we shall remove the iterator from its current hashtable
1479  // iterator's
1480  // list and add it to the new hashtable iterator's list
1481  if (_table_ != from._table_) {
1482  // remove the iterator from its hashtable iterator's list'
1483  _removeFromSafeList_();
1484 
1485  if (from._table_ != nullptr) {
1486  // substitute from by this in the list of safe iterators
1487  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect
1488  = from._table_->_safe_iterators_;
1489 
1490  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1491  if (*ptr == &from) {
1492  *ptr = this;
1493  break;
1494  }
1495  }
1496  }
1497 
1498  _table_ = from._table_;
1499  from._table_ = nullptr;
1500  }
1501 
1502  _index_ = from._index_;
1503  _bucket_ = from._bucket_;
1504  _next_bucket_ = from._next_bucket_;
1505 
1506  return *this;
1507  }
1508 
1509  template < typename Key, typename Val >
1510  INLINE const typename HashTableConstIteratorSafe< Key, Val >::key_type&
1511  HashTableConstIteratorSafe< Key, Val >::key() const {
1512  if (_bucket_ != nullptr)
1513  return _bucket_->key();
1514  else {
1515  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
1516  }
1517  }
1518 
1519  template < typename Key, typename Val >
1520  INLINE const typename HashTableConstIteratorSafe< Key, Val >::mapped_type&
1521  HashTableConstIteratorSafe< Key, Val >::val() const {
1522  if (_bucket_ != nullptr)
1523  return _bucket_->val();
1524  else {
1525  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
1526  }
1527  }
1528 
1529  template < typename Key, typename Val >
1530  INLINE void HashTableConstIteratorSafe< Key, Val >::clear() noexcept {
1531  // remove the iterator from the table's iterator list
1532  _removeFromSafeList_();
1533 
1534  // set its table as well as the element it points to to 0
1535  _table_ = nullptr;
1536  _bucket_ = nullptr;
1537  _next_bucket_ = nullptr;
1538  _index_ = Size(0);
1539  }
1540 
1541  // WARNING: never inline this function: this result in g++4.3.3 producing a
1542  // code that segfaults.
1543  template < typename Key, typename Val >
1544  HashTableConstIteratorSafe< Key, Val >&
1545  HashTableConstIteratorSafe< Key, Val >::operator++() noexcept {
1546  // if _bucket_ != nullptr then use it, else use next_bucket
1547  if (_bucket_ == nullptr) {
1548  // note that this case only happens when the iterator pointed to an
1549  // element
1550  // that has just been erased. Fortunately, in this case, the Hashtable's
1551  // erase functions update appropriately the _next_bucket_ and _index_
1552  // fields.
1553  _bucket_ = _next_bucket_;
1554  _next_bucket_ = nullptr;
1555  } else {
1556  // ok, here we can use _bucket_ as a starting point
1557 
1558  // if we are not pointing on the first element of the chained list, just
1559  // point to the preceding bucket in this list
1560  if (_bucket_->prev) {
1561  _bucket_ = _bucket_->prev;
1562  // here, no need to update _next_bucket_, which is compulsorily
1563  // equal to nullptr, nor _index_ which has not changed.
1564  } else {
1565  // ok, here we are on the beginning of a chained list,
1566  // so 2 cases can obtain:
1567  // 1/ index = 0 : then we have reached the end of the hashtable
1568  // 2/ index != 0 => we must search for a new slot containing elements
1569 
1570  // case 1:
1571  if (_index_ == Size(0)) {
1572  _bucket_ = nullptr;
1573  // we are thus at the end() of the hashTable
1574  }
1575  // case 2:
1576  else {
1577  // arrived here, we need to parse the hash table until we find a new
1578  // bucket because we are pointing on a chained list with no more
1579  // element
1580  // to the left of the current element
1581  if (_index_ > Size(0)) {
1582  for (Size i = _index_ - Size(1); i > Size(0); --i) {
1583  if (_table_->_nodes_[i]._nb_elements_) {
1584  _index_ = i;
1585  _bucket_ = _table_->_nodes_[i]._end_list_;
1586  return *this;
1587  }
1588  }
1589  }
1590 
1591  if (_table_->_nodes_[0]._nb_elements_)
1592  _bucket_ = _table_->_nodes_[0]._end_list_;
1593  else
1594  _bucket_ = nullptr;
1595 
1596  _index_ = 0;
1597  }
1598  }
1599  }
1600 
1601  return *this;
1602  }
1603 
1604  template < typename Key, typename Val >
1605  HashTableConstIteratorSafe< Key, Val >&
1606  HashTableConstIteratorSafe< Key, Val >::operator+=(Size nb) noexcept {
1607  if ((nb == Size(0)) || (_table_ == nullptr)) return *this;
1608 
1609  // if _bucket_ != nullptr then use it, else use next_bucket
1610  if (_bucket_ == nullptr) {
1611  // note that this case only happens when the iterator pointed to an
1612  // element
1613  // that has just been erased. Fortunately, in this case, the Hashtable's
1614  // erase functions update appropriately the _next_bucket_ and _index_
1615  // fields.
1616  _bucket_ = _next_bucket_;
1617  _next_bucket_ = nullptr;
1618  --nb;
1619  }
1620 
1621  // ok, here we can use _bucket_ as a starting point: parse all the elements
1622  // of the current chained list
1623  for (; nb && _bucket_ != nullptr; --nb, _bucket_ = _bucket_->prev) {}
1624 
1625  if (_bucket_ != nullptr) return *this;
1626 
1627  // here, we shall skip all the chained list that have not sufficiently
1628  // many elements
1629  --_index_;
1630 
1631  for (; _index_ < _table_->_size_ && nb >= _table_->_nodes_[_index_]._nb_elements_;
1632  nb -= _table_->_nodes_[_index_]._nb_elements_, --_index_) {}
1633 
1634  // here: either _index_ >= _table_-> _size_, which means that we did not find
1635  // the element we looked for, i.e., we are at the end of the hashtable, or
1636  // nb < _table_-> _nodes_[ _index_]. _nb_elements_, and we should parse the
1637  // chained list to get the element (which, we know for sure, exists)
1638  if (_index_ >= _table_->_size_) {
1639  _index_ = Size(0);
1640  return *this;
1641  }
1642 
1643  for (_bucket_ = _table_->_nodes_[_index_]._end_list_; nb; --nb, _bucket_ = _bucket_->prev) {}
1644 
1645  return *this;
1646  }
1647 
1648  template < typename Key, typename Val >
1649  INLINE HashTableConstIteratorSafe< Key, Val >
1650  HashTableConstIteratorSafe< Key, Val >::operator+(Size nb) const {
1651  return HashTableConstIteratorSafe< Key, Val >{*this} += nb;
1652  }
1653 
1654  template < typename Key, typename Val >
1655  INLINE bool HashTableConstIteratorSafe< Key, Val >::operator!=(
1656  const HashTableConstIteratorSafe< Key, Val >& from) const noexcept {
1657  return ((_bucket_ != from._bucket_) || (_index_ != from._index_));
1658  }
1659 
1660  template < typename Key, typename Val >
1661  INLINE bool HashTableConstIteratorSafe< Key, Val >::operator==(
1662  const HashTableConstIteratorSafe< Key, Val >& from) const noexcept {
1663  return ((_bucket_ == from._bucket_) && (_index_ == from._index_));
1664  }
1665 
1666  template < typename Key, typename Val >
1667  INLINE const typename HashTableConstIteratorSafe< Key, Val >::value_type&
1668  HashTableConstIteratorSafe< Key, Val >::operator*() const {
1669  if (_bucket_)
1670  return _bucket_->elt();
1671  else {
1672  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
1673  }
1674  }
1675 
1676  template < typename Key, typename Val >
1677  INLINE HashTableBucket< Key, Val >*
1678  HashTableConstIteratorSafe< Key, Val >::_getBucket_() const noexcept {
1679  return _bucket_;
1680  }
1681 
1682  template < typename Key, typename Val >
1683  INLINE Size HashTableConstIteratorSafe< Key, Val >::_getIndex_() const noexcept {
1684  return _index_;
1685  }
1686 
1687  // ===========================================================================
1688  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1689  // ===========================================================================
1690 
1691  template < typename Key, typename Val >
1692  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe() :
1693  HashTableConstIteratorSafe< Key, Val >() {
1694  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1695  }
1696 
1697  template < typename Key, typename Val >
1698  template < typename Alloc >
1699  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe(
1700  const HashTable< Key, Val, Alloc >& tab) :
1701  HashTableConstIteratorSafe< Key, Val >(tab) {
1702  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1703  }
1704 
1705  template < typename Key, typename Val >
1706  template < typename Alloc >
1707  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe(
1708  const HashTable< Key, Val, Alloc >& tab,
1709  Size ind_elt) :
1710  HashTableConstIteratorSafe< Key, Val >(tab, ind_elt) {
1711  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1712  }
1713 
1714  template < typename Key, typename Val >
1715  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe(
1716  const HashTableIteratorSafe< Key, Val >& from) :
1717  HashTableConstIteratorSafe< Key, Val >(from) {
1718  GUM_CONS_CPY(HashTableIteratorSafe);
1719  }
1720 
1721  template < typename Key, typename Val >
1722  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe(
1723  const HashTableIterator< Key, Val >& from) :
1724  HashTableConstIteratorSafe< Key, Val >(from) {
1725  GUM_CONS_CPY(HashTableIteratorSafe);
1726  }
1727 
1728  template < typename Key, typename Val >
1729  INLINE HashTableIteratorSafe< Key, Val >::HashTableIteratorSafe(
1730  HashTableIteratorSafe< Key, Val >&& from) noexcept :
1731  HashTableConstIteratorSafe< Key, Val >(std::move(from)) {
1732  GUM_CONS_MOV(HashTableIteratorSafe);
1733  }
1734 
1735  template < typename Key, typename Val >
1736  INLINE HashTableIteratorSafe< Key, Val >::~HashTableIteratorSafe() noexcept {
1737  GUM_DESTRUCTOR(HashTableIteratorSafe);
1738  }
1739 
1740  template < typename Key, typename Val >
1741  INLINE typename HashTableIteratorSafe< Key, Val >::mapped_type&
1742  HashTableIteratorSafe< Key, Val >::val() {
1743  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::val());
1744  }
1745 
1746  template < typename Key, typename Val >
1747  INLINE HashTableIteratorSafe< Key, Val >&
1748  HashTableIteratorSafe< Key, Val >::operator=(const HashTableIteratorSafe< Key, Val >& from) {
1749  GUM_OP_CPY(HashTableIteratorSafe);
1750  HashTableConstIteratorSafe< Key, Val >::operator=(from);
1751  return *this;
1752  }
1753 
1754  template < typename Key, typename Val >
1755  INLINE HashTableIteratorSafe< Key, Val >&
1756  HashTableIteratorSafe< Key, Val >::operator=(const HashTableIterator< Key, Val >& from) {
1757  GUM_OP_CPY(HashTableIteratorSafe);
1758  HashTableConstIteratorSafe< Key, Val >::operator=(from);
1759  return *this;
1760  }
1761 
1762  template < typename Key, typename Val >
1763  INLINE HashTableIteratorSafe< Key, Val >& HashTableIteratorSafe< Key, Val >::operator=(
1764  HashTableIteratorSafe< Key, Val >&& from) noexcept {
1765  HashTableConstIteratorSafe< Key, Val >::operator=(std::move(from));
1766  return *this;
1767  }
1768 
1769  template < typename Key, typename Val >
1770  INLINE HashTableIteratorSafe< Key, Val >&
1771  HashTableIteratorSafe< Key, Val >::operator++() noexcept {
1772  HashTableConstIteratorSafe< Key, Val >::operator++();
1773  return *this;
1774  }
1775 
1776  template < typename Key, typename Val >
1777  INLINE HashTableIteratorSafe< Key, Val >&
1778  HashTableIteratorSafe< Key, Val >::operator+=(Size nb) noexcept {
1779  HashTableConstIteratorSafe< Key, Val >::operator+=(nb);
1780  return *this;
1781  }
1782 
1783  template < typename Key, typename Val >
1784  INLINE HashTableIteratorSafe< Key, Val >
1785  HashTableIteratorSafe< Key, Val >::operator+(Size nb) const {
1786  HashTableIteratorSafe< Key, Val > iter{*this};
1787  iter += nb;
1788  return iter;
1789  }
1790 
1791  template < typename Key, typename Val >
1792  INLINE bool HashTableIteratorSafe< Key, Val >::operator!=(
1793  const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1794  return HashTableConstIteratorSafe< Key, Val >::operator!=(from);
1795  }
1796 
1797  template < typename Key, typename Val >
1798  INLINE bool HashTableIteratorSafe< Key, Val >::operator==(
1799  const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1800  return HashTableConstIteratorSafe< Key, Val >::operator==(from);
1801  }
1802 
1803  template < typename Key, typename Val >
1804  INLINE typename HashTableIteratorSafe< Key, Val >::value_type&
1805  HashTableIteratorSafe< Key, Val >::operator*() {
1806  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::operator*());
1807  }
1808 
1809  template < typename Key, typename Val >
1810  INLINE const typename HashTableIteratorSafe< Key, Val >::value_type&
1811  HashTableIteratorSafe< Key, Val >::operator*() const {
1812  return HashTableConstIteratorSafe< Key, Val >::operator*();
1813  }
1814 
1815  // ===========================================================================
1816  // === UNSAFE HASH TABLE CONST ITERATORS IMPLEMENTATION ===
1817  // ===========================================================================
1818 
1819  template < typename Key, typename Val >
1820  INLINE HashTableConstIterator< Key, Val >::HashTableConstIterator() noexcept {
1821  GUM_CONSTRUCTOR(HashTableConstIterator);
1822  }
1823 
1824  template < typename Key, typename Val >
1825  template < typename Alloc >
1826  INLINE HashTableConstIterator< Key, Val >::HashTableConstIterator(
1827  const HashTable< Key, Val, Alloc >& tab) noexcept :
1828  _table_{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1829  // for debugging purposes
1830  GUM_CONSTRUCTOR(HashTableConstIterator);
1831 
1832  if (_table_->_nb_elements_) {
1833  if (_table_->_begin_index_ != std::numeric_limits< Size >::max()) {
1834  _index_ = _table_->_begin_index_;
1835  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1836  } else {
1837  // find the element we shall point to from the start of the hashtable
1838  for (Size i = _table_->_size_ - Size(1);; --i) { // no test on i since
1839  // _nb_elements_ != 0
1840  if (_table_->_nodes_[i]._nb_elements_) {
1841  _index_ = i;
1842  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1843  _table_->_begin_index_ = _index_;
1844  break;
1845  }
1846  }
1847  }
1848  }
1849  }
1850 
1851  template < typename Key, typename Val >
1852  template < typename Alloc >
1853  HashTableConstIterator< Key, Val >::HashTableConstIterator(
1854  const HashTable< Key, Val, Alloc >& tab,
1855  Size ind_elt) :
1856  _table_{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1857  Size i;
1858 
1859  // check if we are looking for a begin() and we know for sure its index
1860  if ((ind_elt == Size(0)) && (_table_->_begin_index_ != std::numeric_limits< Size >::max())) {
1861  _index_ = _table_->_begin_index_;
1862  _bucket_ = _table_->_nodes_[_index_]._end_list_;
1863  } else {
1864  // check if it is faster to find the ind_eltth element from the start or
1865  // from the end of the hashtable
1866  if (ind_elt < (_table_->_nb_elements_ >> 1)) {
1867  // find the element we shall point to from the start of the hashtable
1868  for (i = _table_->_size_ - 1;; --i) { // no test on i since
1869  // ind_elt < table_-> _nb_elements_
1870  if (_table_->_nodes_[i]._nb_elements_) {
1871  if (ind_elt >= _table_->_nodes_[i]._nb_elements_)
1872  ind_elt -= _table_->_nodes_[i]._nb_elements_;
1873  else {
1874  for (_bucket_ = _table_->_nodes_[i]._end_list_; ind_elt;
1875  --ind_elt, _bucket_ = _bucket_->prev) {}
1876 
1877  _index_ = i;
1878  break;
1879  }
1880  }
1881  }
1882  } else {
1883  // ind_elt = the index of the element we should point to
1884  // check if the index passed as parameter is valid
1885  if (ind_elt >= _table_->_nb_elements_) {
1886  GUM_ERROR(UndefinedIteratorValue, "Not enough elements in the hashtable")
1887  }
1888 
1889  // find the element we shall point to from the end of the hashtable
1890  for (i = 0, ind_elt = _table_->_nb_elements_ - ind_elt - 1;; ++i) {
1891  if (_table_->_nodes_[i]._nb_elements_) {
1892  if (ind_elt >= _table_->_nodes_[i]._nb_elements_)
1893  ind_elt -= _table_->_nodes_[i]._nb_elements_;
1894  else {
1895  for (_bucket_ = _table_->_nodes_[i]._deb_list_; ind_elt;
1896  --ind_elt, _bucket_ = _bucket_->next) {}
1897 
1898  _index_ = i;
1899  break;
1900  }
1901  }
1902  }
1903  }
1904  }
1905 
1906  // for debugging purposes
1907  GUM_CONSTRUCTOR(HashTableConstIterator);
1908  }
1909 
1910  template < typename Key, typename Val >
1911  INLINE HashTableConstIterator< Key, Val >::HashTableConstIterator(
1912  const HashTableConstIterator< Key, Val >& from) noexcept :
1913  _table_{from._table_},
1914  _index_{from._index_}, _bucket_{from._bucket_} {
1915  GUM_CONS_CPY(HashTableConstIterator);
1916  }
1917 
1918  template < typename Key, typename Val >
1919  INLINE HashTableConstIterator< Key, Val >::HashTableConstIterator(
1920  HashTableConstIterator< Key, Val >&& from) noexcept :
1921  _table_{from._table_},
1922  _index_{from._index_}, _bucket_{from._bucket_} {
1923  GUM_CONS_MOV(HashTableConstIterator);
1924  }
1925 
1926  template < typename Key, typename Val >
1927  INLINE HashTableConstIterator< Key, Val >::~HashTableConstIterator() noexcept {
1928  // for debugging purposes
1929  GUM_DESTRUCTOR(HashTableConstIterator);
1930  }
1931 
1932  template < typename Key, typename Val >
1933  INLINE HashTableConstIterator< Key, Val >& HashTableConstIterator< Key, Val >::operator=(
1934  const HashTableConstIterator< Key, Val >& from) noexcept {
1935  // here, no need to avoid self assignment: this would slow down normal
1936  // assignments and, in any case, this would not result in an iterator in
1937  // an incoherent state
1938  _table_ = from._table_;
1939  _index_ = from._index_;
1940  _bucket_ = from._bucket_;
1941 
1942  return *this;
1943  }
1944 
1945  template < typename Key, typename Val >
1946  INLINE HashTableConstIterator< Key, Val >& HashTableConstIterator< Key, Val >::operator=(
1947  HashTableConstIterator< Key, Val >&& from) noexcept {
1948  // here, no need to avoid self assignment: this would slow down normal
1949  // assignments and, in any case, this would not result in an iterator in
1950  // an incoherent state
1951  _table_ = from._table_;
1952  _index_ = from._index_;
1953  _bucket_ = from._bucket_;
1954 
1955  return *this;
1956  }
1957 
1958  template < typename Key, typename Val >
1959  INLINE const typename HashTableConstIterator< Key, Val >::key_type&
1960  HashTableConstIterator< Key, Val >::key() const {
1961  if (_bucket_)
1962  return _bucket_->pair.first;
1963  else {
1964  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
1965  }
1966  }
1967 
1968  template < typename Key, typename Val >
1969  INLINE const typename HashTableConstIterator< Key, Val >::mapped_type&
1970  HashTableConstIterator< Key, Val >::val() const {
1971  if (_bucket_)
1972  return _bucket_->val();
1973  else {
1974  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
1975  }
1976  }
1977 
1978  template < typename Key, typename Val >
1979  INLINE void HashTableConstIterator< Key, Val >::clear() noexcept {
1980  _table_ = nullptr;
1981  _bucket_ = nullptr;
1982  _index_ = 0;
1983  }
1984 
1985  template < typename Key, typename Val >
1986  HashTableConstIterator< Key, Val >& HashTableConstIterator< Key, Val >::operator++() noexcept {
1987  // if _bucket_ == nullptr then we are at the end of the hashtable
1988  if (_bucket_ == nullptr) return *this;
1989 
1990  // if we are not pointing on the first element of the chained list, just
1991  // point to the next bucket in this list
1992  if (_bucket_->prev) {
1993  _bucket_ = _bucket_->prev;
1994  // here, no need to update _index_ which has not changed.
1995  } else {
1996  // ok, here we are on the end of a chained list,
1997  // so 2 cases can obtain:
1998  // 1/ index = 0 : then we have reached the end of the hashtable
1999  // 2/ index != 0 => we must search for a new slot containing elements
2000 
2001  // case 1:
2002  if (_index_ == Size(0)) {
2003  _bucket_ = nullptr;
2004  // we are thus at the end() of the hashTable
2005  }
2006 
2007  // case 2:
2008  else {
2009  // arrived here, we need to parse the hash table until we find a new
2010  // bucket because we are pointing on a chained list with no more element
2011  // to the right of the current element
2012  for (Size i = _index_ - Size(1); i; --i) {
2013  if (_table_->_nodes_[i]._nb_elements_) {
2014  _index_ = i;
2015  _bucket_ = _table_->_nodes_[i]._end_list_;
2016  return *this;
2017  }
2018  }
2019 
2020  if (_table_->_nodes_[0]._nb_elements_)
2021  _bucket_ = _table_->_nodes_[0]._end_list_;
2022  else
2023  _bucket_ = nullptr;
2024 
2025  _index_ = Size(0);
2026  }
2027  }
2028 
2029  return *this;
2030  }
2031 
2032  template < typename Key, typename Val >
2033  HashTableConstIterator< Key, Val >&
2034  HashTableConstIterator< Key, Val >::operator+=(Size nb) noexcept {
2035  if ((nb == 0) || (_table_ == nullptr) || (_bucket_ == nullptr)) return *this;
2036 
2037  // ok, here we can use _bucket_ as a starting point: parse all the elements
2038  // of the current chained list
2039  for (; nb && _bucket_ != nullptr; --nb, _bucket_ = _bucket_->prev) {}
2040 
2041  if (_bucket_ != nullptr) return *this;
2042 
2043  // here, we shall skip all the chained list that have not sufficiently
2044  // many elements
2045  --_index_;
2046 
2047  for (; _index_ < _table_->_size_ && nb >= _table_->_nodes_[_index_]._nb_elements_;
2048  nb -= _table_->_nodes_[_index_]._nb_elements_, --_index_) {}
2049 
2050  // here: either _index_ >= _table_-> _size_, which means that we did not find
2051  // the element we looked for, i.e., we are at the end of the hashtable, or
2052  // nb < _table_-> _nodes_[ _index_]. _nb_elements_, and we should parse the
2053  // chained list to get the element (which, we know for sure, exists)
2054  if (_index_ >= _table_->_size_) {
2055  _index_ = 0;
2056  return *this;
2057  }
2058 
2059  for (_bucket_ = _table_->_nodes_[_index_]._end_list_; nb; --nb, _bucket_ = _bucket_->prev) {}
2060 
2061  return *this;
2062  }
2063 
2064  template < typename Key, typename Val >
2065  INLINE HashTableConstIterator< Key, Val >
2066  HashTableConstIterator< Key, Val >::operator+(Size nb) const noexcept {
2067  return HashTableConstIterator< Key, Val >{*this} += nb;
2068  }
2069 
2070  template < typename Key, typename Val >
2071  INLINE bool HashTableConstIterator< Key, Val >::operator!=(
2072  const HashTableConstIterator< Key, Val >& from) const noexcept {
2073  return (_bucket_ != from._bucket_);
2074  }
2075 
2076  template < typename Key, typename Val >
2077  INLINE bool HashTableConstIterator< Key, Val >::operator==(
2078  const HashTableConstIterator< Key, Val >& from) const noexcept {
2079  return (_bucket_ == from._bucket_);
2080  }
2081 
2082  template < typename Key, typename Val >
2083  INLINE const typename HashTableConstIterator< Key, Val >::value_type&
2084  HashTableConstIterator< Key, Val >::operator*() const {
2085  if (_bucket_)
2086  return _bucket_->elt();
2087  else {
2088  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
2089  }
2090  }
2091 
2092  template < typename Key, typename Val >
2093  INLINE typename HashTable< Key, Val >::Bucket*
2094  HashTableConstIterator< Key, Val >::_getBucket_() const noexcept {
2095  return _bucket_;
2096  }
2097 
2098  template < typename Key, typename Val >
2099  INLINE Size HashTableConstIterator< Key, Val >::_getIndex_() const noexcept {
2100  return _index_;
2101  }
2102 
2103  // ===========================================================================
2104  // === UNSAFE HASH TABLE ITERATORS IMPLEMENTATION ===
2105  // ===========================================================================
2106 
2107  template < typename Key, typename Val >
2108  INLINE HashTableIterator< Key, Val >::HashTableIterator() noexcept :
2109  HashTableConstIterator< Key, Val >() {
2110  GUM_CONSTRUCTOR(HashTableIterator);
2111  }
2112 
2113  template < typename Key, typename Val >
2114  template < typename Alloc >
2115  INLINE HashTableIterator< Key, Val >::HashTableIterator(
2116  const HashTable< Key, Val, Alloc >& tab) noexcept :
2117  HashTableConstIterator< Key, Val >(tab) {
2118  GUM_CONSTRUCTOR(HashTableIterator);
2119  }
2120 
2121  template < typename Key, typename Val >
2122  template < typename Alloc >
2123  INLINE HashTableIterator< Key, Val >::HashTableIterator(const HashTable< Key, Val, Alloc >& tab,
2124  Size ind_elt) :
2125  HashTableConstIterator< Key, Val >(tab, ind_elt) {
2126  GUM_CONSTRUCTOR(HashTableIterator);
2127  }
2128 
2129  template < typename Key, typename Val >
2130  INLINE HashTableIterator< Key, Val >::HashTableIterator(
2131  const HashTableIterator< Key, Val >& from) noexcept :
2132  HashTableConstIterator< Key, Val >(from) {
2133  GUM_CONS_CPY(HashTableIterator);
2134  }
2135 
2136  template < typename Key, typename Val >
2137  INLINE
2138  HashTableIterator< Key, Val >::HashTableIterator(HashTableIterator< Key, Val >&& from) noexcept
2139  :
2140  HashTableConstIterator< Key, Val >(std::move(from)) {
2141  GUM_CONS_MOV(HashTableIterator);
2142  }
2143 
2144  template < typename Key, typename Val >
2145  INLINE HashTableIterator< Key, Val >::~HashTableIterator() noexcept {
2146  GUM_DESTRUCTOR(HashTableIterator);
2147  }
2148 
2149  template < typename Key, typename Val >
2150  INLINE typename HashTableIterator< Key, Val >::mapped_type& HashTableIterator< Key, Val >::val() {
2151  if (this->_bucket_)
2152  return this->_bucket_->val();
2153  else {
2154  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object")
2155  }
2156  }
2157 
2158  template < typename Key, typename Val >
2159  INLINE HashTableIterator< Key, Val >&
2160  HashTableIterator< Key, Val >::operator=(const HashTableIterator< Key, Val >& from) noexcept {
2161  HashTableConstIterator< Key, Val >::operator=(from);
2162  return *this;
2163  }
2164 
2165  template < typename Key, typename Val >
2166  INLINE HashTableIterator< Key, Val >&
2167  HashTableIterator< Key, Val >::operator=(HashTableIterator< Key, Val >&& from) noexcept {
2168  HashTableConstIterator< Key, Val >::operator=(std::move(from));
2169  return *this;
2170  }
2171 
2172  template < typename Key, typename Val >
2173  INLINE HashTableIterator< Key, Val >& HashTableIterator< Key, Val >::operator++() noexcept {
2174  HashTableConstIterator< Key, Val >::operator++();
2175  return *this;
2176  }
2177 
2178  template < typename Key, typename Val >
2179  INLINE HashTableIterator< Key, Val >&
2180  HashTableIterator< Key, Val >::operator+=(Size nb) noexcept {
2181  HashTableConstIterator< Key, Val >::operator+=(nb);
2182  return *this;
2183  }
2184 
2185  template < typename Key, typename Val >
2186  INLINE HashTableIterator< Key, Val >
2187  HashTableIterator< Key, Val >::operator+(Size nb) const noexcept {
2188  HashTableIterator< Key, Val > iter{*this};
2189  iter += nb;
2190  return iter;
2191  }
2192 
2193  template < typename Key, typename Val >
2194  INLINE bool HashTableIterator< Key, Val >::operator!=(
2195  const HashTableIterator< Key, Val >& from) const noexcept {
2196  return HashTableConstIterator< Key, Val >::operator!=(from);
2197  }
2198 
2199  template < typename Key, typename Val >
2200  INLINE bool HashTableIterator< Key, Val >::operator==(
2201  const HashTableIterator< Key, Val >& from) const noexcept {
2202  return HashTableConstIterator< Key, Val >::operator==(from);
2203  }
2204 
2205  template < typename Key, typename Val >
2206  INLINE typename HashTableIterator< Key, Val >::value_type&
2207  HashTableIterator< Key, Val >::operator*() {
2208  return const_cast< value_type& >(HashTableConstIterator< Key, Val >::operator*());
2209  }
2210 
2211  template < typename Key, typename Val >
2212  INLINE const typename HashTableIterator< Key, Val >::value_type&
2213  HashTableIterator< Key, Val >::operator*() const {
2214  return HashTableConstIterator< Key, Val >::operator*();
2215  }
2216 
2217 } /* namespace gum */
aGrUM 0.20.3
Mon Jun 7 2021 17:34:08
© PHW&CG&others - 2021
DoXyGeN 1.8.13