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  * $FreeBSD$
  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
  73     if (ln == NULL) {
  74         nLNode->nextPtr = nLNode->prevPtr = NULL;
  75         list->firstPtr = list->lastPtr = nLNode;
  76     } else {
  77         nLNode->prevPtr = ln;
  78         nLNode->nextPtr = ln->nextPtr;
  79
  80         ln->nextPtr = nLNode;
  81         if (nLNode->nextPtr != NULL) {
  82             nLNode->nextPtr->prevPtr = nLNode;
  83         }
  84
  85         if (ln == list->lastPtr) {
  86             list->lastPtr = nLNode;
  87         }
  88     }
  89 }
  90
  91 /*-
  92  *-----------------------------------------------------------------------
  93  * Lst_Concat --
  94  *      Concatenate two lists. New elements are created to hold the data
  95  *      elements, if specified, but the elements themselves are not copied.
  96  *      If the elements should be duplicated to avoid confusion with another
  97  *      list, the Lst_Duplicate function should be called first.
  98  *
  99  * Results:
 100  *      SUCCESS if all went well. FAILURE otherwise.
 101  *
 102  * Arguments:
 103  *      list1   The list to which list2 is to be appended
 104  *      list2   The list to append to list1
 105  *      flags   LST_CONCNEW if LstNode's should be duplicated
 106  *              LST_CONCLINK if should just be relinked
 107  *
 108  * Side Effects:
 109  *      New elements are created and appended the the first list.
 110  *-----------------------------------------------------------------------
 111  */
 112 void
 113 Lst_Concat(Lst *list1, Lst *list2, int flags)
 114 {
 115     LstNode *ln;        /* original LstNode */
 116     LstNode *nln;       /* new LstNode */
 117     LstNode *last;      /* the last element in the list. Keeps
 118                          * bookkeeping until the end */
 119
 120     if (list2->firstPtr == NULL)
 121         return;
 122
 123     if (flags == LST_CONCLINK) {
 124         /*
 125          * Link the first element of the second list to the last element of the
 126          * first list. If the first list isn't empty, we then link the
 127          * last element of the list to the first element of the second list
 128          * The last element of the second list, if it exists, then becomes
 129          * the last element of the first list.
 130          */
 131         list2->firstPtr->prevPtr = list1->lastPtr;
 132         if (list1->lastPtr != NULL)
 133             list1->lastPtr->nextPtr = list2->firstPtr;
 134         else
 135             list1->firstPtr = list2->firstPtr;
 136         list1->lastPtr = list2->lastPtr;
 137
 138         Lst_Init(list2);
 139     } else {
 140         /*
 141          * The loop simply goes through the entire
 142          * second list creating new LstNodes and filling in the nextPtr, and
 143          * prevPtr to fit into list1 and its datum field from the
 144          * datum field of the corresponding element in list2. The 'last' node
 145          * follows the last of the new nodes along until the entire list2 has
 146          * been appended. Only then does the bookkeeping catch up with the
 147          * changes. During the first iteration of the loop, if 'last' is NULL,
 148          * the first list must have been empty so the newly-created node is
 149          * made the first node of the list.
 150          */
 151         for (last = list1->lastPtr, ln = list2->firstPtr;
 152              ln != NULL;
 153              ln = ln->nextPtr)
 154         {
 155             nln = emalloc(sizeof(*nln));
 156             nln->datum = ln->datum;
 157             if (last != NULL) {
 158                 last->nextPtr = nln;
 159             } else {
 160                 list1->firstPtr = nln;
 161             }
 162             nln->prevPtr = last;
 163             last = nln;
 164         }
 165
 166         /*
 167          * Finish bookkeeping. The last new element becomes the last element
 168          * of list one.
 169          */
 170         list1->lastPtr = last;
 171         last->nextPtr = NULL;
 172     }
 173 }
 174
 175 /*-
 176  *-----------------------------------------------------------------------
 177  * Lst_DeQueue --
 178  *      Remove and return the datum at the head of the given list.
 179  *
 180  * Results:
 181  *      The datum in the node at the head or (ick) NULL if the list
 182  *      is empty.
 183  *
 184  * Side Effects:
 185  *      The head node is removed from the list.
 186  *
 187  *-----------------------------------------------------------------------
 188  */
 189 void *
 190 Lst_DeQueue(Lst *l)
 191 {
 192     void *rd;
 193     LstNode *tln;
 194
 195     tln = Lst_First(l);
 196     if (tln == NULL) {
 197         return (NULL);
 198     }
 199
 200     rd = tln->datum;
 201     Lst_Remove(l, tln);
 202     return (rd);
 203 }
 204
 205 /*-
 206  *-----------------------------------------------------------------------
 207  * Lst_Destroy --
 208  *      Destroy a list and free all its resources. If the freeProc is
 209  *      given, it is called with the datum from each node in turn before
 210  *      the node is freed.
 211  *
 212  * Results:
 213  *      None.
 214  *
 215  * Side Effects:
 216  *      The given list is freed in its entirety.
 217  *
 218  *-----------------------------------------------------------------------
 219  */
 220 void
 221 Lst_Destroy(Lst *list, FreeProc *freeProc)
 222 {
 223     LstNode *ln;
 224
 225     if (list->firstPtr == NULL)
 226         return;
 227
 228     if (freeProc != NOFREE) {
 229         while ((ln = list->firstPtr) != NULL) {
 230             list->firstPtr = ln->nextPtr;
 231             (*freeProc)(ln->datum);
 232             free(ln);
 233         }
 234     } else {
 235         while ((ln = list->firstPtr) != NULL) {
 236             list->firstPtr = ln->nextPtr;
 237             free(ln);
 238         }
 239     }
 240     list->lastPtr = NULL;
 241 }
 242
 243 /*-
 244  *-----------------------------------------------------------------------
 245  * Lst_Duplicate --
 246  *      Duplicate an entire list. If a function to copy a void * is
 247  *      given, the individual client elements will be duplicated as well.
 248  *
 249  * Arguments:
 250  *      dst     the destination list (initialized)
 251  *      src     the list to duplicate
 252  *      copyProc A function to duplicate each void
 253  *
 254  *-----------------------------------------------------------------------
 255  */
 256 void
 257 Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc)
 258 {
 259     LstNode *ln;
 260
 261     ln = src->firstPtr;
 262     while (ln != NULL) {
 263         if (copyProc != NOCOPY)
 264             Lst_AtEnd(dst, (*copyProc)(ln->datum));
 265         else
 266             Lst_AtEnd(dst, ln->datum);
 267         ln = ln->nextPtr;
 268     }
 269 }
 270
 271 /*-
 272  *-----------------------------------------------------------------------
 273  * Lst_Insert --
 274  *      Insert a new node with the given piece of data before the given
 275  *      node in the given list.
 276  *
 277  * Parameters:
 278  *      l       list to manipulate
 279  *      ln      node before which to insert d
 280  *      d       datum to be inserted
 281  *
 282  * Side Effects:
 283  *      the firstPtr field will be changed if ln is the first node in the
 284  *      list.
 285  *
 286  *-----------------------------------------------------------------------
 287  */
 288 void
 289 Lst_Insert(Lst *list, LstNode *ln, void *d)
 290 {
 291     LstNode *nLNode;    /* new lnode for d */
 292
 293     nLNode = emalloc(sizeof(*nLNode));
 294     nLNode->datum = d;
 295
 296     if (ln == NULL) {
 297         nLNode->prevPtr = nLNode->nextPtr = NULL;
 298         list->firstPtr = list->lastPtr = nLNode;
 299     } else {
 300         nLNode->prevPtr = ln->prevPtr;
 301         nLNode->nextPtr = ln;
 302
 303         if (nLNode->prevPtr != NULL) {
 304             nLNode->prevPtr->nextPtr = nLNode;
 305         }
 306         ln->prevPtr = nLNode;
 307
 308         if (ln == list->firstPtr) {
 309             list->firstPtr = nLNode;
 310         }
 311     }
 312 }
 313
 314 LstNode *
 315 Lst_Member(Lst *list, void *d)
 316 {
 317     LstNode *lNode;
 318
 319     lNode = list->firstPtr;
 320     if (lNode == NULL) {
 321         return (NULL);
 322     }
 323
 324     do {
 325         if (lNode->datum == d) {
 326             return (lNode);
 327         }
 328         lNode = lNode->nextPtr;
 329     } while (lNode != NULL && lNode != list->firstPtr);
 330
 331     return (NULL);
 332 }
 333
 334 /*-
 335  *-----------------------------------------------------------------------
 336  * Lst_Remove --
 337  *      Remove the given node from the given list.
 338  *
 339  * Results:
 340  *      SUCCESS or FAILURE.
 341  *
 342  * Side Effects:
 343  *      The list's firstPtr will be set to NULL if ln is the last
 344  *      node on the list. firsPtr and lastPtr will be altered if ln is
 345  *      either the first or last node, respectively, on the list.
 346  *
 347  *-----------------------------------------------------------------------
 348  */
 349 void
 350 Lst_Remove(Lst *list, LstNode *ln)
 351 {
 352     /*
 353      * unlink it from the list
 354      */
 355     if (ln->nextPtr != NULL)
 356         /* unlink from the backward chain */
 357         ln->nextPtr->prevPtr = ln->prevPtr;
 358     else
 359         /* this was the last element */
 360         list->lastPtr = ln->prevPtr;
 361
 362     if (ln->prevPtr != NULL)
 363         /* unlink from the forward chain */
 364         ln->prevPtr->nextPtr = ln->nextPtr;
 365     else
 366         /* this was the first element */
 367         list->firstPtr = ln->nextPtr;
 368
 369     /*
 370      * note that the datum is unmolested. The caller must free it as
 371      * necessary and as expected.
 372      */
 373     free(ln);
 374 }