{"version":3,"sources":["../../../../src/client/components/segment-cache-impl/lru.ts"],"sourcesContent":["export type LRU<T extends LRUNode> = {\n  put(node: T): void\n  delete(node: T): void\n  updateSize(node: T, size: number): void\n}\n\n// Doubly-linked list\ntype LRUNode<T = any> = {\n  // Although it's not encoded in the type, these are both null if the node is\n  // not in the LRU; both non-null if it is.\n  prev: T | null\n  next: T | null\n  size: number\n}\n\n// Rather than create an internal LRU node, the passed-in type must conform\n// the LRUNode interface. This is just a memory optimization to avoid creating\n// another object; we only use this for Segment Cache entries so it doesn't need\n// to be general purpose.\nexport function createLRU<T extends LRUNode>(\n  // From the LRU's perspective, the size unit is arbitrary, but for our\n  // purposes this is the byte size.\n  maxLruSize: number,\n  onEviction: (node: T) => void\n): LRU<T> {\n  let head: T | null = null\n  let didScheduleCleanup: boolean = false\n  let lruSize: number = 0\n\n  function put(node: T) {\n    if (head === node) {\n      // Already at the head\n      return\n    }\n    const prev = node.prev\n    const next = node.next\n    if (next === null || prev === null) {\n      // This is an insertion\n      lruSize += node.size\n      // Whenever we add an entry, we need to check if we've exceeded the\n      // max size. We don't evict entries immediately; they're evicted later in\n      // an asynchronous task.\n      ensureCleanupIsScheduled()\n    } else {\n      // This is a move. Remove from its current position.\n      prev.next = next\n      next.prev = prev\n    }\n\n    // Move to the front of the list\n    if (head === null) {\n      // This is the first entry\n      node.prev = node\n      node.next = node\n    } else {\n      // Add to the front of the list\n      const tail = head.prev\n      node.prev = tail\n      tail.next = node\n      node.next = head\n      head.prev = node\n    }\n    head = node\n  }\n\n  function updateSize(node: T, newNodeSize: number) {\n    // This is a separate function from `put` so that we can resize the entry\n    // regardless of whether it's currently being tracked by the LRU.\n    const prevNodeSize = node.size\n    node.size = newNodeSize\n    if (node.next === null) {\n      // This entry is not currently being tracked by the LRU.\n      return\n    }\n    // Update the total LRU size\n    lruSize = lruSize - prevNodeSize + newNodeSize\n    ensureCleanupIsScheduled()\n  }\n\n  function deleteNode(deleted: T) {\n    const next = deleted.next\n    const prev = deleted.prev\n    if (next !== null && prev !== null) {\n      lruSize -= deleted.size\n\n      deleted.next = null\n      deleted.prev = null\n\n      // Remove from the list\n      if (head === deleted) {\n        // Update the head\n        if (next === head) {\n          // This was the last entry\n          head = null\n        } else {\n          head = next\n        }\n      } else {\n        prev.next = next\n        next.prev = prev\n      }\n    } else {\n      // Already deleted\n    }\n  }\n\n  function ensureCleanupIsScheduled() {\n    if (didScheduleCleanup || lruSize <= maxLruSize) {\n      return\n    }\n    didScheduleCleanup = true\n    requestCleanupCallback(cleanup)\n  }\n\n  function cleanup() {\n    didScheduleCleanup = false\n\n    // Evict entries until we're at 90% capacity. We can assume this won't\n    // infinite loop because even if `maxLruSize` were 0, eventually\n    // `deleteNode` sets `head` to `null` when we run out entries.\n    const ninetyPercentMax = maxLruSize * 0.9\n    while (lruSize > ninetyPercentMax && head !== null) {\n      const tail = head.prev\n      deleteNode(tail)\n      onEviction(tail)\n    }\n  }\n\n  return {\n    put,\n    delete: deleteNode,\n    updateSize,\n  }\n}\n\nconst requestCleanupCallback =\n  typeof requestIdleCallback === 'function'\n    ? requestIdleCallback\n    : (cb: () => void) => setTimeout(cb, 0)\n"],"names":["createLRU","maxLruSize","onEviction","head","didScheduleCleanup","lruSize","put","node","prev","next","size","ensureCleanupIsScheduled","tail","updateSize","newNodeSize","prevNodeSize","deleteNode","deleted","requestCleanupCallback","cleanup","ninetyPercentMax","delete","requestIdleCallback","cb","setTimeout"],"mappings":";;;;+BAmBgBA;;;eAAAA;;;AAAT,SAASA,UACd,sEAAsE;AACtE,kCAAkC;AAClCC,UAAkB,EAClBC,UAA6B;IAE7B,IAAIC,OAAiB;IACrB,IAAIC,qBAA8B;IAClC,IAAIC,UAAkB;IAEtB,SAASC,IAAIC,IAAO;QAClB,IAAIJ,SAASI,MAAM;YACjB,sBAAsB;YACtB;QACF;QACA,MAAMC,OAAOD,KAAKC,IAAI;QACtB,MAAMC,OAAOF,KAAKE,IAAI;QACtB,IAAIA,SAAS,QAAQD,SAAS,MAAM;YAClC,uBAAuB;YACvBH,WAAWE,KAAKG,IAAI;YACpB,mEAAmE;YACnE,yEAAyE;YACzE,wBAAwB;YACxBC;QACF,OAAO;YACL,oDAAoD;YACpDH,KAAKC,IAAI,GAAGA;YACZA,KAAKD,IAAI,GAAGA;QACd;QAEA,gCAAgC;QAChC,IAAIL,SAAS,MAAM;YACjB,0BAA0B;YAC1BI,KAAKC,IAAI,GAAGD;YACZA,KAAKE,IAAI,GAAGF;QACd,OAAO;YACL,+BAA+B;YAC/B,MAAMK,OAAOT,KAAKK,IAAI;YACtBD,KAAKC,IAAI,GAAGI;YACZA,KAAKH,IAAI,GAAGF;YACZA,KAAKE,IAAI,GAAGN;YACZA,KAAKK,IAAI,GAAGD;QACd;QACAJ,OAAOI;IACT;IAEA,SAASM,WAAWN,IAAO,EAAEO,WAAmB;QAC9C,yEAAyE;QACzE,iEAAiE;QACjE,MAAMC,eAAeR,KAAKG,IAAI;QAC9BH,KAAKG,IAAI,GAAGI;QACZ,IAAIP,KAAKE,IAAI,KAAK,MAAM;YACtB,wDAAwD;YACxD;QACF;QACA,4BAA4B;QAC5BJ,UAAUA,UAAUU,eAAeD;QACnCH;IACF;IAEA,SAASK,WAAWC,OAAU;QAC5B,MAAMR,OAAOQ,QAAQR,IAAI;QACzB,MAAMD,OAAOS,QAAQT,IAAI;QACzB,IAAIC,SAAS,QAAQD,SAAS,MAAM;YAClCH,WAAWY,QAAQP,IAAI;YAEvBO,QAAQR,IAAI,GAAG;YACfQ,QAAQT,IAAI,GAAG;YAEf,uBAAuB;YACvB,IAAIL,SAASc,SAAS;gBACpB,kBAAkB;gBAClB,IAAIR,SAASN,MAAM;oBACjB,0BAA0B;oBAC1BA,OAAO;gBACT,OAAO;oBACLA,OAAOM;gBACT;YACF,OAAO;gBACLD,KAAKC,IAAI,GAAGA;gBACZA,KAAKD,IAAI,GAAGA;YACd;QACF,OAAO;QACL,kBAAkB;QACpB;IACF;IAEA,SAASG;QACP,IAAIP,sBAAsBC,WAAWJ,YAAY;YAC/C;QACF;QACAG,qBAAqB;QACrBc,uBAAuBC;IACzB;IAEA,SAASA;QACPf,qBAAqB;QAErB,sEAAsE;QACtE,gEAAgE;QAChE,8DAA8D;QAC9D,MAAMgB,mBAAmBnB,aAAa;QACtC,MAAOI,UAAUe,oBAAoBjB,SAAS,KAAM;YAClD,MAAMS,OAAOT,KAAKK,IAAI;YACtBQ,WAAWJ;YACXV,WAAWU;QACb;IACF;IAEA,OAAO;QACLN;QACAe,QAAQL;QACRH;IACF;AACF;AAEA,MAAMK,yBACJ,OAAOI,wBAAwB,aAC3BA,sBACA,CAACC,KAAmBC,WAAWD,IAAI","ignoreList":[0]}