1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// A Cache is an interface that maps keys to values. It has internal 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// synchronization and may be safely accessed concurrently from 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// multiple threads. It may automatically evict entries to make room 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// for new entries. Values have a specified charge against the cache 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// capacity. For example, a cache where the values are variable 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// length strings, may use the length of the string as the charge for 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// the string. 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// A builtin cache implementation with a least-recently-used eviction 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// policy is provided. Clients may use their own implementations if 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// they want something more sophisticated (like scan-resistance, a 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// custom eviction policy, variable cache sizing, etc.) 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#ifndef STORAGE_LEVELDB_INCLUDE_CACHE_H_ 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#define STORAGE_LEVELDB_INCLUDE_CACHE_H_ 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <stdint.h> 221ca60b12c68a71aac695b15e329b2a76a63cbb0ajorlow@chromium.org#include "leveldb/slice.h" 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Cache; 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Create a new cache with a fixed size capacity. This implementation 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// of Cache uses a least-recently-used eviction policy. 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgextern Cache* NewLRUCache(size_t capacity); 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Cache { 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache() { } 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Destroys all existing entries by calling the "deleter" 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // function that was passed to the constructor. 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual ~Cache(); 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Opaque handle to an entry stored in the cache. 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org struct Handle { }; 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Insert a mapping from key->value into the cache and assign it 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // the specified charge against the total cache capacity. 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Returns a handle that corresponds to the mapping. The caller 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // must call this->Release(handle) when the returned mapping is no 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // longer needed. 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // When the inserted entry is no longer needed, the key and 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // value will be passed to "deleter". 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Handle* Insert(const Slice& key, void* value, size_t charge, 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void (*deleter)(const Slice& key, void* value)) = 0; 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // If the cache has no mapping for "key", returns NULL. 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Else return a handle that corresponds to the mapping. The caller 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // must call this->Release(handle) when the returned mapping is no 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // longer needed. 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Handle* Lookup(const Slice& key) = 0; 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Release a mapping returned by a previous Lookup(). 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: handle must not have been released yet. 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: handle must have been returned by a method on *this. 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Release(Handle* handle) = 0; 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return the value encapsulated in a handle returned by a 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // successful Lookup(). 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: handle must not have been released yet. 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // REQUIRES: handle must have been returned by a method on *this. 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void* Value(Handle* handle) = 0; 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // If the cache contains entry for key, erase it. Note that the 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // underlying entry will be kept around until all existing handles 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // to it have been released. 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Erase(const Slice& key) = 0; 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Return a new numeric id. May be used by multiple clients who are 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // sharing the same cache to partition the key space. Typically the 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // client will allocate a new id at startup and prepend the id to 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // its cache keys. 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual uint64_t NewId() = 0; 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void LRU_Remove(Handle* e); 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void LRU_Append(Handle* e); 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Unref(Handle* e); 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org struct Rep; 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Rep* rep_; 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No copying allowed 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache(const Cache&); 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void operator=(const Cache&); 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 9745b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#endif // STORAGE_LEVELDB_UTIL_CACHE_H_ 100