diff options
Diffstat (limited to 'Build/source/utils/asymptote/LspCpp/LibLsp/lsp/lru_cache.h')
-rw-r--r-- | Build/source/utils/asymptote/LspCpp/LibLsp/lsp/lru_cache.h | 151 |
1 files changed, 0 insertions, 151 deletions
diff --git a/Build/source/utils/asymptote/LspCpp/LibLsp/lsp/lru_cache.h b/Build/source/utils/asymptote/LspCpp/LibLsp/lsp/lru_cache.h deleted file mode 100644 index f33bc5627a8..00000000000 --- a/Build/source/utils/asymptote/LspCpp/LibLsp/lsp/lru_cache.h +++ /dev/null @@ -1,151 +0,0 @@ -#pragma once - -#include <algorithm> -#include <cassert> -#include <limits> -#include <memory> -#include <vector> - -// Cache that evicts old entries which have not been used recently. Implemented -// using array/linear search so this works well for small array sizes. -template <typename TKey, typename TValue> -struct LruCache { - explicit LruCache(int max_entries); - - // Fetches an entry for |key|. If it does not exist, |allocator| will be - // invoked to create one. - template <typename TAllocator> - TValue Get(const TKey& key, TAllocator allocator); - // Returns true if there is an entry for |key|. - bool Has(const TKey& key); - // Fetches the entry for |filename| and updates it's usage so it is less - // likely to be evicted. - bool TryGet(const TKey& key, TValue* dest); - // TryGetEntry, except the entry is removed from the cache. - bool TryTake(const TKey& key, TValue* dest); - // Inserts an entry. Evicts the oldest unused entry if there is no space. - void Insert(const TKey& key, const TValue& value); - - // Call |func| on existing entries. If |func| returns false iteration - // terminates early. - template <typename TFunc> - void IterateValues(TFunc func); - - // Empties the cache - void Clear(void); - - private: - // There is a global score counter, when we access an element we increase - // its score to the current global value, so it has the highest overall - // score. This means that the oldest/least recently accessed value has the - // lowest score. - // - // There is a bit of special logic to handle score overlow. - struct Entry { - uint32_t score = 0; - TKey key; - TValue value; - bool operator<(const Entry& other) const { return score < other.score; } - }; - - void IncrementScore(); - - std::vector<Entry> entries_; - int max_entries_ = 1; - uint32_t next_score_ = 0; -}; - -template <typename TKey, typename TValue> -LruCache<TKey, TValue>::LruCache(int max_entries) : max_entries_(max_entries) { - assert(max_entries > 0); -} - -template <typename TKey, typename TValue> -template <typename TAllocator> -TValue LruCache<TKey, TValue>::Get(const TKey& key, TAllocator allocator) { - for (Entry& entry : entries_) { - if (entry.key == key) - return entry.value; - } - - auto result = allocator(); - Insert(key, result); - return result; -} - -template <typename TKey, typename TValue> -bool LruCache<TKey, TValue>::Has(const TKey& key) { - for (Entry& entry : entries_) { - if (entry.key == key) - return true; - } - return false; -} - -template <typename TKey, typename TValue> -bool LruCache<TKey, TValue>::TryGet(const TKey& key, TValue* dest) { - // Assign new score. - for (Entry& entry : entries_) { - if (entry.key == key) { - entry.score = next_score_; - IncrementScore(); - if (dest) - *dest = entry.value; - return true; - } - } - - return false; -} - -template <typename TKey, typename TValue> -bool LruCache<TKey, TValue>::TryTake(const TKey& key, TValue* dest) { - for (size_t i = 0; i < entries_.size(); ++i) { - if (entries_[i].key == key) { - if (dest) - *dest = entries_[i].value; - entries_.erase(entries_.begin() + i); - return true; - } - } - - return false; -} - -template <typename TKey, typename TValue> -void LruCache<TKey, TValue>::Insert(const TKey& key, const TValue& value) { - if ((int)entries_.size() >= max_entries_) - entries_.erase(std::min_element(entries_.begin(), entries_.end())); - - Entry entry; - entry.score = next_score_; - IncrementScore(); - entry.key = key; - entry.value = value; - entries_.push_back(entry); -} - -template <typename TKey, typename TValue> -template <typename TFunc> -void LruCache<TKey, TValue>::IterateValues(TFunc func) { - for (Entry& entry : entries_) { - if (!func(entry.value)) - break; - } -} - -template <typename TKey, typename TValue> -void LruCache<TKey, TValue>::IncrementScore() { - // Overflow. - if (++next_score_ == 0) { - std::sort(entries_.begin(), entries_.end()); - for (Entry& entry : entries_) - entry.score = next_score_++; - } -} - -template <typename TKey, typename TValue> -void LruCache<TKey, TValue>::Clear(void) { - entries_.clear(); - next_score_ = 0; -} |