diff options
Diffstat (limited to '')
| -rw-r--r-- | gfx/angle/checkout/src/libANGLE/ResourceMap.h | 346 |
1 files changed, 346 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/libANGLE/ResourceMap.h b/gfx/angle/checkout/src/libANGLE/ResourceMap.h new file mode 100644 index 0000000000..b24c1e6240 --- /dev/null +++ b/gfx/angle/checkout/src/libANGLE/ResourceMap.h @@ -0,0 +1,346 @@ +// +// 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_ |