nx_dlist.nx source
↩ module page · 165 lines · 4460 B
1// dlist.nx -- intrusive doubly-linked list.
2//
3// Each node carries prev/next pointers; list has a sentinel node
4// (heap-allocated) whose prev/next thread the ring. Intrusive:
5// the node pointer is the handle the caller holds, not a wrapper
6// around T. Trade-offs vs std::list-style wrapped list:
7// + O(1) remove given just a node pointer (no search)
8// + one user struct can participate in multiple lists (LRU +
9// pending + free) with separate DNode fields
10// - caller allocates nodes
11//
12// Design note: NishiLang v1 doesn't allow `&struct.field` for
13// inline fields, so DList stores the sentinel as a separately-
14// allocated *DNode rather than an embedded DNode. Small extra
15// alloc at list-construction time only.
16//
17// Used by:
18// - LRU caches (move-to-front, evict tail)
19// - scheduler run queues
20// - free-block chains in allocators
21// - order-preserving map iteration (map + sibling dlist)
22//
23// Invariants:
24// DL1 Empty list: sentinel.next == sentinel.prev == sentinel.
25// DL2 dlist_insert_after + dlist_remove maintain
26// n.next.prev == n for all n.
27// DL3 dlist_remove does NOT free the node -- caller owns
28// lifetime.
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"
37
38struct DNode {
39 prev: *DNode,
40 next: *DNode,
41 data: *u8, // arbitrary payload pointer
42}
43
44struct DList {
45 sentinel: *DNode,
46}
47
48// Allocate a fresh empty list.
49func dlist_new() -> *DList {
50 let lst_raw: *u8 = sys_mmap(16)
51 let L: *DList = lst_raw as *DList
52 let s_raw: *u8 = sys_mmap(32)
53 let s: *DNode = s_raw as *DNode
54 s.prev = s
55 s.next = s
56 s.data = 0 as *u8
57 L.sentinel = s
58 return L
59}
60
61// Allocate a node holding `data`.
62func dnode_new(data: *u8) -> *DNode {
63 let raw: *u8 = sys_mmap(32)
64 let n: *DNode = raw as *DNode
65 n.prev = 0 as *DNode
66 n.next = 0 as *DNode
67 n.data = data
68 return n
69}
70
71func dlist_empty(L: *DList) -> i64 {
72 let s: *DNode = L.sentinel
73 if s.next == s { return 1 }
74 return 0
75}
76
77// Insert `n` immediately after `pos`.
78func dlist_insert_after(pos: *DNode, n: *DNode) -> i64 {
79 n.prev = pos
80 n.next = pos.next
81 pos.next.prev = n
82 pos.next = n
83 return 0
84}
85
86// Insert at head (after sentinel).
87func dlist_push_front(L: *DList, n: *DNode) -> i64 {
88 return dlist_insert_after(L.sentinel, n)
89}
90
91// Insert at tail (after sentinel.prev == current last).
92func dlist_push_back(L: *DList, n: *DNode) -> i64 {
93 return dlist_insert_after(L.sentinel.prev, n)
94}
95
96// Unlink a node. Node's prev/next not cleared.
97func dlist_remove(n: *DNode) -> i64 {
98 n.prev.next = n.next
99 n.next.prev = n.prev
100 return 0
101}
102
103// Move an existing node to the front (LRU hit).
104func dlist_move_to_front(L: *DList, n: *DNode) -> i64 {
105 dlist_remove(n)
106 dlist_push_front(L, n)
107 return 0
108}
109
110// Pop head; NULL if empty.
111func dlist_pop_front(L: *DList) -> *DNode {
112 if dlist_empty(L) == 1 { return 0 as *DNode }
113 let n: *DNode = L.sentinel.next
114 dlist_remove(n)
115 return n
116}
117
118// Pop tail; NULL if empty.
119func dlist_pop_back(L: *DList) -> *DNode {
120 if dlist_empty(L) == 1 { return 0 as *DNode }
121 let n: *DNode = L.sentinel.prev
122 dlist_remove(n)
123 return n
124}
125
126// Iteration entry points.
127func dlist_begin(L: *DList) -> *DNode {
128 return L.sentinel.next
129}
130
131func dlist_end(L: *DList) -> *DNode {
132 return L.sentinel
133}
134
135// Compile-only smoke.
136func main() -> i64 {
137 let L: *DList = dlist_new()
138 if dlist_empty(L) != 1 { return 1 }
139
140 let a: *DNode = dnode_new("a" as *u8)
141 let b: *DNode = dnode_new("b" as *u8)
142 let c: *DNode = dnode_new("c" as *u8)
143
144 dlist_push_back(L, a)
145 dlist_push_back(L, b)
146 dlist_push_back(L, c)
147 if dlist_empty(L) != 0 { return 2 }
148
149 let head: *DNode = dlist_begin(L)
150 if head.data[0] != 0x61 { return 3 }
151
152 dlist_move_to_front(L, b)
153 let new_head: *DNode = dlist_begin(L)
154 if new_head.data[0] != 0x62 { return 4 }
155
156 let tail: *DNode = dlist_pop_back(L)
157 if tail.data[0] != 0x63 { return 5 }
158
159 let first: *DNode = dlist_pop_front(L)
160 if first.data[0] != 0x62 { return 6 }
161 let second: *DNode = dlist_pop_front(L)
162 if second.data[0] != 0x61 { return 7 }
163 if dlist_empty(L) != 1 { return 8 }
164 return 0
165}