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