1 files changed, 305 insertions, 0 deletions
diff --git a/src/3rdparty/angle/src/libANGLE/ResourceMap.h b/src/3rdparty/angle/src/libANGLE/ResourceMap.h
new file mode 100644
index 0000000000..b00da68612
--- /dev/null
+++ b/src/3rdparty/angle/src/libANGLE/ResourceMap.h
@@ -0,0 +1,305 @@
+//
+// Copyright 2017 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:
+//   An optimized resource map which packs the first set of allocated objects into a
+//   flat array, and then falls back to an unordered map for the higher handle values.
+//
+
+#ifndef LIBANGLE_RESOURCE_MAP_H_
+#define LIBANGLE_RESOURCE_MAP_H_
+
+#include "libANGLE/angletypes.h"
+
+namespace gl
+{
+
+template <typename ResourceType>
+class ResourceMap final : angle::NonCopyable
+{
+  public:
+    ResourceMap();
+    ~ResourceMap();
+
+    ResourceType *query(GLuint handle) const;
+
+    // Returns true if the handle was reserved. Not necessarily if the resource is created.
+    bool contains(GLuint handle) const;
+
+    // Returns the element that was at this location.
+    bool erase(GLuint handle, ResourceType **resourceOut);
+
+    void assign(GLuint handle, ResourceType *resource);
+
+    // Clears the map.
+    void clear();
+
+    using IndexAndResource = std::pair<GLuint, ResourceType *>;
+    using HashMap          = std::unordered_map<GLuint, ResourceType *>;
+
+    class Iterator final
+    {
+      public:
+        bool operator==(const Iterator &other) const;
+        bool operator!=(const Iterator &other) const;
+        Iterator &operator++();
+        const IndexAndResource *operator->() const;
+        const IndexAndResource &operator*() const;
+
+      private:
+        friend class ResourceMap;
+        Iterator(const ResourceMap &origin,
+                 GLuint flatIndex,
+                 typename HashMap::const_iterator hashIndex);
+        void updateValue();
+
+        const ResourceMap &mOrigin;
+        GLuint mFlatIndex;
+        typename HashMap::const_iterator mHashIndex;
+        IndexAndResource mValue;
+    };
+
+    // null values represent reserved handles.
+    Iterator begin() const;
+    Iterator end() const;
+    Iterator find(GLuint handle) const;
+
+    // Not a constant-time operation, should only be used for verification.
+    bool empty() const;
+
+  private:
+    friend class Iterator;
+
+    GLuint nextNonNullResource(size_t flatIndex) const;
+
+    // constexpr methods cannot contain reinterpret_cast, so we need a static method.
+    static ResourceType *InvalidPointer();
+    static constexpr intptr_t kInvalidPointer = static_cast<intptr_t>(-1);
+
+    // Start with 32 maximum elements in the map, which can grow.
+    static constexpr size_t kInitialFlatResourcesSize = 0x20;
+
+    // Experimental testing suggests that 16k is a reasonable upper limit.
+    static constexpr size_t kFlatResourcesLimit = 0x4000;
+
+    std::vector<ResourceType *> mFlatResources;
+
+    // A map of GL objects indexed by object ID.
+    HashMap mHashedResources;
+};
+
+template <typename ResourceType>
+ResourceMap<ResourceType>::ResourceMap()
+    : mFlatResources(kInitialFlatResourcesSize, InvalidPointer()), mHashedResources()
+{
+}
+
+template <typename ResourceType>
+ResourceMap<ResourceType>::~ResourceMap()
+{
+    ASSERT(empty());
+}
+
+template <typename ResourceType>
+ResourceType *ResourceMap<ResourceType>::query(GLuint handle) const
+{
+    if (handle < mFlatResources.size())
+    {
+        auto value = mFlatResources[handle];
+        return (value == InvalidPointer() ? nullptr : value);
+    }
+    auto it = mHashedResources.find(handle);
+    return (it == mHashedResources.end() ? nullptr : it->second);
+}
+
+template <typename ResourceType>
+bool ResourceMap<ResourceType>::contains(GLuint handle) const
+{
+    if (handle < mFlatResources.size())
+    {
+        return (mFlatResources[handle] != InvalidPointer());
+    }
+    return (mHashedResources.find(handle) != mHashedResources.end());
+}
+
+template <typename ResourceType>
+bool ResourceMap<ResourceType>::erase(GLuint handle, ResourceType **resourceOut)
+{
+    if (handle < mFlatResources.size())
+    {
+        auto &value = mFlatResources[handle];
+        if (value == InvalidPointer())
+        {
+            return false;
+        }
+        *resourceOut = value;
+        value        = InvalidPointer();
+    }
+    else
+    {
+        auto it = mHashedResources.find(handle);
+        if (it == mHashedResources.end())
+        {
+            return false;
+        }
+        *resourceOut = it->second;
+        mHashedResources.erase(it);
+    }
+    return true;
+}
+
+template <typename ResourceType>
+void ResourceMap<ResourceType>::assign(GLuint handle, ResourceType *resource)
+{
+    if (handle < kFlatResourcesLimit)
+    {
+        if (handle >= mFlatResources.size())
+        {
+            // Use power-of-two.
+            size_t newSize = mFlatResources.size();
+            while (newSize <= handle)
+            {
+                newSize *= 2;
+            }
+            mFlatResources.resize(newSize, nullptr);
+        }
+        ASSERT(mFlatResources.size() > handle);
+        mFlatResources[handle] = resource;
+    }
+    else
+    {
+        mHashedResources[handle] = resource;
+    }
+}
+
+template <typename ResourceType>
+typename ResourceMap<ResourceType>::Iterator ResourceMap<ResourceType>::begin() const
+{
+    return Iterator(*this, nextNonNullResource(0), mHashedResources.begin());
+}
+
+template <typename ResourceType>
+typename ResourceMap<ResourceType>::Iterator ResourceMap<ResourceType>::end() const
+{
+    return Iterator(*this, static_cast<GLuint>(mFlatResources.size()), mHashedResources.end());
+}
+
+template <typename ResourceType>
+typename ResourceMap<ResourceType>::Iterator ResourceMap<ResourceType>::find(GLuint handle) const
+{
+    if (handle < mFlatResources.size())
+    {
+        return (mFlatResources[handle] != InvalidPointer()
+                    ? Iterator(handle, mHashedResources.begin())
+                    : end());
+    }
+    else
+    {
+        return mHashedResources.find(handle);
+    }
+}
+
+template <typename ResourceType>
+bool ResourceMap<ResourceType>::empty() const
+{
+    return (begin() == end());
+}
+
+template <typename ResourceType>
+void ResourceMap<ResourceType>::clear()
+{
+    mFlatResources.assign(kInitialFlatResourcesSize, InvalidPointer());
+    mHashedResources.clear();
+}
+
+template <typename ResourceType>
+GLuint ResourceMap<ResourceType>::nextNonNullResource(size_t flatIndex) const
+{
+    for (size_t index = flatIndex; index < mFlatResources.size(); index++)
+    {
+        if (mFlatResources[index] != nullptr && mFlatResources[index] != InvalidPointer())
+        {
+            return static_cast<GLuint>(index);
+        }
+    }
+    return static_cast<GLuint>(mFlatResources.size());
+}
+
+template <typename ResourceType>
+// static
+ResourceType *ResourceMap<ResourceType>::InvalidPointer()
+{
+    return reinterpret_cast<ResourceType *>(kInvalidPointer);
+}
+
+template <typename ResourceType>
+ResourceMap<ResourceType>::Iterator::Iterator(
+    const ResourceMap &origin,
+    GLuint flatIndex,
+    typename ResourceMap<ResourceType>::HashMap::const_iterator hashIndex)
+    : mOrigin(origin), mFlatIndex(flatIndex), mHashIndex(hashIndex), mValue()
+{
+    updateValue();
+}
+
+template <typename ResourceType>
+bool ResourceMap<ResourceType>::Iterator::operator==(const Iterator &other) const
+{
+    return (mFlatIndex == other.mFlatIndex && mHashIndex == other.mHashIndex);
+}
+
+template <typename ResourceType>
+bool ResourceMap<ResourceType>::Iterator::operator!=(const Iterator &other) const
+{
+    return !(*this == other);
+}
+
+template <typename ResourceType>
+typename ResourceMap<ResourceType>::Iterator &ResourceMap<ResourceType>::Iterator::operator++()
+{
+    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResources.size()))
+    {
+        mFlatIndex = mOrigin.nextNonNullResource(mFlatIndex + 1);
+    }
+    else
+    {
+        mHashIndex++;
+    }
+    updateValue();
+    return *this;
+}
+
+template <typename ResourceType>
+const typename ResourceMap<ResourceType>::IndexAndResource
+    *ResourceMap<ResourceType>::Iterator::operator->() const
+{
+    return &mValue;
+}
+
+template <typename ResourceType>
+const typename ResourceMap<ResourceType>::IndexAndResource
+    &ResourceMap<ResourceType>::Iterator::operator*() const
+{
+    return mValue;
+}
+
+template <typename ResourceType>
+void ResourceMap<ResourceType>::Iterator::updateValue()
+{
+    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResources.size()))
+    {
+        mValue.first  = mFlatIndex;
+        mValue.second = mOrigin.mFlatResources[mFlatIndex];
+    }
+    else if (mHashIndex != mOrigin.mHashedResources.end())
+    {
+        mValue.first  = mHashIndex->first;
+        mValue.second = mHashIndex->second;
+    }
+}
+
+}  // namespace gl
+
+#endif  // LIBANGLE_RESOURCE_MAP_H_