rom/exec/enqueue.c

   1 /*
   2     Copyright © 1995-2010, The AROS Development Team. All rights reserved.
   3     $Id$
   4
   5     Desc: Add a node into a sorted list
   6     Lang: english
   7 */
   8 #include <exec/lists.h>
   9 #include <proto/exec.h>
  10 #include <aros/debug.h>
  11
  12 /*****************************************************************************
  13
  14     NAME */
  15
  16         AROS_LH2I(void, Enqueue,
  17
  18 /*  SYNOPSIS */
  19         AROS_LHA(struct List *, list, A0),
  20         AROS_LHA(struct Node *, node, A1),
  21
  22 /*  LOCATION */
  23         struct ExecBase *, SysBase, 45, Exec)
  24
  25 /*  FUNCTION
  26         Sort a node into a list. The sort-key is the field node->ln_Pri.
  27         The node will be inserted into the list before the first node
  28         with lower priority. This creates a FIFO queue for nodes with
  29         the same priority.
  30
  31     INPUTS
  32         list - Insert into this list. The list has to be in descending
  33                 order in respect to the field ln_Pri of all nodes.
  34         node - This node is to be inserted. Note that this has to
  35                 be a complete node and not a MinNode !
  36
  37     RESULT
  38         The new node will be inserted before nodes with lower
  39         priority.
  40
  41     NOTES
  42         The list has to be in descending order in respect to the field
  43         ln_Pri of all nodes.
  44
  45     EXAMPLE
  46         struct List * list;
  47         struct Node * node;
  48
  49         node->ln_Pri = 5;
  50
  51         // Sort the node at the correct place into the list
  52         Enqueue (list, node);
  53
  54     BUGS
  55
  56     SEE ALSO
  57
  58     INTERNALS
  59
  60 ******************************************************************************/
  61 {
  62     AROS_LIBFUNC_INIT
  63
  64     struct Node * next;
  65
  66     ASSERT(list != NULL);
  67     ASSERT(node != NULL);
  68
  69     /* Look through the list */
  70     ForeachNode (list, next)
  71     {
  72         /*
  73             Look for the first node with a lower pri as the node
  74             we have to insert into the list.
  75         */
  76         if (node->ln_Pri > next->ln_Pri)
  77             break;
  78     }
  79
  80     /* Insert the node before(!) next. The situation looks like this:
  81
  82             A<->next<->B *<-node->*
  83
  84         ie. next->ln_Pred points to A, A->ln_Succ points to next,
  85         next->ln_Succ points to B, B->ln_Pred points to next.
  86         ln_Succ and ln_Pred of node contain illegal pointers.
  87     */
  88
  89     /* Let node point to A: A<-node */
  90     node->ln_Pred          = next->ln_Pred;
  91
  92     /* Make node point to next: A<->node->next<->B */
  93     node->ln_Succ          = next;
  94
  95     /* Let A point to node: A->node */
  96     next->ln_Pred->ln_Succ = node;
  97
  98     /* Make next point to node: A<->node<-next<->B */
  99     next->ln_Pred          = node;
 100
 101     AROS_LIBFUNC_EXIT
 102 } /* Enqueue */