lib/Common/DataStructures/WeakReferenceDictionary.h - external/github.com/Microsoft/ChakraCore - Git at Google

 //-------------------------------------------------------------------------------------------------------
 // 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

 namespace JsUtil
 {
     interface IWeakReferenceDictionary
     {
         virtual void Cleanup() = 0;
     };

     template <
         class TKey,
         class TValue,
         class SizePolicy = PowerOf2SizePolicy,
         template <typename ValueOrKey> class Comparer = DefaultComparer
     >
     class WeakReferenceDictionary: public BaseDictionary<TKey, RecyclerWeakReference<TValue>*, RecyclerNonLeafAllocator, SizePolicy, Comparer, WeakRefValueDictionaryEntry>,
                                    public IWeakReferenceDictionary
     {
         typedef BaseDictionary<TKey, RecyclerWeakReference<TValue>*, RecyclerNonLeafAllocator, SizePolicy, Comparer, WeakRefValueDictionaryEntry> Base;
         typedef typename Base::EntryType EntryType;

     public:
         WeakReferenceDictionary(Recycler* recycler, int capacity = 0):
           Base(recycler, capacity)
         {
             Assert(reinterpret_cast<void*>(this) == reinterpret_cast<void*>((IWeakReferenceDictionary*) this));
         }

         virtual void Cleanup() override
         {
             this->MapAndRemoveIf([](typename Base::EntryType &entry)
             {
                 return (Base::EntryType::NeedsCleanup(entry));
             });
         }

     private:
         using Base::Clone;
         using Base::Copy;

         PREVENT_COPY(WeakReferenceDictionary);
     };

 #if ENABLE_WEAK_REFERENCE_REGIONS

     template<bool, typename T = void>
     struct enable_if {};

     template<typename T>
     struct enable_if<true, T>
     {
         typedef T type;
     };

     template <
         class TEntry,
         class TWeak,
         bool keyIsWeak,
         class SizePolicy = PowerOf2SizePolicy,
         template <typename ValueOrKey> class Comparer = DefaultComparer,
         typename Lock = NoResizeLock,
         class AllocType = Recycler // Should always be recycler; this is to sufficiently confuse the RecyclerChecker
     >
     class SplitWeakDictionary : protected Lock, public IWeakReferenceDictionary
     {
     private:
         template <typename T1, typename T2, bool second>
         struct Select;

         template <typename T1, typename T2>
         struct Select<T1, T2, false>
         {
             typedef T1 type;
         };

         template <typename T1, typename T2>
         struct Select<T1, T2, true>
         {
             typedef T2 type;
         };

         typedef typename Select<TEntry, TWeak, keyIsWeak>::type TBKey;
         typedef typename Select<TEntry, TWeak, !keyIsWeak>::type TBValue;

         typedef typename AllocatorInfo<Recycler, TEntry>::AllocatorFunc EntryAllocatorFuncType;

         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
         };

     protected:

         typedef ValueEntry<TEntry> EntryType;
         typedef RecyclerWeakReferenceRegionItem<TWeak> WeakType;

         Field(int*) buckets;
         Field(EntryType*) entries;
         Field(WeakType*) weakRefs;
         FieldNoBarrier(Recycler*) alloc;
         Field(int) size;
         Field(uint) bucketCount;
         Field(int) count;
         Field(int) freeList;
         Field(int) freeCount;
         Field(int) modFunctionIndex;

     private:
         static const int FreeListSentinel = -2;

         PREVENT_COPY(SplitWeakDictionary);


         class AutoDoResize
         {
         public:
             AutoDoResize(Lock& lock) : lock(lock) { lock.BeginResize(); };
             ~AutoDoResize() { lock.EndResize(); };
         private:
             Lock & lock;
         };

     public:
         // Allow SplitWeakDictionary field to be inlined in classes with DEFINE_VTABLE_CTOR_MEMBER_INIT
         SplitWeakDictionary(VirtualTableInfoCtorEnum) { }

         SplitWeakDictionary(Recycler* allocator, int capacity = 0)
             : buckets(nullptr),
             entries(nullptr),
             weakRefs(nullptr),
             alloc(allocator),
             size(0),
             bucketCount(0),
             count(0),
             freeList(0),
             freeCount(0),
             modFunctionIndex(UNKNOWN_MOD_INDEX)
         {
             Assert(allocator);
             Assert(reinterpret_cast<void*>(this) == reinterpret_cast<void*>((IWeakReferenceDictionary*)this));

             // If initial capacity is negative or 0, lazy initialization on
             // the first insert operation is performed.
             if (capacity > 0)
             {
                 Initialize(capacity);
             }
         }

         virtual void Cleanup() override
         {
             this->MapAndRemoveIf([](EntryType& entry, WeakType& weakRef)
             {
                 return weakRef == nullptr;
             });
         }

         inline int Capacity() const
         {
             return size;
         }

         inline int Count() const
         {
             return count - freeCount;
         }

         void Clear()
         {
             if (count > 0)
             {
                 memset(buckets, -1, bucketCount * sizeof(buckets[0]));
                 memset(entries, 0, sizeof(EntryType) * size);
                 memset(weakRefs, 0, sizeof(WeakType) * size); // TODO: issues with background threads?
                 count = 0;
                 freeCount = 0;
             }
         }

         void ResetNoDelete()
         {
             this->size = 0;
             this->bucketCount = 0;
             this->buckets = nullptr;
             this->entries = nullptr;
             this->weakRefs = nullptr;
             this->count = 0;
             this->freeCount = 0;
             this->modFunctionIndex = UNKNOWN_MOD_INDEX;
         }

         void Reset()
         {
             ResetNoDelete();
         }

         // 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;
         }

         TBValue Item(const TBKey& key)
         {
             int i = FindEntry(key);
             Assert(i >= 0);
             return values[i];
         }

         TBValue Item(const TBKey& key) const
         {
             int i = FindEntry(key);
             Assert(i >= 0);
             return values[i];
         }

         int Add(const TBKey& key, const TBValue& value)
         {
             return Insert<Insert_Add>(key, value);
         }

         int AddNew(const TBKey& key, const TBValue& value)
         {
             return Insert<Insert_AddNew>(key, value);
         }

         int Item(const TBKey& key, const TBValue& value)
         {
             return Insert<Insert_Item>(key, value);
         }

         bool Contains(KeyValuePair<TBKey, TBValue> keyValuePair)
         {
             int i = FindEntry(keyValuePair.Key());
             TBValue val = this->GetValue(i);
             if (i >= 0 && Comparer<TBValue>::Equals(val, keyValuePair.Value()))
             {
                 return true;
             }
             return false;
         }

         bool ContainsKey(const TBKey& key) const
         {
             return FindEntry(key) >= 0;
         }

         template <typename TLookup>
         inline const TBValue& LookupWithKey(const TLookup& key, const TBValue& defaultValue)
         {
             int i = FindEntryWithKey(key);
             if (i >= 0)
             {
                 return this->GetValue(i);
             }
             return defaultValue;
         }

         inline const TBValue& Lookup(const TBKey& key, const TBValue& defaultValue)
         {
             return LookupWithKey<TBKey>(key, defaultValue);
         }

         template <typename TLookup>
         bool TryGetValue(const TLookup& key, TBValue* value)
         {
             int i = FindEntryWithKey(key);
             if (i >= 0)
             {
                 *value = this->GetValue(i);
                 return true;
             }
             return false;
         }


         bool TryGetValueAndRemove(const TBKey& key, TBValue* value)
         {
             int i, last;
             uint targetBucket;
             if (FindEntryWithKey(key, &i, &last, &targetBucket))
             {
                 *value = this->GetValue(i);
                 RemoveAt(i, last, targetBucket);
                 return true;
             }
             return false;
         }

         bool Remove(const TBKey& key)
         {
             int i, last;
             uint targetBucket;
             if (FindEntryWithKey(key, &i, &last, &targetBucket))
             {
                 RemoveAt(i, last, targetBucket);
                 return true;
             }
             return false;
         }

         bool Remove(KeyValuePair<TBKey, TBValue> keyValuePair)
         {
             int i, last;
             uint targetBucket;
             if (FindEntryWithKey(keyValuePair.Key(), &i, &last, &targetBucket))
             {
                 const TBValue& value = this->GetValue(i);
                 if (Comparer<TBValue>::Equals(value, keyValuePair.Value()))
                 {
                     RemoveAt(i, last, targetBucket);
                     return true;
                 }
             }
             return false;
         }

         int GetLastIndex()
         {
             return count - 1;
         }

         void LockResize()
         {
             __super::LockResize();
         }

         void UnlockResize()
         {
             __super::UnlockResize();
         }

     protected:

         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], weakRefs[currentIndex]) == true)
                         {
                             const int nextIndex = entries[currentIndex].next;
                             RemoveAt(currentIndex, lastIndex, i);
                             currentIndex = nextIndex;
                         }
                         else
                         {
                             lastIndex = currentIndex;
                             currentIndex = entries[currentIndex].next;
                         }
                     }
                 }
             }
         }

         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 uint GetBucket(hash_t hashCode, int bucketCount, int modFunctionIndex)
         {
             return SizePolicy::GetBucket(UNTAGHASH(hashCode), bucketCount, modFunctionIndex);
         }

         uint GetBucket(hash_t hashCode) const
         {
             return GetBucket(hashCode, this->bucketCount, modFunctionIndex);
         }

         static bool IsFreeEntry(const EntryType &entry)
         {
             // A free entry's next index will be (FreeListSentinel - nextIndex), such that it is always <= FreeListSentinel, 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 <= FreeListSentinel;
         }


         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 FreeListSentinel to indicate that it is a free entry. The end of the
             // free list chain is identified using freeCount.
             freeEntry.next = nextFreeEntryIndex >= 0 ? FreeListSentinel - nextFreeEntryIndex : FreeListSentinel;
         }

         static int GetNextFreeEntryIndex(const EntryType &freeEntry)
         {
             Assert(IsFreeEntry(freeEntry));
             return FreeListSentinel - freeEntry.next;
         }

         void Initialize(int capacity)
         {
             // minimum capacity is 4
             int initSize = max(capacity, 4);
             int modIndex = UNKNOWN_MOD_INDEX;
             uint initBucketCount = SizePolicy::GetBucketSize(initSize, &modIndex);
             AssertMsg(initBucketCount > 0, "Size returned by policy should be greater than 0");

             int* newBuckets = nullptr;
             EntryType* newEntries = nullptr;
             WeakType* newWeakRefs = nullptr;
             Allocate(&newBuckets, &newEntries, &newWeakRefs, initBucketCount, initSize);

             // Allocation can throw - assign only after allocation has succeeded.
             this->buckets = newBuckets;
             this->entries = newEntries;
             this->weakRefs = newWeakRefs;
             this->bucketCount = initBucketCount;
             this->size = initSize;
             this->modFunctionIndex = modIndex;
             Assert(this->freeCount == 0);
         }

         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();
             weakRefs[i].Clear();
             SetNextFreeEntryIndex(entries[i], freeCount == 0 ? -1 : freeList);
             freeList = i;
             freeCount++;
         }

         inline int FindEntry(const TBKey& key)
         {
             return FindEntryWithKey<TBKey>(key);
         }

         template <typename LookupType>
         inline int FindEntryWithKey(const LookupType& key)
         {
             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], last = -1; i >= 0;)
                 {
                     TBKey k = this->GetKey(i);
                     if (this->RemoveIfCollected(k, &i, last, targetBucket))
                     {
                         continue;
                     }
                     if (Comparer<TBKey>::Equals(k, key))
                     {
                         return i;
                     }

                     last = i;
                     i = localEntries[i].next;
                 }
             }
             return -1;
         }

         template <typename LookupType>
         inline bool FindEntryWithKey(const LookupType& key, int *const i, int *const last, uint *const targetBucket)
         {
             int * localBuckets = buckets;
             if (localBuckets != nullptr)
             {
                 hash_t hashCode = GetHashCodeWithKey<LookupType>(key);
                 *targetBucket = this->GetBucket(hashCode);
                 *last = -1;
                 EntryType * localEntries = entries;
                 for (*i = localBuckets[*targetBucket]; *i >= 0;)
                 {
                     TBKey k = this->GetKey(*i);
                     if (this->RemoveIfCollected(k, i, *last, *targetBucket))
                     {
                         continue;
                     }
                     if (Comparer<TBKey>::Equals(k, key))
                     {
                         return true;
                     }

                     *last = *i;
                     *i = localEntries[*i].next;
                 }
             }
             return false;
         }

     private:

         void Resize()
         {
             AutoDoResize autoDoResize(*this);
             __analysis_assert(count > 1);

             int newSize = SizePolicy::GetNextSize(count);
             int modIndex = UNKNOWN_MOD_INDEX;
             uint newBucketCount = SizePolicy::GetBucketSize(newSize, &modIndex);

             __analysis_assume(newSize > count);
             int* newBuckets = nullptr;
             EntryType* newEntries = nullptr;
             WeakType* newWeakRefs = nullptr;
             if (newBucketCount == bucketCount)
             {
                 // no need to rehash
                 newEntries = AllocateEntries(newSize);
                 newWeakRefs = AllocateWeakRefs(newSize);
                 CopyArray<EntryType>(newEntries, newSize, entries, count);
                 CopyArray<WeakType>(newWeakRefs, newSize, weakRefs, count); // TODO: concurrency issues?

                 this->entries = newEntries;
                 this->weakRefs = newWeakRefs;
                 this->size = newSize;
                 this->modFunctionIndex = modIndex;
                 return;
             }

             Allocate(&newBuckets, &newEntries, &newWeakRefs, newBucketCount, newSize);

             this->modFunctionIndex = modIndex;

             // Need to re-bucket the entries
             // Also need to account for whether the weak refs have been collected
             // Have to go in order so we can remove entries as appropriate
             this->count = 0;
             for (uint i = 0; i < this->bucketCount; ++i)
             {
                 if (this->buckets[i] < 0)
                 {
                     continue;
                 }

                 for (int currentEntry = this->buckets[i]; currentEntry != -1; )
                 {
                     if (IsFreeEntry(entries[currentEntry]))
                     {
                         // Entry is free; this shouldn't happen, but stop following the chain
                         AssertMsg(false, "Following bucket chains should not result in free entries");
                         break;
                     }
                     if (this->weakRefs[currentEntry] == nullptr)
                     {
                         // The weak ref has been collected; don't bother bringing it to the new collection
                         currentEntry = this->entries[currentEntry].next;
                         continue;
                     }

                     hash_t hashCode = GetHashCodeWithKey<TBKey>(this->GetKey(currentEntry));
                     int bucket = GetBucket(hashCode, newBucketCount, modFunctionIndex);
                     newEntries[count].next = newBuckets[bucket];
                     newEntries[count].SetValue(this->entries[currentEntry].Value());
                     newWeakRefs[count] = this->weakRefs[currentEntry];
                     newBuckets[bucket] = count;
                     ++count;

                     currentEntry = this->entries[currentEntry].next;
                 }
             }
             this->freeCount = 0;
             this->freeList = 0;
             this->buckets = newBuckets;
             this->entries = newEntries;
             this->weakRefs = newWeakRefs;
             this->bucketCount = newBucketCount;
             this->size = newSize;

         }

         template <InsertOperations op>
         int Insert(const TBKey& key, const TBValue& value)
         {
             int * localBuckets = buckets;
             if (localBuckets == nullptr)
             {
                 Initialize(0);
                 localBuckets = buckets;
             }

 #if DBG
             // Always search and verify
             const bool needSearch = true;
 #else
             const bool needSearch = (op != Insert_Add);
 #endif
             hash_t hashCode = GetHashCodeWithKey<TBKey>(key);
             uint targetBucket = this->GetBucket(hashCode);
             if (needSearch)
             {
                 EntryType * localEntries = entries;
                 for (int i = localBuckets[targetBucket], last = -1; i >= 0;)
                 {
                     TBKey k = this->GetKey(i);
                     if (this->RemoveIfCollected(k, &i, last, targetBucket))
                     {
                         continue;
                     }

                     if (Comparer<TBKey>::Equals(k, key))
                     {
                         Assert(op != Insert_Add);
                         if (op == Insert_Item)
                         {
                             SetValue(value, i);
                             return i;
                         }
                         return -1;
                     }

                     last = i;
                     i = localEntries[i].next;
                 }
             }

             // 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 (freeCount == 0 && count == size)
             {
                 this->Cleanup();
             }

             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);
             }

             SetKeyValue(key, value, index);
             entries[index].next = buckets[targetBucket];
             buckets[targetBucket] = index;

             return index;
         }

         __ecount(bucketCount) int *AllocateBuckets(DECLSPEC_GUARD_OVERFLOW const uint bucketCount)
         {
             return
                 AllocateArray<AllocType, int, false>(
                     TRACK_ALLOC_INFO(alloc, int, AllocType, 0, bucketCount),
                     TypeAllocatorFunc<AllocType, int>::GetAllocFunc(),
                     bucketCount);
         }

         __ecount(size) EntryType * AllocateEntries(DECLSPEC_GUARD_OVERFLOW 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<Recycler, EntryType, false>(
                     TRACK_ALLOC_INFO(alloc, EntryType, Recycler, 0, size),
                     zeroAllocate ? EntryAllocatorFuncType::GetAllocZeroFunc() : EntryAllocatorFuncType::GetAllocFunc(),
                     size);
         }

         __ecount(size) WeakType * AllocateWeakRefs(DECLSPEC_GUARD_OVERFLOW int size)
         {
             return alloc->CreateWeakReferenceRegion<TWeak>(size);
         }


         void Allocate(__deref_out_ecount(bucketCount) int** ppBuckets, __deref_out_ecount(size) EntryType** ppEntries, __deref_out_ecount(size) WeakType** ppWeakRefs, DECLSPEC_GUARD_OVERFLOW uint bucketCount, DECLSPEC_GUARD_OVERFLOW int size)
         {
             int *const newBuckets = AllocateBuckets(bucketCount);
             Assert(newBuckets); // no-throw allocators are currently not supported

             EntryType *newEntries = AllocateEntries(size);
             Assert(newEntries); // no-throw allocators are currently not supported

             WeakType * newWeakRefs = AllocateWeakRefs(size);

             memset(newBuckets, -1, bucketCount * sizeof(newBuckets[0]));

             *ppBuckets = newBuckets;
             *ppEntries = newEntries;
             *ppWeakRefs = newWeakRefs;
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<weakKey, TBKey>::type GetKey(int index) const
         {
             return this->weakRefs[index];
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<!weakKey, TBKey>::type GetKey(int index) const
         {
             return this->entries[index].Value();
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<weakKey, TBValue>::type GetValue(int index) const
         {
             return this->entries[index].Value();
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<!weakKey, TBValue>::type GetValue(int index) const
         {
             return this->weakRefs[index];
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<weakKey, bool>::type RemoveIfCollected(TBKey const key, int* i, int last, int targetBucket)
         {
             if (key == nullptr)
             {
                 // Key has been collected
                 int next = entries[*i].next;
                 RemoveAt(*i, last, targetBucket);
                 *i = next;
                 return true;
             }
             return false;
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<!weakKey, bool>::type RemoveIfCollected(TBKey const key, int* i, int last, int targetBucket)
         {
             return false;
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<weakKey, void>::type SetKeyValue(const TBKey& key, const TBValue& value, int index)
         {
             weakRefs[index] = key;
             entries[index].SetValue(value);
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<!weakKey, void>::type SetKeyValue(const TBKey& key, const TBValue& value, int index)
         {
             entries[index].SetValue(key);
             weakRefs[index] = value;
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<weakKey, void>::type SetValue(const TBValue& value, int index)
         {
             this->entries[index].SetValue(value);
         }

         template <bool weakKey = keyIsWeak>
         inline typename enable_if<!weakKey, void>::type SetValue(const TBValue& value, int index)
         {
             this->weakRefs[index] = value;
         }
     };

     template <
         class TKey,
         class TValue,
         class SizePolicy = PowerOf2SizePolicy,
         template <typename ValueOrKey> class Comparer = DefaultComparer,
         typename Lock = NoResizeLock
     >
     class WeakReferenceRegionDictionary : public SplitWeakDictionary<TKey, TValue, false, SizePolicy, Comparer, Lock, Recycler>
     {
         typedef SplitWeakDictionary<TKey, TValue, false, SizePolicy, Comparer, Lock, Recycler> Base;
         typedef typename Base::EntryType EntryType;
         typedef typename Base::WeakType ValueType;

     public:

         WeakReferenceRegionDictionary(Recycler* allocator, int capacity = 0)
             : Base(allocator, capacity)
         {
         }
     };

     template <
         class TKey,
         class TValue,
         template <typename ValueOrKey> class Comparer = DefaultComparer,
         class SizePolicy = PrimeSizePolicy,
         typename Lock = NoResizeLock
     >
     class WeakReferenceRegionKeyDictionary : public SplitWeakDictionary<TValue, TKey, true, SizePolicy, Comparer, Lock, Recycler>
     {
         typedef SplitWeakDictionary<TValue, TKey, true, SizePolicy, Comparer, Lock, Recycler> Base;

         typedef typename Base::EntryType EntryType;
         typedef typename Base::WeakType KeyType;

     public:
         // Allow WeakReferenceRegionKeyDictionary field to be inlined in classes with DEFINE_VTABLE_CTOR_MEMBER_INIT
         WeakReferenceRegionKeyDictionary(VirtualTableInfoCtorEnum v): Base(v) { }

         WeakReferenceRegionKeyDictionary(Recycler* allocator, int capacity = 0)
             : Base(allocator, capacity)
         {
         }

         template <class Fn>
         void Map(Fn fn)
         {
             this->MapAndRemoveIf([=](EntryType& entry, KeyType& weakRef)
             {
                 if (weakRef == nullptr)
                 {
                     return true;
                 }
                 fn(weakRef, entry.Value(), weakRef);
                 return false;
             });
         }

         bool Clean()
         {
             this->Cleanup();
             return this->freeCount > 0;
         }
     };
 #endif // ENABLE_WEAK_REFERENCE_REGIONS
 };
	//-------------------------------------------------------------------------------------------------------
	// 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

	namespace JsUtil
	{
	interface IWeakReferenceDictionary
	{
	virtual void Cleanup() = 0;
	};

	template <
	class TKey,
	class TValue,
	class SizePolicy = PowerOf2SizePolicy,
	template <typename ValueOrKey> class Comparer = DefaultComparer
	>
	class WeakReferenceDictionary: public BaseDictionary<TKey, RecyclerWeakReference<TValue>*, RecyclerNonLeafAllocator, SizePolicy, Comparer, WeakRefValueDictionaryEntry>,
	public IWeakReferenceDictionary
	{
	typedef BaseDictionary<TKey, RecyclerWeakReference<TValue>*, RecyclerNonLeafAllocator, SizePolicy, Comparer, WeakRefValueDictionaryEntry> Base;
	typedef typename Base::EntryType EntryType;

	public:
	WeakReferenceDictionary(Recycler* recycler, int capacity = 0):
	Base(recycler, capacity)
	{
	Assert(reinterpret_cast<void>(this) == reinterpret_cast<void>((IWeakReferenceDictionary*) this));
	}

	virtual void Cleanup() override
	{
	this->MapAndRemoveIf([](typename Base::EntryType &entry)
	{
	return (Base::EntryType::NeedsCleanup(entry));
	});
	}

	private:
	using Base::Clone;
	using Base::Copy;

	PREVENT_COPY(WeakReferenceDictionary);
	};

	#if ENABLE_WEAK_REFERENCE_REGIONS

	template<bool, typename T = void>
	struct enable_if {};

	template<typename T>
	struct enable_if<true, T>
	{
	typedef T type;
	};

	template <
	class TEntry,
	class TWeak,
	bool keyIsWeak,
	class SizePolicy = PowerOf2SizePolicy,
	template <typename ValueOrKey> class Comparer = DefaultComparer,
	typename Lock = NoResizeLock,
	class AllocType = Recycler // Should always be recycler; this is to sufficiently confuse the RecyclerChecker
	>
	class SplitWeakDictionary : protected Lock, public IWeakReferenceDictionary
	{
	private:
	template <typename T1, typename T2, bool second>
	struct Select;

	template <typename T1, typename T2>
	struct Select<T1, T2, false>
	{
	typedef T1 type;
	};

	template <typename T1, typename T2>
	struct Select<T1, T2, true>
	{
	typedef T2 type;
	};

	typedef typename Select<TEntry, TWeak, keyIsWeak>::type TBKey;
	typedef typename Select<TEntry, TWeak, !keyIsWeak>::type TBValue;

	typedef typename AllocatorInfo<Recycler, TEntry>::AllocatorFunc EntryAllocatorFuncType;

	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
	};

	protected:

	typedef ValueEntry<TEntry> EntryType;
	typedef RecyclerWeakReferenceRegionItem<TWeak> WeakType;

	Field(int*) buckets;
	Field(EntryType*) entries;
	Field(WeakType*) weakRefs;
	FieldNoBarrier(Recycler*) alloc;
	Field(int) size;
	Field(uint) bucketCount;
	Field(int) count;
	Field(int) freeList;
	Field(int) freeCount;
	Field(int) modFunctionIndex;

	private:
	static const int FreeListSentinel = -2;

	PREVENT_COPY(SplitWeakDictionary);


	class AutoDoResize
	{
	public:
	AutoDoResize(Lock& lock) : lock(lock) { lock.BeginResize(); };
	~AutoDoResize() { lock.EndResize(); };
	private:
	Lock & lock;
	};

	public:
	// Allow SplitWeakDictionary field to be inlined in classes with DEFINE_VTABLE_CTOR_MEMBER_INIT
	SplitWeakDictionary(VirtualTableInfoCtorEnum) { }

	SplitWeakDictionary(Recycler* allocator, int capacity = 0)
	: buckets(nullptr),
	entries(nullptr),
	weakRefs(nullptr),
	alloc(allocator),
	size(0),
	bucketCount(0),
	count(0),
	freeList(0),
	freeCount(0),
	modFunctionIndex(UNKNOWN_MOD_INDEX)
	{
	Assert(allocator);
	Assert(reinterpret_cast<void>(this) == reinterpret_cast<void>((IWeakReferenceDictionary*)this));

	// If initial capacity is negative or 0, lazy initialization on
	// the first insert operation is performed.
	if (capacity > 0)
	{
	Initialize(capacity);
	}
	}

	virtual void Cleanup() override
	{
	this->MapAndRemoveIf([](EntryType& entry, WeakType& weakRef)
	{
	return weakRef == nullptr;
	});
	}

	inline int Capacity() const
	{
	return size;
	}

	inline int Count() const
	{
	return count - freeCount;
	}

	void Clear()
	{
	if (count > 0)
	{
	memset(buckets, -1, bucketCount * sizeof(buckets[0]));
	memset(entries, 0, sizeof(EntryType) * size);
	memset(weakRefs, 0, sizeof(WeakType) * size); // TODO: issues with background threads?
	count = 0;
	freeCount = 0;
	}
	}

	void ResetNoDelete()
	{
	this->size = 0;
	this->bucketCount = 0;
	this->buckets = nullptr;
	this->entries = nullptr;
	this->weakRefs = nullptr;
	this->count = 0;
	this->freeCount = 0;
	this->modFunctionIndex = UNKNOWN_MOD_INDEX;
	}

	void Reset()
	{
	ResetNoDelete();
	}

	// 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;
	}

	TBValue Item(const TBKey& key)
	{
	int i = FindEntry(key);
	Assert(i >= 0);
	return values[i];
	}

	TBValue Item(const TBKey& key) const
	{
	int i = FindEntry(key);
	Assert(i >= 0);
	return values[i];
	}

	int Add(const TBKey& key, const TBValue& value)
	{
	return Insert<Insert_Add>(key, value);
	}

	int AddNew(const TBKey& key, const TBValue& value)
	{
	return Insert<Insert_AddNew>(key, value);
	}

	int Item(const TBKey& key, const TBValue& value)
	{
	return Insert<Insert_Item>(key, value);
	}

	bool Contains(KeyValuePair<TBKey, TBValue> keyValuePair)
	{
	int i = FindEntry(keyValuePair.Key());
	TBValue val = this->GetValue(i);
	if (i >= 0 && Comparer<TBValue>::Equals(val, keyValuePair.Value()))
	{
	return true;
	}
	return false;
	}

	bool ContainsKey(const TBKey& key) const
	{
	return FindEntry(key) >= 0;
	}

	template <typename TLookup>
	inline const TBValue& LookupWithKey(const TLookup& key, const TBValue& defaultValue)
	{
	int i = FindEntryWithKey(key);
	if (i >= 0)
	{
	return this->GetValue(i);
	}
	return defaultValue;
	}

	inline const TBValue& Lookup(const TBKey& key, const TBValue& defaultValue)
	{
	return LookupWithKey<TBKey>(key, defaultValue);
	}

	template <typename TLookup>
	bool TryGetValue(const TLookup& key, TBValue* value)
	{
	int i = FindEntryWithKey(key);
	if (i >= 0)
	{
	*value = this->GetValue(i);
	return true;
	}
	return false;
	}


	bool TryGetValueAndRemove(const TBKey& key, TBValue* value)
	{
	int i, last;
	uint targetBucket;
	if (FindEntryWithKey(key, &i, &last, &targetBucket))
	{
	*value = this->GetValue(i);
	RemoveAt(i, last, targetBucket);
	return true;
	}
	return false;
	}

	bool Remove(const TBKey& key)
	{
	int i, last;
	uint targetBucket;
	if (FindEntryWithKey(key, &i, &last, &targetBucket))
	{
	RemoveAt(i, last, targetBucket);
	return true;
	}
	return false;
	}

	bool Remove(KeyValuePair<TBKey, TBValue> keyValuePair)
	{
	int i, last;
	uint targetBucket;
	if (FindEntryWithKey(keyValuePair.Key(), &i, &last, &targetBucket))
	{
	const TBValue& value = this->GetValue(i);
	if (Comparer<TBValue>::Equals(value, keyValuePair.Value()))
	{
	RemoveAt(i, last, targetBucket);
	return true;
	}
	}
	return false;
	}

	int GetLastIndex()
	{
	return count - 1;
	}

	void LockResize()
	{
	__super::LockResize();
	}

	void UnlockResize()
	{
	__super::UnlockResize();
	}

	protected:

	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], weakRefs[currentIndex]) == true)
	{
	const int nextIndex = entries[currentIndex].next;
	RemoveAt(currentIndex, lastIndex, i);
	currentIndex = nextIndex;
	}
	else
	{
	lastIndex = currentIndex;
	currentIndex = entries[currentIndex].next;
	}
	}
	}
	}
	}

	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 uint GetBucket(hash_t hashCode, int bucketCount, int modFunctionIndex)
	{
	return SizePolicy::GetBucket(UNTAGHASH(hashCode), bucketCount, modFunctionIndex);
	}

	uint GetBucket(hash_t hashCode) const
	{
	return GetBucket(hashCode, this->bucketCount, modFunctionIndex);
	}

	static bool IsFreeEntry(const EntryType &entry)
	{
	// A free entry's next index will be (FreeListSentinel - nextIndex), such that it is always <= FreeListSentinel, 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 <= FreeListSentinel;
	}


	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 FreeListSentinel to indicate that it is a free entry. The end of the
	// free list chain is identified using freeCount.
	freeEntry.next = nextFreeEntryIndex >= 0 ? FreeListSentinel - nextFreeEntryIndex : FreeListSentinel;
	}

	static int GetNextFreeEntryIndex(const EntryType &freeEntry)
	{
	Assert(IsFreeEntry(freeEntry));
	return FreeListSentinel - freeEntry.next;
	}

	void Initialize(int capacity)
	{
	// minimum capacity is 4
	int initSize = max(capacity, 4);
	int modIndex = UNKNOWN_MOD_INDEX;
	uint initBucketCount = SizePolicy::GetBucketSize(initSize, &modIndex);
	AssertMsg(initBucketCount > 0, "Size returned by policy should be greater than 0");

	int* newBuckets = nullptr;
	EntryType* newEntries = nullptr;
	WeakType* newWeakRefs = nullptr;
	Allocate(&newBuckets, &newEntries, &newWeakRefs, initBucketCount, initSize);

	// Allocation can throw - assign only after allocation has succeeded.
	this->buckets = newBuckets;
	this->entries = newEntries;
	this->weakRefs = newWeakRefs;
	this->bucketCount = initBucketCount;
	this->size = initSize;
	this->modFunctionIndex = modIndex;
	Assert(this->freeCount == 0);
	}

	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();
	weakRefs[i].Clear();
	SetNextFreeEntryIndex(entries[i], freeCount == 0 ? -1 : freeList);
	freeList = i;
	freeCount++;
	}

	inline int FindEntry(const TBKey& key)
	{
	return FindEntryWithKey<TBKey>(key);
	}

	template <typename LookupType>
	inline int FindEntryWithKey(const LookupType& key)
	{
	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], last = -1; i >= 0;)
	{
	TBKey k = this->GetKey(i);
	if (this->RemoveIfCollected(k, &i, last, targetBucket))
	{
	continue;
	}
	if (Comparer<TBKey>::Equals(k, key))
	{
	return i;
	}

	last = i;
	i = localEntries[i].next;
	}
	}
	return -1;
	}

	template <typename LookupType>
	inline bool FindEntryWithKey(const LookupType& key, int const i, int const last, uint *const targetBucket)
	{
	int * localBuckets = buckets;
	if (localBuckets != nullptr)
	{
	hash_t hashCode = GetHashCodeWithKey<LookupType>(key);
	*targetBucket = this->GetBucket(hashCode);
	*last = -1;
	EntryType * localEntries = entries;
	for (i = localBuckets[targetBucket]; *i >= 0;)
	{
	TBKey k = this->GetKey(*i);
	if (this->RemoveIfCollected(k, i, last, targetBucket))
	{
	continue;
	}
	if (Comparer<TBKey>::Equals(k, key))
	{
	return true;
	}

	last = i;
	i = localEntries[i].next;
	}
	}
	return false;
	}

	private:

	void Resize()
	{
	AutoDoResize autoDoResize(*this);
	__analysis_assert(count > 1);

	int newSize = SizePolicy::GetNextSize(count);
	int modIndex = UNKNOWN_MOD_INDEX;
	uint newBucketCount = SizePolicy::GetBucketSize(newSize, &modIndex);

	__analysis_assume(newSize > count);
	int* newBuckets = nullptr;
	EntryType* newEntries = nullptr;
	WeakType* newWeakRefs = nullptr;
	if (newBucketCount == bucketCount)
	{
	// no need to rehash
	newEntries = AllocateEntries(newSize);
	newWeakRefs = AllocateWeakRefs(newSize);
	CopyArray<EntryType>(newEntries, newSize, entries, count);
	CopyArray<WeakType>(newWeakRefs, newSize, weakRefs, count); // TODO: concurrency issues?

	this->entries = newEntries;
	this->weakRefs = newWeakRefs;
	this->size = newSize;
	this->modFunctionIndex = modIndex;
	return;
	}

	Allocate(&newBuckets, &newEntries, &newWeakRefs, newBucketCount, newSize);

	this->modFunctionIndex = modIndex;

	// Need to re-bucket the entries
	// Also need to account for whether the weak refs have been collected
	// Have to go in order so we can remove entries as appropriate
	this->count = 0;
	for (uint i = 0; i < this->bucketCount; ++i)
	{
	if (this->buckets[i] < 0)
	{
	continue;
	}

	for (int currentEntry = this->buckets[i]; currentEntry != -1; )
	{
	if (IsFreeEntry(entries[currentEntry]))
	{
	// Entry is free; this shouldn't happen, but stop following the chain
	AssertMsg(false, "Following bucket chains should not result in free entries");
	break;
	}
	if (this->weakRefs[currentEntry] == nullptr)
	{
	// The weak ref has been collected; don't bother bringing it to the new collection
	currentEntry = this->entries[currentEntry].next;
	continue;
	}

	hash_t hashCode = GetHashCodeWithKey<TBKey>(this->GetKey(currentEntry));
	int bucket = GetBucket(hashCode, newBucketCount, modFunctionIndex);
	newEntries[count].next = newBuckets[bucket];
	newEntries[count].SetValue(this->entries[currentEntry].Value());
	newWeakRefs[count] = this->weakRefs[currentEntry];
	newBuckets[bucket] = count;
	++count;

	currentEntry = this->entries[currentEntry].next;
	}
	}
	this->freeCount = 0;
	this->freeList = 0;
	this->buckets = newBuckets;
	this->entries = newEntries;
	this->weakRefs = newWeakRefs;
	this->bucketCount = newBucketCount;
	this->size = newSize;

	}

	template <InsertOperations op>
	int Insert(const TBKey& key, const TBValue& value)
	{
	int * localBuckets = buckets;
	if (localBuckets == nullptr)
	{
	Initialize(0);
	localBuckets = buckets;
	}

	#if DBG
	// Always search and verify
	const bool needSearch = true;
	#else
	const bool needSearch = (op != Insert_Add);
	#endif
	hash_t hashCode = GetHashCodeWithKey<TBKey>(key);
	uint targetBucket = this->GetBucket(hashCode);
	if (needSearch)
	{
	EntryType * localEntries = entries;
	for (int i = localBuckets[targetBucket], last = -1; i >= 0;)
	{
	TBKey k = this->GetKey(i);
	if (this->RemoveIfCollected(k, &i, last, targetBucket))
	{
	continue;
	}

	if (Comparer<TBKey>::Equals(k, key))
	{
	Assert(op != Insert_Add);
	if (op == Insert_Item)
	{
	SetValue(value, i);
	return i;
	}
	return -1;
	}

	last = i;
	i = localEntries[i].next;
	}
	}

	// 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 (freeCount == 0 && count == size)
	{
	this->Cleanup();
	}

	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);
	}

	SetKeyValue(key, value, index);
	entries[index].next = buckets[targetBucket];
	buckets[targetBucket] = index;

	return index;
	}

	__ecount(bucketCount) int *AllocateBuckets(DECLSPEC_GUARD_OVERFLOW const uint bucketCount)
	{
	return
	AllocateArray<AllocType, int, false>(
	TRACK_ALLOC_INFO(alloc, int, AllocType, 0, bucketCount),
	TypeAllocatorFunc<AllocType, int>::GetAllocFunc(),
	bucketCount);
	}

	__ecount(size) EntryType * AllocateEntries(DECLSPEC_GUARD_OVERFLOW 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<Recycler, EntryType, false>(
	TRACK_ALLOC_INFO(alloc, EntryType, Recycler, 0, size),
	zeroAllocate ? EntryAllocatorFuncType::GetAllocZeroFunc() : EntryAllocatorFuncType::GetAllocFunc(),
	size);
	}

	__ecount(size) WeakType * AllocateWeakRefs(DECLSPEC_GUARD_OVERFLOW int size)
	{
	return alloc->CreateWeakReferenceRegion<TWeak>(size);
	}


	void Allocate(__deref_out_ecount(bucketCount) int ppBuckets, __deref_out_ecount(size) EntryType ppEntries, __deref_out_ecount(size) WeakType** ppWeakRefs, DECLSPEC_GUARD_OVERFLOW uint bucketCount, DECLSPEC_GUARD_OVERFLOW int size)
	{
	int *const newBuckets = AllocateBuckets(bucketCount);
	Assert(newBuckets); // no-throw allocators are currently not supported

	EntryType *newEntries = AllocateEntries(size);
	Assert(newEntries); // no-throw allocators are currently not supported

	WeakType * newWeakRefs = AllocateWeakRefs(size);

	memset(newBuckets, -1, bucketCount * sizeof(newBuckets[0]));

	*ppBuckets = newBuckets;
	*ppEntries = newEntries;
	*ppWeakRefs = newWeakRefs;
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<weakKey, TBKey>::type GetKey(int index) const
	{
	return this->weakRefs[index];
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<!weakKey, TBKey>::type GetKey(int index) const
	{
	return this->entries[index].Value();
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<weakKey, TBValue>::type GetValue(int index) const
	{
	return this->entries[index].Value();
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<!weakKey, TBValue>::type GetValue(int index) const
	{
	return this->weakRefs[index];
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<weakKey, bool>::type RemoveIfCollected(TBKey const key, int* i, int last, int targetBucket)
	{
	if (key == nullptr)
	{
	// Key has been collected
	int next = entries[*i].next;
	RemoveAt(*i, last, targetBucket);
	*i = next;
	return true;
	}
	return false;
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<!weakKey, bool>::type RemoveIfCollected(TBKey const key, int* i, int last, int targetBucket)
	{
	return false;
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<weakKey, void>::type SetKeyValue(const TBKey& key, const TBValue& value, int index)
	{
	weakRefs[index] = key;
	entries[index].SetValue(value);
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<!weakKey, void>::type SetKeyValue(const TBKey& key, const TBValue& value, int index)
	{
	entries[index].SetValue(key);
	weakRefs[index] = value;
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<weakKey, void>::type SetValue(const TBValue& value, int index)
	{
	this->entries[index].SetValue(value);
	}

	template <bool weakKey = keyIsWeak>
	inline typename enable_if<!weakKey, void>::type SetValue(const TBValue& value, int index)
	{
	this->weakRefs[index] = value;
	}
	};

	template <
	class TKey,
	class TValue,
	class SizePolicy = PowerOf2SizePolicy,
	template <typename ValueOrKey> class Comparer = DefaultComparer,
	typename Lock = NoResizeLock
	>
	class WeakReferenceRegionDictionary : public SplitWeakDictionary<TKey, TValue, false, SizePolicy, Comparer, Lock, Recycler>
	{
	typedef SplitWeakDictionary<TKey, TValue, false, SizePolicy, Comparer, Lock, Recycler> Base;
	typedef typename Base::EntryType EntryType;
	typedef typename Base::WeakType ValueType;

	public:

	WeakReferenceRegionDictionary(Recycler* allocator, int capacity = 0)
	: Base(allocator, capacity)
	{
	}
	};

	template <
	class TKey,
	class TValue,
	template <typename ValueOrKey> class Comparer = DefaultComparer,
	class SizePolicy = PrimeSizePolicy,
	typename Lock = NoResizeLock
	>
	class WeakReferenceRegionKeyDictionary : public SplitWeakDictionary<TValue, TKey, true, SizePolicy, Comparer, Lock, Recycler>
	{
	typedef SplitWeakDictionary<TValue, TKey, true, SizePolicy, Comparer, Lock, Recycler> Base;

	typedef typename Base::EntryType EntryType;
	typedef typename Base::WeakType KeyType;

	public:
	// Allow WeakReferenceRegionKeyDictionary field to be inlined in classes with DEFINE_VTABLE_CTOR_MEMBER_INIT
	WeakReferenceRegionKeyDictionary(VirtualTableInfoCtorEnum v): Base(v) { }

	WeakReferenceRegionKeyDictionary(Recycler* allocator, int capacity = 0)
	: Base(allocator, capacity)
	{
	}

	template <class Fn>
	void Map(Fn fn)
	{
	this->MapAndRemoveIf([=](EntryType& entry, KeyType& weakRef)
	{
	if (weakRef == nullptr)
	{
	return true;
	}
	fn(weakRef, entry.Value(), weakRef);
	return false;
	});
	}

	bool Clean()
	{
	this->Cleanup();
	return this->freeCount > 0;
	}
	};
	#endif // ENABLE_WEAK_REFERENCE_REGIONS
	};