about summary refs log tree commit diff stats
diff options
context:
space:
mode:
authorKartik K. Agaram <vc@akkartik.com>2015-06-18 10:41:14 -0700
committerKartik K. Agaram <vc@akkartik.com>2015-06-18 10:41:14 -0700
commit00ee2decfe597212091e8d282232950055405635 (patch)
tree77f052270e7ceaaded52d79d8ed0887b58d1de84
parent1eb8617cceada1220ee8f494bc5aaa29fcceff48 (diff)
downloadmu-00ee2decfe597212091e8d282232950055405635.tar.gz
1590 - inserting into doubly linked list
-rw-r--r--065duplex_list.mu62
1 files changed, 62 insertions, 0 deletions
diff --git a/065duplex_list.mu b/065duplex_list.mu
index b63e2ef7..8c5f6011 100644
--- a/065duplex_list.mu
+++ b/065duplex_list.mu
@@ -72,3 +72,65 @@ scenario duplex-list-handling [
     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
+  ]
+]