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, typename IDType>
class ResourceMap final : angle::NonCopyable
{
  public:
    ResourceMap();
    ~ResourceMap();

    ANGLE_INLINE ResourceType *query(IDType id) const
    {
        GLuint handle = GetIDValue(id);
        if (handle < mFlatResourcesSize)
        {
            ResourceType *value = mFlatResources[handle];
            return (value == InvalidPointer() ? nullptr : value);
        }
        auto it = mHashedResources.find(handle);
        return (it == mHashedResources.end() ? nullptr : it->second);
    }

    // Returns true if the handle was reserved. Not necessarily if the resource is created.
    bool contains(IDType id) const;

    // Returns the element that was at this location.
    bool erase(IDType id, ResourceType **resourceOut);

    void assign(IDType id, ResourceType *resource);

    // Clears the map.
    void clear();

    using IndexAndResource = std::pair<GLuint, ResourceType *>;
    using HashMap          = angle::HashMap<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,
                 bool skipNulls);
        void updateValue();

        const ResourceMap &mOrigin;
        GLuint mFlatIndex;
        typename HashMap::const_iterator mHashIndex;
        IndexAndResource mValue;
        bool mSkipNulls;
    };

    // null values represent reserved handles.
    Iterator begin() const;
    Iterator end() const;
    Iterator find(IDType handle) const;

    Iterator beginWithNull() const;
    Iterator endWithNull() const;

    // Not a constant-time operation, should only be used for verification.
    bool empty() const;

  private:
    friend class Iterator;

    GLuint nextResource(size_t flatIndex, bool skipNulls) 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;

    // Size of one map element.
    static constexpr size_t kElementSize = sizeof(ResourceType *);

    size_t mFlatResourcesSize;
    ResourceType **mFlatResources;

    // A map of GL objects indexed by object ID.
    HashMap mHashedResources;
};

template <typename ResourceType, typename IDType>
ResourceMap<ResourceType, IDType>::ResourceMap()
    : mFlatResourcesSize(kInitialFlatResourcesSize),
      mFlatResources(new ResourceType *[kInitialFlatResourcesSize])
{
    memset(mFlatResources, kInvalidPointer, mFlatResourcesSize * kElementSize);
}

template <typename ResourceType, typename IDType>
ResourceMap<ResourceType, IDType>::~ResourceMap()
{
    ASSERT(empty());
    delete[] mFlatResources;
}

template <typename ResourceType, typename IDType>
ANGLE_INLINE bool ResourceMap<ResourceType, IDType>::contains(IDType id) const
{
    GLuint handle = GetIDValue(id);
    if (handle < mFlatResourcesSize)
    {
        return (mFlatResources[handle] != InvalidPointer());
    }
    return (mHashedResources.find(handle) != mHashedResources.end());
}

template <typename ResourceType, typename IDType>
bool ResourceMap<ResourceType, IDType>::erase(IDType id, ResourceType **resourceOut)
{
    GLuint handle = GetIDValue(id);
    if (handle < mFlatResourcesSize)
    {
        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, typename IDType>
void ResourceMap<ResourceType, IDType>::assign(IDType id, ResourceType *resource)
{
    GLuint handle = GetIDValue(id);
    if (handle < kFlatResourcesLimit)
    {
        if (handle >= mFlatResourcesSize)
        {
            // Use power-of-two.
            size_t newSize = mFlatResourcesSize;
            while (newSize <= handle)
            {
                newSize *= 2;
            }

            ResourceType **oldResources = mFlatResources;

            mFlatResources = new ResourceType *[newSize];
            memset(&mFlatResources[mFlatResourcesSize], kInvalidPointer,
                   (newSize - mFlatResourcesSize) * kElementSize);
            memcpy(mFlatResources, oldResources, mFlatResourcesSize * kElementSize);
            mFlatResourcesSize = newSize;
            delete[] oldResources;
        }
        ASSERT(mFlatResourcesSize > handle);
        mFlatResources[handle] = resource;
    }
    else
    {
        mHashedResources[handle] = resource;
    }
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::begin()
    const
{
    return Iterator(*this, nextResource(0, true), mHashedResources.begin(), true);
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::end() const
{
    return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), true);
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator
ResourceMap<ResourceType, IDType>::beginWithNull() const
{
    return Iterator(*this, nextResource(0, false), mHashedResources.begin(), false);
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator
ResourceMap<ResourceType, IDType>::endWithNull() const
{
    return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), false);
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::find(
    IDType handle) const
{
    if (handle < mFlatResourcesSize)
    {
        return (mFlatResources[handle] != InvalidPointer()
                    ? Iterator(handle, mHashedResources.begin())
                    : end());
    }
    else
    {
        return mHashedResources.find(handle);
    }
}

template <typename ResourceType, typename IDType>
bool ResourceMap<ResourceType, IDType>::empty() const
{
    return (begin() == end());
}

template <typename ResourceType, typename IDType>
void ResourceMap<ResourceType, IDType>::clear()
{
    memset(mFlatResources, kInvalidPointer, kInitialFlatResourcesSize * kElementSize);
    mFlatResourcesSize = kInitialFlatResourcesSize;
    mHashedResources.clear();
}

template <typename ResourceType, typename IDType>
GLuint ResourceMap<ResourceType, IDType>::nextResource(size_t flatIndex, bool skipNulls) const
{
    for (size_t index = flatIndex; index < mFlatResourcesSize; index++)
    {
        if ((mFlatResources[index] != nullptr || !skipNulls) &&
            mFlatResources[index] != InvalidPointer())
        {
            return static_cast<GLuint>(index);
        }
    }
    return static_cast<GLuint>(mFlatResourcesSize);
}

template <typename ResourceType, typename IDType>
// static
ResourceType *ResourceMap<ResourceType, IDType>::InvalidPointer()
{
    return reinterpret_cast<ResourceType *>(kInvalidPointer);
}

template <typename ResourceType, typename IDType>
ResourceMap<ResourceType, IDType>::Iterator::Iterator(
    const ResourceMap &origin,
    GLuint flatIndex,
    typename ResourceMap<ResourceType, IDType>::HashMap::const_iterator hashIndex,
    bool skipNulls)
    : mOrigin(origin), mFlatIndex(flatIndex), mHashIndex(hashIndex), mSkipNulls(skipNulls)
{
    updateValue();
}

template <typename ResourceType, typename IDType>
bool ResourceMap<ResourceType, IDType>::Iterator::operator==(const Iterator &other) const
{
    return (mFlatIndex == other.mFlatIndex && mHashIndex == other.mHashIndex);
}

template <typename ResourceType, typename IDType>
bool ResourceMap<ResourceType, IDType>::Iterator::operator!=(const Iterator &other) const
{
    return !(*this == other);
}

template <typename ResourceType, typename IDType>
typename ResourceMap<ResourceType, IDType>::Iterator &
ResourceMap<ResourceType, IDType>::Iterator::operator++()
{
    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
    {
        mFlatIndex = mOrigin.nextResource(mFlatIndex + 1, mSkipNulls);
    }
    else
    {
        mHashIndex++;
    }
    updateValue();
    return *this;
}

template <typename ResourceType, typename IDType>
const typename ResourceMap<ResourceType, IDType>::IndexAndResource *
ResourceMap<ResourceType, IDType>::Iterator::operator->() const
{
    return &mValue;
}

template <typename ResourceType, typename IDType>
const typename ResourceMap<ResourceType, IDType>::IndexAndResource &
ResourceMap<ResourceType, IDType>::Iterator::operator*() const
{
    return mValue;
}

template <typename ResourceType, typename IDType>
void ResourceMap<ResourceType, IDType>::Iterator::updateValue()
{
    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
    {
        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_