commit a22123482065fd477dec82127773a4bfbbbf67d6
parent 8e1a457e3438c84ef6b547a47bce241e4694a270
Author: Virgil Dupras <hsoft@hardcoded.net>
Date: Tue, 31 Jan 2023 17:02:04 -0500
lib/ll: new unit
extract a few words from bootlo, and add a few others.
Diffstat:
10 files changed, 71 insertions(+), 30 deletions(-)
diff --git a/fs/comp/c/lib.fs b/fs/comp/c/lib.fs
@@ -3,6 +3,7 @@
?f<< /comp/c/cc.fs
?f<< /lib/str.fs
?f<< /lib/fmt.fs
+?f<< /lib/ll.fs
\ A few system word proxies
:c void abort();
diff --git a/fs/comp/c/type.fs b/fs/comp/c/type.fs
@@ -2,6 +2,7 @@
?f<< /lib/str.fs
?f<< /lib/arena.fs
?f<< /lib/meta.fs
+?f<< /lib/ll.fs
?f<< /comp/c/tok.fs
\ When we parse a type, we can almost never write it directly to "here" because
diff --git a/fs/doc/dict.txt b/fs/doc/dict.txt
@@ -254,15 +254,11 @@ n case .. of condition .. endof .. endcase
llnext ll -- ll Yield next LL element.
llend ll -- ll Iterate LL until we reach the last element.
-llprev tgt ll -- ll From "ll", iterate LL until we reach the element when the
- LL pointer points to "tgt".
llappend elem ll -- Append "elem" at the end of "ll".
lladd ll -- ll Write a new LL element to here, yield it, then write its
address to the last element of "ll".
-llinsert elem ll -- Insert "elem" between "ll" and its next element. If "ll"
- is the last element of the list, this is equivalent to
- "llappend".
-llcnt ll -- n Yield the number of elements in "ll".
+
+For more, see lib/ll.
## Dictionary
diff --git a/fs/doc/lib/ll.txt b/fs/doc/lib/ll.txt
@@ -0,0 +1,20 @@
+# Linked lists
+
+A collection of helpers around linked lists.
+
+Values:
+
+llprev After a llfind or a llitern, llprev is the element preceding the result.
+ It is 0 when no iteration took place.
+llidx After a llfind or a llitern, llidx is the number of iterations that took
+ place.
+
+Words:
+
+llinsert elem ll -- Insert "elem" between "ll" and its next element. If "ll"
+ is the last element of the list, this is equivalent to
+ "llappend".
+llcnt ll -- n Yield the number of elements in "ll".
+llfind elem ll -- f Check whether "elem" exists in "ll".
+llitern n ll -- elem Iterate "n" time in "ll" and return the resulting element
+ or 0 if end of list was reached.
diff --git a/fs/lib/ll.fs b/fs/lib/ll.fs
@@ -0,0 +1,16 @@
+0 value llprev
+0 value llidx
+
+: llinsert ( elem ll -- ) over swap @! swap ! ;
+: llcnt ( ll -- count ) 0 >r begin ?dup not if r> neg exit then llnext next ;
+: llitern ( n ll -- elem )
+ over to llidx 0 to llprev over if swap >r begin ( line )
+ dup to llprev llnext
+ dup not if r@ 1- neg to+ llidx leave then next ( line )
+ else nip then ;
+: llfind ( elem ll -- f )
+ 0 to llidx 0 to llprev begin ( elem line )
+ 2dup <> while
+ 1 to+ llidx dup to llprev
+ llnext dup while repeat then ( elem line )
+ nip bool ;
diff --git a/fs/tests/kernel.fs b/fs/tests/kernel.fs
@@ -79,18 +79,6 @@ current .x
6 foo 209 #eq
20 foo 220 #eq
-\ linked lists
-0 value ll
-4 &+@ myfield
-here to ll 0 , 42 ,
-ll lladd drop 54 ,
-here 0 , 33 , to' ll llinsert
-ll myfield 33 #eq
-ll llnext myfield 42 #eq
-ll llnext llnext myfield 54 #eq
-ll llnext llnext ll llprev myfield 42 #eq
-ll llcnt 3 #eq
-
\ Local variables
: foo 54 >r 42 >r 1 to+ V1 2 to+ V2 V2 V1 rfree ;
foo 55 #eq 44 #eq
diff --git a/fs/tests/lib/all.fs b/fs/tests/lib/all.fs
@@ -2,6 +2,7 @@
f<< /tests/lib/core.fs
f<< /tests/lib/bit.fs
f<< /tests/lib/str.fs
+f<< /tests/lib/ll.fs
f<< /tests/lib/struct.fs
f<< /tests/lib/meta.fs
f<< /tests/lib/context.fs
diff --git a/fs/tests/lib/ll.fs b/fs/tests/lib/ll.fs
@@ -0,0 +1,24 @@
+?f<< /tests/harness.fs
+?f<< /lib/ll.fs
+testbegin
+\ linked lists
+0 value ll
+4 &+@ myfield
+here to ll 0 , 42 ,
+ll lladd drop 54 ,
+here 0 , 33 , to' ll llinsert
+ll myfield 33 #eq
+ll llnext myfield 42 #eq
+ll llnext llnext myfield 54 #eq
+ll llcnt 3 #eq
+2 ll llitern myfield 54 #eq
+llidx 2 #eq
+llprev myfield 42 #eq
+4 ll llitern 0 #eq
+llidx 3 #eq
+llprev myfield 54 #eq
+$1234 ll llfind not #
+ll llnext ll llfind #
+llidx 1 #eq
+llprev myfield 33 #eq
+testend
diff --git a/fs/text/ed.fs b/fs/text/ed.fs
@@ -1,6 +1,7 @@
?f<< /lib/arena.fs
?f<< /lib/fmt.fs
?f<< /lib/str.fs
+?f<< /lib/ll.fs
: nspcs ( n -- ) ?dup if >r begin spc> next then ;
@@ -11,11 +12,7 @@ struct[ Line
: :range ( line -- a u ) dup ptr swap cnt ;
- : :itern ( n line -- iter-n line )
- over not if exit then over >r \ V1=asked-n
- swap >r begin ( line )
- dup llnext ?dup if nip else r> r> -^ swap exit then next ( line )
- r> swap ;
+ : :itern ( n line -- iter-n line ) llitern llidx swap ;
]struct
extends IO struct[ Edbuf
@@ -127,8 +124,10 @@ extends IO struct[ Edbuf
: :dellines ( n self -- )
over not if 2drop exit then >r \ V1=self
- >r V1 sel dup begin llnext dup not if leave then next ( delpoint tgt )
- tuck swap V1 to' lines llprev ( tgt tgt prev ) ! ( tgt )
+ V1 sel V1 lines llfind drop llprev ( n delpoint )
+ ?dup not if V1 to' lines then swap ( delpoint n )
+ V1 sel llitern ( delpoint tgt )
+ tuck swap ( tgt tgt prev ) ! ( tgt )
?dup not if V1 lines llend then r> _sel! ;
]struct
diff --git a/fs/xcomp/bootlo.fs b/fs/xcomp/bootlo.fs
@@ -155,13 +155,8 @@ alias noop [then]
alias @ llnext
: llend ( ll -- lastll ) begin dup llnext ?dup while nip repeat ( ll ) ;
-: llprev ( tgt ll -- prev )
- begin 2dup llnext = not while llnext ?dup while repeat
- abort" llprev failed" then nip ;
: llappend ( elem ll -- ) llend ! ;
: lladd ( ll -- newll ) here swap llappend here 0 , ;
-: llinsert ( elem ll -- ) over swap @! swap ! ;
-: llcnt ( ll -- count ) 0 >r begin ?dup not if r> neg exit then llnext next ;
\ Entry metadata
-4 &+@ emeta
