text: //-------------------------------------------------------------------------------------------------------
  // Copyright (C) Microsoft. All rights reserved.
  // Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
  //-------------------------------------------------------------------------------------------------------
  #pragma once
  
  //////////////////////////////////////////////////////////////////////////
  // Template implementation of dictionary based on .NET BCL implementation.
  //
  // Buckets and entries are allocated as contiguous arrays to maintain good locality of reference.
  //
  // COLLISION STRATEGY
  // This dictionary uses a chaining collision resolution strategy. Chains are implemented using indexes to the 'buckets' array.
  //
  // STORAGE (TAllocator)
  // This dictionary works for both arena and recycler based allocation using TAllocator template parameter.
  // It supports storing of both value and pointer types. Using template specialization, value types (built-in fundamental
  // types and structs) are stored as leaf nodes by default.
  //
  // INITIAL SIZE and BUCKET MAPPING (SizePolicy)
  // This can be specified using TSizePolicy template parameter. There are 2 implementations:
  //         - PrimeSizePolicy (Better distribution): Initial size is a prime number. Mapping to bucket is done using modulus operation (costlier).
  //         - PowerOf2SizePolicy (faster): Initial size is a power of 2. Mapping to bucket is done by a fast truncating the MSB bits up to the size of the table.
  //
  // COMPARISONS AND HASHCODE (Comparer)
  // Enables custom comparisons for TKey and TValue. For example, for strings we use string comparison instead of comparing pointers.
  //
  
  #if PROFILE_DICTIONARY
  #include "DictionaryStats.h"
  #endif
  
  namespace Js
  {
      template <class TDictionary>
      class RemoteDictionary;
  }
  
  namespace JsDiag
  {
      template <class TDictionary>
      struct RemoteDictionary;
  }
  
  namespace JsUtil
  {
      class NoResizeLock
      {
      public:
          void BeginResize() {}
          void EndResize() {}
      };
  
      class AsymetricResizeLock
      {
      public:
          void BeginResize() { cs.Enter(); }
          void EndResize() { cs.Leave(); }
          void LockResize() { cs.Enter(); }
          void UnlockResize() { cs.Leave(); }
      private:
          CriticalSection cs;
      };
  
      template <class TKey, class TValue> class SimpleDictionaryEntry;
  
      template <
          class TKey,
          class TValue,
          class TAllocator,
          class SizePolicy = PowerOf2SizePolicy,
          template <typename ValueOrKey> class Comparer = DefaultComparer,
          template <typename K, typename V> class Entry = SimpleDictionaryEntry,
          typename Lock = NoResizeLock
      >
      class BaseDictionary : protected Lock
      {
      public:
          typedef TKey KeyType;
          typedef TValue ValueType;
          typedef typename AllocatorInfo<TAllocator, TValue>::AllocatorType AllocatorType;
          typedef SizePolicy CurrentSizePolicy;
          typedef Entry<TKey, TValue> EntryType;
  
          template<class TDictionary> class EntryIterator;
          template<class TDictionary> class BucketEntryIterator;
  
      protected:
          typedef typename AllocatorInfo<TAllocator, TValue>::AllocatorFunc EntryAllocatorFuncType;
          friend class Js::RemoteDictionary<BaseDictionary>;
          template <typename ValueOrKey> struct ComparerType { typedef Comparer<ValueOrKey> Type; }; // Used by diagnostics to access Comparer type
  
          int* buckets;
          EntryType* entries;
          AllocatorType* alloc;
          int size;
          uint bucketCount;
          int count;
          int freeList;
          int freeCount;
  
  #if PROFILE_DICTIONARY
          DictionaryStats *stats;
  #endif
          enum InsertOperations
          {
              Insert_Add   ,          // FatalInternalError if the item already exist in debug build
              Insert_AddNew,          // Ignore add if the item already exist
              Insert_Item             // Replace the item if it already exist
          };
  
          class AutoDoResize
          {
          public:
              AutoDoResize(Lock& lock) : lock(lock) { lock.BeginResize(); };
              ~AutoDoResize() { lock.EndResize(); };
          private:
              Lock& lock;
          };
      public:
          BaseDictionary(AllocatorType* allocator, int capacity = 0)
              : buckets (nullptr),
              size(0),
              bucketCount(0),
              entries(nullptr),
              count(0),
              freeCount(0),
              alloc(allocator)
          {
              Assert(allocator);
  #if PROFILE_DICTIONARY
              stats = nullptr;
  #endif
              // If initial capacity is negative or 0, lazy initialization on
              // the first insert operation is performed.
              if (capacity > 0)
              {
                  Initialize(capacity);
              }
          }
  
          BaseDictionary(const BaseDictionary &other) : alloc(other.alloc)
          {
              if(other.Count() == 0)
              {
                  size = 0;
                  bucketCount = 0;
                  buckets = nullptr;
                  entries = nullptr;
                  count = 0;
                  freeCount = 0;
  
  #if PROFILE_DICTIONARY
                  stats = nullptr;
  #endif
                  return;
              }
  
              Assert(other.bucketCount != 0);
              Assert(other.size != 0);
  
              buckets = AllocateBuckets(other.bucketCount);
              Assert(buckets); // no-throw allocators are currently not supported
  
              try
              {
                  entries = AllocateEntries(other.size, false /* zeroAllocate */);
                  Assert(entries); // no-throw allocators are currently not supported
              }
              catch(...)
              {
                  DeleteBuckets(buckets, other.bucketCount);
                  throw;
              }
  
              size = other.size;
              bucketCount = other.bucketCount;
              count = other.count;
              freeList = other.freeList;
              freeCount = other.freeCount;
  
              size_t copySize = bucketCount * sizeof(buckets[0]);
              js_memcpy_s(buckets, copySize, other.buckets, copySize);
  
              copySize = size * sizeof(entries[0]);
              js_memcpy_s(entries, copySize, other.entries, copySize);
  
  #if PROFILE_DICTIONARY
              stats = DictionaryStats::Create(typeid(this).name(), size);
  #endif
          }
  
          ~BaseDictionary()
          {
              if (buckets)
              {
                  DeleteBuckets(buckets, bucketCount);
              }
  
              if (entries)
              {
                  DeleteEntries(entries, size);
              }
          }
  
          AllocatorType *GetAllocator() const
          {
              return alloc;
          }
  
          inline int Capacity() const
          {
              return size;
          }
  
          inline int Count() const
          {
              return count - freeCount;
          }
  
          TValue Item(const TKey& key)
          {
              int i = FindEntry(key);
              Assert(i >= 0);
              return entries[i].Value();
          }
  
          int Add(const TKey& key, const TValue& value)
          {
              return Insert<Insert_Add>(key, value);
          }
  
          int AddNew(const TKey& key, const TValue& value)
          {
              return Insert<Insert_AddNew>(key, value);
          }
  
          int Item(const TKey& key, const TValue& value)
          {
              return Insert<Insert_Item>(key, value);
          }
  
          bool Contains(KeyValuePair<TKey, TValue> keyValuePair)
          {
              int i = FindEntry(keyValuePair.Key());
              if( i >= 0 && Comparer<TValue>::Equals(entries[i].Value(), keyValuePair.Value()))
              {
                  return true;
              }
              return false;
          }
  
          bool Remove(KeyValuePair<TKey, TValue> keyValuePair)
          {
              int i, last;
              uint targetBucket;
              if(FindEntryWithKey(keyValuePair.Key(), &i, &last, &targetBucket))
              {
                  const TValue &value = entries[i].Value();
                  if(Comparer<TValue>::Equals(value, keyValuePair.Value()))
                  {
                      RemoveAt(i, last, targetBucket);
                      return true;
                  }
              }
              return false;
          }
  
          void Clear()
          {
              if (count > 0)
              {
                  memset(buckets, -1, bucketCount * sizeof(buckets[0]));
                  memset(entries, 0, sizeof(EntryType) * size);
                  count = 0;
                  freeCount = 0;
  #if PROFILE_DICTIONARY
                  // To not loose previously collected data, we will treat cleared dictionary as a separate instance for stats tracking purpose
                  stats = DictionaryStats::Create(typeid(this).name(), size);
  #endif
              }
          }
  
          void ResetNoDelete()
          {
              this->size = 0;
              this->bucketCount = 0;
              this->buckets = nullptr;
              this->entries = nullptr;
              this->count = 0;
              this->freeCount = 0;
          }
  
          void Reset()
          {
              if(bucketCount != 0)
              {
                  DeleteBuckets(buckets, bucketCount);
                  buckets = nullptr;
                  bucketCount = 0;
              }
              else
              {
                  Assert(!buckets);
              }
              if(size != 0)
              {
                  DeleteEntries(entries, size);
                  entries = nullptr;
                  freeCount = count = size = 0;
              }
              else
              {
                  Assert(!entries);
                  Assert(count == 0);
                  Assert(freeCount == 0);
              }
          }
  
          bool ContainsKey(const TKey& key) const
          {
              return FindEntry(key) >= 0;
          }
  
          template <typename TLookup>
          inline const TValue& LookupWithKey(const TLookup& key, const TValue& defaultValue) const
          {
              int i = FindEntryWithKey(key);
              if (i >= 0)
              {
                  return entries[i].Value();
              }
              return defaultValue;
          }
  
          inline const TValue& Lookup(const TKey& key, const TValue& defaultValue)
          {
              return LookupWithKey<TKey>(key, defaultValue);
          }
  
          template <typename TLookup>
          bool TryGetValue(const TLookup& key, TValue* value) const
          {
              int i = FindEntryWithKey(key);
              if (i >= 0)
              {
                  *value = entries[i].Value();
                  return true;
              }
              return false;
          }
  
          bool TryGetValueAndRemove(const TKey& key, TValue* value)
          {
              int i, last;
              uint targetBucket;
              if (FindEntryWithKey(key, &i, &last, &targetBucket))
              {
                  *value = entries[i].Value();
                  RemoveAt(i, last, targetBucket);
                  return true;
              }
              return false;
          }
  
          template <typename TLookup>
          bool TryGetReference(const TLookup& key, const TValue** value) const
          {
              int i;
              return TryGetReference(key, value, &i);
          }
  
          template <typename TLookup>
          bool TryGetReference(const TLookup& key, TValue** value) const
          {
              return TryGetReference(key, const_cast<const TValue **>(value));
          }
  
          template <typename TLookup>
          bool TryGetReference(const TLookup& key, const TValue** value, int* index) const
          {
              int i = FindEntryWithKey(key);
              if (i >= 0)
              {
                  *value = &entries[i].Value();
                  *index = i;
                  return true;
              }
              return false;
          }
  
          template <typename TLookup>
          bool TryGetReference(const TLookup& key, TValue** value, int* index) const
          {
              return TryGetReference(key, const_cast<const TValue **>(value), index);
          }
  
          const TValue& GetValueAt(const int index) const
          {
              Assert(index >= 0);
              Assert(index < count);
  
              return entries[index].Value();
          }
  
          TValue* GetReferenceAt(const int index) const
          {
              Assert(index >= 0);
              Assert(index < count);
  
              return &entries[index].Value();
          }
  
          TKey const& GetKeyAt(const int index) const
          {
              Assert(index >= 0);
              Assert(index < count);
  
              return entries[index].Key();
          }
  
          bool TryGetValueAt(const int index, TValue const ** value) const
          {
              if (index >= 0 && index < count)
              {
                  *value = &entries[index].Value();
                  return true;
              }
              return false;
          }
  
          bool TryGetValueAt(int index, TValue * value) const
          {
              if (index >= 0 && index < count)
              {
                  *value = entries[index].Value();
                  return true;
              }
              return false;
          }
  
          bool Remove(const TKey& key)
          {
              int i, last;
              uint targetBucket;
              if(FindEntryWithKey(key, &i, &last, &targetBucket))
              {
                  RemoveAt(i, last, targetBucket);
                  return true;
              }
              return false;
          }
  
          EntryIterator<const BaseDictionary> GetIterator() const
          {
              return EntryIterator<const BaseDictionary>(*this);
          }
  
          EntryIterator<BaseDictionary> GetIterator()
          {
              return EntryIterator<BaseDictionary>(*this);
          }
  
          BucketEntryIterator<BaseDictionary> GetIteratorWithRemovalSupport()
          {
              return BucketEntryIterator<BaseDictionary>(*this);
          }
  
          template<class Fn>
          bool AnyValue(Fn fn) const
          {
              for (uint i = 0; i < bucketCount; i++)
              {
                  if(buckets[i] != -1)
                  {
                      for (int currentIndex = buckets[i] ; currentIndex != -1 ; currentIndex = entries[currentIndex].next)
                      {
                          if (fn(entries[currentIndex].Value()))
                          {
                              return true;
                          }
                      }
                  }
              }
  
              return false;
          }
  
          template<class Fn>
          void EachValue(Fn fn) const
          {
              for (uint i = 0; i < bucketCount; i++)
              {
                  if(buckets[i] != -1)
                  {
                      for (int currentIndex = buckets[i] ; currentIndex != -1 ; currentIndex = entries[currentIndex].next)
                      {
                          fn(entries[currentIndex].Value());
                      }
                  }
              }
          }
  
          template<class Fn>
          void MapReference(Fn fn)
          {
              MapUntilReference([fn](TKey const& key, TValue& value)
              {
                  fn(key, value);
                  return false;
              });
          }
  
          template<class Fn>
          bool MapUntilReference(Fn fn) const
          {
              return MapEntryUntil([fn](EntryType &entry) -> bool
              {
                  return fn(entry.Key(), entry.Value());
              });
          }
  
          template<class Fn>
          void MapAddress(Fn fn) const
          {
              MapUntilAddress([fn](TKey const& key, TValue * value) -> bool
              {
                  fn(key, value);
                  return false;
              });
          }
  
          template<class Fn>
          bool MapUntilAddress(Fn fn) const
          {
              return MapEntryUntil([fn](EntryType &entry) -> bool
              {
                  return fn(entry.Key(), &entry.Value());
              });
          }
  
          template<class Fn>
          void Map(Fn fn) const
          {
              MapUntil([fn](TKey const& key, TValue const& value) -> bool
              {
                  fn(key, value);
                  return false;
              });
          }
  
          template<class Fn>
          bool MapUntil(Fn fn) const
          {
              return MapEntryUntil([fn](EntryType const& entry) -> bool
              {
                  return fn(entry.Key(), entry.Value());
              });
          }
  
          template<class Fn>
          void MapAndRemoveIf(Fn fn)
          {
              for (uint i = 0; i < bucketCount; i++)
              {
                  if (buckets[i] != -1)
                  {
                      for (int currentIndex = buckets[i], lastIndex = -1; currentIndex != -1;)
                      {
                          // If the predicate says we should remove this item
                          if (fn(entries[currentIndex]) == true)
                          {
                              const int nextIndex = entries[currentIndex].next;
                              RemoveAt(currentIndex, lastIndex, i);
                              currentIndex = nextIndex;
                          }
                          else
                          {
                              lastIndex = currentIndex;
                              currentIndex = entries[currentIndex].next;
                          }
                      }
                  }
              }
          }
  
          template <class Fn>
          bool RemoveIf(TKey const& key, Fn fn)
          {
              return RemoveIfWithKey<TKey>(key, fn);
          }
  
          template <typename LookupType, class Fn>
          bool RemoveIfWithKey(LookupType const& lookupKey, Fn fn)
          {
              int i, last;
              uint targetBucket;
              if (FindEntryWithKey<LookupType>(lookupKey, &i, &last, &targetBucket))
              {
                  if (fn(entries[i].Key(), entries[i].Value()))
                  {
                      RemoveAt(i, last, targetBucket);
                      return true;
                  }
              }
              return false;
          }
  
          // Returns whether the dictionary was resized or not
          bool EnsureCapacity()
          {
              if (freeCount == 0 && count == size)
              {
                  Resize();
                  return true;
              }
  
              return false;
          }
  
          int GetNextIndex()
          {
              if (freeCount != 0)
              {
                  Assert(freeCount > 0);
                  Assert(freeList >= 0);
                  Assert(freeList < count);
                  return freeList;
              }
  
              return count;
          }
  
          int GetLastIndex()
          {
              return count - 1;
          }
  
          BaseDictionary *Clone()
          {
              return AllocatorNew(AllocatorType, alloc, BaseDictionary, *this);
          }
  
          void Copy(const BaseDictionary *const other)
          {
              DoCopy(other);
          }
  
          void LockResize()
          {
              __super::LockResize();
          }
  
          void UnlockResize()
          {
              __super::UnlockResize();
          }
      protected:
          template<class T>
          void DoCopy(const T *const other)
          {
              Assert(size == 0);
              Assert(bucketCount == 0);
              Assert(!buckets);
              Assert(!entries);
              Assert(count == 0);
              Assert(freeCount == 0);
  #if PROFILE_DICTIONARY
              Assert(!stats);
  #endif
  
              if(other->Count() == 0)
              {
                  return;
              }
  
              Assert(other->bucketCount != 0);
              Assert(other->size != 0);
  
              buckets = AllocateBuckets(other->bucketCount);
              Assert(buckets); // no-throw allocators are currently not supported
  
              try
              {
                  entries = AllocateEntries(other->size, false /* zeroAllocate */);
                  Assert(entries); // no-throw allocators are currently not supported
              }
              catch(...)
              {
                  DeleteBuckets(buckets, other->bucketCount);
                  buckets = nullptr;
                  throw;
              }
  
              size = other->size;
              bucketCount = other->bucketCount;
              count = other->count;
              freeList = other->freeList;
              freeCount = other->freeCount;
  
              size_t copySize = bucketCount * sizeof(buckets[0]);
              js_memcpy_s(buckets, copySize, other->buckets, copySize);
  
              copySize = size * sizeof(entries[0]);
              js_memcpy_s(entries, copySize, other->entries, copySize);
  
  #if PROFILE_DICTIONARY
              stats = DictionaryStats::Create(typeid(this).name(), size);
  #endif
          }
  
      protected:
          template<class Fn>
          bool MapEntryUntil(Fn fn) const
          {
              for (uint i = 0; i < bucketCount; i++)
              {
                  if(buckets[i] != -1)
                  {
                      for (int currentIndex = buckets[i] ; currentIndex != -1 ; currentIndex = entries[currentIndex].next)
                      {
                          if (fn(entries[currentIndex]))
                          {
                              return true; // fn condition succeeds
                          }
                      }
                  }
              }
  
              return false;
          }
  
      private:
          template <typename TLookup>
          static hash_t GetHashCodeWithKey(const TLookup& key)
          {
              // set last bit to 1 to avoid false positive to make hash appears to be a valid recycler address.
              // In the same line, 0 should be use to indicate a non-existing entry.
              return TAGHASH(Comparer<TLookup>::GetHashCode(key));
          }
  
          static hash_t GetHashCode(const TKey& key)
          {
              return GetHashCodeWithKey<TKey>(key);
          }
  
          static uint GetBucket(hash_t hashCode, int bucketCount)
          {
              return SizePolicy::GetBucket(UNTAGHASH(hashCode), bucketCount);
          }
  
          uint GetBucket(uint hashCode) const
          {
              return GetBucket(hashCode, this->bucketCount);
          }
  
          static bool IsFreeEntry(const EntryType &entry)
          {
              // A free entry's next index will be (-2 - nextIndex), such that it is always <= -2, for fast entry iteration
              // allowing for skipping over free entries. -1 is reserved for the end-of-chain marker for a used entry.
              return entry.next <= -2;
          }
  
          void SetNextFreeEntryIndex(EntryType &freeEntry, const int nextFreeEntryIndex)
          {
              Assert(!IsFreeEntry(freeEntry));
              Assert(nextFreeEntryIndex >= -1);
              Assert(nextFreeEntryIndex < count);
  
              // The last entry in the free list chain will have a next of -2 to indicate that it is a free entry. The end of the
              // free list chain is identified using freeCount.
              freeEntry.next = nextFreeEntryIndex >= 0 ? -2 - nextFreeEntryIndex : -2;
          }
  
          static int GetNextFreeEntryIndex(const EntryType &freeEntry)
          {
              Assert(IsFreeEntry(freeEntry));
              return -2 - freeEntry.next;
          }
  
          template <typename LookupType>
          __inline int FindEntryWithKey(const LookupType& key) const
          {
  #if PROFILE_DICTIONARY
              uint depth = 0;
  #endif
              int * localBuckets = buckets;
              if (localBuckets != nullptr)
              {
                  hash_t hashCode = GetHashCodeWithKey<LookupType>(key);
                  uint targetBucket = this->GetBucket(hashCode);
                  EntryType * localEntries = entries;
                  for (int i = localBuckets[targetBucket]; i >= 0; i = localEntries[i].next)
                  {
                      if (localEntries[i].KeyEquals<Comparer<TKey>>(key, hashCode))
                      {
  #if PROFILE_DICTIONARY
                          if (stats)
                              stats->Lookup(depth);
  #endif
                          return i;
                      }
  
  #if PROFILE_DICTIONARY
                      depth += 1;
  #endif
                  }
              }
  
  #if PROFILE_DICTIONARY
              if (stats)
                  stats->Lookup(depth);
  #endif
              return -1;
          }
  
          inline int FindEntry(const TKey& key) const
          {
              return FindEntryWithKey<TKey>(key);
          }
  
          template <typename LookupType>
          __inline bool FindEntryWithKey(const LookupType& key, int *const i, int *const last, uint *const targetBucket)
          {
  #if PROFILE_DICTIONARY
              uint depth = 0;
  #endif
              int * localBuckets = buckets;
              if (localBuckets != nullptr)
              {
                  uint hashCode = GetHashCodeWithKey<LookupType>(key);
                  *targetBucket = this->GetBucket(hashCode);
                  *last = -1;
                  EntryType * localEntries = entries;
                  for (*i = localBuckets[*targetBucket]; *i >= 0; *last = *i, *i = localEntries[*i].next)
                  {
                      if (localEntries[*i].KeyEquals<Comparer<TKey>>(key, hashCode))
                      {
  #if PROFILE_DICTIONARY
                          if (stats)
                              stats->Lookup(depth);
  #endif
                          return true;
                      }
  #if PROFILE_DICTIONARY
                      depth += 1;
  #endif
                  }
              }
  #if PROFILE_DICTIONARY
              if (stats)
                  stats->Lookup(depth);
  #endif
              return false;
          }
  
          void Initialize(int capacity)
          {
              // minimum capacity is 4
              int initSize = max(capacity, 4);
              uint initBucketCount = SizePolicy::GetBucketSize(initSize);
              AssertMsg(initBucketCount > 0, "Size returned by policy should be greater than 0");
              Allocate(&buckets, &entries, initBucketCount, initSize);
  
              // Allocation can throw - assign the size only after allocation has succeeded.
              this->bucketCount = initBucketCount;
              this->size = initSize;
              Assert(this->freeCount == 0);
  #if PROFILE_DICTIONARY
              stats = DictionaryStats::Create(typeid(this).name(), size);
  #endif
          }
  
          template <InsertOperations op>
          int Insert(TKey key, TValue value)
          {
              int * localBuckets = buckets;
              if (localBuckets == nullptr)
              {
                  Initialize(0);
                  localBuckets = buckets;
              }
  
  #if DBG || PROFILE_DICTIONARY
              // Always search and verify
              const bool needSearch = true;
  #else
              const bool needSearch = (op != Insert_Add);
  #endif
              hash_t hashCode = GetHashCode(key);
              uint targetBucket = this->GetBucket(hashCode);
              if (needSearch)
              {
  #if PROFILE_DICTIONARY
                  uint depth = 0;
  #endif
                  EntryType * localEntries = entries;
                  for (int i = localBuckets[targetBucket]; i >= 0; i = localEntries[i].next)
                  {
                      if (localEntries[i].KeyEquals<Comparer<TKey>>(key, hashCode))
                      {
  #if PROFILE_DICTIONARY
                          if (stats)
                              stats->Lookup(depth);
  #endif
                          Assert(op != Insert_Add);
                          if (op == Insert_Item)
                          {
                              localEntries[i].SetValue(value);
                              return i;
                          }
                          return -1;
                      }
  #if PROFILE_DICTIONARY
                      depth += 1;
  #endif
                  }
  
  #if PROFILE_DICTIONARY
                  if (stats)
                      stats->Lookup(depth);
  #endif
              }
  
              // Ideally we'd do cleanup only if weak references have been collected since the last resize
              // but that would require us to use an additional field to store the last recycler cleanup id
              // that we saw
              // We can add that optimization later if we have to.
              if (EntryType::SupportsCleanup() && freeCount == 0 && count == size)
              {
                  this->MapAndRemoveIf([](EntryType& entry)
                  {
                      return EntryType::NeedsCleanup(entry);
                  });
              }
  
              int index;
              if (freeCount != 0)
              {
                  Assert(freeCount > 0);
                  Assert(freeList >= 0);
                  Assert(freeList < count);
                  index = freeList;
                  freeCount--;
                  if(freeCount != 0)
                  {
                      freeList = GetNextFreeEntryIndex(entries[index]);
                  }
              }
              else
              {
                  // If there's nothing free, then in general, we set index to count, and increment count
                  // If we resize, we also need to recalculate the target
                  // However, if cleanup is supported, then before resize, we should try and clean up and see
                  // if something got freed, and if it did, reuse that index
                  if (count == size)
                  {
                      Resize();
                      targetBucket = this->GetBucket(hashCode);
                      index = count;
                      count++;
                  }
                  else
                  {
                      index = count;
                      count++;
                  }
  
                  Assert(count <= size);
                  Assert(index < size);
              }
  
              entries[index].Set(key, value, hashCode);
              entries[index].next = buckets[targetBucket];
              buckets[targetBucket] = index;
  
  #if PROFILE_DICTIONARY
              int profileIndex = index;
              uint depth = 1;  // need to recalculate depth in case there was a resize (also 1-based for stats->Insert)
              while(entries[profileIndex].next != -1)
              {
                  profileIndex = entries[profileIndex].next;
                  ++depth;
              }
              if (stats)
                  stats->Insert(depth);
  #endif
              return index;
          }
  
          void Resize()
          {
              AutoDoResize autoDoResize(*this);
  
              int newSize = SizePolicy::GetNextSize(count);
              uint newBucketCount = SizePolicy::GetBucketSize(newSize);
  
              __analysis_assume(newSize > count);
              int* newBuckets = nullptr;
              EntryType* newEntries = nullptr;
              if (newBucketCount == bucketCount)
              {
                  // no need to rehash
                  newEntries = AllocateEntries(newSize);
                  js_memcpy_s(newEntries, sizeof(EntryType) * newSize, entries, sizeof(EntryType) * count);
  
                  DeleteEntries(entries, size);
  
                  this->entries = newEntries;
                  this->size = newSize;
                  return;
              }
  
              Allocate(&newBuckets, &newEntries, newBucketCount, newSize);
              js_memcpy_s(newEntries, sizeof(EntryType) * newSize, entries, sizeof(EntryType) * count);
  
              // When TAllocator is of type Recycler, it is possible that the Allocate above causes a collection, which
              // in turn can cause entries in the dictionary to be removed - i.e. the dictionary contains weak references
              // that remove themselves when no longer valid. This means the free list might not be empty anymore.
              for (int i = 0; i < count; i++)
              {
                  __analysis_assume(i < newSize);
  
                  if (!IsFreeEntry(newEntries[i]))
                  {
                      uint hashCode = newEntries[i].GetHashCode<Comparer<TKey>>();
                      int bucket = GetBucket(hashCode, newBucketCount);
                      newEntries[i].next = newBuckets[bucket];
                      newBuckets[bucket] = i;
                  }
              }
  
              DeleteBuckets(buckets, bucketCount);
              DeleteEntries(entries, size);
  
  #if PROFILE_DICTIONARY
              if (stats)
                  stats->Resize(newSize, /*emptyBuckets=*/ newSize - size);
  #endif
              buckets = newBuckets;
              bucketCount = newBucketCount;
              size = newSize;
              entries = newEntries;
          }
  
          __ecount(bucketCount) int *AllocateBuckets(const uint bucketCount)
          {
              return
                  AllocateArray<AllocatorType, int, false>(
                      TRACK_ALLOC_INFO(alloc, int, AllocatorType, 0, bucketCount),
                      TypeAllocatorFunc<AllocatorType, int>::GetAllocFunc(),
                      bucketCount);
          }
  
          __ecount(size) EntryType * AllocateEntries(int size, const bool zeroAllocate = true)
          {
              // Note that the choice of leaf/non-leaf node is decided for the EntryType on the basis of TValue. By default, if
              // TValue is a pointer, a non-leaf allocation is done. This behavior can be overridden by specializing
              // TypeAllocatorFunc for TValue.
              return
                  AllocateArray<AllocatorType, EntryType, false>(
                      TRACK_ALLOC_INFO(alloc, EntryType, AllocatorType, 0, size),
                      zeroAllocate ? EntryAllocatorFuncType::GetAllocZeroFunc() : EntryAllocatorFuncType::GetAllocFunc(),
                      size);
          }
  
          void DeleteBuckets(__in_ecount(bucketCount) int *const buckets, const uint bucketCount)
          {
              Assert(buckets);
              Assert(bucketCount != 0);
  
              AllocatorFree(alloc, (TypeAllocatorFunc<AllocatorType, int>::GetFreeFunc()), buckets, bucketCount * sizeof(int));
          }
  
          void DeleteEntries(__in_ecount(size) EntryType *const entries, const int size)
          {
              Assert(entries);
              Assert(size != 0);
  
              AllocatorFree(alloc, EntryAllocatorFuncType::GetFreeFunc(), entries, size * sizeof(EntryType));
          }
  
          void Allocate(__deref_out_ecount(bucketCount) int** ppBuckets, __deref_out_ecount(size) EntryType** ppEntries, uint bucketCount, int size)
          {
              int *const buckets = AllocateBuckets(bucketCount);
              Assert(buckets); // no-throw allocators are currently not supported
  
              EntryType *entries;
              try
              {
                  entries = AllocateEntries(size);
                  Assert(entries); // no-throw allocators are currently not supported
              }
              catch(...)
              {
                  DeleteBuckets(buckets, bucketCount);
                  throw;
              }
  
              memset(buckets, -1, bucketCount * sizeof(buckets[0]));
  
              *ppBuckets = buckets;
              *ppEntries = entries;
          }
  
          __inline void RemoveAt(const int i, const int last, const uint targetBucket)
          {
              if (last < 0)
              {
                  buckets[targetBucket] = entries[i].next;
              }
              else
              {
                  entries[last].next = entries[i].next;
              }
              entries[i].Clear();
              SetNextFreeEntryIndex(entries[i], freeCount == 0 ? -1 : freeList);
              freeList = i;
              freeCount++;
  #if PROFILE_DICTIONARY
              if (stats)
                  stats->Remove(buckets[targetBucket] == -1);
  #endif
          }
  
  #if DBG_DUMP
      public:
          void Dump()
          {
              printf("Dumping Dictionary\n");
              printf("-------------------\n");
              for (uint i = 0; i < bucketCount; i++)
              {
                  printf("Bucket value: %d\n", buckets[i]);
                  for (int j = buckets[i]; j >= 0; j = entries[j].next)
                  {
                      printf("%d  => %d  Next: %d\n", entries[j].Key(), entries[j].Value(), entries[j].next);
                  }
              }
          }
  #endif
  
      protected:
          template<class TDictionary, class Leaf>
          class IteratorBase abstract
          {
          protected:
              EntryType *const entries;
              int entryIndex;
  
          #if DBG
          protected:
              TDictionary &dictionary;
          private:
              int usedEntryCount;
          #endif
  
          protected:
              IteratorBase(TDictionary &dictionary, const int entryIndex)
                  : entries(dictionary.entries),
                  entryIndex(entryIndex)
              #if DBG
                  ,
                  dictionary(dictionary),
                  usedEntryCount(dictionary.Count())
              #endif
              {
              }
  
          protected:
              void OnEntryRemoved()
              {
                  DebugOnly(--usedEntryCount);
              }
  
          private:
              bool IsValid_Virtual() const
              {
                  return static_cast<const Leaf *>(this)->IsValid();
              }
  
          protected:
              bool IsValid() const
              {
                  Assert(dictionary.entries == entries);
                  Assert(dictionary.Count() == usedEntryCount);
  
                  return true;
              }
  
          public:
              EntryType &Current() const
              {
                  Assert(IsValid_Virtual());
                  Assert(!IsFreeEntry(entries[entryIndex]));
  
                  return entries[entryIndex];
              }
  
              TKey CurrentKey() const
              {
                  return Current().Key();
              }
  
              const TValue &CurrentValue() const
              {
                  return Current().Value();
              }
  
              TValue &CurrentValueReference() const
              {
                  return Current().Value();
              }
  
              void SetCurrentValue(const TValue &value) const
              {
              #if DBG
                  // For BaseHashSet, save the key before changing the value to verify that the key does not change
                  const TKey previousKey = CurrentKey();
                  const hash_t previousHashCode = GetHashCode(previousKey);
              #endif
  
                  Current().SetValue(value);
  
                  Assert(Current().KeyEquals<Comparer<TKey>>(previousKey, previousHashCode));
              }
          };
  
      public:
          template<class TDictionary>
          class EntryIterator sealed : public IteratorBase<TDictionary, EntryIterator<TDictionary>>
          {
          private:
              typedef IteratorBase<TDictionary, EntryIterator<TDictionary>> Base;
  
          private:
              const int entryCount;
  
          public:
              EntryIterator(TDictionary &dictionary) : Base(dictionary, 0), entryCount(dictionary.count)
              {
                  if(IsValid() && IsFreeEntry(entries[entryIndex]))
                  {
                      MoveNext();
                  }
              }
  
          public:
              bool IsValid() const
              {
                  Assert(dictionary.count == entryCount);
                  Assert(entryIndex >= 0);
                  Assert(entryIndex <= entryCount);
  
                  return Base::IsValid() && entryIndex < entryCount;
              }
  
          public:
              void MoveNext()
              {
                  Assert(IsValid());
  
                  do
                  {
                      ++entryIndex;
                  } while(IsValid() && IsFreeEntry(entries[entryIndex]));
              }
          };
  
      public:
          template<class TDictionary>
          class BucketEntryIterator sealed : public IteratorBase<TDictionary, BucketEntryIterator<TDictionary>>
          {
          private:
              typedef IteratorBase<TDictionary, BucketEntryIterator<TDictionary>> Base;
  
          private:
              TDictionary &dictionary;
              int *const buckets;
              const uint bucketCount;
              uint bucketIndex;
              int previousEntryIndexInBucket;
              int indexOfEntryAfterRemovedEntry;
  
          public:
              BucketEntryIterator(TDictionary &dictionary)
                  : Base(dictionary, -1),
                  dictionary(dictionary),
                  buckets(dictionary.buckets),
                  bucketCount(dictionary.bucketCount),
                  bucketIndex(0u - 1)
              #if DBG
                  ,
                  previousEntryIndexInBucket(-2),
                  indexOfEntryAfterRemovedEntry(-2)
              #endif
              {
                  if(dictionary.Count() != 0)
                  {
                      MoveNextBucket();
                  }
              }
  
          public:
              bool IsValid() const
              {
                  Assert(dictionary.buckets == buckets);
                  Assert(dictionary.bucketCount == bucketCount);
                  Assert(entryIndex >= -1);
                  Assert(entryIndex < dictionary.count);
                  Assert(bucketIndex == 0u - 1 || bucketIndex <= bucketCount);
                  Assert(previousEntryIndexInBucket >= -2);
                  Assert(previousEntryIndexInBucket < dictionary.count);
                  Assert(indexOfEntryAfterRemovedEntry >= -2);
                  Assert(indexOfEntryAfterRemovedEntry < dictionary.count);
  
                  return Base::IsValid() && entryIndex >= 0;
              }
  
          public:
              void MoveNext()
              {
                  if(IsValid())
                  {
                      previousEntryIndexInBucket = entryIndex;
                      entryIndex = Current().next;
                  }
                  else
                  {
                      Assert(indexOfEntryAfterRemovedEntry >= -1);
                      entryIndex = indexOfEntryAfterRemovedEntry;
                  }
  
                  if(!IsValid())
                  {
                      MoveNextBucket();
                  }
              }
  
          private:
              void MoveNextBucket()
              {
                  Assert(!IsValid());
  
                  while(++bucketIndex < bucketCount)
                  {
                      entryIndex = buckets[bucketIndex];
                      if(IsValid())
                      {
                          previousEntryIndexInBucket = -1;
                          break;
                      }
                  }
              }
  
          public:
              void RemoveCurrent()
              {
                  Assert(previousEntryIndexInBucket >= -1);
  
                  indexOfEntryAfterRemovedEntry = Current().next;
                  dictionary.RemoveAt(entryIndex, previousEntryIndexInBucket, bucketIndex);
                  OnEntryRemoved();
                  entryIndex = -1;
              }
          };
  
          template<class TDictionary, class Leaf> friend class IteratorBase;
          template<class TDictionary> friend class EntryIterator;
          template<class TDictionary> friend class BucketEntryIterator;
  
          PREVENT_ASSIGN(BaseDictionary);
      };
  
      template <class TKey, class TValue> class SimpleHashedEntry;
  
      template <
          class TElement,
          class TAllocator,
          class SizePolicy = PowerOf2SizePolicy,
          class TKey = TElement,
          template <typename ValueOrKey> class Comparer = DefaultComparer,
          template <typename, typename> class Entry = SimpleHashedEntry,
          typename Lock = NoResizeLock
      >
      class BaseHashSet : protected BaseDictionary<TKey, TElement, TAllocator, SizePolicy, Comparer, Entry, Lock>
      {
          typedef BaseDictionary<TKey, TElement, TAllocator, SizePolicy, Comparer, Entry, Lock> Base;
          typedef Entry<TKey, TElement> EntryType;
  
          friend struct JsDiag::RemoteDictionary<BaseHashSet<TElement, TAllocator, SizePolicy, TKey, Comparer, Entry, Lock>>;
  
      public:
          BaseHashSet(AllocatorType * allocator, int capacity = 0) : BaseDictionary(allocator, capacity) {}
  
          using Base::GetAllocator;
  
          int Count() const
          {
              return __super::Count();
          }
  
          int Add(TElement const& element)
          {
              return __super::Add(ValueToKey<TKey, TElement>::ToKey(element), element);
          }
  
          // Add only if there isn't an existing element
          int AddNew(TElement const& element)
          {
              return __super::AddNew(ValueToKey<TKey, TElement>::ToKey(element), element);
          }
  
          int Item(TElement const& element)
          {
              return __super::Item(ValueToKey<TKey, TElement>::ToKey(element), element);
          }
  
          void Clear()
          {
              __super::Clear();
          }
  
          using Base::Reset;
  
          TElement const& Lookup(TKey const& key)
          {
              // Use a static to pass the null default value, since the
              // default value may get returned out of the current scope by ref.
              static const TElement nullElement = nullptr;
              return __super::Lookup(key, nullElement);
          }
  
          template <typename KeyType>
          TElement const& LookupWithKey(KeyType const& key)
          {
              static const TElement nullElement = nullptr;
  
              return __super::LookupWithKey(key, nullElement);
          }
  
          bool Contains(TElement const& element) const
          {
              return ContainsKey(ValueToKey<TKey, TElement>::ToKey(element));
          }
  
          using Base::ContainsKey;
          using Base::TryGetValue;
          using Base::TryGetReference;
  
          bool RemoveKey(const TKey &key)
          {
              return Base::Remove(key);
          }
  
          bool Remove(TElement const& element)
          {
              return __super::Remove(ValueToKey<TKey, TElement>::ToKey(element));
          }
  
          EntryIterator<const BaseHashSet> GetIterator() const
          {
              return EntryIterator<const BaseHashSet>(*this);
          }
  
          EntryIterator<BaseHashSet> GetIterator()
          {
              return EntryIterator<BaseHashSet>(*this);
          }
  
          BucketEntryIterator<BaseHashSet> GetIteratorWithRemovalSupport()
          {
              return BucketEntryIterator<BaseHashSet>(*this);
          }
  
          template<class Fn>
          void Map(Fn fn)
          {
              MapUntil([fn](TElement const& value) -> bool
              {
                  fn(value);
                  return false;
              });
          }
  
          template<class Fn>
          void MapAndRemoveIf(Fn fn)
          {
              __super::MapAndRemoveIf([fn](EntryType const& entry) -> bool
              {
                  return fn(entry.Value());
              });
          }
  
          template<class Fn>
          bool MapUntil(Fn fn)
          {
              return __super::MapEntryUntil([fn](EntryType const& entry) -> bool
              {
                  return fn(entry.Value());
              });
          }
  
          bool EnsureCapacity()
          {
              return __super::EnsureCapacity();
          }
  
          int GetNextIndex()
          {
              return __super::GetNextIndex();
          }
  
          int GetLastIndex()
          {
              return __super::GetLastIndex();
          }
  
          using Base::GetValueAt;
  
          bool TryGetValueAt(int index, TElement * value) const
          {
              return __super::TryGetValueAt(index, value);
          }
  
          BaseHashSet *Clone()
          {
              return AllocatorNew(AllocatorType, alloc, BaseHashSet, *this);
          }
  
          void Copy(const BaseHashSet *const other)
          {
              DoCopy(other);
          }
  
          void LockResize()
          {
              __super::LockResize();
          }
  
          void UnlockResize()
          {
              __super::UnlockResize();
          }
      public:
          using Base::EntryIterator;
          using Base::BucketEntryIterator;
  
          friend class Base;
  
          // The following syntax works in BaseDictionary (where the classes are defined), but not in derived
          // classes such as BaseHashSet
          //     template<class TDictionary, class Leaf> friend class IteratorBase;
          //     template<class TDictionary> friend class EntryIterator;
          //     template<class TDictionary> friend class BucketEntryIterator;
          friend class Base::IteratorBase<const BaseHashSet, EntryIterator<const BaseHashSet>>;
          friend class Base::IteratorBase<const BaseHashSet, BucketEntryIterator<const BaseHashSet>>;
          friend class Base::IteratorBase<BaseHashSet, EntryIterator<BaseHashSet>>;
          friend class Base::IteratorBase<BaseHashSet, BucketEntryIterator<BaseHashSet>>;
          friend class EntryIterator<const BaseHashSet>;
          friend class EntryIterator<BaseHashSet>;
          friend class BucketEntryIterator<const BaseHashSet>;
          friend class BucketEntryIterator<BaseHashSet>;
  
          PREVENT_ASSIGN(BaseHashSet);
      };
  
      template <
          class TKey,
          class TValue,
          class TAllocator,
          class SizePolicy = PowerOf2SizePolicy,
          template <typename ValueOrKey> class Comparer = DefaultComparer,
          template <typename K, typename V> class Entry = SimpleDictionaryEntry,
          class LockPolicy = Js::DefaultListLockPolicy,   // Controls lock policy for read/map/write/add/remove items
          class SyncObject = CriticalSection
      >
      class SynchronizedDictionary: protected BaseDictionary<TKey, TValue, TAllocator, SizePolicy, Comparer, Entry>
      {
      private:
          SyncObject* syncObj;
  
      public:
          typedef TKey KeyType;
          typedef TValue ValueType;
          typedef BaseDictionary<TKey, TValue, TAllocator, SizePolicy, Comparer, Entry>::EntryType EntryType;
          typedef SynchronizedDictionary<TKey, TValue, TAllocator, SizePolicy, Comparer, Entry, LockPolicy, SyncObject> DictionaryType;
      private:
          friend class Js::RemoteDictionary<DictionaryType>;
  
      public:
          SynchronizedDictionary(AllocatorType * allocator, int capacity, SyncObject* syncObject):
              BaseDictionary(allocator, capacity),
              syncObj(syncObject)
          {}
  
  #ifdef DBG
          void Dump()
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              __super::Dump();
          }
  #endif
  
          TAllocator *GetAllocator() const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::GetAllocator();
          }
  
          inline int Count() const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Count();
          }
  
          inline int Capacity() const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Capacity();
          }
  
          TValue Item(const TKey& key)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Item(key);
          }
  
          bool IsInAdd()
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::IsInAdd();
          }
  
          int Add(const TKey& key, const TValue& value)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::Add(key, value);
          }
  
          int AddNew(const TKey& key, const TValue& value)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::AddNew(key, value);
          }
  
          int Item(const TKey& key, const TValue& value)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::Item(key, value);
          }
  
          bool Contains(KeyValuePair<TKey, TValue> keyValuePair)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Contains(keyValuePair);
          }
  
          bool Remove(KeyValuePair<TKey, TValue> keyValuePair)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::Remove(keyValuePair);
          }
  
          void Clear()
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::Clear();
          }
  
          void Reset()
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::Reset();
          }
  
          bool ContainsKey(const TKey& key)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::ContainsKey(key);
          }
  
          template <typename TLookup>
          inline const TValue& LookupWithKey(const TLookup& key, const TValue& defaultValue)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::LookupWithKey(key, defaultValue);
          }
  
          inline const TValue& Lookup(const TKey& key, const TValue& defaultValue)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Lookup(key, defaultValue);
          }
  
          template <typename TLookup>
          bool TryGetValue(const TLookup& key, TValue* value)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::TryGetValue(key, value);
          }
  
          bool TryGetValueAndRemove(const TKey& key, TValue* value)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::TryGetValueAndRemove(key, value);
          }
  
          template <typename TLookup>
          __inline bool TryGetReference(const TLookup& key, TValue** value)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::TryGetReference(key, value);
          }
  
          template <typename TLookup>
          __inline bool TryGetReference(const TLookup& key, TValue** value, int* index)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::TryGetReference(key, value, index);
          }
  
          const TValue& GetValueAt(const int& index) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::GetValueAt(index);
          }
  
          TValue* GetReferenceAt(const int& index)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::GetReferenceAt(index);
          }
  
          TKey const& GetKeyAt(const int& index)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::GetKeyAt(index);
          }
  
          bool Remove(const TKey& key)
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Remove(key);
          }
  
          template<class Fn>
          void MapReference(Fn fn)
          {
              // TODO: Verify that Map doesn't actually modify the list
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::MapReference(fn);
          }
  
          template<class Fn>
          bool MapUntilReference(Fn fn) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::MapUntilReference(fn);
          }
  
          template<class Fn>
          void MapAddress(Fn fn) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::MapAddress(fn);
          }
  
          template<class Fn>
          bool MapUntilAddress(Fn fn) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::MapUntilAddress(fn);
          }
  
          template<class Fn>
          void Map(Fn fn) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::Map(fn);
          }
  
          template<class Fn>
          bool MapUntil(Fn fn) const
          {
              LockPolicy::ReadLock autoLock(syncObj);
  
              return __super::MapUntil(fn);
          }
  
          template<class Fn>
          void MapAndRemoveIf(Fn fn)
          {
              LockPolicy::AddRemoveLock autoLock(syncObj);
  
              return __super::MapAndRemoveIf(fn);
          }
  
          PREVENT_COPY(SynchronizedDictionary);
      };
  }
  
  