SOURCE

// 请实现类似的逻辑LRUStorage。

// 目的并不是要重现Chrome的内部实现。
// getData 和setData被调用的时候，需要算作'used'。
// 由于时间精度问题，class的constructor请支持第二个getTimestamp 参数。
// interface OriginData {
//   origin: string
//   lastUsed: number
//   size: number
//   persistent: boolean
// }
// interface LRUStorage {
//   capacity: number
//   // to use the data for origin
//   // return size of the data or undefined if not exist
//   getData(origin: string): OriginData | undefined
  
//   // updating data for origin
//   // return boolean to indicate success or failure
//   // If the total size exceeds capacity,
//   // Least Recently Used non-persistent origin data other than itself should be evicted.
//   setData(origin: string, size: number): boolean
//   // manually clear data for origin
//   clearData(origin: string): void
//   // change data for origin to be persistent
//   // it only handles existing data not the data added later
//   // persistent data cannot be evicted unless manually clear it
//   makePersistent(origin: string): void 
// }

 class LRUStorage {
     constructor(capacity,getTimestamp = Date.now) {
         this.capacity = capacity;
         this.getTimestamp = getTimestamp;

         this.currentSize = 0;

         this.map = new Map();

         this.head = null;
         this.tail = null;
     };

     _createNode(data) {
         return {
             data,
             prev:null,
             next:null,
         }
     };

     _addToHead(node) {
         if(!this.head) {
             this.head = node;
             this.tail = node;
         }else {
             node.next = this.head;
             this.head.prev = node;
             this.head = node;
         };
     };

     _remove(node) {
         if(node.prev) {
             node.prev.next = node.next;
         }else{
             this.head = node.next;
         };

         if(node.next) {
             node.next.prev = node.prev;
         }else {
             this.tail = node.prev;
         }
     };

     _moveToHead(node) {
         if(node === this.head) return;

         this._remove(node);
         this._addToHead(node);
     };

     _removeTail() {
         if(!this.tail) return null;

         const node = this.tail;
         this._remove(node);

         return node;
     };

     getData(origin) {
         const node = this.map.get(origin);
         if(!node) return undefined // or -1

         node.data.lastUsed = this.getTimestamp()
         this._moveToHead(node);

         return {
             ...node.data
         };
     };

     setData(origin,size) {
         if(size <= 0 || typeof origin !== 'string' || origin ==='') {
             return false;
         };

         const existing = this.map.get(origin);
         const oldSize = existing ? existing.data.size : 0;

         const delta = size - oldSize;

         if(size > this.capacity && !existing) return false;

         if(this.currentSize + delta > this.capacity) {
             const needed = this.currentSize + delta  - this.capacity;

             if(!this._evict(needed)) return false;
         };

         const now = this.getTimestamp();

         if(existing) {
             existing.data.size = size;
             existing.data.lastUsed = now;

             this.currentSize +=delta;
             this._moveToHead(existing);
         }else{
             const node = this._createNode({
                 origin,
                 lastUsed:now,
                 size,
                 persistent:false
             });
             this.map.set(origin,node);
             this._addToHead(node);
             this.currentSize +=size;
         };

         return true;
     };

     clearData(origin) {
         const node = this.map.get(origin);

         if(node) {
             this.currentSize -= node.data.size;
             this._remove(node);
             this.map.delete(origin);
         };
     };

     makePersistent(origin) {
         const node = this.map.get(origin);
         if(node) {
             node.data.persistent = true;
         }
     };

     _evict(needed) {
         if(needed <= 0) return true;

         let freed = 0;
         let current = this.tail;

         while(current && freed < needed) {
             const prev = current.prev;

             if(!current.data.persistent) {
                 freed += current.data.size;
                 this.currentSize -= current.data.size;
                 this._remove(current);

                 this.map.delete(current.data.origin);
             }

             current = prev;
         }

         return freed >= needed;
     };
 };