Fresh Fish 5/FreshFish_July-August1994.bin/bbs/dev/cmanual-3.0.lha/CManual-3.0/System/Lists/Lists.doc

Text File | 1993-10-12 | 20.5 KB | 780 lines

3    LISTS

3.1  INTRODUCTION

Amiga has a multi tasking operating system which means that
several tasks (programs) can be running simultaneously. This
unique feature is controlled by "Exec" - "the multi tasking
executive". To make it possible for Exec to control several
tasks it uses a complex system of "lists" and "messages".



3.2  THE LIST

A list consists of a "header" and a linked list of "nodes".
The header consists of two pointers to the first and last nodes
in the linked list as well as a field that tells Exec what
type of nodes the list will contain.



3.2.1  THE LIST STRUCTURE

The List structure look like this: (Defined in the header
file "exec/lists.h")

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

lh_Head:     Pointer to the first node in the linked list.

lh_Tail:     Is always zero.

lh_TailPred: Pointer to the last node in the linked list.

lh_Type:     Tells Exec what types of nodes there are in the
             list. See header file "exec/nodes.h" for a complete
             list of the node types. Here are some commonly used
             types:

             NT_UNKNOWN   Type unknown (How could you guess that?)
             NT_TASK      A task node.
             NT_INTERRUPT An interrupt (also software interrupt)
             NT_SOFTINT   Only used by Exec itself.
             etc...

lh_pad:      Not used. (Aligns the structure to the infamous even
             bytes boundary.)



3.2.2  INITIALIZE THE LIST STRUCTURE

Before you may use the list structure you have to initialize it.
Simply follow these steps:

1. Set the lh_Head pointer to the address of lh_Tail.

2. Set the lh_Tail pointer to NULL. (Should always be NULL.)

3. Set the lh_TailPred pointer to the address of lh_Head.

4. Set the lh_Type field to the desired node type. (Note, all
   nodes in the list should be of the same type as the lh_Type.)


Here is an example:

struct List plans;
plans.lh_Head = &plans.lh_Tail;
plans.lh_Tail = NULL;
plans.lh_TailPred = &plans.lh_Head;
plans.lh_Type = NT_UNKNOWN;


This can be replaced by calling the NewList() function, with a
pointer to the list structure as the only argument.

Synopsis: NewList( list );

list:     (struct List *) Pointer to the list that should be
          initialized.


Example: NewList( &plans );



3.2.3  MINI LISTS

There exist a special type of mini lists that are exactly the
same as the normal lists except that no type checking is used
and it only contains mini nodes. (Mini nodes are discussed
further down. They are like normal nodes but without any
priority nor type definitions.) The MinList structure look
like this: (Also defined in the header file "exec/lists.h")

struct MinList
{
  struct MinNode *mlh_Head;
  struct MinNode *mlh_Tail;
  struct MinNode *mlh_TailPred;
};

mlh_Head:     Pointer to the first mini node in the linked list.

mlh_Tail:     Is always zero.

mlh_TailPred: Pointer to the last mini node in the linked list.


These mini lists are used when you only want to use double
linked lists but do not bother about types, priority or names.
Note that these lists can NOT be used by some of the lists
function described further down! (It would be ridiculous, and
very dangerous, to search a mini list for nodes with special
names, for example.)



3.3  NODES

A list is a double linked lists of nodes. (A double linked lists
means that you can both go forward as well as backwards in the
list.) The node consists of two parts:

  1. A node structure with which the nodes are linked together
     with. It also contains information such as node type and
     priority (more about this later). Each node structure has
     also a name which is used to identify the nodes. (Very
     useful during debugging.)

  2. The data itself. This can be anything you like.



3.3.1  THE NODE STRUCTURE

The node structure look like this: (Defined in the header file
"exec/nodes.h")

struct Node
{
  struct Node *ln_Succ;
  struct Node *ln_Pred;
  UBYTE ln_Type;
  BYTE ln_Pri;
  char *ln_Name;
};

ln_Succ: Pointer to the next node. (Successor)

ln_Pred: Pointer to the previous node in the list. (Predecessor)

ln_Type: Type of node. See header file "exec/nodes.h" for a
         complete list of the node types. (See above for some
         examples.)

ln_Pri:  This node's "priority" - a value between -128 and +127.
         The higher value the higher priority. The priority can
         for example be used when the list is sorted. If you
         do not use the priority field, set it to 0.

ln_Name: Pointer to a NULL terminating string which contains
         the name of this node. (Useful for debugging.)



3.3.2  INITIALIZE THE NODE STRUCTURE

Before you may put the node into the list you have to initialize
it. You do it by setting the ln_Type, ln_Pri and ln_Name field
as desired. The ln_Succ and ln_Pred pointers will automatically
be initialized when the node is placed into the list.

Here is an example:

struct Node my_first_node;
my_first_node.ln_Type = NT_UNKNOWN; /* A strange node. */
my_first_node.ln_Pri = 25;          /* A rather important node. */
my_first_node.ln_Name = "Napoleon"  /* This node's name. */



3.3.3  CREATE A COMPLETE NODE

A complete node consists, as said above, of two parts. First we
have the node structure itself, then we have the data. Here is
an example how to create your own complete node:


/* Declare the COMPLETE node structure: */
struct Person author=
{
  /* Succ  Pred    Type     Pri    Name                */
  { NULL, NULL, NT_UNKNOWN, 127, "Anders" }, /* Part 1 */
  CPTR data1;                                /* Part 2 */
  CPTR data2;
  CPTR data3;
};



3.3.4  MINI NODES

As there exist mini lists there also exist mini nodes. They
are like normal nodes, but without type definition, priority
and name.  The MinNode structure look like this: (Also defined
in the header file "exec/nodes.h")

struct MinNode
{
  struct MinNode *mln_Succ;
  struct MinNode *mln_Pred;
};

mln_Succ: Pointer to the next mini node. (Successor)

mln_Pred: Pointer to the previous mini node in the list.
          (Predecessor)



3.4  INSERT AND REMOVE LISTS

Once you have initialized a complete node you can insert it into
a linked list. You would then probably use the Insert() function,
but if you want to insert it first or last into a list you should
rather use the functions AddHead() or AddTail() function. To
remove a node use the function Remove(). To remove the first or
last node in the list you should use the RemHead() or RemTail()
functions since they are much faster. There exist even a
function to insert nodes and positions them corresponding to
their priorities.



3.4.1  INSERT NODES INTO A LIST

To insert a node into a list use the Insert() function:

Synopsis: Insert( list, node, pred );

list:     (struct List *) Pointer to the list you wish to
          insert the node in.

node:     (struct Node *) Pointer to the node you want to insert.

pred:     (struct Node *) Pointer to a node which the new node
          should be placed after. (If this field is NULL or
          points to the list header the node will be inserted
          first in the list. If this field points to the list's
          lh_Tail field the node will be inserted last in the
          list. However, if you which to insert a node first or
          last in a list you should use the faster functions
          AddHead() or AddTail().)

Here is an example how to insert the node "author" just after
the node "housekeeper" in the "plans" list:

Insert( &plans, &author, &housekeeper );



3.4.1.1  INSERT NODES AT THE HEAD OF A LIST

If you want to insert a node a the head of a list you are
recommended to use the fast AddHead() function.

Synopsis: AddHead( list, node )

list:     (struct List *) Pointer to the list you wish to
          insert the node in.

node:     (struct Node *) Pointer to the node you want to insert.


Here is an example how to insert the node "author" at the head
of the list "plans":

AddHead( &plans, &author );



3.4.1.2  INSERT NODES AT THE TAIL OF A LIST

If you want to insert a node a the tail of a list you are
recommended to use the fast AddTail() function.

Synopsis: AddTail( list, node )

list:     (struct List *) Pointer to the list you wish to
          insert the node in.

node:     (struct Node *) Pointer to the node you want to insert.


Here is an example how to insert the node "author" at the tail
of the list "plans":

AddTail( &plans, &author );



3.4.2  REMOVE NODES FROM A LIST

To remove a node from a list use the Remove() function:

Synopsis: Remove( node );

node:     (struct Node *) Pointer to the node you want to insert.

Here is an example how to remove the node "author":

Remove( &author );



3.4.2.1  REMOVE NODES AT THE HEAD OF A LIST

If you want to remove a node a the head of a list you are
recommended to use the fast RemHead() function. This function
will also return a pointer to the removed node, or NULL if
there were no more nodes to remove.

Synopsis: node = RemHead( list )

list:     (struct List *) Pointer to the list you wish to
          remove the head node from.

node:     (struct Node *) Pointer to the node you have
          removed.


Here is an example how to remove the node at the head of the
list "plans": (node_ptr is a pointer to node structures.)

node_ptr = RemHead( &plans );



3.4.2.2  REMOVE NODES AT THE TAIL OF A LIST

If you want to remove a node a the tail of a list you are
recommended to use the fast RemTail() function. This function
will also return a pointer to the removed node, or NULL if
there were no more nodes to remove.

Synopsis: node = RemTail( list )

list:     (struct List *) Pointer to the list you wish to
          remove the tail node from.

node:     (struct Node *) Pointer to the node you have
          removed.


Here is an example how to remove the node at the tail of the
list "plans": (node_ptr is a pointer to node structures.)

node_ptr = RemHead( &plans );



3.4.3  FIFO AND LIFO

The functions above can be combined to generate "First In First
Out" (FIFO) or "Last In First Out" (LIFO).

FIFO Use the functions AddTail() and RemHead() to generate a
     first in first out list. The first node you inserted into
     the list will also be the first node to be removed. (This
     is like a normal queue.)

LIFO Use the functions AddHead() and RemHead() to generate a
     last in first out list. The last node you inserted into
     the list will also be the first node to be removed. (This
     is like a putting nodes onto a "stack".)



3.4.4  INSERT NODES CONSIDERING THEIR PRIORITIES

If you want to insert nodes and use the nodes' priorities to
decide where in the list they should be placed you can use
the Enqueue() function. The node with the highest priority will
be placed at the head of the list, and the lower priority the
further back into the list the nodes will be placed. If you
insert a node with the same priority as an already existing
one, your node will be placed after that one. (FIFO)

To pick out the nodes with the highest priorities first you
should then use the RemHead() function. To pick out the nodes
with the lowest priorities first you should use the RemTail()
function.

Synopsis: Enqueue( list, node );

list:     (struct List *) Pointer to the list you wish to
          insert the node in.

node:     (struct Node *) Pointer to the node you want to
          insert.


NOTE! This function can of course not be used to handle mini
lists. (Mini nodes do not have any priority field.)



3.5  WORK WITH THE LISTS

Here are some common ways to work with lists and nodes.



3.5.1  IS THE LIST EMPTY?

If you want to determine if a list is empty you simply check
if the ln_Succ field of the node lh_Head points to is NULL.
(This may seem a bit strange, but remember that when you
initialize the list structure you set the lh_Head field to
the address of lh_Tail.)

  if( my_list.lh_Head->ln_Succ == NULL )
    printf( "This list is empty!\n" );



3.5.2  SCAN THROUGH A LIST

The lists are, as mentioned above, double linked. You can
therefore scan through a list either from the head to the tail
or from the tail to the head.

Example on how to scan through a list from the head to the tail:

  struct Node *ptr;

  /* Set the node pointer so it points to the first node: */
  ptr = (struct Node *) my_list.lh_Head;

  /* Stay in the loop as long as there is a node after this one: */
  while( ptr->ln_Succ )
  {
    printf( "Node %s\n", ptr->ln_Name );
    ptr = ptr->ln_Succ;
  }


Example on how to scan through a list from the tail to the head:

  struct Node *ptr;

  /* Set the node pointer so it points to the last node: */
  ptr = (struct Node *) my_list.lh_TailPred;

  /* Stay in the loop as long as there is a node before this one: */
  while( ptr->ln_Pred )
  {
    printf( "Node %s\n", ptr->ln_Name );
    ptr = ptr->ln_Pred;
  }



3.5.3  SEARCH FOR A NODE WITH A SPECIAL NAME

It is sometimes necessary to find nodes with special names. The
FindName() function is here very useful. You only need to
specify what name you look for and which list should be examined.
The function will either return a pointer to the first node in
the list with that name, or NULL if no node with the specified
name was found. If you find a node you only have to call the
function again (this time with the node pointer instead of the
list pointer) to find the next correct node.

Synopsis: node = FindName( list, name );

node:     (struct Node *) If FindName() finds a node with the
          name "name" it returns a pointer to it. If no node
          was found it returns NULL.

list:     (struct List *) Pointer to the list you want to
          examine. If you have already found a node and want to
          search for the next you should give it a pointer to
          the last node you found.

name:     (char *) Pointer to a NULL terminated string that
          contains the name of the node(s) you look for.


  /* Find the first node with the name "Internal": */
  node_ptr = (struct Node *) FindName( &my_list, "Internal" );

  /* As long as we find nodes with the name "Internal" we */
  /* stay in the loop:                                    */
  while( node_ptr )
  {
    /* Do what ever you want with the node: */
    printf( "Node %lX is internal.\n", node_ptr );

    /* Try to find yet another node: */
    node_ptr = (struct Node *) FindName( node_ptr, "Internal" );
  }


NOTE! This function can of course not be used to handle mini
lists. (Mini nodes do not have any name field.)



3.6  A COMPLETE EXAMPLE

Here is a not very exciting but complete list example:

#include <exec/types.h>
#include <exec/lists.h> /* This file will automatically */
                        /* include the file "nodes.h".  */


/* Declare a complete node structure: */
struct ToDo
{
  struct Node node; /* Every node must have this. */
  STRPTR Wish;      /* Our own data.              */
};


/* Declare a list structure: */
struct List my_list;


/* Node 1: */
struct ToDo eat=
{
  { NULL, NULL, NT_UNKNOWN, 0, "Food" },
  "eat breakfast"
};

/* Node 2: */
struct ToDo sleep=
{
  { NULL, NULL, NT_UNKNOWN, 0, "Sleep" },
  "rest"
};

/* Node 3: */
struct ToDo drink=
{
  { NULL, NULL, NT_UNKNOWN, 0, "Food" },
  "drink some nice wine"
};


main()
{
  /* Declare a node pointer: */
  struct Node *ptr;

  /* Declare a pointer to ToDo structures: */
  struct ToDo *todo_ptr;


  /* Initialize our list structure: */
  NewList( &my_list );


  /* Add three nodes: */
  AddTail( &my_list, &eat );
  AddTail( &my_list, &sleep );
  AddTail( &my_list, &drink );


  /* Check if the list is empty or not: */
  if( my_list.lh_Head->ln_Succ == NULL )
    printf( "This list is empty!\n" );
  else
    printf( "This list is not empty!\n" );


  /* Scan through the list: (Head to Tail) */
  ptr = (struct Node *) my_list.lh_Head;
  while( ptr->ln_Succ )
  {
    printf( "Node %lX\n", ptr, ptr );
    ptr = ptr->ln_Succ;
  }


  /* Find all nodes with the name "Food": */
  ptr = (struct Node *) FindName( &my_list, "Food" );
  while( ptr )
  {
    todo_ptr = (struct ToDo *) ptr;
    printf( "I want to %s.\n", todo_ptr->Wish );
    ptr = (struct Node *) FindName( ptr, "Food" );
  }


  /* Remove all nodes: */
  RemHead( &my_list, &eat );
  RemHead( &my_list, &sleep );
  RemHead( &my_list, &drink );
}



3.7  FUNCTIONS

NewList()

  This function initializes a list structure.

  Synopsis: NewList( list );

  list:     (struct List *) Pointer to the list that should be
            initialized.


Insert()

  This function is used to insert nodes into a list. If the
  node should be placed first or last in the list you should
  use the faster functions AddHead() or AddTail().

  Synopsis: Insert( list, node, pred );

  list:     (struct List *) Pointer to the list you wish to
            insert the node in.

  node:     (struct Node *) Pointer to the node you want to
            insert.

  pred:     (struct Node *) Pointer to a node which the new
            node should be placed after. (If this field is NULL
            or points to the list header the node will be
            inserted first in the list. If this field points to
            the list's lh_Tail field the node will be inserted
            last in the list. However, if you which to insert
            a node first or last in a list you should use the
            faster functions AddHead() or AddTail().)


Remove()

  This function is used to remove nodes from a list. If the
  node should be removed at the tail of the list you should use
  the faster functions RemHead() or RemTail().

  Synopsis: Remove( node );

  node:     (struct Node *) Pointer to the node you want to
            insert.

  Here is an example how to remove the node "author":


AddHead()

  This function will add a note at the head of a list.

  Synopsis: AddHead( list, node )

  list:     (struct List *) Pointer to the list you wish to
            insert the node in.

  node:     (struct Node *) Pointer to the node you want to
            insert.


AddTail()

  This function will add a note at the tail of a list.

  Synopsis: AddTail( list, node )

  list:     (struct List *) Pointer to the list you wish to
            insert the node in.

  node:     (struct Node *) Pointer to the node you want to
            insert.


RemHead()

  This function will remove a note at the head of a list and
  returns a pointer to the removed node.

  Synopsis: node = RemHead( list )

  list:     (struct List *) Pointer to the list you wish to
            remove the head node from.

  node:     (struct Node *) Pointer to the node you have
            removed, or NULL if there were no more nodes to
            remove.


RemTail()

  This function will remove a note at the tail of a list and
  returns a pointer to the removed node.

  Synopsis: node = RemTail( list )

  list:     (struct List *) Pointer to the list you wish to
            remove the tail node from.

  node:     (struct Node *) Pointer to the node you have
            removed, or NULL if there were no more nodes to
            remove.


Enqueue()

  This function will insert nodes into lists considering the
  node's priority. The higher priority the closer to the head
  they are placed and vice versa.

  NOTE! This function can of course not be used to handle mini
  lists. (Mini nodes do not have any priority field.)

  Synopsis: Enqueue( list, node );

  list:     (struct List *) Pointer to the list you wish to
            insert the node in.

  node:     (struct Node *) Pointer to the node you want to
            insert.


FindName()

  This function will scan a list and search for nodes by their
  name. It will return a pointer to the first node with the
  specified name or NULL if no more node could be found. If it
  found a node you simply have to call it again to find the
  next.

  NOTE! This function can of course not be used to handle mini
  lists. (Mini nodes do not have any name field.)

  Synopsis: node = FindName( list, name );

  node:     (struct Node *) If FindName() finds a node with the
            name "name" it returns a pointer to it. If no node
            was found it returns NULL.

  list:     (struct List *) Pointer to the list you want to
            examine. If you have already found a node and want
            to search for the next you should give it a pointer
            to the last node you found.

  name:     (char *) Pointer to a NULL terminated string that
            contains the name of the node(s) you look for.



3.8  EXAMPLES

Example 1
  Demonstrates how to create a list with three nodes. (Not very
  amazing, but useful to know.)

Example 2
  Demonstrates how to scan through a list from the head to the
  tail, and the other way around.

Example 3
  Demonstrates how to scan through a list looking for nodes with
  a special name. Uses the function FindName().