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. 返回的句柄
  std::memcpy(e->key_data, key.data(), key.size());
  if (capacity_ > 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.)
     // capacity_==0 时表示关闭缓存，不进行任何缓存
    // next is read by key() in an assert, so it must be initialized
    // next 由断言中的 key() 读取，因此必须对其进行初始化
    e->next = nullptr;
  }
  while (usage_ > capacity_ && lru_.next != &lru_) {
  //如果容量超过了设计的容量，并且冷链表中有内容，则从冷链表中删除所有元素
    LRUHandle* old = lru_.next;
    assert(old->refs == 1);
    bool erased = FinishErase(table_.Remove(old->key(), old->hash));
    if (!erased) { // to avoid unused variable when compiled NDEBUG
      assert(erased);
    }
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

if (capacity_ > 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.)
    // 不要缓存。 （容量_==0 受支持并关闭缓存。）
    // next is read by key() in an assert, so it must be initialized
    // next 由断言中的 key() 读取，因此必须对其进行初始化
    e->next = nullptr;
  }

// If e != nullptr, finish removing *e from the cache; it has already been removed from the hash table. Return whether e != nullptr.
// 如果e != nullptr，从缓存中删除*e；表示它已经被从哈希表中删除。同时返回e是否 !=nullptr。
bool LRUCache::FinishErase(LRUHandle* e) {
  if (e != nullptr) {
    assert(e->in_cache);
    LRU_Remove(e);
    e->in_cache  = false;
    usage_ -= e->charge;
    // 状态改变
    Unref(e);
  }
  return e != nullptr;
}

// 机翻自作者的注释，对于理解作者设计比较关键，翻得一般。建议对比原文多读几遍
// LRU缓存实现
//
// 缓存条目有一个“in_cache”布尔值，指示缓存是否有
// 对条目的引用。如果没有传递给其“删除器”的条目是通过 Erase()，
// 通过 Insert() 时， 插入具有重复键的元素，或在缓存销毁时。
//
// 缓存在缓存中保存两个项目的链表。中的所有项目
// 缓存在一个列表或另一个列表中，并且永远不会同时存在。仍被引用的项目
// 由客户端但从缓存中删除的不在列表中。名单是：
// - in-use: 包含客户端当前引用的项目，没有
// 特定顺序。 （这个列表用于不变检查。如果我们
// 删除检查，否则该列表中的元素可能是
// 保留为断开连接的单例列表。）
// - LRU：包含客户端当前未引用的项目，按 LRU 顺序
// 元素通过 Ref() 和 Unref() 方法在这些列表之间移动，
// 当他们检测到缓存中的元素获取或丢失它的唯一
// 外部参考。
// 一个 Entry 是一个可变长度的堆分配结构。 条目保存在按访问时间排序的循环双向链表中。
// 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); // 释放 key value 空间用户回调
  LRUHandle* next_hash; // 用于 Hashtable 处理链表冲突
  LRUHandle* next; // 双向链表维护LRU顺序
  LRUHandle* prev;
  size_t charge; // TODO(opt): Only allow uint32_t?
  size_t key_length;
  bool in_cache; // 该 handle 是否在 cache table 中
  uint32_t refs; // 该 handle 被引用次数
  uint32_t hash; // key 的 hash值，
  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.
  // 仅当 LRU 句柄是空列表的列表头时，next 才等于此值。此时列表头永远不会有有意义的键。
  assert(next != this);
  return Slice(key_data, key_length);
}

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++) {
      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;
  }
  // 全局唯一自增ID
  uint64_t NewId() override {
    MutexLock l(&id_mutex_);
    return ++(last_id_);
  }
  void Prune() override {
    for (int s = 0; s < kNumShards; s++) {
      shard_[s].Prune();
    }
  }
  size_t TotalCharge() const override {
  size_t total = 0;
  for (int s = 0; s < kNumShards; s++) {
    total += shard_[s].TotalCharge();
  }
  return total;
  }
};

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