tor-browser

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

SizedMRUCache.h (4063B)

      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 // SizedMRUCache.h: A hashing map that stores blobs of sized, untyped data.
      7 
      8 #ifndef LIBANGLE_SIZED_MRU_CACHE_H_
      9 #define LIBANGLE_SIZED_MRU_CACHE_H_
     10 
     11 #include <anglebase/containers/mru_cache.h>
     12 
     13 namespace angle
     14 {
     15 
     16 template <typename Key, typename Value>
     17 class SizedMRUCache final : angle::NonCopyable
     18 {
     19  public:
     20    SizedMRUCache(size_t maximumTotalSize)
     21        : mMaximumTotalSize(maximumTotalSize),
     22          mCurrentSize(0),
     23          mStore(SizedMRUCacheStore::NO_AUTO_EVICT)
     24    {}
     25 
     26    // Returns nullptr on failure.
     27    const Value *put(const Key &key, Value &&value, size_t size)
     28    {
     29        if (size > mMaximumTotalSize)
     30        {
     31            return nullptr;
     32        }
     33 
     34        // Check for existing key.
     35        eraseByKey(key);
     36 
     37        auto retVal = mStore.Put(key, ValueAndSize(std::move(value), size));
     38        mCurrentSize += size;
     39 
     40        shrinkToSize(mMaximumTotalSize);
     41 
     42        return &retVal->second.value;
     43    }
     44 
     45    bool get(const Key &key, const Value **valueOut)
     46    {
     47        const auto &iter = mStore.Get(key);
     48        if (iter == mStore.end())
     49        {
     50            return false;
     51        }
     52        *valueOut = &iter->second.value;
     53        return true;
     54    }
     55 
     56    bool getAt(size_t index, const Key **keyOut, const Value **valueOut)
     57    {
     58        if (index < mStore.size())
     59        {
     60            auto it = mStore.begin();
     61            std::advance(it, index);
     62            *keyOut   = &it->first;
     63            *valueOut = &it->second.value;
     64            return true;
     65        }
     66        *valueOut = nullptr;
     67        return false;
     68    }
     69 
     70    bool empty() const { return mStore.empty(); }
     71 
     72    void clear()
     73    {
     74        mStore.Clear();
     75        mCurrentSize = 0;
     76    }
     77 
     78    void eraseByKey(const Key &key)
     79    {
     80        // Check for existing key.
     81        auto existing = mStore.Peek(key);
     82        if (existing != mStore.end())
     83        {
     84            mCurrentSize -= existing->second.size;
     85            mStore.Erase(existing);
     86        }
     87    }
     88 
     89    size_t entryCount() const { return mStore.size(); }
     90 
     91    size_t size() const { return mCurrentSize; }
     92 
     93    // Also discards the cache contents.
     94    void resize(size_t maximumTotalSize)
     95    {
     96        clear();
     97        mMaximumTotalSize = maximumTotalSize;
     98    }
     99 
    100    // Reduce current memory usage.
    101    size_t shrinkToSize(size_t limit)
    102    {
    103        size_t initialSize = mCurrentSize;
    104 
    105        while (mCurrentSize > limit)
    106        {
    107            ASSERT(!mStore.empty());
    108            auto iter = mStore.rbegin();
    109            mCurrentSize -= iter->second.size;
    110            mStore.Erase(iter);
    111        }
    112 
    113        return (initialSize - mCurrentSize);
    114    }
    115 
    116    size_t maxSize() const { return mMaximumTotalSize; }
    117 
    118  private:
    119    struct ValueAndSize
    120    {
    121        ValueAndSize() : value(), size(0) {}
    122        ValueAndSize(Value &&value, size_t size) : value(std::move(value)), size(size) {}
    123        ValueAndSize(ValueAndSize &&other) : ValueAndSize() { *this = std::move(other); }
    124        ValueAndSize &operator=(ValueAndSize &&other)
    125        {
    126            std::swap(value, other.value);
    127            std::swap(size, other.size);
    128            return *this;
    129        }
    130 
    131        Value value;
    132        size_t size;
    133    };
    134 
    135    using SizedMRUCacheStore = base::HashingMRUCache<Key, ValueAndSize>;
    136 
    137    size_t mMaximumTotalSize;
    138    size_t mCurrentSize;
    139    SizedMRUCacheStore mStore;
    140 };
    141 
    142 // Helper function used in a few places.
    143 template <typename T>
    144 void TrimCache(size_t maxStates, size_t gcLimit, const char *name, T *cache)
    145 {
    146    const size_t kGarbageCollectionLimit = maxStates / 2 + gcLimit;
    147 
    148    if (cache->size() >= kGarbageCollectionLimit)
    149    {
    150        WARN() << "Overflowed the " << name << " cache limit of " << (maxStates / 2)
    151               << " elements, removing the least recently used to make room.";
    152        cache->ShrinkToSize(maxStates / 2);
    153    }
    154 }
    155 }  // namespace angle
    156 #endif  // LIBANGLE_SIZED_MRU_CACHE_H_