libutils/include/utils/LruCache.h - third_party/android/platform/system/core - Git at Google

 /*
  * Copyright (C) 2012 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #ifndef ANDROID_UTILS_LRU_CACHE_H
 #define ANDROID_UTILS_LRU_CACHE_H

 #include <memory>
 #include <unordered_set>

 #include "utils/TypeHelpers.h"  // hash_t

 namespace android {

 /**
  * GenerationCache callback used when an item is removed
  */
 template<typename EntryKey, typename EntryValue>
 class OnEntryRemoved {
 public:
     virtual ~OnEntryRemoved() { };
     virtual void operator()(EntryKey& key, EntryValue& value) = 0;
 }; // class OnEntryRemoved

 template <typename TKey, typename TValue>
 class LruCache {
 public:
     explicit LruCache(uint32_t maxCapacity);
     virtual ~LruCache();

     enum Capacity {
         kUnlimitedCapacity,
     };

     void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
     size_t size() const;
     const TValue& get(const TKey& key);
     bool put(const TKey& key, const TValue& value);
     bool remove(const TKey& key);
     bool removeOldest();
     void clear();
     const TValue& peekOldestValue();

 private:
     LruCache(const LruCache& that);  // disallow copy constructor

     // Super class so that we can have entries having only a key reference, for searches.
     class KeyedEntry {
     public:
         virtual const TKey& getKey() const = 0;
         // Make sure the right destructor is executed so that keys and values are deleted.
         virtual ~KeyedEntry() {}
     };

     class Entry final : public KeyedEntry {
     public:
         TKey key;
         TValue value;
         Entry* parent;
         Entry* child;

         Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(nullptr), child(nullptr) {
         }
         const TKey& getKey() const final { return key; }
     };

     class EntryForSearch : public KeyedEntry {
     public:
         const TKey& key;
         EntryForSearch(const TKey& key_) : key(key_) {
         }
         const TKey& getKey() const final { return key; }
     };

     struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> {
         size_t operator() (const KeyedEntry* entry) const {
             return hash_type(entry->getKey());
         };
     };

     struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> {
         bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const {
             return lhs->getKey() == rhs->getKey();
         };
     };

     // All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries
     // that have only a key reference, for searching.
     typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;

     void attachToCache(Entry& entry);
     void detachFromCache(Entry& entry);

     typename LruCacheSet::iterator findByKey(const TKey& key) {
         EntryForSearch entryForSearch(key);
         typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
         return result;
     }

     std::unique_ptr<LruCacheSet> mSet;
     OnEntryRemoved<TKey, TValue>* mListener;
     Entry* mOldest;
     Entry* mYoungest;
     uint32_t mMaxCapacity;
     TValue mNullValue;

 public:
     // To be used like:
     // while (it.next()) {
     //   it.value(); it.key();
     // }
     class Iterator {
     public:
         Iterator(const LruCache<TKey, TValue>& cache):
                 mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
         }

         bool next() {
             if (mIterator == mCache.mSet->end()) {
                 return false;
             }
             if (!mBeginReturned) {
                 // mIterator has been initialized to the beginning and
                 // hasn't been returned. Do not advance:
                 mBeginReturned = true;
             } else {
                 std::advance(mIterator, 1);
             }
             bool ret = (mIterator != mCache.mSet->end());
             return ret;
         }

         const TValue& value() const {
             // All the elements in the set are of type Entry. See comment in the definition
             // of LruCacheSet above.
             return reinterpret_cast<Entry *>(*mIterator)->value;
         }

         const TKey& key() const {
             return (*mIterator)->getKey();
         }
     private:
         const LruCache<TKey, TValue>& mCache;
         typename LruCacheSet::iterator mIterator;
         bool mBeginReturned;
     };
 };

 // Implementation is here, because it's fully templated
 template <typename TKey, typename TValue>
 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
     : mSet(new LruCacheSet())
     , mListener(nullptr)
     , mOldest(nullptr)
     , mYoungest(nullptr)
     , mMaxCapacity(maxCapacity)
     , mNullValue(0) {
     mSet->max_load_factor(1.0);
 };

 template <typename TKey, typename TValue>
 LruCache<TKey, TValue>::~LruCache() {
     // Need to delete created entries.
     clear();
 };

 template<typename K, typename V>
 void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
     mListener = listener;
 }

 template <typename TKey, typename TValue>
 size_t LruCache<TKey, TValue>::size() const {
     return mSet->size();
 }

 template <typename TKey, typename TValue>
 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
     typename LruCacheSet::const_iterator find_result = findByKey(key);
     if (find_result == mSet->end()) {
         return mNullValue;
     }
     // All the elements in the set are of type Entry. See comment in the definition
     // of LruCacheSet above.
     Entry *entry = reinterpret_cast<Entry*>(*find_result);
     detachFromCache(*entry);
     attachToCache(*entry);
     return entry->value;
 }

 template <typename TKey, typename TValue>
 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
     if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
         removeOldest();
     }

     if (findByKey(key) != mSet->end()) {
         return false;
     }

     Entry* newEntry = new Entry(key, value);
     mSet->insert(newEntry);
     attachToCache(*newEntry);
     return true;
 }

 template <typename TKey, typename TValue>
 bool LruCache<TKey, TValue>::remove(const TKey& key) {
     typename LruCacheSet::const_iterator find_result = findByKey(key);
     if (find_result == mSet->end()) {
         return false;
     }
     // All the elements in the set are of type Entry. See comment in the definition
     // of LruCacheSet above.
     Entry* entry = reinterpret_cast<Entry*>(*find_result);
     mSet->erase(entry);
     if (mListener) {
         (*mListener)(entry->key, entry->value);
     }
     detachFromCache(*entry);
     delete entry;
     return true;
 }

 template <typename TKey, typename TValue>
 bool LruCache<TKey, TValue>::removeOldest() {
     if (mOldest != nullptr) {
         return remove(mOldest->key);
         // TODO: should probably abort if false
     }
     return false;
 }

 template <typename TKey, typename TValue>
 const TValue& LruCache<TKey, TValue>::peekOldestValue() {
     if (mOldest) {
         return mOldest->value;
     }
     return mNullValue;
 }

 template <typename TKey, typename TValue>
 void LruCache<TKey, TValue>::clear() {
     if (mListener) {
         for (Entry* p = mOldest; p != nullptr; p = p->child) {
             (*mListener)(p->key, p->value);
         }
     }
     mYoungest = nullptr;
     mOldest = nullptr;
     for (auto entry : *mSet.get()) {
         delete entry;
     }
     mSet->clear();
 }

 template <typename TKey, typename TValue>
 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
     if (mYoungest == nullptr) {
         mYoungest = mOldest = &entry;
     } else {
         entry.parent = mYoungest;
         mYoungest->child = &entry;
         mYoungest = &entry;
     }
 }

 template <typename TKey, typename TValue>
 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
     if (entry.parent != nullptr) {
         entry.parent->child = entry.child;
     } else {
         mOldest = entry.child;
     }
     if (entry.child != nullptr) {
         entry.child->parent = entry.parent;
     } else {
         mYoungest = entry.parent;
     }

     entry.parent = nullptr;
     entry.child = nullptr;
 }

 }
 #endif // ANDROID_UTILS_LRU_CACHE_H
	/*
	* Copyright (C) 2012 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#ifndef ANDROID_UTILS_LRU_CACHE_H
	#define ANDROID_UTILS_LRU_CACHE_H

	#include <memory>
	#include <unordered_set>

	#include "utils/TypeHelpers.h" // hash_t

	namespace android {

	/**
	* GenerationCache callback used when an item is removed
	*/
	template<typename EntryKey, typename EntryValue>
	class OnEntryRemoved {
	public:
	virtual ~OnEntryRemoved() { };
	virtual void operator()(EntryKey& key, EntryValue& value) = 0;
	}; // class OnEntryRemoved

	template <typename TKey, typename TValue>
	class LruCache {
	public:
	explicit LruCache(uint32_t maxCapacity);
	virtual ~LruCache();

	enum Capacity {
	kUnlimitedCapacity,
	};

	void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
	size_t size() const;
	const TValue& get(const TKey& key);
	bool put(const TKey& key, const TValue& value);
	bool remove(const TKey& key);
	bool removeOldest();
	void clear();
	const TValue& peekOldestValue();

	private:
	LruCache(const LruCache& that); // disallow copy constructor

	// Super class so that we can have entries having only a key reference, for searches.
	class KeyedEntry {
	public:
	virtual const TKey& getKey() const = 0;
	// Make sure the right destructor is executed so that keys and values are deleted.
	virtual ~KeyedEntry() {}
	};

	class Entry final : public KeyedEntry {
	public:
	TKey key;
	TValue value;
	Entry* parent;
	Entry* child;

	Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(nullptr), child(nullptr) {
	}
	const TKey& getKey() const final { return key; }
	};

	class EntryForSearch : public KeyedEntry {
	public:
	const TKey& key;
	EntryForSearch(const TKey& key_) : key(key_) {
	}
	const TKey& getKey() const final { return key; }
	};

	struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> {
	size_t operator() (const KeyedEntry* entry) const {
	return hash_type(entry->getKey());
	};
	};

	struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> {
	bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const {
	return lhs->getKey() == rhs->getKey();
	};
	};

	// All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries
	// that have only a key reference, for searching.
	typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;

	void attachToCache(Entry& entry);
	void detachFromCache(Entry& entry);

	typename LruCacheSet::iterator findByKey(const TKey& key) {
	EntryForSearch entryForSearch(key);
	typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
	return result;
	}

	std::unique_ptr<LruCacheSet> mSet;
	OnEntryRemoved<TKey, TValue>* mListener;
	Entry* mOldest;
	Entry* mYoungest;
	uint32_t mMaxCapacity;
	TValue mNullValue;

	public:
	// To be used like:
	// while (it.next()) {
	// it.value(); it.key();
	// }
	class Iterator {
	public:
	Iterator(const LruCache<TKey, TValue>& cache):
	mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
	}

	bool next() {
	if (mIterator == mCache.mSet->end()) {
	return false;
	}
	if (!mBeginReturned) {
	// mIterator has been initialized to the beginning and
	// hasn't been returned. Do not advance:
	mBeginReturned = true;
	} else {
	std::advance(mIterator, 1);
	}
	bool ret = (mIterator != mCache.mSet->end());
	return ret;
	}

	const TValue& value() const {
	// All the elements in the set are of type Entry. See comment in the definition
	// of LruCacheSet above.
	return reinterpret_cast<Entry >(mIterator)->value;
	}

	const TKey& key() const {
	return (*mIterator)->getKey();
	}
	private:
	const LruCache<TKey, TValue>& mCache;
	typename LruCacheSet::iterator mIterator;
	bool mBeginReturned;
	};
	};

	// Implementation is here, because it's fully templated
	template <typename TKey, typename TValue>
	LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
	: mSet(new LruCacheSet())
	, mListener(nullptr)
	, mOldest(nullptr)
	, mYoungest(nullptr)
	, mMaxCapacity(maxCapacity)
	, mNullValue(0) {
	mSet->max_load_factor(1.0);
	};

	template <typename TKey, typename TValue>
	LruCache<TKey, TValue>::~LruCache() {
	// Need to delete created entries.
	clear();
	};

	template<typename K, typename V>
	void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
	mListener = listener;
	}

	template <typename TKey, typename TValue>
	size_t LruCache<TKey, TValue>::size() const {
	return mSet->size();
	}

	template <typename TKey, typename TValue>
	const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
	typename LruCacheSet::const_iterator find_result = findByKey(key);
	if (find_result == mSet->end()) {
	return mNullValue;
	}
	// All the elements in the set are of type Entry. See comment in the definition
	// of LruCacheSet above.
	Entry entry = reinterpret_cast<Entry>(*find_result);
	detachFromCache(*entry);
	attachToCache(*entry);
	return entry->value;
	}

	template <typename TKey, typename TValue>
	bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
	if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
	removeOldest();
	}

	if (findByKey(key) != mSet->end()) {
	return false;
	}

	Entry* newEntry = new Entry(key, value);
	mSet->insert(newEntry);
	attachToCache(*newEntry);
	return true;
	}

	template <typename TKey, typename TValue>
	bool LruCache<TKey, TValue>::remove(const TKey& key) {
	typename LruCacheSet::const_iterator find_result = findByKey(key);
	if (find_result == mSet->end()) {
	return false;
	}
	// All the elements in the set are of type Entry. See comment in the definition
	// of LruCacheSet above.
	Entry* entry = reinterpret_cast<Entry>(find_result);
	mSet->erase(entry);
	if (mListener) {
	(*mListener)(entry->key, entry->value);
	}
	detachFromCache(*entry);
	delete entry;
	return true;
	}

	template <typename TKey, typename TValue>
	bool LruCache<TKey, TValue>::removeOldest() {
	if (mOldest != nullptr) {
	return remove(mOldest->key);
	// TODO: should probably abort if false
	}
	return false;
	}

	template <typename TKey, typename TValue>
	const TValue& LruCache<TKey, TValue>::peekOldestValue() {
	if (mOldest) {
	return mOldest->value;
	}
	return mNullValue;
	}

	template <typename TKey, typename TValue>
	void LruCache<TKey, TValue>::clear() {
	if (mListener) {
	for (Entry* p = mOldest; p != nullptr; p = p->child) {
	(*mListener)(p->key, p->value);
	}
	}
	mYoungest = nullptr;
	mOldest = nullptr;
	for (auto entry : *mSet.get()) {
	delete entry;
	}
	mSet->clear();
	}

	template <typename TKey, typename TValue>
	void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
	if (mYoungest == nullptr) {
	mYoungest = mOldest = &entry;
	} else {
	entry.parent = mYoungest;
	mYoungest->child = &entry;
	mYoungest = &entry;
	}
	}

	template <typename TKey, typename TValue>
	void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
	if (entry.parent != nullptr) {
	entry.parent->child = entry.child;
	} else {
	mOldest = entry.child;
	}
	if (entry.child != nullptr) {
	entry.child->parent = entry.parent;
	} else {
	mYoungest = entry.parent;
	}

	entry.parent = nullptr;
	entry.child = nullptr;
	}

	}
	#endif // ANDROID_UTILS_LRU_CACHE_H