1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
# A doubly linked list permits bidirectional traversal.
container duplex-list [
value:location
next:address:duplex-list
prev:address:duplex-list
]
# result:address:duplex-list <- push-duplex x:location, in:address:duplex-list
recipe push-duplex [
default-space:address:array:location <- new location:type, 30:literal
x:location <- next-ingredient
in:address:duplex-list <- next-ingredient
result:address:duplex-list <- new duplex-list:type
val:address:location <- get-address result:address:duplex-list/deref, value:offset
val:address:location/deref <- copy x:location
next:address:address:duplex-list <- get-address result:address:duplex-list/deref, next:offset
next:address:address:duplex-list/deref <- copy in:address:duplex-list
prev:address:address:duplex-list <- get-address in:address:duplex-list/deref, prev:offset
prev:address:address:duplex-list/deref <- copy result:address:duplex-list
reply result:address:duplex-list
]
# result:location <- first-duplex in:address:duplex-list
recipe first-duplex [
default-space:address:array:location <- new location:type, 30:literal
in:address:duplex-list <- next-ingredient
result:location <- get in:address:duplex-list/deref, value:offset
reply result:location
]
# result:address:duplex-list <- next-duplex in:address:duplex-list
recipe next-duplex [
default-space:address:array:location <- new location:type, 30:literal
in:address:duplex-list <- next-ingredient
result:address:duplex-list <- get in:address:duplex-list/deref, next:offset
reply result:address:duplex-list
]
# result:address:duplex-list <- prev-duplex in:address:duplex-list
recipe prev-duplex [
default-space:address:array:location <- new location:type, 30:literal
in:address:duplex-list <- next-ingredient
result:address:duplex-list <- get in:address:duplex-list/deref, prev:offset
reply result:address:duplex-list
]
scenario duplex-list-handling [
run [
1:address:duplex-list <- copy 0:literal
1:address:duplex-list <- push-duplex 3:literal, 1:address:duplex-list
1:address:duplex-list <- push-duplex 4:literal, 1:address:duplex-list
1:address:duplex-list <- push-duplex 5:literal, 1:address:duplex-list
2:address:duplex-list <- copy 1:address:duplex-list
3:number <- first 2:address:duplex-list
2:address:duplex-list <- next-duplex 2:address:duplex-list
4:number <- first 2:address:duplex-list
2:address:duplex-list <- next-duplex 2:address:duplex-list
5:number <- first 2:address:duplex-list
2:address:duplex-list <- prev-duplex 2:address:duplex-list
6:number <- first 2:address:duplex-list
2:address:duplex-list <- prev-duplex 2:address:duplex-list
7:number <- first 2:address:duplex-list
8:boolean <- equal 1:address:duplex-list, 2:address:duplex-list
]
memory-should-contain [
3 <- 5 # scanning next
4 <- 4
5 <- 3
6 <- 4 # then prev
7 <- 5
8 <- 1 # list back at start
]
]
# l:address:duplex-list <- insert-duplex x:location, in:address:duplex-list
# Inserts 'x' after 'in'. Returns some pointer into the list.
recipe insert-duplex [
default-space:address:array:location <- new location:type, 30:literal
x:location <- next-ingredient
in:address:duplex-list <- next-ingredient
new-node:address:duplex-list <- new duplex-list:type
val:address:location <- get-address new-node:address:duplex-list/deref, value:offset
val:address:location/deref <- copy x:location
next-node:address:duplex-list <- get in:address:duplex-list/deref, next:offset
# in.next = new-node
y:address:address:duplex-list <- get-address in:address:duplex-list/deref, next:offset
y:address:address:duplex-list/deref <- copy new-node:address:duplex-list
# new-node.next = next-node
y:address:address:duplex-list <- get-address new-node:address:duplex-list/deref, next:offset
y:address:address:duplex-list/deref <- copy next-node:address:duplex-list
# next-node.prev = new-node
y:address:address:duplex-list <- get-address next-node:address:duplex-list/deref, prev:offset
y:address:address:duplex-list/deref <- copy new-node:address:duplex-list
# new-node.prev = in
y:address:address:duplex-list <- get-address new-node:address:duplex-list/deref, prev:offset
y:address:address:duplex-list/deref <- copy in:address:duplex-list
reply new-node:address:duplex-list # just signalling something changed; don't rely on the result
]
scenario inserting-into-duplex-list [
run [
1:address:duplex-list <- copy 0:literal # 1 points to head of list
1:address:duplex-list <- push-duplex 3:literal, 1:address:duplex-list
1:address:duplex-list <- push-duplex 4:literal, 1:address:duplex-list
1:address:duplex-list <- push-duplex 5:literal, 1:address:duplex-list
2:address:duplex-list <- next-duplex 1:address:duplex-list # 2 points inside list
2:address:duplex-list <- insert-duplex 6:literal, 2:address:duplex-list
# check structure like before
2:address:duplex-list <- copy 1:address:duplex-list
3:number <- first 2:address:duplex-list
2:address:duplex-list <- next-duplex 2:address:duplex-list
4:number <- first 2:address:duplex-list
2:address:duplex-list <- next-duplex 2:address:duplex-list
5:number <- first 2:address:duplex-list
2:address:duplex-list <- next-duplex 2:address:duplex-list
6:number <- first 2:address:duplex-list
2:address:duplex-list <- prev-duplex 2:address:duplex-list
7:number <- first 2:address:duplex-list
2:address:duplex-list <- prev-duplex 2:address:duplex-list
8:number <- first 2:address:duplex-list
2:address:duplex-list <- prev-duplex 2:address:duplex-list
9:number <- first 2:address:duplex-list
10:boolean <- equal 1:address:duplex-list, 2:address:duplex-list
]
memory-should-contain [
3 <- 5 # scanning next
4 <- 4
5 <- 6 # inserted element
6 <- 3
7 <- 6 # then prev
8 <- 4
9 <- 5
10 <- 1 # list back at start
]
]
|