Node:Structure Usage, Next:Structure Naming Convention, Previous:Why explicit structure support?, Up:Structures

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.

Footnotes

1. This feature is also known as extended records. It is the main innovation in the Oberon language; in other words, adding this feature to Modula-2 led Wirth to create a new language, write a new compiler etc. Adding this feature to Forth just required a few lines of code.