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 <stdint.h>
 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.
 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_