nx_lru.nx source
↩ module page · 167 lines · 4819 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
30// nx_safety_envelope:
31// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
32// sil_target: SIL1
33// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
34// verdict: NOT_YET_EVALUATED
35
36import "nx_syscalls.nx"
37import "nx_map.nx"
38import "nx_dlist.nx"
39
40struct LRUEntry {
41 key: i64,
42 val: i64,
43}
44
45struct LRU {
46 cap: i64,
47 size: i64,
48 m: *Map,
49 order: *DList,
50}
51
52func lru_new(cap: i64) -> *LRU {
53 let raw: *u8 = sys_mmap(64)
54 let c: *LRU = raw as *LRU
55 c.cap = cap
56 c.size = 0
57 // Map cap hint sized for the capacity we'll actually hold.
58 var map_cap: i64 = cap * 2
59 if map_cap < 16 { map_cap = 16 }
60 c.m = map_new(map_cap)
61 c.order = dlist_new()
62 return c
63}
64
65// Get: returns val via *out; returns 1 on hit, 0 on miss. Bumps
66// node to front on hit.
67func lru_get(c: *LRU, key: i64, out: *i64) -> i64 {
68 let node_ptr_raw: *i64 = (sys_mmap(16)) as *i64
69 let hit: i64 = map_get(c.m, key, node_ptr_raw)
70 if hit == 0 { return 0 }
71 let node: *DNode = (*node_ptr_raw) as *DNode
72 let entry: *LRUEntry = node.data as *LRUEntry
73 *out = entry.val
74 dlist_move_to_front(c.order, node)
75 return 1
76}
77
78// Put: insert or update. Evicts tail if full.
79func lru_put(c: *LRU, key: i64, val: i64) -> i64 {
80 if c.cap <= 0 { return 0 }
81
82 // Update path?
83 let existing_raw: *i64 = (sys_mmap(16)) as *i64
84 let hit: i64 = map_get(c.m, key, existing_raw)
85 if hit == 1 {
86 let node: *DNode = (*existing_raw) as *DNode
87 let entry: *LRUEntry = node.data as *LRUEntry
88 entry.val = val
89 dlist_move_to_front(c.order, node)
90 return 0
91 }
92
93 // Evict if full.
94 if c.size >= c.cap {
95 let victim: *DNode = dlist_pop_back(c.order)
96 if victim != (0 as *DNode) {
97 let v_entry: *LRUEntry = victim.data as *LRUEntry
98 map_remove(c.m, v_entry.key)
99 c.size = c.size - 1
100 }
101 }
102
103 // Insert new entry.
104 let entry_raw: *u8 = sys_mmap(16)
105 let entry: *LRUEntry = entry_raw as *LRUEntry
106 entry.key = key
107 entry.val = val
108 let node: *DNode = dnode_new(entry_raw)
109 dlist_push_front(c.order, node)
110 map_insert(c.m, key, node as i64)
111 c.size = c.size + 1
112 return 0
113}
114
115// Explicit delete. Returns 1 if found + removed.
116func lru_delete(c: *LRU, key: i64) -> i64 {
117 let node_ptr_raw: *i64 = (sys_mmap(16)) as *i64
118 let hit: i64 = map_get(c.m, key, node_ptr_raw)
119 if hit == 0 { return 0 }
120 let node: *DNode = (*node_ptr_raw) as *DNode
121 dlist_remove(node)
122 map_remove(c.m, key)
123 c.size = c.size - 1
124 return 1
125}
126
127// Size inspector.
128func lru_size(c: *LRU) -> i64 {
129 return c.size
130}
131
132// Compile-only smoke.
133func main() -> i64 {
134 let c: *LRU = lru_new(3)
135 if lru_size(c) != 0 { return 1 }
136
137 lru_put(c, 1, 100)
138 lru_put(c, 2, 200)
139 lru_put(c, 3, 300)
140 if lru_size(c) != 3 { return 2 }
141
142 let out: *i64 = (sys_mmap(16)) as *i64
143 if lru_get(c, 2, out) != 1 { return 3 }
144 if *out != 200 { return 4 }
145
146 // Now order from front: 2, 3, 1. Adding 4 evicts 1.
147 lru_put(c, 4, 400)
148 if lru_size(c) != 3 { return 5 }
149 if lru_get(c, 1, out) != 0 { return 6 }
150
151 // 4 is present.
152 if lru_get(c, 4, out) != 1 { return 7 }
153 if *out != 400 { return 8 }
154
155 // Update existing: should not change size.
156 lru_put(c, 2, 222)
157 if lru_size(c) != 3 { return 9 }
158 lru_get(c, 2, out)
159 if *out != 222 { return 10 }
160
161 // Delete.
162 if lru_delete(c, 2) != 1 { return 11 }
163 if lru_size(c) != 2 { return 12 }
164 if lru_get(c, 2, out) != 0 { return 13 }
165
166 return 0
167}