| // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. See the AUTHORS file for names of contributors. |
| |
| #if defined(LEVELDB_PLATFORM_POSIX) || defined(LEVELDB_PLATFORM_ANDROID) |
| #include <unordered_set> |
| #elif defined(LEVELDB_PLATFORM_OSX) |
| #include <ext/hash_set> |
| #elif defined(LEVELDB_PLATFORM_CHROMIUM) |
| #include "base/hash_tables.h" |
| #else |
| #include <hash_set> // TODO(sanjay): Switch to unordered_set when possible. |
| #endif |
| |
| #include <assert.h> |
| |
| #include "leveldb/cache.h" |
| #include "port/port.h" |
| #include "util/hash.h" |
| #include "util/mutexlock.h" |
| |
| namespace leveldb { |
| |
| Cache::~Cache() { |
| } |
| |
| namespace { |
| |
| // LRU cache implementation |
| |
| // An entry is a variable length heap-allocated structure. Entries |
| // are kept in a circular doubly linked list ordered by access time. |
| struct LRUHandle { |
| void* value; |
| void (*deleter)(const Slice&, void* value); |
| LRUHandle* next; |
| LRUHandle* prev; |
| size_t charge; // TODO(opt): Only allow uint32_t? |
| size_t key_length; |
| size_t refs; // TODO(opt): Pack with "key_length"? |
| char key_data[1]; // Beginning of key |
| |
| Slice key() const { |
| // For cheaper lookups, we allow a temporary Handle object |
| // to store a pointer to a key in "value". |
| if (next == this) { |
| return *(reinterpret_cast<Slice*>(value)); |
| } else { |
| return Slice(key_data, key_length); |
| } |
| } |
| }; |
| |
| // Pick a platform specific hash_set instantiation |
| #if defined(LEVELDB_PLATFORM_CHROMIUM) && defined(OS_WIN) |
| // Microsoft's hash_set deviates from the standard. See |
| // http://msdn.microsoft.com/en-us/library/1t4xas78(v=vs.80).aspx |
| // for details. Basically the 2 param () operator is a less than and |
| // the 1 param () operator is a hash function. |
| struct HandleHashCompare : public stdext::hash_compare<LRUHandle*> { |
| size_t operator() (LRUHandle* h) const { |
| Slice k = h->key(); |
| return Hash(k.data(), k.size(), 0); |
| } |
| bool operator() (LRUHandle* a, LRUHandle* b) const { |
| return a->key().compare(b->key()) < 0; |
| } |
| }; |
| typedef base::hash_set<LRUHandle*, HandleHashCompare> HandleTable; |
| #else |
| struct HandleHash { |
| inline size_t operator()(LRUHandle* h) const { |
| Slice k = h->key(); |
| return Hash(k.data(), k.size(), 0); |
| } |
| }; |
| |
| struct HandleEq { |
| inline bool operator()(LRUHandle* a, LRUHandle* b) const { |
| return a->key() == b->key(); |
| } |
| }; |
| # if defined(LEVELDB_PLATFORM_CHROMIUM) |
| typedef base::hash_set<LRUHandle*, HandleHash, HandleEq> HandleTable; |
| # elif defined(LEVELDB_PLATFORM_POSIX) || defined(LEVELDB_PLATFORM_ANDROID) |
| typedef std::unordered_set<LRUHandle*, HandleHash, HandleEq> HandleTable; |
| # else |
| typedef __gnu_cxx::hash_set<LRUHandle*, HandleHash, HandleEq> HandleTable; |
| # endif |
| #endif |
| |
| class LRUCache : public Cache { |
| public: |
| explicit LRUCache(size_t capacity); |
| virtual ~LRUCache(); |
| |
| virtual Handle* Insert(const Slice& key, void* value, size_t charge, |
| void (*deleter)(const Slice& key, void* value)); |
| virtual Handle* Lookup(const Slice& key); |
| virtual void Release(Handle* handle); |
| virtual void* Value(Handle* handle); |
| virtual void Erase(const Slice& key); |
| virtual uint64_t NewId(); |
| |
| private: |
| void LRU_Remove(LRUHandle* e); |
| void LRU_Append(LRUHandle* e); |
| void Unref(LRUHandle* e); |
| |
| // Constructor parameters |
| const size_t capacity_; |
| |
| // mutex_ protects the following state. |
| port::Mutex mutex_; |
| size_t usage_; |
| uint64_t last_id_; |
| |
| // Dummy head of LRU list. |
| // lru.prev is newest entry, lru.next is oldest entry. |
| LRUHandle lru_; |
| |
| HandleTable table_; |
| }; |
| |
| LRUCache::LRUCache(size_t capacity) |
| : capacity_(capacity), |
| usage_(0), |
| last_id_(0) { |
| // Make empty circular linked list |
| lru_.next = &lru_; |
| lru_.prev = &lru_; |
| } |
| |
| LRUCache::~LRUCache() { |
| table_.clear(); |
| for (LRUHandle* e = lru_.next; e != &lru_; ) { |
| LRUHandle* next = e->next; |
| assert(e->refs == 1); // Error if caller has an unreleased handle |
| Unref(e); |
| e = next; |
| } |
| } |
| |
| void LRUCache::Unref(LRUHandle* e) { |
| assert(e->refs > 0); |
| e->refs--; |
| if (e->refs <= 0) { |
| usage_ -= e->charge; |
| (*e->deleter)(e->key(), e->value); |
| free(e); |
| } |
| } |
| |
| void LRUCache::LRU_Remove(LRUHandle* e) { |
| e->next->prev = e->prev; |
| e->prev->next = e->next; |
| } |
| |
| void LRUCache::LRU_Append(LRUHandle* e) { |
| // Make "e" newest entry by inserting just before lru_ |
| e->next = &lru_; |
| e->prev = lru_.prev; |
| e->prev->next = e; |
| e->next->prev = e; |
| } |
| |
| Cache::Handle* LRUCache::Lookup(const Slice& key) { |
| MutexLock l(&mutex_); |
| |
| LRUHandle dummy; |
| dummy.next = &dummy; |
| dummy.value = const_cast<Slice*>(&key); |
| HandleTable::iterator iter = table_.find(&dummy); |
| if (iter == table_.end()) { |
| return NULL; |
| } else { |
| LRUHandle* e = const_cast<LRUHandle*>(*iter); |
| e->refs++; |
| LRU_Remove(e); |
| LRU_Append(e); |
| return reinterpret_cast<Handle*>(e); |
| } |
| } |
| |
| void* LRUCache::Value(Handle* handle) { |
| return reinterpret_cast<LRUHandle*>(handle)->value; |
| } |
| |
| void LRUCache::Release(Handle* handle) { |
| MutexLock l(&mutex_); |
| Unref(reinterpret_cast<LRUHandle*>(handle)); |
| } |
| |
| Cache::Handle* LRUCache::Insert(const Slice& key, void* value, size_t charge, |
| void (*deleter)(const Slice& key, void* value)) { |
| MutexLock l(&mutex_); |
| |
| LRUHandle* e = reinterpret_cast<LRUHandle*>( |
| malloc(sizeof(LRUHandle)-1 + key.size())); |
| e->value = value; |
| e->deleter = deleter; |
| e->charge = charge; |
| e->key_length = key.size(); |
| e->refs = 2; // One from LRUCache, one for the returned handle |
| memcpy(e->key_data, key.data(), key.size()); |
| LRU_Append(e); |
| usage_ += charge; |
| |
| std::pair<HandleTable::iterator,bool> p = table_.insert(e); |
| if (!p.second) { |
| // Kill existing entry |
| LRUHandle* old = const_cast<LRUHandle*>(*(p.first)); |
| LRU_Remove(old); |
| table_.erase(p.first); |
| table_.insert(e); |
| Unref(old); |
| } |
| |
| while (usage_ > capacity_ && lru_.next != &lru_) { |
| LRUHandle* old = lru_.next; |
| LRU_Remove(old); |
| table_.erase(old); |
| Unref(old); |
| } |
| |
| return reinterpret_cast<Handle*>(e); |
| } |
| |
| void LRUCache::Erase(const Slice& key) { |
| MutexLock l(&mutex_); |
| |
| LRUHandle dummy; |
| dummy.next = &dummy; |
| dummy.value = const_cast<Slice*>(&key); |
| HandleTable::iterator iter = table_.find(&dummy); |
| if (iter != table_.end()) { |
| LRUHandle* e = const_cast<LRUHandle*>(*iter); |
| LRU_Remove(e); |
| table_.erase(iter); |
| Unref(e); |
| } |
| } |
| |
| uint64_t LRUCache::NewId() { |
| MutexLock l(&mutex_); |
| return ++(last_id_); |
| } |
| |
| } // end anonymous namespace |
| |
| Cache* NewLRUCache(size_t capacity) { |
| return new LRUCache(capacity); |
| } |
| |
| } |