From 00ee2decfe597212091e8d282232950055405635 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Thu, 18 Jun 2015 10:41:14 -0700 Subject: 1590 - inserting into doubly linked list --- 065duplex_list.mu | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 62 insertions(+) (limited to '065duplex_list.mu') 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 + ] +] -- cgit 1.4.1-2-gfad0