`dlist.nx` source

↩ module page · 159 lines · 4365 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
30import "syscalls.nx"
31
32struct DNode {
33    prev: *DNode,
34    next: *DNode,
35    data: *u8,    // arbitrary payload pointer
36}
37
38struct DList {
39    sentinel: *DNode,
40}
41
42// Allocate a fresh empty list.
43func dlist_new() -> *DList {
44    let lst_raw: *u8 = sys_mmap(16)
45    let L: *DList = lst_raw as *DList
46    let s_raw: *u8 = sys_mmap(32)
47    let s: *DNode = s_raw as *DNode
48    s.prev = s
49    s.next = s
50    s.data = 0 as *u8
51    L.sentinel = s
52    return L
53}
54
55// Allocate a node holding `data`.
56func dnode_new(data: *u8) -> *DNode {
57    let raw: *u8 = sys_mmap(32)
58    let n: *DNode = raw as *DNode
59    n.prev = 0 as *DNode
60    n.next = 0 as *DNode
61    n.data = data
62    return n
63}
64
65func dlist_empty(L: *DList) -> i64 {
66    let s: *DNode = L.sentinel
67    if s.next == s { return 1 }
68    return 0
69}
70
71// Insert `n` immediately after `pos`.
72func dlist_insert_after(pos: *DNode, n: *DNode) -> i64 {
73    n.prev = pos
74    n.next = pos.next
75    pos.next.prev = n
76    pos.next = n
77    return 0
78}
79
80// Insert at head (after sentinel).
81func dlist_push_front(L: *DList, n: *DNode) -> i64 {
82    return dlist_insert_after(L.sentinel, n)
83}
84
85// Insert at tail (after sentinel.prev == current last).
86func dlist_push_back(L: *DList, n: *DNode) -> i64 {
87    return dlist_insert_after(L.sentinel.prev, n)
88}
89
90// Unlink a node.  Node's prev/next not cleared.
91func dlist_remove(n: *DNode) -> i64 {
92    n.prev.next = n.next
93    n.next.prev = n.prev
94    return 0
95}
96
97// Move an existing node to the front (LRU hit).
98func dlist_move_to_front(L: *DList, n: *DNode) -> i64 {
99    dlist_remove(n)
100    dlist_push_front(L, n)
101    return 0
102}
103
104// Pop head; NULL if empty.
105func dlist_pop_front(L: *DList) -> *DNode {
106    if dlist_empty(L) == 1 { return 0 as *DNode }
107    let n: *DNode = L.sentinel.next
108    dlist_remove(n)
109    return n
110}
111
112// Pop tail; NULL if empty.
113func dlist_pop_back(L: *DList) -> *DNode {
114    if dlist_empty(L) == 1 { return 0 as *DNode }
115    let n: *DNode = L.sentinel.prev
116    dlist_remove(n)
117    return n
118}
119
120// Iteration entry points.
121func dlist_begin(L: *DList) -> *DNode {
122    return L.sentinel.next
123}
124
125func dlist_end(L: *DList) -> *DNode {
126    return L.sentinel
127}
128
129// Compile-only smoke.
130func main() -> i64 {
131    let L: *DList = dlist_new()
132    if dlist_empty(L) != 1 { return 1 }
133
134    let a: *DNode = dnode_new("a" as *u8)
135    let b: *DNode = dnode_new("b" as *u8)
136    let c: *DNode = dnode_new("c" as *u8)
137
138    dlist_push_back(L, a)
139    dlist_push_back(L, b)
140    dlist_push_back(L, c)
141    if dlist_empty(L) != 0 { return 2 }
142
143    let head: *DNode = dlist_begin(L)
144    if head.data[0] != 0x61 { return 3 }
145
146    dlist_move_to_front(L, b)
147    let new_head: *DNode = dlist_begin(L)
148    if new_head.data[0] != 0x62 { return 4 }
149
150    let tail: *DNode = dlist_pop_back(L)
151    if tail.data[0] != 0x63 { return 5 }
152
153    let first: *DNode = dlist_pop_front(L)
154    if first.data[0] != 0x62 { return 6 }
155    let second: *DNode = dlist_pop_front(L)
156    if second.data[0] != 0x61 { return 7 }
157    if dlist_empty(L) != 1 { return 8 }
158    return 0
159}
dlist.nx source

`dlist.nx` source
