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 const removed = this.#deleteFn ? [...this] : [];
60 super.clear();
61 this.#order.clear();
62 this.#head = none;
63 this.#tail = none;
64 this.#used = 0;
65 for (const [key, value] of removed) this.#deleteFn?.(value, key);
66 }
67 override delete(key: K): boolean {
68 const entry = this.#evict(key);
69 if (!entry) return false;
70 const value = super.get(key) as V;
71 this.#used -= entry[0];
72 ASSERT(this.#order.delete(key));
73 ASSERT(super.delete(key));
74 this.#deleteFn?.(value, key);
75 return true;
76 }
77 override get(key: K): V | undefined {
78 if (this.#head !== key) {
79 const entry = this.#evict(key);
80 if (!entry) return undefined;
81 entry[1] = none, entry[2] = this.#head;
82 UNWRAP(this.#order.get(this.#head as K))[1] = key;
83 this.#head = key;
84 }
85 return super.get(key) as V;
86 }
87 override set(key: K, value: V): this {
88 const size = this.#sizeFn(value, key);
89 {
90 const uc = this.unlockedCapacity;
91 if (size > uc) {
92 const label = uc === this.#capacity ? " " : " unlocked ";
93 const msg = `Object of size ${size} exceeds${label}capacity ${uc}`;
94 throw new RangeError(msg);
95 }
96 }
97
98 const entry = this.#evict(key);
99 if (entry) {
100 // relocate
101 this.#used -= entry[0];
102 const head = this.#head;
103 ASSERT(head !== key);
104 entry[0] = size, entry[1] = none, entry[2] = this.#head;
105 if (head !== none) UNWRAP(this.#order.get(this.#head as K))[1] = key;
106 if (this.#tail === none) this.#tail = key;
107 } else {
108 // insertion
109 const { size: mapSize } = this;
110 const order: Order<K> = [size, none, mapSize > 0 ? this.#head : none, 0];
111 this.#order.set(key, order);
112 if (mapSize === 0) this.#tail = key;
113 else if (this.#head !== none) {
114 UNWRAP(this.#order.get(this.#head as K))[1] = key;
115 }
116 }
117
118 this.#head = key;
119 this.#used += size;
120 try {
121 this.ensureUnusedCapacity(0);
122 } catch {
123 ASSERT(false, "capacity is already verified");
124 }
125 super.set(key, value);
126 return this;
127 }
128
129 /** prevent an item from being automatically evicted */
130 lock(key: K): ts.Dispose {
131 const order = this.#order.get(key);
132 if (!order) throw new Error(`Key ${key} not in Lru`);
133 const count = order[3] += 1;
134 if (count === 1) this.#locked += order[0];
135 return ts.defer(() => {
136 const count = order![3] -= 1;
137 if (count === 0) this.#locked -= order[0];
138 });
139 }
140
141 /** evict items until there are `unused` capacity slots. */
142 ensureUnusedCapacity(unused: number) {
143 const uc = this.unlockedCapacity;
144 if (unused > uc) {
145 const label = uc === this.#capacity ? "capacity" : "unlocked capacity";
146 const msg = `Can't ensure ${unused} unused capacity with ${label} ${uc}`;
147 throw new RangeError(msg);
148 }
149 const needed = this.#used - this.#capacity + unused;
150 if (needed <= 0) return;
151 let remain = needed;
152 const evictFn = this.#evictFn;
153 const deleteFn = this.#deleteFn;
154 const order = this.#order;
155 let key = this.#tail;
156 loop: {
157 let hadLocks = false;
158 while (key !== none) {
159 const entry = UNWRAP(order.get(key));
160 if (entry[3] > 0) {
161 key = entry[1];
162 hadLocks = true;
163 continue;
164 }
165 ASSERT(this.#evict(key) === entry);
166 if (evictFn) evictFn(super.get(key) as V, key);
167 if (deleteFn) deleteFn(super.get(key) as V, key);
168 ASSERT(this.#order.delete(key));
169 ASSERT(super.delete(key));
170 remain -= entry[0];
171 if (remain <= 0) break loop;
172 key = entry[1];
173 }
174 ASSERT(hadLocks);
175 const msg = `Too many locked objects, cannot free ${unused} capacity`;
176 throw new RangeError(msg);
177 }
178 this.#used -= needed - remain;
179 }
180
181 /** unlink an entry without removing it. */
182 #evict(key: K) {
183 const entry = this.#order.get(key);
184 if (!entry) return null;
185 const [, before, after] = entry;
186 if (before !== none) {
187 UNWRAP(this.#order.get(before as K))[2] = after;
188 } else this.#head = after;
189 if (after !== none) {
190 UNWRAP(this.#order.get(after as K))[1] = before;
191 } else this.#tail = before;
192 return entry;
193 }
194
195 get capacity(): number {
196 return this.#capacity;
197 }
198 set capacity(capacity: number) {
199 this.#capacity = capacity;
200 this.ensureUnusedCapacity(0);
201 }
202 get remaining(): number {
203 return this.#capacity - this.#used;
204 }
205 get unlockedCapacity(): number {
206 return this.#capacity - this.#locked;
207 }
208 get used(): number {
209 return this.#used;
210 }
211
212 serialize(): Serialized<K, V>;
213 serialize<OK, OV>(o: SerializeOptions<K, V, OK, OV>): Serialized<OK, OV>;
214 serialize<OK, OV>(
215 opts: SerializeOptions<K, V, OK, OV> = {},
216 ): Serialized<OK, OV> {
217 const { map = (k, v) => [k as unknown as OK, v as unknown as OV] } = opts;
218 const result: Serialized<OK, OV> = [];
219 const order = this.#order;
220 let head = this.#head;
221 while (head !== none) {
222 const entry = UNWRAP(order.get(head), head);
223 const kv = map(head, super.get(head) as V);
224 head = entry[2];
225 if (!kv) continue;
226 const [key, value] = kv;
227 result.push([key, value, entry[0]]);
228 }
229 return result;
230 }
231 revive<IK, IV>(
232 entries: Serialized<IK, IV>,
233 opts: SerializeOptions<IK, IV, K, V> = {},
234 ) {
235 const { map = (k, v) => [k as unknown as K, v as unknown as V] } = opts;
236 const order = this.#order;
237 let prev: Order<K> | null = null;
238 let pk!: K;
239 let totalSize = 0;
240 for (let i = entries.length - 1; i >= 0; i -= 1) {
241 const [ik, iv, size] = UNWRAP(entries[i]);
242 const kv = map(ik, iv);
243 if (!kv) continue;
244 const [k, v] = kv;
245 super.set(k, v);
246 const current: Order<K> = [size, none, prev ? pk : none, 0];
247 if (prev) prev[1] = k;
248 else this.#tail = k;
249 order.set(k, current);
250 prev = current;
251 pk = k;
252 totalSize += size;
253 }
254 if (prev) this.#head = pk;
255 this.#used = totalSize;
256 }
257}
258
259/** the first item is the most recently used. */
260type Serialized<K, V> = Array<[K, V, number]>;
261
262interface SerializeOptions<IK, IV, OK = IK, OV = IV> {
263 /** null = omit in serialization/serialization */
264 map?: (key: IK, value: IV) => [OK, OV] | null;
265}
266
267type Order<K> = [
268 /** number of units computed at insertion time. */
269 size: number,
270 /** towards most recently used */
271 before: K | none,
272 /** towards least recently used */
273 after: K | none,
274 /** locking prevents automatic eviction */
275 locks: number,
276];
277
278export declare namespace Lru {
279 export type { Serialized, SerializeOptions };
280}
281
282const none: unique symbol = Symbol();
283type none = typeof none;
284
285import { ASSERT, UNWRAP } from "./assert.ts";
286import * as ts from "./ts.ts";