// 插入一个键值对（key，value）到缓存（cache）中，
// 并从缓存总容量中减去该键值对所占额度（charge） 
// 
// 返回指向该键值对的句柄（handle），调用者在用完句柄后，
// 需要调用 this->Release(handle) 进行释放
//
// 在键值对不再被使用时，键值对会被传入的 deleter 参数
// 释放
virtual Handle* Insert(const Slice& key, void* value, size_t charge,
                       void (*deleter)(const Slice& key, void* value)) = 0;
// 如果缓存中没有相应键（key），则返回 nullptr
//
// 否则返回指向对应键值对的句柄（Handle）。调用者用完句柄后，
// 要记得调用 this->Release(handle) 进行释放
virtual Handle* Lookup(const Slice& key) = 0;
// 释放 Insert/Lookup 函数返回的句柄
// 要求：该句柄没有被释放过，即不能多次释放
// 要求：该句柄必须是同一个实例返回的
virtual void Release(Handle* handle) = 0;
// 获取句柄中的值，类型为 void*（表示任意用户自定义类型）
// 要求：该句柄没有被释放
// 要求：该句柄必须由同一实例所返回
virtual void* Value(Handle* handle) = 0;
// 如果缓存中包含给定键所指向的条目，则删除之。
// 需要注意的是，只有在所有持有该条目句柄都释放时，该条目所占空间才会真正被释放
virtual void Erase(const Slice& key) = 0;
// 返回一个自增的数值 id。当一个缓存实例由多个客户端共享时，
// 为了避免多个客户端的键冲突，每个客户端可能想获取一个独有
// 的 id，并将其作为键的前缀。类似于给每个客户端一个单独的命名空间。
virtual uint64_t NewId() = 0;
// 驱逐全部没有被使用的数据条目
// 内存吃紧型的应用可能想利用此接口定期释放内存。
// 基类中的 Prune 默认实现为空，但强烈建议所有子类自行实现。
// 将来的版本可能会增加一个默认实现。
virtual void Prune() {}
// 返回当前缓存中所有数据条目所占容量总和的一个预估
virtual size_t TotalCharge() const = 0;

private:
// The table consists of an array of buckets where each bucket is
// a linked list of cache entries that hash into the bucket.
// 第一个length_ 保存了桶的个数
uint32_t length_;
// 维护在整个hash表中一共存放了多少个元素
uint32_t elems_;
// 二维指针，每一个指针指向一个桶的表头位置
LRUHandle** list_;

// 首先读取 `next_hash`，找到下一个链节，将其链到待插入节点后边，然后修改前驱节点 `next_hash` 指向。
LRUHandle* Insert(LRUHandle* h) {
  // 查找节点，路由定位
  LRUHandle** ptr = FindPointer(h->key(), h->hash);
  LRUHandle* old = *ptr;
  h->next_hash = (old == nullptr ? nullptr : old->next_hash);
  *ptr = h;
  if (old == nullptr) {
    ++elems_;
    if (elems_ > length_) {
      // Since each cache entry is fairly large, we aim for a small average linked list length (<= 1).
      // 由于每个缓存条目都相当大，我们的目标是一个小的平均链表长度（<= 1）。
      Resize();
    }
  }
  return old;
}

/*
    Resize 操作
  */
  void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      // 扩展
      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++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        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);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
  }
};

// 返回一个指向 slot 的指针，该指针指向一个缓存条目
// 匹配键/哈希。 如果没有这样的缓存条目，则返回一个
// 指向对应链表中尾随槽的指针。
LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)];
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

LRUHandle* Remove(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = FindPointer(key, hash);
    LRUHandle* result = *ptr;
    if (result != nullptr) {
      *ptr = result->next_hash;
      --elems_;
    }
    return result;
  }

LRUHandle lru_;      // lru_ 是冷链表，属于冷宫，
  LRUHandle in_use_;   // in_use_ 属于热链表，热数据在此链表
  HandleTable table_; // 哈希表部分已经讲过

class LRUCache {
 public:
  LRUCache();
  ~LRUCache();
  // 构造方法可以手动之处容量，
  void SetCapacity(size_t capacity) { capacity_ = capacity; }
 private:
  // 辅助函数：将链节 e 从双向链表中摘除
  void LRU_Remove(LRUHandle* e);
  // 辅助函数：将链节 e 追加到链表头
  void LRU_Append(LRUHandle* list, LRUHandle* e);
  // 辅助函数：增加链节 e 的引用
  void Ref(LRUHandle* e);
  // 辅助函数：减少链节 e 的引用
  void Unref(LRUHandle* e);
  // 辅助函数：从缓存中删除单个链节 e
  bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  // 在使用 LRUCache 前必须先初始化此值
  size_t capacity_;
  // mutex_ 用以保证此后的字段的线程安全
  mutable port::Mutex mutex_;
  size_t usage_ GUARDED_BY(mutex_);
  // lru 双向链表的空表头
  // lru.prev 指向最新的条目，lru.next 指向最老的条目
  // 此链表中所有条目都满足 refs==1 和 in_cache==true
  // 表示所有条目只被缓存引用，而没有客户端在使用
  // 作者注释
  // LRU 列表的虚拟头。
   // lru.prev 是最新条目，lru.next 是最旧条目。
   // 条目有 refs==1 和 in_cache==t
  LRUHandle lru_ GUARDED_BY(mutex_);
  // in-use 双向链表的空表头
  // 保存所有仍然被客户端引用的条目
  // 由于在被客户端引用的同时还被缓存引用，
  // 肯定有 refs >= 2 和 in_cache==true.
  // 作者注释：
  // 使用中列表的虚拟头。
  // 条目正在被客户端使用，并且 refs >= 2 并且 in_cache==true。
  LRUHandle in_use_ GUARDED_BY(mutex_);
  // 所有条目的哈希表索引
  HandleTable table_ GUARDED_BY(mutex_);
};

void LRUCache::Ref(LRUHandle* e) {
    if (e->refs == 1 && e->in_cache) { 
      // If on lru_ list, move to in_use_ list.
      LRU_Remove(e);
      // 打入热链表
      LRU_Append(&in_use_, e);
    }
    e->refs++;
  }
  void LRUCache::Unref(LRUHandle* e) {
    assert(e->refs > 0);
    e->refs--;
    if (e->refs == 0) { 
      // Deallocate.
      // 解除分配
      assert(!e->in_cache);
      (*e->deleter)(e->key(), e->value);
      free(e);
    } else if (e->in_cache && e->refs == 1) {
      // No longer in use; move to lru_ list.
      // 不再使用； 移动到 冷链表。
      LRU_Remove(e);
      LRU_Append(&lru_, e);
    }
  }

void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) {
    // 通过在 *list 之前插入来创建“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;
  }
  void LRUCache::LRU_Remove(LRUHandle* e) {
    e->next->prev = e->prev;
    e->prev->next = e->next;
  }