2 * Copyright (c) 1988, 1989, 1990, 1993
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
32 * $DragonFly: src/usr.bin/make/lst.c,v 1.2 2005/02/01 22:05:36 okumoto Exp $
37 * Routines to maintain a linked list of objects.
48 *-----------------------------------------------------------------------
50 * Create a new node and add it to the given list after the given node.
54 * ln node after which to append the datum
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
63 *-----------------------------------------------------------------------
66 Lst_Append(Lst *list, LstNode *ln, void *d)
70 nLNode = emalloc(sizeof(*nLNode));
72 nLNode->useCount = nLNode->flags = 0;
75 nLNode->nextPtr = nLNode->prevPtr = NULL;
76 list->firstPtr = list->lastPtr = nLNode;
79 nLNode->nextPtr = ln->nextPtr;
82 if (nLNode->nextPtr != NULL) {
83 nLNode->nextPtr->prevPtr = nLNode;
86 if (ln == list->lastPtr) {
87 list->lastPtr = nLNode;
93 *-----------------------------------------------------------------------
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.
101 * SUCCESS if all went well. FAILURE otherwise.
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
110 * New elements are created and appended the the first list.
111 *-----------------------------------------------------------------------
114 Lst_Concat(Lst *list1, Lst *list2, int flags)
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 */
121 if (list2->firstPtr == NULL)
124 if (flags == LST_CONCLINK) {
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.
132 list2->firstPtr->prevPtr = list1->lastPtr;
133 if (list1->lastPtr != NULL)
134 list1->lastPtr->nextPtr = list2->firstPtr;
136 list1->firstPtr = list2->firstPtr;
137 list1->lastPtr = list2->lastPtr;
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.
152 for (last = list1->lastPtr, ln = list2->firstPtr;
156 nln = emalloc(sizeof(*nln));
157 nln->datum = ln->datum;
161 list1->firstPtr = nln;
164 nln->flags = nln->useCount = 0;
169 * Finish bookkeeping. The last new element becomes the last element
172 list1->lastPtr = last;
173 last->nextPtr = NULL;
178 *-----------------------------------------------------------------------
180 * Remove and return the datum at the head of the given list.
183 * The datum in the node at the head or (ick) NULL if the list
187 * The head node is removed from the list.
189 *-----------------------------------------------------------------------
208 *-----------------------------------------------------------------------
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
218 * The given list is freed in its entirety.
220 *-----------------------------------------------------------------------
223 Lst_Destroy(Lst *list, FreeProc *freeProc)
227 if (list->firstPtr == NULL)
230 if (freeProc != NOFREE) {
231 while ((ln = list->firstPtr) != NULL) {
232 list->firstPtr = ln->nextPtr;
233 (*freeProc)(ln->datum);
237 while ((ln = list->firstPtr) != NULL) {
238 list->firstPtr = ln->nextPtr;
242 list->lastPtr = NULL;
246 *-----------------------------------------------------------------------
248 * Duplicate an entire list. If a function to copy a void * is
249 * given, the individual client elements will be duplicated as well.
252 * dst the destination list (initialized)
253 * src the list to duplicate
254 * copyProc A function to duplicate each void
256 *-----------------------------------------------------------------------
259 Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc)
265 if (copyProc != NOCOPY)
266 Lst_AtEnd(dst, (*copyProc)(ln->datum));
268 Lst_AtEnd(dst, ln->datum);
274 *-----------------------------------------------------------------------
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.
281 * The found node or NULL
286 *-----------------------------------------------------------------------
289 Lst_FindFrom(Lst *l, LstNode *ln, const void *d, CompareProc *cProc)
292 Boolean found = FALSE;
294 if (!Lst_Valid(l) || Lst_IsEmpty(l) || !Lst_NodeValid(ln, l)) {
301 if ((*cProc)(tln->datum, d) == 0) {
307 } while (tln != ln && tln != NULL);
317 *-----------------------------------------------------------------------
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.
327 * Only those created by the passed-in function.
329 *-----------------------------------------------------------------------
332 Lst_ForEachFrom(Lst *list, LstNode *ln, DoProc *proc, void *d)
338 if (!Lst_Valid(list) || Lst_IsEmpty(list)) {
344 * Take care of having the current element deleted out from under
351 result = (*proc)(ln->datum, d);
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
360 done = (next == ln->nextPtr &&
361 (next == NULL || next == list->firstPtr));
365 if (ln->flags & LN_DELETED) {
369 } while (!result && !Lst_IsEmpty(list) && !done);
373 *-----------------------------------------------------------------------
375 * Insert a new node with the given piece of data before the given
376 * node in the given list.
379 * l list to manipulate
380 * ln node before which to insert d
381 * d datum to be inserted
384 * the firstPtr field will be changed if ln is the first node in the
387 *-----------------------------------------------------------------------
390 Lst_Insert(Lst *list, LstNode *ln, void *d)
392 LstNode *nLNode; /* new lnode for d */
394 nLNode = emalloc(sizeof(*nLNode));
396 nLNode->useCount = nLNode->flags = 0;
399 nLNode->prevPtr = nLNode->nextPtr = NULL;
400 list->firstPtr = list->lastPtr = nLNode;
402 nLNode->prevPtr = ln->prevPtr;
403 nLNode->nextPtr = ln;
405 if (nLNode->prevPtr != NULL) {
406 nLNode->prevPtr->nextPtr = nLNode;
408 ln->prevPtr = nLNode;
410 if (ln == list->firstPtr) {
411 list->firstPtr = nLNode;
417 Lst_Member(Lst *list, void *d)
421 lNode = list->firstPtr;
427 if (lNode->datum == d) {
430 lNode = lNode->nextPtr;
431 } while (lNode != NULL && lNode != list->firstPtr);
437 *-----------------------------------------------------------------------
439 * Remove the given node from the given list.
442 * SUCCESS or FAILURE.
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.
449 *-----------------------------------------------------------------------
452 Lst_Remove(Lst *list, LstNode *ln)
455 * unlink it from the list
457 if (ln->nextPtr != NULL)
458 /* unlink from the backward chain */
459 ln->nextPtr->prevPtr = ln->prevPtr;
461 /* this was the last element */
462 list->lastPtr = ln->prevPtr;
464 if (ln->prevPtr != NULL)
465 /* unlink from the forward chain */
466 ln->prevPtr->nextPtr = ln->nextPtr;
468 /* this was the first element */
469 list->firstPtr = ln->nextPtr;
472 * note that the datum is unmolested. The caller must free it as
473 * necessary and as expected.
475 if (ln->useCount == 0) {
478 ln->flags |= LN_DELETED;