From dbe124108b7a3529feeeba91339928c4ac737072 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Tue, 23 Jun 2015 14:02:12 -0700 Subject: 1631 - update html versions Html is a little more readable thanks to feedback from J David Eisenberg (https://news.ycombinator.com/item?id=9766330), in particular the suggestion to use https://addons.mozilla.org/En-us/firefox/addon/wcag-contrast-checker. --- html/065duplex_list.mu.html | 407 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 407 insertions(+) create mode 100644 html/065duplex_list.mu.html (limited to 'html/065duplex_list.mu.html') diff --git a/html/065duplex_list.mu.html b/html/065duplex_list.mu.html new file mode 100644 index 00000000..6f81c5fa --- /dev/null +++ b/html/065duplex_list.mu.html @@ -0,0 +1,407 @@ + + + + +Mu - 065duplex_list.mu + + + + + + + + + + +
+# 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
+  reply-unless in:address:duplex-list, result: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
+  reply-unless in:address:duplex-list, 0:literal
+  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
+  reply-unless in:address:duplex-list, 0:literal
+  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
+  reply-unless in:address:duplex-list, 0:literal
+  result:address:duplex-list <- get in:address:duplex-list/deref, prev:offset
+  reply result:address:duplex-list
+]
+
+scenario duplex-list-handling [
+  run [
+    # reserve locations 0, 1 and 2 to check for missing null check
+    1:number <- copy 34:literal
+    2:number <- copy 35:literal
+    3:address:duplex-list <- copy 0:literal
+    3:address:duplex-list <- push-duplex 3:literal, 3:address:duplex-list
+    3:address:duplex-list <- push-duplex 4:literal, 3:address:duplex-list
+    3:address:duplex-list <- push-duplex 5:literal, 3:address:duplex-list
+    4:address:duplex-list <- copy 3:address:duplex-list
+    5:number <- first 4:address:duplex-list
+    4:address:duplex-list <- next-duplex 4:address:duplex-list
+    6:number <- first 4:address:duplex-list
+    4:address:duplex-list <- next-duplex 4:address:duplex-list
+    7:number <- first 4:address:duplex-list
+    8:address:duplex-list <- next-duplex 4:address:duplex-list
+    9:number <- first 8:address:duplex-list
+    10:address:duplex-list <- next-duplex 8:address:duplex-list
+    11:address:duplex-list <- prev-duplex 8:address:duplex-list
+    4:address:duplex-list <- prev-duplex 4:address:duplex-list
+    12:number <- first 4:address:duplex-list
+    4:address:duplex-list <- prev-duplex 4:address:duplex-list
+    13:number <- first 4:address:duplex-list
+    14:boolean <- equal 3:address:duplex-list, 4:address:duplex-list
+#?     $dump-trace #? 1
+  ]
+  memory-should-contain [
+    0 <- 0  # no modifications to null pointers
+    1 <- 34
+    2 <- 35
+    5 <- 5  # scanning next
+    6 <- 4
+    7 <- 3
+    8 <- 0  # null
+    9 <- 0  # first of null
+    10 <- 0  # next of null
+    11 <- 0  # prev of null
+    12 <- 4  # then start scanning prev
+    13 <- 5
+    14 <- 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.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
+  # 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
+  # if next-node is not null
+  reply-unless next-node:address:duplex-list, new-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
+  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
+  ]
+]
+
+scenario inserting-at-end-of-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 <- next-duplex 2:address:duplex-list  # now at end of 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 <- 3
+    6 <- 6  # inserted element
+    7 <- 3  # then prev
+    8 <- 4
+    9 <- 5
+    10 <- 1  # list back at start
+  ]
+]
+
+scenario inserting-after-start-of-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 <- insert-duplex 6:literal, 1: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 <- 6  # inserted element
+    5 <- 4
+    6 <- 3
+    7 <- 4  # then prev
+    8 <- 6
+    9 <- 5
+    10 <- 1  # list back at start
+  ]
+]
+
+# l:address:duplex-list <- remove-duplex in:address:duplex-list
+# Removes 'in' from its surrounding list. Returns some valid pointer into the
+# rest of the list.
+#
+# Returns null if and only if list is empty. Beware: in that case any pointers
+# to the head are now invalid.
+recipe remove-duplex [
+  default-space:address:array:location <- new location:type, 30:literal
+  in:address:duplex-list <- next-ingredient
+  # if 'in' is null, return
+  reply-unless in:address:duplex-list, in:address:duplex-list
+  next-node:address:duplex-list <- get in:address:duplex-list/deref, next:offset
+  prev-node:address:duplex-list <- get in:address:duplex-list/deref, prev:offset
+  # null in's pointers
+  x:address:address:duplex-list <- get-address in:address:duplex-list/deref, next:offset
+  x:address:address:duplex-list/deref <- copy 0:literal
+  x:address:address:duplex-list <- get-address in:address:duplex-list/deref, prev:offset
+  x:address:address:duplex-list/deref <- copy 0:literal
+  {
+    # if next-node is not null
+    break-unless next-node:address:duplex-list
+    # next-node.prev = prev-node
+    x:address:address:duplex-list <- get-address next-node:address:duplex-list/deref, prev:offset
+    x:address:address:duplex-list/deref <- copy prev-node:address:duplex-list
+  }
+  {
+    # if prev-node is not null
+    break-unless prev-node:address:duplex-list
+    # prev-node.next = next-node
+    x:address:address:duplex-list <- get-address prev-node:address:duplex-list/deref, next:offset
+    x:address:address:duplex-list/deref <- copy next-node:address:duplex-list
+    reply prev-node:address:duplex-list
+  }
+  reply next-node:address:duplex-list
+]
+
+scenario removing-from-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 at second element
+    2:address:duplex-list <- remove-duplex 2:address:duplex-list
+    3:boolean <- equal 2:address:duplex-list, 0:literal
+    # check structure like before
+    2:address:duplex-list <- copy 1: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
+    6:address:duplex-list <- next-duplex 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 <- 0  # remove returned non-null
+    4 <- 5  # scanning next, skipping deleted element
+    5 <- 3
+    6 <- 0  # no more elements
+    7 <- 5  # prev of final element
+    8 <- 1  # list back at start
+  ]
+]
+
+scenario removing-from-start-of-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
+    # removing from head? return value matters.
+    1:address:duplex-list <- remove-duplex 1: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
+    5:address:duplex-list <- next-duplex 2:address:duplex-list
+    2:address:duplex-list <- prev-duplex 2:address:duplex-list
+    6:number <- first 2:address:duplex-list
+    7:boolean <- equal 1:address:duplex-list, 2:address:duplex-list
+  ]
+  memory-should-contain [
+    3 <- 4  # scanning next, skipping deleted element
+    4 <- 3
+    5 <- 0  # no more elements
+    6 <- 4  # prev of final element
+    7 <- 1  # list back at start
+  ]
+]
+
+scenario removing-from-end-of-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
+    # delete last element
+    2:address:duplex-list <- next-duplex 1:address:duplex-list
+    2:address:duplex-list <- next-duplex 2:address:duplex-list
+    2:address:duplex-list <- remove-duplex 2:address:duplex-list
+    3:boolean <- equal 2:address:duplex-list, 0:literal
+    # check structure like before
+    2:address:duplex-list <- copy 1: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
+    6:address:duplex-list <- next-duplex 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 <- 0  # remove returned non-null
+    4 <- 5  # scanning next, skipping deleted element
+    5 <- 4
+    6 <- 0  # no more elements
+    7 <- 5  # prev of final element
+    8 <- 1  # list back at start
+  ]
+]
+
+scenario removing-from-singleton-list [
+  run [
+    1:address:duplex-list <- copy 0:literal  # 1 points to singleton list
+    1:address:duplex-list <- push-duplex 3:literal, 1:address:duplex-list
+    2:address:duplex-list <- remove-duplex 1:address:duplex-list
+    3:address:duplex-list <- get 1:address:duplex-list/deref, next:offset
+    4:address:duplex-list <- get 1:address:duplex-list/deref, prev:offset
+  ]
+  memory-should-contain [
+    2 <- 0  # remove returned null
+    3 <- 0  # removed node is also detached
+    4 <- 0
+  ]
+]
+
+ + + -- cgit 1.4.1-2-gfad0