Exec Lists and Queues - Revision history

Costel Mincea: Text replacement - "" to ""

2025-01-26T19:19:11Z

Text replacement - "<syntaxhighlight>" to "<syntaxhighlight lang="C" line>"

← Older revision		Revision as of 19:19, 26 January 2025
Line 17:		Line 17:
	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.		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>		<syntaxhighlight lang="C" line>
	struct MinNode		struct MinNode
	{		{
Line 33:		Line 33:
	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>		<syntaxhighlight lang="C" line>
	struct Node		struct Node
	{		{
Line 55:		Line 55:
	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>		<syntaxhighlight lang="C" line>
	struct Interrupt		struct Interrupt
	{		{
Line 72:		Line 72:
	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:		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>		<syntaxhighlight lang="C" line>
	#define NT_MYTYPE1 NT_USER		#define NT_MYTYPE1 NT_USER
	#define NT_MYTYPE2 (NT_USER - 1)		#define NT_MYTYPE2 (NT_USER - 1)
Line 85:		Line 85:
	This code fragment initializes a Node called ''sample.interrupt'', an instance of the Interrupt data structure introduced above:		This code fragment initializes a Node called ''sample.interrupt'', an instance of the Interrupt data structure introduced above:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct Interrupt interrupt;		struct Interrupt interrupt;

Line 99:		Line 99:
	The structure MinList defines a minimum list header.		The structure MinList defines a minimum list header.

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct MinList		struct MinList
	{		{
Line 119:		Line 119:
	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>		<syntaxhighlight lang="C" line>
	struct List		struct List
	{		{
Line 157:		Line 157:
	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:		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:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct List *newFontList;		struct List *newFontList;

Line 216:		Line 216:
	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:		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:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	VOID DisplayName(struct List *list, CONST_STRPTR name)		VOID DisplayName(struct List *list, CONST_STRPTR name)
	{		{
Line 239:		Line 239:
	These methods would be written as follows:		These methods would be written as follows:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	/* You can use this method... */		/* You can use this method... */
	if ( list->lh_TailPred == (struct Node *)list )		if ( list->lh_TailPred == (struct Node *)list )
Line 251:		Line 251:
	Macros are available to make the code easier to read:		Macros are available to make the code easier to read:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct List *list;		struct List *list;
	struct MinList *minlist;		struct MinList *minlist;
Line 270:		Line 270:
	Here is a code fragment that uses pointers and 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>		<syntaxhighlight lang="C" line>
	struct List *list;		struct List *list;
	struct Node *node;		struct Node *node;
Line 282:		Line 282:
	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:		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:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct List *list;		struct List *list;
	struct Node node, next;		struct Node node, next;
Line 299:		Line 299:
	Here is a code fragment that uses functions and a ''for'' loop to print the names of all nodes in a list:		Here is a code fragment that uses functions and a ''for'' loop to print the names of all nodes in a list:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct List *list;		struct List *list;
	struct Node *node;		struct Node *node;
Line 309:		Line 309:
	Here is an example showing how to properly remove a node from a list while traversing:		Here is an example showing how to properly remove a node from a list while traversing:

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	struct List *list;		struct List *list;
	struct Node node, next;		struct Node node, next;
Line 331:		Line 331:
	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.		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>		<syntaxhighlight lang="C" line>
	struct List findListOfNode(struct Node node)		struct List findListOfNode(struct Node node)
	{		{
Line 354:		Line 354:
	The code below demonstrates the concepts and functions discussed in this section by building an application-defined Exec List.		The code below demonstrates the concepts and functions discussed in this section by building an application-defined Exec List.

	<syntaxhighlight>		<syntaxhighlight lang="C" line>
	// buildlist.c - example which uses an application-specific Exec list		// buildlist.c - example which uses an application-specific Exec list

Fredrik Wikstrom: /* Scanning a List */

2017-09-21T17:29:55Z

Scanning a List

← Older revision		Revision as of 17:29, 21 September 2017
Line 274:		Line 274:
	struct Node *node;		struct Node *node;

	for ( node = list->lh_Head ; node->ln_Succ ; node = node->ln_Succ )		for ( node = list->lh_Head ; node->ln_Succ != NULL ; node = node->ln_Succ )
	IDOS->Printf("%p -> %s\n", node, node->ln_Name);		IDOS->Printf("%p -> %s\n", node, node->ln_Name);
	</syntaxhighlight>		</syntaxhighlight>
Line 286:		Line 286:
	struct Node node, next;		struct Node node, next;

	for ( node = list->lh_Head; node->ln_Succ; node = next )		for ( node = list->lh_Head; (next = node->ln_Succ) != NULL ; node = next )
	{		{
	next = node->ln_Succ;
	/* Do something with the node. */		/* Do something with the node. */
	/* This may include node removal from the list. */		/* This may include node removal from the list. */

Steven Solie: /* Scanning a List */

2017-06-13T21:06:42Z

Scanning a List

← Older revision		Revision as of 21:06, 13 June 2017
Line 327:		Line 327:

	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.		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 ====		==== Exec List Example ====

Steven Solie: /* Scanning a List */

2015-09-02T15:46:58Z

Scanning a List

← Older revision		Revision as of 15:46, 2 September 2015
Line 304:		Line 304:
	struct Node *node;		struct Node *node;

	for ( node = IExec->GetHead() ; node != NULL ; node = IExec->GetSucc(node) )		for ( node = IExec->GetHead(list) ; node != NULL ; node = IExec->GetSucc(node) )
	IDOS->Printf("%p -> %s\n", node, node->ln_Name);		IDOS->Printf("%p -> %s\n", node, node->ln_Name);
	</syntaxhighlight>		</syntaxhighlight>

Daniel Jedlicka: Node Initialization: added info on custom (user-defined) node types. More on the Use of Named Lists: renamed this section to "More on the Use of Named Nodes" because there's in fact nothing like "named lists" - only nodes can have names.

2015-08-22T19:38:38Z

Node Initialization: added info on custom (user-defined) node types. More on the Use of Named Lists: renamed this section to "More on the Use of Named Nodes" because there's in fact nothing like "named lists" - only nodes can have names.

← Older revision		Revision as of 19:38, 22 August 2015
Line 45:		Line 45:

	; ln_Type		; ln_Type
	: defines the type of the node (see <exec/nodes.h> for a list).		: defines the type of the node (see <exec/nodes.h> for a complete list of types).

	; ln_Pri		; ln_Pri
	: specifies the priority of the node (+127 (highest) to -128 (lowest)).		: specifies the priority of the node, ranging from +127 (highest) to -128 (lowest).

	; ln_Name		; ln_Name
Line 68:		Line 68:
	=== 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 (A MinNode structure does not have these fields). The successor and predecessor fields do not require 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.		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 205:		Line 212:
	[[File:LibFig23-4.png\|frame\|center\|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() or FindIName() 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:
Line 259:		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. ~~One way is~~ via direct manipulation of the pointers. ~~The~~ ~~other~~ ~~way~~ ~~uses~~ functions from Exec.		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:		Here is a code fragment that uses pointers and a ''for'' loop to print the names of all nodes in a list:

Daniel Jedlicka: Updated code fragments and the Function Reference. Removed duplicate function reference from the List Functions section.

2015-04-03T10:07:50Z

Updated code fragments and the Function Reference. Removed duplicate function reference from the List Functions section.

Show changes

Steven Solie: /* Searching by Name */

2013-05-08T19:22:43Z

Searching by Name

← Older revision		Revision as of 19:22, 8 May 2013
Line 222:		Line 222:
	The case of the name characters is significant; "foo" is different from "Foo." If the case of a name should not be significant then use the FindIName() function.		The case of the name characters is significant; "foo" is different from "Foo." If the case of a name should not be significant then use the FindIName() function.

	[[File:LibFig23-4.png\|center]]		[[File:LibFig23-4.png\|frame\|center\|Complete Sample List Showing all Interconnections]]

	<center>'''Figure 23-4: Complete Sample List Showing all Interconnections'''</center>

	=== More on the Use of Named Lists ===		=== More on the Use of Named Lists ===

Steven Solie: /* List Structure */

2013-05-08T19:21:50Z

List Structure

← Older revision		Revision as of 19:21, 8 May 2013
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\|center]]		[[File:LibFig23-1.png\|frame\|center\|Simplified Overview of an Exec List]]

	<center>'''Figure 23-1: Simplified Overview of an Exec List'''</center>

	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 133:		Line 131:
	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\|center]]		[[File:LibFig23-2.png\|frame\|center\|List Header Overlap]]

	<center>'''Figure 23-2: List Header Overlap'''</center>

	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.		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.
Line 150:		Line 146:
	# 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\|center]]		[[File:LibFig23-3.png\|frame\|center\|Initializing a List Header Structure]]

	<center>'''Figure 23-3: Initializing a List Header Structure'''</center>

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

Bill Borsari: /* Exec List Example */

2013-03-10T21:10:56Z

Exec List Example

← Older revision		Revision as of 21:10, 10 March 2013
Line 399:		Line 399:
	IExec->FreeSysObject(ASOT_LIST, NameList); /* Free list header */		IExec->FreeSysObject(ASOT_LIST, NameList); /* Free list header */
	}		}

			return 0;
	}		}

Line 417:		Line 419:
	IUtility->Strlcpy(namenode->nn_Data, name, sizeof(namenode->nn_Data));		IUtility->Strlcpy(namenode->nn_Data, name, sizeof(namenode->nn_Data));
	namenode->nn_Node.ln_Name = namenode->nn_Data;		namenode->nn_Node.ln_Name = namenode->nn_Data;
	AddHead((struct List )list, (struct Node )namenode);		IExec->AddHead((struct List )list, (struct Node )namenode);
	}		}
	}		}
Line 432:		Line 434:

	worknode = (struct NameNode )(IExec->GetHead(list)); / First node */		worknode = (struct NameNode )(IExec->GetHead(list)); / First node */
	while (nextnode = (struct NameNode *)(IExec->GetSucc(worknode))) {		while ((nextnode = (struct NameNode )(IExec->GetSucc((struct Node)worknode)))) {
	IExec->FreeSysObject(ASOT_NODE, worknode);		IExec->FreeSysObject(ASOT_NODE, worknode);
	worknode = nextnode;		worknode = nextnode;
Line 460:		Line 462:
	struct Node *node;		struct Node *node;

	if (node = IExec->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);		IDOS->Printf("Found a %s at location %lx\n", node->ln_Name, node);
	node = IExec->FindName((struct List *)node,name);		node = IExec->FindName((struct List *)node,name);
	}		}
	} else ~~IExec~~->Printf("No node with name %s found.\n", name);		} else IDOS->Printf("No node with name %s found.\n", name);
	}		}
	</syntaxhighlight>		</syntaxhighlight>

Steven Solie: /* Prioritized Insertion */

2012-07-12T20:00:26Z

Prioritized Insertion

← Older revision		Revision as of 20:00, 12 July 2012
Line 218:		Line 218:
	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.		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.}}
	{\| class="wikitable"
⚫	\| ''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 ===		=== Searching by Name ===