aGrUM  0.13.2
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 = 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&
237  HashTableList< Key, Val, Alloc >::at(unsigned int i) const {
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  }
269 
270  template < typename Key, typename Val, typename Alloc >
271  INLINE bool HashTableList< Key, Val, Alloc >::exists(const Key& key) const {
272  for (Bucket* ptr = __deb_list; ptr != nullptr; ptr = ptr->next) {
273  if (ptr->key() == key) { return true; }
274  }
275 
276  return false;
277  }
278 
279  template < typename Key, typename Val, typename Alloc >
280  INLINE bool HashTableList< Key, Val, Alloc >::empty() const noexcept {
281  return (__nb_elements == 0);
282  }
283 
284  template < typename Key, typename Val, typename Alloc >
286  HashTableBucket< Key, Val >* new_elt) noexcept {
287  // place the bucket at the beginning of the list
288  new_elt->prev = nullptr;
289  new_elt->next = __deb_list;
290 
291  if (__deb_list != nullptr)
292  __deb_list->prev = new_elt;
293  else
294  __end_list = new_elt;
295 
296  __deb_list = new_elt;
297 
298  ++__nb_elements;
299  }
300 
301  // ===========================================================================
302  // === GENERIC HASH TABLE IMPLEMENTATION ===
303  // ===========================================================================
304 
305  template < typename Key, typename Val, typename Alloc >
306  template < typename OtherAlloc >
308  const HashTable< Key, Val, OtherAlloc >& table) {
309  // in debug mode, check that this and table have '__nodes' arrays of the
310  // same size
311  GUM_ASSERT(table.__size == __size);
312 
313  // try to fill the array of chained lists
314  for (Size i = 0; i < table.__size; ++i) {
315  try {
316  __nodes[i] = table.__nodes[i];
317  } catch (...) {
318  // here we could allocate the __nodes[j], j=0..i-1, so we should
319  // deallocate them
320  for (Size j = 0; j < __size; ++j)
321  __nodes[j].clear();
322 
323  __nb_elements = 0;
324 
325  // propagate the exception
326  throw;
327  }
328  }
329 
331  }
332 
333  template < typename Key, typename Val, typename Alloc >
334  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
336  return *(reinterpret_cast< const iterator* >(
338  }
339 
340  template < typename Key, typename Val, typename Alloc >
341  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
343  return *(reinterpret_cast< const const_iterator* >(
345  }
346 
347  template < typename Key, typename Val, typename Alloc >
348  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
350  return *(reinterpret_cast< const iterator_safe* >(
352  }
353 
354  template < typename Key, typename Val, typename Alloc >
357  return *(reinterpret_cast< const const_iterator_safe* >(
359  }
360 
361  template < typename Key, typename Val, typename Alloc >
363  // setup the __nodes vector (contains only empty lists)
364  __nodes.resize(size);
365 
366  for (auto& list : __nodes) {
367  list.setAllocator(__alloc);
368  }
369 
370  // set up properly the hash function
371  __hash_func.resize(size);
372 
373  // make sure the end() iterator is constructed properly
374  end4Statics();
375  endSafe4Statics();
376  }
377 
378  template < typename Key, typename Val, typename Alloc >
380  bool resize_pol,
381  bool key_uniqueness_pol) :
382  // size must be >= 2 else we lose all the bits of the hash function
383  __size{Size(1) << __hashTableLog2(std::max(Size(2), size_param))},
384  __resize_policy{resize_pol}, __key_uniqueness_policy{key_uniqueness_pol} {
385  // for debugging purposes
386  GUM_CONSTRUCTOR(HashTable);
387 
388  // finalize the creation
389  __create(__size);
390  }
391 
392  template < typename Key, typename Val, typename Alloc >
394  std::initializer_list< std::pair< Key, Val > > list) :
395  // size must be >= 2 else we lose all the bits of the hash function
397  std::max< Size >(Size(2), Size(list.size()) / 2))} {
398  // for debugging purposes
399  GUM_CONSTRUCTOR(HashTable);
400 
401  // setup the __nodes vector (contains only empty lists)
402  __create(__size);
403 
404  // insert all the elements
405  for (const auto& elt : list) {
406  insert(elt);
407  }
408  }
409 
410  template < typename Key, typename Val, typename Alloc >
412  const HashTable< Key, Val, Alloc >& table) :
413  __size{table.__size},
414  __resize_policy{table.__resize_policy},
415  __key_uniqueness_policy{table.__key_uniqueness_policy},
416  __begin_index{table.__begin_index} {
417  // for debugging purposes
418  GUM_CONS_CPY(HashTable);
419 
420  // setup the __nodes vector (contains only empty lists)
421  __create(__size);
422 
423  // fill with the content of table
424  __copy(table);
425  }
426 
427  template < typename Key, typename Val, typename Alloc >
428  template < typename OtherAlloc >
430  const HashTable< Key, Val, OtherAlloc >& table) :
431  __size{table.__size},
432  __resize_policy{table.__resize_policy},
433  __key_uniqueness_policy{table.__key_uniqueness_policy},
434  __begin_index{table.__begin_index} {
435  // for debugging purposes
436  GUM_CONS_CPY(HashTable);
437 
438  // setup the __nodes vector (contains only empty lists)
439  __create(__size);
440 
441  // fill with the content of table
442  __copy(table);
443  }
444 
445  template < typename Key, typename Val, typename Alloc >
447  __nodes(std::move(table.__nodes)), __size{table.__size},
448  __nb_elements{table.__nb_elements}, __hash_func{table.__hash_func},
449  __resize_policy{table.__resize_policy},
450  __key_uniqueness_policy{table.__key_uniqueness_policy},
451  __begin_index{table.__begin_index},
452  __safe_iterators(std::move(table.__safe_iterators)),
453  __alloc(std::move(table.__alloc)) {
454  // for debugging purposes
455  table.__size = 0;
456  GUM_CONS_MOV(HashTable);
457  }
458 
459  template < typename Key, typename Val, typename Alloc >
461  Size len = Size(__safe_iterators.size());
462  for (Size i = 0; i < len; ++i)
463  __safe_iterators[i]->clear();
464  }
465 
466  template < typename Key, typename Val, typename Alloc >
468  // update all the registered iterators: they should now point to nullptr
469  // and they are positioned to the end of the hashtable.
471 
472  // remove the buckets
473  for (Size i = 0; i < __size; ++i)
474  __nodes[i].clear();
475 
476  __nb_elements = 0;
477  __begin_index = std::numeric_limits< Size >::max();
478  }
479 
480  template < typename Key, typename Val, typename Alloc >
482  // for debugging purposes
483  GUM_DESTRUCTOR(HashTable);
484 
485  // update all the registered iterators: they should now point to nullptr
486  // and their hashtable should be set to nullptr
488  }
489 
490  template < typename Key, typename Val, typename Alloc >
493  // avoid self assignment
494  if (this != &from) {
495  // for debugging purposes
496  GUM_OP_CPY(HashTable);
497 
498  // first remove the current content of the hashtable and make
499  // the iterators point to end
500  clear();
501 
502  // if sizes of from's and this' __nodes vectors are not the same,
503  // we need to remove the current __nodes' array and to create a
504  // new array with the correct size
505  if (__size != from.__size) {
506  __nodes.resize(from.__size);
507 
508  for (Size i = 0; i < from.__size; ++i) {
509  __nodes[i].setAllocator(__alloc);
510  }
511 
512  __size = from.__size;
513 
514  // update the hash function : this is important as the computation of
515  // the hash values heavily depends on the size of the hash table
516  __hash_func.resize(__size);
517  }
518 
522 
523  // perform the copy
524  __copy(from);
525  }
526 
527  return *this;
528  }
529 
530  template < typename Key, typename Val, typename Alloc >
531  template < typename OtherAlloc >
534  // avoid self assignment
535  if (this != reinterpret_cast< const HashTable< Key, Val, Alloc >* >(&from)) {
536  // for debugging purposes
537  GUM_OP_CPY(HashTable);
538 
539  // first remove the current content of the hashtable and make
540  // the iterators point to end
541  clear();
542 
543  // if sizes of from's and this' __nodes vectors are not the same,
544  // we need to remove the current __nodes' array and to create a
545  // new array with the correct size
546  if (__size != from.__size) {
547  __nodes.resize(from.__size);
548 
549  for (Size i = 0; i < from.__size; ++i) {
550  __nodes[i].setAllocator(__alloc);
551  }
552 
553  __size = from.__size;
554 
555  // update the hash function : this is important as the computation of
556  // the hash values heavily depends on the size of the hash table
557  __hash_func.resize(__size);
558  }
559 
563 
564  // perform the copy
565  __copy(from);
566  }
567 
568  return *this;
569  }
570 
571  template < typename Key, typename Val, typename Alloc >
574  // avoid self assignment
575  if (this != &table) {
576  // for debugging purposes
577  GUM_OP_MOV(HashTable);
578 
579  // first remove the current content of the hashtable and make
580  // the iterators point to end
581  clear();
582 
583  __nodes = std::move(table.__nodes);
584  __safe_iterators = std::move(table.__safe_iterators);
585  __alloc = std::move(table.__alloc);
586  __size = table.__size;
587  __nb_elements = table.__nb_elements;
588  __hash_func = table.__hash_func;
589  __resize_policy = table.__resize_policy;
590  __key_uniqueness_policy = table.__key_uniqueness_policy;
591  __begin_index = table.__begin_index;
592 
593  table.__size = 0; // necessary if we wish to perform moves iteratively,
594  // i.e. x = std::move ( y ); y = std::move ( z ); ...
595  }
596 
597  return *this;
598  }
599 
600  template < typename Key, typename Val, typename Alloc >
601  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
603  // note that, here, we know for sure that HashTableIterEnd has been properly
604  // initialized as it is initialized by end4Statics, which is called by
605  // all hashtables' constructors
606  return *(reinterpret_cast< const iterator* >(
608  }
609 
610  template < typename Key, typename Val, typename Alloc >
611  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
613  // note that, here, we know for sure that HashTableIterEnd has been properly
614  // initialized as it is initialized by end4Statics, which is called by
615  // all hashtables' constructors
616  return *(reinterpret_cast< const const_iterator* >(
618  }
619 
620  template < typename Key, typename Val, typename Alloc >
621  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
623  // note that, here, we know for sure that HashTableIterEnd has been properly
624  // initialized as it is initialized by end4Statics, which is called by
625  // all hashtables' constructors
626  return *(reinterpret_cast< const const_iterator* >(
628  }
629 
630  template < typename Key, typename Val, typename Alloc >
633  // if the table is empty, make the begin and end point to the same element
634  if (__nb_elements == 0)
635  return iterator{end()};
636  else
637  return iterator{*this};
638  }
639 
640  template < typename Key, typename Val, typename Alloc >
643  // if the table is empty, make the begin and end point to the same element
644  if (__nb_elements == 0)
645  return const_iterator{end()};
646  else
647  return const_iterator{*this};
648  }
649 
650  template < typename Key, typename Val, typename Alloc >
653  // if the table is empty, make the begin and end point to the same element
654  if (__nb_elements == 0)
655  return const_iterator{cend()};
656  else
657  return const_iterator{*this};
658  }
659 
660  template < typename Key, typename Val, typename Alloc >
661  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
663  // note that, here, we know for sure that HashTableIterEnd has been properly
664  // initialized as it is initialized by end4Statics, which is called by
665  // all hashtables' constructors
666  return *(reinterpret_cast< const iterator_safe* >(
668  }
669 
670  template < typename Key, typename Val, typename Alloc >
673  // note that, here, we know for sure that HashTableIterEnd has been properly
674  // initialized as it is initialized by end4Statics, which is called by
675  // all hashtables' constructors
676  return *(reinterpret_cast< const const_iterator_safe* >(
678  }
679 
680  template < typename Key, typename Val, typename Alloc >
683  // note that, here, we know for sure that HashTableIterEnd has been properly
684  // initialized as it is initialized by end4Statics, which is called by
685  // all hashtables' constructors
686  return *(reinterpret_cast< const const_iterator_safe* >(
688  }
689 
690  template < typename Key, typename Val, typename Alloc >
693  // if the table is empty, make the begin and end point to the same element
694  if (__nb_elements == 0)
695  return iterator_safe{endSafe()};
696  else
697  return iterator_safe{*this};
698  }
699 
700  template < typename Key, typename Val, typename Alloc >
703  // if the table is empty, make the begin and end point to the same element
704  if (__nb_elements == 0)
705  return const_iterator_safe{endSafe()};
706  else
707  return const_iterator_safe{*this};
708  }
709 
710  template < typename Key, typename Val, typename Alloc >
713  // if the table is empty, make the begin and end point to the same element
714  if (__nb_elements == 0)
715  return const_iterator_safe{cendSafe()};
716  else
717  return const_iterator_safe{*this};
718  }
719 
720  template < typename Key, typename Val, typename Alloc >
722  return __nodes[__hash_func(key)][key];
723  }
724 
725  template < typename Key, typename Val, typename Alloc >
726  INLINE const Val& HashTable< Key, Val, Alloc >::
727  operator[](const Key& key) const {
728  return __nodes[__hash_func(key)][key];
729  }
730 
731  template < typename Key, typename Val, typename Alloc >
732  INLINE Size HashTable< Key, Val, Alloc >::size() const noexcept {
733  return __nb_elements;
734  }
735 
736  template < typename Key, typename Val, typename Alloc >
738  return __size;
739  }
740 
741  template < typename Key, typename Val, typename Alloc >
742  INLINE bool HashTable< Key, Val, Alloc >::exists(const Key& key) const {
743  return __nodes[__hash_func(key)].exists(key);
744  }
745 
746  template < typename Key, typename Val, typename Alloc >
747  INLINE void
748  HashTable< Key, Val, Alloc >::setResizePolicy(const bool new_policy) noexcept {
749  __resize_policy = new_policy;
750  }
751 
752  template < typename Key, typename Val, typename Alloc >
753  INLINE bool HashTable< Key, Val, Alloc >::resizePolicy() const noexcept {
754  return __resize_policy;
755  }
756 
757  template < typename Key, typename Val, typename Alloc >
759  const bool new_policy) noexcept {
760  __key_uniqueness_policy = new_policy;
761  }
762 
763  template < typename Key, typename Val, typename Alloc >
766  }
767 
768  template < typename Key, typename Val, typename Alloc >
770  // new_size must be >= 2 else all the bits of the hash function are lost
771  new_size = std::max(Size(2), new_size);
772 
773  // find the real size for allocation (the smallest power of 2 greater
774  // than or equal to new_size) and get its base-2 logarithm
775  int log_size = __hashTableLog2(new_size);
776  new_size = Size(1) << log_size;
777 
778  // check if the new size is different from the actual size
779  // if not, nothing else need be done
780 
781  if (new_size != __size) {
782  // under automatic resize policy, check if the new size leaves
783  // enough space for storing all the current elements
784  if (!__resize_policy
785  || (__nb_elements
787  // create a new array of __nodes to store the elements
788  std::vector< HashTableList< Key, Val, Alloc > > new_nodes(new_size);
789 
790  for (auto& list : new_nodes) {
791  list.setAllocator(__alloc);
792  }
793 
794  // set the new hash function
795  __hash_func.resize(new_size);
796 
797  // put all the elements of the current __nodes array into the new one
798  Bucket* bucket;
799  Size new_hashed_key;
800 
801  for (Size i = 0; i < __size; ++i) {
802  while ((bucket = __nodes[i].__deb_list) != nullptr) {
803  // compute the new hashed key
804  new_hashed_key = __hash_func(bucket->key());
805 
806  // remove the bucket from the list of buckets of the current
807  // node vector
808  __nodes[i].__deb_list = bucket->next;
809 
810  // put the bucket into the new __nodes vector
811  new_nodes[new_hashed_key].insert(bucket);
812  }
813  }
814 
815  // update the size of the hash table
816  __size = new_size;
817  __begin_index = std::numeric_limits< Size >::max();
818 
819  // substitute the current __nodes array by the new one
820  std::swap(__nodes, new_nodes);
821 
822  // update the iterators
823  for (auto iter : __safe_iterators) {
824  if (iter->__bucket)
825  iter->__index = __hash_func(iter->__bucket->key());
826  else {
827  iter->__next_bucket = nullptr;
828  iter->__index = 0;
829  }
830  }
831  }
832  }
833  }
834 
835  template < typename Key, typename Val, typename Alloc >
836  void
838  Size hash_key = __hash_func(bucket->key());
839 
840  // check that there does not already exist an element with the same key
841  if (__key_uniqueness_policy && __nodes[hash_key].exists(bucket->key())) {
842  // remove the bucket from memory
843  __alloc.destroy(bucket);
844  __alloc.deallocate(bucket, 1);
846  "the hashtable contains an element with the same key");
847  }
848 
849  // check whether there is sufficient space to insert the new pair
850  // if not, resize the current hashtable
851  if (__resize_policy
853  resize(__size << 1);
854  hash_key = __hash_func(bucket->key());
855  }
856 
857  // add the new pair
858  __nodes[hash_key].insert(bucket);
859  ++__nb_elements;
860 
861  // recompute the index of the beginning of the hashtable if possible
862  // WARNING: if __begin_index = std::numeric_limits<Size>::max (), we CANNOT
863  // recompute the index because we cannot know whether the current index is
864  // equal to max because there was no element in the hashtable or whether a
865  // previous __erase() has set the index to max.
866  if (__begin_index < hash_key) { __begin_index = hash_key; }
867  }
868 
869  template < typename Key, typename Val, typename Alloc >
871  HashTable< Key, Val, Alloc >::insert(const Key& thekey, const Val& theval) {
872  Bucket* bucket = __alloc.allocate(1);
873 
874  try {
875  __alloc.construct(bucket, thekey, theval);
876  } catch (...) {
877  __alloc.deallocate(bucket, 1);
878  throw;
879  }
880 
881  __insert(bucket);
882  return bucket->elt();
883  }
884 
885  template < typename Key, typename Val, typename Alloc >
887  HashTable< Key, Val, Alloc >::insert(Key&& thekey, Val&& theval) {
888  Bucket* bucket = __alloc.allocate(1);
889 
890  try {
891  __alloc.construct(bucket, std::move(thekey), std::move(theval));
892  } catch (...) {
893  __alloc.deallocate(bucket, 1);
894  throw;
895  }
896 
897  __insert(bucket);
898  return bucket->elt();
899  }
900 
901  template < typename Key, typename Val, typename Alloc >
903  HashTable< Key, Val, Alloc >::insert(const std::pair< Key, Val >& elt) {
904  Bucket* bucket = __alloc.allocate(1);
905 
906  try {
907  __alloc.construct(bucket, reinterpret_cast< const value_type& >(elt));
908  } catch (...) {
909  __alloc.deallocate(bucket, 1);
910  throw;
911  }
912 
913  __insert(bucket);
914  return bucket->elt();
915  }
916 
917  template < typename Key, typename Val, typename Alloc >
919  HashTable< Key, Val, Alloc >::insert(std::pair< Key, Val >&& elt) {
920  Bucket* bucket = __alloc.allocate(1);
921 
922  try {
923  __alloc.construct(bucket, std::move(reinterpret_cast< value_type& >(elt)));
924  } catch (...) {
925  __alloc.deallocate(bucket, 1);
926  throw;
927  }
928 
929  __insert(bucket);
930  return bucket->elt();
931  }
932 
933  template < typename Key, typename Val, typename Alloc >
934  template < typename... Args >
937  Bucket* bucket = __alloc.allocate(1);
938 
939  try {
940  __alloc.construct(bucket,
942  std::forward< Args >(args)...);
943  } catch (...) {
944  __alloc.deallocate(bucket, 1);
945  throw;
946  }
947 
948  __insert(bucket);
949  return bucket->elt();
950  }
951 
952  template < typename Key, typename Val, typename Alloc >
955  const Val& default_value) {
956  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
957 
958  if (bucket == nullptr)
959  return insert(key, default_value).second;
960  else
961  return bucket->val();
962  }
963 
964  template < typename Key, typename Val, typename Alloc >
966  HashTable< Key, Val, Alloc >::getWithDefault(Key&& key, Val&& default_value) {
967  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
968 
969  if (bucket == nullptr)
970  return insert(std::move(key), std::move(default_value)).second;
971  else
972  return bucket->val();
973  }
974 
975  template < typename Key, typename Val, typename Alloc >
976  INLINE void HashTable< Key, Val, Alloc >::set(const Key& key, const Val& value) {
977  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
978 
979  if (bucket == nullptr)
980  insert(key, value);
981  else
982  bucket->val() = value;
983  }
984 
985  template < typename Key, typename Val, typename Alloc >
987  Size index) {
988  if (bucket == nullptr) return;
989 
990  // update the registered iterators pointing to this bucket
991  for (auto iter : __safe_iterators) {
992  if (iter->__bucket == bucket) {
993  iter->operator++();
994  iter->__next_bucket = iter->__bucket;
995  iter->__bucket = nullptr;
996  } else if (iter->__next_bucket == bucket) {
997  iter->__bucket = bucket;
998  iter->operator++();
999  iter->__next_bucket = iter->__bucket;
1000  iter->__bucket = nullptr;
1001  }
1002  }
1003 
1004  // remove the element from the __nodes vector
1005  __nodes[index].erase(bucket);
1006 
1007  --__nb_elements;
1008 
1009  if ((index == __begin_index) && __nodes[index].empty()) {
1010  __begin_index = std::numeric_limits< Size >::max();
1011  }
1012  }
1013 
1014  template < typename Key, typename Val, typename Alloc >
1015  INLINE void HashTable< Key, Val, Alloc >::erase(const Key& key) {
1016  // get the hashed key
1017  Size hash = __hash_func(key);
1018 
1019  // get the bucket containing the element to erase
1020  HashTableBucket< Key, Val >* bucket = __nodes[hash].bucket(key);
1021 
1022  __erase(bucket, hash);
1023  }
1024 
1025  template < typename Key, typename Val, typename Alloc >
1027  __erase(iter.__getBucket(), iter.__getIndex());
1028  }
1029 
1030  template < typename Key, typename Val, typename Alloc >
1031  INLINE void
1033  __erase(iter.__getBucket(), iter.__getIndex());
1034  }
1035 
1036  template < typename Key, typename Val, typename Alloc >
1037  INLINE void HashTable< Key, Val, Alloc >::eraseByVal(const Val& val) {
1038  for (auto iter = cbegin(); iter != cend(); ++iter)
1039  if (iter.__bucket->val() == val) {
1040  __erase(iter.__getBucket(), iter.__getIndex());
1041  return;
1042  }
1043  }
1044 
1045  template < typename Key, typename Val, typename Alloc >
1046  INLINE void HashTable< Key, Val, Alloc >::reset(const Key& key) {
1047  erase(key);
1048  }
1049 
1050  template < typename Key, typename Val, typename Alloc >
1051  INLINE const Key& HashTable< Key, Val, Alloc >::keyByVal(const Val& val) const {
1052  for (auto iter = begin(); iter != end(); ++iter)
1053  if (iter.__bucket->val() == val) return iter.key();
1054 
1055  GUM_ERROR(NotFound, "not enough elements in the chained list");
1056  }
1057 
1058  template < typename Key, typename Val, typename Alloc >
1059  INLINE const Key& HashTable< Key, Val, Alloc >::key(const Key& key) const {
1060  // get the bucket corresponding to the key
1061  Bucket* bucket = __nodes[__hash_func(key)].bucket(key);
1062 
1063  if (bucket == nullptr) {
1064  GUM_ERROR(NotFound, "key does not belong to the hashtable");
1065  }
1066 
1067  return bucket->key();
1068  }
1069 
1070  template < typename Key, typename Val, typename Alloc >
1072  for (auto iterAll = cbeginSafe(); iterAll != cendSafe(); ++iterAll) {
1073  if (iterAll.__bucket->val() == val) {
1074  __erase(iterAll.__bucket, iterAll.__index);
1075  }
1076  }
1077  }
1078 
1079  template < typename Key, typename Val, typename Alloc >
1080  INLINE bool HashTable< Key, Val, Alloc >::empty() const noexcept {
1081  return (__nb_elements == 0);
1082  }
1083 
1084  template < typename Key, typename Val, typename Alloc >
1085  template < typename Mount, typename OtherAlloc >
1087  Mount (*f)(Val), Size size, bool resize_pol, bool key_uniqueness_pol) const {
1088  // determine the proper size of the hashtable
1089  // by default, the size of the table is set so that the table does not take
1090  // too much space while allowing to add a few elements without needing to
1091  // resize in autmatic resizing mode
1092  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1093 
1094  // create a new table
1096  size, resize_pol, key_uniqueness_pol);
1097 
1098  // fill the new hash table
1099  for (auto iter = begin(); iter != end(); ++iter) {
1100  table.insert(iter.key(), f(iter.val()));
1101  }
1102 
1103  return table;
1104  }
1105 
1106  template < typename Key, typename Val, typename Alloc >
1107  template < typename Mount, typename OtherAlloc >
1109  Mount (*f)(Val&), Size size, bool resize_pol, bool key_uniqueness_pol) const {
1110  // determine the proper size of the hashtable
1111  // by default, the size of the table is set so that the table does not take
1112  // too much space while allowing to add a few elements without needing to
1113  // resize in autmatic resizing mode
1114  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1115 
1116  // create a new table
1118  size, resize_pol, key_uniqueness_pol);
1119 
1120  // fill the new hash table
1121  for (auto iter = begin(); iter != end(); ++iter) {
1122  table.insert(iter.key(), f(const_cast< Val& >(iter.val())));
1123  }
1124 
1125  return table;
1126  }
1127 
1128  template < typename Key, typename Val, typename Alloc >
1129  template < typename Mount, typename OtherAlloc >
1131  INLINE HashTable< Key, Val, Alloc >::map(Mount (*f)(const Val&),
1132  Size size,
1133  bool resize_pol,
1134  bool key_uniqueness_pol) const {
1135  // determine the proper size of the hashtable
1136  // by default, the size of the table is set so that the table does not take
1137  // too much space while allowing to add a few elements without needing to
1138  // resize in autmatic resizing mode
1139  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1140 
1141  // create a new table
1143  size, resize_pol, key_uniqueness_pol);
1144 
1145  // fill the new hash table
1146  for (auto iter = begin(); iter != end(); ++iter) {
1147  table.insert(iter.key(), f(iter.val()));
1148  }
1149 
1150  return table;
1151  }
1152 
1153  template < typename Key, typename Val, typename Alloc >
1154  template < typename Mount, typename OtherAlloc >
1156  const Mount& val, Size size, bool resize_pol, bool key_uniqueness_pol) const {
1157  // determine the proper size of the hashtable
1158  // by default, the size of the table is set so that the table does not take
1159  // too much space while allowing to add a few elements without needing to
1160  // resize in autmatic resizing mode
1161  if (size == 0) size = std::max(Size(2), __nb_elements / 2);
1162 
1163  // create a new table
1165  size, resize_pol, key_uniqueness_pol);
1166 
1167  // fill the new hash table
1168  for (auto iter = begin(); iter != end(); ++iter) {
1169  table.insert(iter.key(), val);
1170  }
1171 
1172  return table;
1173  }
1174 
1175  template < typename Key, typename Val, typename Alloc >
1176  template < typename OtherAlloc >
1179  // checks whether the two hashtables contain the same number of elements
1180  if (from.__nb_elements != __nb_elements) return false;
1181 
1182  // parse this and check that each element also belongs to from
1183  for (auto iter = begin(); iter != end(); ++iter) {
1184  try {
1185  if (iter.val() != from[iter.key()]) return false;
1186  } catch (NotFound&) { return false; }
1187  }
1188 
1189  return true;
1190  }
1191 
1192  template < typename Key, typename Val, typename Alloc >
1193  template < typename OtherAlloc >
1194  INLINE bool HashTable< Key, Val, Alloc >::
1196  return !operator==(from);
1197  }
1198 
1199  template < typename Key, typename Val, typename Alloc >
1200  std::ostream& operator<<(std::ostream& stream,
1201  const HashTableList< Key, Val, Alloc >& list) {
1202  bool deja = false;
1203  stream << "[";
1204 
1205  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1206  ptr = ptr->list.next, deja = true) {
1207  if (deja) stream << " , ";
1208 
1209  stream << ptr->key() << "=>" << ptr->val();
1210  }
1211 
1212  stream << "]";
1213 
1214  return stream;
1215  }
1216 
1217  template < typename Key, typename Val, typename Alloc >
1218  std::ostream& operator<<(std::ostream& stream,
1219  const HashTableList< Key*, Val, Alloc >& list) {
1220  bool deja = false;
1221  stream << "[";
1222 
1223  for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
1224  ptr = ptr->list.next, deja = true) {
1225  if (deja) stream << " , ";
1226 
1227  stream << ptr->key() << "=>" << ptr->val();
1228  }
1229 
1230  stream << "]";
1231 
1232  return stream;
1233  }
1234 
1235  template < typename Key, typename Val, typename Alloc >
1236  std::ostream& operator<<(std::ostream& stream,
1237  const HashTable< Key, Val, Alloc >& table) {
1238  bool deja = false;
1239  stream << "{";
1240 
1241  for (Size i = 0; i < table.__size; ++i)
1242  for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
1243  if (deja) stream << " , ";
1244 
1245  stream << ptr->key() << "=>" << ptr->val();
1246 
1247  deja = true;
1248  }
1249 
1250  stream << "}";
1251 
1252  return stream;
1253  }
1254 
1255  template < typename Key, typename Val, typename Alloc >
1256  std::ostream& operator<<(std::ostream& stream,
1257  const HashTable< Key*, Val, Alloc >& table) {
1258  bool deja = false;
1259  stream << "{";
1260 
1261  for (Size i = 0; i < table.__size; ++i)
1262  for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
1263  if (deja) stream << " , ";
1264 
1265  stream << ptr->key() << "=>" << ptr->val();
1266 
1267  deja = true;
1268  }
1269 
1270  stream << "}";
1271 
1272  return stream;
1273  }
1274 
1275  // ===========================================================================
1276  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1277  // ===========================================================================
1278 
1279  template < typename Key, typename Val >
1280  INLINE void
1282  __table->__safe_iterators.push_back(
1283  const_cast< HashTableConstIteratorSafe< Key, Val >* >(this));
1284  }
1285 
1286  template < typename Key, typename Val >
1287  INLINE void
1289  if (__table == nullptr) return;
1290 
1291  // find where the iterator is
1292  std::vector< HashTableConstIteratorSafe< Key, Val >* >& iter_vect =
1293  __table->__safe_iterators;
1294 
1295  auto len = iter_vect.size();
1296  for (Size i = 0; i < len; ++i) {
1297  if (iter_vect[i] == this) {
1298  iter_vect.erase(iter_vect.begin() + i);
1299  break;
1300  }
1301  }
1302  }
1303 
1304  template < typename Key, typename Val >
1306  // for debugging purposes
1307  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1308  }
1309 
1310  template < typename Key, typename Val >
1311  template < typename Alloc >
1313  const HashTable< Key, Val, Alloc >& tab) :
1314  __table{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1315  // for debugging purposes
1316  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1317 
1318  // make the hashtable keep track of this iterator
1320 
1321  if (__table->__nb_elements) {
1322  if (__table->__begin_index != std::numeric_limits< Size >::max()) {
1324  __bucket = __table->__nodes[__index].__end_list;
1325  } else {
1326  // find the element we shall point to from the start of the hashtable
1327  for (unsigned int i = __table->__size - 1;; --i) { // no test on i since
1328  // __nb_elements != 0
1329  if (__table->__nodes[i].__nb_elements) {
1330  __index = i;
1331  __bucket = __table->__nodes[__index].__end_list;
1333  break;
1334  }
1335  }
1336  }
1337  }
1338  }
1339 
1340  template < typename Key, typename Val >
1341  template < typename Alloc >
1343  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1344  __table{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1345  Size i;
1346 
1347  // check if we are looking for a begin() and we know for sure its index
1348  if ((ind_elt == 0)
1349  && (__table->__begin_index != std::numeric_limits< Size >::max())) {
1351  __bucket = __table->__nodes[__index].__end_list;
1352  } else {
1353  // check if it is faster to find the ind_eltth element from the start or
1354  // from the end of the hashtable
1355  if (ind_elt < (__table->__nb_elements >> 1)) {
1356  // find the element we shall point to from the start of the hashtable
1357  for (i = __table->__size - 1;; --i) { // no test on i since
1358  // ind_elt < _table->__nb_elements
1359  if (__table->__nodes[i].__nb_elements) {
1360  if (ind_elt >= __table->__nodes[i].__nb_elements)
1361  ind_elt -= __table->__nodes[i].__nb_elements;
1362  else {
1363  for (__bucket = __table->__nodes[i].__end_list; ind_elt;
1364  --ind_elt, __bucket = __bucket->prev) {}
1365 
1366  __index = i;
1367  break;
1368  }
1369  }
1370  }
1371  } else {
1372  // ind_elt = the index of the element we should point to
1373  // check if the index passed as parameter is valid
1374  if (ind_elt >= __table->__nb_elements) {
1376  "Not enough elements in the hashtable");
1377  }
1378 
1379  // find the element we shall point to from the end of the hashtable
1380  for (i = 0, ind_elt = __table->__nb_elements - ind_elt - 1;; ++i) {
1381  if (__table->__nodes[i].__nb_elements) {
1382  if (ind_elt >= __table->__nodes[i].__nb_elements)
1383  ind_elt -= __table->__nodes[i].__nb_elements;
1384  else {
1385  for (__bucket = __table->__nodes[i].__deb_list; ind_elt;
1386  --ind_elt, __bucket = __bucket->next) {}
1387 
1388  __index = i;
1389  break;
1390  }
1391  }
1392  }
1393  }
1394  }
1395 
1396  // for debugging purposes
1397  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1398 
1399  // make the hashtable keep track of this iterator
1401  }
1402 
1403  template < typename Key, typename Val >
1406  __table{from.__table},
1407  __index{from.__index}, __bucket{from.__bucket}, __next_bucket{
1408  from.__next_bucket} {
1409  // make the hashtable keep track of this iterator
1410  if (__table != nullptr) { __insertIntoSafeList(); }
1411 
1412  // for debugging purposes
1413  GUM_CONS_CPY(HashTableConstIteratorSafe);
1414  }
1415 
1416  template < typename Key, typename Val >
1418  const HashTableConstIterator< Key, Val >& from) :
1419  __table{from.__table},
1420  __index{from.__index}, __bucket{from.__bucket} {
1421  // make the hashtable keep track of this iterator
1422  if (__table != nullptr) { __insertIntoSafeList(); }
1423 
1424  // for debugging purposes
1425  GUM_CONS_CPY(HashTableConstIteratorSafe);
1426  }
1427 
1428  template < typename Key, typename Val >
1431  __table{from.__table},
1432  __index{from.__index}, __bucket{from.__bucket}, __next_bucket{
1433  from.__next_bucket} {
1434  GUM_CONS_MOV(HashTableConstIteratorSafe);
1435 
1436  // find "from" in the hashtable's list of safe iterators and substitute
1437  // it by this
1438  if (__table != nullptr) {
1439  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect =
1441 
1442  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1443  if (*ptr == &from) {
1444  *ptr = this;
1445  from.__table = nullptr;
1446  break;
1447  }
1448  }
1449  }
1450  }
1451 
1452  template < typename Key, typename Val >
1453  INLINE
1456  // for debugging purposes
1457  GUM_DESTRUCTOR(HashTableConstIteratorSafe);
1458 
1459  // remove the iterator from the table's iterator list
1461  }
1462 
1463  template < typename Key, typename Val >
1466  // here, no need to avoid self assignment: this would slow down normal
1467  // assignments and, in any case, this would not result in an iterator in
1468  // an incoherent state
1469  // check if the current hashtable is different from that of "from". In such
1470  // a case, we shall remove the iterator from its current hashtable
1471  // iterator's
1472  // list and add it to the new hashtable iterator's list
1473  if (__table != from.__table) {
1474  // remove the iterator from its hashtable iterator's list'
1476 
1477  __table = from.__table;
1478 
1479  // add to the new table
1480  if (__table) { __insertIntoSafeList(); }
1481  }
1482 
1483  __index = from.__index;
1484  __bucket = from.__bucket;
1486 
1487  return *this;
1488  }
1489 
1490  template < typename Key, typename Val >
1493  // here, no need to avoid self assignment: this would slow down normal
1494  // assignments and, in any case, this would not result in an iterator in
1495  // an incoherent state
1496  // check if the current hashtable is different from that of "from". In such
1497  // a case, we shall remove the iterator from its current hashtable
1498  // iterator's
1499  // list and add it to the new hashtable iterator's list
1500  if (__table != from.__table) {
1501  // remove the iterator from its hashtable iterator's list'
1503 
1504  __table = from.__table;
1505 
1506  // add to the new table
1507  if (__table) { __insertIntoSafeList(); }
1508  }
1509 
1510  __index = from.__index;
1511  __bucket = from.__bucket;
1512  __next_bucket = nullptr;
1513 
1514  return *this;
1515  }
1516 
1517  template < typename Key, typename Val >
1521  // here, no need to avoid self assignment: this would slow down normal
1522  // assignments and, in any case, this would not result in an iterator in
1523  // an incoherent state
1524  // check if the current hashtable is different from that of "from". In such
1525  // a case, we shall remove the iterator from its current hashtable
1526  // iterator's
1527  // list and add it to the new hashtable iterator's list
1528  if (__table != from.__table) {
1529  // remove the iterator from its hashtable iterator's list'
1531 
1532  if (from.__table != nullptr) {
1533  // substitute from by this in the list of safe iterators
1534  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect =
1535  from.__table->__safe_iterators;
1536 
1537  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1538  if (*ptr == &from) {
1539  *ptr = this;
1540  break;
1541  }
1542  }
1543  }
1544 
1545  __table = from.__table;
1546  from.__table = nullptr;
1547  }
1548 
1549  __index = from.__index;
1550  __bucket = from.__bucket;
1551  __next_bucket = from.__next_bucket;
1552 
1553  return *this;
1554  }
1555 
1556  template < typename Key, typename Val >
1559  if (__bucket)
1560  return __bucket->key();
1561  else {
1562  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1563  }
1564  }
1565 
1566  template < typename Key, typename Val >
1569  if (__bucket)
1570  return __bucket->val();
1571  else {
1572  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1573  }
1574  }
1575 
1576  template < typename Key, typename Val >
1578  // remove the iterator from the table's iterator list
1580 
1581  // set its table as well as the element it points to to 0
1582  __table = nullptr;
1583  __bucket = nullptr;
1584  __next_bucket = nullptr;
1585  __index = 0;
1586  }
1587 
1588  // WARNING: never inline this function: this result in g++4.3.3 producing a
1589  // code that segfaults.
1590  template < typename Key, typename Val >
1592  operator++() noexcept {
1593  // if __bucket != nullptr then use it, else use next_bucket
1594  if (__bucket == nullptr) {
1595  // note that this case only happens when the iterator pointed to an
1596  // element
1597  // that has just been erased. Fortunately, in this case, the Hashtable's
1598  // erase functions update appropriately the __next_bucket and __index
1599  // fields.
1601  __next_bucket = nullptr;
1602  } else {
1603  // ok, here we can use __bucket as a starting point
1604 
1605  // if we are not pointing on the first element of the chained list, just
1606  // point to the preceding bucket in this list
1607  if (__bucket->prev) {
1608  __bucket = __bucket->prev;
1609  // here, no need to update __next_bucket, which is compulsorily
1610  // equal to nullptr, nor __index which has not changed.
1611  } else {
1612  // ok, here we are on the beginning of a chained list,
1613  // so 2 cases can obtain:
1614  // 1/ index = 0 : then we have reached the end of the hashtable
1615  // 2/ index != 0 => we must search for a new slot containing elements
1616 
1617  // case 1:
1618  if (__index == 0) {
1619  __bucket = nullptr;
1620  // we are thus at the end() of the hashTable
1621  }
1622  // case 2:
1623  else {
1624  // arrived here, we need to parse the hash table until we find a new
1625  // bucket because we are pointing on a chained list with no more
1626  // element
1627  // to the left of the current element
1628  if (__index > 0) {
1629  for (Size i = __index - 1; i > 0; --i) {
1630  if (__table->__nodes[i].__nb_elements) {
1631  __index = i;
1632  __bucket = __table->__nodes[i].__end_list;
1633  return *this;
1634  }
1635  }
1636  }
1637 
1638  if (__table->__nodes[0].__nb_elements)
1639  __bucket = __table->__nodes[0].__end_list;
1640  else
1641  __bucket = nullptr;
1642 
1643  __index = 0;
1644  }
1645  }
1646  }
1647 
1648  return *this;
1649  }
1650 
1651  template < typename Key, typename Val >
1653  operator+=(unsigned int nb) noexcept {
1654  if ((nb == 0) || (__table == nullptr)) return *this;
1655 
1656  // if __bucket != nullptr then use it, else use next_bucket
1657  if (__bucket == nullptr) {
1658  // note that this case only happens when the iterator pointed to an
1659  // element
1660  // that has just been erased. Fortunately, in this case, the Hashtable's
1661  // erase functions update appropriately the __next_bucket and __index
1662  // fields.
1664  __next_bucket = nullptr;
1665  --nb;
1666  }
1667 
1668  // ok, here we can use __bucket as a starting point: parse all the elements
1669  // of the current chained list
1670  for (; nb && __bucket != nullptr; --nb, __bucket = __bucket->prev) {}
1671 
1672  if (__bucket != nullptr) return *this;
1673 
1674  // here, we shall skip all the chained list that have not sufficiently
1675  // many elements
1676  --__index;
1677 
1678  for (; __index < __table->__size
1679  && nb >= __table->__nodes[__index].__nb_elements;
1680  nb -= __table->__nodes[__index].__nb_elements, --__index) {}
1681 
1682  // here: either __index >= __table->__size, which means that we did not find
1683  // the element we looked for, i.e., we are at the end of the hashtable, or
1684  // nb < __table->__nodes[__index].__nb_elements, and we should parse the
1685  // chained list to get the element (which, we know for sure, exists)
1686  if (__index >= __table->__size) {
1687  __index = 0;
1688  return *this;
1689  }
1690 
1691  for (__bucket = __table->__nodes[__index].__end_list; nb;
1692  --nb, __bucket = __bucket->prev) {}
1693 
1694  return *this;
1695  }
1696 
1697  template < typename Key, typename Val >
1700  return HashTableConstIteratorSafe< Key, Val >{*this} += nb;
1701  }
1702 
1703  template < typename Key, typename Val >
1706  return ((__bucket != from.__bucket) || (__index != from.__index));
1707  }
1708 
1709  template < typename Key, typename Val >
1712  return ((__bucket == from.__bucket) && (__index == from.__index));
1713  }
1714 
1715  template < typename Key, typename Val >
1718  if (__bucket)
1719  return __bucket->elt();
1720  else {
1721  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1722  }
1723  }
1724 
1725  template < typename Key, typename Val >
1728  return __bucket;
1729  }
1730 
1731  template < typename Key, typename Val >
1733  return __index;
1734  }
1735 
1736  // ===========================================================================
1737  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1738  // ===========================================================================
1739 
1740  template < typename Key, typename Val >
1742  HashTableConstIteratorSafe< Key, Val >() {
1743  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1744  }
1745 
1746  template < typename Key, typename Val >
1747  template < typename Alloc >
1749  const HashTable< Key, Val, Alloc >& tab) :
1750  HashTableConstIteratorSafe< Key, Val >(tab) {
1751  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1752  }
1753 
1754  template < typename Key, typename Val >
1755  template < typename Alloc >
1757  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1758  HashTableConstIteratorSafe< Key, Val >(tab, ind_elt) {
1759  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1760  }
1761 
1762  template < typename Key, typename Val >
1764  const HashTableIteratorSafe< Key, Val >& from) :
1765  HashTableConstIteratorSafe< Key, Val >(from) {
1766  GUM_CONS_CPY(HashTableIteratorSafe);
1767  }
1768 
1769  template < typename Key, typename Val >
1771  const HashTableIterator< Key, Val >& from) :
1772  HashTableConstIteratorSafe< Key, Val >(from) {
1773  GUM_CONS_CPY(HashTableIteratorSafe);
1774  }
1775 
1776  template < typename Key, typename Val >
1778  HashTableIteratorSafe< Key, Val >&& from) noexcept :
1779  HashTableConstIteratorSafe< Key, Val >(std::move(from)) {
1780  GUM_CONS_MOV(HashTableIteratorSafe);
1781  }
1782 
1783  template < typename Key, typename Val >
1785  GUM_DESTRUCTOR(HashTableIteratorSafe);
1786  }
1787 
1788  template < typename Key, typename Val >
1791  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::val());
1792  }
1793 
1794  template < typename Key, typename Val >
1797  GUM_OP_CPY(HashTableIteratorSafe);
1799  return *this;
1800  }
1801 
1802  template < typename Key, typename Val >
1805  GUM_OP_CPY(HashTableIteratorSafe);
1807  return *this;
1808  }
1809 
1810  template < typename Key, typename Val >
1814  return *this;
1815  }
1816 
1817  template < typename Key, typename Val >
1819  operator++() noexcept {
1821  return *this;
1822  }
1823 
1824  template < typename Key, typename Val >
1826  operator+=(unsigned int nb) noexcept {
1828  return *this;
1829  }
1830 
1831  template < typename Key, typename Val >
1833  operator+(unsigned int nb) const {
1835  iter += nb;
1836  return iter;
1837  }
1838 
1839  template < typename Key, typename Val >
1841  operator!=(const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1843  }
1844 
1845  template < typename Key, typename Val >
1847  operator==(const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1849  }
1850 
1851  template < typename Key, typename Val >
1854  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::operator*());
1855  }
1856 
1857  template < typename Key, typename Val >
1858  INLINE const typename HashTableIteratorSafe< Key, Val >::value_type&
1861  }
1862 
1863  // ===========================================================================
1864  // === UNSAFE HASH TABLE CONST ITERATORS IMPLEMENTATION ===
1865  // ===========================================================================
1866 
1867  template < typename Key, typename Val >
1869  GUM_CONSTRUCTOR(HashTableConstIterator);
1870  }
1871 
1872  template < typename Key, typename Val >
1873  template < typename Alloc >
1875  const HashTable< Key, Val, Alloc >& tab) noexcept :
1876  __table{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1877  // for debugging purposes
1878  GUM_CONSTRUCTOR(HashTableConstIterator);
1879 
1880  if (__table->__nb_elements) {
1881  if (__table->__begin_index != std::numeric_limits< Size >::max()) {
1883  __bucket = __table->__nodes[__index].__end_list;
1884  } else {
1885  // find the element we shall point to from the start of the hashtable
1886  for (unsigned int i = __table->__size - 1;; --i) { // no test on i since
1887  // __nb_elements != 0
1888  if (__table->__nodes[i].__nb_elements) {
1889  __index = i;
1890  __bucket = __table->__nodes[__index].__end_list;
1892  break;
1893  }
1894  }
1895  }
1896  }
1897  }
1898 
1899  template < typename Key, typename Val >
1900  template < typename Alloc >
1902  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1903  __table{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1904  Size i;
1905 
1906  // check if we are looking for a begin() and we know for sure its index
1907  if ((ind_elt == 0)
1908  && (__table->__begin_index != std::numeric_limits< Size >::max())) {
1910  __bucket = __table->__nodes[__index].__end_list;
1911  } else {
1912  // check if it is faster to find the ind_eltth element from the start or
1913  // from the end of the hashtable
1914  if (ind_elt < (__table->__nb_elements >> 1)) {
1915  // find the element we shall point to from the start of the hashtable
1916  for (i = __table->__size - 1;; --i) { // no test on i since
1917  // ind_elt < _table->__nb_elements
1918  if (__table->__nodes[i].__nb_elements) {
1919  if (ind_elt >= __table->__nodes[i].__nb_elements)
1920  ind_elt -= __table->__nodes[i].__nb_elements;
1921  else {
1922  for (__bucket = __table->__nodes[i].__end_list; ind_elt;
1923  --ind_elt, __bucket = __bucket->prev) {}
1924 
1925  __index = i;
1926  break;
1927  }
1928  }
1929  }
1930  } else {
1931  // ind_elt = the index of the element we should point to
1932  // check if the index passed as parameter is valid
1933  if (ind_elt >= __table->__nb_elements) {
1935  "Not enough elements in the hashtable");
1936  }
1937 
1938  // find the element we shall point to from the end of the hashtable
1939  for (i = 0, ind_elt = __table->__nb_elements - ind_elt - 1;; ++i) {
1940  if (__table->__nodes[i].__nb_elements) {
1941  if (ind_elt >= __table->__nodes[i].__nb_elements)
1942  ind_elt -= __table->__nodes[i].__nb_elements;
1943  else {
1944  for (__bucket = __table->__nodes[i].__deb_list; ind_elt;
1945  --ind_elt, __bucket = __bucket->next) {}
1946 
1947  __index = i;
1948  break;
1949  }
1950  }
1951  }
1952  }
1953  }
1954 
1955  // for debugging purposes
1956  GUM_CONSTRUCTOR(HashTableConstIterator);
1957  }
1958 
1959  template < typename Key, typename Val >
1961  const HashTableConstIterator< Key, Val >& from) noexcept :
1962  __table{from.__table},
1963  __index{from.__index}, __bucket{from.__bucket} {
1964  GUM_CONS_CPY(HashTableConstIterator);
1965  }
1966 
1967  template < typename Key, typename Val >
1969  HashTableConstIterator< Key, Val >&& from) noexcept :
1970  __table{from.__table},
1971  __index{from.__index}, __bucket{from.__bucket} {
1972  GUM_CONS_MOV(HashTableConstIterator);
1973  }
1974 
1975  template < typename Key, typename Val >
1977  // for debugging purposes
1978  GUM_DESTRUCTOR(HashTableConstIterator);
1979  }
1980 
1981  template < typename Key, typename Val >
1984  // here, no need to avoid self assignment: this would slow down normal
1985  // assignments and, in any case, this would not result in an iterator in
1986  // an incoherent state
1987  __table = from.__table;
1988  __index = from.__index;
1989  __bucket = from.__bucket;
1990 
1991  return *this;
1992  }
1993 
1994  template < typename Key, typename Val >
1997  // here, no need to avoid self assignment: this would slow down normal
1998  // assignments and, in any case, this would not result in an iterator in
1999  // an incoherent state
2000  __table = from.__table;
2001  __index = from.__index;
2002  __bucket = from.__bucket;
2003 
2004  return *this;
2005  }
2006 
2007  template < typename Key, typename Val >
2008  INLINE const typename HashTableConstIterator< Key, Val >::key_type&
2010  if (__bucket)
2011  return __bucket->pair.first;
2012  else {
2013  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2014  }
2015  }
2016 
2017  template < typename Key, typename Val >
2020  if (__bucket)
2021  return __bucket->val();
2022  else {
2023  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2024  }
2025  }
2026 
2027  template < typename Key, typename Val >
2029  __table = nullptr;
2030  __bucket = nullptr;
2031  __index = 0;
2032  }
2033 
2034  template < typename Key, typename Val >
2036  operator++() noexcept {
2037  // if __bucket == nullptr then we are at the end of the hashtable
2038  if (__bucket == nullptr) return *this;
2039 
2040  // if we are not pointing on the first element of the chained list, just
2041  // point to the next bucket in this list
2042  if (__bucket->prev) {
2043  __bucket = __bucket->prev;
2044  // here, no need to update __index which has not changed.
2045  } else {
2046  // ok, here we are on the end of a chained list,
2047  // so 2 cases can obtain:
2048  // 1/ index = 0 : then we have reached the end of the hashtable
2049  // 2/ index != 0 => we must search for a new slot containing elements
2050 
2051  // case 1:
2052  if (!__index) {
2053  __bucket = nullptr;
2054  // we are thus at the end() of the hashTable
2055  }
2056 
2057  // case 2:
2058  else {
2059  // arrived here, we need to parse the hash table until we find a new
2060  // bucket because we are pointing on a chained list with no more element
2061  // to the right of the current element
2062  for (Size i = __index - 1UL; i; --i) {
2063  if (__table->__nodes[i].__nb_elements) {
2064  __index = i;
2065  __bucket = __table->__nodes[i].__end_list;
2066  return *this;
2067  }
2068  }
2069 
2070  if (__table->__nodes[0].__nb_elements)
2071  __bucket = __table->__nodes[0].__end_list;
2072  else
2073  __bucket = nullptr;
2074 
2075  __index = 0;
2076  }
2077  }
2078 
2079  return *this;
2080  }
2081 
2082  template < typename Key, typename Val >
2084  operator+=(unsigned int nb) noexcept {
2085  if ((nb == 0) || (__table == nullptr) || (__bucket == nullptr)) return *this;
2086 
2087  // ok, here we can use __bucket as a starting point: parse all the elements
2088  // of the current chained list
2089  for (; nb && __bucket != nullptr; --nb, __bucket = __bucket->prev) {}
2090 
2091  if (__bucket != nullptr) return *this;
2092 
2093  // here, we shall skip all the chained list that have not sufficiently
2094  // many elements
2095  --__index;
2096 
2097  for (; __index < __table->__size
2098  && nb >= __table->__nodes[__index].__nb_elements;
2099  nb -= __table->__nodes[__index].__nb_elements, --__index) {}
2100 
2101  // here: either __index >= __table->__size, which means that we did not find
2102  // the element we looked for, i.e., we are at the end of the hashtable, or
2103  // nb < __table->__nodes[__index].__nb_elements, and we should parse the
2104  // chained list to get the element (which, we know for sure, exists)
2105  if (__index >= __table->__size) {
2106  __index = 0;
2107  return *this;
2108  }
2109 
2110  for (__bucket = __table->__nodes[__index].__end_list; nb;
2111  --nb, __bucket = __bucket->prev) {}
2112 
2113  return *this;
2114  }
2115 
2116  template < typename Key, typename Val >
2118  operator+(unsigned int nb) const noexcept {
2119  return HashTableConstIterator< Key, Val >{*this} += nb;
2120  }
2121 
2122  template < typename Key, typename Val >
2125  return (__bucket != from.__bucket);
2126  }
2127 
2128  template < typename Key, typename Val >
2131  return (__bucket == from.__bucket);
2132  }
2133 
2134  template < typename Key, typename Val >
2135  INLINE const typename HashTableConstIterator< Key, Val >::value_type&
2137  if (__bucket)
2138  return __bucket->elt();
2139  else {
2140  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2141  }
2142  }
2143 
2144  template < typename Key, typename Val >
2145  INLINE typename HashTable< Key, Val >::Bucket*
2147  return __bucket;
2148  }
2149 
2150  template < typename Key, typename Val >
2152  return __index;
2153  }
2154 
2155  // ===========================================================================
2156  // === UNSAFE HASH TABLE ITERATORS IMPLEMENTATION ===
2157  // ===========================================================================
2158 
2159  template < typename Key, typename Val >
2161  HashTableConstIterator< Key, Val >() {
2162  GUM_CONSTRUCTOR(HashTableIterator);
2163  }
2164 
2165  template < typename Key, typename Val >
2166  template < typename Alloc >
2168  const HashTable< Key, Val, Alloc >& tab) noexcept :
2170  GUM_CONSTRUCTOR(HashTableIterator);
2171  }
2172 
2173  template < typename Key, typename Val >
2174  template < typename Alloc >
2176  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
2177  HashTableConstIterator< Key, Val >(tab, ind_elt) {
2178  GUM_CONSTRUCTOR(HashTableIterator);
2179  }
2180 
2181  template < typename Key, typename Val >
2183  const HashTableIterator< Key, Val >& from) noexcept :
2185  GUM_CONS_CPY(HashTableIterator);
2186  }
2187 
2188  template < typename Key, typename Val >
2190  HashTableIterator< Key, Val >&& from) noexcept :
2191  HashTableConstIterator< Key, Val >(std::move(from)) {
2192  GUM_CONS_MOV(HashTableIterator);
2193  }
2194 
2195  template < typename Key, typename Val >
2197  GUM_DESTRUCTOR(HashTableIterator);
2198  }
2199 
2200  template < typename Key, typename Val >
2203  if (this->__bucket)
2204  return this->__bucket->val();
2205  else {
2206  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2207  }
2208  }
2209 
2210  template < typename Key, typename Val >
2214  return *this;
2215  }
2216 
2217  template < typename Key, typename Val >
2221  return *this;
2222  }
2223 
2224  template < typename Key, typename Val >
2226  operator++() noexcept {
2228  return *this;
2229  }
2230 
2231  template < typename Key, typename Val >
2233  operator+=(unsigned int nb) noexcept {
2235  return *this;
2236  }
2237 
2238  template < typename Key, typename Val >
2240  operator+(unsigned int nb) const noexcept {
2241  HashTableIterator< Key, Val > iter{*this};
2242  iter += nb;
2243  return iter;
2244  }
2245 
2246  template < typename Key, typename Val >
2248  operator!=(const HashTableIterator< Key, Val >& from) const noexcept {
2250  }
2251 
2252  template < typename Key, typename Val >
2254  operator==(const HashTableIterator< Key, Val >& from) const noexcept {
2256  }
2257 
2258  template < typename Key, typename Val >
2261  return const_cast< value_type& >(
2263  }
2264 
2265  template < typename Key, typename Val >
2266  INLINE const typename HashTableIterator< Key, Val >::value_type&
2269  }
2270 
2271 } /* namespace gum */
bool operator==(const HashTableConstIterator< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward equal elements.
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
iterator begin()
Returns an unsafe iterator pointing to the beginning of the hashtable.
void __insert(Bucket *bucket)
Adds a new element (actually a copy of this element) in the hash table.
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
~HashTable()
Class destructor.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
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
HashTableIteratorSafe< Key, Val > & operator++() noexcept
Makes the iterator point to the next element in the hash table.
HashTableConstIterator< Key, Val > & operator++() noexcept
Makes the iterator point to the next element in the hash table.
static const iterator_safe & endSafe4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse H...
Definition: hashTable.h:2462
const iterator & end() noexcept
Returns the unsafe iterator pointing to the end of the hashtable.
~HashTableConstIterator() noexcept
Class destructor.
const iterator_safe & endSafe() noexcept
Returns the safe iterator pointing to the end of the hashtable.
Val & operator[](const Key &key)
Returns a reference on the value the key of which is passed in argument.
HashTableConstIteratorSafe< Key, Val > & operator++() noexcept
Makes the iterator point to the next element in the hash table.
HashTableIterator< Key, Val > & operator=(const HashTableIterator< Key, Val > &from) noexcept
Copy operator.
HashTable< Key, Val, Alloc > & operator=(const HashTable< Key, Val, Alloc > &from)
Copy operator.
void __removeFromSafeList() const
Removes the iterator from its hashtable&#39; safe iterators list.
A recipient for a pair of key value in a gum::HashTableList.
Definition: hashTable.h:199
value_type & at(unsigned int i)
Function at returns the ith element in the current chained list.
Size size() const noexcept
Returns the number of elements stored into the hashtable.
bool operator==(const HashTable< Key, Val, OtherAlloc > &from) const
Checks whether two hashtables contain the same elements.
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:1921
HashTableConstIteratorSafe< Key, Val > operator+(unsigned int i) const
Returns a new iterator poiting to i elements further in the hashtable.
static const const_iterator & constEnd4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
BucketAllocator __alloc
The allocator for the buckets.
Definition: hashTable.h:1760
const value_type & operator*() const
Returns the value pointed to by the iterator.
void erase(const Key &key)
Removes a given element from the hash table.
~HashTableList()
Class destructor.
Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables...
Definition: hashTable.h:2747
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
value_type & operator*()
Returns the value pointed to by the iterator.
bool operator!=(const HashTableIteratorSafe< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward different elements.
void clear()
Removes all the elements of this chained list.
HashFunc< Key > __hash_func
The function used to hash keys (may change when the table is resized).
Definition: hashTable.h:1724
Safe Const Iterators for hashtables.
Definition: hashTable.h:1915
void erase(Bucket *ptr)
Removes an element from this chained list.
STL namespace.
void setResizePolicy(const bool new_policy) noexcept
Enables the user to change dynamically the resizing policy.
bool resizePolicy() const noexcept
Returns the current resizing policy.
Bucket * bucket(const Key &key) const
A method to get the bucket corresponding to a given key.
Definition: hashTable_tpl.h:98
bool operator==(const HashTableIteratorSafe< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward equal elements.
HashTableConstIteratorSafe()
Basic constructor: creates an iterator pointing to nothing.
HashTableBucket< Key, Val > * __getBucket() const noexcept
Returns the current iterator&#39;s bucket.
const value_type & operator*() const
Returns the element pointed to by the iterator.
Size __size
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1718
const key_type & key() const
Returns the key corresponding to the element pointed to by the iterator.
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
static const HashTableIterator< int, int > * __HashTableIterEnd
The unsafe iterator used by everyone.
Definition: hashTable.h:1831
void insert(Bucket *new_elt) noexcept
Inserts a new element in the chained list.
void clear() noexcept
Makes the iterator point toward nothing (in particular, it is not related anymore to its current hash...
HashTableIterator() noexcept
Basic constructor: creates an iterator pointing to nothing.
Safe Iterators for hashtables.
Definition: hashTable.h:2217
friend std::ostream & operator<<(std::ostream &, const HashTable< Key, Val, Alloc > &)
Prints the content of a gum::HashTable in the stream.
std::vector< HashTableList< Key, Val, Alloc > > __nodes
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1715
~HashTableIteratorSafe() noexcept
Class destructor.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
bool operator!=(const HashTable< Key, Val, OtherAlloc > &from) const
Checks whether two hashtables contain different sets of elements.
static const HashTableConstIteratorSafe< int, int > * constEndSafe4Statics()
Creates (if needed) and returns the iterator __HashTableIterEndSafe.
Size __getIndex() const noexcept
Returns the index in the hashtable&#39;s node vector pointed to by the iterator.
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
HashTable< Key, Mount, OtherAlloc > map(Mount(*f)(Val), Size size=0, bool resize_pol=HashTableConst::default_resize_policy, bool key_uniqueness_pol=HashTableConst::default_uniqueness_policy) const
Transforms a hashtable of vals into a hashtable of mountains.
const Key & key(const Key &key) const
Returns a reference on a given key.
bool exists(const key_type &key) const
Returns true if a value with the given key exists.
~HashTableConstIteratorSafe() noexcept
Destructor.
HashTableIteratorSafe< Key, Val > & operator=(const HashTableIteratorSafe< Key, Val > &from)
Copy operator.
std::vector< HashTableConstIteratorSafe< Key, Val > * > __safe_iterators
The list of safe iterators pointing to the hash table.
Definition: hashTable.h:1750
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
bool operator!=(const HashTableConstIteratorSafe< Key, Val > &from) const noexcept
Checks whether two iterators are not equal.
void __create(Size size)
Used by all default constructors (general and specialized).
const_iterator cbegin() const
Returns an unsafe const_iterator pointing to the beginning of the hashtable.
HashTableConstIterator< Key, Val > & operator=(const HashTableConstIterator< Key, Val > &from) noexcept
Copy operator.
Size __nb_elements
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1721
static const HashTableIterator< int, int > * end4Statics()
Creates (if needed) and returns the iterator __HashTableIterEnd.
Key key_type
Types for STL compliance.
Definition: hashTable.h:2467
bool empty() const noexcept
Returns true if this chained list is empty.
friend class HashTable
Friends to optimize the access to data, iterators must be friends.
Definition: hashTable.h:1695
bool operator==(const HashTableIterator< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward equal elements.
mapped_type & getWithDefault(const Key &key, const Val &default_value)
Returns a reference on the element the key of which is passed in argument.
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
void reset(const Key &key)
Removes a property (i.e., remove an element).
value_type & emplace(Args &&...args)
Emplace a new element into the hashTable.
const const_iterator_safe & cendSafe() const noexcept
Returns the safe const_iterator pointing to the end of the hashtable.
static const HashTableIteratorSafe< int, int > * endSafe4Statics()
Creates (if needed) and returns the iterator __HashTableIterEndSafe.
mapped_type & val()
Returns the mapped value pointed to by the iterator.
HashTableIterator< Key, Val > operator+(unsigned int i) const noexcept
Returns a new iterator.
HashTableBucket< Key, Val > * __bucket
The bucket in the chained list pointed to by the iterator.
Definition: hashTable.h:2132
static const HashTableIteratorSafe< int, int > * __HashTableIterEndSafe
The safe iterator used by everyone.
Definition: hashTable.h:1834
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:2468
bool operator!=(const HashTableConstIterator< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward different elements.
~HashTableIterator() noexcept
Class destructor.
Val mapped_type
types for STL compliance
Definition: hashTable.h:2753
HashTableConstIteratorSafe< Key, Val > & operator+=(unsigned int i) noexcept
Makes the iterator point to i elements further in the hashtable.
const const_iterator & cend() const noexcept
Returns the unsafe const_iterator pointing to the end of the hashtable.
void __clearIterators()
Clear all the safe iterators.
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
HashTableIterator< Key, Val > & operator++() noexcept
Makes the iterator point to the next element in the hash table.
void set(const Key &key, const Val &default_value)
Add a new property or modify it if it already existed.
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:681
HashTableConstIteratorSafe< Key, Val > & operator=(const HashTableConstIteratorSafe< Key, Val > &from)
Copy operator.
void __insertIntoSafeList() const
Insert the iterator into the hashtable&#39;s list of safe iterators.
HashTableList< Key, Val, Alloc > & operator=(const HashTableList< Key, Val, Alloc > &from)
Assignment operator.
const mapped_type & val() const
Returns the mapped value pointed to by the iterator.
HashTableIteratorSafe()
Basic constructor: creates an iterator pointing to nothing.
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:2223
bool keyUniquenessPolicy() const noexcept
Returns the current checking policy.
HashTable< Key, Val >::Bucket * __bucket
The bucket in the chained list pointed to by the iterator.
Definition: hashTable.h:2678
const Key & keyByVal(const Val &val) const
Returns a reference on the key given a value.
HashTableConstIterator< Key, Val > & operator+=(unsigned int i) noexcept
Makes the iterator point to i elements further in the hashtable.
Val mapped_type
types for STL compliance
Definition: hashTable.h:307
value_type & operator*()
Returns the value pointed to by the iterator.
Size capacity() const noexcept
Returns the number of slots in the &#39;nodes&#39; vector of the hashtable.
HashTableIterator< Key, Val > & operator+=(unsigned int i) noexcept
Makes the iterator point to i elements further in the hashtable.
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
void __erase(HashTableBucket< Key, Val > *bucket, Size index)
Erases a given bucket.
HashTableBucket< Key, Val > * next
A pointer toward the next bucket in the gum::HashTableList.
Definition: hashTable.h:207
static const iterator & end4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
std::pair< const Key, Val > value_type
Types for STL compliance.
Definition: hashTable.h:2469
bool operator==(const HashTableConstIteratorSafe< Key, Val > &from) const noexcept
Checks whether two iterators are equal.
const HashTable< Key, Val > * __table
The hash table the iterator is pointing to.
Definition: hashTable.h:2123
unsigned int __hashTableLog2(const Size &nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater or equal to nb...
void clear()
Removes all the elements in the hash table.
iterator_safe beginSafe()
Returns the safe iterator pointing to the beginning of the hashtable.
mapped_type & operator[](const key_type &key)
Returns the value corresponding to a given key.
unsigned int __nb_elements
The number of elements in the chained list.
Definition: hashTable.h:537
A chained list used by gum::HashTable.
Definition: hashTable.h:302
void eraseAllVal(const Val &val)
Removes all the elements having a certain value from the hash table.
static const const_iterator_safe & constEndSafe4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
static const HashTableConstIterator< int, int > * constEnd4Statics()
Creates (if needed) and returns the iterator __HashTableIterEnd.
HashTable< Key, Val >::Bucket * __getBucket() const noexcept
Returns the current iterator&#39;s bucket.
HashTableBucket< Key, Val > * __end_list
A pointer on the last element of the chained list.
Definition: hashTable.h:534
void setKeyUniquenessPolicy(const bool new_policy) noexcept
Enables the user to change dynamically the policy for checking whether there can exist several elemen...
void clear() noexcept
Makes the iterator point toward nothing (in particular, it is not related anymore to its current hash...
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
HashTableConstIterator< Key, Val > operator+(unsigned int i) const noexcept
Returns a new iterator pointing to i elements further in the hashtable.
void __copy(const HashTable< Key, Val, OtherAlloc > &table)
A function used to perform copies of HashTables.
HashTableIteratorSafe< Key, Val > operator+(unsigned int i) const
Returns a new iterator pointing to i elements further in the hashtable.
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
HashTableIteratorSafe< Key, Val > & operator+=(unsigned int i) noexcept
Makes the iterator point to i elements further in the hashtable.
HashTableBucket< Key, Val > * __next_bucket
the bucket we should start from when we decide to do a ++.
Definition: hashTable.h:2142
bool operator!=(const HashTableIterator< Key, Val > &from) const noexcept
Checks whether two iterators are pointing toward different elements.
bool empty() const noexcept
Indicates whether the hash table is empty.
void eraseByVal(const Val &val)
Removes a given element from the hash table.
typename Alloc::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:319
void setAllocator(BucketAllocator &alloc)
Sets a new allocator.
static constexpr unsigned int default_mean_val_by_slot
The average number of elements admissible by slots.
Definition: hashTable.h:84
Class hash tables iterators.
const_iterator_safe cbeginSafe() const
Returns the safe const_iterator pointing to the beginning of the hashtable.
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:66
const key_type & key() const
Returns the key pointed to by the iterator.
HashTableConstIterator() noexcept
Basic constructor: creates an iterator pointing to nothing.
std::pair< const Key, Val > value_type
types for STL compliance
Definition: hashTable.h:2754
const mapped_type & val() const
Returns the mapped value pointed to by the iterator.