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