src/libANGLE/ResourceMap.h

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