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#include "leveldb/slice.h"
23
24namespace leveldb {
25
26class Cache;
27
28// Create a new cache with a fixed size capacity.  This implementation
29// of Cache uses a least-recently-used eviction policy.
30extern Cache* NewLRUCache(size_t capacity);
31
32class Cache {
33 public:
34  Cache() { }
35
36  // Destroys all existing entries by calling the "deleter"
37  // function that was passed to the constructor.
38  virtual ~Cache();
39
40  // Opaque handle to an entry stored in the cache.
41  struct Handle { };
42
43  // Insert a mapping from key->value into the cache and assign it
44  // the specified charge against the total cache capacity.
45  //
46  // Returns a handle that corresponds to the mapping.  The caller
47  // must call this->Release(handle) when the returned mapping is no
48  // longer needed.
49  //
50  // When the inserted entry is no longer needed, the key and
51  // value will be passed to "deleter".
52  virtual Handle* Insert(const Slice& key, void* value, size_t charge,
53                         void (*deleter)(const Slice& key, void* value)) = 0;
54
55  // If the cache has no mapping for "key", returns NULL.
56  //
57  // Else return a handle that corresponds to the mapping.  The caller
58  // must call this->Release(handle) when the returned mapping is no
59  // longer needed.
60  virtual Handle* Lookup(const Slice& key) = 0;
61
62  // Release a mapping returned by a previous Lookup().
63  // REQUIRES: handle must not have been released yet.
64  // REQUIRES: handle must have been returned by a method on *this.
65  virtual void Release(Handle* handle) = 0;
66
67  // Return the value encapsulated in a handle returned by a
68  // successful Lookup().
69  // REQUIRES: handle must not have been released yet.
70  // REQUIRES: handle must have been returned by a method on *this.
71  virtual void* Value(Handle* handle) = 0;
72
73  // If the cache contains entry for key, erase it.  Note that the
74  // underlying entry will be kept around until all existing handles
75  // to it have been released.
76  virtual void Erase(const Slice& key) = 0;
77
78  // Return a new numeric id.  May be used by multiple clients who are
79  // sharing the same cache to partition the key space.  Typically the
80  // client will allocate a new id at startup and prepend the id to
81  // its cache keys.
82  virtual uint64_t NewId() = 0;
83
84 private:
85  void LRU_Remove(Handle* e);
86  void LRU_Append(Handle* e);
87  void Unref(Handle* e);
88
89  struct Rep;
90  Rep* rep_;
91
92  // No copying allowed
93  Cache(const Cache&);
94  void operator=(const Cache&);
95};
96
97}  // namespace leveldb
98
99#endif  // STORAGE_LEVELDB_UTIL_CACHE_H_
100