About Linked Lists

Linked lists are used throughout Portfolio and in applications you create with it. To make using lists easier (and to meet the needs of system software and its lists), the kernel defines a special type of linked list, known as a Portfolio list. The kernel also provides a variety of functions for creating and managing Portfolio lists.

Like all linked lists, Portfolio lists are dynamic; they can expand and contract as needed. Their contents, known as nodes, are ordered (there is a first node, a second node, and so on), and you can add a new node at any position in a list. The following sections explain how Portfolio lists are different from other linked lists.

Characteristics of Portfolio Lists

Unlike ordinary linked lists, which contain only nodes, Portfolio lists also contain a special component known as an anchor, which marks both ends of the list. The anchor (which is implemented as a C union) serves as both the beginning-of-list marker (known as the head anchor) and the end-of-list marker (known as the tail anchor). Figure 1 illustrates an anchored list.

Graphic cannot be displayed Figure 1: Anchored list.

When a task traverses a Portfolio list, it determines whether it's at the beginning or end of the list by testing to see if the subsequent node is an anchor.

As the previous illustration shows, Portfolio lists are doubly linked: Each node contains two pointers, one to point to the following node or anchor and one to the previous node or anchor. As a result, back-to-front list traversals are as efficient as front-to-back traversals.

Characteristics of Nodes

In Portfolio lists, there are special data structures that contain only information needed for list management. This information includes the necessary forward and backward pointers, a priority value (described later in this section), and other fields that are used primarily by the operating system. A node can also have a name. Use the FindNamedNode() call to find a node by name.

To create a list component, you define a data structure whose first field is a node. An example is the NoteTracker structure defined in the music library:

Example 1: The Note Tracker structure in the music library.

typedef struct NoteTracker
{
        Node    nttr_Node;
        int8    nttr_Note;
        int8    nttr_MixerChannel;
        uint8   nttr_Flags;
        int8    nttr_Channel;  /* MIDI */
        Item    nttr_Instrument;
} NoteTracker;

To pass such a component to one of the many list-manipulation functions that takes a Node structure as an argument, you simply cast the argument to type Node. Here's an example:

AddTail( &DSPPData.dspp_ExternalList, (Node *) dext );

Every node in a list has a priority (a value from 0-255 that is stored in the n_Priority field of the Node structure). When you use a list, you have the option of keeping its nodes sorted by priority (done automatically by the kernel if you use InsertNodeFromHead() or InsertNodeFromTail()), or you can specify other ways to arrange the contents (by using the UniversalInsertNode() function). You can also change the priority of a node in a list with the SetNodePri() function, whereupon the kernel automatically repositions the node in the list to reflect its new priority value.

A node can be in only one list at a time.