leveldb笔记之11:LRUCache的实现

// 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);//当refs降为0时的清理函数
  LRUHandle* next_hash;//HandleTable hash冲突时指向下一个LRUHandle*
  LRUHandle* next;//LRU链表双向指针
  LRUHandle* prev;//LRU链表双向指针
  // 用于计算LRUCache容量
  size_t charge;      // TODO(opt): Only allow uint32_t?
  size_t key_length;// key长度
  // 是否在LRUCache in_use_ 链表
  bool in_cache;      // Whether entry is in the cache.
  // 引用计数，用于删除数据
  uint32_t refs;      // References, including cache reference, if present.
  // key 对应的hash值
  uint32_t hash;      // Hash of key(); used for fast sharding and comparisons
  // 占位符，结构体末尾，通过key_length获取真正的key
  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);

    return Slice(key_data, key_length);
  }
};

// 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*存在相同的hash&&key值，则返回该LRUHandle*的二级指针，即指向上一个LRUHandle*的next_hash的二级
指针.
// 如果不存在这样的LRUHandle*，则返回指向该bucket的最后一个LRUHandle*的next_hash的二级指针，其值为nullptr.
// 返回next_hash地址的作用是可以直接修改该值，因此起到修改链表的作用
LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
//先查找处于哪个桶
LRUHandle** ptr = &list_[hash & (length_ - 1)];
//next_hash 查找该桶，直到满足以下条件之一：
//*ptr == nullptr
//某个LRUHandle* hash和key的值都与目标值相同
while (*ptr != nullptr &&
       ((*ptr)->hash != hash || key != (*ptr)->key())) {
  ptr = &(*ptr)->next_hash;
}
//返回符合条件的LRUHandle**
return ptr;
}

  // Initialized before use.
  size_t capacity_;

  // mutex_ protects the following state.
  mutable port::Mutex mutex_;//Insert/Lookup等操作时都先加锁
  size_t usage_ GUARDED_BY(mutex_);//用于跟capacity_比较，判断是否超过容量

  // 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_);

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != nullptr) {
    Ref(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

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内存，初始化该结构体
  // refs = 2:
  // 1. 返回的Cache::Handle*
  // 2. in_use_链表里记录
  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) {
    e->refs++;  // for the cache's reference.
    e->in_cache = true;
    //添加到in_use_队列
    LRU_Append(&in_use_, e);
    usage_ += charge;

    // 如果是更新的，删除原有节点
    FinishErase(table_.Insert(e));

  // 如果超过了容量限制，根据lru_按照lru策略淘汰
  while (usage_ > capacity_ && lru_.next != &lru_) {
    // lru_.next是最老的节点，首先淘汰
    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);
    }
  }

void LRUCache::Release(Cache::Handle* handle) {
  MutexLock l(&mutex_);
  Unref(reinterpret_cast<LRUHandle*>(handle));
}

static const int kNumShardBits = 4;
static const int kNumShards = 1 << kNumShardBits;//16，即16个分片，二进制定义的好处是取模时>>即可(参考ShardedLRUCache::Shard实现)

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);
    }
  }
  virtual ~ShardedLRUCache() { }

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