mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

	Commit message (Expand)	Author	Age	Files	Lines
*	.	Kartik Agaram	2021-03-29	1	-2/+2
*	.	Kartik K. Agaram	2021-03-08	1	-2/+1
*	7846	Kartik K. Agaram	2021-03-04	1	-4/+5
*	7842 - new directory organization	Kartik K. Agaram	2021-03-03	1	-0/+33

# 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 [ local-scope 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 [ local-scope 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 [ local-scope 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 [ local-scope 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 [ local-scope 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 [ local-scope 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 ] ]