src/libANGLE/ResourceMap_unittest.cpp - third_party/angle - Git at Google

 //
 // Copyright 2018 The ANGLE Project Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 //
 // ResourceMap_unittest:
 //   Unit tests for the ResourceMap template class.
 //

 #include <gtest/gtest.h>
 #include <map>

 #include "libANGLE/ResourceMap.h"

 using namespace gl;

 namespace gl
 {
 template <>
 inline GLuint GetIDValue(int id)
 {
     return id;
 }
 template <>
 inline GLuint GetIDValue(unsigned int id)
 {
     return id;
 }
 template <>
 inline GLuint GetIDValue(uint16_t id)
 {
     return id;
 }
 // For the purpose of unit testing, |int| is considered private (not needing lock), |unsigned int|
 // is considered shared (needing lock), and |uint16_t| additionally has a small flat array to
 // exercise all three storage levels.
 template <>
 struct ResourceMapParams<unsigned int>
 {
     static constexpr size_t kInitialFlatResourcesSize    = 0xC0;
     static constexpr size_t kAdditionalFlatResourcesSize = 0;
     static constexpr bool kNeedsLock                     = true;
 };
 template <>
 struct ResourceMapParams<uint16_t>
 {
     static constexpr size_t kInitialFlatResourcesSize    = 3;
     static constexpr size_t kAdditionalFlatResourcesSize = 7;
     static constexpr bool kNeedsLock                     = true;
 };
 }  // namespace gl

 namespace
 {
 // The resourceMap class uses a lock for "unsigned int" types to support this unit test.
 using LocklessType = int;
 using LockedType   = unsigned int;
 using AdditionalFlatType = uint16_t;

 template <typename T>
 void AssignAndErase()
 {
     constexpr size_t kSize = 300;
     ResourceMap<size_t, T> resourceMap;
     std::vector<size_t> objects(kSize, 1);
     for (size_t index = 0; index < kSize; ++index)
     {
         resourceMap.assign(index + 1, &objects[index]);
     }

     for (size_t index = 0; index < kSize; ++index)
     {
         size_t *found = nullptr;
         ASSERT_TRUE(resourceMap.erase(index + 1, &found));
         ASSERT_EQ(&objects[index], found);
     }

     ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
 }

 // Tests assigning slots in the map and then deleting elements.
 TEST(ResourceMapTest, AssignAndEraseLockless)
 {
     AssignAndErase<LocklessType>();
 }
 // Tests assigning slots in the map and then deleting elements.
 TEST(ResourceMapTest, AssignAndEraseLocked)
 {
     AssignAndErase<LockedType>();
 }

 template <typename T>
 void AssignAndClear()
 {
     constexpr size_t kSize = 280;
     ResourceMap<size_t, T> resourceMap;
     std::vector<size_t> objects(kSize, 1);
     for (size_t index = 0; index < kSize; ++index)
     {
         resourceMap.assign(index + 1, &objects[index]);
     }

     resourceMap.clear();
     ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
 }

 // Tests assigning slots in the map and then using clear() to free it.
 TEST(ResourceMapTest, AssignAndClearLockless)
 {
     AssignAndClear<LocklessType>();
 }
 // Tests assigning slots in the map and then using clear() to free it.
 TEST(ResourceMapTest, AssignAndClearLocked)
 {
     AssignAndClear<LockedType>();
 }

 template <typename T>
 void BigGrowth()
 {
     constexpr size_t kSize = 8;

     ResourceMap<size_t, T> resourceMap;
     std::vector<size_t> objects;

     for (size_t index = 0; index < kSize; ++index)
     {
         objects.push_back(index);
     }

     // Assign a large value.
     constexpr size_t kLargeIndex = 128;
     objects.push_back(kLargeIndex);

     for (size_t &object : objects)
     {
         resourceMap.assign(object, &object);
     }

     for (size_t object : objects)
     {
         size_t *found = nullptr;
         ASSERT_TRUE(resourceMap.erase(object, &found));
         ASSERT_EQ(object, *found);
     }

     ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
 }

 // Tests growing a map more than double the size.
 TEST(ResourceMapTest, BigGrowthLockless)
 {
     BigGrowth<LocklessType>();
 }
 // Tests growing a map more than double the size.
 TEST(ResourceMapTest, BigGrowthLocked)
 {
     BigGrowth<LockedType>();
 }

 template <typename T>
 void QueryUnassigned()
 {
     constexpr size_t kSize        = 8;
     constexpr T kZero             = 0;
     constexpr T kIdInFlatRange    = 10;
     constexpr T kIdOutOfFlatRange = 500;

     ResourceMap<size_t, T> resourceMap;
     std::vector<size_t> objects;

     for (size_t index = 0; index < kSize; ++index)
     {
         objects.push_back(index);
     }

     ASSERT_FALSE(resourceMap.contains(kZero));
     ASSERT_EQ(nullptr, resourceMap.query(kZero));
     ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
     ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));

     for (size_t &object : objects)
     {
         resourceMap.assign(object, &object);
     }

     ASSERT_FALSE(UnsafeResourceMapIter(resourceMap).empty());

     for (size_t &object : objects)
     {
         ASSERT_TRUE(resourceMap.contains(object));
         ASSERT_EQ(&object, resourceMap.query(object));
     }

     ASSERT_FALSE(resourceMap.contains(kIdInFlatRange));
     ASSERT_EQ(nullptr, resourceMap.query(kIdInFlatRange));
     ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
     ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));

     for (size_t object : objects)
     {
         size_t *found = nullptr;
         ASSERT_TRUE(resourceMap.erase(object, &found));
         ASSERT_EQ(object, *found);
     }

     ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());

     ASSERT_FALSE(resourceMap.contains(kZero));
     ASSERT_EQ(nullptr, resourceMap.query(kZero));
     ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
     ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));
 }

 // Tests querying unassigned or erased values.
 TEST(ResourceMapTest, QueryUnassignedLockless)
 {
     QueryUnassigned<LocklessType>();
 }
 // Tests querying unassigned or erased values.
 TEST(ResourceMapTest, QueryUnassignedLocked)
 {
     QueryUnassigned<LockedType>();
 }

 template <typename IDType>
 void ConcurrentAccess(size_t iterations, size_t idCycleSize)
 {
     if (std::is_same_v<ResourceMapMutex, angle::NoOpMutex>)
     {
         GTEST_SKIP() << "Test skipped: Locking is disabled in build.";
     }

     constexpr size_t kThreadCount = 13;

     ResourceMap<size_t, IDType> resourceMap;

     std::array<std::thread, kThreadCount> threads;
     std::array<std::map<IDType, size_t>, kThreadCount> insertedIds;

     for (size_t i = 0; i < kThreadCount; ++i)
     {
         threads[i] = std::thread([&, i]() {
             // Each thread manipulates a different set of ids.  The resource map guarantees that the
             // data structure itself is thread-safe, not accesses to the same id.
             for (size_t j = 0; j < iterations; ++j)
             {
                 const IDType id =
                     static_cast<IDType>((j % (idCycleSize / kThreadCount)) * kThreadCount + i);

                 ASSERT_LE(id, 0xFFFFu);
                 ASSERT_LE(j, 0xFFFFu);
                 const size_t value = id | j << 16;

                 size_t *valuePtr = reinterpret_cast<size_t *>(value);

                 const size_t *queryResult = resourceMap.query(id);
                 const bool containsResult = resourceMap.contains(id);

                 const bool expectContains = insertedIds[i].count(id) > 0;
                 if (expectContains)
                 {
                     EXPECT_TRUE(containsResult);
                     const IDType queryResultInt =
                         static_cast<IDType>(reinterpret_cast<size_t>(queryResult) & 0xFFFF);
                     const size_t queryResultIteration = reinterpret_cast<size_t>(queryResult) >> 16;
                     EXPECT_EQ(queryResultInt, id);
                     EXPECT_LT(queryResultIteration, j);

                     size_t *erasedValue = nullptr;
                     const bool erased   = resourceMap.erase(id, &erasedValue);

                     EXPECT_TRUE(erased);
                     EXPECT_EQ(erasedValue, queryResult);

                     insertedIds[i].erase(id);
                 }
                 else
                 {
                     EXPECT_FALSE(containsResult);
                     EXPECT_EQ(queryResult, nullptr);

                     resourceMap.assign(id, valuePtr);
                     EXPECT_TRUE(resourceMap.contains(id));

                     ASSERT_TRUE(insertedIds[i].count(id) == 0);
                     insertedIds[i][id] = value;
                 }
             }
         });
     }

     for (size_t i = 0; i < kThreadCount; ++i)
     {
         threads[i].join();
     }

     // Verify that every value that is expected to be there is actually there
     std::map<size_t, size_t> allIds;
     size_t allIdsPrevSize = 0;

     for (size_t i = 0; i < kThreadCount; ++i)
     {
         // Merge all the sets together.  The sets are disjoint, which is verified by the ASSERT_EQ.
         allIds.insert(insertedIds[i].begin(), insertedIds[i].end());
         ASSERT_EQ(allIds.size(), allIdsPrevSize + insertedIds[i].size());
         allIdsPrevSize = allIds.size();

         // Make sure every id that is expected to be there is actually there.
         for (auto &idValue : insertedIds[i])
         {
             EXPECT_TRUE(resourceMap.contains(idValue.first));
             EXPECT_EQ(resourceMap.query(idValue.first), reinterpret_cast<size_t *>(idValue.second));
         }
     }

     // Verify that every value that is NOT expected to be there isn't actually there
     for (auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         EXPECT_TRUE(allIds.count(idValue.first) == 1);
         EXPECT_EQ(idValue.second, reinterpret_cast<size_t *>(allIds[idValue.first]));
     }

     resourceMap.clear();
 }

 // Tests that concurrent access to thread-safe resource maps works for small ids that are mostly in
 // the flat map range.
 TEST(ResourceMapTest, ConcurrentAccessSmallIds)
 {
     ConcurrentAccess<LockedType>(50'000, 128);
 }
 // Tests that concurrent access to thread-safe resource maps works for a wider range of ids.
 TEST(ResourceMapTest, ConcurrentAccessLargeIds)
 {
     ConcurrentAccess<LockedType>(10'000, 20'000);
 }
 // Tests that concurrent access to thread-safe resource maps works for the initial flat array, the
 // secondary flat array and the hashmap.
 TEST(ResourceMapTest, ConcurrentAccessFlatArraysAndHashMap)
 {
     // Set idCycleSize to 26 (2 * kThreadCount) so that each thread gets 2 IDs and covers the flat
     // arrays and the hashmap.
     ConcurrentAccess<AdditionalFlatType>(20'000, 26);
 }

 // Tests growth across the initial flat array, the secondary flat array, and the hashmap.
 TEST(ResourceMapTest, GrowthAcrossFlatArraysAndHashMap)
 {
     // Handle Layout
     // - initial flat array     : 1, 2
     // - additional flat array  : 3, 4, 5, 6, 7, 8, 9
     // - hashmap                : 10, 11, 12
     constexpr size_t kTotalHandle = 12;
     std::vector<size_t> objects(kTotalHandle);
     for (size_t index = 0; index < kTotalHandle; ++index)
     {
         objects[index] = index + 1;
     }

     ResourceMap<size_t, AdditionalFlatType> resourceMap;

     for (size_t index = 0; index < kTotalHandle; ++index)
     {
         resourceMap.assign(static_cast<AdditionalFlatType>(index + 1), &objects[index]);
     }

     for (size_t index = 0; index < kTotalHandle; ++index)
     {
         const AdditionalFlatType handle = static_cast<AdditionalFlatType>(index + 1);
         EXPECT_TRUE(resourceMap.contains(handle)) << "handle=" << handle;
         EXPECT_EQ(resourceMap.query(handle), &objects[index]) << "handle=" << handle;
     }

     // Handles that have never been assigned must not be found.
     EXPECT_FALSE(resourceMap.contains(static_cast<AdditionalFlatType>(0)));
     EXPECT_EQ(resourceMap.query(static_cast<AdditionalFlatType>(0)), nullptr);
     EXPECT_FALSE(resourceMap.contains(static_cast<AdditionalFlatType>(kTotalHandle + 1)));
     EXPECT_EQ(resourceMap.query(static_cast<AdditionalFlatType>(kTotalHandle + 1)), nullptr);

     // The iterator must visit each assigned handle exactly once across all flat arrays and the
     // hashmap.
     std::map<GLuint, size_t *> visitedHandleMap;
     for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         EXPECT_EQ(visitedHandleMap.count(idValue.first), 0u) << "duplicate id=" << idValue.first;
         visitedHandleMap[idValue.first] = idValue.second;
     }
     EXPECT_EQ(visitedHandleMap.size(), kTotalHandle);

     for (size_t index = 0; index < kTotalHandle; ++index)
     {
         const GLuint handle = static_cast<GLuint>(index + 1);
         ASSERT_EQ(visitedHandleMap.count(handle), 1u) << "missing handle=" << handle;
         EXPECT_EQ(visitedHandleMap[handle], &objects[index]);
     }

     for (size_t index = 0; index < kTotalHandle; ++index)
     {
         const AdditionalFlatType handle = static_cast<AdditionalFlatType>(index + 1);
         size_t *erased                  = nullptr;
         EXPECT_TRUE(resourceMap.erase(handle, &erased)) << "handle=" << handle;
         EXPECT_EQ(erased, &objects[index]) << "handle=" << handle;
         EXPECT_FALSE(resourceMap.contains(handle)) << "handle is still present after erase";
     }

     EXPECT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
 }

 // Tests that the iterator visits all valid handles when resources exist only in the hash map, and
 // no ID in the additional flat array has ever been assigned.
 TEST(ResourceMapTest, IteratorVisitsHashMapWithoutAdditionalFlatArray)
 {
     // Assign handles in the hashmap range to keep mAdditionalFlatResources nullptr.
     // kHashmapIdx0, kHashmapIdx1 >= kInitialFlatResourcesSize + kAdditionalFlatResourcesSize
     //                            >= kLocklessFlatResourcesLimit = 3 + 7 = 10
     constexpr AdditionalFlatType kHashmapIdx0 = 10;
     constexpr AdditionalFlatType kHashmapIdx1 = 11;
     size_t hashmapValue0                      = 100;
     size_t hashmapValue1                      = 200;

     ResourceMap<size_t, AdditionalFlatType> resourceMap;
     resourceMap.assign(kHashmapIdx0, &hashmapValue0);
     resourceMap.assign(kHashmapIdx1, &hashmapValue1);

     EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
     EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
     EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
     EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

     constexpr AdditionalFlatType kInitialArrayIdx    = 1;
     constexpr AdditionalFlatType kAdditionalArrayIdx = 5;

     // Since IDs in the initial and additional flat arrays are never allocated, they should always
     // return false or nullptr.
     EXPECT_FALSE(resourceMap.contains(kInitialArrayIdx));
     EXPECT_EQ(resourceMap.query(kInitialArrayIdx), nullptr);
     EXPECT_FALSE(resourceMap.contains(kAdditionalArrayIdx));
     EXPECT_EQ(resourceMap.query(kAdditionalArrayIdx), nullptr);

     // The iterator must visit both hashmap entries.
     std::map<GLuint, size_t *> visitedHandleMap;
     for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         visitedHandleMap[idValue.first] = idValue.second;
     }
     EXPECT_EQ(visitedHandleMap.size(), 2u);
     EXPECT_EQ(visitedHandleMap.count(kHashmapIdx0), 1u);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
     EXPECT_EQ(visitedHandleMap.count(kHashmapIdx1), 1u);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

     resourceMap.clear();
 }

 // Tests that the iterator correctly visits all valid handles stored in the upper portion of the
 // additional flat array.
 TEST(ResourceMapTest, IteratorVisitsUpperAdditionalFlatArray)
 {
     // Additional flat range = [kInitialFlatResourcesSize, kLocklessFlatResourcesLimit) = [3, 10)
     // Assign handles in the upper portion of the additional flat array.
     constexpr AdditionalFlatType kFirstIdx = 7;
     constexpr AdditionalFlatType kLastIdx  = 9;
     size_t value7                          = 7;
     size_t value8                          = 8;
     size_t value9                          = 9;

     ResourceMap<size_t, AdditionalFlatType> resourceMap;
     resourceMap.assign(kFirstIdx, &value7);
     resourceMap.assign(kFirstIdx + 1, &value8);
     resourceMap.assign(kLastIdx, &value9);

     EXPECT_TRUE(resourceMap.contains(kFirstIdx));
     EXPECT_EQ(resourceMap.query(kFirstIdx), &value7);
     EXPECT_TRUE(resourceMap.contains(kFirstIdx + 1));
     EXPECT_EQ(resourceMap.query(kFirstIdx + 1), &value8);
     EXPECT_TRUE(resourceMap.contains(kLastIdx));
     EXPECT_EQ(resourceMap.query(kLastIdx), &value9);

     // Iterator must visit all three handles.
     std::map<GLuint, size_t *> visitedHandleMap;
     for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         visitedHandleMap[idValue.first] = idValue.second;
     }
     EXPECT_EQ(visitedHandleMap.size(), 3u);
     EXPECT_EQ(visitedHandleMap[kFirstIdx], &value7);
     EXPECT_EQ(visitedHandleMap[kFirstIdx + 1], &value8);
     EXPECT_EQ(visitedHandleMap[kLastIdx], &value9);

     resourceMap.clear();
 }

 // Tests that the iterator visits all valid handles when they are assigned only in the additional
 // flat array and the hash map.
 TEST(ResourceMapTest, IteratorVisitsAdditionalFlatArrayAndHashMap)
 {
     // Assign handles in the additional flat range [3, 10) and the hashmap (>= 10).  No handles are
     // assigned in the initial flat array [0, 3)
     constexpr AdditionalFlatType kAdditionalIdx0 = 4;
     constexpr AdditionalFlatType kAdditionalIdx1 = 8;
     constexpr AdditionalFlatType kHashmapIdx0    = 20;
     constexpr AdditionalFlatType kHashmapIdx1    = 21;
     size_t additionalValue0                      = 100;
     size_t additionalValue1                      = 200;
     size_t hashmapValue0                         = 300;
     size_t hashmapValue1                         = 400;

     ResourceMap<size_t, AdditionalFlatType> resourceMap;
     resourceMap.assign(kAdditionalIdx0, &additionalValue0);
     resourceMap.assign(kAdditionalIdx1, &additionalValue1);
     resourceMap.assign(kHashmapIdx0, &hashmapValue0);
     resourceMap.assign(kHashmapIdx1, &hashmapValue1);

     EXPECT_TRUE(resourceMap.contains(kAdditionalIdx0));
     EXPECT_EQ(resourceMap.query(kAdditionalIdx0), &additionalValue0);
     EXPECT_TRUE(resourceMap.contains(kAdditionalIdx1));
     EXPECT_EQ(resourceMap.query(kAdditionalIdx1), &additionalValue1);
     EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
     EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
     EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
     EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

     constexpr AdditionalFlatType kInitialArrayIdx = 1;

     // Since IDs in the initial flat array are never allocated, the lookup should always return
     // false or nullptr.
     EXPECT_FALSE(resourceMap.contains(kInitialArrayIdx));
     EXPECT_EQ(resourceMap.query(kInitialArrayIdx), nullptr);

     // The iterator must visit all four handles.
     std::map<GLuint, size_t *> visitedHandleMap;
     for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         visitedHandleMap[idValue.first] = idValue.second;
     }
     EXPECT_EQ(visitedHandleMap.size(), 4u);
     EXPECT_EQ(visitedHandleMap[kAdditionalIdx0], &additionalValue0);
     EXPECT_EQ(visitedHandleMap[kAdditionalIdx1], &additionalValue1);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

     resourceMap.clear();
 }

 // Tests that the iterator correctly transitions from the initial flat array to the hash map when
 // the additional flat array has never been allocated.  This verifies that nextResource() skips the
 // additional flat range when additionalResources is nullptr, so updateValue() never dereferences a
 // null pointer.
 TEST(ResourceMapTest, IteratorVisitsInitialFlatArrayAndHashMap)
 {
     // Assign handles in the initial flat array (1, 2) and in the hashmap (>= 10).  Since no handles
     // are assigned in the additional flat range [3, 10), mAdditionalFlatResources remains nullptr.
     constexpr AdditionalFlatType kInitialIdx0 = 1;
     constexpr AdditionalFlatType kInitialIdx1 = 2;
     constexpr AdditionalFlatType kHashmapIdx0 = 10;
     constexpr AdditionalFlatType kHashmapIdx1 = 18;
     size_t initialValue0                      = 100;
     size_t initialValue1                      = 200;
     size_t hashmapValue0                      = 300;
     size_t hashmapValue1                      = 400;

     ResourceMap<size_t, AdditionalFlatType> resourceMap;
     resourceMap.assign(kInitialIdx0, &initialValue0);
     resourceMap.assign(kInitialIdx1, &initialValue1);
     resourceMap.assign(kHashmapIdx0, &hashmapValue0);
     resourceMap.assign(kHashmapIdx1, &hashmapValue1);

     EXPECT_TRUE(resourceMap.contains(kInitialIdx0));
     EXPECT_EQ(resourceMap.query(kInitialIdx0), &initialValue0);
     EXPECT_TRUE(resourceMap.contains(kInitialIdx1));
     EXPECT_EQ(resourceMap.query(kInitialIdx1), &initialValue1);
     EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
     EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
     EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
     EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

     // Since IDs in the additional flat array are never allocated, the lookup should always return
     // false or nullptr.
     constexpr AdditionalFlatType kAdditionalArrayIdx = 5;
     EXPECT_FALSE(resourceMap.contains(kAdditionalArrayIdx));
     EXPECT_EQ(resourceMap.query(kAdditionalArrayIdx), nullptr);

     // The iterator must visit all four handles.
     std::map<GLuint, size_t *> visitedHandleMap;
     for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
     {
         visitedHandleMap[idValue.first] = idValue.second;
     }
     EXPECT_EQ(visitedHandleMap.size(), 4u);
     EXPECT_EQ(visitedHandleMap[kInitialIdx0], &initialValue0);
     EXPECT_EQ(visitedHandleMap[kInitialIdx1], &initialValue1);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
     EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

     resourceMap.clear();
 }
 }  // anonymous namespace
	//
	// Copyright 2018 The ANGLE Project Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.
	//
	// ResourceMap_unittest:
	// Unit tests for the ResourceMap template class.
	//

	#include <gtest/gtest.h>
	#include <map>

	#include "libANGLE/ResourceMap.h"

	using namespace gl;

	namespace gl
	{
	template <>
	inline GLuint GetIDValue(int id)
	{
	return id;
	}
	template <>
	inline GLuint GetIDValue(unsigned int id)
	{
	return id;
	}
	template <>
	inline GLuint GetIDValue(uint16_t id)
	{
	return id;
	}
	// For the purpose of unit testing, \|int\| is considered private (not needing lock), \|unsigned int\|
	// is considered shared (needing lock), and \|uint16_t\| additionally has a small flat array to
	// exercise all three storage levels.
	template <>
	struct ResourceMapParams<unsigned int>
	{
	static constexpr size_t kInitialFlatResourcesSize = 0xC0;
	static constexpr size_t kAdditionalFlatResourcesSize = 0;
	static constexpr bool kNeedsLock = true;
	};
	template <>
	struct ResourceMapParams<uint16_t>
	{
	static constexpr size_t kInitialFlatResourcesSize = 3;
	static constexpr size_t kAdditionalFlatResourcesSize = 7;
	static constexpr bool kNeedsLock = true;
	};
	} // namespace gl

	namespace
	{
	// The resourceMap class uses a lock for "unsigned int" types to support this unit test.
	using LocklessType = int;
	using LockedType = unsigned int;
	using AdditionalFlatType = uint16_t;

	template <typename T>
	void AssignAndErase()
	{
	constexpr size_t kSize = 300;
	ResourceMap<size_t, T> resourceMap;
	std::vector<size_t> objects(kSize, 1);
	for (size_t index = 0; index < kSize; ++index)
	{
	resourceMap.assign(index + 1, &objects[index]);
	}

	for (size_t index = 0; index < kSize; ++index)
	{
	size_t *found = nullptr;
	ASSERT_TRUE(resourceMap.erase(index + 1, &found));
	ASSERT_EQ(&objects[index], found);
	}

	ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
	}

	// Tests assigning slots in the map and then deleting elements.
	TEST(ResourceMapTest, AssignAndEraseLockless)
	{
	AssignAndErase<LocklessType>();
	}
	// Tests assigning slots in the map and then deleting elements.
	TEST(ResourceMapTest, AssignAndEraseLocked)
	{
	AssignAndErase<LockedType>();
	}

	template <typename T>
	void AssignAndClear()
	{
	constexpr size_t kSize = 280;
	ResourceMap<size_t, T> resourceMap;
	std::vector<size_t> objects(kSize, 1);
	for (size_t index = 0; index < kSize; ++index)
	{
	resourceMap.assign(index + 1, &objects[index]);
	}

	resourceMap.clear();
	ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
	}

	// Tests assigning slots in the map and then using clear() to free it.
	TEST(ResourceMapTest, AssignAndClearLockless)
	{
	AssignAndClear<LocklessType>();
	}
	// Tests assigning slots in the map and then using clear() to free it.
	TEST(ResourceMapTest, AssignAndClearLocked)
	{
	AssignAndClear<LockedType>();
	}

	template <typename T>
	void BigGrowth()
	{
	constexpr size_t kSize = 8;

	ResourceMap<size_t, T> resourceMap;
	std::vector<size_t> objects;

	for (size_t index = 0; index < kSize; ++index)
	{
	objects.push_back(index);
	}

	// Assign a large value.
	constexpr size_t kLargeIndex = 128;
	objects.push_back(kLargeIndex);

	for (size_t &object : objects)
	{
	resourceMap.assign(object, &object);
	}

	for (size_t object : objects)
	{
	size_t *found = nullptr;
	ASSERT_TRUE(resourceMap.erase(object, &found));
	ASSERT_EQ(object, *found);
	}

	ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
	}

	// Tests growing a map more than double the size.
	TEST(ResourceMapTest, BigGrowthLockless)
	{
	BigGrowth<LocklessType>();
	}
	// Tests growing a map more than double the size.
	TEST(ResourceMapTest, BigGrowthLocked)
	{
	BigGrowth<LockedType>();
	}

	template <typename T>
	void QueryUnassigned()
	{
	constexpr size_t kSize = 8;
	constexpr T kZero = 0;
	constexpr T kIdInFlatRange = 10;
	constexpr T kIdOutOfFlatRange = 500;

	ResourceMap<size_t, T> resourceMap;
	std::vector<size_t> objects;

	for (size_t index = 0; index < kSize; ++index)
	{
	objects.push_back(index);
	}

	ASSERT_FALSE(resourceMap.contains(kZero));
	ASSERT_EQ(nullptr, resourceMap.query(kZero));
	ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
	ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));

	for (size_t &object : objects)
	{
	resourceMap.assign(object, &object);
	}

	ASSERT_FALSE(UnsafeResourceMapIter(resourceMap).empty());

	for (size_t &object : objects)
	{
	ASSERT_TRUE(resourceMap.contains(object));
	ASSERT_EQ(&object, resourceMap.query(object));
	}

	ASSERT_FALSE(resourceMap.contains(kIdInFlatRange));
	ASSERT_EQ(nullptr, resourceMap.query(kIdInFlatRange));
	ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
	ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));

	for (size_t object : objects)
	{
	size_t *found = nullptr;
	ASSERT_TRUE(resourceMap.erase(object, &found));
	ASSERT_EQ(object, *found);
	}

	ASSERT_TRUE(UnsafeResourceMapIter(resourceMap).empty());

	ASSERT_FALSE(resourceMap.contains(kZero));
	ASSERT_EQ(nullptr, resourceMap.query(kZero));
	ASSERT_FALSE(resourceMap.contains(kIdOutOfFlatRange));
	ASSERT_EQ(nullptr, resourceMap.query(kIdOutOfFlatRange));
	}

	// Tests querying unassigned or erased values.
	TEST(ResourceMapTest, QueryUnassignedLockless)
	{
	QueryUnassigned<LocklessType>();
	}
	// Tests querying unassigned or erased values.
	TEST(ResourceMapTest, QueryUnassignedLocked)
	{
	QueryUnassigned<LockedType>();
	}

	template <typename IDType>
	void ConcurrentAccess(size_t iterations, size_t idCycleSize)
	{
	if (std::is_same_v<ResourceMapMutex, angle::NoOpMutex>)
	{
	GTEST_SKIP() << "Test skipped: Locking is disabled in build.";
	}

	constexpr size_t kThreadCount = 13;

	ResourceMap<size_t, IDType> resourceMap;

	std::array<std::thread, kThreadCount> threads;
	std::array<std::map<IDType, size_t>, kThreadCount> insertedIds;

	for (size_t i = 0; i < kThreadCount; ++i)
	{
	threads[i] = std::thread([&, i]() {
	// Each thread manipulates a different set of ids. The resource map guarantees that the
	// data structure itself is thread-safe, not accesses to the same id.
	for (size_t j = 0; j < iterations; ++j)
	{
	const IDType id =
	static_cast<IDType>((j % (idCycleSize / kThreadCount)) * kThreadCount + i);

	ASSERT_LE(id, 0xFFFFu);
	ASSERT_LE(j, 0xFFFFu);
	const size_t value = id \| j << 16;

	size_t valuePtr = reinterpret_cast<size_t >(value);

	const size_t *queryResult = resourceMap.query(id);
	const bool containsResult = resourceMap.contains(id);

	const bool expectContains = insertedIds[i].count(id) > 0;
	if (expectContains)
	{
	EXPECT_TRUE(containsResult);
	const IDType queryResultInt =
	static_cast<IDType>(reinterpret_cast<size_t>(queryResult) & 0xFFFF);
	const size_t queryResultIteration = reinterpret_cast<size_t>(queryResult) >> 16;
	EXPECT_EQ(queryResultInt, id);
	EXPECT_LT(queryResultIteration, j);

	size_t *erasedValue = nullptr;
	const bool erased = resourceMap.erase(id, &erasedValue);

	EXPECT_TRUE(erased);
	EXPECT_EQ(erasedValue, queryResult);

	insertedIds[i].erase(id);
	}
	else
	{
	EXPECT_FALSE(containsResult);
	EXPECT_EQ(queryResult, nullptr);

	resourceMap.assign(id, valuePtr);
	EXPECT_TRUE(resourceMap.contains(id));

	ASSERT_TRUE(insertedIds[i].count(id) == 0);
	insertedIds[i][id] = value;
	}
	}
	});
	}

	for (size_t i = 0; i < kThreadCount; ++i)
	{
	threads[i].join();
	}

	// Verify that every value that is expected to be there is actually there
	std::map<size_t, size_t> allIds;
	size_t allIdsPrevSize = 0;

	for (size_t i = 0; i < kThreadCount; ++i)
	{
	// Merge all the sets together. The sets are disjoint, which is verified by the ASSERT_EQ.
	allIds.insert(insertedIds[i].begin(), insertedIds[i].end());
	ASSERT_EQ(allIds.size(), allIdsPrevSize + insertedIds[i].size());
	allIdsPrevSize = allIds.size();

	// Make sure every id that is expected to be there is actually there.
	for (auto &idValue : insertedIds[i])
	{
	EXPECT_TRUE(resourceMap.contains(idValue.first));
	EXPECT_EQ(resourceMap.query(idValue.first), reinterpret_cast<size_t *>(idValue.second));
	}
	}

	// Verify that every value that is NOT expected to be there isn't actually there
	for (auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	EXPECT_TRUE(allIds.count(idValue.first) == 1);
	EXPECT_EQ(idValue.second, reinterpret_cast<size_t *>(allIds[idValue.first]));
	}

	resourceMap.clear();
	}

	// Tests that concurrent access to thread-safe resource maps works for small ids that are mostly in
	// the flat map range.
	TEST(ResourceMapTest, ConcurrentAccessSmallIds)
	{
	ConcurrentAccess<LockedType>(50'000, 128);
	}
	// Tests that concurrent access to thread-safe resource maps works for a wider range of ids.
	TEST(ResourceMapTest, ConcurrentAccessLargeIds)
	{
	ConcurrentAccess<LockedType>(10'000, 20'000);
	}
	// Tests that concurrent access to thread-safe resource maps works for the initial flat array, the
	// secondary flat array and the hashmap.
	TEST(ResourceMapTest, ConcurrentAccessFlatArraysAndHashMap)
	{
	// Set idCycleSize to 26 (2 * kThreadCount) so that each thread gets 2 IDs and covers the flat
	// arrays and the hashmap.
	ConcurrentAccess<AdditionalFlatType>(20'000, 26);
	}

	// Tests growth across the initial flat array, the secondary flat array, and the hashmap.
	TEST(ResourceMapTest, GrowthAcrossFlatArraysAndHashMap)
	{
	// Handle Layout
	// - initial flat array : 1, 2
	// - additional flat array : 3, 4, 5, 6, 7, 8, 9
	// - hashmap : 10, 11, 12
	constexpr size_t kTotalHandle = 12;
	std::vector<size_t> objects(kTotalHandle);
	for (size_t index = 0; index < kTotalHandle; ++index)
	{
	objects[index] = index + 1;
	}

	ResourceMap<size_t, AdditionalFlatType> resourceMap;

	for (size_t index = 0; index < kTotalHandle; ++index)
	{
	resourceMap.assign(static_cast<AdditionalFlatType>(index + 1), &objects[index]);
	}

	for (size_t index = 0; index < kTotalHandle; ++index)
	{
	const AdditionalFlatType handle = static_cast<AdditionalFlatType>(index + 1);
	EXPECT_TRUE(resourceMap.contains(handle)) << "handle=" << handle;
	EXPECT_EQ(resourceMap.query(handle), &objects[index]) << "handle=" << handle;
	}

	// Handles that have never been assigned must not be found.
	EXPECT_FALSE(resourceMap.contains(static_cast<AdditionalFlatType>(0)));
	EXPECT_EQ(resourceMap.query(static_cast<AdditionalFlatType>(0)), nullptr);
	EXPECT_FALSE(resourceMap.contains(static_cast<AdditionalFlatType>(kTotalHandle + 1)));
	EXPECT_EQ(resourceMap.query(static_cast<AdditionalFlatType>(kTotalHandle + 1)), nullptr);

	// The iterator must visit each assigned handle exactly once across all flat arrays and the
	// hashmap.
	std::map<GLuint, size_t *> visitedHandleMap;
	for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	EXPECT_EQ(visitedHandleMap.count(idValue.first), 0u) << "duplicate id=" << idValue.first;
	visitedHandleMap[idValue.first] = idValue.second;
	}
	EXPECT_EQ(visitedHandleMap.size(), kTotalHandle);

	for (size_t index = 0; index < kTotalHandle; ++index)
	{
	const GLuint handle = static_cast<GLuint>(index + 1);
	ASSERT_EQ(visitedHandleMap.count(handle), 1u) << "missing handle=" << handle;
	EXPECT_EQ(visitedHandleMap[handle], &objects[index]);
	}

	for (size_t index = 0; index < kTotalHandle; ++index)
	{
	const AdditionalFlatType handle = static_cast<AdditionalFlatType>(index + 1);
	size_t *erased = nullptr;
	EXPECT_TRUE(resourceMap.erase(handle, &erased)) << "handle=" << handle;
	EXPECT_EQ(erased, &objects[index]) << "handle=" << handle;
	EXPECT_FALSE(resourceMap.contains(handle)) << "handle is still present after erase";
	}

	EXPECT_TRUE(UnsafeResourceMapIter(resourceMap).empty());
	}

	// Tests that the iterator visits all valid handles when resources exist only in the hash map, and
	// no ID in the additional flat array has ever been assigned.
	TEST(ResourceMapTest, IteratorVisitsHashMapWithoutAdditionalFlatArray)
	{
	// Assign handles in the hashmap range to keep mAdditionalFlatResources nullptr.
	// kHashmapIdx0, kHashmapIdx1 >= kInitialFlatResourcesSize + kAdditionalFlatResourcesSize
	// >= kLocklessFlatResourcesLimit = 3 + 7 = 10
	constexpr AdditionalFlatType kHashmapIdx0 = 10;
	constexpr AdditionalFlatType kHashmapIdx1 = 11;
	size_t hashmapValue0 = 100;
	size_t hashmapValue1 = 200;

	ResourceMap<size_t, AdditionalFlatType> resourceMap;
	resourceMap.assign(kHashmapIdx0, &hashmapValue0);
	resourceMap.assign(kHashmapIdx1, &hashmapValue1);

	EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
	EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
	EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
	EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

	constexpr AdditionalFlatType kInitialArrayIdx = 1;
	constexpr AdditionalFlatType kAdditionalArrayIdx = 5;

	// Since IDs in the initial and additional flat arrays are never allocated, they should always
	// return false or nullptr.
	EXPECT_FALSE(resourceMap.contains(kInitialArrayIdx));
	EXPECT_EQ(resourceMap.query(kInitialArrayIdx), nullptr);
	EXPECT_FALSE(resourceMap.contains(kAdditionalArrayIdx));
	EXPECT_EQ(resourceMap.query(kAdditionalArrayIdx), nullptr);

	// The iterator must visit both hashmap entries.
	std::map<GLuint, size_t *> visitedHandleMap;
	for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	visitedHandleMap[idValue.first] = idValue.second;
	}
	EXPECT_EQ(visitedHandleMap.size(), 2u);
	EXPECT_EQ(visitedHandleMap.count(kHashmapIdx0), 1u);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
	EXPECT_EQ(visitedHandleMap.count(kHashmapIdx1), 1u);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

	resourceMap.clear();
	}

	// Tests that the iterator correctly visits all valid handles stored in the upper portion of the
	// additional flat array.
	TEST(ResourceMapTest, IteratorVisitsUpperAdditionalFlatArray)
	{
	// Additional flat range = [kInitialFlatResourcesSize, kLocklessFlatResourcesLimit) = [3, 10)
	// Assign handles in the upper portion of the additional flat array.
	constexpr AdditionalFlatType kFirstIdx = 7;
	constexpr AdditionalFlatType kLastIdx = 9;
	size_t value7 = 7;
	size_t value8 = 8;
	size_t value9 = 9;

	ResourceMap<size_t, AdditionalFlatType> resourceMap;
	resourceMap.assign(kFirstIdx, &value7);
	resourceMap.assign(kFirstIdx + 1, &value8);
	resourceMap.assign(kLastIdx, &value9);

	EXPECT_TRUE(resourceMap.contains(kFirstIdx));
	EXPECT_EQ(resourceMap.query(kFirstIdx), &value7);
	EXPECT_TRUE(resourceMap.contains(kFirstIdx + 1));
	EXPECT_EQ(resourceMap.query(kFirstIdx + 1), &value8);
	EXPECT_TRUE(resourceMap.contains(kLastIdx));
	EXPECT_EQ(resourceMap.query(kLastIdx), &value9);

	// Iterator must visit all three handles.
	std::map<GLuint, size_t *> visitedHandleMap;
	for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	visitedHandleMap[idValue.first] = idValue.second;
	}
	EXPECT_EQ(visitedHandleMap.size(), 3u);
	EXPECT_EQ(visitedHandleMap[kFirstIdx], &value7);
	EXPECT_EQ(visitedHandleMap[kFirstIdx + 1], &value8);
	EXPECT_EQ(visitedHandleMap[kLastIdx], &value9);

	resourceMap.clear();
	}

	// Tests that the iterator visits all valid handles when they are assigned only in the additional
	// flat array and the hash map.
	TEST(ResourceMapTest, IteratorVisitsAdditionalFlatArrayAndHashMap)
	{
	// Assign handles in the additional flat range [3, 10) and the hashmap (>= 10). No handles are
	// assigned in the initial flat array [0, 3)
	constexpr AdditionalFlatType kAdditionalIdx0 = 4;
	constexpr AdditionalFlatType kAdditionalIdx1 = 8;
	constexpr AdditionalFlatType kHashmapIdx0 = 20;
	constexpr AdditionalFlatType kHashmapIdx1 = 21;
	size_t additionalValue0 = 100;
	size_t additionalValue1 = 200;
	size_t hashmapValue0 = 300;
	size_t hashmapValue1 = 400;

	ResourceMap<size_t, AdditionalFlatType> resourceMap;
	resourceMap.assign(kAdditionalIdx0, &additionalValue0);
	resourceMap.assign(kAdditionalIdx1, &additionalValue1);
	resourceMap.assign(kHashmapIdx0, &hashmapValue0);
	resourceMap.assign(kHashmapIdx1, &hashmapValue1);

	EXPECT_TRUE(resourceMap.contains(kAdditionalIdx0));
	EXPECT_EQ(resourceMap.query(kAdditionalIdx0), &additionalValue0);
	EXPECT_TRUE(resourceMap.contains(kAdditionalIdx1));
	EXPECT_EQ(resourceMap.query(kAdditionalIdx1), &additionalValue1);
	EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
	EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
	EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
	EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

	constexpr AdditionalFlatType kInitialArrayIdx = 1;

	// Since IDs in the initial flat array are never allocated, the lookup should always return
	// false or nullptr.
	EXPECT_FALSE(resourceMap.contains(kInitialArrayIdx));
	EXPECT_EQ(resourceMap.query(kInitialArrayIdx), nullptr);

	// The iterator must visit all four handles.
	std::map<GLuint, size_t *> visitedHandleMap;
	for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	visitedHandleMap[idValue.first] = idValue.second;
	}
	EXPECT_EQ(visitedHandleMap.size(), 4u);
	EXPECT_EQ(visitedHandleMap[kAdditionalIdx0], &additionalValue0);
	EXPECT_EQ(visitedHandleMap[kAdditionalIdx1], &additionalValue1);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

	resourceMap.clear();
	}

	// Tests that the iterator correctly transitions from the initial flat array to the hash map when
	// the additional flat array has never been allocated. This verifies that nextResource() skips the
	// additional flat range when additionalResources is nullptr, so updateValue() never dereferences a
	// null pointer.
	TEST(ResourceMapTest, IteratorVisitsInitialFlatArrayAndHashMap)
	{
	// Assign handles in the initial flat array (1, 2) and in the hashmap (>= 10). Since no handles
	// are assigned in the additional flat range [3, 10), mAdditionalFlatResources remains nullptr.
	constexpr AdditionalFlatType kInitialIdx0 = 1;
	constexpr AdditionalFlatType kInitialIdx1 = 2;
	constexpr AdditionalFlatType kHashmapIdx0 = 10;
	constexpr AdditionalFlatType kHashmapIdx1 = 18;
	size_t initialValue0 = 100;
	size_t initialValue1 = 200;
	size_t hashmapValue0 = 300;
	size_t hashmapValue1 = 400;

	ResourceMap<size_t, AdditionalFlatType> resourceMap;
	resourceMap.assign(kInitialIdx0, &initialValue0);
	resourceMap.assign(kInitialIdx1, &initialValue1);
	resourceMap.assign(kHashmapIdx0, &hashmapValue0);
	resourceMap.assign(kHashmapIdx1, &hashmapValue1);

	EXPECT_TRUE(resourceMap.contains(kInitialIdx0));
	EXPECT_EQ(resourceMap.query(kInitialIdx0), &initialValue0);
	EXPECT_TRUE(resourceMap.contains(kInitialIdx1));
	EXPECT_EQ(resourceMap.query(kInitialIdx1), &initialValue1);
	EXPECT_TRUE(resourceMap.contains(kHashmapIdx0));
	EXPECT_EQ(resourceMap.query(kHashmapIdx0), &hashmapValue0);
	EXPECT_TRUE(resourceMap.contains(kHashmapIdx1));
	EXPECT_EQ(resourceMap.query(kHashmapIdx1), &hashmapValue1);

	// Since IDs in the additional flat array are never allocated, the lookup should always return
	// false or nullptr.
	constexpr AdditionalFlatType kAdditionalArrayIdx = 5;
	EXPECT_FALSE(resourceMap.contains(kAdditionalArrayIdx));
	EXPECT_EQ(resourceMap.query(kAdditionalArrayIdx), nullptr);

	// The iterator must visit all four handles.
	std::map<GLuint, size_t *> visitedHandleMap;
	for (const auto &idValue : UnsafeResourceMapIter(resourceMap))
	{
	visitedHandleMap[idValue.first] = idValue.second;
	}
	EXPECT_EQ(visitedHandleMap.size(), 4u);
	EXPECT_EQ(visitedHandleMap[kInitialIdx0], &initialValue0);
	EXPECT_EQ(visitedHandleMap[kInitialIdx1], &initialValue1);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx0], &hashmapValue0);
	EXPECT_EQ(visitedHandleMap[kHashmapIdx1], &hashmapValue1);

	resourceMap.clear();
	}
	} // anonymous namespace