Exec Lists and Queues

Exec Lists and Queues

The Amiga system software operates in a dynamic environment of data structures. An early design goal of Exec was to keep the system flexible and open-ended by eliminating artificial boundaries on the number of system structures used. Rather than using static system tables, Exec uses dynamically created structures that are added and removed as needed. These structures can be put in an unordered list, or in an ordered list known as a queue. A list can be empty, but never full. This concept is central to the design of Exec. Understanding lists and queues is important to understanding not only Exec itself, but also the mechanism behind the Amiga's message and port based inter-process communication.

Exec uses lists to maintain its internal database of system structures. Tasks, interrupts, libraries, devices, messages, I/O requests, and all other Exec data structures are supported and serviced through the consistent application of Exec's list mechanism. Lists have a common data structure, and a common set of functions is used for manipulating them. Because all of these structures are treated in a similar manner, only a small number of list handling functions need be supported by Exec.

List Structure

A list is composed of a header and a doubly-linked chain of elements called nodes. The header contains memory pointers to the first and last nodes of the linked chain. The address of the header is used as the handle to the entire list. To manipulate a list, you must provide the address of its header.

Figure 23-1: Simplified Overview of an Exec List

Nodes may be scattered anywhere in memory. Each node contains two pointers; a successor and a predecessor. As illustrated above, a list header contains two placeholder nodes that contain no data. In an empty list, the head and tail nodes point to each other.

Node Structure Definition

A Node structure is divided into three parts: linkage, information, and content. The linkage part contains memory pointers to the node's successor and predecessor nodes. The information part contains the node type, the priority, and a name pointer. The content part stores the actual data structure of interest. For nodes that require linkage only, a small MinNode structure is used.

struct MinNode
{
    struct MinNode *mln_Succ;
    struct MinNode *mln_Pred;
};

mln_Succ

points to the next node in the list (successor).

mln_Pred

points to the previous node in the list (predecessor).

When a type, priority, or name is required, a full-featured Node structure is used.

struct Node
{
    struct Node *ln_Succ;
    struct Node *ln_Pred;
    UBYTE        ln_Type;
    BYTE         ln_Pri;
    char        *ln_Name;
};

ln_Type

defines the type of the node (see <exec/nodes.h> for a list).

ln_Pri

specifies the priority of the node (+127 (highest) to -128 (lowest)).

ln_Name

points to a printable name for the node (a NULL-terminated string).

The Node and MinNode structures are often incorporated into larger structures, so groups of the larger structures can easily be linked together. For example, the Exec Interrupt structure is defined as follows:

struct Interrupt
{
    struct Node is_Node;
    APTR        is_Data;
    VOID        (*is_Code)();
};

Here the is_Data and is_Code fields represent the useful content of the node. Because the Interrupt structure begins with a Node structure, it may be passed to any of the Exec List manipulation functions.

Node Initialization

Before linking a node into a list, certain fields may need initialization. Initialization consists of setting the ln_Type, ln_Pri, and ln_Name fields to their appropriate values (A MinNode structure does not have these fields). The successor and predecessor fields do not require initialization.

The ln_Type field contains the data type of the node. This indicates to Exec (and other subsystems) the type, and hence the structure, of the content portion of the node (the extra data after the Node structure). The standard system types are defined in the <exec/nodes.h> include file. Some examples of standard system types are NT_TASK, NT_INTERRUPT, NT_DEVICE, and NT_MSGPORT.

The ln_Pri field uses a signed numerical value ranging from +127 to -128 to indicate the priority of the node. Higher-priority nodes have greater values; for example, 127 is the highest priority, zero is nominal priority, and -128 is the lowest priority. Some Exec lists are kept sorted by priority order. In such lists, the highest-priority node is at the head of the list, and the lowest-priority node is at the tail of the list. Most Exec node types do not use a priority. In such cases, initialize the priority field to zero.

The ln_Name field is a pointer to a NULL-terminated string of characters. Node names are used to find and identify list-bound objects (like public message ports and libraries), and to bind symbolic names to actual nodes. Names are also useful for debugging purposes, so it is a good idea to provide every node with a name. Take care to provide a valid name pointer; Exec does not copy name strings.

This fragment initializes a Node called myInt, an instance of the Interrupt data structure introduced above.

struct Interrupt interrupt;
 
interrupt.is_Node.ln_Type = NT_INTERRUPT;
interrupt.is_Node.ln_Pri  = -10;
interrupt.is_Node.ln_Name = "sample.interrupt";

List Header Structure Definition

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 MinList defines a minimum list header.

struct MinList
{
    struct MinNode *mlh_Head;
    struct MinNode *mlh_Tail;
    struct MinNode *mlh_TailPred;
};

mlh_Head

points to the first node in the list.

mlh_Tail

is always NULL.

mlh_TailPred

points to the last node in the list.

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

struct List
{
    struct Node *lh_Head;
    struct Node *lh_Tail;
    struct Node *lh_TailPred;
    UBYTE        lh_Type;
    UBYTE        lh_Pad;
};

lh_Type

defines the type of nodes within the list (see <exec/nodes.h>).

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.

Figure 23-2: List Header Overlap

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

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

Header Initialization

List headers must be properly initialized before use. It is not adequate to initialize the entire header to zero. The head and tail entries must have specific values. The header must be initialized 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 the list. (Unless you are using a MinList).

Figure 23-3: Initializing a List Header Structure

The functions NewList() and NewMinList() are provided to properly initialize a List or MinList respectively prior to use.

List Functions

Exec provides a number of symmetric functions for handling lists. There are functions for inserting and removing nodes, for adding and removing head and tail nodes, for inserting nodes in a priority order, and for searching for nodes by name. The prototypes for Exec list handling functions are as follows.

VOID AddHead( struct List *list, struct Node *node );

VOID AddTail( struct List *list, struct Node *node );

VOID Enqueue( struct List *list, struct Node *node );

struct Node *FindIName( struct List *list, STRPTR name );

struct Node *FindName( struct List *list, STRPTR name );

struct Node *GetHead(struct List *list);

struct Node *GetPred(struct Node *node);

struct Node *GetSucc(struct Node *node);

struct Node *GetTail(struct List *list);

VOID Insert( struct List *list, struct Node *node, struct Node *pred );

VOID Remove( struct Node *node );

struct Node *RemHead( struct List *list );

struct Node *RemTail( struct List *list );

VOID NewList( struct List *list );

VOID NewMinList( struct MinList *list );

In this discussion of the Exec list handling functions, header represents a pointer to List header, and node represents pointer to a Node.

Insertion and Removal

The Insert() function is used for inserting a new node into any position in a list. It always inserts the node following a specified node that is already part of the list. For example, Insert(header,node,pred) inserts the node node after the node pred in the specified list. If the pred node points to the list header or is NULL, the new node will be inserted at the head of the list. Similarly, if the pred node points to the lh_Tail of the list, the new node will be inserted at the tail of the list. However, both of these actions can be better accomplished with the functions mentioned in the "Special Case Insertion" section below.

The Remove() function is used to remove a specified node from a list. For example, Remove(node) will remove the specified node from whatever list it is in. To be removed, a node must actually be in a list. If you attempt to remove a node that is not in a list, you will cause serious system problems.

Special Case Insertion

Although the Insert() function allows new nodes to be inserted at the head and the tail of a list, the AddHead() and AddTail() functions will do so with higher efficiency. Adding to the head or tail of a list is common practice in first-in-first-out (FIFO) or last-in-first-out (LIFO or stack) operations. For example, AddHead(header,node) would insert the node at the head of the specified list.

Special Case Removal

The two functions RemHead() and RemTail() are used in combination with AddHead() and AddTail() to create special list ordering. When you combine AddTail() and RemHead(), you produce a first-in-first-out (FIFO) list. When you combine AddHead() and RemHead() a last-in-first-out (LIFO or stack) list is produced. RemTail() exists for symmetry. Other combinations of these functions can also be used productively.

Both RemHead() and RemTail() remove a node from the list, and return a pointer to the removed node. If the list is empty, the function return a NULL result.

MinList / MinNode Operations

All of the above functions and macros will work with long or short format node structures. A MinNode structure contains only linkage information. A full Node structure contains linkage information, as well as type, priority and name fields. The smaller MinNode is used where space and memory alignment issues are important. The larger Node is used for queues or lists that require a name tag for each node.

Prioritized Insertion

The list functions discussed so far do not make use of the priority field in a Node. The Enqueue() function is equivalent to Insert(), except it inserts nodes into a list sorting them according to their priority. It keeps the higher-priority nodes towards the head of the list. All nodes passed to this function must have their priority and name assigned prior to the call. Enqueue(header,mynode) inserts mynode behind the lowest priority node with a priority greater than or equal to mynode's. For Enqueue() to work properly, the list must already be sort according to priority. Because the highest priority node is at the head of the list, the RemHead() function will remove the highest-priority node. Likewise, RemTail() will remove the lowest-priority node.

FIFO Is Used For The Same Priority
If you add a node that has the same priority as another node in the queue, Enqueue() will use FIFO ordering. The new node is inserted following the last node of equal priority.

Searching by Name

Because many lists contain nodes with symbolic names attached (via the ln_Name field), it is possible to find a node by its name. This naming technique is used throughout Exec for such nodes as tasks, libraries, devices, and resources.

The FindName() function searches a list for the first node with a given name. For example, FindName(header, "Furrbol") returns a pointer to the first node named "Furrbol." If no such node exists, a NULL is returned.

The case of the name characters is significant; "foo" is different from "Foo." If the case of a name should not be significant then use the FindIName() function.

Figure 23-4: Complete Sample List Showing all Interconnections

More on the Use of Named Lists

To find multiple occurrences of nodes with identical names, the FindName() or FindIName() function is called multiple times. For example, if you want to find all the nodes with the name pointed to by name:

VOID DisplayName(struct List *list, CONST_STRPTR name)
{
struct Node *node;
 
    if (node = IExec->FindName(list, name))
        while (node)
        {
            IDOS->Printf("Found %s at location %lx\n", node->ln_Name, node);
            node = IExec->FindName((struct List *)node, name);
        }
    else IDOS->Printf("No node with name %s found.\n", name);
}

Notice that the second search uses the node found by the first search. The FindName() function never compares the specified name with that of the starting node. It always begins the search with the successor of the starting point.

Empty Lists

It is often important to determine if a list is empty. This can be done in many ways, but only two are worth mentioning. If either the lh_TailPred field is pointing to the list header or the ln_Succ field of the lh_Head is NULL, then the list is empty.

These methods would be written as follows:

/* You can use this method...   */
if (list->lh_TailPred == (struct Node *)list)
    IDOS->Printf("list is empty\n");
 
/* Or you can use this method   */
if (NULL == list->lh_Head->ln_Succ)
    IDOS->Printf("list is empty\n");

Macros are available to make code easier to read:

struct List *list;
struct MinList *minlist;
 
if (IsListEmpty(list))
    IDOS->Printf("list is empty\n");
 
if (IsMinListEmpty(minlist))
    IDOS->Printf("minlist is empty\n");

Scanning a List

Occasionally a program may need to scan a list to locate a particular node, find a node that has a field with a particular value, or just print the list. Because lists are linked in both the forward and backward directions, the list can be scanned from either the head or tail.

There are two methods to traverse lists in AmigaOS. One way is via direct manipulation of the pointers. The other way uses functions from Exec.

Here is a code fragment that uses pointers and for loop to print the names of all nodes in a list:

struct List *list;
struct Node *node;
 
for (node = list->lh_Head ; node->ln_Succ ; node = node->ln_Succ)
    IDOS->Printf("%p -> %s\n", node, node->ln_Name);

A common mistake is to process the head or tail nodes. Valid data nodes have non-NULL successor and predecessor pointers. The above loop exits when node->ln_Succ is NULL.

Another common mistake is to free a node from within a loop, then reference the free memory to obtain the next node pointer. An extra temporary pointer solves this second problem. Here is an example:

struct List *list;
struct Node *node, *next;
 
for (node = list->lh_Head; node->ln_Succ; node = next)
{
     next = node->ln_Succ;
     /* Do something with node. */
     /* This may include node removal from list. */
     if( some_condition )
     {
          IExec->Remove(node);
     }
}

Here is a code fragment that uses functions and for loop to print the names of all nodes in a list:

struct List *list;
struct Node *node;
 
for (node = IExec->GetHead() ; node != NULL ; node = IExec->GetSucc(node))
    IDOS->Printf("%p -> %s\n", node, node->ln_Name);

Here is an example showing how to properly remove a node from a list while traversing:

struct List *list;
struct Node *node, *next;
 
for (node = IExec->GetHead(list); node != NULL; node = next)
{
     next = IExec->GetSucc(node);
     /* Do something with node. */
     /* This may include node removal from list. */
     if( some_condition )
     {
          IExec->Remove(node);
     }
}

Programmers are free to choose the method they prefer. Performance is not likely a concern unless the code is used in a critical section of a program.

Exec List Example

The code below demonstrates the concepts and functions discussed in this section by building an application-defined Exec List.

// buildlist.c - example which uses an application-specific Exec list
 
#include <exec/types.h>
#include <exec/lists.h>
#include <exec/nodes.h>
#include <exec/memory.h>
 
#include <proto/exec.h>
#include <proto/dos.h>
#include <proto/utility.h>
 
/* Our function prototypes */
VOID AddName(struct List *, CONST_STRPTR);
VOID FreeNameNodes(struct List *);
VOID DisplayNameList(struct List *);
VOID DisplayName(struct List *, CONST_STRPTR);
 
struct NameNode {
    struct Node nn_Node;        /* System Node structure */
    TEXT   nn_Data[62];         /* Node-specific data */
};
 
#define NAMENODE_ID   100       /* The type of "NameNode" */
 
int main()
{
    struct  List    *NameList;    /* Note that a MinList would also work */
 
    NameList = IExec->AllocSysObjectTags(ASOT_LIST, TAG_END);
 
    if (NameList == NULL)
        IDOS->Printf("Out of memory\n");
    else {
        AddName(NameList,"Name7");   AddName(NameList,"Name6");
        AddName(NameList,"Name5");   AddName(NameList,"Name4");
        AddName(NameList,"Name2");   AddName(NameList,"Name0");
 
        AddName(NameList,"Name7");   AddName(NameList,"Name5");
        AddName(NameList,"Name3");   AddName(NameList,"Name1");
 
        DisplayName(NameList,"Name5");
        DisplayNameList(NameList);
 
        FreeNameNodes(NameList);
        IExec->FreeSysObject(ASOT_LIST, NameList);  /* Free list header */
    }
}
 
/* Allocate a NameNode structure, copy the given name into the structure,
 * then add it the specified list.  This example does not provide an
 * error return for the out of memory condition.
*/
VOID AddName(struct List *list, CONST_STRPTR name)
{
    struct NameNode *namenode = IExec->AllocSysObjectTags(ASOT_NODE,
      ASONODE_Size, sizeof(struct NameNode),
      ASONODE_Type, NAMENODE_ID,
      TAG_END);
 
    if (namenode == NULL)
        IDOS->Printf("Out of memory\n");
    else {
        IUtility->Strlcpy(namenode->nn_Data, name, sizeof(namenode->nn_Data));
        namenode->nn_Node.ln_Name = namenode->nn_Data;
        AddHead((struct List *)list, (struct Node *)namenode);
    }
}
 
/*
 * Free the entire list, including the header.  The header is not updated
 * as the list is freed.  This function demonstrates how to avoid
 * referencing freed memory when deallocating nodes.
 */
VOID FreeNameNodes(struct List *list)
{
    struct NameNode *worknode;
    struct NameNode *nextnode;
 
    worknode = (struct NameNode *)(IExec->GetHead(list)); /* First node */
    while (nextnode = (struct NameNode *)(IExec->GetSucc(worknode))) {
        IExec->FreeSysObject(ASOT_NODE, worknode);
        worknode = nextnode;
    }
}
 
/*
 * Print the names of each node in a list.
 */
VOID DisplayNameList(struct List *list)
{
    struct Node *node;
 
    if (IsListEmpty(list))
        IDOS->Printf("List is empty.\n");
    else {
        for (node = IExec->GetHead(list); node != NULL; node = IExec->GetSucc(node))
            IDOS->Printf("%lx -> %s\n", node, node->ln_Name);
    }
}
 
/*
 * Print the location of all nodes with a specified name.
 */
VOID DisplayName(struct List *list, CONST_STRPTR name)
{
    struct Node *node;
 
    if (node = IExec->FindName(list, name)) {
        while (node) {
            IDOS->Printf("Found a %s at location %lx\n", node->ln_Name, node);
            node = IExec->FindName((struct List *)node,name);
        }
    } else IExec->Printf("No node with name %s found.\n", name);
}

Important Note About Shared Lists

It is possible to run into contention problems with other tasks when manipulating a list that is shared by more than one task. None of the standard Exec list functions arbitrates for access to the list. For example, if some other task happens to be modifying a list while your task scans it, an inconsistent view of the list may be formed. This can result in a corrupted system.

Generally it is not permissible to read or write a shared list without first locking out access from other tasks. All users of a list must use the same arbitration method. Several arbitration techniques are used on the Amiga. Some lists are protected by a semaphore. The ObtainSemaphore() call grants ownership of the list (see the Exec Semaphores for more information). Some lists require special arbitration. For example, you must use the Intuition LockIBase(0) call before accessing any Intuition lists. Other lists may be accessed only during Forbid() or Disable() (see Exec Tasks for more information).

The preferred method for arbitrating use of a shared list is through semaphores because a semaphores only holds off other tasks that are trying to access the shared list. Rather than suspending all multitasking. Failure to lock a shared list before use will result in unreliable operation.

Note that I/O functions including printf() generally call Wait() to wait for I/O completion, and this allows other tasks to run. Therefore, it is not safe to print or Wait() while traversing a list unless the list is fully controlled by your application, or if the list is otherwise guaranteed not to change during multitasking.

Function Reference

The following charts give a brief description of the Exec list and queue functions and macros. See the SDK for details about each call.

Exec Function	Description
AddHead()	Insert a node at the head of a list.
AddTail()	Append a node to the tail of a list.
Enqueue()	Insert or append a node to a system queue.
FindIName()	Find a node with a given name in a system list ignoring case.
FindName()	Find a node with a given name in a system list.
GetHead()	Gets the head node of a list.
GetPred()	Gets the node predecessor.
GetSucc()	Gets the node successor.
GetTail()	Gets the tail node of a list.
Insert()	Insert a node into a list.
IsMinListEmpty	Test if minimal list is empty
IsListEmpty	Test if list is empty
NewMinList()	Initialize a minimal list structure for use.
NewList()	Initialize a list structure for use.
MoveList()	Moves all the nodes from one list to another efficiently.
RemHead()	Remove the head node from a list.
Remove()	Remove a node from a list.
RemTail()	Remove the tail node from a list.