lru.nx source
↩ module page · 161 lines · 4720 B
1// lru.nx -- Least-Recently-Used cache.
2//
3// Composes map.nx (key -> node) + dlist.nx (recency order).
4// Classic design, same shape as the LRU in every modern kernel
5// page cache + every language std lib's LinkedHashMap:
6// - get(k) -> value + moves node to front
7// - put(k, v) -> insert or update + moves node to front,
8// evicts tail if over capacity
9//
10// This is the first module composing two runtime data structures
11// end-to-end. Proves the shelves interlock cleanly.
12//
13// Storage per entry: DNode with data pointer holding a
14// LRUEntry struct {key, val}. Map stores key -> node pointer
15// so get() is O(1) amortised.
16//
17// Use cases: compiled-template cache (nishi-pages), route
18// table in HTTP router, DNS resolver cache, prepared-SQL cache,
19// image thumbnail cache.
20//
21// Invariants:
22// L1 size <= capacity at all times (enforced by eviction
23// on insert).
24// L2 Map and dlist stay in sync: every map entry value is a
25// live DNode in the dlist; every live dlist node has an
26// entry in the map.
27// L3 get(missing) returns -1 without mutating state.
28// L4 Capacity of 0 is legal (no entries ever admitted).
29
30import "syscalls.nx"
31import "map.nx"
32import "dlist.nx"
33
34struct LRUEntry {
35 key: i64,
36 val: i64,
37}
38
39struct LRU {
40 cap: i64,
41 size: i64,
42 m: *Map,
43 order: *DList,
44}
45
46func lru_new(cap: i64) -> *LRU {
47 let raw: *u8 = sys_mmap(64)
48 let c: *LRU = raw as *LRU
49 c.cap = cap
50 c.size = 0
51 // Map cap hint sized for the capacity we'll actually hold.
52 var map_cap: i64 = cap * 2
53 if map_cap < 16 { map_cap = 16 }
54 c.m = map_new(map_cap)
55 c.order = dlist_new()
56 return c
57}
58
59// Get: returns val via *out; returns 1 on hit, 0 on miss. Bumps
60// node to front on hit.
61func lru_get(c: *LRU, key: i64, out: *i64) -> i64 {
62 let node_ptr_raw: *i64 = (sys_mmap(16)) as *i64
63 let hit: i64 = map_get(c.m, key, node_ptr_raw)
64 if hit == 0 { return 0 }
65 let node: *DNode = (*node_ptr_raw) as *DNode
66 let entry: *LRUEntry = node.data as *LRUEntry
67 *out = entry.val
68 dlist_move_to_front(c.order, node)
69 return 1
70}
71
72// Put: insert or update. Evicts tail if full.
73func lru_put(c: *LRU, key: i64, val: i64) -> i64 {
74 if c.cap <= 0 { return 0 }
75
76 // Update path?
77 let existing_raw: *i64 = (sys_mmap(16)) as *i64
78 let hit: i64 = map_get(c.m, key, existing_raw)
79 if hit == 1 {
80 let node: *DNode = (*existing_raw) as *DNode
81 let entry: *LRUEntry = node.data as *LRUEntry
82 entry.val = val
83 dlist_move_to_front(c.order, node)
84 return 0
85 }
86
87 // Evict if full.
88 if c.size >= c.cap {
89 let victim: *DNode = dlist_pop_back(c.order)
90 if victim != (0 as *DNode) {
91 let v_entry: *LRUEntry = victim.data as *LRUEntry
92 map_remove(c.m, v_entry.key)
93 c.size = c.size - 1
94 }
95 }
96
97 // Insert new entry.
98 let entry_raw: *u8 = sys_mmap(16)
99 let entry: *LRUEntry = entry_raw as *LRUEntry
100 entry.key = key
101 entry.val = val
102 let node: *DNode = dnode_new(entry_raw)
103 dlist_push_front(c.order, node)
104 map_insert(c.m, key, node as i64)
105 c.size = c.size + 1
106 return 0
107}
108
109// Explicit delete. Returns 1 if found + removed.
110func lru_delete(c: *LRU, key: i64) -> i64 {
111 let node_ptr_raw: *i64 = (sys_mmap(16)) as *i64
112 let hit: i64 = map_get(c.m, key, node_ptr_raw)
113 if hit == 0 { return 0 }
114 let node: *DNode = (*node_ptr_raw) as *DNode
115 dlist_remove(node)
116 map_remove(c.m, key)
117 c.size = c.size - 1
118 return 1
119}
120
121// Size inspector.
122func lru_size(c: *LRU) -> i64 {
123 return c.size
124}
125
126// Compile-only smoke.
127func main() -> i64 {
128 let c: *LRU = lru_new(3)
129 if lru_size(c) != 0 { return 1 }
130
131 lru_put(c, 1, 100)
132 lru_put(c, 2, 200)
133 lru_put(c, 3, 300)
134 if lru_size(c) != 3 { return 2 }
135
136 let out: *i64 = (sys_mmap(16)) as *i64
137 if lru_get(c, 2, out) != 1 { return 3 }
138 if *out != 200 { return 4 }
139
140 // Now order from front: 2, 3, 1. Adding 4 evicts 1.
141 lru_put(c, 4, 400)
142 if lru_size(c) != 3 { return 5 }
143 if lru_get(c, 1, out) != 0 { return 6 }
144
145 // 4 is present.
146 if lru_get(c, 4, out) != 1 { return 7 }
147 if *out != 400 { return 8 }
148
149 // Update existing: should not change size.
150 lru_put(c, 2, 222)
151 if lru_size(c) != 3 { return 9 }
152 lru_get(c, 2, out)
153 if *out != 222 { return 10 }
154
155 // Delete.
156 if lru_delete(c, 2) != 1 { return 11 }
157 if lru_size(c) != 2 { return 12 }
158 if lru_get(c, 2, out) != 0 { return 13 }
159
160 return 0
161}