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 ANS 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.