Dorper Website of Paul Carver Harrison

Amiga Exec Doubly Linked Priority Queue Explained

The Amiga Executive and Net/Exec frequently use a doubly linked priority queue structure for storing collections of objects. Objects that can be put into one of these lists have their first member be something along the lines of struct Node node. This gives the object a header that can be used by the list manipulation functions. The struct could occur anywhere in the object but it's usually kept at the top because it makes accessing the rest of the structure a simple cast rather than requiring subtraction.

List Structure

struct List {
  struct Node *lh_Head;
  struct Node *lh_Tail;
  struct Node *lh_TailPred;
  UBYTE        lh_Type;
  UBYTE        lh_Pad;
};

Node Structure

struct Node {
  struct Node *ln_Succ;
  struct Node *ln_Pred;
  UBYTE        ln_Type;
  BYTE         ln_Pri;
  char        *ln_Name;
};
Successor (*ln_Succ) and Predecessor (*ln_Pred)
If the node is the head of the list, its predecessor is NULL. If it's the tail of the list, its successor is NULL.
Type (ln_Type)
Used to determine the type of an object in many different functions. The OS and user software use this field for different purposes. For example, ReplyMsg will set a Message's type to NT_REPLYMSG. The list functions don't care about its value.
Priority (ln_Pri)
Priority is between -128 (lowest) and +127 (highest). When Enqueue is used, the node will be inserted before the first node of lower priority. Tasks use this field to determine their preemption priority.
Name (*ln_Name)
Pointer to null-terminated string. FindName can be used to perform an O(n) search to find a node with a matching name. Set to NULL if not used.

Further Reading