Exec Lists
From MorphOS Library
Grzegorz Kraszewski
Contents
Introduction
A list is the simplest dynamic data structure. An array is even simplier, but it is not dynamic. Adding a single item to an array requires reallocation of memory and copying the whole old contents, similarly for removing. Inserting and removing elements to a list is very fast operation and its computational costs do not increase with number of items. Because of this, list is the basic structure used in exec.library, the MorphOS kernel. One could say the Exec is built on lists. Lists are also used through all the system to manage processes, windows, screens, devices, DOS volumes, fonts, libraries and more. Of course lists are also used by applications to manage dynamic data. Many more sophisticated data structures are built on lists. For all these reasons understanding lists and their MorphOS flavour is essential for every programmer.
Lists may be divided to intrusive and nonintrusive ones. An intrusive list is one requiring that every list item contains a part called a node. The node is then used for linking items into list. A nonintrusive list creates nodes itself. Both kinds have their advantages. Exec lists are intrusive. Why? For a nonintrusive list adding an item means allocating memory for its node. Exec lists are often used at really low levels of the system, like interrupt handling, process scheduler or input/output hardware devices. Calling memory allocator from there is unacceptable. Also error handling would become a nightmare (every memory allocation can fail...). In some parts of the system lists also have to be extremely fast. Memory allocation is a complex operation and can't be expected to finish in a few processor cycles. Of course on higher levels of the system, intrusiveness has more disadvantages than advantages. For example an item of intrusive list cannot be added to more than one list. Then high level components (for example MUI List class) may be nonintrusive ones.
From a Plain List to Exec List
The simplest form of list is a unidirectional one. Node of every item consists only of pointer to the next element. The list is identified by keeping a pointer to its first item. Unidirectional lists however are used only in special cases. While inserting an element at list start is easy, inserting at end requires traversing the whole list. Time of this operation increases linearly with number of items. It is also not possible to traverse the list in the backward direction. Then bidirectional lists are much more common. Exec lists are bidirectional. Every node contains two pointers: one to the next element and one to the previous element. For the first element pointer to the previous one is NULL. For the last one, pointer to the next one is NULL. If a list user keeps pointers to both the first and the last element, she has symmetrical access to the start and the end of the list.
While the idea is still simple, we have to complicate it a bit. As mentioned before, the list user keeps track of it by maintaining two pointers: to the first and the last item. These pointers will be modified every time an item is added or removed at the start or end of the list respectively. But what if a list has multiple users not knowing about each other? Adding an item at the start or at the end would require pointer update for all the users. To solve the problem, two artificial items are introduced: a list head and a list tail. Those two elements do not carry payload, only consist of a node. Their location does not change during the list lifetime so they work as anchors. Inserting an element at list start is in fact inserting it between the list head and the former first element. Similarly element inserted at end is in fact inserted between the former last element and the list tail. As pointers to the head and the tail are constant, they may be shared between multiple users.
Exec lists combine the list head and the list tail into one structure, named list header. As the Exec was designed in the days when computer memory was counted in kilobytes rather than gigabytes, designers saw a way to save a few bytes. The "previous" field of list head node always contains NULL. Similarly the "next" field of the list tail always contains NULL. Then they can be merged into one. That is why the list header contains only three pointers instead of four. For the C language the list header is defined as struct List and lists are commonly referenced by a pointer to it.
Exec List Elements: Node and Header
Exec defines two kinds of nodes: a full one and a minimal one. The minimal node consists only of pointers to the next and the previous item and is defined in C in <exec/nodes.h> header file as follows:
struct MinNode
{
struct MinNode *mln_Succ; // successor, the next item
struct MinNode *mln_Pred; // predecessor, the previous item
};
The full node has additional fields used in many system lists. These fields are: item name, item type and item priority.
struct Node
{
struct Node* ln_Succ; // successor
struct Node* ln_Pred; // predecessor
UBYTE ln_Type; // item type
BYTE ln_Pri; // item priority
char* ln_Name; // item name
};
Additional node fields have meaning only for system lists and may be considered as part of payload. If we ignore C types, a Node is just a MinNode with three fields added at the end. Node priority may be used to implement ordered lists or queues. Exec.library provides functions for ordered item insertion.
As there are two kinds of nodes, there are also two types of list headers. Both are defined in <exec/lists.h>:
struct MinList
{
struct MinNode* mlh_Head; // pointer to the first real item
struct MinNode* mlh_Tail; // merged head "previous" and tail "next"
struct MinNode* mlh_TailPred; // pointer to the last real item
};
Header for full nodes has additional type field (used for system lists) and one byte padding to make the structure size even.
struct List
{
struct Node* lh_Head; // pointer to the first real item
struct Node* lh_Tail; // merged head "previous" and tail "next"
struct Node* lh_TailPred; // pointer to the last real item
UBYTE lh_Type;
UBYTE lh_pad;
};
Again, when one ignores C types, the List structure is MinList with two extra fields.
As Exec lists are intrusive, a custom item structure must contain MinNode (or Node if needed) as the first field. It must be a complete structure, not a pointer. Here is an example:
struct MyNode
{
struct MinNode Node; // must be the first
struct Whatever Foobar; // example payload fields
ULONG Something;
char MoreData[10];
/* ... */
};
There is no limit on custom item size. As items are not copied, big items are manipulated with exactly the same speed as small ones.
List Initialization, Empty List Check
The list header, which is either List or MinList structure must be initialized before use. Please note well:
Looking at the diagrams above, we know how an empty list should look like:
An empty list contains only its head and tail, both merged into the header. When one splits them back in mind, initialization becomes obvious:
- The "next" field of the head points to the tail.
- The "prev" field of the head is NULL.
- The "next" field of the tail is NULL.
- The "prev" field of the tail points to the head.
Then the second and the third operation merge into one, as fields are merged. Following code performs proper Exec list initialization. Note the address operators &, forgetting them is a common mistake:
struct MinList mylist; mylist.mlh_Head = (struct MinNode*)&mylist.mlh_Tail; mylist.mlh_Tail = NULL; mylist.mlh_TailPred = (struct MinNode*)&mylist.mlh_Head;
In case of full List, initialization is the same, just typecasts have Node instead of MinNode. List initialization is a common operation, so <exec/lists.h> defines a NEWLIST macro for it. The macro takes a pointer to List or MinList, so for the above example it would be called as follows:
NEWLIST(&mylist);
Empty list check is another common operation. It may be derived from the diagram above. One can check if a list is empty using four equivalent conditions:
if (mylist.mlh_Head->mln_Succ == NULL) /* list is empty */ if (mylist.mlh_Head == (struct MinNode*)&mylist.mlh_Tail) /* list is empty */ if (mylist.mlh_TailPred->mln_Pred == NULL) /* list is empty */ if (mylist.mlh_TailPred == (struct MinNode*)&mylist.mlh_Head) /* list is empty */
A IsListEmpty() macro defined in <exec/lists.h> uses the last condition, simplified by the fact that address of mlh_Head is the same as address of the whole MinList (a good compiler will optimize field reference out anyway).
List Iterator
A list iterator is a fragment of code (usually a loop) used for traversing the list and performing operations on its elements. The simplest, browsing iterator is usually implemented as a for loop:
struct MyNode *n;
struct MinList *list; // let's assume it is initialized already
for (n = (struct MyNode*)list->mlh_Head; n->Node.mln_Succ; n = (struct MyNode*)n->Node.mln_Succ)
{
/* do something with node 'n' */
}
The first part of the for statement initializes the pointer n to the first real item of the list (the successor of the head item). The second part is the loop end condition. Loop ends when successor of the current element is NULL, which happens when the current element is the list tail. Then the loop contents is not executed for the tail, as the tail is not a "real" item, as said above. Finally the third part of for statement moves the pointer to the next list item. A symmetric iterator may be written for browsing a list from the end in backward direction:
for (n = (struct MyNode*)list->mlh_TailPred; n->Node.mln_Pred; n = (struct MyNode*)n->
Node.mln_Pred)
{
/* do something with node 'n' */
}
This time the pointer n is initialized to the last real item (predecessor of the list tail), pointer is moved to the previous item in each loop turn. The loop finishes, when the predecessor of the current item is NULL, which is the case for the list head. Again, the loop is not executed for the list head itself.
The <exec/lists.h> header file provides ForeachNode() macro for building a for based iterator. The macro is a bit dangerous however, because it blindly typecasts the node pointer to struct Node* and the list pointer to struct List*. It effectively bypasses the static C language type control and can lead to bugs in code. It is much safer to cast the node pointer to the real type of the list item, as shown in the above example iterators. Then a safer iterator macro should take the type name as one of arguments:
#define ForEachNode(n, T, list) for (n = (T)(list)->mlh_Head; n->Node.mln_Succ; \ n = (T)n->Node.mln_Succ)
The macro may be used as follows:
ForEachNode(n, struct MyNode*, list)
{
/* do something with node 'n' */
}
This macro is not so universal, as it assumes MinList list and also assumes that the MinNode field placed at the start of MyNode structure is named Node. On the other hand it puts static type control in good use. A similar macro may be defined for a backward iterator. In C++ language Exec lists iterators may be defined as templates.
Removing List Items From Inside of an Iterator
Some attention has to be put to a case when iterator is used for selective removal of items. Someone may try to do it as follows:
/* BAD CODE EXAMPLE */
ForEachNode(n, MyNode, list)
{
if (/*some condition*/)
{
Remove((struct Node*)n);
FreeVec(n);
}
}
Why the code above is buggy? If the item n is being removed and its memory freed, reference to n in the next loop turn is in fact a reference to free memory. In most cases the memory contents will stay unchanged. That is why such a bug is so popular, it may go unnoticed if the code is not tested enough. Nothing stops the process scheduler to switch our process out, then the memory may be allocated by another process and its contents overwritten. Then, when control will be returned to our process, n points to undefined data and the loop crashes. A solution of this problem is to read the successor from an item before the item is freed. It requires a second pointer to be defined:
struct MyNode *n, *n2;
for (n = (struct MyNode*)list->mlh_Head; n2 = (struct MyNode*)n->Node.mln_Succ; n = n2)
{
if (/* some condition */)
{
Remove((struct Node*)n);
FreeVec(n);
}
}
Now a pointer to the successor of item n is stored in n2 before the item n is freed. At the next loop turn, the iterator moves to the next item and checks for the list end using valid n2 pointer instead of a reference to free memory.
Things are easier when all items on the list are to be removed unconditionally, so the list is made empty and all the items are disposed. Of course one can still use the safe loop above, but there is a bit faster alternative:
while (n = (struct MyNode*)RemHead((struct List*)list)) FreeVec(n);
RemTail() function may be used in this loop as well, because when one removes all the items, the order does not matter usually.
Adding and Removing Items
Adding an item in arbitrary position of a list requires only updating 4 pointers, regardless of the item size. The diagram below explains the operation.
Inserting an item into an Exec list.
The diagam corresponds to the following code:
struct MyNode *n; /* insert after this item */ struct MyNode *a; /* insert this */ n->Node.mln_Succ->mln_Pred = &a.Node; /* 1 */ a->Node.mln_Succ = n->Node.mln_Succ; /* 2 */ a->Node.mln_Pred = &n.Node; /* 3 */ n->Node.mln_Succ = &a.Node; /* 4 */
Observe the order of operations. It is important. If one starts from operation 4 for example, he would loose the only link to the rest of the list after the insert position.
Removing link is even faster, as it only requires modifying two pointers: one in the predecessor of removed item and one in its successor. Let's assume element n is to be removed:
n->Node.mln_Pred->mln_Succ = n->Node.mln_Succ; n->Node.mln_Succ->mln_Pred = n->Node.mln_Pred;
Insert and remove operations have been standarizded in MorphOS in two ways: as exec.library API calls and as macros. The library functions are Insert() and Remove(), their macro counterparts are named INSERT() and REMOVE(). Both Insert() function and INSERT() macro take also a pointer to list header. While it is not neccesary in general case, it allows to handle the case when an item is inserted as the first one by passing NULL as the insert position. Inserting as the first element can be also done by passing the list header address as the insert position.
It should be noted, that both Remove() function and REMOVE() macro do not verify if the removed node is really in any list. Any attempt to "remove" a node not being in a list may result in random memory trashing and horrible crash.
Head and Tail
The most common operations of inserting and removing elements are performed on both the ends of a list. For example common data structures like stack or queue may be implemented using list. For stack, items are added at the list head and also removed from the head. For queue items are added at the tail and removed at the head.
Having a list head and tail pseudoitems gives an advantage, that operations at both list ends are not different than the general case. One just replaces – on the diagram in the previous subchapter – either the element before the insert position with the list head, or the element after the insert position with the list tail. The only difference comes from the fact that head and tail operations usually take just the address of the list header as their argument. The complete set of four operations is provided:
- AddHead() function and ADDHEAD() macro add a node as the first one.
- RemHead() function and REMHEAD() macro remove the first node and return its address.
- AddTail() function and ADDTAIL() macro add a node as the last one.
- RemTail() function and REMTAIL() macro remove the last node and return its address.
All these operations require only an address of the list header. Remove operations return the address of removed node, or NULL if the list is empty.
Functions or Macros?
After reading all the sections above it is clear, that most of the list operations is very simple and compiles to a few processor instructions. That is why they are also defined as macros. What to to use then? In general macros are faster, but some of them may be a few bytes longer than calls to library functions (especially INSERT()). On the other hand even a few kilobytes of additional code is usually not a problem nowadays, while gain in speed is often valuable. Then in places where speed is critical, macros are a better choice.
Enqueueing
Full list nodes have a priority field, named ln_Pri. The field is often used by the system to maintain prioritized lists or queues. To keep the list ordered by priority, a special insert operation is required. It is provided as an exec.library call named Enqueue(). The function takes a node (it must be full Node, not MinNode), reads its priority and finds a place for insert comparing priorities of nodes. If there are any nodes in the list with the same priority as the inserted one, it is inserted before already existing ones. Of course Enqueue() may be used also for implementing custom queues. One has to take into account however that the priority field is limited to signed 8-bit number and the function does not scale well for very long lists, as the insert position search is linear.