commit db2d62ee6cebdcd83b897c73deed5dcd66ecbf3b
parent 95c0b3ff2ec3510be9a7ddae0062fcf444f681fe
Author: Virgil Dupras <hsoft@hardcoded.net>
Date: Sat, 11 Feb 2023 20:54:13 -0500
lib/array: new unit
See doc/lib/array. I tried editing the documentation from within Dusk for the
first time, but paragraph reflow is too painful. I'll pospone that first for
when my tooling is adequate.
I'm getting comfy with in-Dusk test writing though...
Diffstat:
6 files changed, 150 insertions(+), 0 deletions(-)
diff --git a/fs/doc/lib/array.txt b/fs/doc/lib/array.txt
@@ -0,0 +1,61 @@
+# Array
+
+Prerequisite: lib/malloc
+
+Arrays are lists of elements of arbitrary size living in contiguous memory,
+which means they can quickly be accessed by index. Arrays can have elements
+inserted to them and deleted from them, which means they can possibly end up
+with more elements than they started with. This represents a challenge in terms
+of memory allocation.
+
+This challenge is met with lib/malloc. Upon creation, an array must be specified
+a maximum capacity. It begins its life empty and as elements are added to it,
+its capacity is checked. If the needed capacity exceeds the current one, we
+reallocate (using "realloc") the array with a capacity that is the double of
+what is needed at that time (the goal being to minimize reallocations).
+
+Out of bounds index access aborts with error message.
+
+## Example usage
+
+CELLSZ 10 Array :new structbind Array arr
+1 arr :append 42 swap !
+2 arr :append 54 swap !+ 102 swap !
+1 2 arr :insert 99 swap !
+\ "arr" is now an array with 4 elements 42, 54, 99, 102 and with a capacity of
+\ 10 elements where each element is 4 bytes wide. if you try to add 5 more
+\ elements, the array will be reallocated.
+
+## Array API
+
+An Array is a structure.
+
+Fields:
+
+ptr Pointer to current "malloc-ed" memory area. Pointer to first element.
+cnt Number of elements in the array.
+elemsz Size in bytes of each element.
+alloc Capacity in bytes of the array.
+
+Methods:
+
+:new ( elemsz allocnt -- array )
+ Create a new array where each element is "elemsz" bytes wide with enough
+ capacity for "allocnt" elements.
+
+:' ( idx array -- a )
+ Address in array of index "idx".
+
+:@ ( idx array -- n )
+ :' followed by @.
+
+:append ( cnt array -- a )
+ Add "cnt" elements to the array, uninitialized, returning the address of the
+ first added element.
+
+:insert ( cnt idx array -- a )
+ Insert "cnt" elements in the array, uninitialized, at index "idx" and return
+ the address of the first inserted element.
+
+:delete ( cnt idx array -- )
+ Delete "cnt" elements from the array at index "idx".
diff --git a/fs/home/initw.fs b/fs/home/initw.fs
@@ -8,6 +8,8 @@ f<< /lib/diag.fs
f<< /sys/rdln.fs
f<< /text/pager.fs
f<< /lib/context.fs
+f<< /tests/harness.fs
+f<< /home/w.fs
context asm
?f<< /asm/i386.fs
context ed
diff --git a/fs/home/w.fs b/fs/home/w.fs
@@ -0,0 +1,5 @@
+\ This file contains temporary words that help with whatever I'm working on
+\ at the moment. It changes often and I don't commit those changes to
+\ minimize noise.
+
+: testw S" /tests/lib/array.fs" curpath :find# Path :fload ;
+\ No newline at end of file
diff --git a/fs/lib/array.fs b/fs/lib/array.fs
@@ -0,0 +1,44 @@
+?f<< /lib/malloc.fs
+
+: move- ( src dst u -- )
+ rot> over - >r over + swap for ( a ) \ V1=delta
+ 1- dup c@ over V1 + c! next drop rdrop ;
+
+struct[ Array
+ sfield ptr
+ sfield cnt
+ sfield elemsz
+ sfield alloc
+
+ : :new ( elemsz allotcnt -- array )
+ over * dup malloc here >r , 0 , swap , , r> ;
+
+ : _' ( idx self -- a ) dup ptr swap elemsz rot * + ;
+ : _#bounds ( idx self -- ) cnt >= if abort" array bounds error" then ;
+ : :' ( idx self -- a ) 2dup _#bounds _' ;
+ : _'end ( self -- a ) dup cnt swap _' ;
+ : :@ ( idx self -- n ) :' @ ;
+ : _?alloc ( cnt self -- )
+ tuck cnt + over elemsz * ( self minalloc )
+ over alloc over < if ( self newalloc )
+ << 2dup swap to alloc
+ over ptr swap realloc swap to ptr ( )
+ else 2drop then ;
+ : :append ( cnt self -- a )
+ 2dup _?alloc dup _'end ( cnt self a )
+ rot> to+ cnt ( a ) ;
+ : :insert ( cnt idx self -- a ) >r \ V1=self
+ dup V1 _#bounds ( cnt idx )
+ V1 :' >r dup V1 elemsz * V2 + ( cnt dst ) \ V2=src
+ V1 _'end V2 - ( cnt dst u )
+ V2 rot> move- ( cnt )
+ V1 to+ cnt r> rdrop ( a ) ;
+ : :delete ( cnt idx self -- ) >r \ V1=self
+ dup V1 _#bounds
+ 2dup + V1 cnt < if ( cnt idx )
+ V1 :' dup >r over V1 elemsz * + ( cnt src ) \ V2=dst
+ V1 _'end over - ( cnt src u )
+ r> swap move ( cnt )
+ neg r> to+ cnt
+ else nip r> to cnt then ( ) ;
+]struct
diff --git a/fs/tests/lib/all.fs b/fs/tests/lib/all.fs
@@ -8,6 +8,7 @@ f<< /tests/lib/meta.fs
f<< /tests/lib/context.fs
f<< /tests/lib/arena.fs
f<< /tests/lib/malloc.fs
+f<< /tests/lib/array.fs
f<< /tests/lib/math.fs
f<< /tests/lib/stack.fs
f<< /tests/lib/tree.fs
diff --git a/fs/tests/lib/array.fs b/fs/tests/lib/array.fs
@@ -0,0 +1,35 @@
+?f<< /tests/harness.fs
+?f<< /lib/array.fs
+testbegin
+\ Array tests
+create foo 4 nc, 1 2 3 4
+foo foo 1+ 3 move-
+create expected 4 nc, 1 1 2 3
+foo expected 4 []= #
+
+CELLSZ 3 Array :new structbind Array arr
+arr ptr value oldptr
+arr cnt 0 #eq
+1 arr :append dup oldptr #eq
+42 swap !
+arr cnt 1 #eq
+arr ptr oldptr #eq
+0 arr :@ 42 #eq
+3 arr :append dup oldptr <> #
+arr ptr oldptr <> #
+54 swap !+ 102 swap !+ 12 swap !
+arr cnt 4 #eq
+create expected 42 , 54 , 102 , 12 ,
+arr ptr expected 16 []= #
+1 2 arr :insert 123 swap !
+arr cnt 5 #eq
+create expected 42 , 54 , 123 , 102 , 12 ,
+arr ptr expected 20 []= #
+2 1 arr :delete
+arr cnt 3 #eq
+create expected 42 , 102 , 12 ,
+arr ptr expected 12 []= #
+3 1 arr :delete \ we auto-adjust 3 to 2
+arr cnt 1 #eq
+0 arr :@ 42 #eq
+testend
+\ No newline at end of file
