Skip to content
Source
Sign inSign up
TanStack/router
Open History to see the last commit

sieve-cache.ts

75 lines2.2 KB

1export type SieveCache<TKey, TValue> = {
2 get: (key: TKey) => TValue | undefined
3 set: (key: TKey, value: TValue) => void
4 clear: () => void
5}
6​
7/**
8 * A fixed-capacity cache using the SIEVE eviction algorithm
9 * (https://cachemon.github.io/SIEVE-website/).
10 *
11 * Entries live in the Map's FIFO insertion order; a hit only flips a `visited`
12 * bit instead of relinking the entry, which makes `get` (by far the hottest
13 * operation here) one `Map.get` plus a boolean store. Eviction sweeps a `hand`
14 * from the oldest entry towards the newest, clearing `visited` bits until it
15 * finds an unvisited entry to drop, so entries touched since the last sweep
16 * survive one more round. This keeps LRU-like hit ratios while being
17 * scan-resistant.
18 */
19export function createSieveCache<TKey, TValue>(
20 max: number,
21): SieveCache<TKey, TValue> {
22 type Node = {
23 key: TKey
24 value: TValue
25 visited: boolean
26 }
27 const cache = new Map<TKey, Node>()
28 let hand: IterableIterator<Node> | undefined
29 let newest: Node | undefined
30​
31 return {
32 get(key) {
33 const entry = cache.get(key)
34 if (!entry) {
35 return undefined
36 }
37 entry.visited = true
38 return entry.value
39 },
40 set(key, value) {
41 const existing = cache.get(key)
42 if (existing) {
43 existing.value = value
44 return
45 }
46 if (cache.size >= max) {
47 // sweep from `hand` towards `newest` (wrapping around to `oldest`),
48 // clearing `visited` bits, and evict the first unvisited entry
49 let node = hand?.next().value
50 while (!node || node.visited) {
51 if (node) {
52 node.visited = false
53 } else {
54 hand = cache.values()
55 }
56 node = hand!.next().value
57 }
58 // Live Map iterators see later insertions. Reset at the boundary so the
59 // next sweep wraps to the oldest entry instead of visiting a replacement.
60 if (node === newest) {
61 hand = undefined
62 }
63 cache.delete(node.key)
64 }
65 const entry: Node = { key, value, visited: false }
66 newest = entry
67 cache.set(key, entry)
68 },
69 clear() {
70 cache.clear()
71 hand = undefined
72 newest = undefined
73 },
74 }