2 * Copyright (c) 2017 The xterm.js authors. All rights reserved.
6 interface ILinkedListNode<T> {
7 prev: ILinkedListNode<T> | null;
8 next: ILinkedListNode<T> | null;
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;
20 constructor(public capacity: number) { }
22 private _unlinkNode(node: ILinkedListNode<T>): void {
23 const prev = node.prev;
24 const next = node.next;
25 if (node === this._head) {
28 if (node === this._tail) {
39 private _appendNode(node: ILinkedListNode<T>): void {
40 const tail = this._tail;
47 if (this._head === null) {
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.
56 * Each empty object only consumes about 60 bytes of memory, so this is pretty cheap, even for
59 public prealloc(count: number): void {
60 const nodePool = this._nodePool;
61 for (let i = 0; i < count; i++) {
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);
84 * Gets a value from a key without marking it as the most recently used item.
86 public peekValue(key: number): T | null {
87 const node = this._map[key];
88 if (node !== undefined) {
94 public peek(): T | null {
95 const head = this._head;
96 return head === null ? null : head.value;
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);
107 } else if (this.size >= this.capacity) {
108 // we're out of space: recycle the head node, move it to the tail
110 this._unlinkNode(node);
111 delete this._map[node.key!];
114 this._map[key] = node;
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()!;
131 this._map[key] = node;
134 this._appendNode(node);