1/**
2 * least-recently-used cache.
3 * this module is intended to be imported via the main class.
4 *
5 * ```ts
6 * import { Lru } from '@clo/lib/Lru';
7 * // Extra types are in a `declare namespace`
8 * const opts: Lru.Options = { capacity: 2 };
9 * const lru = new Lru(opts);
10 * ```
11 *
12 * @module
13 */
14
15interface Options<K, V> {
16 capacity: number;
17 /**
18 * decide how many units of size each entry takes.
19 * For example, accessing `.byteLength` of a Buffer.
20 */
21 sizeFn?: (value: V, key: K) => number;
22 /** called when `set` or `ensureUnusedCapacity` removes items. */
23 evict?: (value: V, key: K) => void;
24 /** called when anything removes items. */
25 delete?: (value: V, key: K) => void;
26}
27
28/**
29 * a Least-recently-used cache has a set capacity, removing the oldest item
30 * when trying to insert an item that would exceed such capacity. this
31 * implementation supports variable sized items, eviction callbacks, entry
32 * locking, and JSON-compatible serialization.
33 *
34 * https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
35 */
36export class Lru<K, V> extends Map<K, V> {
37 #order = new Map<K, Order<K>>();
38 /** the most recently used */
39 #head: K | none = none;
40 /** the least recently used */
41 #tail: K | none = none;
42 #used: number = 0;
43 #locked: number = 0;
44 #capacity: number;
45 #sizeFn: (value: V, key: K) => number;
46 #deleteFn: null | ((value: V, key: K) => void);
47 #evictFn: null | ((value: V, key: K) => void);
48
49 constructor(opts: Options<K, V>) {
50 super();
51 const { capacity, sizeFn, delete: deleteFn, evict } = opts;
52 this.#capacity = capacity;
53 this.#sizeFn = sizeFn ?? (() => 1);
54 this.#deleteFn = deleteFn ?? null;
55 this.#evictFn = evict ?? null;
56 }
57
58 override clear() {
59 super.clear();
60 this.#order.clear();
61 this.#head = none;
62 this.#tail = none;
63 this.#used = 0;
64 }
65 override delete(key: K): boolean {
66 const entry = this.#evict(key);
67 if (!entry) return false;
68 this.#used -= entry[0];
69 ASSERT(this.#order.delete(key));
70 ASSERT(super.delete(key));
71 return true;
72 }
73 override get(key: K): V | undefined {
74 if (this.#head !== key) {
75 const entry = this.#evict(key);
76 if (!entry) return undefined;
77 entry[1] = none, entry[2] = this.#head;
78 UNWRAP(this.#order.get(this.#head as K))[1] = key;
79 this.#head = key;
80 }
81 return super.get(key) as V;
82 }
83 override set(key: K, value: V): this {
84 const size = this.#sizeFn(value, key);
85 {
86 const uc = this.unlockedCapacity;
87 if (size > uc) {
88 const label = uc === this.#capacity ? " " : " unlocked ";
89 const msg = `Object of size ${size} exceeds${label}capacity ${uc}`;
90 throw new RangeError(msg);
91 }
92 }
93
94 const entry = this.#evict(key);
95 if (entry) {
96 // relocate
97 this.#used -= entry[0];
98 const head = this.#head;
99 ASSERT(head !== key);
100 entry[0] = size, entry[1] = none, entry[2] = this.#head;
101 if (head !== none) UNWRAP(this.#order.get(this.#head as K))[1] = key;
102 if (this.#tail === none) this.#tail = key;
103 } else {
104 // insertion
105 const { size: mapSize } = this;
106 const order: Order<K> = [size, none, mapSize > 0 ? this.#head : none, 0];
107 this.#order.set(key, order);
108 if (mapSize === 0) this.#tail = key;
109 else if (this.#head !== none) {
110 UNWRAP(this.#order.get(this.#head as K))[1] = key;
111 }
112 }
113
114 this.#head = key;
115 this.#used += size;
116 try {
117 this.ensureUnusedCapacity(0);
118 } catch {
119 ASSERT(false, "capacity is already verified");
120 }
121 super.set(key, value);
122 return this;
123 }
124
125 /** prevent an item from being automatically evicted */
126 lock(key: K): ts.Dispose {
127 const order = this.#order.get(key);
128 if (!order) throw new Error(`Key ${key} not in Lru`);
129 const count = order[3] += 1;
130 if (count === 1) this.#locked += order[0];
131 return ts.defer(() => {
132 const count = order![3] -= 1;
133 if (count === 0) this.#locked -= order[0];
134 });
135 }
136
137 /** evict items until there are `unused` capacity slots. */
138 ensureUnusedCapacity(unused: number) {
139 const uc = this.unlockedCapacity;
140 if (unused > uc) {
141 const label = uc === this.#capacity ? "capacity" : "unlocked capacity";
142 const msg = `Can't ensure ${unused} unused capacity with ${label} ${uc}`;
143 throw new RangeError(msg);
144 }
145 const needed = this.#used - this.#capacity + unused;
146 if (needed <= 0) return;
147 let remain = needed;
148 const evictFn = this.#evictFn;
149 const deleteFn = this.#deleteFn;
150 const order = this.#order;
151 let key = this.#tail;
152 loop: {
153 let hadLocks = false;
154 while (key !== none) {
155 const entry = UNWRAP(order.get(key));
156 if (entry[3] > 0) {
157 key = entry[1];
158 hadLocks = true;
159 continue;
160 }
161 ASSERT(this.#evict(key) === entry);
162 if (evictFn) evictFn(super.get(key) as V, key);
163 if (deleteFn) deleteFn(super.get(key) as V, key);
164 ASSERT(this.#order.delete(key));
165 ASSERT(super.delete(key));
166 remain -= entry[0];
167 if (remain <= 0) break loop;
168 key = entry[1];
169 }
170 ASSERT(hadLocks);
171 const msg = `Too many locked objects, cannot free ${unused} capacity`;
172 throw new RangeError(msg);
173 }
174 this.#used -= needed - remain;
175 }
176
177 /** unlink an entry without removing it. */
178 #evict(key: K) {
179 const entry = this.#order.get(key);
180 if (!entry) return null;
181 const [, before, after] = entry;
182 if (before !== none) {
183 UNWRAP(this.#order.get(before as K))[2] = after;
184 } else this.#head = after;
185 if (after !== none) {
186 UNWRAP(this.#order.get(after as K))[1] = before;
187 } else this.#tail = before;
188 return entry;
189 }
190
191 get capacity(): number {
192 return this.#capacity;
193 }
194 set capacity(capacity: number) {
195 this.#capacity = capacity;
196 this.ensureUnusedCapacity(0);
197 }
198 get remaining(): number {
199 return this.#capacity - this.#used;
200 }
201 get unlockedCapacity(): number {
202 return this.#capacity - this.#locked;
203 }
204 get used(): number {
205 return this.#used;
206 }
207
208 serialize(): Serialized<K, V>;
209 serialize<OK, OV>(o: SerializeOptions<K, V, OK, OV>): Serialized<OK, OV>;
210 serialize<OK, OV>(
211 opts: SerializeOptions<K, V, OK, OV> = {},
212 ): Serialized<OK, OV> {
213 const { map = (k, v) => [k as unknown as OK, v as unknown as OV] } = opts;
214 const result: Serialized<OK, OV> = [];
215 const order = this.#order;
216 let head = this.#head;
217 while (head !== none) {
218 const entry = UNWRAP(order.get(head), head);
219 const kv = map(head, super.get(head) as V);
220 head = entry[2];
221 if (!kv) continue;
222 const [key, value] = kv;
223 result.push([key, value, entry[0]]);
224 }
225 return result;
226 }
227 revive<IK, IV>(
228 entries: Serialized<IK, IV>,
229 opts: SerializeOptions<IK, IV, K, V> = {},
230 ) {
231 const { map = (k, v) => [k as unknown as K, v as unknown as V] } = opts;
232 const order = this.#order;
233 let prev: Order<K> | null = null;
234 let pk!: K;
235 let totalSize = 0;
236 for (let i = entries.length - 1; i >= 0; i -= 1) {
237 const [ik, iv, size] = UNWRAP(entries[i]);
238 const kv = map(ik, iv);
239 if (!kv) continue;
240 const [k, v] = kv;
241 super.set(k, v);
242 const current: Order<K> = [size, none, prev ? pk : none, 0];
243 if (prev) prev[1] = k;
244 else this.#tail = k;
245 order.set(k, current);
246 prev = current;
247 pk = k;
248 totalSize += size;
249 }
250 if (prev) this.#head = pk;
251 this.#used = totalSize;
252 }
253}
254
255/** the first item is the most recently used. */
256type Serialized<K, V> = Array<[K, V, number]>;
257
258interface SerializeOptions<IK, IV, OK = IK, OV = IV> {
259 /** null = omit in serialization/serialization */
260 map?: (key: IK, value: IV) => [OK, OV] | null;
261}
262
263type Order<K> = [
264 /** number of units computed at insertion time. */
265 size: number,
266 /** towards most recently used */
267 before: K | none,
268 /** towards least recently used */
269 after: K | none,
270 /** locking prevents automatic eviction */
271 locks: number,
272];
273
274export declare namespace Lru {
275 export type { Serialized, SerializeOptions };
276}
277
278const none: unique symbol = Symbol();
279type none = typeof none;
280
281import { ASSERT, UNWRAP } from "./assert.ts";
282import * as ts from "./ts.ts";