rom/exec/lists.c

   1 /*
   2     Copyright © 1995-2001, The AROS Development Team. All rights reserved.
   3
   4 #Description: @AROS.Exec.LISTS@
   5
   6 <chapter title="Exec Lists">
   7
   8 <p>Exec offers a standard way to create lists of structures. All you
   9 need to do is to put <code>struct Node node;</code>
  10 as the first
  11 field into any structure you want to collect in a list. You can
  12 then use the macro <code>NEWLIST()</code> to initialize a structure
  13 of the type <code>struct List</code> and insert the nodes
  14 with <code>AddHead()</code>, <code>AddTail()</code>,
  15 <code>Enqueue()</code> or <code>Insert()</code>.<p>
  16
  17 <p>FIXME Explain other functions, how to use the macros,
  18 give some example programs and explain how lists work.<p>
  19
  20 </chapter>
  21
  22 */
  23 #include <string.h>
  24 #include <exec/lists.h> /*#ALL*/
  25 #include <proto/exec.h> /*#ALL*/
  26
  27 /*#AROS_LH********************************************************************
  28
  29     NAME */
  30         void AddHead (
  31
  32 /*  SYNOPSIS */
  33         struct List * list, /*#A0
  34             The list to insert the node into */
  35         struct Node * node) /*#A1
  36             This node is to be inserted */
  37
  38 /*  LOCATION
  39         Exec (40), BaseNotNecessary
  40
  41     FUNCTION
  42         Insert Node <code>node</code> as the first node of the list.
  43
  44     RESULT
  45         None.
  46
  47     NOTES
  48
  49     EXAMPLE
  50         struct List * list;
  51         struct Node * pred;
  52
  53         // Insert Node at top
  54         AddHead (list, node);
  55
  56     BUGS
  57
  58     SEE ALSO
  59         @AROS.Exec.LISTS@
  60
  61     INTERNALS
  62
  63 ******************************************************************************/
  64 {
  65     ASSERT_VALID_PTR(node);
  66     ASSERT_VALID_PTR(list);
  67
  68     /*
  69         Make the node point to the old first node in the list and to the
  70         head of the list.
  71     */
  72     node->ln_Succ          = list->lh_Head;
  73     node->ln_Pred          = (struct Node *)&list->lh_Head;
  74
  75     /*
  76         New we come before the old first node which must now point to us
  77         and the same applies to the pointer to-the-first-node in the
  78         head of the list.
  79     */
  80     list->lh_Head->ln_Pred = node;
  81     list->lh_Head          = node;
  82 } /* AddHead */
  83
  84 /*#AROS_LH********************************************************************
  85
  86     NAME */
  87         void AddTail (
  88
  89 /*  SYNOPSIS */
  90         struct List * list, /*#A0
  91             The list to insert the node into */
  92         struct Node * node) /*#A1
  93             This node is to be inserted */
  94
  95 /*  LOCATION
  96         Exec (41), BaseNotNecessary
  97
  98     FUNCTION
  99         Insert Node node at the end of a list.
 100
 101     RESULT
 102
 103     NOTES
 104
 105     EXAMPLE
 106         struct List * list;
 107         struct Node * pred;
 108
 109         // Insert Node at end of the list
 110         AddTail (list, node);
 111
 112     BUGS
 113
 114     SEE ALSO
 115         @AROS.Exec.LISTS@
 116
 117     INTERNALS
 118
 119 ******************************************************************************/
 120 {
 121 //  ASSERT_VALID_PTR(node); argh! TypeOfMem() doesn't know about the data segment!
 122     ASSERT_VALID_PTR(list);
 123
 124     /*
 125         Make the node point to the head of the list. Our predecessor is the
 126         previous last node of the list.
 127     */
 128     node->ln_Succ              = (struct Node *)&list->lh_Tail;
 129     node->ln_Pred              = list->lh_TailPred;
 130
 131     /*
 132         Now we are the last now. Make the old last node point to us
 133         and the pointer to the last node, too.
 134     */
 135     list->lh_TailPred->ln_Succ = node;
 136     list->lh_TailPred          = node;
 137 } /* AddTail */
 138
 139 /*#AROS_LH********************************************************************
 140
 141     NAME */
 142         void Enqueue (
 143
 144 /*  SYNOPSIS */
 145         struct List * list, /*#A0
 146             Insert into this list. The list has to be in descending
 147             order in respect to the field ln_Pri of all nodes. */
 148         struct Node * node) /*#A1
 149             This node is to be inserted. Note that this has to
 150             be a complete node and not a MinNode ! */
 151
 152 /*  LOCATION
 153         Exec (45), BaseNotNecessary
 154
 155     FUNCTION
 156         Sort a node into a list. The sort-key is the field
 157         <code>node->ln_Pri</code>.
 158         The node will be inserted into the list before the first node
 159         with lower priority. This creates a FIFO queue for nodes with
 160         the same priority.
 161
 162     RESULT
 163         The new node will be inserted before nodes with lower
 164         priority.
 165
 166     NOTES
 167         The list has to be in descending order in respect to the field
 168         <code>ln_Pri</code> of all nodes.
 169
 170     EXAMPLE
 171         struct List * list;
 172         struct Node * node;
 173
 174         node->ln_Pri = 5;
 175
 176         // Sort the node at the correct place into the list
 177         Enqueue (list, node);
 178
 179     BUGS
 180
 181     SEE ALSO
 182         @AROS.Exec.LISTS@
 183
 184     INTERNALS
 185
 186 ******************************************************************************/
 187 {
 188     struct Node * next;
 189
 190     assert (list);
 191     assert (node);
 192
 193     /* Look through the list */
 194     ForeachNode (list, next)
 195     {
 196         /*
 197             Look for the first node with a lower pri as the node
 198             we have to insert into the list.
 199         */
 200         if (node->ln_Pri > next->ln_Pri)
 201             break;
 202     }
 203
 204     /* Insert the node before(!) next. The situation looks like this:
 205
 206             A<->next<->B *<-node->*
 207
 208         ie. next->ln_Pred points to A, A->ln_Succ points to next,
 209         next->ln_Succ points to B, B->ln_Pred points to next.
 210         ln_Succ and ln_Pred of node contain illegal pointers.
 211     */
 212
 213     /* Let node point to A: A<-node */
 214     node->ln_Pred          = next->ln_Pred;
 215
 216     /* Let A point to node: A->node */
 217     next->ln_Pred->ln_Succ = node;
 218
 219     /* Make next point to node: A<->node<-next<->B */
 220     next->ln_Pred          = node;
 221
 222     /* Make node point to next: A<->node->next<->B */
 223     node->ln_Succ          = next;
 224
 225 } /* Enqueue */
 226
 227 /*#AROS_LH********************************************************************
 228
 229     NAME */
 230         struct Node * FindName (
 231
 232 /*  SYNOPSIS */
 233         struct List * list, /*#A0
 234             Search this list. */
 235         UBYTE       * name) /*#A1
 236             This is the name to look for. */
 237
 238 /*  LOCATION
 239         Exec (46), BaseNotNecessary
 240
 241     FUNCTION
 242         Look for a node with a certain name in a list.
 243
 244     RESULT
 245
 246     NOTES
 247         The search is case-sensitive, so "Hello" will not find a node
 248         named "hello".
 249
 250         The list must contain complete Nodes and no MinNodes.
 251
 252     EXAMPLE
 253         struct List * list;
 254         struct Node * node;
 255
 256         // Look for a node with the name "Hello"
 257         node = FindName (list, "Hello");
 258
 259     BUGS
 260
 261     SEE ALSO
 262         @AROS.Exec.LISTS@
 263
 264     INTERNALS
 265
 266 ******************************************************************************/
 267 {
 268     struct Node * node;
 269
 270     assert (list);
 271     assert (name);
 272
 273     /* Look through the list */
 274     for (node=GetHead(list); node; node=GetSucc(node))
 275     {
 276         /* Only compare the names if this node has one. */
 277         if(node->ln_Name)
 278         {
 279             /* Check the node. If we found it, stop. */
 280             if (!strcmp (node->ln_Name, name))
 281                 break;
 282         }
 283     }
 284
 285     /*
 286         If we found a node, this will contain the pointer to it. If we
 287         didn't, this will be <code>NULL</code> (either because the list was
 288         empty or because we tried all nodes in the list)
 289     */
 290     return node;
 291 } /* FindName */
 292
 293 /*#AROS_LH********************************************************************
 294
 295     NAME */
 296         void Insert (
 297
 298 /*  SYNOPSIS */
 299         struct List * list, /*#A0
 300             The list to insert the node into */
 301         struct Node * node, /*#A1
 302             This node is to be inserted */
 303         struct Node * pred) /*#A2
 304             Insert after this node. If this is NULL, node is inserted
 305             as the first node (same as AddHead()) */
 306
 307 /*  LOCATION
 308         Exec (39), BaseNotNecessary
 309
 310     FUNCTION
 311         Insert Node <code>node</code> after <code>pred</code> in list.
 312
 313     RESULT
 314
 315     NOTES
 316
 317     EXAMPLE
 318         struct List * list;
 319         struct Node * pred, * node;
 320
 321         // Insert Node node as second node in list
 322         pred = GetHead (list);
 323         Insert (list, node, pred);
 324
 325     BUGS
 326
 327     SEE ALSO
 328         @AROS.Exec.LISTS@
 329
 330     INTERNALS
 331
 332 ******************************************************************************/
 333 {
 334     assert (node);
 335     assert (list);
 336
 337     /* If we have a node to insert behind... */
 338     if (pred)
 339     {
 340         /* Is this the last node in the list ? */
 341         if (pred->ln_Succ) /* Normal node ? */
 342         {
 343             /*
 344                 Our successor is the successor of the node we add ourselves
 345                 behind and our predecessor is just the node itself.
 346             */
 347             node->ln_Succ = pred->ln_Succ;
 348             node->ln_Pred = pred;
 349
 350             /*
 351                 We are the predecessor of the successor of our predecessor
 352                 (What ? blblblb... ;) and of our predecessor itself.
 353                 Note that here the sequence is quite important since
 354                 we need ln_Succ in the first expression and change it in
 355                 the second.
 356             */
 357             pred->ln_Succ->ln_Pred = node;
 358             pred->ln_Succ = node;
 359         }
 360         else /* last node */
 361         {
 362             /*
 363                 Add the node at the end of the list.
 364                 Make the node point to the head of the list. Our
 365                 predecessor is the previous last node of the list.
 366             */
 367             node->ln_Succ              = (struct Node *)&list->lh_Tail;
 368             node->ln_Pred              = list->lh_TailPred;
 369
 370             /*
 371                 Now we are the last now. Make the old last node point to us
 372                 and the pointer to the last node, too.
 373             */
 374             list->lh_TailPred->ln_Succ = node;
 375             list->lh_TailPred          = node;
 376         }
 377     }
 378     else
 379     {
 380         /*
 381             add at the top of the list. I do not use <code>AddHead()</code>
 382             here but write the code twice for two reasons: 1. The code is small
 383             and therefore errors are unlikely and 2. If I would call
 384             <code>AddHead()</code>, it would take almost as long to call the
 385             function as the execution would take yielding 100% overhead.
 386         */
 387         node->ln_Succ          = list->lh_Head;
 388         node->ln_Pred          = (struct Node *)&list->lh_Head;
 389         list->lh_Head->ln_Pred = node;
 390         list->lh_Head          = node;
 391     }
 392 } /* Insert */
 393
 394 /*#AROS_LH********************************************************************
 395
 396     NAME */
 397         struct Node * RemHead (
 398
 399 /*  SYNOPSIS */
 400         struct List * list) /*#A0
 401             The list to remove the node from */
 402
 403 /*  LOCATION
 404         Exec (43), BaseNotNecessary
 405
 406     FUNCTION
 407         Remove the first node from a list.
 408
 409     RESULT
 410         The node that has been removed.
 411
 412     NOTES
 413
 414     EXAMPLE
 415         struct List * list;
 416         struct Node * head;
 417
 418         // Remove node and return it
 419         head = RemHead (list);
 420
 421     BUGS
 422
 423     SEE ALSO
 424         @AROS.Exec.LISTS@
 425
 426     INTERNALS
 427
 428 ******************************************************************************/
 429 {
 430     struct Node * node;
 431
 432     assert (list);
 433     /*
 434         Unfortunately, there is no (quick) check that the node
 435         is in a list
 436     */
 437
 438     /* Get the address of the first node or NULL */
 439     node = list->lh_Head->ln_Succ;
 440     if (node)
 441     {
 442         node->ln_Pred = (struct Node *)list;
 443         node = list->lh_Head;
 444         list->lh_Head = node->ln_Succ;
 445     }
 446
 447     /* Return the address or NULL */
 448     return node;
 449 } /* RemHead */
 450
 451 /*#AROS_LH********************************************************************
 452
 453     NAME */
 454         void Remove (
 455
 456 /*  SYNOPSIS */
 457         struct Node * node) /*#A1
 458             Remove this node from the list it is currently in. */
 459
 460 /*  LOCATION
 461         Exec (42), BaseNotNecessary
 462
 463     FUNCTION
 464         Remove a node from a list.
 465
 466     RESULT
 467
 468     NOTES
 469         There is no need to specify the list but the node must be in
 470         a list !
 471
 472     EXAMPLE
 473         struct Node * node;
 474
 475         // Remove node
 476         Remove (node);
 477
 478     BUGS
 479
 480     SEE ALSO
 481         @AROS.Exec.LISTS@
 482
 483     INTERNALS
 484
 485 ******************************************************************************/
 486 {
 487     assert (node);
 488     /*
 489         Unfortunately, there is no (quick) check that the node
 490         is in a list.
 491     */
 492
 493     /*
 494         Just bend the pointers around the node, ie. we make our
 495         predecessor point to our successor and vice versa
 496     */
 497     node->ln_Pred->ln_Succ = node->ln_Succ;
 498     node->ln_Succ->ln_Pred = node->ln_Pred;
 499 } /* Remove */
 500
 501 /*#AROS_LH********************************************************************
 502
 503     NAME */
 504         struct Node * RemTail (
 505
 506 /*  SYNOPSIS */
 507         struct List * list) /*#A0
 508             The list to remove the node from */
 509
 510 /*  LOCATION
 511         Exec (44), BaseNotNecessary
 512
 513     FUNCTION
 514         Remove the last node from a list.
 515
 516     RESULT
 517         The node that has been removed.
 518
 519     NOTES
 520
 521     EXAMPLE
 522         struct List * list;
 523         struct Node * tail;
 524
 525         // Remove node and return it
 526         tail = RemTail (list);
 527
 528     BUGS
 529
 530     SEE ALSO
 531         @AROS.Exec.LISTS@
 532
 533     INTERNALS
 534
 535 ******************************************************************************/
 536 {
 537     struct Node * node;
 538
 539     assert (list);
 540     /*
 541         Unfortunately, there is no (quick) check that the node
 542         is in a list.
 543     */
 544
 545     /* Get the last node of the list */
 546     if ( (node = GetTail (list)) )
 547     {
 548         /* normal code to remove a node if there is one */
 549         node->ln_Pred->ln_Succ = node->ln_Succ;
 550         node->ln_Succ->ln_Pred = node->ln_Pred;
 551     }
 552
 553     /* return it's address or NULL if there was no node */
 554     return node;
 555 } /* RemTail */
 556