5.22.2 Structure Usage

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 get the the size of a list node with list% %size and its alignment with list% %alignment.

Note that in Standard Forth the body of a created word is aligned but not necessarily faligned; therefore, if you do a:

create name foo% %allot drop

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. Therefore, if your structure contains floats, better use

foo% %allot constant name

You can include a structure foo% as a field of another structure, like this:

struct
...
    foo% field ...
...
end-struct ...

Instead of starting with an empty structure, you can 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:³²

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: If you compile a first-field words, no code is generated. So, in the interest of readability and maintainability you should include the word for the field when accessing the field.