usr.bin/make/lst.c

   1 /*-
   2  * Copyright (c) 1988, 1989, 1990, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Adam de Boor.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $DragonFly: src/usr.bin/make/lst.c,v 1.2 2005/02/01 22:05:36 okumoto Exp $
  33  */
  34
  35 /*-
  36  * lst.c --
  37  *      Routines to maintain a linked list of objects.
  38  */
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42
  43 #include "lst.h"
  44 #include "make.h"
  45 #include "util.h"
  46
  47 /*-
  48  *-----------------------------------------------------------------------
  49  * Lst_Append --
  50  *      Create a new node and add it to the given list after the given node.
  51  *
  52  * Arguments:
  53  *      l       affected list
  54  *      ln      node after which to append the datum
  55  *      d       said datum
  56  *
  57  * Side Effects:
  58  *      A new LstNode is created and linked in to the List. The lastPtr
  59  *      field of the List will be altered if ln is the last node in the
  60  *      list. lastPtr and firstPtr will alter if the list was empty and
  61  *      ln was NULL.
  62  *
  63  *-----------------------------------------------------------------------
  64  */
  65 void
  66 Lst_Append(Lst *list, LstNode *ln, void *d)
  67 {
  68     LstNode *nLNode;
  69
  70     nLNode = emalloc(sizeof(*nLNode));
  71     nLNode->datum = d;
  72     nLNode->useCount = nLNode->flags = 0;
  73
  74     if (ln == NULL) {
  75         nLNode->nextPtr = nLNode->prevPtr = NULL;
  76         list->firstPtr = list->lastPtr = nLNode;
  77     } else {
  78         nLNode->prevPtr = ln;
  79         nLNode->nextPtr = ln->nextPtr;
  80
  81         ln->nextPtr = nLNode;
  82         if (nLNode->nextPtr != NULL) {
  83             nLNode->nextPtr->prevPtr = nLNode;
  84         }
  85
  86         if (ln == list->lastPtr) {
  87             list->lastPtr = nLNode;
  88         }
  89     }
  90 }
  91
  92 /*-
  93  *-----------------------------------------------------------------------
  94  * Lst_Concat --
  95  *      Concatenate two lists. New elements are created to hold the data
  96  *      elements, if specified, but the elements themselves are not copied.
  97  *      If the elements should be duplicated to avoid confusion with another
  98  *      list, the Lst_Duplicate function should be called first.
  99  *
 100  * Results:
 101  *      SUCCESS if all went well. FAILURE otherwise.
 102  *
 103  * Arguments:
 104  *      list1   The list to which list2 is to be appended
 105  *      list2   The list to append to list1
 106  *      flags   LST_CONCNEW if LstNode's should be duplicated
 107  *              LST_CONCLINK if should just be relinked
 108  *
 109  * Side Effects:
 110  *      New elements are created and appended the the first list.
 111  *-----------------------------------------------------------------------
 112  */
 113 void
 114 Lst_Concat(Lst *list1, Lst *list2, int flags)
 115 {
 116     LstNode *ln;        /* original LstNode */
 117     LstNode *nln;       /* new LstNode */
 118     LstNode *last;      /* the last element in the list. Keeps
 119                          * bookkeeping until the end */
 120
 121     if (list2->firstPtr == NULL)
 122         return;
 123
 124     if (flags == LST_CONCLINK) {
 125         /*
 126          * Link the first element of the second list to the last element of the
 127          * first list. If the first list isn't empty, we then link the
 128          * last element of the list to the first element of the second list
 129          * The last element of the second list, if it exists, then becomes
 130          * the last element of the first list.
 131          */
 132         list2->firstPtr->prevPtr = list1->lastPtr;
 133         if (list1->lastPtr != NULL)
 134             list1->lastPtr->nextPtr = list2->firstPtr;
 135         else
 136             list1->firstPtr = list2->firstPtr;
 137         list1->lastPtr = list2->lastPtr;
 138
 139         Lst_Init(list2);
 140     } else {
 141         /*
 142          * The loop simply goes through the entire
 143          * second list creating new LstNodes and filling in the nextPtr, and
 144          * prevPtr to fit into list1 and its datum field from the
 145          * datum field of the corresponding element in list2. The 'last' node
 146          * follows the last of the new nodes along until the entire list2 has
 147          * been appended. Only then does the bookkeeping catch up with the
 148          * changes. During the first iteration of the loop, if 'last' is NULL,
 149          * the first list must have been empty so the newly-created node is
 150          * made the first node of the list.
 151          */
 152         for (last = list1->lastPtr, ln = list2->firstPtr;
 153              ln != NULL;
 154              ln = ln->nextPtr)
 155         {
 156             nln = emalloc(sizeof(*nln));
 157             nln->datum = ln->datum;
 158             if (last != NULL) {
 159                 last->nextPtr = nln;
 160             } else {
 161                 list1->firstPtr = nln;
 162             }
 163             nln->prevPtr = last;
 164             nln->flags = nln->useCount = 0;
 165             last = nln;
 166         }
 167
 168         /*
 169          * Finish bookkeeping. The last new element becomes the last element
 170          * of list one.
 171          */
 172         list1->lastPtr = last;
 173         last->nextPtr = NULL;
 174     }
 175 }
 176
 177 /*-
 178  *-----------------------------------------------------------------------
 179  * Lst_DeQueue --
 180  *      Remove and return the datum at the head of the given list.
 181  *
 182  * Results:
 183  *      The datum in the node at the head or (ick) NULL if the list
 184  *      is empty.
 185  *
 186  * Side Effects:
 187  *      The head node is removed from the list.
 188  *
 189  *-----------------------------------------------------------------------
 190  */
 191 void *
 192 Lst_DeQueue(Lst *l)
 193 {
 194     void *rd;
 195     LstNode *tln;
 196
 197     tln = Lst_First(l);
 198     if (tln == NULL) {
 199         return (NULL);
 200     }
 201
 202     rd = tln->datum;
 203     Lst_Remove(l, tln);
 204     return (rd);
 205 }
 206
 207 /*-
 208  *-----------------------------------------------------------------------
 209  * Lst_Destroy --
 210  *      Destroy a list and free all its resources. If the freeProc is
 211  *      given, it is called with the datum from each node in turn before
 212  *      the node is freed.
 213  *
 214  * Results:
 215  *      None.
 216  *
 217  * Side Effects:
 218  *      The given list is freed in its entirety.
 219  *
 220  *-----------------------------------------------------------------------
 221  */
 222 void
 223 Lst_Destroy(Lst *list, FreeProc *freeProc)
 224 {
 225     LstNode *ln;
 226
 227     if (list->firstPtr == NULL)
 228         return;
 229
 230     if (freeProc != NOFREE) {
 231         while ((ln = list->firstPtr) != NULL) {
 232             list->firstPtr = ln->nextPtr;
 233             (*freeProc)(ln->datum);
 234             free(ln);
 235         }
 236     } else {
 237         while ((ln = list->firstPtr) != NULL) {
 238             list->firstPtr = ln->nextPtr;
 239             free(ln);
 240         }
 241     }
 242     list->lastPtr = NULL;
 243 }
 244
 245 /*-
 246  *-----------------------------------------------------------------------
 247  * Lst_Duplicate --
 248  *      Duplicate an entire list. If a function to copy a void * is
 249  *      given, the individual client elements will be duplicated as well.
 250  *
 251  * Arguments:
 252  *      dst     the destination list (initialized)
 253  *      src     the list to duplicate
 254  *      copyProc A function to duplicate each void
 255  *
 256  *-----------------------------------------------------------------------
 257  */
 258 void
 259 Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc)
 260 {
 261     LstNode *ln;
 262
 263     ln = src->firstPtr;
 264     while (ln != NULL) {
 265         if (copyProc != NOCOPY)
 266             Lst_AtEnd(dst, (*copyProc)(ln->datum));
 267         else
 268             Lst_AtEnd(dst, ln->datum);
 269         ln = ln->nextPtr;
 270     }
 271 }
 272
 273 /*-
 274  *-----------------------------------------------------------------------
 275  * Lst_FindFrom --
 276  *      Search for a node starting and ending with the given one on the
 277  *      given list using the passed datum and comparison function to
 278  *      determine when it has been found.
 279  *
 280  * Results:
 281  *      The found node or NULL
 282  *
 283  * Side Effects:
 284  *      None.
 285  *
 286  *-----------------------------------------------------------------------
 287  */
 288 LstNode *
 289 Lst_FindFrom(Lst *l, LstNode *ln, const void *d, CompareProc *cProc)
 290 {
 291     LstNode *tln;
 292     Boolean     found = FALSE;
 293
 294     if (!Lst_Valid(l) || Lst_IsEmpty(l) || !Lst_NodeValid(ln, l)) {
 295         return (NULL);
 296     }
 297
 298     tln = ln;
 299
 300     do {
 301         if ((*cProc)(tln->datum, d) == 0) {
 302             found = TRUE;
 303             break;
 304         } else {
 305             tln = tln->nextPtr;
 306         }
 307     } while (tln != ln && tln != NULL);
 308
 309     if (found) {
 310         return (tln);
 311     } else {
 312         return (NULL);
 313     }
 314 }
 315
 316 /*-
 317  *-----------------------------------------------------------------------
 318  * Lst_ForEachFrom --
 319  *      Apply the given function to each element of the given list. The
 320  *      function should return 0 if traversal should continue and non-
 321  *      zero if it should abort.
 322  *
 323  * Results:
 324  *      None.
 325  *
 326  * Side Effects:
 327  *      Only those created by the passed-in function.
 328  *
 329  *-----------------------------------------------------------------------
 330  */
 331 void
 332 Lst_ForEachFrom(Lst *list, LstNode *ln, DoProc *proc, void *d)
 333 {
 334     LstNode     *next;
 335     Boolean     done;
 336     int         result;
 337
 338     if (!Lst_Valid(list) || Lst_IsEmpty(list)) {
 339         return;
 340     }
 341
 342     do {
 343         /*
 344          * Take care of having the current element deleted out from under
 345          * us.
 346          */
 347
 348         next = ln->nextPtr;
 349
 350         ln->useCount++;
 351         result = (*proc)(ln->datum, d);
 352         ln->useCount--;
 353
 354         /*
 355          * We're done with the traversal if
 356          *  - nothing's been added after the current node and
 357          *  - the next node to examine is the first in the queue or
 358          *    doesn't exist.
 359          */
 360         done = (next == ln->nextPtr &&
 361                 (next == NULL || next == list->firstPtr));
 362
 363         next = ln->nextPtr;
 364
 365         if (ln->flags & LN_DELETED) {
 366             free(ln);
 367         }
 368         ln = next;
 369     } while (!result && !Lst_IsEmpty(list) && !done);
 370 }
 371
 372 /*-
 373  *-----------------------------------------------------------------------
 374  * Lst_Insert --
 375  *      Insert a new node with the given piece of data before the given
 376  *      node in the given list.
 377  *
 378  * Parameters:
 379  *      l       list to manipulate
 380  *      ln      node before which to insert d
 381  *      d       datum to be inserted
 382  *
 383  * Side Effects:
 384  *      the firstPtr field will be changed if ln is the first node in the
 385  *      list.
 386  *
 387  *-----------------------------------------------------------------------
 388  */
 389 void
 390 Lst_Insert(Lst *list, LstNode *ln, void *d)
 391 {
 392     LstNode *nLNode;    /* new lnode for d */
 393
 394     nLNode = emalloc(sizeof(*nLNode));
 395     nLNode->datum = d;
 396     nLNode->useCount = nLNode->flags = 0;
 397
 398     if (ln == NULL) {
 399         nLNode->prevPtr = nLNode->nextPtr = NULL;
 400         list->firstPtr = list->lastPtr = nLNode;
 401     } else {
 402         nLNode->prevPtr = ln->prevPtr;
 403         nLNode->nextPtr = ln;
 404
 405         if (nLNode->prevPtr != NULL) {
 406             nLNode->prevPtr->nextPtr = nLNode;
 407         }
 408         ln->prevPtr = nLNode;
 409
 410         if (ln == list->firstPtr) {
 411             list->firstPtr = nLNode;
 412         }
 413     }
 414 }
 415
 416 LstNode *
 417 Lst_Member(Lst *list, void *d)
 418 {
 419     LstNode *lNode;
 420
 421     lNode = list->firstPtr;
 422     if (lNode == NULL) {
 423         return (NULL);
 424     }
 425
 426     do {
 427         if (lNode->datum == d) {
 428             return (lNode);
 429         }
 430         lNode = lNode->nextPtr;
 431     } while (lNode != NULL && lNode != list->firstPtr);
 432
 433     return (NULL);
 434 }
 435
 436 /*-
 437  *-----------------------------------------------------------------------
 438  * Lst_Remove --
 439  *      Remove the given node from the given list.
 440  *
 441  * Results:
 442  *      SUCCESS or FAILURE.
 443  *
 444  * Side Effects:
 445  *      The list's firstPtr will be set to NULL if ln is the last
 446  *      node on the list. firsPtr and lastPtr will be altered if ln is
 447  *      either the first or last node, respectively, on the list.
 448  *
 449  *-----------------------------------------------------------------------
 450  */
 451 void
 452 Lst_Remove(Lst *list, LstNode *ln)
 453 {
 454     /*
 455      * unlink it from the list
 456      */
 457     if (ln->nextPtr != NULL)
 458         /* unlink from the backward chain */
 459         ln->nextPtr->prevPtr = ln->prevPtr;
 460     else
 461         /* this was the last element */
 462         list->lastPtr = ln->prevPtr;
 463
 464     if (ln->prevPtr != NULL)
 465         /* unlink from the forward chain */
 466         ln->prevPtr->nextPtr = ln->nextPtr;
 467     else
 468         /* this was the first element */
 469         list->firstPtr = ln->nextPtr;
 470
 471     /*
 472      * note that the datum is unmolested. The caller must free it as
 473      * necessary and as expected.
 474      */
 475     if (ln->useCount == 0) {
 476         free(ln);
 477     } else {
 478         ln->flags |= LN_DELETED;
 479     }
 480 }