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