LRU Cache

[PolluxLee]

LRU 是 Least Recently Used 的缩写，即最近最少使用

           entry             entry             entry             entry        
           ______            ______            ______            ______       
          | head |.newer => |      |.newer => |      |.newer => | tail |      
.newest = |  A   |          |  B   |          |  C   |          |  D   | = .oldest
          |______| <= older.|______| <= older.|______| <= older.|______|      
                                                                             
       removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added

• get: 获取数据，并将数据移动到双链表尾部
• set: 新增数据，将数据插入到双联表尾部，同时判断链表元素数量是否超出限制，若超出则移除 head 指针指向的元素

class Cache {
  constructor(limit) {
    this.size = 0;
    this.limit = limit;
    this.head = this.tail = undefined;
    this._keymap = Object.create(null);
  }

  set(key, value) {
    let entry = { key, value };
    this._keymap[key] = entry;
    if (this.tail) {
      this.tail.newer = entry;
      entry.older = this.tail;
    } else {
      this.head = entry;
    }
    this.tail = entry;
    if (this.size === this.limit) {
      return this.shift();
    } else {
      this.size++;
    }
  }

  shift() {
    let entry = this.head;
    if (entry) {
      this.head = this.head.newer;
      this.head.older = undefined;
      entry.newer = entry.older = undefined;
      this._keymap[entry.key] = undefined;
    }
    return entry;
  }

  get(key, returnEntry) {
    let entry = this._keymap[key];
    if (entry === undefined) { return; }
    if (entry === this.tail) {
      return returnEntry
        ? entry
        : entry.value;
    }
    // HEAD--------------TAIL
    //   <.older   .newer>
    //  <--- add direction --
    //   A  B  C  <D>  E
    if (entry.newer) {
      if (entry === this.head) {
        this.head = entry.newer;
      }
      entry.newer.older = entry.older; // C <-- E.
    }
    if (entry.older) {
      entry.older.newer = entry.newer; // C. --> E
    }
    entry.newer = undefined; // D --x
    entry.older = this.tail; // D. --> E
    if (this.tail) {
      this.tail.newer = entry; // E. <-- D
    }
    this.tail = entry;
    return returnEntry
      ? entry
      : entry.value;
  }
}

export default Cache;