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 # should I say in/contained-in:result, allow ingredients to refer to products?
 10 def push x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 11   local-scope
 12   load-ingredients
 13   result:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 14   *result <- merge x, in, 0
 15   {
 16     break-unless in
 17     *in <- put *in, prev:offset, result
 18   }
 19   return result  # needed explicitly because we need to replace 'in' with 'result'
 20 ]
 21 
 22 def first in:&:duplex-list:_elem -> result:_elem [
 23   local-scope
 24   load-ingredients
 25   return-unless in, 0
 26   result <- get *in, value:offset
 27 ]
 28 
 29 def next in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 30   local-scope
 31   load-ingredients
 32   return-unless in, 0
 33   result <- get *in, next:offset
 34 ]
 35 
 36 def prev in:&:duplex-list:_elem -> result:&:duplex-list:_elem/contained-in:in [
 37   local-scope
 38   load-ingredients
 39   return-unless in, 0
 40   result <- get *in, prev:offset
 41   return result
 42 ]
 43 
 44 scenario duplex-list-handling [
 45   run [
 46     local-scope
 47     # reserve locations 0-9 to check for missing null check
 48     10:num/raw <- copy 34
 49     11:num/raw <- copy 35
 50     list:&:duplex-list:char <- push 3, 0
 51     list <- push 4, list
 52     list <- push 5, list
 53     list2:&:duplex-list:char <- copy list
 54     20:char/raw <- first list2
 55     list2 <- next list2
 56     21:char/raw <- first list2
 57     list2 <- next list2
 58     22:char/raw <- first list2
 59     30:&:duplex-list:char/raw <- next list2
 60     31:char/raw <- first 30:&:duplex-list:char/raw
 61     32:&:duplex-list:char/raw <- next 30:&:duplex-list:char/raw
 62     33:&:duplex-list:char/raw <- prev 30:&:duplex-list:char/raw
 63     list2 <- prev list2
 64     40:char/raw <- first list2
 65     list2 <- prev list2
 66     41:char/raw <- first list2
 67     50:bool/raw <- equal list, list2
 68   ]
 69   memory-should-contain [
 70     0 <- 0  # no modifications to null pointers
 71     10 <- 34
 72     11 <- 35
 73     20 <- 5  # scanning next
 74     21 <- 4
 75     22 <- 3
 76     30 <- 0  # null
 77     31 <- 0  # first of null
 78     32 <- 0  # next of null
 79     33 <- 0  # prev of null
 80     40 <- 4  # then start scanning prev
 81     41 <- 5
 82     50 <- 1  # list back at start
 83   ]
 84 ]
 85 
 86 # insert 'x' after 'in'
 87 def insert x:_elem, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
 88   local-scope
 89   load-ingredients
 90   new-node:&:duplex-list:_elem <- new {(duplex-list _elem): type}
 91   *new-node <- put *new-node, value:offset, x
 92   # save old next before changing it
 93   next-node:&:duplex-list:_elem <- get *in, next:offset
 94   *in <- put *in, next:offset, new-node
 95   *new-node <- put *new-node, prev:offset, in
 96   *new-node <- put *new-node, next:offset, next-node
 97   return-unless next-node
 98   *next-node <- put *next-node, prev:offset, new-node
 99 ]
100 
101 scenario inserting-into-duplex-list [
102   local-scope
103   list:&:duplex-list:char <- push 3, 0
104   list <- push 4, list
105   list <- push 5, list
106   run [
107     list2:&:duplex-list:char <- next list  # inside list
108     list2 <- insert 6, list2
109     # check structure like before
110     list2 <- copy list
111     10:char/raw <- first list2
112     list2 <- next list2
113     11:char/raw <- first list2
114     list2 <- next list2
115     12:char/raw <- first list2
116     list2 <- next list2
117     13:char/raw <- first list2
118     list2 <- prev list2
119     20:char/raw <- first list2
120     list2 <- prev list2
121     21:char/raw <- first list2
122     list2 <- prev list2
123     22:char/raw <- first list2
124     30:bool/raw <- equal list, list2
125   ]
126   memory-should-contain [
127     10 <- 5  # scanning next
128     11 <- 4
129     12 <- 6  # inserted element
130     13 <- 3
131     20 <- 6  # then prev
132     21 <- 4
133     22 <- 5
134     30 <- 1  # list back at start
135   ]
136 ]
137 
138 scenario inserting-at-end-of-duplex-list [
139   local-scope
140   list:&:duplex-list:char <- push 3, 0
141   list <- push 4, list
142   list <- push 5, list
143   run [
144     list2:&:duplex-list:char <- next list  # inside list
145     list2 <- next list2  # now at end of list
146     list2 <- insert 6, list2
147     # check structure like before
148     list2 <- copy list
149     10:char/raw <- first list2
150     list2 <- next list2
151     11:char/raw <- first list2
152     list2 <- next list2
153     12:char/raw <- first list2
154     list2 <- next list2
155     13:char/raw <- first list2
156     list2 <- prev list2
157     20:char/raw <- first list2
158     list2 <- prev list2
159     21:char/raw <- first list2
160     list2 <- prev list2
161     22:char/raw <- first list2
162     30:bool/raw <- equal list, list2
163   ]
164   memory-should-contain [
165     10 <- 5  # scanning next
166     11 <- 4
167     12 <- 3
168     13 <- 6  # inserted element
169     20 <- 3  # then prev
170     21 <- 4
171     22 <- 5
172     30 <- 1  # list back at start
173   ]
174 ]
175 
176 scenario inserting-after-start-of-duplex-list [
177   local-scope
178   list:&:duplex-list:char <- push 3, 0
179   list <- push 4, list
180   list <- push 5, list
181   run [
182     list <- insert 6, list
183     # check structure like before
184     list2:&:duplex-list:char <- copy list
185     10:char/raw <- first list2
186     list2 <- next list2
187     11:char/raw <- first list2
188     list2 <- next list2
189     12:char/raw <- first list2
190     list2 <- next list2
191     13:char/raw <- first list2
192     list2 <- prev list2
193     20:char/raw <- first list2
194     list2 <- prev list2
195     21:char/raw <- first list2
196     list2 <- prev list2
197     22:char/raw <- first list2
198     30:bool/raw <- equal list, list2
199   ]
200   memory-should-contain [
201     10 <- 5  # scanning next
202     11 <- 6  # inserted element
203     12 <- 4
204     13 <- 3
205     20 <- 4  # then prev
206     21 <- 6
207     22 <- 5
208     30 <- 1  # list back at start
209   ]
210 ]
211 
212 # remove 'x' from its surrounding list 'in'
213 #
214 # Returns null if and only if list is empty. Beware: in that case any other
215 # pointers to the head are now invalid.
216 def remove x:&:duplex-list:_elem/contained-in:in, in:&:duplex-list:_elem -> in:&:duplex-list:_elem [
217   local-scope
218   load-ingredients
219   # if 'x' is null, return
220   return-unless x
221   next-node:&:duplex-list:_elem <- get *x, next:offset
222   prev-node:&:duplex-list:_elem <- get *x, prev:offset
223   # null x's pointers
224   *x <- put *x, next:offset, 0
225   *x <- put *x, prev:offset, 0
226   # if next-node is not null, set its prev pointer
227   {
228     break-unless next-node
229     *next-node <- put *next-node, prev:offset, prev-node
230   }
231   # if prev-node is not null, set its next pointer and return
232   {
233     break-unless prev-node
234     *prev-node <- put *prev-node, next:offset, next-node
235     return
236   }
237   # if prev-node is null, then we removed the head node at 'in'
238   # return the new head rather than the old 'in'
239   return next-node
240 ]
241 
242 scenario removing-from-duplex-list [
243   local-scope
244   list:&:duplex-list:char <- push 3, 0
245   list <- push 4, list
246   list <- push 5, list
247   run [
248     list2:&:duplex-list:char <- next list  # second element
249     list <- remove list2, list
250     10:bool/raw <- equal list2, 0
251     # check structure like before
252     list2 <- copy list
253     11:char/raw <- first list2
254     list2 <- next list2
255     12:char/raw <- first list2
256     20:&:duplex-list:char/raw <- next list2
257     list2 <- prev list2
258     30:char/raw <- first list2
259     40:bool/raw <- equal list, list2
260   ]
261   memory-should-contain [
262     10 <- 0  # remove returned non-null
263     11 <- 5  # scanning next, skipping deleted element
264     12 <- 3
265     20 <- 0  # no more elements
266     30 <- 5  # prev of final element
267     40 <- 1  # list back at start
268   ]
269 ]
270 
271 scenario removing-from-start-of-duplex-list [
272   local-scope
273   list:&:duplex-list:char <- push 3, 0
274   list <- push 4, list
275   list <- push 5, list
276   run [
277     list <- remove list, list
278     # check structure like before
279     list2:&:duplex-list:char <- copy list
280     10:char/raw <- first list2
281     list2 <- next list2
282     11:char/raw <- first list2
283     20:&:duplex-list:char/raw <- next list2
284     list2 <- prev list2
285     30:char/raw <- first list2
286     40:bool/raw <- equal list, list2
287   ]
288   memory-should-contain [
289     10 <- 4  # scanning next, skipping deleted element
290     11 <- 3
291     20 <- 0  # no more elements
292     30 <- 4  # prev of final element
293     40 <- 1  # list back at start
294   ]
295 ]
296 
297 scenario removing-from-end-of-duplex-list [
298   local-scope
299   list:&:duplex-list:char <- push 3, 0
300   list <- push 4, list
301   list <- push 5, list
302   run [
303     # delete last element
304     list2:&:duplex-list:char <- next list
305     list2 <- next list2
306     list <- remove list2, list
307     10:bool/raw <- equal list2, 0
308     # check structure like before
309     list2 <- copy list
310     11:char/raw <- first list2
311     list2 <- next list2
312     12:char/raw <- first list2
313     20:&:duplex-list:char/raw <- next list2
314     list2 <- prev list2
315     30:char/raw <- first list2
316     40:bool/raw <- equal list, list2
317   ]
318   memory-should-contain [
319     10 <- 0  # remove returned non-null
320     11 <- 5  # scanning next, skipping deleted element
321     12 <- 4
322     20 <- 0  # no more elements
323     30 <- 5  # prev of final element
324     40 <- 1  # list back at start
325   ]
326 ]
327 
328 scenario removing-from-singleton-duplex-list [
329   local-scope
330   list:&:duplex-list:char <- push 3, 0
331   run [
332     list <- remove list, list
333     1:num/raw <- copy list
334   ]
335   memory-should-contain [
336     1 <- 0  # back to an empty list
337   ]
338 ]
339 
340 # remove values between 'start' and 'end' (both exclusive).
341 # also clear pointers back out from start/end for hygiene.
342 # set end to 0 to delete everything past start.
343 # can't set start to 0 to delete everything before end, because there's no
344 # clean way to return the new head pointer.
345 def remove-between start:&:duplex-list:_elem, end:&:duplex-list:_elem/contained-in:start -> start:&:duplex-list:_elem [
346   local-scope
347   load-ingredients
348   next:&:duplex-list:_elem <- get *start, next:offset
349   nothing-to-delete?:bool <- equal next, end
350   return-if nothing-to-delete?
351   assert next, [malformed duplex list]
352   # start->next->prev = 0
353   # start->next = end
354   *next <- put *next, prev:offset, 0
355   *start <- put *start, next:offset, end
356   return-unless end
357   # end->prev->next = 0
358   # end->prev = start
359   prev:&:duplex-list:_elem <- get *end, prev:offset
360   assert prev, [malformed duplex list - 2]
361   *prev <- put *prev, next:offset, 0
362   *end <- put *end, prev:offset, start
363 ]
364 
365 scenario remove-range [
366   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
367   local-scope
368   list:&:duplex-list:char <- push 18, 0
369   list <- push 17, list
370   list <- push 16, list
371   list <- push 15, list
372   list <- push 14, list
373   list <- push 13, list
374   run [
375     # delete 16 onwards
376     # first pointer: to the third element
377     list2:&:duplex-list:char <- next list
378     list2 <- next list2
379     list2 <- remove-between list2, 0
380     # now check the list
381     10:char/raw <- get *list, value:offset
382     list <- next list
383     11:char/raw <- get *list, value:offset
384     list <- next list
385     12:char/raw <- get *list, value:offset
386     20:&:duplex-list:char/raw <- next list
387   ]
388   memory-should-contain [
389     10 <- 13
390     11 <- 14
391     12 <- 15
392     20 <- 0
393   ]
394 ]
395 
396 scenario remove-range-to-final [
397   local-scope
398   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
399   list:&:duplex-list:char <- push 18, 0
400   list <- push 17, list
401   list <- push 16, list
402   list <- push 15, list
403   list <- push 14, list
404   list <- push 13, list
405   run [
406     # delete 15, 16 and 17
407     # start pointer: to the second element
408     list2:&:duplex-list:char <- next list
409     # end pointer: to the last (sixth) element
410     end:&:duplex-list:char <- next list2
411     end <- next end
412     end <- next end
413     end <- next end
414     remove-between list2, end
415     # now check the list
416     10:char/raw <- get *list, value:offset
417     list <- next list
418     11:char/raw <- get *list, value:offset
419     list <- next list
420     12:char/raw <- get *list, value:offset
421     20:&:duplex-list:char/raw <- next list
422   ]
423   memory-should-contain [
424     10 <- 13
425     11 <- 14
426     12 <- 18
427     20 <- 0  # no more elements
428   ]
429 ]
430 
431 scenario remove-range-empty [
432   local-scope
433   # construct a duplex list with three elements [13, 14, 15]
434   list:&:duplex-list:char <- push 15, 0
435   list <- push 14, list
436   list <- push 13, list
437   run [
438     # delete between first and second element (i.e. nothing)
439     list2:&:duplex-list:char <- next list
440     remove-between list, list2
441     # now check the list
442     10:char/raw <- get *list, value:offset
443     list <- next list
444     11:char/raw <- get *list, value:offset
445     list <- next list
446     12:char/raw <- get *list, value:offset
447     20:&:duplex-list:char/raw <- next list
448   ]
449   # no change
450   memory-should-contain [
451     10 <- 13
452     11 <- 14
453     12 <- 15
454     20 <- 0
455   ]
456 ]
457 
458 scenario remove-range-to-end [
459   local-scope
460   # construct a duplex list with six elements [13, 14, 15, 16, 17, 18]
461   list:&:duplex-list:char <- push 18, 0
462   list <- push 17, list
463   list <- push 16, list
464   list <- push 15, list
465   list <- push 14, list
466   list <- push 13, list
467   run [
468     # remove the third element and beyond
469     list2:&:duplex-list:char <- next list
470     remove-between list2, 0
471     # now check the list
472     10:char/raw <- get *list, value:offset
473     list <- next list
474     11:char/raw <- get *list, value:offset
475     20:&:duplex-list:char/raw <- next list
476   ]
477   memory-should-contain [
478     10 <- 13
479     11 <- 14
480     20 <- 0
481   ]
482 ]
483 
484 # insert list beginning at 'new' after 'in'
485 def insert-range in:&:duplex-list:_elem, start:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
486   local-scope
487   load-ingredients
488   return-unless in
489   return-unless start
490   end:&:duplex-list:_elem <- copy start
491   {
492     next:&:duplex-list:_elem <- next end/insert-range
493     break-unless next
494     end <- copy next
495     loop
496   }
497   next:&:duplex-list:_elem <- next in
498   *end <- put *end, next:offset, next
499   {
500     break-unless next
501     *next <- put *next, prev:offset, end
502   }
503   *in <- put *in, next:offset, start
504   *start <- put *start, prev:offset, in
505 ]
506 
507 def append in:&:duplex-list:_elem, new:&:duplex-list:_elem/contained-in:in -> in:&:duplex-list:_elem [
508   local-scope
509   load-ingredients
510   last:&:duplex-list:_elem <- last in
511   *last <- put *last, next:offset, new
512   return-unless new
513   *new <- put *new, prev:offset, last
514 ]
515 
516 def last in:&:duplex-list:_elem -> result:&:duplex-list:_elem [
517   local-scope
518   load-ingredients
519   result <- copy in
520   {
521     next:&:duplex-list:_elem <- next result
522     break-unless next
523     result <- copy next
524     loop
525   }
526 ]
527 
528 # helper for debugging
529 def dump-from x:&:duplex-list:_elem [
530   local-scope
531   load-ingredients
532   $print x, [: ]
533   {
534     break-unless x
535     c:_elem <- get *x, value:offset
536     $print c, [ ]
537     x <- next x
538     {
539       is-newline?:bool <- equal c, 10/newline
540       break-unless is-newline?
541       $print 10/newline
542       $print x, [: ]
543     }
544     loop
545   }
546   $print 10/newline, [---], 10/newline
547 ]