Nugget
hashtable.h
1 // Copyright (c) Electronic Arts Inc. All rights reserved.
4 
6 // This file implements a hashtable, much like the C++11 unordered_set/unordered_map.
7 // proposed classes.
8 // The primary distinctions between this hashtable and C++11 unordered containers are:
9 // - hashtable is savvy to an environment that doesn't have exception handling,
10 // as is sometimes the case with console or embedded environments.
11 // - hashtable is slightly more space-efficient than a conventional std hashtable
12 // implementation on platforms with 64 bit size_t. This is
13 // because std STL uses size_t (64 bits) in data structures whereby 32 bits
14 // of data would be fine.
15 // - hashtable can contain objects with alignment requirements. TR1 hash tables
16 // cannot do so without a bit of tedious non-portable effort.
17 // - hashtable supports debug memory naming natively.
18 // - hashtable provides a find function that lets you specify a type that is
19 // different from the hash table key type. This is particularly useful for
20 // the storing of string objects but finding them by char pointers.
21 // - hashtable provides a lower level insert function which lets the caller
22 // specify the hash code and optionally the node instance.
24 
25 
26 #ifndef EASTL_INTERNAL_HASHTABLE_H
27 #define EASTL_INTERNAL_HASHTABLE_H
28 
29 
30 #include <EABase/eabase.h>
31 #if defined(EA_PRAGMA_ONCE_SUPPORTED)
32  #pragma once
33 #endif
34 
35 #include <EASTL/internal/config.h>
36 #include <EASTL/type_traits.h>
37 #include <EASTL/allocator.h>
38 #include <EASTL/iterator.h>
39 #include <EASTL/functional.h>
40 #include <EASTL/utility.h>
41 #include <EASTL/algorithm.h>
42 #include <EASTL/initializer_list.h>
43 #include <EASTL/tuple.h>
44 #include <string.h>
45 
46 EA_DISABLE_ALL_VC_WARNINGS()
47  #include <new>
48  #include <stddef.h>
49 EA_RESTORE_ALL_VC_WARNINGS()
50 
51 // 4512 - 'class' : assignment operator could not be generated.
52 // 4530 - C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
53 // 4571 - catch(...) semantics changed since Visual C++ 7.1; structured exceptions (SEH) are no longer caught.
54 EA_DISABLE_VC_WARNING(4512 4530 4571);
55 
56 
57 namespace eastl
58 {
59 
64  #ifndef EASTL_HASHTABLE_DEFAULT_NAME
65  #define EASTL_HASHTABLE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hashtable" // Unless the user overrides something, this is "EASTL hashtable".
66  #endif
67 
68 
71  #ifndef EASTL_HASHTABLE_DEFAULT_ALLOCATOR
72  #define EASTL_HASHTABLE_DEFAULT_ALLOCATOR allocator_type(EASTL_HASHTABLE_DEFAULT_NAME)
73  #endif
74 
75 
78  enum { kHashtableAllocFlagBuckets = 0x00400000 };
79 
80 
87  extern EASTL_API void* gpEmptyBucketArray[2];
88 
89 
94  #define EASTL_MACRO_SWAP(Type, a, b) \
95  { Type temp = a; a = b; b = temp; }
96 
97 
106  template <typename Value, bool bCacheHashCode>
107  struct hash_node;
108 
109  EA_DISABLE_VC_WARNING(4625 4626) // "copy constructor / assignment operator could not be generated because a base class copy constructor is inaccessible or deleted"
110  #ifdef EA_COMPILER_MSVC_2015
111  EA_DISABLE_VC_WARNING(5026) // disable warning: "move constructor was implicitly defined as deleted"
112  #endif
113  template <typename Value>
114  struct hash_node<Value, true>
115  {
116  hash_node() = default;
117  hash_node(const hash_node&) = default;
118  hash_node(hash_node&&) = default;
119 
120  Value mValue;
121  hash_node* mpNext;
122  eastl_size_t mnHashCode; // See config.h for the definition of eastl_size_t, which defaults to size_t.
123  } EASTL_MAY_ALIAS;
124 
125  template <typename Value>
126  struct hash_node<Value, false>
127  {
128  hash_node() = default;
129  hash_node(const hash_node&) = default;
130  hash_node(hash_node&&) = default;
131 
132  Value mValue;
133  hash_node* mpNext;
134  } EASTL_MAY_ALIAS;
135 
136  #ifdef EA_COMPILER_MSVC_2015
137  EA_RESTORE_VC_WARNING()
138  #endif
139  EA_RESTORE_VC_WARNING()
140 
141 
142  // has_hashcode_member
143  //
144  // Custom type-trait that checks for the existence of a class data member 'mnHashCode'.
145  //
146  // In order to explicitly instantiate the hashtable without error we need to SFINAE away the functions that will
147  // fail to compile based on if the 'hash_node' contains a 'mnHashCode' member dictated by the hashtable template
148  // parameters. The hashtable support this level of configuration to allow users to choose which between the space vs.
149  // time optimization.
150  //
151  namespace Internal
152  {
153  template <class T>
154  struct has_hashcode_member
155  {
156  private:
157  template <class U> static eastl::no_type test(...);
158  template <class U> static eastl::yes_type test(decltype(U::mnHashCode)* = 0);
159  public:
160  static const bool value = sizeof(test<T>(0)) == sizeof(eastl::yes_type);
161  };
162  }
163 
164  static_assert(Internal::has_hashcode_member<hash_node<int, true>>::value, "contains a mnHashCode member");
165  static_assert(!Internal::has_hashcode_member<hash_node<int, false>>::value, "doesn't contain a mnHashCode member");
166 
167  // convenience macros to increase the readability of the code paths that must SFINAE on if the 'hash_node'
168  // contains the cached hashed value or not.
169  #define ENABLE_IF_HAS_HASHCODE(T, RT) typename eastl::enable_if<Internal::has_hashcode_member<T>::value, RT>::type*
170  #define ENABLE_IF_HASHCODE_EASTLSIZET(T, RT) typename eastl::enable_if<eastl::is_convertible<T, eastl_size_t>::value, RT>::type
171  #define ENABLE_IF_TRUETYPE(T) typename eastl::enable_if<T::value>::type*
172  #define DISABLE_IF_TRUETYPE(T) typename eastl::enable_if<!T::value>::type*
173 
174 
182  template <typename Value, bool bCacheHashCode>
183  struct node_iterator_base
184  {
185  typedef hash_node<Value, bCacheHashCode> node_type;
186 
187  node_type* mpNode;
188 
189  node_iterator_base(node_type* pNode)
190  : mpNode(pNode) { }
191 
192  void increment()
193  { mpNode = mpNode->mpNext; }
194  };
195 
196 
197 
205  template <typename Value, bool bConst, bool bCacheHashCode>
206  struct node_iterator : public node_iterator_base<Value, bCacheHashCode>
207  {
208  public:
209  typedef node_iterator_base<Value, bCacheHashCode> base_type;
210  typedef node_iterator<Value, bConst, bCacheHashCode> this_type;
211  typedef typename base_type::node_type node_type;
212  typedef Value value_type;
213  typedef typename type_select<bConst, const Value*, Value*>::type pointer;
214  typedef typename type_select<bConst, const Value&, Value&>::type reference;
215  typedef ptrdiff_t difference_type;
216  typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
217 
218  public:
219  explicit node_iterator(node_type* pNode = NULL)
220  : base_type(pNode) { }
221 
222  node_iterator(const node_iterator<Value, true, bCacheHashCode>& x)
223  : base_type(x.mpNode) { }
224 
225  reference operator*() const
226  { return base_type::mpNode->mValue; }
227 
228  pointer operator->() const
229  { return &(base_type::mpNode->mValue); }
230 
231  node_iterator& operator++()
232  { base_type::increment(); return *this; }
233 
234  node_iterator operator++(int)
235  { node_iterator temp(*this); base_type::increment(); return temp; }
236 
237  }; // node_iterator
238 
239 
240 
251  template <typename Value, bool bCacheHashCode>
252  struct hashtable_iterator_base
253  {
254  public:
255  typedef hashtable_iterator_base<Value, bCacheHashCode> this_type;
256  typedef hash_node<Value, bCacheHashCode> node_type;
257 
258  protected:
259  template <typename, typename, typename, typename, typename, typename, typename, typename, typename, bool, bool, bool>
260  friend class hashtable;
261 
262  template <typename, bool, bool>
263  friend struct hashtable_iterator;
264 
265  template <typename V, bool b>
266  friend bool operator==(const hashtable_iterator_base<V, b>&, const hashtable_iterator_base<V, b>&);
267 
268  template <typename V, bool b>
269  friend bool operator!=(const hashtable_iterator_base<V, b>&, const hashtable_iterator_base<V, b>&);
270 
271  node_type* mpNode; // Current node within current bucket.
272  node_type** mpBucket; // Current bucket.
273 
274  public:
275  hashtable_iterator_base(node_type* pNode, node_type** pBucket)
276  : mpNode(pNode), mpBucket(pBucket) { }
277 
278  void increment_bucket()
279  {
280  ++mpBucket;
281  while(*mpBucket == NULL) // We store an extra bucket with some non-NULL value at the end
282  ++mpBucket; // of the bucket array so that finding the end of the bucket
283  mpNode = *mpBucket; // array is quick and simple.
284  }
285 
286  void increment()
287  {
288  mpNode = mpNode->mpNext;
289 
290  while(mpNode == NULL)
291  mpNode = *++mpBucket;
292  }
293 
294  }; // hashtable_iterator_base
295 
296 
297 
298 
309  template <typename Value, bool bConst, bool bCacheHashCode>
310  struct hashtable_iterator : public hashtable_iterator_base<Value, bCacheHashCode>
311  {
312  public:
313  typedef hashtable_iterator_base<Value, bCacheHashCode> base_type;
314  typedef hashtable_iterator<Value, bConst, bCacheHashCode> this_type;
315  typedef hashtable_iterator<Value, false, bCacheHashCode> this_type_non_const;
316  typedef typename base_type::node_type node_type;
317  typedef Value value_type;
318  typedef typename type_select<bConst, const Value*, Value*>::type pointer;
319  typedef typename type_select<bConst, const Value&, Value&>::type reference;
320  typedef ptrdiff_t difference_type;
321  typedef EASTL_ITC_NS::forward_iterator_tag iterator_category;
322 
323  public:
324  hashtable_iterator(node_type* pNode = NULL, node_type** pBucket = NULL)
325  : base_type(pNode, pBucket) { }
326 
327  hashtable_iterator(node_type** pBucket)
328  : base_type(*pBucket, pBucket) { }
329 
330  hashtable_iterator(const this_type_non_const& x)
331  : base_type(x.mpNode, x.mpBucket) { }
332 
333  reference operator*() const
334  { return base_type::mpNode->mValue; }
335 
336  pointer operator->() const
337  { return &(base_type::mpNode->mValue); }
338 
339  hashtable_iterator& operator++()
340  { base_type::increment(); return *this; }
341 
342  hashtable_iterator operator++(int)
343  { hashtable_iterator temp(*this); base_type::increment(); return temp; }
344 
345  const node_type* get_node() const
346  { return base_type::mpNode; }
347 
348  }; // hashtable_iterator
349 
350 
351 
352 
363  template <typename Iterator>
364  inline typename eastl::iterator_traits<Iterator>::difference_type
365  distance_fw_impl(Iterator /*first*/, Iterator /*last*/, EASTL_ITC_NS::input_iterator_tag)
366  {
367  return 0;
368  }
369 
370  template <typename Iterator>
371  inline typename eastl::iterator_traits<Iterator>::difference_type
372  distance_fw_impl(Iterator first, Iterator last, EASTL_ITC_NS::forward_iterator_tag)
373  { return eastl::distance(first, last); }
374 
375  template <typename Iterator>
376  inline typename eastl::iterator_traits<Iterator>::difference_type
377  ht_distance(Iterator first, Iterator last)
378  {
379  typedef typename eastl::iterator_traits<Iterator>::iterator_category IC;
380  return distance_fw_impl(first, last, IC());
381  }
382 
383 
384 
385 
391  struct mod_range_hashing
392  {
393  uint32_t operator()(size_t r, uint32_t n) const
394  { return r % n; }
395  };
396 
397 
406  struct default_ranged_hash{ };
407 
408 
414  struct EASTL_API prime_rehash_policy
415  {
416  public:
417  float mfMaxLoadFactor;
418  float mfGrowthFactor;
419  mutable uint32_t mnNextResize;
420 
421  public:
422  prime_rehash_policy(float fMaxLoadFactor = 1.f)
423  : mfMaxLoadFactor(fMaxLoadFactor), mfGrowthFactor(2.f), mnNextResize(0) { }
424 
425  float GetMaxLoadFactor() const
426  { return mfMaxLoadFactor; }
427 
430  static uint32_t GetPrevBucketCountOnly(uint32_t nBucketCountHint);
431 
434  uint32_t GetPrevBucketCount(uint32_t nBucketCountHint) const;
435 
438  uint32_t GetNextBucketCount(uint32_t nBucketCountHint) const;
439 
442  uint32_t GetBucketCount(uint32_t nElementCount) const;
443 
448  eastl::pair<bool, uint32_t>
449  GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd) const;
450  };
451 
452 
453 
454 
455 
457  // Base classes for hashtable. We define these base classes because
458  // in some cases we want to do different things depending on the
459  // value of a policy class. In some cases the policy class affects
460  // which member functions and nested typedefs are defined; we handle that
461  // by specializing base class templates. Several of the base class templates
462  // need to access other members of class template hashtable, so we use
463  // the "curiously recurring template pattern" (parent class is templated
464  // on type of child class) for them.
466 
467 
473  template <typename RehashPolicy, typename Hashtable>
474  struct rehash_base { };
475 
476  template <typename Hashtable>
477  struct rehash_base<prime_rehash_policy, Hashtable>
478  {
479  // Returns the max load factor, which is the load factor beyond
480  // which we rebuild the container with a new bucket count.
481  float get_max_load_factor() const
482  {
483  const Hashtable* const pThis = static_cast<const Hashtable*>(this);
484  return pThis->rehash_policy().GetMaxLoadFactor();
485  }
486 
487  // If you want to make the hashtable never rehash (resize),
488  // set the max load factor to be a very high number (e.g. 100000.f).
489  void set_max_load_factor(float fMaxLoadFactor)
490  {
491  Hashtable* const pThis = static_cast<Hashtable*>(this);
492  pThis->rehash_policy(prime_rehash_policy(fMaxLoadFactor));
493  }
494  };
495 
496 
497 
498 
513  template <typename Key, typename Value, typename ExtractKey, typename Equal,
514  typename H1, typename H2, typename H, bool bCacheHashCode>
515  struct hash_code_base;
516 
517 
523  template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2, typename H>
524  struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false>
525  {
526  protected:
527  ExtractKey mExtractKey; // To do: Make this member go away entirely, as it never has any data.
528  Equal mEqual; // To do: Make this instance use zero space when it is zero size.
529  H mRangedHash; // To do: Make this instance use zero space when it is zero size
530 
531  public:
532  H1 hash_function() const
533  { return H1(); }
534 
535  Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
536  { return mEqual; } // has specified in its hashtable (unordered_*) proposal.
537 
538  const Equal& key_eq() const
539  { return mEqual; }
540 
541  Equal& key_eq()
542  { return mEqual; }
543 
544  protected:
545  typedef void* hash_code_t;
546  typedef uint32_t bucket_index_t;
547 
548  hash_code_base(const ExtractKey& extractKey, const Equal& eq, const H1&, const H2&, const H& h)
549  : mExtractKey(extractKey), mEqual(eq), mRangedHash(h) { }
550 
551  hash_code_t get_hash_code(const Key& key) const
552  {
553  EA_UNUSED(key);
554  return NULL;
555  }
556 
557  bucket_index_t bucket_index(hash_code_t, uint32_t) const
558  { return (bucket_index_t)0; }
559 
560  bucket_index_t bucket_index(const Key& key, hash_code_t, uint32_t nBucketCount) const
561  { return (bucket_index_t)mRangedHash(key, nBucketCount); }
562 
563  bucket_index_t bucket_index(const hash_node<Value, false>* pNode, uint32_t nBucketCount) const
564  { return (bucket_index_t)mRangedHash(mExtractKey(pNode->mValue), nBucketCount); }
565 
566  bool compare(const Key& key, hash_code_t, hash_node<Value, false>* pNode) const
567  { return mEqual(key, mExtractKey(pNode->mValue)); }
568 
569  void copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
570  { } // Nothing to do.
571 
572  void set_code(hash_node<Value, false>* pDest, hash_code_t c) const
573  {
574  EA_UNUSED(pDest);
575  EA_UNUSED(c);
576  }
577 
578  void base_swap(hash_code_base& x)
579  {
580  eastl::swap(mExtractKey, x.mExtractKey);
581  eastl::swap(mEqual, x.mEqual);
582  eastl::swap(mRangedHash, x.mRangedHash);
583  }
584 
585  }; // hash_code_base
586 
587 
588 
589  // No specialization for ranged hash function while caching hash codes.
590  // That combination is meaningless, and trying to do it is an error.
591 
592 
599  template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2, typename H>
600  struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;
601 
602 
603 
610  template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2>
611  struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false>
612  {
613  protected:
614  ExtractKey mExtractKey;
615  Equal mEqual;
616  H1 m_h1;
617  H2 m_h2;
618 
619  public:
620  typedef H1 hasher;
621 
622  H1 hash_function() const
623  { return m_h1; }
624 
625  Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
626  { return mEqual; } // has specified in its hashtable (unordered_*) proposal.
627 
628  const Equal& key_eq() const
629  { return mEqual; }
630 
631  Equal& key_eq()
632  { return mEqual; }
633 
634  protected:
635  typedef size_t hash_code_t;
636  typedef uint32_t bucket_index_t;
637  typedef hash_node<Value, false> node_type;
638 
639  hash_code_base(const ExtractKey& ex, const Equal& eq, const H1& h1, const H2& h2, const default_ranged_hash&)
640  : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
641 
642  hash_code_t get_hash_code(const Key& key) const
643  { return (hash_code_t)m_h1(key); }
644 
645  bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount) const
646  { return (bucket_index_t)m_h2(c, nBucketCount); }
647 
648  bucket_index_t bucket_index(const Key&, hash_code_t c, uint32_t nBucketCount) const
649  { return (bucket_index_t)m_h2(c, nBucketCount); }
650 
651  bucket_index_t bucket_index(const node_type* pNode, uint32_t nBucketCount) const
652  { return (bucket_index_t)m_h2((hash_code_t)m_h1(mExtractKey(pNode->mValue)), nBucketCount); }
653 
654  bool compare(const Key& key, hash_code_t, node_type* pNode) const
655  { return mEqual(key, mExtractKey(pNode->mValue)); }
656 
657  void copy_code(node_type*, const node_type*) const
658  { } // Nothing to do.
659 
660  void set_code(node_type*, hash_code_t) const
661  { } // Nothing to do.
662 
663  void base_swap(hash_code_base& x)
664  {
665  eastl::swap(mExtractKey, x.mExtractKey);
666  eastl::swap(mEqual, x.mEqual);
667  eastl::swap(m_h1, x.m_h1);
668  eastl::swap(m_h2, x.m_h2);
669  }
670 
671  }; // hash_code_base
672 
673 
674 
681  template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2>
682  struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true>
683  {
684  protected:
685  ExtractKey mExtractKey;
686  Equal mEqual;
687  H1 m_h1;
688  H2 m_h2;
689 
690  public:
691  typedef H1 hasher;
692 
693  H1 hash_function() const
694  { return m_h1; }
695 
696  Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
697  { return mEqual; } // has specified in its hashtable (unordered_*) proposal.
698 
699  const Equal& key_eq() const
700  { return mEqual; }
701 
702  Equal& key_eq()
703  { return mEqual; }
704 
705  protected:
706  typedef uint32_t hash_code_t;
707  typedef uint32_t bucket_index_t;
708  typedef hash_node<Value, true> node_type;
709 
710  hash_code_base(const ExtractKey& ex, const Equal& eq, const H1& h1, const H2& h2, const default_ranged_hash&)
711  : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
712 
713  hash_code_t get_hash_code(const Key& key) const
714  { return (hash_code_t)m_h1(key); }
715 
716  bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount) const
717  { return (bucket_index_t)m_h2(c, nBucketCount); }
718 
719  bucket_index_t bucket_index(const Key&, hash_code_t c, uint32_t nBucketCount) const
720  { return (bucket_index_t)m_h2(c, nBucketCount); }
721 
722  bucket_index_t bucket_index(const node_type* pNode, uint32_t nBucketCount) const
723  { return (bucket_index_t)m_h2((uint32_t)pNode->mnHashCode, nBucketCount); }
724 
725  bool compare(const Key& key, hash_code_t c, node_type* pNode) const
726  { return (pNode->mnHashCode == c) && mEqual(key, mExtractKey(pNode->mValue)); }
727 
728  void copy_code(node_type* pDest, const node_type* pSource) const
729  { pDest->mnHashCode = pSource->mnHashCode; }
730 
731  void set_code(node_type* pDest, hash_code_t c) const
732  { pDest->mnHashCode = c; }
733 
734  void base_swap(hash_code_base& x)
735  {
736  eastl::swap(mExtractKey, x.mExtractKey);
737  eastl::swap(mEqual, x.mEqual);
738  eastl::swap(m_h1, x.m_h1);
739  eastl::swap(m_h2, x.m_h2);
740  }
741 
742  }; // hash_code_base
743 
744 
745 
746 
747 
824  template <typename Key, typename Value, typename Allocator, typename ExtractKey,
825  typename Equal, typename H1, typename H2, typename H,
826  typename RehashPolicy, bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>
827  class hashtable
828  : public rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys> >,
829  public hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode>
830  {
831  public:
832  typedef Key key_type;
833  typedef Value value_type;
834  typedef typename ExtractKey::result_type mapped_type;
835  typedef hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode> hash_code_base_type;
836  typedef typename hash_code_base_type::hash_code_t hash_code_t;
837  typedef Allocator allocator_type;
838  typedef Equal key_equal;
839  typedef ptrdiff_t difference_type;
840  typedef eastl_size_t size_type; // See config.h for the definition of eastl_size_t, which defaults to size_t.
841  typedef value_type& reference;
842  typedef const value_type& const_reference;
843  typedef node_iterator<value_type, !bMutableIterators, bCacheHashCode> local_iterator;
844  typedef node_iterator<value_type, true, bCacheHashCode> const_local_iterator;
845  typedef hashtable_iterator<value_type, !bMutableIterators, bCacheHashCode> iterator;
846  typedef hashtable_iterator<value_type, true, bCacheHashCode> const_iterator;
847  typedef hash_node<value_type, bCacheHashCode> node_type;
848  typedef typename type_select<bUniqueKeys, eastl::pair<iterator, bool>, iterator>::type insert_return_type;
849  typedef hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H,
850  RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys> this_type;
851  typedef RehashPolicy rehash_policy_type;
852  typedef ExtractKey extract_key_type;
853  typedef H1 h1_type;
854  typedef H2 h2_type;
855  typedef H h_type;
856  typedef integral_constant<bool, bUniqueKeys> has_unique_keys_type;
857 
858  using hash_code_base_type::key_eq;
859  using hash_code_base_type::hash_function;
860  using hash_code_base_type::mExtractKey;
861  using hash_code_base_type::get_hash_code;
862  using hash_code_base_type::bucket_index;
863  using hash_code_base_type::compare;
864  using hash_code_base_type::set_code;
865  using hash_code_base_type::copy_code;
866 
867  static const bool kCacheHashCode = bCacheHashCode;
868 
869  enum
870  {
871  // This enumeration is deprecated in favor of eastl::kHashtableAllocFlagBuckets.
872  kAllocFlagBuckets = eastl::kHashtableAllocFlagBuckets // Flag to allocator which indicates that we are allocating buckets and not nodes.
873  };
874 
875  protected:
876  node_type** mpBucketArray;
877  size_type mnBucketCount;
878  size_type mnElementCount;
879  RehashPolicy mRehashPolicy; // To do: Use base class optimization to make this go away.
880  allocator_type mAllocator; // To do: Use base class optimization to make this go away.
881 
882  public:
883  hashtable(size_type nBucketCount, const H1&, const H2&, const H&, const Equal&, const ExtractKey&,
884  const allocator_type& allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
885 
886  template <typename FowardIterator>
887  hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
888  const H1&, const H2&, const H&, const Equal&, const ExtractKey&,
889  const allocator_type& allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
890 
891  hashtable(const hashtable& x);
892 
893  // initializer_list ctor support is implemented in subclasses (e.g. hash_set).
894  // hashtable(initializer_list<value_type>, size_type nBucketCount, const H1&, const H2&, const H&,
895  // const Equal&, const ExtractKey&, const allocator_type& allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
896 
897  hashtable(this_type&& x);
898  hashtable(this_type&& x, const allocator_type& allocator);
899  ~hashtable();
900 
901  const allocator_type& get_allocator() const EA_NOEXCEPT;
902  allocator_type& get_allocator() EA_NOEXCEPT;
903  void set_allocator(const allocator_type& allocator);
904 
905  this_type& operator=(const this_type& x);
906  this_type& operator=(std::initializer_list<value_type> ilist);
907  this_type& operator=(this_type&& x);
908 
909  void swap(this_type& x);
910 
911  iterator begin() EA_NOEXCEPT
912  {
913  iterator i(mpBucketArray);
914  if(!i.mpNode)
915  i.increment_bucket();
916  return i;
917  }
918 
919  const_iterator begin() const EA_NOEXCEPT
920  {
921  const_iterator i(mpBucketArray);
922  if(!i.mpNode)
923  i.increment_bucket();
924  return i;
925  }
926 
927  const_iterator cbegin() const EA_NOEXCEPT
928  { return begin(); }
929 
930  iterator end() EA_NOEXCEPT
931  { return iterator(mpBucketArray + mnBucketCount); }
932 
933  const_iterator end() const EA_NOEXCEPT
934  { return const_iterator(mpBucketArray + mnBucketCount); }
935 
936  const_iterator cend() const EA_NOEXCEPT
937  { return const_iterator(mpBucketArray + mnBucketCount); }
938 
939  // Returns an iterator to the first item in bucket n.
940  local_iterator begin(size_type n) EA_NOEXCEPT
941  { return local_iterator(mpBucketArray[n]); }
942 
943  const_local_iterator begin(size_type n) const EA_NOEXCEPT
944  { return const_local_iterator(mpBucketArray[n]); }
945 
946  const_local_iterator cbegin(size_type n) const EA_NOEXCEPT
947  { return const_local_iterator(mpBucketArray[n]); }
948 
949  // Returns an iterator to the last item in a bucket returned by begin(n).
950  local_iterator end(size_type) EA_NOEXCEPT
951  { return local_iterator(NULL); }
952 
953  const_local_iterator end(size_type) const EA_NOEXCEPT
954  { return const_local_iterator(NULL); }
955 
956  const_local_iterator cend(size_type) const EA_NOEXCEPT
957  { return const_local_iterator(NULL); }
958 
959  bool empty() const EA_NOEXCEPT
960  { return mnElementCount == 0; }
961 
962  size_type size() const EA_NOEXCEPT
963  { return mnElementCount; }
964 
965  size_type bucket_count() const EA_NOEXCEPT
966  { return mnBucketCount; }
967 
968  size_type bucket_size(size_type n) const EA_NOEXCEPT
969  { return (size_type)eastl::distance(begin(n), end(n)); }
970 
971  //size_type bucket(const key_type& k) const EA_NOEXCEPT
972  // { return bucket_index(k, (hash code here), (uint32_t)mnBucketCount); }
973 
974  // Returns the ratio of element count to bucket count. A return value of 1 means
975  // there's an optimal 1 bucket for each element.
976  float load_factor() const EA_NOEXCEPT
977  { return (float)mnElementCount / (float)mnBucketCount; }
978 
979  // Inherited from the base class.
980  // Returns the max load factor, which is the load factor beyond
981  // which we rebuild the container with a new bucket count.
982  // get_max_load_factor comes from rehash_base.
983  // float get_max_load_factor() const;
984 
985  // Inherited from the base class.
986  // If you want to make the hashtable never rehash (resize),
987  // set the max load factor to be a very high number (e.g. 100000.f).
988  // set_max_load_factor comes from rehash_base.
989  // void set_max_load_factor(float fMaxLoadFactor);
990 
993  const rehash_policy_type& rehash_policy() const EA_NOEXCEPT
994  { return mRehashPolicy; }
995 
998  void rehash_policy(const rehash_policy_type& rehashPolicy);
999 
1000  template <class... Args>
1001  insert_return_type emplace(Args&&... args);
1002 
1003  template <class... Args>
1004  iterator emplace_hint(const_iterator position, Args&&... args);
1005 
1006  template <class... Args> insert_return_type try_emplace(const key_type& k, Args&&... args);
1007  template <class... Args> insert_return_type try_emplace(key_type&& k, Args&&... args);
1008  template <class... Args> iterator try_emplace(const_iterator position, const key_type& k, Args&&... args);
1009  template <class... Args> iterator try_emplace(const_iterator position, key_type&& k, Args&&... args);
1010 
1011  insert_return_type insert(const value_type& value);
1012  insert_return_type insert(value_type&& otherValue);
1013  iterator insert(const_iterator hint, const value_type& value);
1014  iterator insert(const_iterator hint, value_type&& value);
1015  void insert(std::initializer_list<value_type> ilist);
1016  template <typename InputIterator> void insert(InputIterator first, InputIterator last);
1017  //insert_return_type insert(node_type&& nh);
1018  //iterator insert(const_iterator hint, node_type&& nh);
1019 
1020  // This overload attempts to mitigate the overhead associated with mismatched cv-quality elements of
1021  // the hashtable pair. It can avoid copy overhead because it will perfect forward the user provided pair types
1022  // until it can constructed in-place in the allocated hashtable node.
1023  //
1024  // Ideally we would remove this overload as it deprecated and removed in C++17 but it currently causes
1025  // performance regressions for hashtables with complex keys (keys that allocate resources).
1026  template <class P,
1027  class = typename eastl::enable_if_t<
1028  #if EASTL_ENABLE_PAIR_FIRST_ELEMENT_CONSTRUCTOR
1029  !eastl::is_same_v<eastl::decay_t<P>, key_type> &&
1030  #endif
1031  !eastl::is_literal_type_v<P> &&
1032  eastl::is_constructible_v<value_type, P&&>>>
1033  insert_return_type insert(P&& otherValue);
1034 
1035  // Non-standard extension
1036  template <class P> // See comments below for the const value_type& equivalent to this function.
1037  insert_return_type insert(hash_code_t c, node_type* pNodeNew, P&& otherValue);
1038 
1039  // We provide a version of insert which lets the caller directly specify the hash value and
1040  // a potential node to insert if needed. This allows for less thread contention in the case
1041  // of a thread-shared hash table that's accessed during a mutex lock, because the hash calculation
1042  // and node creation is done outside of the lock. If pNodeNew is supplied by the user (i.e. non-NULL)
1043  // then it must be freeable via the hash table's allocator. If the return value is true then this function
1044  // took over ownership of pNodeNew, else pNodeNew is still owned by the caller to free or to pass
1045  // to another call to insert. pNodeNew need not be assigned the value by the caller, as the insert
1046  // function will assign value to pNodeNew upon insertion into the hash table. pNodeNew may be
1047  // created by the user with the allocate_uninitialized_node function, and freed by the free_uninitialized_node function.
1048  insert_return_type insert(hash_code_t c, node_type* pNodeNew, const value_type& value);
1049 
1050  template <class M> eastl::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
1051  template <class M> eastl::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
1052  template <class M> iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
1053  template <class M> iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
1054 
1055  // Used to allocate and free memory used by insert(const value_type& value, hash_code_t c, node_type* pNodeNew).
1056  node_type* allocate_uninitialized_node();
1057  void free_uninitialized_node(node_type* pNode);
1058 
1059  iterator erase(const_iterator position);
1060  iterator erase(const_iterator first, const_iterator last);
1061  size_type erase(const key_type& k);
1062 
1063  void clear();
1064  void clear(bool clearBuckets); // If clearBuckets is true, we free the bucket memory and set the bucket count back to the newly constructed count.
1065  void reset_lose_memory() EA_NOEXCEPT; // This is a unilateral reset to an initially empty state. No destructors are called, no deallocation occurs.
1066  void rehash(size_type nBucketCount);
1067  void reserve(size_type nElementCount);
1068 
1069  iterator find(const key_type& key);
1070  const_iterator find(const key_type& key) const;
1071 
1087  template <typename U, typename UHash, typename BinaryPredicate>
1088  iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate);
1089 
1090  template <typename U, typename UHash, typename BinaryPredicate>
1091  const_iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate) const;
1092 
1093  template <typename U>
1094  iterator find_as(const U& u);
1095 
1096  template <typename U>
1097  const_iterator find_as(const U& u) const;
1098 
1099  // Note: find_by_hash and find_range_by_hash both perform a search based on a hash value.
1100  // It is important to note that multiple hash values may map to the same hash bucket, so
1101  // it would be incorrect to assume all items returned match the hash value that
1102  // was searched for.
1103 
1106 
1107  template<typename HashCodeT>
1108  ENABLE_IF_HASHCODE_EASTLSIZET(HashCodeT, iterator) find_by_hash(HashCodeT c)
1109  {
1110  EASTL_CT_ASSERT_MSG(bCacheHashCode,
1111  "find_by_hash(hash_code_t c) is designed to avoid recomputing hashes, "
1112  "so it requires cached hash codes. Consider setting template parameter "
1113  "bCacheHashCode to true or using find_by_hash(const key_type& k, hash_code_t c) instead.");
1114 
1115  const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1116 
1117  node_type* const pNode = DoFindNode(mpBucketArray[n], c);
1118 
1119  return pNode ? iterator(pNode, mpBucketArray + n) :
1120  iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1121  }
1122 
1123  template<typename HashCodeT>
1124  ENABLE_IF_HASHCODE_EASTLSIZET(HashCodeT, const_iterator) find_by_hash(HashCodeT c) const
1125  {
1126  EASTL_CT_ASSERT_MSG(bCacheHashCode,
1127  "find_by_hash(hash_code_t c) is designed to avoid recomputing hashes, "
1128  "so it requires cached hash codes. Consider setting template parameter "
1129  "bCacheHashCode to true or using find_by_hash(const key_type& k, hash_code_t c) instead.");
1130 
1131  const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1132 
1133  node_type* const pNode = DoFindNode(mpBucketArray[n], c);
1134 
1135  return pNode ?
1136  const_iterator(pNode, mpBucketArray + n) :
1137  const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1138  }
1139 
1140  iterator find_by_hash(const key_type& k, hash_code_t c)
1141  {
1142  const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1143 
1144  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
1145  return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1146  }
1147 
1148  const_iterator find_by_hash(const key_type& k, hash_code_t c) const
1149  {
1150  const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1151 
1152  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
1153  return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1154  }
1155 
1156  // Returns a pair that allows iterating over all nodes in a hash bucket
1157  // first in the pair returned holds the iterator for the beginning of the bucket,
1158  // second in the pair returned holds the iterator for the end of the bucket,
1159  // If no bucket is found, both values in the pair are set to end().
1160  //
1161  // See also the note above.
1162  eastl::pair<iterator, iterator> find_range_by_hash(hash_code_t c);
1163  eastl::pair<const_iterator, const_iterator> find_range_by_hash(hash_code_t c) const;
1164 
1165  size_type count(const key_type& k) const EA_NOEXCEPT;
1166 
1167  eastl::pair<iterator, iterator> equal_range(const key_type& k);
1168  eastl::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1169 
1170  bool validate() const;
1171  int validate_iterator(const_iterator i) const;
1172 
1173  protected:
1174  // We must remove one of the 'DoGetResultIterator' overloads from the overload-set (via SFINAE) because both can
1175  // not compile successfully at the same time. The 'bUniqueKeys' template parameter chooses at compile-time the
1176  // type of 'insert_return_type' between a pair<iterator,bool> and a raw iterator. We must pick between the two
1177  // overloads that unpacks the iterator from the pair or simply passes the provided iterator to the caller based
1178  // on the class template parameter.
1179  template <typename BoolConstantT>
1180  iterator DoGetResultIterator(BoolConstantT,
1181  const insert_return_type& irt,
1182  ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr) const EA_NOEXCEPT
1183  {
1184  return irt.first;
1185  }
1186 
1187  template <typename BoolConstantT>
1188  iterator DoGetResultIterator(BoolConstantT,
1189  const insert_return_type& irt,
1190  DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr) const EA_NOEXCEPT
1191  {
1192  return irt;
1193  }
1194 
1195  node_type* DoAllocateNodeFromKey(const key_type& key);
1196  node_type* DoAllocateNodeFromKey(key_type&& key);
1197  void DoFreeNode(node_type* pNode);
1198  void DoFreeNodes(node_type** pBucketArray, size_type);
1199 
1200  node_type** DoAllocateBuckets(size_type n);
1201  void DoFreeBuckets(node_type** pBucketArray, size_type n);
1202 
1203  template <typename BoolConstantT, class... Args, ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr>
1204  eastl::pair<iterator, bool> DoInsertValue(BoolConstantT, Args&&... args);
1205 
1206  template <typename BoolConstantT, class... Args, DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr>
1207  iterator DoInsertValue(BoolConstantT, Args&&... args);
1208 
1209 
1210  template <typename BoolConstantT>
1211  eastl::pair<iterator, bool> DoInsertValueExtra(BoolConstantT,
1212  const key_type& k,
1213  hash_code_t c,
1214  node_type* pNodeNew,
1215  value_type&& value,
1216  ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1217 
1218  template <typename BoolConstantT>
1219  eastl::pair<iterator, bool> DoInsertValue(BoolConstantT,
1220  value_type&& value,
1221  ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1222 
1223  template <typename BoolConstantT>
1224  iterator DoInsertValueExtra(BoolConstantT,
1225  const key_type& k,
1226  hash_code_t c,
1227  node_type* pNodeNew,
1228  value_type&& value,
1229  DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1230 
1231  template <typename BoolConstantT>
1232  iterator DoInsertValue(BoolConstantT, value_type&& value, DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1233 
1234 
1235  template <typename BoolConstantT>
1236  eastl::pair<iterator, bool> DoInsertValueExtra(BoolConstantT,
1237  const key_type& k,
1238  hash_code_t c,
1239  node_type* pNodeNew,
1240  const value_type& value,
1241  ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1242 
1243  template <typename BoolConstantT>
1244  eastl::pair<iterator, bool> DoInsertValue(BoolConstantT,
1245  const value_type& value,
1246  ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1247 
1248  template <typename BoolConstantT>
1249  iterator DoInsertValueExtra(BoolConstantT,
1250  const key_type& k,
1251  hash_code_t c,
1252  node_type* pNodeNew,
1253  const value_type& value,
1254  DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1255 
1256  template <typename BoolConstantT>
1257  iterator DoInsertValue(BoolConstantT, const value_type& value, DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr);
1258 
1259  template <class... Args>
1260  node_type* DoAllocateNode(Args&&... args);
1261  node_type* DoAllocateNode(value_type&& value);
1262  node_type* DoAllocateNode(const value_type& value);
1263 
1264  // DoInsertKey is supposed to get hash_code_t c = get_hash_code(key).
1265  // it is done in case application has it's own hashset/hashmap-like containter, where hash code is for some reason known prior the insert
1266  // this allows to save some performance, especially with heavy hash functions
1267  eastl::pair<iterator, bool> DoInsertKey(true_type, const key_type& key, hash_code_t c);
1268  iterator DoInsertKey(false_type, const key_type& key, hash_code_t c);
1269  eastl::pair<iterator, bool> DoInsertKey(true_type, key_type&& key, hash_code_t c);
1270  iterator DoInsertKey(false_type, key_type&& key, hash_code_t c);
1271 
1272  // We keep DoInsertKey overload without third parameter, for compatibility with older revisions of EASTL (3.12.07 and earlier)
1273  // It used to call get_hash_code as a first call inside the DoInsertKey.
1274  eastl::pair<iterator, bool> DoInsertKey(true_type, const key_type& key) { return DoInsertKey(true_type(), key, get_hash_code(key)); }
1275  iterator DoInsertKey(false_type, const key_type& key) { return DoInsertKey(false_type(), key, get_hash_code(key)); }
1276  eastl::pair<iterator, bool> DoInsertKey(true_type, key_type&& key) { return DoInsertKey(true_type(), eastl::move(key), get_hash_code(key)); }
1277  iterator DoInsertKey(false_type, key_type&& key) { return DoInsertKey(false_type(), eastl::move(key), get_hash_code(key)); }
1278 
1279  void DoRehash(size_type nBucketCount);
1280  node_type* DoFindNode(node_type* pNode, const key_type& k, hash_code_t c) const;
1281 
1282  template <typename T>
1283  ENABLE_IF_HAS_HASHCODE(T, node_type) DoFindNode(T* pNode, hash_code_t c) const
1284  {
1285  for (; pNode; pNode = pNode->mpNext)
1286  {
1287  if (pNode->mnHashCode == c)
1288  return pNode;
1289  }
1290  return NULL;
1291  }
1292 
1293  template <typename U, typename BinaryPredicate>
1294  node_type* DoFindNodeT(node_type* pNode, const U& u, BinaryPredicate predicate) const;
1295 
1296  }; // class hashtable
1297 
1298 
1299 
1300 
1301 
1303  // node_iterator_base
1305 
1306  template <typename Value, bool bCacheHashCode>
1307  inline bool operator==(const node_iterator_base<Value, bCacheHashCode>& a, const node_iterator_base<Value, bCacheHashCode>& b)
1308  { return a.mpNode == b.mpNode; }
1309 
1310  template <typename Value, bool bCacheHashCode>
1311  inline bool operator!=(const node_iterator_base<Value, bCacheHashCode>& a, const node_iterator_base<Value, bCacheHashCode>& b)
1312  { return a.mpNode != b.mpNode; }
1313 
1314 
1315 
1316 
1318  // hashtable_iterator_base
1320 
1321  template <typename Value, bool bCacheHashCode>
1322  inline bool operator==(const hashtable_iterator_base<Value, bCacheHashCode>& a, const hashtable_iterator_base<Value, bCacheHashCode>& b)
1323  { return a.mpNode == b.mpNode; }
1324 
1325  template <typename Value, bool bCacheHashCode>
1326  inline bool operator!=(const hashtable_iterator_base<Value, bCacheHashCode>& a, const hashtable_iterator_base<Value, bCacheHashCode>& b)
1327  { return a.mpNode != b.mpNode; }
1328 
1329 
1330 
1331 
1333  // hashtable
1335 
1336  template <typename K, typename V, typename A, typename EK, typename Eq,
1337  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1338  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>
1339  ::hashtable(size_type nBucketCount, const H1& h1, const H2& h2, const H& h,
1340  const Eq& eq, const EK& ek, const allocator_type& allocator)
1341  : rehash_base<RP, hashtable>(),
1342  hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(ek, eq, h1, h2, h),
1343  mnBucketCount(0),
1344  mnElementCount(0),
1345  mRehashPolicy(),
1346  mAllocator(allocator)
1347  {
1348  if(nBucketCount < 2) // If we are starting in an initially empty state, with no memory allocation done.
1349  reset_lose_memory();
1350  else // Else we are creating a potentially non-empty hashtable...
1351  {
1352  EASTL_ASSERT(nBucketCount < 10000000);
1353  mnBucketCount = (size_type)mRehashPolicy.GetNextBucketCount((uint32_t)nBucketCount);
1354  mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will always be at least 2.
1355  }
1356  }
1357 
1358 
1359 
1360  template <typename K, typename V, typename A, typename EK, typename Eq,
1361  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1362  template <typename FowardIterator>
1363  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
1364  const H1& h1, const H2& h2, const H& h,
1365  const Eq& eq, const EK& ek, const allocator_type& allocator)
1366  : rehash_base<rehash_policy_type, hashtable>(),
1367  hash_code_base<key_type, value_type, extract_key_type, key_equal, h1_type, h2_type, h_type, kCacheHashCode>(ek, eq, h1, h2, h),
1368  //mnBucketCount(0), // This gets re-assigned below.
1369  mnElementCount(0),
1370  mRehashPolicy(),
1371  mAllocator(allocator)
1372  {
1373  if(nBucketCount < 2)
1374  {
1375  const size_type nElementCount = (size_type)eastl::ht_distance(first, last);
1376  mnBucketCount = (size_type)mRehashPolicy.GetBucketCount((uint32_t)nElementCount);
1377  }
1378  else
1379  {
1380  EASTL_ASSERT(nBucketCount < 10000000);
1381  mnBucketCount = nBucketCount;
1382  }
1383 
1384  mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will always be at least 2.
1385 
1386  #if EASTL_EXCEPTIONS_ENABLED
1387  try
1388  {
1389  #endif
1390  for(; first != last; ++first)
1391  insert(*first);
1392  #if EASTL_EXCEPTIONS_ENABLED
1393  }
1394  catch(...)
1395  {
1396  clear();
1397  DoFreeBuckets(mpBucketArray, mnBucketCount);
1398  throw;
1399  }
1400  #endif
1401  }
1402 
1403 
1404 
1405  template <typename K, typename V, typename A, typename EK, typename Eq,
1406  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1407  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(const this_type& x)
1408  : rehash_base<RP, hashtable>(x),
1409  hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(x),
1410  mnBucketCount(x.mnBucketCount),
1411  mnElementCount(x.mnElementCount),
1412  mRehashPolicy(x.mRehashPolicy),
1413  mAllocator(x.mAllocator)
1414  {
1415  if(mnElementCount) // If there is anything to copy...
1416  {
1417  mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will be at least 2.
1418 
1419  #if EASTL_EXCEPTIONS_ENABLED
1420  try
1421  {
1422  #endif
1423  for(size_type i = 0; i < x.mnBucketCount; ++i)
1424  {
1425  node_type* pNodeSource = x.mpBucketArray[i];
1426  node_type** ppNodeDest = mpBucketArray + i;
1427 
1428  while(pNodeSource)
1429  {
1430  *ppNodeDest = DoAllocateNode(pNodeSource->mValue);
1431  copy_code(*ppNodeDest, pNodeSource);
1432  ppNodeDest = &(*ppNodeDest)->mpNext;
1433  pNodeSource = pNodeSource->mpNext;
1434  }
1435  }
1436  #if EASTL_EXCEPTIONS_ENABLED
1437  }
1438  catch(...)
1439  {
1440  clear();
1441  DoFreeBuckets(mpBucketArray, mnBucketCount);
1442  throw;
1443  }
1444  #endif
1445  }
1446  else
1447  {
1448  // In this case, instead of allocate memory and copy nothing from x,
1449  // we reset ourselves to a zero allocation state.
1450  reset_lose_memory();
1451  }
1452  }
1453 
1454 
1455  template <typename K, typename V, typename A, typename EK, typename Eq,
1456  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1457  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(this_type&& x)
1458  : rehash_base<RP, hashtable>(x),
1459  hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(x),
1460  mnBucketCount(0),
1461  mnElementCount(0),
1462  mRehashPolicy(x.mRehashPolicy),
1463  mAllocator(x.mAllocator)
1464  {
1465  reset_lose_memory(); // We do this here the same as we do it in the default ctor because it puts the container in a proper initial empty state. This code would be cleaner if we could rely on being able to use C++11 delegating constructors and just call the default ctor here.
1466  swap(x);
1467  }
1468 
1469 
1470  template <typename K, typename V, typename A, typename EK, typename Eq,
1471  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1472  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(this_type&& x, const allocator_type& allocator)
1473  : rehash_base<RP, hashtable>(x),
1474  hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(x),
1475  mnBucketCount(0),
1476  mnElementCount(0),
1477  mRehashPolicy(x.mRehashPolicy),
1478  mAllocator(allocator)
1479  {
1480  reset_lose_memory(); // We do this here the same as we do it in the default ctor because it puts the container in a proper initial empty state. This code would be cleaner if we could rely on being able to use C++11 delegating constructors and just call the default ctor here.
1481  swap(x); // swap will directly or indirectly handle the possibility that mAllocator != x.mAllocator.
1482  }
1483 
1484 
1485  template <typename K, typename V, typename A, typename EK, typename Eq,
1486  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1487  inline const typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::allocator_type&
1488  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::get_allocator() const EA_NOEXCEPT
1489  {
1490  return mAllocator;
1491  }
1492 
1493 
1494 
1495  template <typename K, typename V, typename A, typename EK, typename Eq,
1496  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1497  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::allocator_type&
1498  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::get_allocator() EA_NOEXCEPT
1499  {
1500  return mAllocator;
1501  }
1502 
1503 
1504 
1505  template <typename K, typename V, typename A, typename EK, typename Eq,
1506  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1507  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::set_allocator(const allocator_type& allocator)
1508  {
1509  mAllocator = allocator;
1510  }
1511 
1512 
1513 
1514  template <typename K, typename V, typename A, typename EK, typename Eq,
1515  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1516  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::this_type&
1517  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::operator=(const this_type& x)
1518  {
1519  if(this != &x)
1520  {
1521  clear();
1522 
1523  #if EASTL_ALLOCATOR_COPY_ENABLED
1524  mAllocator = x.mAllocator;
1525  #endif
1526 
1527  insert(x.begin(), x.end());
1528  }
1529  return *this;
1530  }
1531 
1532 
1533  template <typename K, typename V, typename A, typename EK, typename Eq,
1534  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1535  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::this_type&
1536  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::operator=(this_type&& x)
1537  {
1538  if(this != &x)
1539  {
1540  clear(); // To consider: Are we really required to clear here? x is going away soon and will clear itself in its dtor.
1541  swap(x); // member swap handles the case that x has a different allocator than our allocator by doing a copy.
1542  }
1543  return *this;
1544  }
1545 
1546 
1547  template <typename K, typename V, typename A, typename EK, typename Eq,
1548  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1549  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::this_type&
1550  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::operator=(std::initializer_list<value_type> ilist)
1551  {
1552  // The simplest means of doing this is to clear and insert. There probably isn't a generic
1553  // solution that's any more efficient without having prior knowledge of the ilist contents.
1554  clear();
1555  insert(ilist.begin(), ilist.end());
1556  return *this;
1557  }
1558 
1559 
1560 
1561  template <typename K, typename V, typename A, typename EK, typename Eq,
1562  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1563  inline hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::~hashtable()
1564  {
1565  clear();
1566  DoFreeBuckets(mpBucketArray, mnBucketCount);
1567  }
1568 
1569 
1570  template <typename K, typename V, typename A, typename EK, typename Eq,
1571  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1572  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1573  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNodeFromKey(const key_type& key)
1574  {
1575  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
1576  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
1577 
1578  #if EASTL_EXCEPTIONS_ENABLED
1579  try
1580  {
1581  #endif
1582  ::new(eastl::addressof(pNode->mValue)) value_type(pair_first_construct, key);
1583  pNode->mpNext = NULL;
1584  return pNode;
1585  #if EASTL_EXCEPTIONS_ENABLED
1586  }
1587  catch(...)
1588  {
1589  EASTLFree(mAllocator, pNode, sizeof(node_type));
1590  throw;
1591  }
1592  #endif
1593  }
1594 
1595 
1596  template <typename K, typename V, typename A, typename EK, typename Eq,
1597  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1598  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1599  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNodeFromKey(key_type&& key)
1600  {
1601  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
1602  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
1603 
1604  #if EASTL_EXCEPTIONS_ENABLED
1605  try
1606  {
1607  #endif
1608  ::new(eastl::addressof(pNode->mValue)) value_type(pair_first_construct, eastl::move(key));
1609  pNode->mpNext = NULL;
1610  return pNode;
1611  #if EASTL_EXCEPTIONS_ENABLED
1612  }
1613  catch(...)
1614  {
1615  EASTLFree(mAllocator, pNode, sizeof(node_type));
1616  throw;
1617  }
1618  #endif
1619  }
1620 
1621 
1622  template <typename K, typename V, typename A, typename EK, typename Eq,
1623  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1624  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNode(node_type* pNode)
1625  {
1626  pNode->~node_type();
1627  EASTLFree(mAllocator, pNode, sizeof(node_type));
1628  }
1629 
1630 
1631 
1632  template <typename K, typename V, typename A, typename EK, typename Eq,
1633  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1634  void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNodes(node_type** pNodeArray, size_type n)
1635  {
1636  for(size_type i = 0; i < n; ++i)
1637  {
1638  node_type* pNode = pNodeArray[i];
1639  while(pNode)
1640  {
1641  node_type* const pTempNode = pNode;
1642  pNode = pNode->mpNext;
1643  DoFreeNode(pTempNode);
1644  }
1645  pNodeArray[i] = NULL;
1646  }
1647  }
1648 
1649 
1650 
1651  template <typename K, typename V, typename A, typename EK, typename Eq,
1652  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1653  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type**
1654  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateBuckets(size_type n)
1655  {
1656  // We allocate one extra bucket to hold a sentinel, an arbitrary
1657  // non-null pointer. Iterator increment relies on this.
1658  EASTL_ASSERT(n > 1); // We reserve an mnBucketCount of 1 for the shared gpEmptyBucketArray.
1659  EASTL_CT_ASSERT(kHashtableAllocFlagBuckets == 0x00400000); // Currently we expect this to be so, because the allocator has a copy of this enum.
1660  node_type** const pBucketArray = (node_type**)EASTLAllocAlignedFlags(mAllocator, (n + 1) * sizeof(node_type*), EASTL_ALIGN_OF(node_type*), 0, kHashtableAllocFlagBuckets);
1661  //eastl::fill(pBucketArray, pBucketArray + n, (node_type*)NULL);
1662  memset(pBucketArray, 0, n * sizeof(node_type*));
1663  pBucketArray[n] = reinterpret_cast<node_type*>((uintptr_t)~0);
1664  return pBucketArray;
1665  }
1666 
1667 
1668 
1669  template <typename K, typename V, typename A, typename EK, typename Eq,
1670  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1671  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeBuckets(node_type** pBucketArray, size_type n)
1672  {
1673  // If n <= 1, then pBucketArray is from the shared gpEmptyBucketArray. We don't test
1674  // for pBucketArray == &gpEmptyBucketArray because one library have a different gpEmptyBucketArray
1675  // than another but pass a hashtable to another. So we go by the size.
1676  if(n > 1)
1677  EASTLFree(mAllocator, pBucketArray, (n + 1) * sizeof(node_type*)); // '+1' because DoAllocateBuckets allocates nBucketCount + 1 buckets in order to have a NULL sentinel at the end.
1678  }
1679 
1680 
1681  template <typename K, typename V, typename A, typename EK, typename Eq,
1682  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1683  void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::swap(this_type& x)
1684  {
1685  hash_code_base<K, V, EK, Eq, H1, H2, H, bC>::base_swap(x); // hash_code_base has multiple implementations, so we let them handle the swap.
1686  eastl::swap(mRehashPolicy, x.mRehashPolicy);
1687  EASTL_MACRO_SWAP(node_type**, mpBucketArray, x.mpBucketArray);
1688  eastl::swap(mnBucketCount, x.mnBucketCount);
1689  eastl::swap(mnElementCount, x.mnElementCount);
1690 
1691  if (mAllocator != x.mAllocator) // If allocators are not equivalent...
1692  {
1693  eastl::swap(mAllocator, x.mAllocator);
1694  }
1695  }
1696 
1697 
1698  template <typename K, typename V, typename A, typename EK, typename Eq,
1699  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1700  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash_policy(const rehash_policy_type& rehashPolicy)
1701  {
1702  mRehashPolicy = rehashPolicy;
1703 
1704  const size_type nBuckets = rehashPolicy.GetBucketCount((uint32_t)mnElementCount);
1705 
1706  if(nBuckets > mnBucketCount)
1707  DoRehash(nBuckets);
1708  }
1709 
1710 
1711 
1712  template <typename K, typename V, typename A, typename EK, typename Eq,
1713  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1714  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1715  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(const key_type& k)
1716  {
1717  const hash_code_t c = get_hash_code(k);
1718  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1719 
1720  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
1721  return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1722  }
1723 
1724 
1725 
1726  template <typename K, typename V, typename A, typename EK, typename Eq,
1727  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1728  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
1729  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(const key_type& k) const
1730  {
1731  const hash_code_t c = get_hash_code(k);
1732  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1733 
1734  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
1735  return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1736  }
1737 
1738 
1739 
1740  template <typename K, typename V, typename A, typename EK, typename Eq,
1741  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1742  template <typename U, typename UHash, typename BinaryPredicate>
1743  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1744  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate)
1745  {
1746  const hash_code_t c = (hash_code_t)uhash(other);
1747  const size_type n = (size_type)(c % mnBucketCount); // This assumes we are using the mod range policy.
1748 
1749  node_type* const pNode = DoFindNodeT(mpBucketArray[n], other, predicate);
1750  return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1751  }
1752 
1753 
1754 
1755  template <typename K, typename V, typename A, typename EK, typename Eq,
1756  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1757  template <typename U, typename UHash, typename BinaryPredicate>
1758  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
1759  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate) const
1760  {
1761  const hash_code_t c = (hash_code_t)uhash(other);
1762  const size_type n = (size_type)(c % mnBucketCount); // This assumes we are using the mod range policy.
1763 
1764  node_type* const pNode = DoFindNodeT(mpBucketArray[n], other, predicate);
1765  return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
1766  }
1767 
1768 
1783  template <typename H, typename U>
1784  inline typename H::iterator hashtable_find(H& hashTable, U u)
1785  { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
1786 
1787  template <typename H, typename U>
1788  inline typename H::const_iterator hashtable_find(const H& hashTable, U u)
1789  { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
1790 
1791 
1792 
1793  template <typename K, typename V, typename A, typename EK, typename Eq,
1794  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1795  template <typename U>
1796  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
1797  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other)
1798  { return eastl::hashtable_find(*this, other); }
1799  // VC++ doesn't appear to like the following, though it seems correct to me.
1800  // So we implement the workaround above until we can straighten this out.
1801  //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); }
1802 
1803 
1804  template <typename K, typename V, typename A, typename EK, typename Eq,
1805  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1806  template <typename U>
1807  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
1808  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other) const
1809  { return eastl::hashtable_find(*this, other); }
1810  // VC++ doesn't appear to like the following, though it seems correct to me.
1811  // So we implement the workaround above until we can straighten this out.
1812  //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); }
1813 
1814 
1815 
1816  template <typename K, typename V, typename A, typename EK, typename Eq,
1817  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1818  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator,
1819  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator>
1820  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_range_by_hash(hash_code_t c) const
1821  {
1822  const size_type start = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1823  node_type* const pNodeStart = mpBucketArray[start];
1824 
1825  if (pNodeStart)
1826  {
1827  eastl::pair<const_iterator, const_iterator> pair(const_iterator(pNodeStart, mpBucketArray + start),
1828  const_iterator(pNodeStart, mpBucketArray + start));
1829  pair.second.increment_bucket();
1830  return pair;
1831  }
1832 
1833  return eastl::pair<const_iterator, const_iterator>(const_iterator(mpBucketArray + mnBucketCount),
1834  const_iterator(mpBucketArray + mnBucketCount));
1835  }
1836 
1837 
1838 
1839  template <typename K, typename V, typename A, typename EK, typename Eq,
1840  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1841  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
1842  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator>
1843  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_range_by_hash(hash_code_t c)
1844  {
1845  const size_type start = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
1846  node_type* const pNodeStart = mpBucketArray[start];
1847 
1848  if (pNodeStart)
1849  {
1850  eastl::pair<iterator, iterator> pair(iterator(pNodeStart, mpBucketArray + start),
1851  iterator(pNodeStart, mpBucketArray + start));
1852  pair.second.increment_bucket();
1853  return pair;
1854 
1855  }
1856 
1857  return eastl::pair<iterator, iterator>(iterator(mpBucketArray + mnBucketCount),
1858  iterator(mpBucketArray + mnBucketCount));
1859  }
1860 
1861 
1862 
1863  template <typename K, typename V, typename A, typename EK, typename Eq,
1864  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1865  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
1866  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::count(const key_type& k) const EA_NOEXCEPT
1867  {
1868  const hash_code_t c = get_hash_code(k);
1869  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1870  size_type result = 0;
1871 
1872  // To do: Make a specialization for bU (unique keys) == true and take
1873  // advantage of the fact that the count will always be zero or one in that case.
1874  for(node_type* pNode = mpBucketArray[n]; pNode; pNode = pNode->mpNext)
1875  {
1876  if(compare(k, c, pNode))
1877  ++result;
1878  }
1879  return result;
1880  }
1881 
1882 
1883 
1884  template <typename K, typename V, typename A, typename EK, typename Eq,
1885  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1886  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
1887  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator>
1888  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(const key_type& k)
1889  {
1890  const hash_code_t c = get_hash_code(k);
1891  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1892  node_type** head = mpBucketArray + n;
1893  node_type* pNode = DoFindNode(*head, k, c);
1894 
1895  if(pNode)
1896  {
1897  node_type* p1 = pNode->mpNext;
1898 
1899  for(; p1; p1 = p1->mpNext)
1900  {
1901  if(!compare(k, c, p1))
1902  break;
1903  }
1904 
1905  iterator first(pNode, head);
1906  iterator last(p1, head);
1907 
1908  if(!p1)
1909  last.increment_bucket();
1910 
1911  return eastl::pair<iterator, iterator>(first, last);
1912  }
1913 
1914  return eastl::pair<iterator, iterator>(iterator(mpBucketArray + mnBucketCount), // iterator(mpBucketArray + mnBucketCount) == end()
1915  iterator(mpBucketArray + mnBucketCount));
1916  }
1917 
1918 
1919 
1920 
1921  template <typename K, typename V, typename A, typename EK, typename Eq,
1922  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1923  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator,
1924  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator>
1925  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(const key_type& k) const
1926  {
1927  const hash_code_t c = get_hash_code(k);
1928  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
1929  node_type** head = mpBucketArray + n;
1930  node_type* pNode = DoFindNode(*head, k, c);
1931 
1932  if(pNode)
1933  {
1934  node_type* p1 = pNode->mpNext;
1935 
1936  for(; p1; p1 = p1->mpNext)
1937  {
1938  if(!compare(k, c, p1))
1939  break;
1940  }
1941 
1942  const_iterator first(pNode, head);
1943  const_iterator last(p1, head);
1944 
1945  if(!p1)
1946  last.increment_bucket();
1947 
1948  return eastl::pair<const_iterator, const_iterator>(first, last);
1949  }
1950 
1951  return eastl::pair<const_iterator, const_iterator>(const_iterator(mpBucketArray + mnBucketCount), // iterator(mpBucketArray + mnBucketCount) == end()
1952  const_iterator(mpBucketArray + mnBucketCount));
1953  }
1954 
1955 
1956 
1957  template <typename K, typename V, typename A, typename EK, typename Eq,
1958  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1959  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1960  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode, const key_type& k, hash_code_t c) const
1961  {
1962  for(; pNode; pNode = pNode->mpNext)
1963  {
1964  if(compare(k, c, pNode))
1965  return pNode;
1966  }
1967  return NULL;
1968  }
1969 
1970 
1971 
1972  template <typename K, typename V, typename A, typename EK, typename Eq,
1973  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1974  template <typename U, typename BinaryPredicate>
1975  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
1976  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNodeT(node_type* pNode, const U& other, BinaryPredicate predicate) const
1977  {
1978  for(; pNode; pNode = pNode->mpNext)
1979  {
1980  if(predicate(mExtractKey(pNode->mValue), other)) // Intentionally compare with key as first arg and other as second arg.
1981  return pNode;
1982  }
1983  return NULL;
1984  }
1985 
1986 
1987 
1988  template <typename K, typename V, typename A, typename EK, typename Eq,
1989  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
1990  template <typename BoolConstantT, class... Args, ENABLE_IF_TRUETYPE(BoolConstantT)>
1991  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
1992  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, Args&&... args) // true_type means bUniqueKeys is true.
1993  {
1994  // Adds the value to the hash table if not already present.
1995  // If already present then the existing value is returned via an iterator/bool pair.
1996 
1997  // We have a chicken-and-egg problem here. In order to know if and where to insert the value, we need to get the
1998  // hashtable key for the value. But we don't explicitly have a value argument, we have a templated Args&&... argument.
1999  // We need the value_type in order to proceed, but that entails getting an instance of a value_type from the args.
2000  // And it may turn out that the value is already present in the hashtable and we need to cancel the insertion,
2001  // despite having obtained a value_type to put into the hashtable. We have mitigated this problem somewhat by providing
2002  // specializations of the insert function for const value_type& and value_type&&, and so the only time this function
2003  // should get called is when args refers to arguments to construct a value_type.
2004 
2005  node_type* const pNodeNew = DoAllocateNode(eastl::forward<Args>(args)...);
2006  const key_type& k = mExtractKey(pNodeNew->mValue);
2007  const hash_code_t c = get_hash_code(k);
2008  size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2009  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
2010 
2011  if(pNode == NULL) // If value is not present... add it.
2012  {
2013  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2014 
2015  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2016 
2017  #if EASTL_EXCEPTIONS_ENABLED
2018  try
2019  {
2020  #endif
2021  if(bRehash.first)
2022  {
2023  n = (size_type)bucket_index(k, c, (uint32_t)bRehash.second);
2024  DoRehash(bRehash.second);
2025  }
2026 
2027  EASTL_ASSERT((uintptr_t)mpBucketArray != (uintptr_t)&gpEmptyBucketArray[0]);
2028  pNodeNew->mpNext = mpBucketArray[n];
2029  mpBucketArray[n] = pNodeNew;
2030  ++mnElementCount;
2031 
2032  return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
2033  #if EASTL_EXCEPTIONS_ENABLED
2034  }
2035  catch(...)
2036  {
2037  DoFreeNode(pNodeNew);
2038  throw;
2039  }
2040  #endif
2041  }
2042  else
2043  {
2044  // To do: We have an inefficiency to deal with here. We allocated a node above but we are freeing it here because
2045  // it turned out it wasn't needed. But we needed to create the node in order to get the hashtable key for
2046  // the node. One possible resolution is to create specializations: DoInsertValue(true_type, value_type&&) and
2047  // DoInsertValue(true_type, const value_type&) which don't need to create a node up front in order to get the
2048  // hashtable key. Probably most users would end up using these pathways instead of this Args... pathway.
2049  // While we should considering handling this to-do item, a lot of the performance limitations of maps and sets
2050  // in practice is with finding elements rather than adding (potentially redundant) new elements.
2051  DoFreeNode(pNodeNew);
2052  }
2053 
2054  return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
2055  }
2056 
2057 
2058  template <typename K, typename V, typename A, typename EK, typename Eq,
2059  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2060  template <typename BoolConstantT, class... Args, DISABLE_IF_TRUETYPE(BoolConstantT)>
2061  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2062  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, Args&&... args) // false_type means bUniqueKeys is false.
2063  {
2064  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2065 
2066  if(bRehash.first)
2067  DoRehash(bRehash.second);
2068 
2069  node_type* pNodeNew = DoAllocateNode(eastl::forward<Args>(args)...);
2070  const key_type& k = mExtractKey(pNodeNew->mValue);
2071  const hash_code_t c = get_hash_code(k);
2072  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2073 
2074  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2075 
2076  // To consider: Possibly make this insertion not make equal elements contiguous.
2077  // As it stands now, we insert equal values contiguously in the hashtable.
2078  // The benefit is that equal_range can work in a sensible manner and that
2079  // erase(value) can more quickly find equal values. The downside is that
2080  // this insertion operation taking some extra time. How important is it to
2081  // us that equal_range span all equal items?
2082  node_type* const pNodePrev = DoFindNode(mpBucketArray[n], k, c);
2083 
2084  if(pNodePrev == NULL)
2085  {
2086  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2087  pNodeNew->mpNext = mpBucketArray[n];
2088  mpBucketArray[n] = pNodeNew;
2089  }
2090  else
2091  {
2092  pNodeNew->mpNext = pNodePrev->mpNext;
2093  pNodePrev->mpNext = pNodeNew;
2094  }
2095 
2096  ++mnElementCount;
2097 
2098  return iterator(pNodeNew, mpBucketArray + n);
2099  }
2100 
2101 
2102  template <typename K, typename V, typename A, typename EK, typename Eq,
2103  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2104  template <class... Args>
2105  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
2106  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNode(Args&&... args)
2107  {
2108  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
2109  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
2110 
2111  #if EASTL_EXCEPTIONS_ENABLED
2112  try
2113  {
2114  #endif
2115  ::new(eastl::addressof(pNode->mValue)) value_type(eastl::forward<Args>(args)...);
2116  pNode->mpNext = NULL;
2117  return pNode;
2118  #if EASTL_EXCEPTIONS_ENABLED
2119  }
2120  catch(...)
2121  {
2122  EASTLFree(mAllocator, pNode, sizeof(node_type));
2123  throw;
2124  }
2125  #endif
2126  }
2127 
2128 
2130  // Note: The following insertion-related functions are nearly copies of the above three functions,
2131  // but are for value_type&& and const value_type& arguments. It's useful for us to have the functions
2132  // below, even when using a fully compliant C++11 compiler that supports the above functions.
2133  // The reason is because the specializations below are slightly more efficient because they can delay
2134  // the creation of a node until it's known that it will be needed.
2136 
2137  template <typename K, typename V, typename A, typename EK, typename Eq,
2138  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2139  template <typename BoolConstantT>
2140  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2141  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValueExtra(BoolConstantT, const key_type& k,
2142  hash_code_t c, node_type* pNodeNew, value_type&& value, ENABLE_IF_TRUETYPE(BoolConstantT)) // true_type means bUniqueKeys is true.
2143  {
2144  // Adds the value to the hash table if not already present.
2145  // If already present then the existing value is returned via an iterator/bool pair.
2146  size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2147  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
2148 
2149  if(pNode == NULL) // If value is not present... add it.
2150  {
2151  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2152 
2153  // Allocate the new node before doing the rehash so that we don't
2154  // do a rehash if the allocation throws.
2155  #if EASTL_EXCEPTIONS_ENABLED
2156  bool nodeAllocated; // If exceptions are enabled then we we need to track if we allocated the node so we can free it in the catch block.
2157  #endif
2158 
2159  if(pNodeNew)
2160  {
2161  ::new(eastl::addressof(pNodeNew->mValue)) value_type(eastl::move(value)); // It's expected that pNodeNew was allocated with allocate_uninitialized_node.
2162  #if EASTL_EXCEPTIONS_ENABLED
2163  nodeAllocated = false;
2164  #endif
2165  }
2166  else
2167  {
2168  pNodeNew = DoAllocateNode(eastl::move(value));
2169  #if EASTL_EXCEPTIONS_ENABLED
2170  nodeAllocated = true;
2171  #endif
2172  }
2173 
2174  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2175 
2176  #if EASTL_EXCEPTIONS_ENABLED
2177  try
2178  {
2179  #endif
2180  if(bRehash.first)
2181  {
2182  n = (size_type)bucket_index(k, c, (uint32_t)bRehash.second);
2183  DoRehash(bRehash.second);
2184  }
2185 
2186  EASTL_ASSERT((uintptr_t)mpBucketArray != (uintptr_t)&gpEmptyBucketArray[0]);
2187  pNodeNew->mpNext = mpBucketArray[n];
2188  mpBucketArray[n] = pNodeNew;
2189  ++mnElementCount;
2190 
2191  return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
2192  #if EASTL_EXCEPTIONS_ENABLED
2193  }
2194  catch(...)
2195  {
2196  if(nodeAllocated) // If we allocated the node within this function, free it. Else let the caller retain ownership of it.
2197  DoFreeNode(pNodeNew);
2198  throw;
2199  }
2200  #endif
2201  }
2202  // Else the value is already present, so don't add a new node. And don't free pNodeNew.
2203 
2204  return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
2205  }
2206 
2207 
2208  template <typename K, typename V, typename A, typename EK, typename Eq,
2209  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2210  template <typename BoolConstantT>
2211  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2212  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, value_type&& value, ENABLE_IF_TRUETYPE(BoolConstantT)) // true_type means bUniqueKeys is true.
2213  {
2214  const key_type& k = mExtractKey(value);
2215  const hash_code_t c = get_hash_code(k);
2216 
2217  return DoInsertValueExtra(true_type(), k, c, NULL, eastl::move(value));
2218  }
2219 
2220 
2221  template <typename K, typename V, typename A, typename EK, typename Eq,
2222  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2223  template <typename BoolConstantT>
2224  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2225  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValueExtra(BoolConstantT, const key_type& k, hash_code_t c, node_type* pNodeNew, value_type&& value,
2226  DISABLE_IF_TRUETYPE(BoolConstantT)) // false_type means bUniqueKeys is false.
2227  {
2228  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2229 
2230  if(bRehash.first)
2231  DoRehash(bRehash.second); // Note: We don't need to wrap this call with try/catch because there's nothing we would need to do in the catch.
2232 
2233  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2234 
2235  if(pNodeNew)
2236  ::new(eastl::addressof(pNodeNew->mValue)) value_type(eastl::move(value)); // It's expected that pNodeNew was allocated with allocate_uninitialized_node.
2237  else
2238  pNodeNew = DoAllocateNode(eastl::move(value));
2239 
2240  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2241 
2242  // To consider: Possibly make this insertion not make equal elements contiguous.
2243  // As it stands now, we insert equal values contiguously in the hashtable.
2244  // The benefit is that equal_range can work in a sensible manner and that
2245  // erase(value) can more quickly find equal values. The downside is that
2246  // this insertion operation taking some extra time. How important is it to
2247  // us that equal_range span all equal items?
2248  node_type* const pNodePrev = DoFindNode(mpBucketArray[n], k, c);
2249 
2250  if(pNodePrev == NULL)
2251  {
2252  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2253  pNodeNew->mpNext = mpBucketArray[n];
2254  mpBucketArray[n] = pNodeNew;
2255  }
2256  else
2257  {
2258  pNodeNew->mpNext = pNodePrev->mpNext;
2259  pNodePrev->mpNext = pNodeNew;
2260  }
2261 
2262  ++mnElementCount;
2263 
2264  return iterator(pNodeNew, mpBucketArray + n);
2265  }
2266 
2267 
2268  template <typename K, typename V, typename A, typename EK, typename Eq,
2269  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2270  template<typename BoolConstantT>
2271  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2272  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, value_type&& value, DISABLE_IF_TRUETYPE(BoolConstantT)) // false_type means bUniqueKeys is false.
2273  {
2274  const key_type& k = mExtractKey(value);
2275  const hash_code_t c = get_hash_code(k);
2276 
2277  return DoInsertValueExtra(false_type(), k, c, NULL, eastl::move(value));
2278  }
2279 
2280 
2281  template <typename K, typename V, typename A, typename EK, typename Eq,
2282  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2283  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
2284  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNode(value_type&& value)
2285  {
2286  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
2287  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
2288 
2289  #if EASTL_EXCEPTIONS_ENABLED
2290  try
2291  {
2292  #endif
2293  ::new(eastl::addressof(pNode->mValue)) value_type(eastl::move(value));
2294  pNode->mpNext = NULL;
2295  return pNode;
2296  #if EASTL_EXCEPTIONS_ENABLED
2297  }
2298  catch(...)
2299  {
2300  EASTLFree(mAllocator, pNode, sizeof(node_type));
2301  throw;
2302  }
2303  #endif
2304  }
2305 
2306 
2307  template <typename K, typename V, typename A, typename EK, typename Eq,
2308  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2309  template<typename BoolConstantT>
2310  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2311  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValueExtra(BoolConstantT, const key_type& k, hash_code_t c, node_type* pNodeNew, const value_type& value,
2312  ENABLE_IF_TRUETYPE(BoolConstantT)) // true_type means bUniqueKeys is true.
2313  {
2314  // Adds the value to the hash table if not already present.
2315  // If already present then the existing value is returned via an iterator/bool pair.
2316  size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2317  node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
2318 
2319  if(pNode == NULL) // If value is not present... add it.
2320  {
2321  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2322 
2323  // Allocate the new node before doing the rehash so that we don't
2324  // do a rehash if the allocation throws.
2325  #if EASTL_EXCEPTIONS_ENABLED
2326  bool nodeAllocated; // If exceptions are enabled then we we need to track if we allocated the node so we can free it in the catch block.
2327  #endif
2328 
2329  if(pNodeNew)
2330  {
2331  ::new(eastl::addressof(pNodeNew->mValue)) value_type(value); // It's expected that pNodeNew was allocated with allocate_uninitialized_node.
2332  #if EASTL_EXCEPTIONS_ENABLED
2333  nodeAllocated = false;
2334  #endif
2335  }
2336  else
2337  {
2338  pNodeNew = DoAllocateNode(value);
2339  #if EASTL_EXCEPTIONS_ENABLED
2340  nodeAllocated = true;
2341  #endif
2342  }
2343 
2344  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2345 
2346  #if EASTL_EXCEPTIONS_ENABLED
2347  try
2348  {
2349  #endif
2350  if(bRehash.first)
2351  {
2352  n = (size_type)bucket_index(k, c, (uint32_t)bRehash.second);
2353  DoRehash(bRehash.second);
2354  }
2355 
2356  EASTL_ASSERT((uintptr_t)mpBucketArray != (uintptr_t)&gpEmptyBucketArray[0]);
2357  pNodeNew->mpNext = mpBucketArray[n];
2358  mpBucketArray[n] = pNodeNew;
2359  ++mnElementCount;
2360 
2361  return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
2362  #if EASTL_EXCEPTIONS_ENABLED
2363  }
2364  catch(...)
2365  {
2366  if(nodeAllocated) // If we allocated the node within this function, free it. Else let the caller retain ownership of it.
2367  DoFreeNode(pNodeNew);
2368  throw;
2369  }
2370  #endif
2371  }
2372  // Else the value is already present, so don't add a new node. And don't free pNodeNew.
2373 
2374  return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
2375  }
2376 
2377 
2378  template <typename K, typename V, typename A, typename EK, typename Eq,
2379  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2380  template<typename BoolConstantT>
2381  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2382  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, const value_type& value, ENABLE_IF_TRUETYPE(BoolConstantT)) // true_type means bUniqueKeys is true.
2383  {
2384  const key_type& k = mExtractKey(value);
2385  const hash_code_t c = get_hash_code(k);
2386 
2387  return DoInsertValueExtra(true_type(), k, c, NULL, value);
2388  }
2389 
2390 
2391  template <typename K, typename V, typename A, typename EK, typename Eq,
2392  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2393  template <typename BoolConstantT>
2394  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2395  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValueExtra(BoolConstantT, const key_type& k, hash_code_t c, node_type* pNodeNew, const value_type& value,
2396  DISABLE_IF_TRUETYPE(BoolConstantT)) // false_type means bUniqueKeys is false.
2397  {
2398  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2399 
2400  if(bRehash.first)
2401  DoRehash(bRehash.second); // Note: We don't need to wrap this call with try/catch because there's nothing we would need to do in the catch.
2402 
2403  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2404 
2405  if(pNodeNew)
2406  ::new(eastl::addressof(pNodeNew->mValue)) value_type(value); // It's expected that pNodeNew was allocated with allocate_uninitialized_node.
2407  else
2408  pNodeNew = DoAllocateNode(value);
2409 
2410  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2411 
2412  // To consider: Possibly make this insertion not make equal elements contiguous.
2413  // As it stands now, we insert equal values contiguously in the hashtable.
2414  // The benefit is that equal_range can work in a sensible manner and that
2415  // erase(value) can more quickly find equal values. The downside is that
2416  // this insertion operation taking some extra time. How important is it to
2417  // us that equal_range span all equal items?
2418  node_type* const pNodePrev = DoFindNode(mpBucketArray[n], k, c);
2419 
2420  if(pNodePrev == NULL)
2421  {
2422  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2423  pNodeNew->mpNext = mpBucketArray[n];
2424  mpBucketArray[n] = pNodeNew;
2425  }
2426  else
2427  {
2428  pNodeNew->mpNext = pNodePrev->mpNext;
2429  pNodePrev->mpNext = pNodeNew;
2430  }
2431 
2432  ++mnElementCount;
2433 
2434  return iterator(pNodeNew, mpBucketArray + n);
2435  }
2436 
2437 
2438  template <typename K, typename V, typename A, typename EK, typename Eq,
2439  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2440  template<typename BoolConstantT>
2441  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2442  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(BoolConstantT, const value_type& value, DISABLE_IF_TRUETYPE(BoolConstantT)) // false_type means bUniqueKeys is false.
2443  {
2444  const key_type& k = mExtractKey(value);
2445  const hash_code_t c = get_hash_code(k);
2446 
2447  return DoInsertValueExtra(false_type(), k, c, NULL, value);
2448  }
2449 
2450 
2451  template <typename K, typename V, typename A, typename EK, typename Eq,
2452  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2453  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
2454  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNode(const value_type& value)
2455  {
2456  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
2457  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
2458 
2459  #if EASTL_EXCEPTIONS_ENABLED
2460  try
2461  {
2462  #endif
2463  ::new(eastl::addressof(pNode->mValue)) value_type(value);
2464  pNode->mpNext = NULL;
2465  return pNode;
2466  #if EASTL_EXCEPTIONS_ENABLED
2467  }
2468  catch(...)
2469  {
2470  EASTLFree(mAllocator, pNode, sizeof(node_type));
2471  throw;
2472  }
2473  #endif
2474  }
2475 
2476 
2477  template <typename K, typename V, typename A, typename EK, typename Eq,
2478  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2479  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
2480  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::allocate_uninitialized_node()
2481  {
2482  // We don't wrap this in try/catch because users of this function are expected to do that themselves as needed.
2483  node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), EASTL_ALIGN_OF(node_type), 0);
2484  EASTL_ASSERT_MSG(pNode != nullptr, "the behaviour of eastl::allocators that return nullptr is not defined.");
2485  // Leave pNode->mValue uninitialized.
2486  pNode->mpNext = NULL;
2487  return pNode;
2488  }
2489 
2490 
2491  template <typename K, typename V, typename A, typename EK, typename Eq,
2492  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2493  void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::free_uninitialized_node(node_type* pNode)
2494  {
2495  // pNode->mValue is expected to be uninitialized.
2496  EASTLFree(mAllocator, pNode, sizeof(node_type));
2497  }
2498 
2499 
2500  template <typename K, typename V, typename A, typename EK, typename Eq,
2501  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2502  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2503  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(true_type, const key_type& key, const hash_code_t c) // true_type means bUniqueKeys is true.
2504  {
2505  size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
2506  node_type* const pNode = DoFindNode(mpBucketArray[n], key, c);
2507 
2508  if(pNode == NULL)
2509  {
2510  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2511 
2512  // Allocate the new node before doing the rehash so that we don't
2513  // do a rehash if the allocation throws.
2514  node_type* const pNodeNew = DoAllocateNodeFromKey(key);
2515  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2516 
2517  #if EASTL_EXCEPTIONS_ENABLED
2518  try
2519  {
2520  #endif
2521  if(bRehash.first)
2522  {
2523  n = (size_type)bucket_index(key, c, (uint32_t)bRehash.second);
2524  DoRehash(bRehash.second);
2525  }
2526 
2527  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2528  pNodeNew->mpNext = mpBucketArray[n];
2529  mpBucketArray[n] = pNodeNew;
2530  ++mnElementCount;
2531 
2532  return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
2533  #if EASTL_EXCEPTIONS_ENABLED
2534  }
2535  catch(...)
2536  {
2537  DoFreeNode(pNodeNew);
2538  throw;
2539  }
2540  #endif
2541  }
2542 
2543  return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
2544  }
2545 
2546 
2547 
2548  template <typename K, typename V, typename A, typename EK, typename Eq,
2549  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2550  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2551  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(false_type, const key_type& key, const hash_code_t c) // false_type means bUniqueKeys is false.
2552  {
2553  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2554 
2555  if(bRehash.first)
2556  DoRehash(bRehash.second);
2557 
2558  const size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
2559 
2560  node_type* const pNodeNew = DoAllocateNodeFromKey(key);
2561  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2562 
2563  // To consider: Possibly make this insertion not make equal elements contiguous.
2564  // As it stands now, we insert equal values contiguously in the hashtable.
2565  // The benefit is that equal_range can work in a sensible manner and that
2566  // erase(value) can more quickly find equal values. The downside is that
2567  // this insertion operation taking some extra time. How important is it to
2568  // us that equal_range span all equal items?
2569  node_type* const pNodePrev = DoFindNode(mpBucketArray[n], key, c);
2570 
2571  if(pNodePrev == NULL)
2572  {
2573  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2574  pNodeNew->mpNext = mpBucketArray[n];
2575  mpBucketArray[n] = pNodeNew;
2576  }
2577  else
2578  {
2579  pNodeNew->mpNext = pNodePrev->mpNext;
2580  pNodePrev->mpNext = pNodeNew;
2581  }
2582 
2583  ++mnElementCount;
2584 
2585  return iterator(pNodeNew, mpBucketArray + n);
2586  }
2587 
2588 
2589  template <typename K, typename V, typename A, typename EK, typename Eq,
2590  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2591  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2592  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(true_type, key_type&& key, const hash_code_t c) // true_type means bUniqueKeys is true.
2593  {
2594  size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
2595  node_type* const pNode = DoFindNode(mpBucketArray[n], key, c);
2596 
2597  if(pNode == NULL)
2598  {
2599  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2600 
2601  // Allocate the new node before doing the rehash so that we don't
2602  // do a rehash if the allocation throws.
2603  node_type* const pNodeNew = DoAllocateNodeFromKey(eastl::move(key));
2604  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2605 
2606  #if EASTL_EXCEPTIONS_ENABLED
2607  try
2608  {
2609  #endif
2610  if(bRehash.first)
2611  {
2612  n = (size_type)bucket_index(key, c, (uint32_t)bRehash.second);
2613  DoRehash(bRehash.second);
2614  }
2615 
2616  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2617  pNodeNew->mpNext = mpBucketArray[n];
2618  mpBucketArray[n] = pNodeNew;
2619  ++mnElementCount;
2620 
2621  return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
2622  #if EASTL_EXCEPTIONS_ENABLED
2623  }
2624  catch(...)
2625  {
2626  DoFreeNode(pNodeNew);
2627  throw;
2628  }
2629  #endif
2630  }
2631 
2632  return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
2633  }
2634 
2635 
2636  template <typename K, typename V, typename A, typename EK, typename Eq,
2637  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2638  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2639  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(false_type, key_type&& key, const hash_code_t c) // false_type means bUniqueKeys is false.
2640  {
2641  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
2642 
2643  if(bRehash.first)
2644  DoRehash(bRehash.second);
2645 
2646  const size_type n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
2647 
2648  node_type* const pNodeNew = DoAllocateNodeFromKey(eastl::move(key));
2649  set_code(pNodeNew, c); // This is a no-op for most hashtables.
2650 
2651  // To consider: Possibly make this insertion not make equal elements contiguous.
2652  // As it stands now, we insert equal values contiguously in the hashtable.
2653  // The benefit is that equal_range can work in a sensible manner and that
2654  // erase(value) can more quickly find equal values. The downside is that
2655  // this insertion operation taking some extra time. How important is it to
2656  // us that equal_range span all equal items?
2657  node_type* const pNodePrev = DoFindNode(mpBucketArray[n], key, c);
2658 
2659  if(pNodePrev == NULL)
2660  {
2661  EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
2662  pNodeNew->mpNext = mpBucketArray[n];
2663  mpBucketArray[n] = pNodeNew;
2664  }
2665  else
2666  {
2667  pNodeNew->mpNext = pNodePrev->mpNext;
2668  pNodePrev->mpNext = pNodeNew;
2669  }
2670 
2671  ++mnElementCount;
2672 
2673  return iterator(pNodeNew, mpBucketArray + n);
2674  }
2675 
2676 
2677  template <typename K, typename V, typename A, typename EK, typename Eq,
2678  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2679  template <class... Args>
2680  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2681  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::emplace(Args&&... args)
2682  {
2683  return DoInsertValue(has_unique_keys_type(), eastl::forward<Args>(args)...); // Need to use forward instead of move because Args&& is a "universal reference" instead of an rvalue reference.
2684  }
2685 
2686  template <typename K, typename V, typename A, typename EK, typename Eq,
2687  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2688  template <class... Args>
2689  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2690  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::emplace_hint(const_iterator, Args&&... args)
2691  {
2692  // We currently ignore the iterator argument as a hint.
2693  insert_return_type result = DoInsertValue(has_unique_keys_type(), eastl::forward<Args>(args)...);
2694  return DoGetResultIterator(has_unique_keys_type(), result);
2695  }
2696 
2697  template <typename K, typename V, typename A, typename EK, typename Eq,
2698  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2699  template <class... Args>
2700  // inline eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2701  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2702  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::try_emplace(const key_type& key, Args&&... args)
2703  {
2704  return DoInsertValue(has_unique_keys_type(), piecewise_construct, eastl::forward_as_tuple(key),
2705  eastl::forward_as_tuple(eastl::forward<Args>(args)...));
2706  }
2707 
2708  template <typename K, typename V, typename A, typename EK, typename Eq,
2709  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2710  template <class... Args>
2711  // inline eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2712  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2713  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::try_emplace(key_type&& key, Args&&... args)
2714  {
2715  return DoInsertValue(has_unique_keys_type(), piecewise_construct, eastl::forward_as_tuple(eastl::move(key)),
2716  eastl::forward_as_tuple(eastl::forward<Args>(args)...));
2717  }
2718 
2719  template <typename K, typename V, typename A, typename EK, typename Eq,
2720  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2721  template <class... Args>
2722  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2723  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::try_emplace(const_iterator, const key_type& key, Args&&... args)
2724  {
2725  insert_return_type result = DoInsertValue(
2726  has_unique_keys_type(),
2727  value_type(piecewise_construct, eastl::forward_as_tuple(key), eastl::forward_as_tuple(eastl::forward<Args>(args)...)));
2728 
2729  return DoGetResultIterator(has_unique_keys_type(), result);
2730  }
2731 
2732  template <typename K, typename V, typename A, typename EK, typename Eq,
2733  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2734  template <class... Args>
2735  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2736  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::try_emplace(const_iterator, key_type&& key, Args&&... args)
2737  {
2738  insert_return_type result =
2739  DoInsertValue(has_unique_keys_type(), value_type(piecewise_construct, eastl::forward_as_tuple(eastl::move(key)),
2740  eastl::forward_as_tuple(eastl::forward<Args>(args)...)));
2741 
2742  return DoGetResultIterator(has_unique_keys_type(), result);
2743  }
2744 
2745  template <typename K, typename V, typename A, typename EK, typename Eq,
2746  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2747  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2748  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(value_type&& otherValue)
2749  {
2750  return DoInsertValue(has_unique_keys_type(), eastl::move(otherValue));
2751  }
2752 
2753 
2754  template <typename K, typename V, typename A, typename EK, typename Eq,
2755  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2756  template <class P>
2757  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2758  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(hash_code_t c, node_type* pNodeNew, P&& otherValue)
2759  {
2760  // pNodeNew->mValue is expected to be uninitialized.
2761  value_type value(eastl::forward<P>(otherValue)); // Need to use forward instead of move because P&& is a "universal reference" instead of an rvalue reference.
2762  const key_type& k = mExtractKey(value);
2763  return DoInsertValueExtra(has_unique_keys_type(), k, c, pNodeNew, eastl::move(value));
2764  }
2765 
2766 
2767  template <typename K, typename V, typename A, typename EK, typename Eq,
2768  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2769  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2770  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const_iterator, value_type&& value)
2771  {
2772  // We currently ignore the iterator argument as a hint.
2773  insert_return_type result = DoInsertValue(has_unique_keys_type(), value_type(eastl::move(value)));
2774  return DoGetResultIterator(has_unique_keys_type(), result);
2775  }
2776 
2777 
2778  template <typename K, typename V, typename A, typename EK, typename Eq,
2779  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2780  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2781  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const value_type& value)
2782  {
2783  return DoInsertValue(has_unique_keys_type(), value);
2784  }
2785 
2786 
2787  template <typename K, typename V, typename A, typename EK, typename Eq,
2788  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2789  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2790  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(hash_code_t c, node_type* pNodeNew, const value_type& value)
2791  {
2792  // pNodeNew->mValue is expected to be uninitialized.
2793  const key_type& k = mExtractKey(value);
2794  return DoInsertValueExtra(has_unique_keys_type(), k, c, pNodeNew, value);
2795  }
2796 
2797 
2798  template <typename K, typename V, typename A, typename EK, typename Eq,
2799  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2800  template <typename P, class>
2801  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
2802  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(P&& otherValue)
2803  {
2804  return emplace(eastl::forward<P>(otherValue));
2805  }
2806 
2807 
2808  template <typename K, typename V, typename A, typename EK, typename Eq,
2809  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2810  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2811  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const_iterator, const value_type& value)
2812  {
2813  // We ignore the first argument (hint iterator). It's not likely to be useful for hashtable containers.
2814  insert_return_type result = DoInsertValue(has_unique_keys_type(), value);
2815  return DoGetResultIterator(has_unique_keys_type(), result);
2816  }
2817 
2818 
2819  template <typename K, typename V, typename A, typename EK, typename Eq,
2820  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2821  void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(std::initializer_list<value_type> ilist)
2822  {
2823  insert(ilist.begin(), ilist.end());
2824  }
2825 
2826 
2827  template <typename K, typename V, typename A, typename EK, typename Eq,
2828  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2829  template <typename InputIterator>
2830  void
2831  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(InputIterator first, InputIterator last)
2832  {
2833  const uint32_t nElementAdd = (uint32_t)eastl::ht_distance(first, last);
2834  const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, nElementAdd);
2835 
2836  if(bRehash.first)
2837  DoRehash(bRehash.second);
2838 
2839  for(; first != last; ++first)
2840  DoInsertValue(has_unique_keys_type(), *first);
2841  }
2842 
2843 
2844  template <typename K, typename V, typename A, typename EK, typename Eq,
2845  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2846  template <class M>
2847  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2848  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_or_assign(const key_type& k, M&& obj)
2849  {
2850  auto iter = find(k);
2851  if(iter == end())
2852  {
2853  return insert(value_type(piecewise_construct, eastl::forward_as_tuple(k), eastl::forward_as_tuple(eastl::forward<M>(obj))));
2854  }
2855  else
2856  {
2857  iter->second = eastl::forward<M>(obj);
2858  return {iter, false};
2859  }
2860  }
2861 
2862  template <typename K, typename V, typename A, typename EK, typename Eq,
2863  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2864  template <class M>
2865  eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
2866  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_or_assign(key_type&& k, M&& obj)
2867  {
2868  auto iter = find(k);
2869  if(iter == end())
2870  {
2871  return insert(value_type(piecewise_construct, eastl::forward_as_tuple(eastl::move(k)), eastl::forward_as_tuple(eastl::forward<M>(obj))));
2872  }
2873  else
2874  {
2875  iter->second = eastl::forward<M>(obj);
2876  return {iter, false};
2877  }
2878  }
2879 
2880  template <typename K, typename V, typename A, typename EK, typename Eq,
2881  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2882  template <class M>
2883  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2884  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_or_assign(const_iterator, const key_type& k, M&& obj)
2885  {
2886  return insert_or_assign(k, eastl::forward<M>(obj)).first; // we ignore the iterator hint
2887  }
2888 
2889  template <typename K, typename V, typename A, typename EK, typename Eq,
2890  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2891  template <class M>
2892  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2893  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_or_assign(const_iterator, key_type&& k, M&& obj)
2894  {
2895  return insert_or_assign(eastl::move(k), eastl::forward<M>(obj)).first; // we ignore the iterator hint
2896  }
2897 
2898 
2899  template <typename K, typename V, typename A, typename EK, typename Eq,
2900  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2901  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2902  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(const_iterator i)
2903  {
2904  iterator iNext(i.mpNode, i.mpBucket); // Convert from const_iterator to iterator while constructing.
2905  ++iNext;
2906 
2907  node_type* pNode = i.mpNode;
2908  node_type* pNodeCurrent = *i.mpBucket;
2909 
2910  if(pNodeCurrent == pNode)
2911  *i.mpBucket = pNodeCurrent->mpNext;
2912  else
2913  {
2914  // We have a singly-linked list, so we have no choice but to
2915  // walk down it till we find the node before the node at 'i'.
2916  node_type* pNodeNext = pNodeCurrent->mpNext;
2917 
2918  while(pNodeNext != pNode)
2919  {
2920  pNodeCurrent = pNodeNext;
2921  pNodeNext = pNodeCurrent->mpNext;
2922  }
2923 
2924  pNodeCurrent->mpNext = pNodeNext->mpNext;
2925  }
2926 
2927  DoFreeNode(pNode);
2928  --mnElementCount;
2929 
2930  return iNext;
2931  }
2932 
2933 
2934 
2935  template <typename K, typename V, typename A, typename EK, typename Eq,
2936  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2937  inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
2938  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(const_iterator first, const_iterator last)
2939  {
2940  while(first != last)
2941  first = erase(first);
2942  return iterator(first.mpNode, first.mpBucket);
2943  }
2944 
2945 
2946 
2947  template <typename K, typename V, typename A, typename EK, typename Eq,
2948  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2949  typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
2950  hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(const key_type& k)
2951  {
2952  // To do: Reimplement this function to do a single loop and not try to be
2953  // smart about element contiguity. The mechanism here is only a benefit if the
2954  // buckets are heavily overloaded; otherwise this mechanism may be slightly slower.
2955 
2956  const hash_code_t c = get_hash_code(k);
2957  const size_type n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
2958  const size_type nElementCountSaved = mnElementCount;
2959 
2960  node_type** pBucketArray = mpBucketArray + n;
2961 
2962  while(*pBucketArray && !compare(k, c, *pBucketArray))
2963  pBucketArray = &(*pBucketArray)->mpNext;
2964 
2965  while(*pBucketArray && compare(k, c, *pBucketArray))
2966  {
2967  node_type* const pNode = *pBucketArray;
2968  *pBucketArray = pNode->mpNext;
2969  DoFreeNode(pNode);
2970  --mnElementCount;
2971  }
2972 
2973  return nElementCountSaved - mnElementCount;
2974  }
2975 
2976 
2977 
2978  template <typename K, typename V, typename A, typename EK, typename Eq,
2979  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2980  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear()
2981  {
2982  DoFreeNodes(mpBucketArray, mnBucketCount);
2983  mnElementCount = 0;
2984  }
2985 
2986 
2987 
2988  template <typename K, typename V, typename A, typename EK, typename Eq,
2989  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
2990  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear(bool clearBuckets)
2991  {
2992  DoFreeNodes(mpBucketArray, mnBucketCount);
2993  if(clearBuckets)
2994  {
2995  DoFreeBuckets(mpBucketArray, mnBucketCount);
2996  reset_lose_memory();
2997  }
2998  mnElementCount = 0;
2999  }
3000 
3001 
3002 
3003  template <typename K, typename V, typename A, typename EK, typename Eq,
3004  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3005  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reset_lose_memory() EA_NOEXCEPT
3006  {
3007  // The reset function is a special extension function which unilaterally
3008  // resets the container to an empty state without freeing the memory of
3009  // the contained objects. This is useful for very quickly tearing down a
3010  // container built into scratch memory.
3011  mnBucketCount = 1;
3012 
3013  #ifdef _MSC_VER
3014  mpBucketArray = (node_type**)&gpEmptyBucketArray[0];
3015  #else
3016  void* p = &gpEmptyBucketArray[0];
3017  memcpy(&mpBucketArray, &p, sizeof(mpBucketArray)); // Other compilers implement strict aliasing and casting is thus unsafe.
3018  #endif
3019 
3020  mnElementCount = 0;
3021  mRehashPolicy.mnNextResize = 0;
3022  }
3023 
3024 
3025  template <typename K, typename V, typename A, typename EK, typename Eq,
3026  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3027  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reserve(size_type nElementCount)
3028  {
3029  rehash(mRehashPolicy.GetBucketCount(uint32_t(nElementCount)));
3030  }
3031 
3032 
3033 
3034  template <typename K, typename V, typename A, typename EK, typename Eq,
3035  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3036  inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash(size_type nBucketCount)
3037  {
3038  // Note that we unilaterally use the passed in bucket count; we do not attempt migrate it
3039  // up to the next prime number. We leave it at the user's discretion to do such a thing.
3040  DoRehash(nBucketCount);
3041  }
3042 
3043 
3044 
3045  template <typename K, typename V, typename A, typename EK, typename Eq,
3046  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3047  void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoRehash(size_type nNewBucketCount)
3048  {
3049  node_type** const pBucketArray = DoAllocateBuckets(nNewBucketCount); // nNewBucketCount should always be >= 2.
3050 
3051  #if EASTL_EXCEPTIONS_ENABLED
3052  try
3053  {
3054  #endif
3055  node_type* pNode;
3056 
3057  for(size_type i = 0; i < mnBucketCount; ++i)
3058  {
3059  while((pNode = mpBucketArray[i]) != NULL) // Using '!=' disables compiler warnings.
3060  {
3061  const size_type nNewBucketIndex = (size_type)bucket_index(pNode, (uint32_t)nNewBucketCount);
3062 
3063  mpBucketArray[i] = pNode->mpNext;
3064  pNode->mpNext = pBucketArray[nNewBucketIndex];
3065  pBucketArray[nNewBucketIndex] = pNode;
3066  }
3067  }
3068 
3069  DoFreeBuckets(mpBucketArray, mnBucketCount);
3070  mnBucketCount = nNewBucketCount;
3071  mpBucketArray = pBucketArray;
3072  #if EASTL_EXCEPTIONS_ENABLED
3073  }
3074  catch(...)
3075  {
3076  // A failure here means that a hash function threw an exception.
3077  // We can't restore the previous state without calling the hash
3078  // function again, so the only sensible recovery is to delete everything.
3079  DoFreeNodes(pBucketArray, nNewBucketCount);
3080  DoFreeBuckets(pBucketArray, nNewBucketCount);
3081  DoFreeNodes(mpBucketArray, mnBucketCount);
3082  mnElementCount = 0;
3083  throw;
3084  }
3085  #endif
3086  }
3087 
3088 
3089  template <typename K, typename V, typename A, typename EK, typename Eq,
3090  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3091  inline bool hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate() const
3092  {
3093  // Verify our empty bucket array is unmodified.
3094  if(gpEmptyBucketArray[0] != NULL)
3095  return false;
3096 
3097  if(gpEmptyBucketArray[1] != (void*)uintptr_t(~0))
3098  return false;
3099 
3100  // Verify that we have at least one bucket. Calculations can
3101  // trigger division by zero exceptions otherwise.
3102  if(mnBucketCount == 0)
3103  return false;
3104 
3105  // Verify that gpEmptyBucketArray is used correctly.
3106  // gpEmptyBucketArray is only used when initially empty.
3107  if((void**)mpBucketArray == &gpEmptyBucketArray[0])
3108  {
3109  if(mnElementCount) // gpEmptyBucketArray is used only for empty hash tables.
3110  return false;
3111 
3112  if(mnBucketCount != 1) // gpEmptyBucketArray is used exactly an only for mnBucketCount == 1.
3113  return false;
3114  }
3115  else
3116  {
3117  if(mnBucketCount < 2) // Small bucket counts *must* use gpEmptyBucketArray.
3118  return false;
3119  }
3120 
3121  // Verify that the element count matches mnElementCount.
3122  size_type nElementCount = 0;
3123 
3124  for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
3125  ++nElementCount;
3126 
3127  if(nElementCount != mnElementCount)
3128  return false;
3129 
3130  // To do: Verify that individual elements are in the expected buckets.
3131 
3132  return true;
3133  }
3134 
3135 
3136  template <typename K, typename V, typename A, typename EK, typename Eq,
3137  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3138  int hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate_iterator(const_iterator i) const
3139  {
3140  // To do: Come up with a more efficient mechanism of doing this.
3141 
3142  for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
3143  {
3144  if(temp == i)
3145  return (isf_valid | isf_current | isf_can_dereference);
3146  }
3147 
3148  if(i == end())
3149  return (isf_valid | isf_current);
3150 
3151  return isf_none;
3152  }
3153 
3154 
3155 
3157  // global operators
3159 
3160  // operator==, != have been moved to the specific container subclasses (e.g. hash_map).
3161 
3162  // The following comparison operators are deprecated and will likely be removed in a
3163  // future version of this package.
3164  //
3165  // Comparing hash tables for less-ness is an odd thing to do. We provide it for
3166  // completeness, though the user is advised to be wary of how they use this.
3167  //
3168  template <typename K, typename V, typename A, typename EK, typename Eq,
3169  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3170  inline bool operator<(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
3171  const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
3172  {
3173  // This requires hash table elements to support operator<. Since the hash table
3174  // doesn't compare elements via less (it does so via equals), we must use the
3175  // globally defined operator less for the elements.
3176  return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
3177  }
3178 
3179 
3180  template <typename K, typename V, typename A, typename EK, typename Eq,
3181  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3182  inline bool operator>(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
3183  const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
3184  {
3185  return b < a;
3186  }
3187 
3188 
3189  template <typename K, typename V, typename A, typename EK, typename Eq,
3190  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3191  inline bool operator<=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
3192  const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
3193  {
3194  return !(b < a);
3195  }
3196 
3197 
3198  template <typename K, typename V, typename A, typename EK, typename Eq,
3199  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3200  inline bool operator>=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
3201  const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
3202  {
3203  return !(a < b);
3204  }
3205 
3206 
3207  template <typename K, typename V, typename A, typename EK, typename Eq,
3208  typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
3209  inline void swap(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
3210  const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
3211  {
3212  a.swap(b);
3213  }
3214 
3215 
3216 } // namespace eastl
3217 
3218 
3219 EA_RESTORE_VC_WARNING();
3220 
3221 
3222 #endif // Header include guard
eastl::allocator
Definition: allocator.h:52
eastl::hashtable
Definition: hashtable.h:830
eastl::hashtable::rehash_policy
const rehash_policy_type & rehash_policy() const EA_NOEXCEPT
Definition: hashtable.h:993
eastl::hashtable::rehash_policy
void rehash_policy(const rehash_policy_type &rehashPolicy)
Definition: hashtable.h:1700
eastl::hashtable::find_as
iterator find_as(const U &u, UHash uhash, BinaryPredicate predicate)
Definition: hashtable.h:1744
std::initializer_list
Definition: initializer_list.h:38
eastl
EA Standard Template Library.
Definition: algorithm.h:288
eastl::find
InputIterator find(InputIterator first, InputIterator last, const T &value)
Definition: algorithm.h:1421
eastl::equal_range
pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first, ForwardIterator last, const T &value)
Definition: algorithm.h:2370
eastl::piecewise_construct
EA_CONSTEXPR piecewise_construct_t piecewise_construct
Definition: piecewise_construct_t.h:35
eastl::move
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
Definition: copy_help.h:170
eastl::distance_fw_impl
eastl::iterator_traits< Iterator >::difference_type distance_fw_impl(Iterator, Iterator, EASTL_ITC_NS::input_iterator_tag)
Definition: hashtable.h:365
eastl::gpEmptyBucketArray
EASTL_API void * gpEmptyBucketArray[2]
Definition: hashtable.cpp:24
eastl::addressof
T * addressof(T &value) EA_NOEXCEPT
Definition: memory_base.h:29
eastl::isf_valid
@ isf_valid
This is called none and not called invalid because it is not strictly the opposite of invalid.
Definition: iterator.h:56
eastl::isf_can_dereference
@ isf_can_dereference
The iterator is valid and points to the same element it did when created. For example,...
Definition: iterator.h:58
eastl::isf_current
@ isf_current
The iterator is valid, which means it is in the range of [begin, end].
Definition: iterator.h:57
eastl::lexicographical_compare
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: algorithm.h:1996
eastl::allocate_memory
void * allocate_memory(Allocator &a, size_t n, size_t alignment, size_t alignmentOffset)
Definition: allocator.h:354
eastl::hashtable_find
H::iterator hashtable_find(H &hashTable, U u)
Definition: hashtable.h:1784
eastl::Internal::has_hashcode_member
Definition: hashtable.h:155
eastl::default_ranged_hash
Definition: hashtable.h:406
eastl::equal_to_2
Definition: functional.h:395
eastl::hash_code_base
Definition: hashtable.h:515
eastl::hash_node< Value, false >
Definition: hashtable.h:127
eastl::hash_node
Definition: hashtable.h:107
eastl::hash
Definition: functional.h:1015
eastl::hashtable_iterator_base
Definition: hashtable.h:253
eastl::hashtable_iterator
Definition: hashtable.h:311
eastl::integral_constant
Definition: type_traits.h:263
eastl::iterator
Definition: iterator.h:86
eastl::mod_range_hashing
Definition: hashtable.h:392
eastl::no_type
Definition: type_traits.h:303
eastl::node_iterator_base
Definition: hashtable.h:184
eastl::node_iterator
Definition: hashtable.h:207
eastl::pair
Definition: utility.h:371
eastl::prime_rehash_policy
Definition: hashtable.h:415
eastl::rbtree_iterator
Definition: red_black_tree.h:152
eastl::rehash_base
Definition: hashtable.h:474
eastl::type_select
Definition: type_traits.h:348
Generated by doxygen 1.9.1