As mentioned earlier, a list header maintains memory pointers to the first
and last nodes of the linked chain of nodes.  It also serves as a handle
for referencing the entire list.  The minimum list header ("mlh_") and the
full-featured list header ("lh_") are generally interchangeable.

The structure MinListHeader& defines a minimum list header:

    DefSTRUCTURE MinListHeader&, 0&
    DefGPMPTR    mlh_Head&
    DefGPMPTR    mlh_Tail&
    DefGPMPTR    mlh_TailPred&
    DefLABEL     MinListHeader_SizeOf&

mlh_Head&
    points to the first node in the list

mlh_Tail&
    is always zero

mlh_TailPred&
    points to the last node in the list

In a few limited cases a full-featured ListHeader& structure will
be required:

    DefSTRUCTURE ListHeader&, 0&
    DefGPMPTR    lh_Head&
    DefGPMPTR    lh_Tail&
    DefGPMPTR    lh_TailPred&
    DefUBYTE     lh_Type&
    DefUBYTE     lh_Pad&
    DefLABEL     ListHeader_SizeOf&

lh_Head&
    points to the first node in the list

lh_Tail&
    is always zero

lh_TailPred&
    points to the last node in the list

lh_Type&
    defines the type of nodes within the list ("NT_" types)

lh_Pad&
    is a structure alignment byte

One subtlety here must be explained further.  The list header is
constructed in an efficient, but confusing manner.  Think of the header as
a structure containing the head and tail nodes for the list.  The head and
tail nodes are placeholders, and never carry data.  The head and tail
portions of the header actually overlap in memory.  lh_Head& and lh_Tail&
form the head node, lh_Tail& and lh_TailPred& form the tail node.  This
makes it easy to find the start or end of the list, and eliminates any
special cases for insertion or removal.
           ____________                      ____________
          |            |                    |            |
          |  ln_Succ&  |                    |  lh_Head&  |
          |____________|____________        |____________|
          |            |            | /___\ |            |
          | ln_Pred&=0 | ln_Succ&=0 | \   / | lh_Tail&=0 |
          |____________|____________|       |____________|
                       |            |       |            |
                       |  ln_Pred&  |       |lh_TailPred&|
                       |____________|       |____________|

                   Figure 2: List Header Overlap

The lh_Head& and lh_Tail& fields of the list header act like the ln_Succ& and
ln_Pred& fields of a node.  The lh_Tail& field is set permanently to zero,
indicating that the head node is indeed the first on the list -- that is,
it has no predecessors.  See the figure above.

Likewise, the lh_Tail& and lh_TailPred& fields of the list header act like
the ln_Succ& and ln_Pred& fields of a node. Here the zero lh_Tail& indicates
that the tail node is indeed the last on the list -- that is, it has no
successors.  See the figure above.

Because of the facts discussed above it seems obvious, that headers must be
properly initialized before use.  It is not adequate to simply initialize all
header fields to zero.  The head and tail entries must have specific values.

The header must be initialized for use as follows:

    1. Set the lh_Head& field to the address of lh_Tail&.

    2. Clear the lh_Tail& field.

    3. Set the lh_TailPred& field to the address of lh_Head&.

    4. Set lh_Type& to the same data type as the nodes to be kept in the list.
       (Unless you are using a MinListHeader&).

    4.1. If you intent to link nodes of different data types into the list,
         then you rather should use an untyped MinListHeader& and therefore
         full-featured ListNode& structures to assign the types directly
         to the nodes.
                         __________________
                        |   ____________   |
                        |  |            |__|
                        |  |  lh_Head&  |/_
                        |  |____________|\ |
                        |_\|            |  |
                          /| lh_Tail&=0 |  |
                           |____________|  |
                           |            |  |
                           |lh_TailPred&|__|
                           |____________|
 one of the "NT_" types __\|            |
                          /|  lh_Type&  |
                           |____________|
                           |            |
                           |  lh_Pad&   |
                           |____________|

    PokeL list&, lh_Head&, (list& + lh_Tail&)
    PokeL list&, lh_Tail&, 0&
    PokeL list&, lh_TailPred&, (list& + lh_Head&)
    'now, if needed
    PokeB list&, lh_Type&, NT_...&

            Figure 3: Initializing a List Header Structure

The sequence of PokeL SUB calls in the figure above (except for the type
field) is equivalent to the SUB NewList, contained in the include file
lists.bm.  Since the MinListHeader& structure is the same as the
ListHeader& structure except for the type and pad fields, this sequence
of code will work for both structures.  However, the preferred way to
initialize a list header structure is to call the SUB NewList with the
list header's address, what will make your programs more readable.

                                                      Back to List Overview