diff options
Diffstat (limited to 'usr.bin/make/lst.c')
| -rw-r--r-- | usr.bin/make/lst.c | 344 |
1 files changed, 344 insertions, 0 deletions
diff --git a/usr.bin/make/lst.c b/usr.bin/make/lst.c new file mode 100644 index 0000000..d57c34b --- /dev/null +++ b/usr.bin/make/lst.c @@ -0,0 +1,344 @@ +/*- + * Copyright (c) 1988, 1989, 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Adam de Boor. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +/*- + * lst.c -- + * Routines to maintain a linked list of objects. + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "lst.h" +#include "util.h" + +/** + * Lst_Append + * Create a new node and add it to the given list after the given node. + * + * Arguments: + * l affected list + * ln node after which to append the datum + * d said datum + * + * Side Effects: + * A new LstNode is created and linked in to the List. The lastPtr + * field of the List will be altered if ln is the last node in the + * list. lastPtr and firstPtr will alter if the list was empty and + * ln was NULL. + */ +void +Lst_Append(Lst *list, LstNode *ln, void *d) +{ + LstNode *nLNode; + + nLNode = emalloc(sizeof(*nLNode)); + nLNode->datum = d; + + if (ln == NULL) { + nLNode->nextPtr = nLNode->prevPtr = NULL; + list->firstPtr = list->lastPtr = nLNode; + } else { + nLNode->prevPtr = ln; + nLNode->nextPtr = ln->nextPtr; + + ln->nextPtr = nLNode; + if (nLNode->nextPtr != NULL) { + nLNode->nextPtr->prevPtr = nLNode; + } + + if (ln == list->lastPtr) { + list->lastPtr = nLNode; + } + } +} + +/** + * Lst_Concat + * Concatenate two lists. New elements are created to hold the data + * elements, if specified, but the elements themselves are not copied. + * If the elements should be duplicated to avoid confusion with another + * list, the Lst_Duplicate function should be called first. + * + * Arguments: + * list1 The list to which list2 is to be appended + * list2 The list to append to list1 + * flags LST_CONCNEW if LstNode's should be duplicated + * LST_CONCLINK if should just be relinked + * + * Side Effects: + * New elements are created and appended the first list. + */ +void +Lst_Concat(Lst *list1, Lst *list2, int flags) +{ + LstNode *ln; /* original LstNode */ + LstNode *nln; /* new LstNode */ + LstNode *last; /* the last element in the list. Keeps + * bookkeeping until the end */ + + if (list2->firstPtr == NULL) + return; + + if (flags == LST_CONCLINK) { + /* + * Link the first element of the second list to the last + * element of the first list. If the first list isn't empty, + * we then link the last element of the list to the first + * element of the second list. The last element of the second + * list, if it exists, then becomes the last element of the + * first list. + */ + list2->firstPtr->prevPtr = list1->lastPtr; + if (list1->lastPtr != NULL) + list1->lastPtr->nextPtr = list2->firstPtr; + else + list1->firstPtr = list2->firstPtr; + list1->lastPtr = list2->lastPtr; + + Lst_Init(list2); + } else { + /* + * The loop simply goes through the entire second list creating + * new LstNodes and filling in the nextPtr, and prevPtr to fit + * into list1 and its datum field from the datum field of the + * corresponding element in list2. The 'last' node follows the + * last of the new nodes along until the entire list2 has been + * appended. Only then does the bookkeeping catch up with the + * changes. During the first iteration of the loop, if 'last' + * is NULL, the first list must have been empty so the + * newly-created node is made the first node of the list. + */ + for (last = list1->lastPtr, ln = list2->firstPtr; + ln != NULL; + ln = ln->nextPtr) { + nln = emalloc(sizeof(*nln)); + nln->datum = ln->datum; + if (last != NULL) { + last->nextPtr = nln; + } else { + list1->firstPtr = nln; + } + nln->prevPtr = last; + last = nln; + } + + /* + * Finish bookkeeping. The last new element becomes the last + * element of list one. + */ + list1->lastPtr = last; + last->nextPtr = NULL; + } +} + +/** + * Lst_DeQueue + * Remove and return the datum at the head of the given list. + * + * Results: + * The datum in the node at the head or (ick) NULL if the list + * is empty. + * + * Side Effects: + * The head node is removed from the list. + */ +void * +Lst_DeQueue(Lst *l) +{ + void *rd; + LstNode *tln; + + tln = Lst_First(l); + if (tln == NULL) { + return (NULL); + } + + rd = tln->datum; + Lst_Remove(l, tln); + return (rd); +} + +/** + * Lst_Destroy + * Destroy a list and free all its resources. If the freeProc is + * given, it is called with the datum from each node in turn before + * the node is freed. + * + * Side Effects: + * The given list is freed in its entirety. + */ +void +Lst_Destroy(Lst *list, FreeProc *freeProc) +{ + LstNode *ln; + + if (list->firstPtr == NULL) + return; + + if (freeProc != NOFREE) { + while ((ln = list->firstPtr) != NULL) { + list->firstPtr = ln->nextPtr; + (*freeProc)(ln->datum); + free(ln); + } + } else { + while ((ln = list->firstPtr) != NULL) { + list->firstPtr = ln->nextPtr; + free(ln); + } + } + list->lastPtr = NULL; +} + +/** + * Lst_Duplicate + * Duplicate an entire list. If a function to copy a void * is + * given, the individual client elements will be duplicated as well. + * + * Arguments: + * dst the destination list (initialized) + * src the list to duplicate + * copyProc A function to duplicate each void + */ +void +Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc) +{ + LstNode *ln; + + ln = src->firstPtr; + while (ln != NULL) { + if (copyProc != NOCOPY) + Lst_AtEnd(dst, (*copyProc)(ln->datum)); + else + Lst_AtEnd(dst, ln->datum); + ln = ln->nextPtr; + } +} + +/** + * Lst_Insert + * Insert a new node with the given piece of data before the given + * node in the given list. + * + * Parameters: + * l list to manipulate + * ln node before which to insert d + * d datum to be inserted + * + * Side Effects: + * the firstPtr field will be changed if ln is the first node in the + * list. + */ +void +Lst_Insert(Lst *list, LstNode *ln, void *d) +{ + LstNode *nLNode; /* new lnode for d */ + + nLNode = emalloc(sizeof(*nLNode)); + nLNode->datum = d; + + if (ln == NULL) { + nLNode->prevPtr = nLNode->nextPtr = NULL; + list->firstPtr = list->lastPtr = nLNode; + } else { + nLNode->prevPtr = ln->prevPtr; + nLNode->nextPtr = ln; + + if (nLNode->prevPtr != NULL) { + nLNode->prevPtr->nextPtr = nLNode; + } + ln->prevPtr = nLNode; + + if (ln == list->firstPtr) { + list->firstPtr = nLNode; + } + } +} + +LstNode * +Lst_Member(Lst *list, void *d) +{ + LstNode *lNode; + + lNode = list->firstPtr; + if (lNode == NULL) { + return (NULL); + } + + do { + if (lNode->datum == d) { + return (lNode); + } + lNode = lNode->nextPtr; + } while (lNode != NULL && lNode != list->firstPtr); + + return (NULL); +} + +/** + * Lst_Remove + * Remove the given node from the given list. + * + * Side Effects: + * The list's firstPtr will be set to NULL if ln is the last + * node on the list. firsPtr and lastPtr will be altered if ln is + * either the first or last node, respectively, on the list. + */ +void +Lst_Remove(Lst *list, LstNode *ln) +{ + /* + * unlink it from the list + */ + if (ln->nextPtr != NULL) + /* unlink from the backward chain */ + ln->nextPtr->prevPtr = ln->prevPtr; + else + /* this was the last element */ + list->lastPtr = ln->prevPtr; + + if (ln->prevPtr != NULL) + /* unlink from the forward chain */ + ln->prevPtr->nextPtr = ln->nextPtr; + else + /* this was the first element */ + list->firstPtr = ln->nextPtr; + + /* + * note that the datum is unmolested. The caller must free it as + * necessary and as expected. + */ + free(ln); +} |
