kc3-lang/angle/src/libANGLE/ResourceMap.h

• Show log

  Commit

• Hash : c859c0ac
  Author :
  Date : 2020-11-24T17:21:38
  

  Batch replace std::unordered_map with angle::HashMap in src/
  
  There are a few places that will remain std::unordered_map due to build
  or run-time errors, which will need to be evaluated more closely to
  determine if they should remain std::unordered_map or if there is
  another Abseil data structure that would be more efficient while still
  working correctly.
  
  Bug: angleproject:4873
  Change-Id: Ib04253e3ad6398e63f4cc2bfe12c0f9e57cb112b
  Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/2558873
  Commit-Queue: Tim Van Patten <timvp@google.com>
  Reviewed-by: Jamie Madill <jmadill@chromium.org>
  Reviewed-by: Shahbaz Youssefi <syoussefi@chromium.org>
  Reviewed-by: Charlie Lao <cclao@google.com>
  

Download

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

Download