chromium/third_party/leveldatabase/src/util/cache.cc

// 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.

#include "leveldb/cache.h"

#include <cassert>
#include <cstdio>
#include <cstdlib>

#include "port/port.h"
#include "port/thread_annotations.h"
#include "util/hash.h"
#include "util/mutexlock.h"

namespace leveldb {

Cache::~Cache() { … }

namespace {

// LRU cache implementation
//
// Cache entries have an "in_cache" boolean indicating whether the cache has a
// reference on the entry.  The only ways that this can become false without the
// entry being passed to its "deleter" are via Erase(), via Insert() when
// an element with a duplicate key is inserted, or on destruction of the cache.
//
// The cache keeps two linked lists of items in the cache.  All items in the
// cache are in one list or the other, and never both.  Items still referenced
// by clients but erased from the cache are in neither list.  The lists are:
// - in-use:  contains the items currently referenced by clients, in no
//   particular order.  (This list is used for invariant checking.  If we
//   removed the check, elements that would otherwise be on this list could be
//   left as disconnected singleton lists.)
// - LRU:  contains the items not currently referenced by clients, in LRU order
// Elements are moved between these lists by the Ref() and Unref() methods,
// when they detect an element in the cache acquiring or losing its only
// external reference.

// An entry is a variable length heap-allocated structure.  Entries
// are kept in a circular doubly linked list ordered by access time.
struct LRUHandle { … };

// We provide our own simple hash table since it removes a whole bunch
// of porting hacks and is also faster than some of the built-in hash
// table implementations in some of the compiler/runtime combinations
// we have tested.  E.g., readrandom speeds up by ~5% over the g++
// 4.4.3's builtin hashtable.
class HandleTable { … };

// A single shard of sharded cache.
class LRUCache { … };

LRUCache::LRUCache() : … { … }

LRUCache::~LRUCache() { … }

void LRUCache::Ref(LRUHandle* e) { … }

void LRUCache::Unref(LRUHandle* e) { … }

void LRUCache::LRU_Remove(LRUHandle* e) { … }

void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) { … }

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) { … }

void LRUCache::Release(Cache::Handle* handle) { … }

Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
                                size_t charge,
                                void (*deleter)(const Slice& key,
                                                void* value)) { … }

// If e != nullptr, finish removing *e from the cache; it has already been
// removed from the hash table.  Return whether e != nullptr.
bool LRUCache::FinishErase(LRUHandle* e) { … }

void LRUCache::Erase(const Slice& key, uint32_t hash) { … }

void LRUCache::Prune() { … }

static const int kNumShardBits = …;
static const int kNumShards = …;

class ShardedLRUCache : public Cache { … };

}  // end anonymous namespace

Cache* NewLRUCache(size_t capacity) { … }

}  // namespace leveldb