Index: head/usr.bin/make/lst.h =================================================================== --- head/usr.bin/make/lst.h (revision 138565) +++ head/usr.bin/make/lst.h (revision 138566) @@ -1,196 +1,196 @@ /* * Copyright (c) 1988, 1989, 1990, 1993 * The Regents of the University of California. All rights reserved. * Copyright (c) 1988, 1989 by Adam de Boor * Copyright (c) 1989 by Berkeley Softworks * 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. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. 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. * * @(#)lst.h 8.2 (Berkeley) 4/28/95 * $FreeBSD$ */ /*- * lst.h -- * Header for using the list library */ #ifndef _LST_H_ #define _LST_H_ #include #include #include "sprite.h" /* * Structure of a list node. */ struct LstNode { struct LstNode *prevPtr; /* previous element in list */ struct LstNode *nextPtr; /* next in list */ int useCount:8; /* Count of functions using the node. Node may not * be deleted until count goes to 0 */ int flags:8; /* Node status flags */ void *datum; /* datum associated with this element */ }; typedef struct LstNode LstNode; /* * Flags required for synchronization */ #define LN_DELETED 0x0001 /* List node should be removed when done */ typedef enum { LstHead, LstMiddle, LstTail, LstUnknown } LstWhere; /* * The list itself */ struct Lst { LstNode *firstPtr; /* first node in list */ LstNode *lastPtr; /* last node in list */ }; typedef struct Lst Lst; typedef int CompareProc(const void *, const void *); typedef int DoProc(void *, void *); typedef void *DuplicateProc(void *); typedef void FreeProc(void *); /* * NOFREE can be used as the freeProc to Lst_Destroy when the elements are * not to be freed. * NOCOPY performs similarly when given as the copyProc to Lst_Duplicate. */ #define NOFREE ((FreeProc *)NULL) #define NOCOPY ((DuplicateProc *)NULL) #define LST_CONCNEW 0 /* create new LstNode's when using Lst_Concat */ #define LST_CONCLINK 1 /* relink LstNode's when using Lst_Concat */ /* * Creation/destruction functions */ /* Create a new list */ Lst *Lst_Init(void); /* Duplicate an existing list */ Lst *Lst_Duplicate(Lst *, DuplicateProc *); /* Destroy an old one */ void Lst_Destroy(Lst *, FreeProc *); /* * Functions to modify a list */ /* Insert an element before another */ ReturnStatus Lst_Insert(Lst *, LstNode *, void *); /* Insert an element after another */ ReturnStatus Lst_Append(Lst *, LstNode *, void *); /* Place an element at the front of a lst. */ #define Lst_AtFront(LST, D) (Lst_Insert((LST), Lst_First(LST), (D))) /* Place an element at the end of a lst. */ #define Lst_AtEnd(LST, D) (Lst_Append((LST), Lst_Last(LST), (D))) /* Remove an element */ ReturnStatus Lst_Remove(Lst *, LstNode *); /* Replace a node with a new value */ #define Lst_Replace(NODE, D) (((NODE) == NULL) ? FAILURE : \ (((NODE)->datum = (D)), SUCCESS)) /* Concatenate two lists */ -ReturnStatus Lst_Concat(Lst *, Lst *, int); +void Lst_Concat(Lst *, Lst *, int); /* * Node-specific functions */ /* Return first element in list */ #define Lst_First(LST) ((Lst_Valid(LST) && !Lst_IsEmpty(LST)) \ ? (LST)->firstPtr : NULL) /* Return last element in list */ #define Lst_Last(LST) ((Lst_Valid(LST) && !Lst_IsEmpty(LST)) \ ? (LST)->lastPtr : NULL) /* Return successor to given element */ #define Lst_Succ(NODE) (((NODE) == NULL) ? NULL : (NODE)->nextPtr) /* Get datum from LstNode */ #define Lst_Datum(NODE) ((NODE)->datum) /* * Functions for entire lists */ /* Find an element in a list */ #define Lst_Find(LST, D, FN) (Lst_FindFrom((LST), Lst_First(LST), (D), (FN))) /* Find an element starting from somewhere */ LstNode *Lst_FindFrom(Lst *, LstNode *, const void *, CompareProc *); /* * See if the given datum is on the list. Returns the LstNode containing * the datum */ LstNode *Lst_Member(Lst *, void *); /* Apply a function to all elements of a lst */ void Lst_ForEach(Lst *, DoProc *, void *); #define Lst_ForEach(LST, FN, D) (Lst_ForEachFrom((LST), Lst_First(LST), \ (FN), (D))) /* * Apply a function to all elements of a lst starting from a certain point. * If the list is circular, the application will wrap around to the * beginning of the list again. */ void Lst_ForEachFrom(Lst *, LstNode *, DoProc *, void *); /* * for using the list as a queue */ /* Place an element at tail of queue */ #define Lst_EnQueue(LST, D) (Lst_Valid(LST) \ ? Lst_Append((LST), Lst_Last(LST), (D)) \ : FAILURE) /* Remove an element from head of queue */ void *Lst_DeQueue(Lst *); /* * LstValid (L) -- * Return TRUE if the list L is valid */ #define Lst_Valid(L) (((L) == NULL) ? FALSE : TRUE) /* * LstNodeValid (LN, L) -- * Return TRUE if the LstNode LN is valid with respect to L */ #define Lst_NodeValid(LN, L) (((LN) == NULL) ? FALSE : TRUE) /* * Lst_IsEmpty(L) -- * TRUE if the list L is empty. */ #define Lst_IsEmpty(L) (!Lst_Valid(L) || (L)->firstPtr == NULL) #endif /* _LST_H_ */ Index: head/usr.bin/make/lst.lib/lstConcat.c =================================================================== --- head/usr.bin/make/lst.lib/lstConcat.c (revision 138565) +++ head/usr.bin/make/lst.lib/lstConcat.c (revision 138566) @@ -1,150 +1,134 @@ /* * 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. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. 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. * * @(#)lstConcat.c 8.1 (Berkeley) 6/6/93 */ #ifndef lint #include __FBSDID("$FreeBSD$"); #endif /* not lint */ /*- * listConcat.c -- * Function to concatentate two lists. */ #include "make.h" #include "lst.h" /*- *----------------------------------------------------------------------- * 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. * * Results: * SUCCESS if all went well. FAILURE otherwise. * * 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 the first list. *----------------------------------------------------------------------- */ -ReturnStatus +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 (!Lst_Valid(list1) || !Lst_Valid(list2)) { - return (FAILURE); - } + if (list2->firstPtr == NULL) + return; if (flags == LST_CONCLINK) { - if (list2->firstPtr != NULL) { - /* - * We set the nextPtr of the last element of list two to be NULL - * to make the loop easier and so we don't need an extra case -- - * the final element will already point to NULL space and the first - * element will be untouched if it existed before and will also - * point to NULL space if it didn't. - */ - list2->lastPtr->nextPtr = NULL; - /* - * So long as the second list isn't empty, we just 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; - } - } else if (list2->firstPtr != NULL) { /* - * We set the nextPtr of the last element of list 2 to be NULL to make - * the loop less difficult. The loop simply goes through the entire + * 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; + + } 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. */ - list2->lastPtr->nextPtr = NULL; 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; nln->flags = nln->useCount = 0; last = nln; } /* * Finish bookkeeping. The last new element becomes the last element * of list one. */ list1->lastPtr = last; last->nextPtr = NULL; } - - return (SUCCESS); }