You can define a structure for a (data-less) linked list with
struct cell% field list-next end-struct list%
With the address of the list node on the stack, you can compute the
address of the field that contains the address of the next node with
list-next
. E.g., you can determine the length of a list
with:
: list-length ( list -- n ) \ "list" is a pointer to the first element of a linked list \ "n" is the length of the list 0 begin ( list1 n1 ) over while ( list1 n1 ) 1+ swap list-next @ swap repeat nip ;
You can reserve memory for a list node in the dictionary with
list% %allot
, which leaves the address of the list node on the
stack. For the equivalent allocation on the heap you can use list%
%alloc
(or, for an allocate
-like stack effect (i.e., with ior),
use list% %allocate
). You can also get the the size of a list
node with list% %size
and it's alignment with list%
%alignment
.
Note that in ANS Forth the body of a create
d word is
aligned
but not necessarily faligned
;
therefore, if you do a
create name foo% %allot
then the memory alloted for foo%
is
guaranteed to start at the body of name
only if
foo%
contains only character, cell and double fields.
You can also include a structure foo%
as field of
another structure, with:
struct ... foo% field ... ... end-struct ...
Instead of starting with an empty structure, you can also extend an existing structure. E.g., a plain linked list without data, as defined above, is hardly useful; You can extend it to a linked list of integers, like this:(5)
list% cell% field intlist-int end-struct intlist%
intlist%
is a structure with two fields:
list-next
and intlist-int
.
You can specify an array type containing n elements of
type foo%
like this:
foo% n *
You can use this array type in any place where you can use a normal
type, e.g., when defining a field
, or with
%allot
.
The first field is at the base address of a structure and the word
for this field (e.g., list-next
) actually does not change
the address on the stack. You may be tempted to leave it away in the
interest of run-time and space efficiency. This is not necessary,
because the structure package optimizes this case and compiling such
words does not generate any code. So, in the interest of readability
and maintainability you should include the word for the field when
accessing the field.
Go to the first, previous, next, last section, table of contents.