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         When supplied with a NULL list argument, defaults to the exec port list.
 253
 254     EXAMPLE
 255         struct List * list;
 256         struct Node * node;
 257
 258         // Look for a node with the name "Hello"
 259         node = FindName (list, "Hello");
 260
 261     BUGS
 262
 263     SEE ALSO
 264         @AROS.Exec.LISTS@
 265
 266     INTERNALS
 267
 268 ******************************************************************************/
 269 {
 270     struct Node * node;
 271
 272 /* FIX
 273         FindNode when supplied with a NULL list searches the exec ports list.
 274         per ampurtle, reference RKM 1.0
 275         Hmmm... why is there also a separate FindName.c
 276         Both files changed....
 277 */
 278     if( !list )
 279         list = &SysBase->PortList;
 280
 281     /* assert (list); */
 282     assert (name);
 283
 284     /* Look through the list */
 285     for (node=GetHead(list); node; node=GetSucc(node))
 286     {
 287         /* Only compare the names if this node has one. */
 288         if(node->ln_Name)
 289         {
 290             /* Check the node. If we found it, stop. */
 291             if (!strcmp (node->ln_Name, name))
 292                 break;
 293         }
 294     }
 295
 296     /*
 297         If we found a node, this will contain the pointer to it. If we
 298         didn't, this will be <code>NULL</code> (either because the list was
 299         empty or because we tried all nodes in the list)
 300     */
 301     return node;
 302 } /* FindName */
 303
 304 /*#AROS_LH********************************************************************
 305
 306     NAME */
 307         void Insert (
 308
 309 /*  SYNOPSIS */
 310         struct List * list, /*#A0
 311             The list to insert the node into */
 312         struct Node * node, /*#A1
 313             This node is to be inserted */
 314         struct Node * pred) /*#A2
 315             Insert after this node. If this is NULL, node is inserted
 316             as the first node (same as AddHead()) */
 317
 318 /*  LOCATION
 319         Exec (39), BaseNotNecessary
 320
 321     FUNCTION
 322         Insert Node <code>node</code> after <code>pred</code> in list.
 323
 324     RESULT
 325
 326     NOTES
 327
 328     EXAMPLE
 329         struct List * list;
 330         struct Node * pred, * node;
 331
 332         // Insert Node node as second node in list
 333         pred = GetHead (list);
 334         Insert (list, node, pred);
 335
 336     BUGS
 337
 338     SEE ALSO
 339         @AROS.Exec.LISTS@
 340
 341     INTERNALS
 342
 343 ******************************************************************************/
 344 {
 345     assert (node);
 346     assert (list);
 347
 348     /* If we have a node to insert behind... */
 349     if (pred)
 350     {
 351         /* Is this the last node in the list ? */
 352         if (pred->ln_Succ) /* Normal node ? */
 353         {
 354             /*
 355                 Our successor is the successor of the node we add ourselves
 356                 behind and our predecessor is just the node itself.
 357             */
 358             node->ln_Succ = pred->ln_Succ;
 359             node->ln_Pred = pred;
 360
 361             /*
 362                 We are the predecessor of the successor of our predecessor
 363                 (What ? blblblb... ;) and of our predecessor itself.
 364                 Note that here the sequence is quite important since
 365                 we need ln_Succ in the first expression and change it in
 366                 the second.
 367             */
 368             pred->ln_Succ->ln_Pred = node;
 369             pred->ln_Succ = node;
 370         }
 371         else /* last node */
 372         {
 373             /*
 374                 Add the node at the end of the list.
 375                 Make the node point to the head of the list. Our
 376                 predecessor is the previous last node of the list.
 377             */
 378             node->ln_Succ              = (struct Node *)&list->lh_Tail;
 379             node->ln_Pred              = list->lh_TailPred;
 380
 381             /*
 382                 Now we are the last now. Make the old last node point to us
 383                 and the pointer to the last node, too.
 384             */
 385             list->lh_TailPred->ln_Succ = node;
 386             list->lh_TailPred          = node;
 387         }
 388     }
 389     else
 390     {
 391         /*
 392             add at the top of the list. I do not use <code>AddHead()</code>
 393             here but write the code twice for two reasons: 1. The code is small
 394             and therefore errors are unlikely and 2. If I would call
 395             <code>AddHead()</code>, it would take almost as long to call the
 396             function as the execution would take yielding 100% overhead.
 397         */
 398         node->ln_Succ          = list->lh_Head;
 399         node->ln_Pred          = (struct Node *)&list->lh_Head;
 400         list->lh_Head->ln_Pred = node;
 401         list->lh_Head          = node;
 402     }
 403 } /* Insert */
 404
 405 /*#AROS_LH********************************************************************
 406
 407     NAME */
 408         struct Node * RemHead (
 409
 410 /*  SYNOPSIS */
 411         struct List * list) /*#A0
 412             The list to remove the node from */
 413
 414 /*  LOCATION
 415         Exec (43), BaseNotNecessary
 416
 417     FUNCTION
 418         Remove the first node from a list.
 419
 420     RESULT
 421         The node that has been removed.
 422
 423     NOTES
 424
 425     EXAMPLE
 426         struct List * list;
 427         struct Node * head;
 428
 429         // Remove node and return it
 430         head = RemHead (list);
 431
 432     BUGS
 433
 434     SEE ALSO
 435         @AROS.Exec.LISTS@
 436
 437     INTERNALS
 438
 439 ******************************************************************************/
 440 {
 441     struct Node * node;
 442
 443     assert (list);
 444     /*
 445         Unfortunately, there is no (quick) check that the node
 446         is in a list
 447     */
 448
 449     /* Get the address of the first node or NULL */
 450     node = list->lh_Head->ln_Succ;
 451     if (node)
 452     {
 453         node->ln_Pred = (struct Node *)list;
 454         node = list->lh_Head;
 455         list->lh_Head = node->ln_Succ;
 456     }
 457
 458     /* Return the address or NULL */
 459     return node;
 460 } /* RemHead */
 461
 462 /*#AROS_LH********************************************************************
 463
 464     NAME */
 465         void Remove (
 466
 467 /*  SYNOPSIS */
 468         struct Node * node) /*#A1
 469             Remove this node from the list it is currently in. */
 470
 471 /*  LOCATION
 472         Exec (42), BaseNotNecessary
 473
 474     FUNCTION
 475         Remove a node from a list.
 476
 477     RESULT
 478
 479     NOTES
 480         There is no need to specify the list but the node must be in
 481         a list !
 482
 483     EXAMPLE
 484         struct Node * node;
 485
 486         // Remove node
 487         Remove (node);
 488
 489     BUGS
 490
 491     SEE ALSO
 492         @AROS.Exec.LISTS@
 493
 494     INTERNALS
 495
 496 ******************************************************************************/
 497 {
 498     assert (node);
 499     /*
 500         Unfortunately, there is no (quick) check that the node
 501         is in a list.
 502     */
 503
 504     /*
 505         Just bend the pointers around the node, ie. we make our
 506         predecessor point to our successor and vice versa
 507     */
 508     node->ln_Pred->ln_Succ = node->ln_Succ;
 509     node->ln_Succ->ln_Pred = node->ln_Pred;
 510 } /* Remove */
 511
 512 /*#AROS_LH********************************************************************
 513
 514     NAME */
 515         struct Node * RemTail (
 516
 517 /*  SYNOPSIS */
 518         struct List * list) /*#A0
 519             The list to remove the node from */
 520
 521 /*  LOCATION
 522         Exec (44), BaseNotNecessary
 523
 524     FUNCTION
 525         Remove the last node from a list.
 526
 527     RESULT
 528         The node that has been removed.
 529
 530     NOTES
 531
 532     EXAMPLE
 533         struct List * list;
 534         struct Node * tail;
 535
 536         // Remove node and return it
 537         tail = RemTail (list);
 538
 539     BUGS
 540
 541     SEE ALSO
 542         @AROS.Exec.LISTS@
 543
 544     INTERNALS
 545
 546 ******************************************************************************/
 547 {
 548     struct Node * node;
 549
 550     assert (list);
 551     /*
 552         Unfortunately, there is no (quick) check that the node
 553         is in a list.
 554     */
 555
 556     /* Get the last node of the list */
 557     if ( (node = GetTail (list)) )
 558     {
 559         /* normal code to remove a node if there is one */
 560         node->ln_Pred->ln_Succ = node->ln_Succ;
 561         node->ln_Succ->ln_Pred = node->ln_Pred;
 562     }
 563
 564     /* return it's address or NULL if there was no node */
 565     return node;
 566 } /* RemTail */
 567