node_modules/xterm/src/browser/renderer/atlas/LRUMap.ts

   1 /**
   2  * Copyright (c) 2017 The xterm.js authors. All rights reserved.
   3  * @license MIT
   4  */
   5
   6 interface ILinkedListNode<T> {
   7   prev: ILinkedListNode<T> | null;
   8   next: ILinkedListNode<T> | null;
   9   key: number | null;
  10   value: T | null;
  11 }
  12
  13 export class LRUMap<T> {
  14   private _map: { [key: number]: ILinkedListNode<T> } = {};
  15   private _head: ILinkedListNode<T> | null = null;
  16   private _tail: ILinkedListNode<T> | null = null;
  17   private _nodePool: ILinkedListNode<T>[] = [];
  18   public size: number = 0;
  19
  20   constructor(public capacity: number) { }
  21
  22   private _unlinkNode(node: ILinkedListNode<T>): void {
  23     const prev = node.prev;
  24     const next = node.next;
  25     if (node === this._head) {
  26       this._head = next;
  27     }
  28     if (node === this._tail) {
  29       this._tail = prev;
  30     }
  31     if (prev !== null) {
  32       prev.next = next;
  33     }
  34     if (next !== null) {
  35       next.prev = prev;
  36     }
  37   }
  38
  39   private _appendNode(node: ILinkedListNode<T>): void {
  40     const tail = this._tail;
  41     if (tail !== null) {
  42       tail.next = node;
  43     }
  44     node.prev = tail;
  45     node.next = null;
  46     this._tail = node;
  47     if (this._head === null) {
  48       this._head = node;
  49     }
  50   }
  51
  52   /**
  53    * Preallocate a bunch of linked-list nodes. Allocating these nodes ahead of time means that
  54    * they're more likely to live next to each other in memory, which seems to improve performance.
  55    *
  56    * Each empty object only consumes about 60 bytes of memory, so this is pretty cheap, even for
  57    * large maps.
  58    */
  59   public prealloc(count: number): void {
  60     const nodePool = this._nodePool;
  61     for (let i = 0; i < count; i++) {
  62       nodePool.push({
  63         prev: null,
  64         next: null,
  65         key: null,
  66         value: null
  67       });
  68     }
  69   }
  70
  71   public get(key: number): T | null {
  72     // This is unsafe: We're assuming our keyspace doesn't overlap with Object.prototype. However,
  73     // it's faster than calling hasOwnProperty, and in our case, it would never overlap.
  74     const node = this._map[key];
  75     if (node !== undefined) {
  76       this._unlinkNode(node);
  77       this._appendNode(node);
  78       return node.value;
  79     }
  80     return null;
  81   }
  82
  83   /**
  84    * Gets a value from a key without marking it as the most recently used item.
  85    */
  86   public peekValue(key: number): T | null {
  87     const node = this._map[key];
  88     if (node !== undefined) {
  89       return node.value;
  90     }
  91     return null;
  92   }
  93
  94   public peek(): T | null {
  95     const head = this._head;
  96     return head === null ? null : head.value;
  97   }
  98
  99   public set(key: number, value: T): void {
 100     // This is unsafe: See note above.
 101     let node = this._map[key];
 102     if (node !== undefined) {
 103       // already exists, we just need to mutate it and move it to the end of the list
 104       node = this._map[key];
 105       this._unlinkNode(node);
 106       node.value = value;
 107     } else if (this.size >= this.capacity) {
 108       // we're out of space: recycle the head node, move it to the tail
 109       node = this._head!;
 110       this._unlinkNode(node);
 111       delete this._map[node.key!];
 112       node.key = key;
 113       node.value = value;
 114       this._map[key] = node;
 115     } else {
 116       // make a new element
 117       const nodePool = this._nodePool;
 118       if (nodePool.length > 0) {
 119         // use a preallocated node if we can
 120         node = nodePool.pop()!;
 121         node.key = key;
 122         node.value = value;
 123       } else {
 124         node = {
 125           prev: null,
 126           next: null,
 127           key,
 128           value
 129         };
 130       }
 131       this._map[key] = node;
 132       this.size++;
 133     }
 134     this._appendNode(node);
 135   }
 136 }