Copyright (c) Hyperion Entertainment and contributors.
Difference between revisions of "Exec Lists and Queues"
Steven Solie (talk | contribs) |
|||
(41 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | = 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 |
+ | 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 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 == |
== List Structure == |
||
Line 9: | Line 9: | ||
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. |
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. |
||
− | [[File:LibFig23-1.png]] |
+ | [[File:LibFig23-1.png|frame|center|Simplified Overview of an Exec List]] |
− | |||
− | 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. |
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. |
||
Line 17: | Line 15: | ||
=== Node Structure Definition === |
=== Node Structure Definition === |
||
− | A Node structure is divided into three parts: linkage, information, and content. The linkage part contains memory pointers to the |
+ | 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. |
+ | <syntaxhighlight> |
||
− | |||
+ | struct MinNode |
||
− | |||
− | <pre>struct MinNode |
||
{ |
{ |
||
struct MinNode *mln_Succ; |
struct MinNode *mln_Succ; |
||
struct MinNode *mln_Pred; |
struct MinNode *mln_Pred; |
||
− | }; |
+ | }; |
+ | </syntaxhighlight> |
||
− | points to the next node in the list (successor). |
||
+ | |||
+ | ; mln_Succ |
||
+ | : points to the next node in the list (successor). |
||
+ | ; mln_Pred |
||
− | points to the previous node in the list (predecessor). |
||
+ | : points to the previous node in the list (predecessor). |
||
When a type, priority, or name is required, a full-featured Node structure is used. |
When a type, priority, or name is required, a full-featured Node structure is used. |
||
+ | <syntaxhighlight> |
||
− | <pre>struct Node |
||
+ | struct Node |
||
{ |
{ |
||
struct Node *ln_Succ; |
struct Node *ln_Succ; |
||
struct Node *ln_Pred; |
struct Node *ln_Pred; |
||
− | + | uint8 ln_Type; |
|
− | + | int8 ln_Pri; |
|
− | + | STRPTR ln_Name; |
|
− | }; |
+ | }; |
+ | </syntaxhighlight> |
||
− | defines the type of the node (see <exec/nodes.h> for a list). |
||
+ | ; ln_Type |
||
− | specifies the priority of the node (+127 (highest) to -128 (lowest)). |
||
+ | : defines the type of the node (see <exec/nodes.h> for a complete list of types). |
||
+ | ; ln_Pri |
||
− | points to a printable name for the node (a NULL-terminated string). |
||
+ | : specifies the priority of the node, ranging from +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: |
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: |
||
+ | <syntaxhighlight> |
||
− | <pre>struct Interrupt |
||
+ | struct Interrupt |
||
{ |
{ |
||
struct Node is_Node; |
struct Node is_Node; |
||
APTR is_Data; |
APTR is_Data; |
||
VOID (*is_Code)(); |
VOID (*is_Code)(); |
||
− | }; |
+ | }; |
+ | </syntaxhighlight> |
||
+ | |||
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. |
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 === |
=== 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 ( |
+ | 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. (Note: this is only relevant to Node structures. The simpler 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_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. Custom node types are allowed, and should be defined ''downwards'' from NT_USER, for example like this: |
+ | |||
+ | <syntaxhighlight> |
||
+ | #define NT_MYTYPE1 NT_USER |
||
+ | #define NT_MYTYPE2 (NT_USER - 1) |
||
+ | #define NT_MYTYPE3 (NT_USER - 2) |
||
+ | /* etc., you get the idea */ |
||
+ | </syntaxhighlight> |
||
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_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. |
||
Line 66: | Line 83: | ||
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. |
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 |
+ | This code fragment initializes a Node called ''sample.interrupt'', an instance of the Interrupt data structure introduced above: |
+ | <syntaxhighlight> |
||
− | <pre>struct Interrupt interrupt; |
||
+ | struct Interrupt interrupt; |
||
interrupt.is_Node.ln_Type = NT_INTERRUPT; |
interrupt.is_Node.ln_Type = NT_INTERRUPT; |
||
interrupt.is_Node.ln_Pri = -10; |
interrupt.is_Node.ln_Pri = -10; |
||
− | interrupt.is_Node.ln_Name = |
+ | interrupt.is_Node.ln_Name = "sample.interrupt"; |
+ | </syntaxhighlight> |
||
+ | |||
=== List Header Structure Definition === |
=== List Header Structure Definition === |
||
Line 79: | Line 99: | ||
The structure MinList defines a minimum list header. |
The structure MinList defines a minimum list header. |
||
+ | <syntaxhighlight> |
||
− | <pre>struct MinList |
||
+ | struct MinList |
||
{ |
{ |
||
struct MinNode *mlh_Head; |
struct MinNode *mlh_Head; |
||
struct MinNode *mlh_Tail; |
struct MinNode *mlh_Tail; |
||
struct MinNode *mlh_TailPred; |
struct MinNode *mlh_TailPred; |
||
− | }; |
+ | }; |
+ | </syntaxhighlight> |
||
− | points to the first node in the list. |
||
+ | |||
+ | ; mlh_Head |
||
+ | : points to the first node in the list. |
||
+ | ; mlh_Tail |
||
− | is always NULL. |
||
+ | : is always NULL. |
||
+ | ; mlh_TailPred |
||
− | points to the last node in the list. |
||
+ | : points to the last node in the list. |
||
In a few limited cases a full-featured List structure will be required: |
In a few limited cases a full-featured List structure will be required: |
||
+ | <syntaxhighlight> |
||
− | <pre>struct List |
||
+ | struct List |
||
{ |
{ |
||
struct Node *lh_Head; |
struct Node *lh_Head; |
||
struct Node *lh_Tail; |
struct Node *lh_Tail; |
||
struct Node *lh_TailPred; |
struct Node *lh_TailPred; |
||
− | + | uint8 lh_Type; |
|
− | + | uint8 lh_Pad; |
|
− | }; |
+ | }; |
+ | </syntaxhighlight> |
||
− | defines the type of nodes within the list (see <exec/nodes.h>). |
||
+ | |||
+ | ; lh_Type |
||
+ | : defines the type of nodes within the list (see <exec/nodes.h>). |
||
+ | ; lh_Pad |
||
− | is a structure alignment byte. |
||
+ | : 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. |
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. |
||
− | [[File:LibFig23-2.png]] |
+ | [[File:LibFig23-2.png|frame|center|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. |
||
− | Figure 23-2: List Header Overlap |
||
− | + | 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. |
|
− | |||
− | 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 === |
=== Header Initialization === |
||
Line 124: | Line 153: | ||
# Set lh_Type to the same data type as the nodes to be kept the list. (Unless you are using a MinList). |
# Set lh_Type to the same data type as the nodes to be kept the list. (Unless you are using a MinList). |
||
− | [[File:LibFig23-3.png]] |
+ | [[File:LibFig23-3.png|frame|center|Initializing a List Header Structure]] |
+ | The functions NewList() and NewMinList() are provided to properly initialize a List or a MinList, respectively, prior to use. This is not required if you create the List or MinList using AllocSysObject() because this function takes care of the initialization. The following call creates an empty Exec List of the NT_FONT type and initializes its header for you: |
||
− | Figure 23-3: Initializing a List Header Structure |
||
+ | <syntaxhighlight> |
||
− | The sequence of assembly instructions in the figure above is equivalent to the macro NEWLIST, contained in the include file <exec/lists.i>. Since the MinList structure is the same as the List structure except for the type and pad fields, this sequence of assembly language code will work for both structures. The sequence performs its function without destroying the pointer to the list header in A0 (which is why ADDQ.L is used). This function may also be accessed from C as a call to NewList(header), where header is the address of a list header. |
||
+ | struct List *newFontList; |
||
+ | newFontList = (struct List *) IExec->AllocSysObjectTags(ASOT_LIST, |
||
− | == List Functions == |
||
+ | ASOLIST_Type, NT_FONT, |
||
+ | TAG_END); |
||
+ | if ( newFontList == NULL ) |
||
+ | IDOS->Printf("Out of memory\n"); |
||
+ | </syntaxhighlight> |
||
+ | Lists or MinLists created via AllocSysObject() must be disposed of using a corresponding FreeSysObject() call. Please note that the list must always be empty before disposal – FreeSysObject() does not handle node removal, so failing to free your list nodes will cause a memory leak! |
||
+ | == 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 );<br /> |
||
− | VOID AddTail( struct List *list, struct Node *node );<br /> |
||
− | VOID Enqueue( struct List *list, struct Node *node );<br /> |
||
− | struct Node *FindName( struct List *list, UBYTE *name );<br /> |
||
− | VOID Insert( struct List *list, struct Node *node, struct Node *pred );<br /> |
||
− | VOID Remove( struct Node *node );<br /> |
||
− | struct Node *RemHead( struct List *list );<br /> |
||
− | struct Node *RemTail( struct List *list ); |
||
− | |||
− | VOID NewList( struct List *list ); |
||
+ | 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. |
||
− | 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 === |
+ | === 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 |
+ | 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. |
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 === |
=== 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. |
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 === |
=== 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. |
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 |
+ | 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 returns a NULL result. |
=== MinList / MinNode Operations === |
=== MinList / MinNode Operations === |
||
Line 175: | Line 196: | ||
=== Prioritized Insertion === |
=== 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. |
||
+ | {{Note|title=FIFO Is Used For The Same Priority|text=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.}} |
||
− | |||
− | 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. |
||
− | |||
− | <sub>b</sub>oxFIFO 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 === |
=== Searching by Name === |
||
Line 185: | Line 204: | ||
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. |
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 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, use the FindIName() function. |
||
− | [[File:LibFig23-4.png]] |
||
+ | Quite naturally, you cannot use FindName() or FindIName() with MinLists because these do not support named nodes. |
||
− | Figure 23-4: Complete Sample List Showing all Interconnections |
||
+ | [[File:LibFig23-4.png|frame|center|Complete Sample List Showing all Interconnections]] |
||
− | === More on the Use of Named Lists === |
||
+ | === More on the Use of Named Nodes === |
||
− | To find multiple occurrences of nodes with identical names, the FindName() function is called multiple times. For example, if you want to find all the nodes with the name pointed to by name: |
||
+ | 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: |
||
− | <pre>VOID DisplayName(struct List *list,UBYTE *name) |
||
+ | |||
+ | <syntaxhighlight> |
||
+ | VOID DisplayName(struct List *list, CONST_STRPTR name) |
||
{ |
{ |
||
struct Node *node; |
struct Node *node; |
||
− | if (node = FindName(list,name)) |
+ | if ( (node = IExec->FindName(list, name)) ) |
− | while (node) |
+ | while ( node ) |
{ |
{ |
||
− | + | IDOS->Printf("Found %s at location %lx\n", node->ln_Name, node); |
|
− | node = FindName((struct List *)node,name); |
+ | node = IExec->FindName((struct List *)node, name); |
} |
} |
||
− | else |
+ | else IDOS->Printf("No node with name %s found.\n", name); |
+ | } |
||
− | }</pre> |
||
+ | </syntaxhighlight> |
||
+ | |||
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. |
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. |
||
− | === List Macros for Assembly Language Programmers === |
||
− | |||
− | Assembly language programmers may want to optimize their code by using assembly code list macros. Because these macros actually embed the specified list operation into the code, they result in slightly faster operations. The file <exec/lists.i> contains the recommended set of macros. |
||
− | |||
− | For example, the following instructions implement the REMOVE macro: |
||
− | |||
− | <pre>MOVE.L LN_SUCC(A1),A0 ; get successor |
||
− | MOVE.L LN_PRED(A1),A1 ; get predecessor |
||
− | MOVE.L A0,LN_SUCC(A1) ; fix up predecessor's succ pointer |
||
− | MOVE.L A1,LN_PRED(A0) ; fix up successor's pred pointer</pre> |
||
=== Empty Lists === |
=== 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. |
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: |
|
+ | <syntaxhighlight> |
||
− | <pre>/* You can use this method... */ |
||
+ | /* You can use this method... */ |
||
− | if (list->lh_TailPred == (struct Node *)list) |
||
+ | if ( list->lh_TailPred == (struct Node *)list ) |
||
− | printf("list is empty\n"); |
||
+ | IDOS->Printf("list is empty\n"); |
||
/* Or you can use this method */ |
/* Or you can use this method */ |
||
− | if (NULL == list- |
+ | if ( NULL == list->lh_Head->ln_Succ ) |
− | + | IDOS->Printf("list is empty\n"); |
|
+ | </syntaxhighlight> |
||
− | In assembly code, if A0 points to the list header, these methods would be written as follows: |
||
+ | Macros are available to make the code easier to read: |
||
− | <pre>; Use this method... |
||
− | CMP.L LH_TAILPRED(A0),A0 |
||
− | BEQ list_is_empty |
||
+ | <syntaxhighlight> |
||
− | ; Or use this method |
||
+ | struct List *list; |
||
− | MOVE.L LH_HEAD(A0),A1 |
||
+ | struct MinList *minlist; |
||
− | TST.L LN_SUCC(A1) |
||
+ | |||
− | BEQ list_is_empty</pre> |
||
+ | if ( IsListEmpty(list) ) |
||
− | Because LH_HEAD and LN_SUCC are both zero offsets, the second case may be simplified or optimized by your assembler. |
||
+ | IDOS->Printf("list is empty\n"); |
||
+ | |||
+ | if ( IsMinListEmpty(minlist) ) |
||
+ | IDOS->Printf("minlist is empty\n"); |
||
+ | </syntaxhighlight> |
||
=== Scanning a List === |
=== Scanning a List === |
||
Line 248: | Line 266: | ||
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. |
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: 1) via direct manipulation of the pointers, and 2) using dedicated functions from Exec. |
||
− | Here is a code fragment that uses a ''for'' loop to print the names of all nodes in a list: |
||
+ | |||
+ | Here is a code fragment that uses pointers and a ''for'' loop to print the names of all nodes in a list: |
||
+ | <syntaxhighlight> |
||
− | <pre>struct List *list; |
||
+ | struct List *list; |
||
struct Node *node; |
struct Node *node; |
||
− | for (node = list- |
+ | for ( node = list->lh_Head ; node->ln_Succ != NULL ; node = node->ln_Succ ) |
− | + | IDOS->Printf("%p -> %s\n", node, node->ln_Name); |
|
+ | </syntaxhighlight> |
||
− | 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. |
||
+ | 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. |
||
− | In assembly code, it is more efficient to use a look-ahead cache pointer when scanning a list. In this example the list is scanned until the first zero-priority node is reached: |
||
+ | 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: |
||
− | <pre> MOVE.L (A1),D1 ; first node |
||
− | scan: MOVE.L D1,A1 |
||
− | MOVE.L (A1),D1 ; lookahead to next |
||
− | BEQ.S not_found ; end of list... |
||
− | TST.B LN_PRI(A1) |
||
− | BNE.S scan |
||
− | ... ; found one |
||
+ | <syntaxhighlight> |
||
− | not_found:</pre> |
||
− | + | struct List *list; |
|
+ | struct Node *node, *next; |
||
+ | for ( node = list->lh_Head; (next = node->ln_Succ) != NULL ; node = next ) |
||
+ | { |
||
+ | /* Do something with the node. */ |
||
+ | /* This may include node removal from the list. */ |
||
+ | if ( some_condition ) |
||
+ | { |
||
+ | IExec->Remove(node); |
||
+ | } |
||
+ | } |
||
+ | </syntaxhighlight> |
||
+ | Here is a code fragment that uses functions and a ''for'' loop to print the names of all nodes in a list: |
||
+ | <syntaxhighlight> |
||
− | The code below demonstrates the concepts and functions discussed in this chapter by building an application-defined Exec List. |
||
+ | struct List *list; |
||
+ | struct Node *node; |
||
+ | for ( node = IExec->GetHead(list) ; node != NULL ; node = IExec->GetSucc(node) ) |
||
− | <pre>;/* buildlist.c - Execute me to compile me with SAS C 5.10 |
||
+ | IDOS->Printf("%p -> %s\n", node, node->ln_Name); |
||
− | LC -b1 -cfistq -v -y -j73 buildlist.c |
||
+ | </syntaxhighlight> |
||
− | Blink FROM LIB:c.o,buildlist.o TO buildlist LIBRARY LIB:LC.lib,LIB:Amiga.lib |
||
− | quit |
||
+ | Here is an example showing how to properly remove a node from a list while traversing: |
||
− | buildlist.c - example which uses an application-specific Exec list |
||
+ | |||
− | */ |
||
+ | <syntaxhighlight> |
||
+ | struct List *list; |
||
+ | struct Node *node, *next; |
||
+ | |||
+ | for ( node = IExec->GetHead(list); node != NULL; node = next ) |
||
+ | { |
||
+ | next = IExec->GetSucc(node); |
||
+ | /* Do something with the node. */ |
||
+ | /* This may include node removal from the list. */ |
||
+ | if ( some_condition ) |
||
+ | { |
||
+ | IExec->Remove(node); |
||
+ | } |
||
+ | } |
||
+ | </syntaxhighlight> |
||
+ | |||
+ | 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. |
||
+ | |||
+ | === Finding the List of a Node === |
||
+ | |||
+ | In an Exec List, the address of the header is used as the handle to the entire list so we can find the List given only a Node. |
||
+ | |||
+ | <syntaxhighlight> |
||
+ | struct List *findListOfNode(struct Node *node) |
||
+ | { |
||
+ | struct List *head = NULL; |
||
+ | |||
+ | if ( node != NULL ) |
||
+ | { |
||
+ | while ( node->ln_Pred != NULL ) |
||
+ | { |
||
+ | node = node->ln_Pred; |
||
+ | } |
||
+ | |||
+ | head = (struct List*)node; |
||
+ | } |
||
+ | |||
+ | return head; |
||
+ | } |
||
+ | </syntaxhighlight> |
||
+ | |||
+ | ==== Exec List Example ==== |
||
+ | The code below demonstrates the concepts and functions discussed in this section by building an application-defined Exec List. |
||
− | #include <exec/types.h> |
||
− | #include <exec/lists.h> |
||
− | #include <exec/nodes.h> |
||
− | #include <exec/memory.h> |
||
+ | <syntaxhighlight> |
||
− | #include <clib/alib_protos.h> |
||
+ | // buildlist.c - example which uses an application-specific Exec list |
||
− | #include <clib/exec_protos.h> |
||
− | #include |
+ | #include <exec/types.h> |
− | #include |
+ | #include <exec/lists.h> |
+ | #include <exec/nodes.h> |
||
+ | #include <exec/memory.h> |
||
+ | #include <proto/exec.h> |
||
− | #ifdef LATTICE |
||
+ | #include <proto/dos.h> |
||
− | int CXBRK(void) { return(0); } /* Disable Lattice CTRL/C handling */ |
||
+ | #include <proto/utility.h> |
||
− | void chkabort(void) { return; } /* really */ |
||
− | #endif |
||
/* Our function prototypes */ |
/* Our function prototypes */ |
||
− | VOID AddName(struct List *, |
+ | VOID AddName(struct List *, CONST_STRPTR); |
VOID FreeNameNodes(struct List *); |
VOID FreeNameNodes(struct List *); |
||
VOID DisplayNameList(struct List *); |
VOID DisplayNameList(struct List *); |
||
− | VOID DisplayName(struct List *, |
+ | VOID DisplayName(struct List *, CONST_STRPTR); |
struct NameNode { |
struct NameNode { |
||
struct Node nn_Node; /* System Node structure */ |
struct Node nn_Node; /* System Node structure */ |
||
− | + | TEXT nn_Data[62]; /* Node-specific data */ |
|
}; |
}; |
||
− | #define NAMENODE_ID 100 /* The type of |
+ | #define NAMENODE_ID 100 /* The type of "NameNode" */ |
− | + | int main() |
|
{ |
{ |
||
− | struct |
+ | struct List *nameList; |
− | + | nameList = (struct List *) IExec->AllocSysObjectTags(ASOT_LIST, TAG_END); |
|
+ | |||
− | printf("Out of memory\n"); |
||
+ | if ( nameList == NULL ) |
||
+ | IDOS->Printf("Out of memory\n"); |
||
else { |
else { |
||
+ | AddName(nameList,"Name7"); AddName(nameList,"Name6"); |
||
− | NewList(NameList); /* Important: prepare header for use */ |
||
+ | AddName(nameList,"Name5"); AddName(nameList,"Name4"); |
||
+ | AddName(nameList,"Name2"); AddName(nameList,"Name0"); |
||
− | AddName( |
+ | AddName(nameList,"Name7"); AddName(nameList,"Name5"); |
− | AddName( |
+ | AddName(nameList,"Name3"); AddName(nameList,"Name1"); |
− | AddName(NameList,"Name2"); AddName(NameList,"Name0"); |
||
+ | DisplayName(nameList,"Name5"); |
||
− | AddName(NameList,"Name7"); AddName(NameList,"Name5"); |
||
+ | DisplayNameList(nameList); |
||
− | AddName(NameList,"Name3"); AddName(NameList,"Name1"); |
||
− | + | FreeNameNodes(nameList); |
|
+ | IExec->FreeSysObject(ASOT_LIST, nameList); /* Free list header */ |
||
− | DisplayNameList(NameList); |
||
− | |||
− | FreeNameNodes(NameList); |
||
− | FreeMem(NameList,sizeof(struct List)); /* Free list header */ |
||
} |
} |
||
+ | |||
+ | return 0; |
||
} |
} |
||
Line 339: | Line 409: | ||
* error return for the out of memory condition. |
* error return for the out of memory condition. |
||
*/ |
*/ |
||
− | VOID AddName(struct List *list, |
+ | VOID AddName(struct List *list, CONST_STRPTR name) |
{ |
{ |
||
− | struct NameNode * |
+ | struct NameNode *nameNode = IExec->AllocSysObjectTags(ASOT_NODE, |
+ | ASONODE_Size, sizeof(struct NameNode), |
||
+ | ASONODE_Type, NAMENODE_ID, |
||
+ | TAG_END); |
||
+ | if ( nameNode == NULL ) |
||
− | if (!( namenode = AllocMem(sizeof(struct NameNode),MEMF_CLEAR) )) |
||
− | + | IDOS->Printf("Out of memory\n"); |
|
else { |
else { |
||
− | + | IUtility->Strlcpy(nameNode->nn_Data, name, sizeof(nameNode->nn_Data)); |
|
− | + | nameNode->nn_Node.ln_Name = nameNode->nn_Data; |
|
+ | IExec->AddHead((struct List *)list, (struct Node *)nameNode); |
||
− | namenode->nn_Node.ln_Type = NAMENODE_ID; |
||
− | namenode->nn_Node.ln_Pri = 0; |
||
− | AddHead((struct List *)list,(struct Node *)namenode); |
||
} |
} |
||
} |
} |
||
Line 356: | Line 427: | ||
/* |
/* |
||
* Free the entire list, including the header. The header is not updated |
* Free the entire list, including the header. The header is not updated |
||
− | * as the list is freed. |
+ | * as the list is freed. This function demonstrates how to avoid |
* referencing freed memory when deallocating nodes. |
* referencing freed memory when deallocating nodes. |
||
*/ |
*/ |
||
VOID FreeNameNodes(struct List *list) |
VOID FreeNameNodes(struct List *list) |
||
{ |
{ |
||
− | struct NameNode * |
+ | struct NameNode *workNode; |
− | struct NameNode * |
+ | struct NameNode *nextNode; |
− | + | workNode = (struct NameNode *) IExec->GetHead(list); /* First node */ |
|
− | while ( |
+ | while ( (nextNode = (struct NameNode *) IExec->GetSucc((struct Node *)workNode)) ) { |
− | + | IExec->FreeSysObject(ASOT_NODE, workNode); |
|
− | + | workNode = nextNode; |
|
} |
} |
||
− | |||
} |
} |
||
Line 377: | Line 447: | ||
VOID DisplayNameList(struct List *list) |
VOID DisplayNameList(struct List *list) |
||
{ |
{ |
||
− | struct Node *node; |
+ | struct Node *node; |
+ | if ( IsListEmpty(list) ) |
||
− | if (list->lh_TailPred == (struct Node *)list) |
||
− | + | IDOS->Printf("List is empty.\n"); |
|
else { |
else { |
||
− | for (node = list |
+ | for ( node = IExec->GetHead(list); node != NULL; node = IExec->GetSucc(node) ) |
− | + | IDOS->Printf("%lx -> %s\n", node, node->ln_Name); |
|
} |
} |
||
} |
} |
||
Line 390: | Line 460: | ||
* Print the location of all nodes with a specified name. |
* Print the location of all nodes with a specified name. |
||
*/ |
*/ |
||
− | VOID DisplayName(struct List *list, |
+ | VOID DisplayName(struct List *list, CONST_STRPTR name) |
{ |
{ |
||
− | struct Node *node; |
+ | struct Node *node; |
− | if (node = FindName(list,name)) { |
+ | if ( (node = IExec->FindName(list, name)) ) { |
− | while (node) { |
+ | while ( node ) { |
− | + | IDOS->Printf("Found a %s at location %lx\n", node->ln_Name, node); |
|
− | node = FindName((struct List *)node,name); |
+ | node = IExec->FindName((struct List *)node, name); |
} |
} |
||
− | } else |
+ | } else IDOS->Printf("No node with name %s found.\n", name); |
+ | } |
||
− | }</pre> |
||
+ | </syntaxhighlight> |
||
+ | |||
=== Important Note About Shared Lists === |
=== 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. |
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 |
+ | 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|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|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. |
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. |
||
Line 413: | Line 485: | ||
== Function Reference == |
== Function Reference == |
||
− | The following |
+ | The following table gives a brief description of the Exec list and queue functions and macros. See the SDK for details about each call. |
− | |||
− | |||
− | |||
− | [h] Exec List and Queue Functions |
||
− | |||
− | <table> |
||
− | <thead> |
||
− | <tr class="header"> |
||
− | <th align="left">'''Exec Function'''</th> |
||
− | <th align="left">'''Description'''</th> |
||
− | </tr> |
||
− | </thead> |
||
− | <tbody> |
||
− | <tr class="odd"> |
||
− | <td align="left">AddHead()</td> |
||
− | <td align="left">Insert a node at the head of a list.</td> |
||
− | </tr> |
||
− | <tr class="even"> |
||
− | <td align="left">AddTail()</td> |
||
− | <td align="left">Append a node to the tail of a list.</td> |
||
− | </tr> |
||
− | <tr class="odd"> |
||
− | <td align="left">Enqueue()</td> |
||
− | <td align="left">Insert or append a node to a system queue.</td> |
||
− | </tr> |
||
− | <tr class="even"> |
||
− | <td align="left">FindName()</td> |
||
− | <td align="left">Find a node with a given name in a system list.</td> |
||
− | </tr> |
||
− | <tr class="odd"> |
||
− | <td align="left">Insert()</td> |
||
− | <td align="left">Insert a node into a list.</td> |
||
− | </tr> |
||
− | <tr class="even"> |
||
− | <td align="left">IsListEmpty</td> |
||
− | <td align="left">Test if list is empty</td> |
||
− | </tr> |
||
− | <tr class="odd"> |
||
− | <td align="left">NewList()</td> |
||
− | <td align="left">Initialize a list structure for use.</td> |
||
− | </tr> |
||
− | <tr class="even"> |
||
− | <td align="left">RemHead()</td> |
||
− | <td align="left">Remove the head node from a list.</td> |
||
− | </tr> |
||
− | <tr class="odd"> |
||
− | <td align="left">Remove()</td> |
||
− | <td align="left">Remove a node from a list.</td> |
||
− | </tr> |
||
− | <tr class="even"> |
||
− | <td align="left">RemTail()</td> |
||
− | <td align="left">Remove the tail node from a list.</td> |
||
− | </tr> |
||
− | </tbody> |
||
− | </table> |
||
− | |||
− | [h] Exec List and Queue Assembler Macros |
||
+ | {| class="wikitable" |
||
− | <table> |
||
+ | ! Exec Function |
||
− | <thead> |
||
+ | ! Description |
||
− | <tr class="header"> |
||
+ | |- |
||
− | <th align="left">'''Exec Function'''</th> |
||
+ | | AddHead() |
||
− | <th align="left">'''Description'''</th> |
||
+ | | Insert a node at the head of a list. |
||
− | </tr> |
||
+ | |- |
||
− | </thead> |
||
+ | | AddTail() |
||
− | <tbody> |
||
+ | | Append a node to the tail of a list. |
||
− | <tr class="odd"> |
||
+ | |- |
||
− | <td align="left">NEWLIST</td> |
||
+ | | AllocSysObject(ASOT_LIST) |
||
− | <td align="left">Initialize a list header for use.</td> |
||
+ | | Allocate and initialize a new List or MinList. |
||
− | </tr> |
||
+ | |- |
||
− | <tr class="even"> |
||
+ | | AllocSysObject(ASOT_NODE) |
||
− | <td align="left">TSTLIST</td> |
||
+ | | Allocate and initialize a new list node. |
||
− | <td align="left">Test if list is empty (list address in register). No arbitration needed.</td> |
||
+ | |- |
||
− | </tr> |
||
+ | | Enqueue() |
||
− | <tr class="odd"> |
||
+ | | Insert or append a node to a system queue. |
||
− | <td align="left">TSTLST2</td> |
||
+ | |- |
||
− | <td align="left">Test is list is empty (from effective address of list). Arbitration needed.</td> |
||
+ | | FindIName() |
||
− | </tr> |
||
+ | | Find a node with a given name in a system list ignoring case. |
||
− | <tr class="even"> |
||
+ | |- |
||
− | <td align="left">SUCC</td> |
||
+ | | FindName() |
||
− | <td align="left">Get next node in a list.</td> |
||
+ | | Find a node with a given name in a system list. |
||
− | </tr> |
||
+ | |- |
||
− | <tr class="odd"> |
||
+ | | FreeSysObject(ASOT_LIST) |
||
− | <td align="left">PRED</td> |
||
+ | | Free an allocated List or MinList. |
||
− | <td align="left">Get previous node in a list.</td> |
||
+ | |- |
||
− | </tr> |
||
+ | | FreeSysObject(ASOT_NODE) |
||
− | <tr class="even"> |
||
+ | | Free an allocated list node. |
||
− | <td align="left">IFEMPTY</td> |
||
+ | |- |
||
− | <td align="left">Branch if list is empty.</td> |
||
+ | | GetHead() |
||
− | </tr> |
||
+ | | Gets the head node of a list. |
||
− | <tr class="odd"> |
||
+ | |- |
||
− | <td align="left">IFNOTEMPTY</td> |
||
+ | | GetPred() |
||
− | <td align="left">Branch if list is not empty.</td> |
||
+ | | Gets the node predecessor. |
||
− | </tr> |
||
+ | |- |
||
− | <tr class="even"> |
||
+ | | GetSucc() |
||
− | <td align="left">TSTNODE</td> |
||
+ | | Gets the node successor. |
||
− | <td align="left">Get next node, test if at end of list.</td> |
||
+ | |- |
||
− | </tr> |
||
+ | | GetTail() |
||
− | <tr class="odd"> |
||
+ | | Gets the tail node of a list. |
||
− | <td align="left">NEXTNODE</td> |
||
+ | |- |
||
− | <td align="left">Get next node, go to exit label if at end.</td> |
||
+ | | Insert() |
||
− | </tr> |
||
+ | | Insert a node into a list. |
||
− | <tr class="even"> |
||
+ | |- |
||
− | <td align="left">ADDHEAD</td> |
||
+ | | IsMinListEmpty |
||
− | <td align="left">Add node to head of list.</td> |
||
+ | | Test if minimal list is empty |
||
− | </tr> |
||
+ | |- |
||
− | <tr class="odd"> |
||
+ | | IsListEmpty |
||
− | <td align="left">ADDTAIL</td> |
||
+ | | Test if list is empty |
||
− | <td align="left">Add node to tail of list.</td> |
||
+ | |- |
||
− | </tr> |
||
+ | | NewMinList() |
||
− | <tr class="even"> |
||
+ | | Initialize a minimal list structure for use. |
||
− | <td align="left">REMOVE</td> |
||
+ | |- |
||
− | <td align="left">Remove node from a list.</td> |
||
+ | | NewList() |
||
− | </tr> |
||
+ | | Initialize a list structure for use. |
||
− | <tr class="odd"> |
||
+ | |- |
||
− | <td align="left">REMHEAD</td> |
||
+ | | MoveList() |
||
− | <td align="left">Remove node from head of list.</td> |
||
+ | | Moves all the nodes from one list to another efficiently. |
||
− | </tr> |
||
+ | |- |
||
− | <tr class="even"> |
||
+ | | RemHead() |
||
− | <td align="left">REMHEADQ</td> |
||
− | + | | Remove the head node from a list. |
|
+ | |- |
||
− | </tr> |
||
+ | | Remove() |
||
− | <tr class="odd"> |
||
+ | | Remove a node from a list. |
||
− | <td align="left">REMTAIL</td> |
||
+ | |- |
||
− | <td align="left">Remove node from tail of list.</td> |
||
+ | | RemTail() |
||
− | </tr> |
||
+ | | Remove the tail node from a list. |
||
− | </tbody> |
||
+ | |} |
||
− | </table> |
Latest revision as of 18:29, 21 September 2017
Contents
- 1 Exec Lists and Queues
- 2 List Structure
- 3 List Functions
- 3.1 Node Insertion and Removal
- 3.2 Special Case Insertion
- 3.3 Special Case Removal
- 3.4 MinList / MinNode Operations
- 3.5 Prioritized Insertion
- 3.6 Searching by Name
- 3.7 More on the Use of Named Nodes
- 3.8 Empty Lists
- 3.9 Scanning a List
- 3.10 Finding the List of a Node
- 3.11 Important Note About Shared Lists
- 4 Function Reference
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.
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; uint8 ln_Type; int8 ln_Pri; STRPTR ln_Name; };
- ln_Type
- defines the type of the node (see <exec/nodes.h> for a complete list of types).
- ln_Pri
- specifies the priority of the node, ranging from +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. (Note: this is only relevant to Node structures. The simpler 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. Custom node types are allowed, and should be defined downwards from NT_USER, for example like this:
#define NT_MYTYPE1 NT_USER #define NT_MYTYPE2 (NT_USER - 1) #define NT_MYTYPE3 (NT_USER - 2) /* etc., you get the idea */
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 code fragment initializes a Node called sample.interrupt, 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; uint8 lh_Type; uint8 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.
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:
- Set the lh_Head field to the address of lh_Tail.
- Clear the lh_Tail field.
- Set the lh_TailPred field to the address of lh_Head.
- Set lh_Type to the same data type as the nodes to be kept the list. (Unless you are using a MinList).
The functions NewList() and NewMinList() are provided to properly initialize a List or a MinList, respectively, prior to use. This is not required if you create the List or MinList using AllocSysObject() because this function takes care of the initialization. The following call creates an empty Exec List of the NT_FONT type and initializes its header for you:
struct List *newFontList; newFontList = (struct List *) IExec->AllocSysObjectTags(ASOT_LIST, ASOLIST_Type, NT_FONT, TAG_END); if ( newFontList == NULL ) IDOS->Printf("Out of memory\n");
Lists or MinLists created via AllocSysObject() must be disposed of using a corresponding FreeSysObject() call. Please note that the list must always be empty before disposal – FreeSysObject() does not handle node removal, so failing to free your list nodes will cause a memory leak!
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.
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 returns 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, use the FindIName() function.
Quite naturally, you cannot use FindName() or FindIName() with MinLists because these do not support named nodes.
More on the Use of Named Nodes
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 the 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: 1) via direct manipulation of the pointers, and 2) using dedicated functions from Exec.
Here is a code fragment that uses pointers and a 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 != NULL ; 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; (next = node->ln_Succ) != NULL ; node = next ) { /* Do something with the node. */ /* This may include node removal from the list. */ if ( some_condition ) { IExec->Remove(node); } }
Here is a code fragment that uses functions and a for loop to print the names of all nodes in a list:
struct List *list; struct Node *node; for ( node = IExec->GetHead(list) ; 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 the node. */ /* This may include node removal from the 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.
Finding the List of a Node
In an Exec List, the address of the header is used as the handle to the entire list so we can find the List given only a Node.
struct List *findListOfNode(struct Node *node) { struct List *head = NULL; if ( node != NULL ) { while ( node->ln_Pred != NULL ) { node = node->ln_Pred; } head = (struct List*)node; } return head; }
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; nameList = (struct List *) 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 */ } return 0; } /* 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; IExec->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((struct Node *)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 IDOS->Printf("No node with name %s found.\n", name); }
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 table gives 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. |
AllocSysObject(ASOT_LIST) | Allocate and initialize a new List or MinList. |
AllocSysObject(ASOT_NODE) | Allocate and initialize a new list node. |
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. |
FreeSysObject(ASOT_LIST) | Free an allocated List or MinList. |
FreeSysObject(ASOT_NODE) | Free an allocated list node. |
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. |