1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. See the AUTHORS file for names of contributors. 4 // 5 // A Cache is an interface that maps keys to values. It has internal 6 // synchronization and may be safely accessed concurrently from 7 // multiple threads. It may automatically evict entries to make room 8 // for new entries. Values have a specified charge against the cache 9 // capacity. For example, a cache where the values are variable 10 // length strings, may use the length of the string as the charge for 11 // the string. 12 // 13 // A builtin cache implementation with a least-recently-used eviction 14 // policy is provided. Clients may use their own implementations if 15 // they want something more sophisticated (like scan-resistance, a 16 // custom eviction policy, variable cache sizing, etc.) 17 18 #ifndef STORAGE_LEVELDB_INCLUDE_CACHE_H_ 19 #define STORAGE_LEVELDB_INCLUDE_CACHE_H_ 20 21 #include <cstdint> 22 23 #include "leveldb/export.h" 24 #include "leveldb/slice.h" 25 26 namespace leveldb { 27 28 class LEVELDB_EXPORT Cache; 29 30 // Create a new cache with a fixed size capacity. This implementation 31 // of Cache uses a least-recently-used eviction policy. 32 LEVELDB_EXPORT Cache* NewLRUCache(size_t capacity); 33 34 class LEVELDB_EXPORT Cache { 35 public: 36 Cache() = default; 37 38 Cache(const Cache&) = delete; 39 Cache& operator=(const Cache&) = delete; 40 41 // Destroys all existing entries by calling the "deleter" 42 // function that was passed to the constructor. 43 virtual ~Cache(); 44 45 // Opaque handle to an entry stored in the cache. 46 struct Handle {}; 47 48 // Insert a mapping from key->value into the cache and assign it 49 // the specified charge against the total cache capacity. 50 // 51 // Returns a handle that corresponds to the mapping. The caller 52 // must call this->Release(handle) when the returned mapping is no 53 // longer needed. 54 // 55 // When the inserted entry is no longer needed, the key and 56 // value will be passed to "deleter". 57 virtual Handle* Insert(const Slice& key, void* value, size_t charge, 58 void (*deleter)(const Slice& key, void* value)) = 0; 59 60 // If the cache has no mapping for "key", returns nullptr. 61 // 62 // Else return a handle that corresponds to the mapping. The caller 63 // must call this->Release(handle) when the returned mapping is no 64 // longer needed. 65 virtual Handle* Lookup(const Slice& key) = 0; 66 67 // Release a mapping returned by a previous Lookup(). 68 // REQUIRES: handle must not have been released yet. 69 // REQUIRES: handle must have been returned by a method on *this. 70 virtual void Release(Handle* handle) = 0; 71 72 // Return the value encapsulated in a handle returned by a 73 // successful Lookup(). 74 // REQUIRES: handle must not have been released yet. 75 // REQUIRES: handle must have been returned by a method on *this. 76 virtual void* Value(Handle* handle) = 0; 77 78 // If the cache contains entry for key, erase it. Note that the 79 // underlying entry will be kept around until all existing handles 80 // to it have been released. 81 virtual void Erase(const Slice& key) = 0; 82 83 // Return a new numeric id. May be used by multiple clients who are 84 // sharing the same cache to partition the key space. Typically the 85 // client will allocate a new id at startup and prepend the id to 86 // its cache keys. 87 virtual uint64_t NewId() = 0; 88 89 // Remove all cache entries that are not actively in use. Memory-constrained 90 // applications may wish to call this method to reduce memory usage. 91 // Default implementation of Prune() does nothing. Subclasses are strongly 92 // encouraged to override the default implementation. A future release of 93 // leveldb may change Prune() to a pure abstract method. Prune()94 virtual void Prune() {} 95 96 // Return an estimate of the combined charges of all elements stored in the 97 // cache. 98 virtual size_t TotalCharge() const = 0; 99 100 private: 101 void LRU_Remove(Handle* e); 102 void LRU_Append(Handle* e); 103 void Unref(Handle* e); 104 105 struct Rep; 106 Rep* rep_; 107 }; 108 109 } // namespace leveldb 110 111 #endif // STORAGE_LEVELDB_INCLUDE_CACHE_H_ 112