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