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

#include <stdio.h>

#include <stdlib.h>

#include "leveldb/cache.h"

#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 {

  void* value;

  void (*deleter)(const Slice&, void* value);

  LRUHandle* next_hash;

  LRUHandle* next;

  LRUHandle* prev;

  size_t charge;  // TODO(opt): Only allow uint32_t?

  size_t key_length;

  bool in_cache;     // Whether entry is in the cache.

  uint32_t refs;     // References, including cache reference, if present.

  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons

  char key_data[1];  // Beginning of key

  Slice key() const {

    // next_ is only equal to this if the LRU handle is the list head of an

    // empty list. List heads never have meaningful keys.

    assert(next != this);

  Branch (58:5): [True: 60, False: 0]

    return Slice(key_data, key_length);

  }

};

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

 public:

  HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }

  ~HandleTable() { delete[] list_; }

  LRUHandle* Lookup(const Slice& key, uint32_t hash) {

    return *FindPointer(key, hash);

  }

  LRUHandle* Insert(LRUHandle* h) {

    LRUHandle** ptr = FindPointer(h->key(), h->hash);

    LRUHandle* old = *ptr;

    h->next_hash = (old == nullptr ? nullptr : old->next_hash);

  Branch (81:21): [True: 24, False: 0]

    *ptr = h;

    if (old == nullptr) {

  Branch (83:9): [True: 24, False: 0]

      ++elems_;

      if (elems_ > length_) {

  Branch (85:11): [True: 0, False: 24]

        // Since each cache entry is fairly large, we aim for a small

        // average linked list length (<= 1).

        Resize();

      }

    }

    return old;

  }

  LRUHandle* Remove(const Slice& key, uint32_t hash) {

    LRUHandle** ptr = FindPointer(key, hash);

    LRUHandle* result = *ptr;

    if (result != nullptr) {

  Branch (97:9): [True: 0, False: 0]

      *ptr = result->next_hash;

      --elems_;

    }

    return result;

  }

 private:

  // The table consists of an array of buckets where each bucket is

  // a linked list of cache entries that hash into the bucket.

  uint32_t length_;

  uint32_t elems_;

  LRUHandle** list_;

  // Return a pointer to slot that points to a cache entry that

  // matches key/hash.  If there is no such cache entry, return a

  // pointer to the trailing slot in the corresponding linked list.

  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {

    LRUHandle** ptr = &list_[hash & (length_ - 1)];

    while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {

  Branch (116:12): [True: 12, False: 60]
  Branch (116:12): [True: 0, False: 72]
  Branch (116:32): [True: 0, False: 12]
  Branch (116:56): [True: 0, False: 12]

      ptr = &(*ptr)->next_hash;

    }

    return ptr;

  }

  void Resize() {

    uint32_t new_length = 4;

    while (new_length < elems_) {

  Branch (124:12): [True: 0, False: 1.06M]

      new_length *= 2;

    }

    LRUHandle** new_list = new LRUHandle*[new_length];

    memset(new_list, 0, sizeof(new_list[0]) * new_length);

    uint32_t count = 0;

    for (uint32_t i = 0; i < length_; i++) {

  Branch (130:26): [True: 0, False: 1.06M]

      LRUHandle* h = list_[i];

      while (h != nullptr) {

  Branch (132:14): [True: 0, False: 0]

        LRUHandle* next = h->next_hash;

        uint32_t hash = h->hash;

        LRUHandle** ptr = &new_list[hash & (new_length - 1)];

        h->next_hash = *ptr;

        *ptr = h;

        h = next;

        count++;

      }

    }

    assert(elems_ == count);

  Branch (142:5): [True: 1.06M, False: 0]

    delete[] list_;

    list_ = new_list;

    length_ = new_length;

  }

};

// A single shard of sharded cache.

class LRUCache {

 public:

  LRUCache();

  ~LRUCache();

  // Separate from constructor so caller can easily make an array of LRUCache

  void SetCapacity(size_t capacity) { capacity_ = capacity; }

  // Like Cache methods, but with an extra "hash" parameter.

  Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,

                        size_t charge,

                        void (*deleter)(const Slice& key, void* value));

  Cache::Handle* Lookup(const Slice& key, uint32_t hash);

  void Release(Cache::Handle* handle);

  void Erase(const Slice& key, uint32_t hash);

  void Prune();

  size_t TotalCharge() const {

    MutexLock l(&mutex_);

    return usage_;

  }

 private:

  void LRU_Remove(LRUHandle* e);

  void LRU_Append(LRUHandle* list, LRUHandle* e);

  void Ref(LRUHandle* e);

  void Unref(LRUHandle* e);

  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  // Initialized before use.

  size_t capacity_;

  // mutex_ protects the following state.

  mutable port::Mutex mutex_;

  size_t usage_ GUARDED_BY(mutex_);

  // Dummy head of LRU list.

  // lru.prev is newest entry, lru.next is oldest entry.

  // Entries have refs==1 and in_cache==true.

  LRUHandle lru_ GUARDED_BY(mutex_);

  // Dummy head of in-use list.

  // Entries are in use by clients, and have refs >= 2 and in_cache==true.

  LRUHandle in_use_ GUARDED_BY(mutex_);

  HandleTable table_ GUARDED_BY(mutex_);

};

LRUCache::LRUCache() : capacity_(0), usage_(0) {

  // Make empty circular linked lists.

  lru_.next = &lru_;

  lru_.prev = &lru_;

  in_use_.next = &in_use_;

  in_use_.prev = &in_use_;

}

LRUCache::~LRUCache() {

  assert(in_use_.next == &in_use_);  // Error if caller has an unreleased handle

  Branch (206:3): [True: 1.06M, False: 0]

  for (LRUHandle* e = lru_.next; e != &lru_;) {

  Branch (207:34): [True: 24, False: 1.06M]

    LRUHandle* next = e->next;

    assert(e->in_cache);

  Branch (209:5): [True: 24, False: 0]

    e->in_cache = false;

    assert(e->refs == 1);  // Invariant of lru_ list.

  Branch (211:5): [True: 24, False: 0]

    Unref(e);

    e = next;

  }

}

void LRUCache::Ref(LRUHandle* e) {

  if (e->refs == 1 && e->in_cache) {  // If on lru_ list, move to in_use_ list.

  Branch (218:7): [True: 12, False: 0]
  Branch (218:23): [True: 12, False: 0]

    LRU_Remove(e);

    LRU_Append(&in_use_, e);

  }

  e->refs++;

}

void LRUCache::Unref(LRUHandle* e) {

  assert(e->refs > 0);

  Branch (226:3): [True: 60, False: 0]

  e->refs--;

  if (e->refs == 0) {  // Deallocate.

  Branch (228:7): [True: 24, False: 36]

    assert(!e->in_cache);

  Branch (229:5): [True: 24, False: 0]

    (*e->deleter)(e->key(), e->value);

    free(e);

  } else if (e->in_cache && e->refs == 1) {

  Branch (232:14): [True: 36, False: 0]
  Branch (232:29): [True: 36, False: 0]

    // No longer in use; move to lru_ list.

    LRU_Remove(e);

    LRU_Append(&lru_, e);

  }

}

void LRUCache::LRU_Remove(LRUHandle* e) {

  e->next->prev = e->prev;

  e->prev->next = e->next;

}

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

  // Make "e" newest entry by inserting just before *list

  e->next = list;

  e->prev = list->prev;

  e->prev->next = e;

  e->next->prev = e;

}

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

  MutexLock l(&mutex_);

  LRUHandle* e = table_.Lookup(key, hash);

  if (e != nullptr) {

  Branch (255:7): [True: 12, False: 36]

    Ref(e);

  }

  return reinterpret_cast<Cache::Handle*>(e);

}

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

  MutexLock l(&mutex_);

  Unref(reinterpret_cast<LRUHandle*>(handle));

}

Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,

                                size_t charge,

                                void (*deleter)(const Slice& key,

                                                void* value)) {

  MutexLock l(&mutex_);

  LRUHandle* e =

      reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));

  e->value = value;

  e->deleter = deleter;

  e->charge = charge;

  e->key_length = key.size();

  e->hash = hash;

  e->in_cache = false;

  e->refs = 1;  // for the returned handle.

  memcpy(e->key_data, key.data(), key.size());

  if (capacity_ > 0) {

  Branch (283:7): [True: 24, False: 0]

    e->refs++;  // for the cache's reference.

    e->in_cache = true;

    LRU_Append(&in_use_, e);

    usage_ += charge;

    FinishErase(table_.Insert(e));

  } else {  // don't cache. (capacity_==0 is supported and turns off caching.)

    // next is read by key() in an assert, so it must be initialized

    e->next = nullptr;

  }

  while (usage_ > capacity_ && lru_.next != &lru_) {

  Branch (293:10): [True: 0, False: 24]
  Branch (293:32): [True: 0, False: 0]

    LRUHandle* old = lru_.next;

    assert(old->refs == 1);

  Branch (295:5): [True: 0, False: 0]

    bool erased = FinishErase(table_.Remove(old->key(), old->hash));

    if (!erased) {  // to avoid unused variable when compiled NDEBUG

  Branch (297:9): [True: 0, False: 0]

      assert(erased);

  Branch (298:7): [True: 0, False: 0]

    }

  }

  return reinterpret_cast<Cache::Handle*>(e);

}

// 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) {

  if (e != nullptr) {

  Branch (308:7): [True: 0, False: 24]

    assert(e->in_cache);

  Branch (309:5): [True: 0, False: 0]

    LRU_Remove(e);

    e->in_cache = false;

    usage_ -= e->charge;

    Unref(e);

  }

  return e != nullptr;

}

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

  MutexLock l(&mutex_);

  FinishErase(table_.Remove(key, hash));

}

void LRUCache::Prune() {

  MutexLock l(&mutex_);

  while (lru_.next != &lru_) {

  Branch (325:10): [True: 0, False: 0]

    LRUHandle* e = lru_.next;

    assert(e->refs == 1);

  Branch (327:5): [True: 0, False: 0]

    bool erased = FinishErase(table_.Remove(e->key(), e->hash));

    if (!erased) {  // to avoid unused variable when compiled NDEBUG

  Branch (329:9): [True: 0, False: 0]

      assert(erased);

  Branch (330:7): [True: 0, False: 0]

    }

  }

}

static const int kNumShardBits = 4;

static const int kNumShards = 1 << kNumShardBits;

class ShardedLRUCache : public Cache {

 private:

  LRUCache shard_[kNumShards];

  port::Mutex id_mutex_;

  uint64_t last_id_;

  static inline uint32_t HashSlice(const Slice& s) {

    return Hash(s.data(), s.size(), 0);

  }

  static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }

 public:

  explicit ShardedLRUCache(size_t capacity) : last_id_(0) {

    const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;

    for (int s = 0; s < kNumShards; s++) {

  Branch (353:21): [True: 1.06M, False: 66.5k]

      shard_[s].SetCapacity(per_shard);

    }

  }

  ~ShardedLRUCache() override {}

  Handle* Insert(const Slice& key, void* value, size_t charge,

                 void (*deleter)(const Slice& key, void* value)) override {

    const uint32_t hash = HashSlice(key);

    return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);

  }

  Handle* Lookup(const Slice& key) override {

    const uint32_t hash = HashSlice(key);

    return shard_[Shard(hash)].Lookup(key, hash);

  }

  void Release(Handle* handle) override {

    LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);

    shard_[Shard(h->hash)].Release(handle);

  }

  void Erase(const Slice& key) override {

    const uint32_t hash = HashSlice(key);

    shard_[Shard(hash)].Erase(key, hash);

  }

  void* Value(Handle* handle) override {

    return reinterpret_cast<LRUHandle*>(handle)->value;

  }

  uint64_t NewId() override {

    MutexLock l(&id_mutex_);

    return ++(last_id_);

  }

  void Prune() override {

    for (int s = 0; s < kNumShards; s++) {

  Branch (383:21): [True: 0, False: 0]

      shard_[s].Prune();

    }

  }

  size_t TotalCharge() const override {

    size_t total = 0;

    for (int s = 0; s < kNumShards; s++) {

  Branch (389:21): [True: 0, False: 0]

      total += shard_[s].TotalCharge();

    }

    return total;

  }

};

}  // end anonymous namespace

Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }

}  // namespace leveldb