Exec Lists - Revision history

Krashan: /* List Iterator */ Fixed bugs in ForEachNode() macro iterator.

2013-01-12T20:26:40Z

‎List Iterator: Fixed bugs in ForEachNode() macro iterator.

Krashan: /* From a Plain List to Exec List */

2011-11-17T10:58:20Z

‎From a Plain List to Exec List

Krashan: /* List Iterator */ Fixed ForEachNode() marco

2011-11-13T17:51:11Z

‎List Iterator: Fixed ForEachNode() marco

Krashan: /* Head and Tail */ style

2011-11-11T15:42:06Z

‎Head and Tail: style

Krashan: Contents.

2011-11-11T15:34:22Z

Contents.

Krashan: /* Functions or Macros? */ Contents

2011-11-11T15:21:16Z

‎Functions or Macros?: Contents

Krashan: /* Adding and Removing Items */ removed non-paired parenthesis

2011-11-11T15:11:02Z

‎Adding and Removing Items: removed non-paired parenthesis

Krashan: /* Adding and Removing Items */ More contents.

2011-11-11T15:09:07Z

‎Adding and Removing Items: More contents.

Krashan: /* Head and Tail */ Contents.

2011-11-11T15:07:11Z

‎Head and Tail: Contents.

Krashan: /* Adding and Removing Items */ Some restructuring, contents.

2011-11-11T14:42:06Z

‎Adding and Removing Items: Some restructuring, contents.

@@ Line 149: / Line 149: @@
 This time the pointer ''n'' is initialized to the last real item (predecessor of the list tail), pointer is moved to the previous item in each loop turn. The loop finishes, when the predecessor of the current item is ''NULL'', which is the case for the list head. Again, the loop is not executed for the list head itself.
-The ''&lt;exec/lists.h&gt;'' header file provides ''ForEachNode()'' macro for building a ''for'' based iterator. The macro is a bit dangerous however, because it blindly typecasts the node pointer to ''struct Node*'' and the list pointer to ''struct List*''. It effectively bypasses the static C language type control and can lead to bugs in code. It is much safer to cast the node pointer to the real type of the list item, as shown in the above example iterators. Then a safer iterator macro should take the type name as one of arguments:
+The ''&lt;exec/lists.h&gt;'' header file provides ''ForeachNode()'' macro for building a ''for'' based iterator. The macro is a bit dangerous however, because it blindly typecasts the node pointer to ''struct Node*'' and the list pointer to ''struct List*''. It effectively bypasses the static C language type control and can lead to bugs in code. It is much safer to cast the node pointer to the real type of the list item, as shown in the above example iterators. Then a safer iterator macro should take the type name as one of arguments:
-  #define ForEachNode(n, T, list) for (n = (T)(list)->mlh_TailPred; n->Node.mln_Succ; \
+  #define ForEachNode(n, T, list) for (n = (T)(list)->mlh_Head; n->Node.mln_Succ; \
-   n = (T)n->Node.mln_Pred)
+   n = (T)n->Node.mln_Succ)
 The macro may be used as follows:

← Older revision		Revision as of 10:58, 17 November 2011
Line 15:		Line 15:


−	While the idea is still simple, we have to complicate it a bit. As mentioned before, the list user keeps track of it by maintaining two pointers: to the first and the last item. These pointers will be modified every time an item is added at the start or end of the list respectively. But what if a list has multiple users not knowing about each other? Adding an item at the start or at the end would require pointer update for '''all''' the users. To solve the problem, two artificial items are introduced: a '''list head''' and a '''list tail'''. Those two elements do not carry payload, only consist of a node. Their location does not change during the list lifetime so they work as anchors. Inserting an element at list start is in fact inserting it between the list head and the former first element. Similarly element inserted at end is in fact inserted between the former last element and the list tail. As pointers to the head and the tail are constant, they may be shared between multiple users.	+	While the idea is still simple, we have to complicate it a bit. As mentioned before, the list user keeps track of it by maintaining two pointers: to the first and the last item. These pointers will be modified every time an item is added or removed at the start or end of the list respectively. But what if a list has multiple users not knowing about each other? Adding an item at the start or at the end would require pointer update for '''all''' the users. To solve the problem, two artificial items are introduced: a '''list head''' and a '''list tail'''. Those two elements do not carry payload, only consist of a node. Their location does not change during the list lifetime so they work as anchors. Inserting an element at list start is in fact inserting it between the list head and the former first element. Similarly element inserted at end is in fact inserted between the former last element and the list tail. As pointers to the head and the tail are constant, they may be shared between multiple users.

@@ Line 151: / Line 151: @@
 The ''&lt;exec/lists.h&gt;'' header file provides ''ForEachNode()'' macro for building a ''for'' based iterator. The macro is a bit dangerous however, because it blindly typecasts the node pointer to ''struct Node*'' and the list pointer to ''struct List*''. It effectively bypasses the static C language type control and can lead to bugs in code. It is much safer to cast the node pointer to the real type of the list item, as shown in the above example iterators. Then a safer iterator macro should take the type name as one of arguments:
-  #define ForEachNode(n, T, list) for (n = (T*)(list)->mlh_TailPred; n->Node.mln_Succ; \
+  #define ForEachNode(n, T, list) for (n = (T)(list)->mlh_TailPred; n->Node.mln_Succ; \
-   n = (T*)n->Node.mln_Pred)
+   n = (T)n->Node.mln_Pred)
 The macro may be used as follows:
-  ForEachNode(n, MyNode, list)
+  ForEachNode(n, struct MyNode*, list)
+  {
     /* do something with node 'n' */

@@ Line 231: / Line 231: @@
 The most common operations of inserting and removing elements are performed on both the ends of a list. For example common data structures like stack or queue may be implemented using list. For stack, items are added at the list head and also removed from the head. For queue items are added at the tail and removed at the head.
-Having a list head and tail pseudoitems gives an advantage, that operations at both list ends are not different than the general case. One just replaces &ndash; on the diagram in the previous subchapter &ndash; either the element before the insert position with the list head, or the element after the insert position with the list tail. The only difference comes from the fact as head and tail operations usually take just the address of the list header as their argument. The complete set of four operations is provided:
+Having a list head and tail pseudoitems gives an advantage, that operations at both list ends are not different than the general case. One just replaces &ndash; on the diagram in the previous subchapter &ndash; either the element before the insert position with the list head, or the element after the insert position with the list tail. The only difference comes from the fact that head and tail operations usually take just the address of the list header as their argument. The complete set of four operations is provided:
 * ''AddHead()'' function and ''ADDHEAD()'' macro add a node as the first one.
 * ''RemHead()'' function and ''REMHEAD()'' macro remove the first node and return its address.

@@ Line 239: / Line 239: @@
 ==Functions or Macros?==
 After reading all the sections above it is clear, that most of the list operations is very simple and compiles to a few processor instructions. That is why they are also defined as macros. What to to use then? In general macros are faster, but some of them may be a few bytes longer than calls to library functions (especially ''INSERT()''). On the other hand even a few kilobytes of additional code is usually not a problem nowadays, while gain in speed is often valuable. Then in places where speed is critical, macros are a better choice.
 ==Enqueueing==
-=Access Arbitration=
+Full list nodes have a '''priority''' field, named ''ln_Pri''. The field is often used by the system to maintain prioritized lists or queues. To keep the list ordered by priority, a special insert operation is required. It is provided as an ''exec.library'' call named ''Enqueue()''. The function takes a node (it must be full ''Node'', not ''MinNode''), reads its priority and finds a place for insert comparing priorities of nodes. If there are any nodes in the list with the same priority as the inserted one, it is inserted '''before''' already existing ones. Of course ''Enqueue()'' may be used also for implementing custom queues. One has to take into account however that the priority field is limited to signed 8-bit number and the function does not scale well for very long lists, as the insert position search is linear.

@@ Line 218: / Line 218: @@
 Observe the order of operations. It is important. If one starts from operation 4 for example,  he would loose the only link to the rest of the list after the insert position.
-Removing link is even faster, as it only requires modifying two pointers (one in the predecessor of removed item and one in its successor. Let's assume element ''n'' is to be removed:
+Removing link is even faster, as it only requires modifying two pointers: one in the predecessor of removed item and one in its successor. Let's assume element ''n'' is to be removed:
   n->Node.mln_Pred->mln_Succ = n->Node.mln_Succ;

← Older revision		Revision as of 15:07, 11 November 2011
Line 229:		Line 229:
	The most common operations of inserting and removing elements are performed on both the ends of a list. For example common data structures like stack or queue may be implemented using list. For stack, items are added at the list head and also removed from the head. For queue items are added at the tail and removed at the head.		The most common operations of inserting and removing elements are performed on both the ends of a list. For example common data structures like stack or queue may be implemented using list. For stack, items are added at the list head and also removed from the head. For queue items are added at the tail and removed at the head.

		+	Having a list head and tail pseudoitems gives an advantage, that operations at both list ends are not different than the general case. One just replaces – on the diagram in the previous subchapter – either the element before the insert position with the list head, or the element after the insert position with the list tail. The only difference comes from the fact as head and tail operations usually take just the address of the list header as their argument. The complete set of four operations is provided:
		+	* ''AddHead()'' function and ''ADDHEAD()'' macro add a node as the first one.
		+	* ''RemHead()'' function and ''REMHEAD()'' macro remove the first node and return its address.
		+	* ''AddTail()'' function and ''ADDTAIL()'' macro add a node as the last one.
		+	* ''RemTail()'' function and ''REMTAIL()'' macro remove the last node and return its address.
		+	All these operations require only an address of the list header. Remove operations return the address of removed node, or ''NULL'' if the list is empty.

	==Functions or Macros?==		==Functions or Macros?==

@@ Line 218: / Line 218: @@
 Observe the order of operations. It is important. If one starts from operation 4 for example,  he would loose the only link to the rest of the list after the insert position.
-Removing link is even faster, as it only requires modifying two pointers (one in the predecessor of removed item and one in its successor. Let's assume element ''n'' is to be removed:
+Removing link is even faster, as it only requires modifying two pointers (one in the predecessor of removed item and one i                                                            sfgh                                                                                       n its successor. Let's assume element ''n'' is to be removed:
   n->Node.mln_Pred->mln_Succ = n->Node.mln_Succ;
   n->Node.mln_Succ->mln_Pred = n->Node.mln_Pred;
-Insert and remove operations have been standarizded in MorphOS in two ways: as ''exec.library'' API calls and as macros. The library functions are ''Insert()'' and ''Remove()'', their macro counterparts are named ''INSERT()'' and ''REMOVE()''.
+Insert and remove operations have been standarizded in MorphOS in two ways: as ''exec.library'' API calls and as macros. The library functions are ''Insert()'' and ''Remove()'', their macro counterparts are named ''INSERT()'' and ''REMOVE()''. Both ''Insert()'' function and ''INSERT()'' macro take also a pointer to list header. While it is not neccesary in general case, it allows to handle the case when an item is inserted as the first one by passing ''NULL'' as the insert position. Inserting as the first element can be also done by passing the list header address as the insert position.
+==Head and Tail==
-==Head==
+The most common operations of inserting and removing elements are performed on both the ends of a list. For example common data structures like stack or queue may be implemented using list. For stack, items are added at the list head and also removed from the head. For queue items are added at the tail and removed at the head.
-==Tail==
-==Any Position==
 ==Enqueueing==
 =Access Arbitration=
 =System Lists=