tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

ResourceMap.h (10524B)

      1 //
      2 // Copyright 2017 The ANGLE Project Authors. All rights reserved.
      3 // Use of this source code is governed by a BSD-style license that can be
      4 // found in the LICENSE file.
      5 //
      6 // ResourceMap:
      7 //   An optimized resource map which packs the first set of allocated objects into a
      8 //   flat array, and then falls back to an unordered map for the higher handle values.
      9 //
     10 
     11 #ifndef LIBANGLE_RESOURCE_MAP_H_
     12 #define LIBANGLE_RESOURCE_MAP_H_
     13 
     14 #include "libANGLE/angletypes.h"
     15 
     16 namespace gl
     17 {
     18 
     19 template <typename ResourceType, typename IDType>
     20 class ResourceMap final : angle::NonCopyable
     21 {
     22  public:
     23    ResourceMap();
     24    ~ResourceMap();
     25 
     26    ANGLE_INLINE ResourceType *query(IDType id) const
     27    {
     28        GLuint handle = GetIDValue(id);
     29        if (handle < mFlatResourcesSize)
     30        {
     31            ResourceType *value = mFlatResources[handle];
     32            return (value == InvalidPointer() ? nullptr : value);
     33        }
     34        auto it = mHashedResources.find(handle);
     35        return (it == mHashedResources.end() ? nullptr : it->second);
     36    }
     37 
     38    // Returns true if the handle was reserved. Not necessarily if the resource is created.
     39    bool contains(IDType id) const;
     40 
     41    // Returns the element that was at this location.
     42    bool erase(IDType id, ResourceType **resourceOut);
     43 
     44    void assign(IDType id, ResourceType *resource);
     45 
     46    // Clears the map.
     47    void clear();
     48 
     49    using IndexAndResource = std::pair<GLuint, ResourceType *>;
     50    using HashMap          = angle::HashMap<GLuint, ResourceType *>;
     51 
     52    class Iterator final
     53    {
     54      public:
     55        bool operator==(const Iterator &other) const;
     56        bool operator!=(const Iterator &other) const;
     57        Iterator &operator++();
     58        const IndexAndResource *operator->() const;
     59        const IndexAndResource &operator*() const;
     60 
     61      private:
     62        friend class ResourceMap;
     63        Iterator(const ResourceMap &origin,
     64                 GLuint flatIndex,
     65                 typename HashMap::const_iterator hashIndex,
     66                 bool skipNulls);
     67        void updateValue();
     68 
     69        const ResourceMap &mOrigin;
     70        GLuint mFlatIndex;
     71        typename HashMap::const_iterator mHashIndex;
     72        IndexAndResource mValue;
     73        bool mSkipNulls;
     74    };
     75 
     76    // null values represent reserved handles.
     77    Iterator begin() const;
     78    Iterator end() const;
     79    Iterator find(IDType handle) const;
     80 
     81    Iterator beginWithNull() const;
     82    Iterator endWithNull() const;
     83 
     84    // Not a constant-time operation, should only be used for verification.
     85    bool empty() const;
     86 
     87  private:
     88    friend class Iterator;
     89 
     90    GLuint nextResource(size_t flatIndex, bool skipNulls) const;
     91 
     92    // constexpr methods cannot contain reinterpret_cast, so we need a static method.
     93    static ResourceType *InvalidPointer();
     94    static constexpr intptr_t kInvalidPointer = static_cast<intptr_t>(-1);
     95 
     96    // Start with 32 maximum elements in the map, which can grow.
     97    static constexpr size_t kInitialFlatResourcesSize = 0x20;
     98 
     99    // Experimental testing suggests that 16k is a reasonable upper limit.
    100    static constexpr size_t kFlatResourcesLimit = 0x4000;
    101 
    102    // Size of one map element.
    103    static constexpr size_t kElementSize = sizeof(ResourceType *);
    104 
    105    size_t mFlatResourcesSize;
    106    ResourceType **mFlatResources;
    107 
    108    // A map of GL objects indexed by object ID.
    109    HashMap mHashedResources;
    110 };
    111 
    112 template <typename ResourceType, typename IDType>
    113 ResourceMap<ResourceType, IDType>::ResourceMap()
    114    : mFlatResourcesSize(kInitialFlatResourcesSize),
    115      mFlatResources(new ResourceType *[kInitialFlatResourcesSize])
    116 {
    117    memset(mFlatResources, kInvalidPointer, mFlatResourcesSize * kElementSize);
    118 }
    119 
    120 template <typename ResourceType, typename IDType>
    121 ResourceMap<ResourceType, IDType>::~ResourceMap()
    122 {
    123    ASSERT(empty());
    124    delete[] mFlatResources;
    125 }
    126 
    127 template <typename ResourceType, typename IDType>
    128 ANGLE_INLINE bool ResourceMap<ResourceType, IDType>::contains(IDType id) const
    129 {
    130    GLuint handle = GetIDValue(id);
    131    if (handle < mFlatResourcesSize)
    132    {
    133        return (mFlatResources[handle] != InvalidPointer());
    134    }
    135    return (mHashedResources.find(handle) != mHashedResources.end());
    136 }
    137 
    138 template <typename ResourceType, typename IDType>
    139 bool ResourceMap<ResourceType, IDType>::erase(IDType id, ResourceType **resourceOut)
    140 {
    141    GLuint handle = GetIDValue(id);
    142    if (handle < mFlatResourcesSize)
    143    {
    144        auto &value = mFlatResources[handle];
    145        if (value == InvalidPointer())
    146        {
    147            return false;
    148        }
    149        *resourceOut = value;
    150        value        = InvalidPointer();
    151    }
    152    else
    153    {
    154        auto it = mHashedResources.find(handle);
    155        if (it == mHashedResources.end())
    156        {
    157            return false;
    158        }
    159        *resourceOut = it->second;
    160        mHashedResources.erase(it);
    161    }
    162    return true;
    163 }
    164 
    165 template <typename ResourceType, typename IDType>
    166 void ResourceMap<ResourceType, IDType>::assign(IDType id, ResourceType *resource)
    167 {
    168    GLuint handle = GetIDValue(id);
    169    if (handle < kFlatResourcesLimit)
    170    {
    171        if (handle >= mFlatResourcesSize)
    172        {
    173            // Use power-of-two.
    174            size_t newSize = mFlatResourcesSize;
    175            while (newSize <= handle)
    176            {
    177                newSize *= 2;
    178            }
    179 
    180            ResourceType **oldResources = mFlatResources;
    181 
    182            mFlatResources = new ResourceType *[newSize];
    183            memset(&mFlatResources[mFlatResourcesSize], kInvalidPointer,
    184                   (newSize - mFlatResourcesSize) * kElementSize);
    185            memcpy(mFlatResources, oldResources, mFlatResourcesSize * kElementSize);
    186            mFlatResourcesSize = newSize;
    187            delete[] oldResources;
    188        }
    189        ASSERT(mFlatResourcesSize > handle);
    190        mFlatResources[handle] = resource;
    191    }
    192    else
    193    {
    194        mHashedResources[handle] = resource;
    195    }
    196 }
    197 
    198 template <typename ResourceType, typename IDType>
    199 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::begin()
    200    const
    201 {
    202    return Iterator(*this, nextResource(0, true), mHashedResources.begin(), true);
    203 }
    204 
    205 template <typename ResourceType, typename IDType>
    206 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::end() const
    207 {
    208    return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), true);
    209 }
    210 
    211 template <typename ResourceType, typename IDType>
    212 typename ResourceMap<ResourceType, IDType>::Iterator
    213 ResourceMap<ResourceType, IDType>::beginWithNull() const
    214 {
    215    return Iterator(*this, nextResource(0, false), mHashedResources.begin(), false);
    216 }
    217 
    218 template <typename ResourceType, typename IDType>
    219 typename ResourceMap<ResourceType, IDType>::Iterator
    220 ResourceMap<ResourceType, IDType>::endWithNull() const
    221 {
    222    return Iterator(*this, static_cast<GLuint>(mFlatResourcesSize), mHashedResources.end(), false);
    223 }
    224 
    225 template <typename ResourceType, typename IDType>
    226 typename ResourceMap<ResourceType, IDType>::Iterator ResourceMap<ResourceType, IDType>::find(
    227    IDType handle) const
    228 {
    229    if (handle < mFlatResourcesSize)
    230    {
    231        return (mFlatResources[handle] != InvalidPointer()
    232                    ? Iterator(handle, mHashedResources.begin())
    233                    : end());
    234    }
    235    else
    236    {
    237        return mHashedResources.find(handle);
    238    }
    239 }
    240 
    241 template <typename ResourceType, typename IDType>
    242 bool ResourceMap<ResourceType, IDType>::empty() const
    243 {
    244    return (begin() == end());
    245 }
    246 
    247 template <typename ResourceType, typename IDType>
    248 void ResourceMap<ResourceType, IDType>::clear()
    249 {
    250    memset(mFlatResources, kInvalidPointer, kInitialFlatResourcesSize * kElementSize);
    251    mFlatResourcesSize = kInitialFlatResourcesSize;
    252    mHashedResources.clear();
    253 }
    254 
    255 template <typename ResourceType, typename IDType>
    256 GLuint ResourceMap<ResourceType, IDType>::nextResource(size_t flatIndex, bool skipNulls) const
    257 {
    258    for (size_t index = flatIndex; index < mFlatResourcesSize; index++)
    259    {
    260        if ((mFlatResources[index] != nullptr || !skipNulls) &&
    261            mFlatResources[index] != InvalidPointer())
    262        {
    263            return static_cast<GLuint>(index);
    264        }
    265    }
    266    return static_cast<GLuint>(mFlatResourcesSize);
    267 }
    268 
    269 template <typename ResourceType, typename IDType>
    270 // static
    271 ResourceType *ResourceMap<ResourceType, IDType>::InvalidPointer()
    272 {
    273    return reinterpret_cast<ResourceType *>(kInvalidPointer);
    274 }
    275 
    276 template <typename ResourceType, typename IDType>
    277 ResourceMap<ResourceType, IDType>::Iterator::Iterator(
    278    const ResourceMap &origin,
    279    GLuint flatIndex,
    280    typename ResourceMap<ResourceType, IDType>::HashMap::const_iterator hashIndex,
    281    bool skipNulls)
    282    : mOrigin(origin), mFlatIndex(flatIndex), mHashIndex(hashIndex), mSkipNulls(skipNulls)
    283 {
    284    updateValue();
    285 }
    286 
    287 template <typename ResourceType, typename IDType>
    288 bool ResourceMap<ResourceType, IDType>::Iterator::operator==(const Iterator &other) const
    289 {
    290    return (mFlatIndex == other.mFlatIndex && mHashIndex == other.mHashIndex);
    291 }
    292 
    293 template <typename ResourceType, typename IDType>
    294 bool ResourceMap<ResourceType, IDType>::Iterator::operator!=(const Iterator &other) const
    295 {
    296    return !(*this == other);
    297 }
    298 
    299 template <typename ResourceType, typename IDType>
    300 typename ResourceMap<ResourceType, IDType>::Iterator &
    301 ResourceMap<ResourceType, IDType>::Iterator::operator++()
    302 {
    303    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
    304    {
    305        mFlatIndex = mOrigin.nextResource(mFlatIndex + 1, mSkipNulls);
    306    }
    307    else
    308    {
    309        mHashIndex++;
    310    }
    311    updateValue();
    312    return *this;
    313 }
    314 
    315 template <typename ResourceType, typename IDType>
    316 const typename ResourceMap<ResourceType, IDType>::IndexAndResource *
    317 ResourceMap<ResourceType, IDType>::Iterator::operator->() const
    318 {
    319    return &mValue;
    320 }
    321 
    322 template <typename ResourceType, typename IDType>
    323 const typename ResourceMap<ResourceType, IDType>::IndexAndResource &
    324 ResourceMap<ResourceType, IDType>::Iterator::operator*() const
    325 {
    326    return mValue;
    327 }
    328 
    329 template <typename ResourceType, typename IDType>
    330 void ResourceMap<ResourceType, IDType>::Iterator::updateValue()
    331 {
    332    if (mFlatIndex < static_cast<GLuint>(mOrigin.mFlatResourcesSize))
    333    {
    334        mValue.first  = mFlatIndex;
    335        mValue.second = mOrigin.mFlatResources[mFlatIndex];
    336    }
    337    else if (mHashIndex != mOrigin.mHashedResources.end())
    338    {
    339        mValue.first  = mHashIndex->first;
    340        mValue.second = mHashIndex->second;
    341    }
    342 }
    343 
    344 }  // namespace gl
    345 
    346 #endif  // LIBANGLE_RESOURCE_MAP_H_