1 # A doubly linked list permits bidirectional traversal.
  2 
  3 container duplex-list:_elem [
  4   value:_elem
  5   next:&:duplex-list:_elem
  6   prev:&:duplex-list:_elem
  7 ]
  8 
  9 def push x:_elem, in:&:duplex-list:_elem/contained-in:result -> result:&:duplex-list:_elem [
 10   local-scope
 11   load-inputs
 12   result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 13   *result <- merge x, in, null
 14   return-unless in
 15   put *in, prev:offset, result
 16 ]
 17 
 18 def first in:&:duplex-list:_elem -> result:_elem [
 19   local-scope
 20   load-inputs
 21   {
 22     break-if in
 23     zero:&:_elem <- new _elem:type
 24     zero-result:_elem <- copy *zero
 25     abandon zero
 26     return zero-result
 27   }
 28   result <- get *in, value:offset
 29 ]
 30 
 31 def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 32   local-scope
 33   load-inputs
 34   return-unless in, null
 35   result <- get *in, next:offset
 36 ]
 37 
 38 def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 39   local-scope
 40   load-inputs
 41   return-unless in, null
 42   result <- get *in, prev:offset
 43   return result
 44 ]
 45 
 46 scenario duplex-list-handling [
 47   run [
 48     local-scope
 49     # reserve locations 0-9 to check for missing null check
 50     10:num/raw <- copy 34
 51     11:num/raw <- copy 35
 52     list:&:duplex-list:num <- push 3, null
 53     list <- push 4, list
 54     list <- push 5, list
 55     list2:&:duplex-list:num <- copy list
 56     20:num/raw <- first list2
 57     list2 <- next list2
 58     21:num/raw <- first list2
 59     list2 <- next list2
 60     22:num/raw <- first list2
 61     30:&:duplex-list:num/raw <- next list2
 62     31:num/raw <- first 30:&:duplex-list:num/raw
 63     32:&:duplex-list:num/raw <- next 30:&:duplex-list:num/raw
 64     33:&:duplex-list:num/raw <- prev 30:&:duplex-list:num/raw
 65     list2 <- prev list2
 66     40:num/raw <- first list2
 67     list2 <- prev list2
 68     41:num/raw <- first list2
 69     50:bool/raw <- equal list, list2
 70   ]
 71   memory-should-contain [
 72     0 <- 0  # no modifications to null pointers
 73     10 <- 34
 74     11 <- 35
 75     20 <- 5  # scanning next
 76     21 <- 4
 77     22 <- 3
 78     30 <- 0  # null
 79     31 <- 0  # first of null
 80     32 <- 0  # next of null
 81     33 <- 0  # prev of null
 82     40 <- 4  # then start scanning prev
 83     41 <- 5
 84     50 <- 1  # list back at start
 85   ]
 86 ]
 87 
 88 def length l:&:duplex-list:_elem -> result:num [
 89   local-scope
 90   load-inputs
 91   result <- copy 0
 92   {
 93     break-unless l
 94     result <- add result, 1
 95     l <- next l
 96     loop
 97   }
 98 ]
 99 
100 # insert 'x' after 'in'
101 def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
102   local-scope
103   load-inputs
104   new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
105   *new-node <- put *new-node, value:offset, x
106   # save old next before changing it
107   next-node:&:duplex-list:_elem <- get *in, next:offset
108   *in <- put *in, next:offset, new-node
109   *new-node <- put *new-node, prev:offset, in
110   *new-node <- put *new-node, next:offset, next-node
111   return-unless next-node
112   *next-node <- put *next-node, prev:offset, new-node
113 ]
114 
115 scenario inserting-into-duplex-list [
116   local-scope
117   list:&:duplex-list:num <- push 3, null
118   list <- push 4, list
119   list <- push 5, list
120   run [
121     list2:&:duplex-list:num <- next list  # inside list
122     list2 <- insert 6, list2
123     # check structure like before
124     list2 <- copy list
125     10:num/raw <- first list2
126     list2 <- next list2
127     11:num/raw <- first list2
128     list2 <- next list2
129     12:num/raw <- first list2
130     list2 <- next list2
131     13:num/raw <- first list2
132     list2 <- prev list2
133     20:num/raw <- first list2
134     list2 <- prev list2
135     21:num/raw <- first list2
136     list2 <- prev list2
137     22:num/raw <- first list2
138     30:bool/raw <- equal list, list2
139   ]
140   memory-should-contain [
141     10 <- 5  # scanning next
142     11 <- 4
143     12 <- 6  # inserted element
144     13 <- 3
145     20 <- 6  # then prev
146     21 <- 4
147     22 <- 5
148     30 <- 1  # list back at start
149   ]
150 ]
151 
152 scenario inserting-at-end-of-duplex-list [
153   local-scope
154   list:&:duplex-list:num <- push 3, null
155   list <- push 4, list
156   list <- push 5, list
157   run [
158     list2:&:duplex-list:num <- next list  # inside list
159     list2 <- next list2  # now at end of list
160     list2 <- insert 6, list2
161     # check structure like before
162     list2 <- copy list
163     10:num/raw <- first list2
164     list2 <- next list2
165     11:num/raw <- first list2
166     list2 <- next list2
167     12:num/raw <- first list2
168     list2 <- next list2
169     13:num/raw <- first list2
170     list2 <- prev list2
171     20:num/raw <- first list2
172     list2 <- prev list2
173     21:num/raw <- first list2
174     list2 <- prev list2
175     22:num/raw <- first list2
176     30:bool/raw <- equal list, list2
177   ]
178   memory-should-contain [
179     10 <- 5  # scanning next
180     11 <- 4
181     12 <- 3
182     13 <- 6  # inserted element
183     20 <- 3  # then prev
184     21 <- 4
185     22 <- 5
186     30 <- 1  # list back at start
187   ]
188 ]
189 
190 scenario inserting-after-start-of-duplex-list [
191   local-scope
192   list:&:duplex-list:num <- push 3, null
193   list <- push 4, list
194   list <- push 5, list
195   run [
196     list <- insert 6, list
197     # check structure like before
198     list2:&:duplex-list:num <- copy list
199     10:num/raw <- first list2
200     list2 <- next list2
201     11:num/raw <- first list2
202     list2 <- next list2
203     12:num/raw <- first list2
204     list2 <- next list2
205     13:num/raw <- first list2
206     list2 <- prev list2
207     20:num/raw <- first list2
208     list2 <- prev list2
209     21:num/raw <- first list2
210     list2 <- prev list2
211     22:num/raw <- first list2
212     30:bool/raw <- equal list, list2
213   ]
214   memory-should-contain [
215     10 <- 5  # scanning next
216     11 <- 6  # inserted element
217     12 <- 4
218     13 <- 3
219     20 <- 4  # then prev
220     21 <- 6
221     22 <- 5
222     30 <- 1  # list back at start
223   ]
224 ]
225 
226 # remove 'x' from its surrounding list 'in'
227 #
228 # Returns null if and only if list is empty. Beware: in that case any other
229 # pointers to the head are now invalid.
230 def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
231   local-scope
232   load-inputs
233   # if 'x' is null, return
234   return-unless x
235   next-node:&:duplex-list:_elem <- get *x, next:offset
236   prev-node:&:duplex-list:_elem <- get *x, prev:offset
237   # null x's pointers
238   *x <- put *x, next:offset, null
239   *x <- put *x, prev:offset, null
240   # if next-node is not null, set its prev pointer
241   {
242     break-unless next-node
243     *next-node <- put *next-node, prev:offset, prev-node
244   }
245   # if prev-node is not null, set its next pointer and return
246   {
247     break-unless prev-node
248     *prev-node <- put *prev-node, next:offset, next-node
249     return
250   }
251   # if prev-node is null, then we removed the head node at 'in'
252   # return the new head rather than the old 'in'
253   return next-node
254 ]
255 
256 scenario removing-from-duplex-list [
257   local-scope
258   list:&:duplex-list:num <- push 3, null
259   list <- push 4, list
260   list <- push 5, list
261   run [
262     list2:&:duplex-list:num <- next list  # second element
263     list <- remove list2, list
264     10:bool/raw <- equal list2, null
265     # check structure like before
266     list2 <- copy list
267     11:num/raw <- first list2
268     list2 <- next list2
269     12:num/raw <- first list2
270     20:&:duplex-list:num/raw <- next list2
271     list2 <- prev list2
272     30:num/raw <- first list2
273     40:bool/raw <- equal list, list2
274   ]
275   memory-should-contain [
276     10 <- 0  # remove returned non-null
277     11 <- 5  # scanning next, skipping deleted element
278     12 <- 3
279     20 <- 0  # no more elements
280     30 <- 5  # prev of final element
281     40 <- 1  # list back at start
282   ]
283 ]
284 
285 scenario removing-from-start-of-duplex-list [
286   local-scope
287   list:&:duplex-list:num <- push 3, null
288   list <- push 4, list
289   list <- push 5, list
290   run [
291     list <- remove list, list
292     # check structure like before
293     list2:&:duplex-list:num <- copy list
294     10:num/raw <- first list2
295     list2 <- next list2
296     11:num/raw <- first list2
297     20:&:duplex-list:num/raw <- next list2
298     list2 <- prev list2
299     30:num/raw <- first list2
300     40:bool/raw <- equal list, list2
301   ]
302   memory-should-contain [
303     10 <- 4  # scanning next, skipping deleted element
304     11 <- 3
305     20 <- 0  # no more elements
306     30 <- 4  # prev of final element
307     40 <- 1  # list back at start
308   ]
309 ]
310 
311 scenario removing-from-end-of-duplex-list [
312   local-scope
313   list:&:duplex-list:num <- push 3, null
314   list <- push 4, list
315   list <- push 5, list
316   run [
317     # delete last element
318     list2:&:duplex-list:num <- next list
319     list2 <- next list2
320     list <- remove list2, list
321     10:bool/raw <- equal list2, null
322     # check structure like before
323     list2 <- copy list
324     11:num/raw <- first list2
325     list2 <- next list2
326     12:num/raw <- first list2
327     20:&:duplex-list:num/raw <- next list2
328     list2 <- prev list2
329     30:num/raw <- first list2
330     40:bool/raw <- equal list, list2
331   ]
332   memory-should-contain [
333     10 <- 0  # remove returned non-null
334     11 <- 5  # scanning next, skipping deleted element
335     12 <- 4
336     20 <- 0  # no more elements
337     30 <- 5  # prev of final element
338     40 <- 1  # list back at start
339   ]
340 ]
341 
342 scenario removing-from-singleton-duplex-list [
343   local-scope
344   list:&:duplex-list:num <- push 3, null
345   run [
346     list <- remove list, list
347     1:num/raw <- deaddress list
348   ]
349   memory-should-contain [
350     1 <- 0  # back to an empty list
351   ]
352 ]
353 
354 def remove x:&:duplex-list:_elem/contained-in:in, n:num, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
355   local-scope
356   load-inputs
357   i:num <- copy 0
358   curr:&:duplex-list:_elem <- copy x
359   {
360     done?:bool <- greater-or-equal i, n
361     break-if done?
362     break-unless curr
363     next:&:duplex-list:_elem <- next curr
364     in <- remove curr, in
365     curr <- copy next
366     i <- add i, 1
367     loop
368   }
369 ]
370 
371 scenario removing-multiple-from-duplex-list [
372   local-scope
373   list:&:duplex-list:num <- push 3, null
374   list <- push 4, list
375   list <- push 5, list
376   run [
377     list2:&:duplex-list:num <- next list  # second element
378     list <- remove list2, 2, list
379     stash list
380   ]
381   trace-should-contain [
382     app: 5
383   ]
384 ]
385 
386 # remove values between 'start' and 'end' (both exclusive).
387 # also clear pointers back out from start/end for hygiene.
388 # set end to 0 to delete everything past start.
389 # can't set start to 0 to delete everything before end, because there's no
390 # clean way to return the new head pointer.
391 def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
392   local-scope
393   load-inputs
394   next:&:duplex-list:_elem <- get *start, next:offset
395   nothing-to-delete?:bool <- equal next, end
396   return-if nothing-to-delete?
397   assert next, [malformed duplex list]
398   # start->next->prev = 0
399   # start->next = end
400   *next <- put *next, prev:offset, null
401   *start <- put *start, next:offset, end
402   {
403     break-if end
404     stash [spliced:] next
405     return
406   }
407   # end->prev->next = 0
408   # end->prev = start
409   prev:&:duplex-list:_elem <- get *end, prev:offset
410   assert prev, [malformed duplex list - 2]
411   *prev <- put *prev, next:offset, null
412   stash [spliced:] next
413   *end <- put *end, prev:offset, start
414 ]
415 
416 scenario remove-range [
417   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
418   local-scope
419   list:&:duplex-list:num <- push 18, null
420   list <- push 17, list
421   list <- push 16, list
422   list <- push 15, list
423   list <- push 14, list
424   list <- push 13, list
425   run [
426     # delete 16 onwards
427     # first pointer: to the third element
428     list2:&:duplex-list:num <- next list
429     list2 <- next list2
430     list2 <- remove-between list2, null
431     # now check the list
432     10:num/raw <- get *list, value:offset
433     list <- next list
434     11:num/raw <- get *list, value:offset
435     list <- next list
436     12:num/raw <- get *list, value:offset
437     20:&:duplex-list:num/raw <- next list
438   ]
439   memory-should-contain [
440     10 <- 13
441     11 <- 14
442     12 <- 15
443     20 <- 0
444   ]
445   trace-should-contain [
446     app: spliced: 16 <-> 17 <-> 18
447   ]
448 ]
449 
450 scenario remove-range-to-final [
451   local-scope
452   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
453   list:&:duplex-list:num <- push 18, null
454   list <- push 17, list
455   list <- push 16, list
456   list <- push 15, list
457   list <- push 14, list
458   list <- push 13, list
459   run [
460     # delete 15, 16 and 17
461     # start pointer: to the second element
462     list2:&:duplex-list:num <- next list
463     # end pointer: to the last (sixth) element
464     end:&:duplex-list:num <- next list2
465     end <- next end
466     end <- next end
467     end <- next end
468     remove-between list2, end
469     # now check the list
470     10:num/raw <- get *list, value:offset
471     list <- next list
472     11:num/raw <- get *list, value:offset
473     list <- next list
474     12:num/raw <- get *list, value:offset
475     20:&:duplex-list:num/raw <- next list
476   ]
477   memory-should-contain [
478     10 <- 13
479     11 <- 14
480     12 <- 18
481     20 <- 0  # no more elements
482   ]
483   trace-should-contain [
484     app: spliced: 15 <-> 16 <-> 17
485   ]
486 ]
487 
488 scenario remove-range-to-penultimate [
489   local-scope
490   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
491   list:&:duplex-list:num <- push 18, null
492   list <- push 17, list
493   list <- push 16, list
494   list <- push 15, list
495   list <- push 14, list
496   list <- push 13, list
497   run [
498     # delete 15 and 16
499     # start pointer: to the second element
500     list2:&:duplex-list:num <- next list
501     # end pointer: to the last (sixth) element
502     end:&:duplex-list:num <- next list2
503     end <- next end
504     end <- next end
505     remove-between list2, end
506     # now check the list
507     10:num/raw <- get *list, value:offset
508     list <- next list
509     11:num/raw <- get *list, value:offset
510     list <- next list
511     12:num/raw <- get *list, value:offset
512     list <- next list
513     13:num/raw <- get *list, value:offset
514     20:&:duplex-list:num/raw <- next list
515   ]
516   memory-should-contain [
517     10 <- 13
518     11 <- 14
519     12 <- 17
520     13 <- 18
521     20 <- 0  # no more elements
522   ]
523   trace-should-contain [
524     app: spliced: 15 <-> 16
525   ]
526 ]
527 
528 scenario remove-range-empty [
529   local-scope
530   # construct a duplex list with three elements [13, 14, 15]
531   list:&:duplex-list:num <- push 15, null
532   list <- push 14, list
533   list <- push 13, list
534   run [
535     # delete between first and second element (i.e. nothing)
536     list2:&:duplex-list:num <- next list
537     remove-between list, list2
538     # now check the list
539     10:num/raw <- get *list, value:offset
540     list <- next list
541     11:num/raw <- get *list, value:offset
542     list <- next list
543     12:num/raw <- get *list, value:offset
544     20:&:duplex-list:num/raw <- next list
545   ]
546   # no change
547   memory-should-contain [
548     10 <- 13
549     11 <- 14
550     12 <- 15
551     20 <- 0
552   ]
553 ]
554 
555 scenario remove-range-to-end [
556   local-scope
557   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
558   list:&:duplex-list:num <- push 18, null
559   list <- push 17, list
560   list <- push 16, list
561   list <- push 15, list
562   list <- push 14, list
563   list <- push 13, list
564   run [
565     # remove the third element and beyond
566     list2:&:duplex-list:num <- next list
567     remove-between list2, null
568     # now check the list
569     10:num/raw <- get *list, value:offset
570     list <- next list
571     11:num/raw <- get *list, value:offset
572     20:&:duplex-list:num/raw <- next list
573   ]
574   memory-should-contain [
575     10 <- 13
576     11 <- 14
577     20 <- 0
578   ]
579 ]
580 
581 # insert list beginning at 'start' after 'in'
582 def splice in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
583   local-scope
584   load-inputs
585   return-unless in
586   return-unless start
587   end:&:duplex-list:_elem <- last start
588   next:&:duplex-list:_elem <- next in
589   {
590     break-unless next
591     *end <- put *end, next:offset, next
592     *next <- put *next, prev:offset, end
593   }
594   *in <- put *in, next:offset, start
595   *start <- put *start, prev:offset, in
596 ]
597 
598 # insert contents of 'new' after 'in'
599 def insert in:&:duplex-list:_elem, new:&:@:_elem -> in:&:duplex-list:_elem [
600   local-scope
601   load-inputs
602   return-unless in
603   return-unless new
604   len:num <- length *new
605   return-unless len
606   curr:&:duplex-list:_elem <- copy in
607   idx:num <- copy 0
608   {
609     done?:bool <- greater-or-equal idx, len
610     break-if done?
611     c:_elem <- index *new, idx
612     insert c, curr
613     # next iter
614     curr <- next curr
615     idx <- add idx, 1
616     loop
617   }
618 ]
619 
620 def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
621   local-scope
622   load-inputs
623   last:&:duplex-list:_elem <- last in
624   *last <- put *last, next:offset, new
625   return-unless new
626   *new <- put *new, prev:offset, last
627 ]
628 
629 def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
630   local-scope
631   load-inputs
632   result <- copy in
633   {
634     next:&:duplex-list:_elem <- next result
635     break-unless next
636     result <- copy next
637     loop
638   }
639 ]
640 
641 # does a duplex list start with a certain sequence of elements?
642 def match x:&:duplex-list:_elem, y:&:@:_elem -> result:bool [
643   local-scope
644   load-inputs
645   i:num <- copy 0
646   max:num <- length *y
647   {
648     done?:bool <- greater-or-equal i, max
649     break-if done?
650     expected:_elem <- index *y, i
651     return-unless x, false/no-match
652     curr:_elem <- first x
653     curr-matches?:bool <- equal curr, expected
654     return-unless curr-matches?, false/no-match
655     x <- next x
656     i <- add i, 1
657     loop
658   }
659   return true/successful-match
660 ]
661 
662 scenario duplex-list-match [
663   local-scope
664   list:&:duplex-list:char <- push 97/a, null
665   list <- push 98/b, list
666   list <- push 99/c, list
667   list <- push 100/d, list
668   run [
669     10:bool/raw <- match list, []
670     11:bool/raw <- match list, [d]
671     12:bool/raw <- match list, [dc]
672     13:bool/raw <- match list, [dcba]
673     14:bool/raw <- match list, [dd]
674     15:bool/raw <- match list, [dcbax]
675   ]
676   memory-should-contain [
677     10 <- 1  # matches []
678     11 <- 1  # matches [d]
679     12 <- 1  # matches [dc]
680     13 <- 1  # matches [dcba]
681     14 <- 0  # does not match [dd]
682     15 <- 0  # does not match [dcbax]
683   ]
684 ]
685 
686 # helper for debugging
687 def dump-from x:&:duplex-list:_elem [
688   local-scope
689   load-inputs
690   $print x, [: ]
691   {
692     break-unless x
693     c:_elem <- get *x, value:offset
694     $print c, [ ]
695     x <- next x
696     {
697       is-newline?:bool <- equal c, 10/newline
698       break-unless is-newline?
699       $print 10/newline
700       $print x, [: ]
701     }
702     loop
703   }
704   $print 10/newline, [---], 10/newline
705 ]
706 
707 scenario stash-duplex-list [
708   local-scope
709   list:&:duplex-list:num <- push 1, null
710   list <- push 2, list
711   list <- push 3, list
712   run [
713     stash [list:], list
714   ]
715   trace-should-contain [
716     app: list: 3 <-> 2 <-> 1
717   ]
718 ]
719 
720 def to-text in:&:duplex-list:_elem -> result:text [
721   local-scope
722   load-inputs
723   buf:&:buffer:char <- new-buffer 80
724   buf <- to-buffer in, buf
725   result <- buffer-to-array buf
726 ]
727 
728 # variant of 'to-text' which stops printing after a few elements (and so is robust to cycles)
729 def to-text-line in:&:duplex-list:_elem -> result:text [
730   local-scope
731   load-inputs
732   buf:&:buffer:char <- new-buffer 80
733   buf <- to-buffer in, buf, 6  # max elements to display
734   result <- buffer-to-array buf
735 ]
736 
737 def to-buffer in:&:duplex-list:_elem, buf:&:buffer:char -> buf:&:buffer:char [
738   local-scope
739   load-inputs
740   {
741     break-if in
742     buf <- append buf, [[]]
743     return
744   }
745   # append in.value to buf
746   val:_elem <- get *in, value:offset
747   buf <- append buf, val
748   # now prepare next
749   next:&:duplex-list:_elem <- next in
750   nextn:num <- deaddress next
751   return-unless next
752   buf <- append buf, [ <-> ]
753   # and recurse
754   remaining:num, optional-input-found?:bool <- next-input
755   {
756     break-if optional-input-found?
757     # unlimited recursion
758     buf <- to-buffer next, buf
759     return
760   }
761   {
762     break-unless remaining
763     # limited recursion
764     remaining <- subtract remaining, 1
765     buf <- to-buffer next, buf, remaining
766     return
767   }
768   # past recursion depth; insert ellipses and stop
769   append buf, [...]
770 ]
771 
772 scenario stash-empty-duplex-list [
773   local-scope
774   x:&:duplex-list:num <- copy null
775   run [
776     stash x
777   ]
778   trace-should-contain [
779     app: []
780   ]
781 ]