BSD 4.4 Lite Usr.bin Sources

27 files changed, 2405 insertions, 0 deletions

diff --git a/usr.bin/make/lst.lib/lstAppend.c b/usr.bin/make/lst.lib/lstAppend.c
new file mode 100644
index 000000000000..0a1d52b24506
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstAppend.c
@@ -0,0 +1,113 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstAppend.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstAppend.c --
+ *	Add a new node with a new datum after an existing node
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Append --
+ *	Create a new node and add it to the given list after the given node.
+ *
+ * Results:
+ *	SUCCESS if all went well.
+ *
+ * Side Effects:
+ *	A new ListNode 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 NILLNODE.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Append (l, ln, d)
+    Lst	  	l;	/* affected list */
+    LstNode	ln;	/* node after which to append the datum */
+    ClientData	d;	/* said datum */
+{
+    register List 	list;
+    register ListNode	lNode;
+    register ListNode	nLNode;
+    
+    if (LstValid (l) && (ln == NILLNODE && LstIsEmpty (l))) {
+	goto ok;
+    }
+    
+    if (!LstValid (l) || LstIsEmpty (l)  || ! LstNodeValid (ln, l)) {
+	return (FAILURE);
+    }
+    ok:
+    
+    list = (List)l;
+    lNode = (ListNode)ln;
+
+    PAlloc (nLNode, ListNode);
+    nLNode->datum = d;
+    nLNode->useCount = nLNode->flags = 0;
+    
+    if (lNode == NilListNode) {
+	if (list->isCirc) {
+	    nLNode->nextPtr = nLNode->prevPtr = nLNode;
+	} else {
+	    nLNode->nextPtr = nLNode->prevPtr = NilListNode;
+	}
+	list->firstPtr = list->lastPtr = nLNode;
+    } else {
+	nLNode->prevPtr = lNode;
+	nLNode->nextPtr = lNode->nextPtr;
+	
+	lNode->nextPtr = nLNode;
+	if (nLNode->nextPtr != NilListNode) {
+	    nLNode->nextPtr->prevPtr = nLNode;
+	}
+	
+	if (lNode == list->lastPtr) {
+	    list->lastPtr = nLNode;
+	}
+    }
+    
+    return (SUCCESS);
+}
+
diff --git a/usr.bin/make/lst.lib/lstAtEnd.c b/usr.bin/make/lst.lib/lstAtEnd.c
new file mode 100644
index 000000000000..dce8a07f77dc
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstAtEnd.c
@@ -0,0 +1,70 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstAtEnd.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstAtEnd.c --
+ *	Add a node at the end of the list
+ */
+
+#include	"lstInt.h"
+	
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_AtEnd --
+ *	Add a node to the end of the given list
+ *
+ * Results:
+ *	SUCCESS if life is good.
+ *
+ * Side Effects:
+ *	A new ListNode is created and added to the list.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_AtEnd (l, d)
+    Lst		l;	/* List to which to add the datum */
+    ClientData	d;	/* Datum to add */
+{
+    register LstNode	end;
+    
+    end = Lst_Last (l);
+    return (Lst_Append (l, end, d));
+}
diff --git a/usr.bin/make/lst.lib/lstAtFront.c b/usr.bin/make/lst.lib/lstAtFront.c
new file mode 100644
index 000000000000..58a235d2a0ed
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstAtFront.c
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstAtFront.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstAtFront.c --
+ *	Add a node at the front of the list
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_AtFront --
+ *	Place a piece of data at the front of a list
+ *
+ * Results:
+ *	SUCCESS or FAILURE
+ *
+ * Side Effects:
+ *	A new ListNode is created and stuck at the front of the list.
+ *	hence, firstPtr (and possible lastPtr) in the list are altered.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_AtFront (l, d)
+    Lst		l;
+    ClientData	d;
+{
+    register LstNode	front;
+    
+    front = Lst_First (l);
+    return (Lst_Insert (l, front, d));
+}
diff --git a/usr.bin/make/lst.lib/lstClose.c b/usr.bin/make/lst.lib/lstClose.c
new file mode 100644
index 000000000000..624e6c6dc3b4
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstClose.c
@@ -0,0 +1,77 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstClose.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstClose.c --
+ *	Close a list for sequential access.
+ *	The sequential functions access the list in a slightly different way.
+ *	CurPtr points to their idea of the current node in the list and they
+ *	access the list based on it. Because the list is circular, Lst_Next
+ *	and Lst_Prev will go around the list forever. Lst_IsAtEnd must be
+ *	used to determine when to stop.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Close --
+ *	Close a list which was opened for sequential access.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	The list is closed.
+ *
+ *-----------------------------------------------------------------------
+ */
+void
+Lst_Close (l)
+    Lst	    l;	  	/* The list to close */
+{
+    register List 	list = (List) l;
+    
+    if (LstValid(l) == TRUE) {
+	list->isOpen = FALSE;
+	list->atEnd = Unknown;
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstConcat.c b/usr.bin/make/lst.lib/lstConcat.c
new file mode 100644
index 000000000000..505d49f058ea
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstConcat.c
@@ -0,0 +1,174 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstConcat.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * listConcat.c --
+ *	Function to concatentate two lists.
+ */
+
+#include    "lstInt.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.
+ *	If LST_CONCLINK is specified, the second list is destroyed since
+ *	its pointers have been corrupted and the list is no longer useable.
+ *
+ * Results:
+ *	SUCCESS if all went well. FAILURE otherwise.
+ *
+ * Side Effects:
+ *	New elements are created and appended the the first list.
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Concat (l1, l2, flags)
+    Lst    	  	l1; 	/* The list to which l2 is to be appended */
+    Lst    	  	l2; 	/* The list to append to l1 */
+    int	   	  	flags;  /* LST_CONCNEW if LstNode's should be duplicated
+				 * LST_CONCLINK if should just be relinked */
+{
+    register ListNode  	ln;     /* original LstNode */
+    register ListNode  	nln;    /* new LstNode */
+    register ListNode  	last;   /* the last element in the list. Keeps
+				 * bookkeeping until the end */
+    register List 	list1 = (List)l1;
+    register List 	list2 = (List)l2;
+
+    if (!LstValid (l1) || !LstValid (l2)) {
+	return (FAILURE);
+    }
+
+    if (flags == LST_CONCLINK) {
+	if (list2->firstPtr != NilListNode) {
+	    /*
+	     * We set the nextPtr of the
+	     * last element of list two to be NIL to make the loop easier and
+	     * so we don't need an extra case should the first list turn
+	     * out to be non-circular -- the final element will already point
+	     * to NIL space and the first element will be untouched if it
+	     * existed before and will also point to NIL space if it didn't.
+	     */
+	    list2->lastPtr->nextPtr = NilListNode;
+	    /*
+	     * 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 != NilListNode) {
+ 		list1->lastPtr->nextPtr = list2->firstPtr;
+	    }
+	    list1->lastPtr = list2->lastPtr;
+	}
+	if (list1->isCirc && list1->firstPtr != NilListNode) {
+	    /*
+	     * If the first list is supposed to be circular and it is (now)
+	     * non-empty, we must make sure it's circular by linking the
+	     * first element to the last and vice versa
+	     */
+	    list1->firstPtr->prevPtr = list1->lastPtr;
+	    list1->lastPtr->nextPtr = list1->firstPtr;
+	}
+	free ((Address)l2);
+    } else if (list2->firstPtr != NilListNode) {
+	/*
+	 * We set the nextPtr of the last element of list 2 to be nil to make
+	 * the loop less difficult. The loop simply goes through the entire
+	 * second list creating new LstNodes and filling in the nextPtr, and
+	 * prevPtr to fit into l1 and its datum field from the
+	 * datum field of the corresponding element in l2. The 'last' node
+	 * follows the last of the new nodes along until the entire l2 has
+	 * been appended. Only then does the bookkeeping catch up with the
+	 * changes. During the first iteration of the loop, if 'last' is nil,
+	 * the first list must have been empty so the newly-created node is
+	 * made the first node of the list.
+	 */
+	list2->lastPtr->nextPtr = NilListNode;
+	for (last = list1->lastPtr, ln = list2->firstPtr;
+	     ln != NilListNode;
+	     ln = ln->nextPtr)
+	{
+	    PAlloc (nln, ListNode);
+	    nln->datum = ln->datum;
+	    if (last != NilListNode) {
+		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;
+
+	/*
+	 * The circularity of both list one and list two must be corrected
+	 * for -- list one because of the new nodes added to it; list two
+	 * because of the alteration of list2->lastPtr's nextPtr to ease the
+	 * above for loop.
+	 */
+	if (list1->isCirc) {
+	    list1->lastPtr->nextPtr = list1->firstPtr;
+	    list1->firstPtr->prevPtr = list1->lastPtr;
+	} else {
+	    last->nextPtr = NilListNode;
+	}
+
+	if (list2->isCirc) {
+	    list2->lastPtr->nextPtr = list2->firstPtr;
+	}
+    }
+
+    return (SUCCESS);
+}
+	
diff --git a/usr.bin/make/lst.lib/lstDatum.c b/usr.bin/make/lst.lib/lstDatum.c
new file mode 100644
index 000000000000..542898b29ae7
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstDatum.c
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstDatum.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstDatum.c --
+ *	Return the datum associated with a list node.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Datum --
+ *	Return the datum stored in the given node.
+ *
+ * Results:
+ *	The datum or (ick!) NIL if the node is invalid.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+ClientData
+Lst_Datum (ln)
+    LstNode	ln;
+{
+    if (ln != NILLNODE) {
+	return (((ListNode)ln)->datum);
+    } else {
+	return ((ClientData) NIL);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstDeQueue.c b/usr.bin/make/lst.lib/lstDeQueue.c
new file mode 100644
index 000000000000..921889ae910e
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstDeQueue.c
@@ -0,0 +1,81 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstDeQueue.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstDeQueue.c --
+ *	Remove the node and return its datum from the head of the list
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * 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) NIL if the list
+ *	is empty.
+ *
+ * Side Effects:
+ *	The head node is removed from the list.
+ *
+ *-----------------------------------------------------------------------
+ */
+ClientData
+Lst_DeQueue (l)
+    Lst	    	  l;
+{
+    ClientData	  rd;
+    register ListNode	tln;
+    
+    tln = (ListNode) Lst_First (l);
+    if (tln == NilListNode) {
+	return ((ClientData) NIL);
+    }
+    
+    rd = tln->datum;
+    if (Lst_Remove (l, (LstNode)tln) == FAILURE) {
+	return ((ClientData) NIL);
+    } else {
+	return (rd);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstDestroy.c b/usr.bin/make/lst.lib/lstDestroy.c
new file mode 100644
index 000000000000..3dedbf1c5379
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstDestroy.c
@@ -0,0 +1,98 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstDestroy.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstDestroy.c --
+ *	Nuke a list and all its resources
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * 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.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	The given list is freed in its entirety.
+ *
+ *-----------------------------------------------------------------------
+ */
+void
+Lst_Destroy (l, freeProc)
+    Lst	    	  	l;
+    register void	(*freeProc)();
+{
+    register ListNode	ln;
+    register ListNode	tln = NilListNode;
+    register List 	list = (List)l;
+    
+    if (l == NILLST || ! l) {
+	/*
+	 * Note the check for l == (Lst)0 to catch uninitialized static Lst's.
+	 * Gross, but useful.
+	 */
+	return;
+    }
+    
+    if (freeProc) {
+	for (ln = list->firstPtr;
+	     ln != NilListNode && tln != list->firstPtr;
+	     ln = tln) {
+		 tln = ln->nextPtr;
+		 (*freeProc) (ln->datum);
+		 free ((Address)ln);
+	}
+    } else {
+	for (ln = list->firstPtr;
+	     ln != NilListNode && tln != list->firstPtr;
+	     ln = tln) {
+		 tln = ln->nextPtr;
+		 free ((Address)ln);
+	}
+    }
+    
+    free ((Address)l);
+}
diff --git a/usr.bin/make/lst.lib/lstDupl.c b/usr.bin/make/lst.lib/lstDupl.c
new file mode 100644
index 000000000000..302bb30b866a
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstDupl.c
@@ -0,0 +1,98 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstDupl.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * listDupl.c --
+ *	Duplicate a list. This includes duplicating the individual
+ *	elements.
+ */
+
+#include    "lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Duplicate --
+ *	Duplicate an entire list. If a function to copy a ClientData is
+ *	given, the individual client elements will be duplicated as well.
+ *
+ * Results:
+ *	The new Lst structure or NILLST if failure.
+ *
+ * Side Effects:
+ *	A new list is created.
+ *-----------------------------------------------------------------------
+ */
+Lst
+Lst_Duplicate (l, copyProc)
+    Lst     	  l;	    	 /* the list to duplicate */
+    ClientData	  (*copyProc)(); /* A function to duplicate each ClientData */
+{
+    register Lst 	nl;
+    register ListNode  	ln;
+    register List 	list = (List)l;
+    
+    if (!LstValid (l)) {
+	return (NILLST);
+    }
+
+    nl = Lst_Init (list->isCirc);
+    if (nl == NILLST) {
+	return (NILLST);
+    }
+
+    ln = list->firstPtr;
+    while (ln != NilListNode) {
+	if (copyProc != NOCOPY) {
+	    if (Lst_AtEnd (nl, (*copyProc) (ln->datum)) == FAILURE) {
+		return (NILLST);
+	    }
+	} else if (Lst_AtEnd (nl, ln->datum) == FAILURE) {
+	    return (NILLST);
+	}
+
+	if (list->isCirc && ln == list->lastPtr) {
+	    ln = NilListNode;
+	} else {
+	    ln = ln->nextPtr;
+	}
+    }
+	
+    return (nl);
+}
diff --git a/usr.bin/make/lst.lib/lstEnQueue.c b/usr.bin/make/lst.lib/lstEnQueue.c
new file mode 100644
index 000000000000..14e36e3d0dbd
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstEnQueue.c
@@ -0,0 +1,73 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstEnQueue.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstEnQueue.c--
+ *	Treat the list as a queue and place a datum at its end
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_EnQueue --
+ *	Add the datum to the tail of the given list.
+ *
+ * Results:
+ *	SUCCESS or FAILURE as returned by Lst_Append.
+ *
+ * Side Effects:
+ *	the lastPtr field is altered all the time and the firstPtr field
+ *	will be altered if the list used to be empty.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_EnQueue (l, d)
+    Lst	    	  l;
+    ClientData	  d;
+{
+    if (LstValid (l) == FALSE) {
+	return (FAILURE);
+    }
+    
+    return (Lst_Append (l, Lst_Last(l), d));
+}
+
diff --git a/usr.bin/make/lst.lib/lstFind.c b/usr.bin/make/lst.lib/lstFind.c
new file mode 100644
index 000000000000..1efdc5458874
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstFind.c
@@ -0,0 +1,70 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstFind.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstFind.c --
+ *	Find a node on a list.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Find --
+ *	Find a node on the given list using the given comparison function
+ *	and the given datum.
+ *
+ * Results:
+ *	The found node or NILLNODE if none matches.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_Find (l, d, cProc)
+    Lst		l;
+    ClientData	d;
+    int		(*cProc)();
+{
+    return (Lst_FindFrom (l, Lst_First(l), d, cProc));
+}
+
diff --git a/usr.bin/make/lst.lib/lstFindFrom.c b/usr.bin/make/lst.lib/lstFindFrom.c
new file mode 100644
index 000000000000..e1da0337b909
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstFindFrom.c
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstFindFrom.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstFindFrom.c --
+ *	Find a node on a list from a given starting point. Used by Lst_Find.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_FindFrom --
+ *	Search for a node starting and ending with the given one on the
+ *	given list using the passed datum and comparison function to
+ *	determine when it has been found.
+ *
+ * Results:
+ *	The found node or NILLNODE
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_FindFrom (l, ln, d, cProc)
+    Lst		      	l;
+    register LstNode    ln;
+    register ClientData d;
+    register int	(*cProc)();
+{
+    register ListNode	tln;
+    Boolean		found = FALSE;
+    
+    if (!LstValid (l) || LstIsEmpty (l) || !LstNodeValid (ln, l)) {
+	return (NILLNODE);
+    }
+    
+    tln = (ListNode)ln;
+    
+    do {
+	if ((*cProc) (tln->datum, d) == 0) {
+	    found = TRUE;
+	    break;
+	} else {
+	    tln = tln->nextPtr;
+	}
+    } while (tln != (ListNode)ln && tln != NilListNode);
+    
+    if (found) {
+	return ((LstNode)tln);
+    } else {
+	return (NILLNODE);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstFirst.c b/usr.bin/make/lst.lib/lstFirst.c
new file mode 100644
index 000000000000..95e0893893d4
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstFirst.c
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstFirst.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstFirst.c --
+ *	Return the first node of a list
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_First --
+ *	Return the first node on the given list.
+ *
+ * Results:
+ *	The first node or NILLNODE if the list is empty.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_First (l)
+    Lst	l;
+{
+    if (!LstValid (l) || LstIsEmpty (l)) {
+	return (NILLNODE);
+    } else {
+	return ((LstNode)((List)l)->firstPtr);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstForEach.c b/usr.bin/make/lst.lib/lstForEach.c
new file mode 100644
index 000000000000..9fbdca597ea8
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstForEach.c
@@ -0,0 +1,72 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstForEach.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstForeach.c --
+ *	Perform a given function on all elements of a list.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_ForEach --
+ *	Apply the given function to each element of the given list. The
+ *	function should return 0 if Lst_ForEach should continue and non-
+ *	zero if it should abort.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Only those created by the passed-in function.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*VARARGS2*/
+void
+Lst_ForEach (l, proc, d)
+    Lst	    	  	l;
+    register int	(*proc)();
+    register ClientData	d;
+{
+    Lst_ForEachFrom(l, Lst_First(l), proc, d);
+}
+
diff --git a/usr.bin/make/lst.lib/lstForEachFrom.c b/usr.bin/make/lst.lib/lstForEachFrom.c
new file mode 100644
index 000000000000..f19357f79050
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstForEachFrom.c
@@ -0,0 +1,111 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstForEachFrom.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * lstForEachFrom.c --
+ *	Perform a given function on all elements of a list starting from
+ *	a given point.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_ForEachFrom --
+ *	Apply the given function to each element of the given list. The
+ *	function should return 0 if traversal should continue and non-
+ *	zero if it should abort. 
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	Only those created by the passed-in function.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*VARARGS2*/
+void
+Lst_ForEachFrom (l, ln, proc, d)
+    Lst	    	    	l;
+    LstNode    	  	ln;
+    register int	(*proc)();
+    register ClientData	d;
+{
+    register ListNode	tln = (ListNode)ln;
+    register List 	list = (List)l;
+    register ListNode	next;
+    Boolean 	    	done;
+    int     	    	result;
+    
+    if (!LstValid (list) || LstIsEmpty (list)) {
+	return;
+    }
+    
+    do {
+	/*
+	 * Take care of having the current element deleted out from under
+	 * us.
+	 */
+	
+	next = tln->nextPtr;
+	
+	(void) tln->useCount++;
+	result = (*proc) (tln->datum, d);
+	(void) tln->useCount--;
+
+	/*
+	 * We're done with the traversal if
+	 *  - nothing's been added after the current node and
+	 *  - the next node to examine is the first in the queue or
+	 *    doesn't exist.
+	 */
+	done = (next == tln->nextPtr &&
+		(next == NilListNode || next == list->firstPtr));
+	
+	next = tln->nextPtr;
+
+	if (tln->flags & LN_DELETED) {
+	    free((char *)tln);
+	}
+	tln = next;
+    } while (!result && !LstIsEmpty(list) && !done);
+    
+}
diff --git a/usr.bin/make/lst.lib/lstInit.c b/usr.bin/make/lst.lib/lstInit.c
new file mode 100644
index 000000000000..c548c7fd0306
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstInit.c
@@ -0,0 +1,76 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstInit.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * init.c --
+ *	Initialize a new linked list.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Init --
+ *	Create and initialize a new list.
+ *
+ * Results:
+ *	The created list.
+ *
+ * Side Effects:
+ *	A list is created, what else?
+ *
+ *-----------------------------------------------------------------------
+ */
+Lst
+Lst_Init(circ)
+    Boolean		circ;	/* TRUE if the list should be made circular */
+{
+    register List	nList;
+    
+    PAlloc (nList, List);
+    
+    nList->firstPtr = NilListNode;
+    nList->lastPtr = NilListNode;
+    nList->isOpen = FALSE;
+    nList->isCirc = circ;
+    nList->atEnd = Unknown;
+    
+    return ((Lst)nList);
+}
diff --git a/usr.bin/make/lst.lib/lstInsert.c b/usr.bin/make/lst.lib/lstInsert.c
new file mode 100644
index 000000000000..45577c4b040b
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstInsert.c
@@ -0,0 +1,113 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstInsert.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstInsert.c --
+ *	Insert a new datum before an old one
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Insert --
+ *	Insert a new node with the given piece of data before the given
+ *	node in the given list.
+ *
+ * Results:
+ *	SUCCESS or FAILURE.
+ *
+ * Side Effects:
+ *	the firstPtr field will be changed if ln is the first node in the
+ *	list.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Insert (l, ln, d)
+    Lst	    	  	l;	/* list to manipulate */
+    LstNode	  	ln;	/* node before which to insert d */
+    ClientData	  	d;	/* datum to be inserted */
+{
+    register ListNode	nLNode;	/* new lnode for d */
+    register ListNode	lNode = (ListNode)ln;
+    register List 	list = (List)l;
+
+
+    /*
+     * check validity of arguments
+     */
+    if (LstValid (l) && (LstIsEmpty (l) && ln == NILLNODE))
+	goto ok;
+    
+    if (!LstValid (l) || LstIsEmpty (l) || !LstNodeValid (ln, l)) {
+	return (FAILURE);
+    }
+    
+    ok:
+    PAlloc (nLNode, ListNode);
+    
+    nLNode->datum = d;
+    nLNode->useCount = nLNode->flags = 0;
+    
+    if (ln == NILLNODE) {
+	if (list->isCirc) {
+	    nLNode->prevPtr = nLNode->nextPtr = nLNode;
+	} else {
+	    nLNode->prevPtr = nLNode->nextPtr = NilListNode;
+	}
+	list->firstPtr = list->lastPtr = nLNode;
+    } else {
+	nLNode->prevPtr = lNode->prevPtr;
+	nLNode->nextPtr = lNode;
+	
+	if (nLNode->prevPtr != NilListNode) {
+	    nLNode->prevPtr->nextPtr = nLNode;
+	}
+	lNode->prevPtr = nLNode;
+	
+	if (lNode == list->firstPtr) {
+	    list->firstPtr = nLNode;
+	}
+    }
+    
+    return (SUCCESS);
+}
+	
diff --git a/usr.bin/make/lst.lib/lstInt.h b/usr.bin/make/lst.lib/lstInt.h
new file mode 100644
index 000000000000..0296558df3d3
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstInt.h
@@ -0,0 +1,110 @@
+/*
+ * 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.
+ *
+ *	@(#)lstInt.h	8.1 (Berkeley) 6/6/93
+ */
+
+/*-
+ * lstInt.h --
+ *	Internals for the list library
+ */
+#ifndef _LSTINT_H_
+#define _LSTINT_H_
+
+#include	  "lst.h"
+
+typedef struct ListNode {
+	struct ListNode	*prevPtr;   /* previous element in list */
+	struct ListNode	*nextPtr;   /* next in list */
+	short	    	useCount:8, /* Count of functions using the node.
+				     * node may not be deleted until count
+				     * goes to 0 */
+ 	    	    	flags:8;    /* Node status flags */
+	ClientData	datum;	    /* datum associated with this element */
+} *ListNode;
+/*
+ * Flags required for synchronization
+ */
+#define LN_DELETED  	0x0001      /* List node should be removed when done */
+
+#define NilListNode	((ListNode)-1)
+
+typedef enum {
+    Head, Middle, Tail, Unknown
+} Where;
+
+typedef struct	{
+	ListNode  	firstPtr; /* first node in list */
+	ListNode  	lastPtr;  /* last node in list */
+	Boolean	  	isCirc;	  /* true if the list should be considered
+				   * circular */
+/*
+ * fields for sequential access
+ */
+	Where	  	atEnd;	  /* Where in the list the last access was */
+	Boolean	  	isOpen;	  /* true if list has been Lst_Open'ed */
+	ListNode  	curPtr;	  /* current node, if open. NilListNode if
+				   * *just* opened */
+	ListNode  	prevPtr;  /* Previous node, if open. Used by
+				   * Lst_Remove */
+} *List;
+
+#define NilList	  	((List)-1)
+
+/*
+ * PAlloc (var, ptype) --
+ *	Allocate a pointer-typedef structure 'ptype' into the variable 'var'
+ */
+#define	PAlloc(var,ptype)	var = (ptype) malloc (sizeof (*var))
+
+/*
+ * LstValid (l) --
+ *	Return TRUE if the list l is valid
+ */
+#define LstValid(l)	(((Lst)l == NILLST) ? FALSE : TRUE)
+
+/*
+ * LstNodeValid (ln, l) --
+ *	Return TRUE if the LstNode ln is valid with respect to l
+ */
+#define LstNodeValid(ln, l)	((((LstNode)ln) == NILLNODE) ? FALSE : TRUE)
+
+/*
+ * LstIsEmpty (l) --
+ *	TRUE if the list l is empty.
+ */
+#define LstIsEmpty(l)	(((List)l)->firstPtr == NilListNode)
+
+#endif _LSTINT_H_
diff --git a/usr.bin/make/lst.lib/lstIsAtEnd.c b/usr.bin/make/lst.lib/lstIsAtEnd.c
new file mode 100644
index 000000000000..2a8fc2f56798
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstIsAtEnd.c
@@ -0,0 +1,81 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstIsAtEnd.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstIsAtEnd.c --
+ *	Tell if the current node is at the end of the list.
+ *	The sequential functions access the list in a slightly different way.
+ *	CurPtr points to their idea of the current node in the list and they
+ *	access the list based on it. Because the list is circular, Lst_Next
+ *	and Lst_Prev will go around the list forever. Lst_IsAtEnd must be
+ *	used to determine when to stop.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_IsAtEnd --
+ *	Return true if have reached the end of the given list.
+ *
+ * Results:
+ *	TRUE if at the end of the list (this includes the list not being
+ *	open or being invalid) or FALSE if not. We return TRUE if the list
+ *	is invalid or unopend so as to cause the caller to exit its loop
+ *	asap, the assumption being that the loop is of the form
+ *	    while (!Lst_IsAtEnd (l)) {
+ *	    	  ...
+ *	    }
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+Boolean
+Lst_IsAtEnd (l)
+    Lst	    l;
+{
+    register List list = (List) l;
+
+    return (!LstValid (l) || !list->isOpen ||
+	    (list->atEnd == Head) || (list->atEnd == Tail));
+}
+
diff --git a/usr.bin/make/lst.lib/lstIsEmpty.c b/usr.bin/make/lst.lib/lstIsEmpty.c
new file mode 100644
index 000000000000..c2a6509d6425
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstIsEmpty.c
@@ -0,0 +1,69 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstIsEmpty.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstIsEmpty.c --
+ *	A single function to decide if a list is empty
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_IsEmpty --
+ *	Return TRUE if the given list is empty.
+ *
+ * Results:
+ *	TRUE if the list is empty, FALSE otherwise.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *	A list is considered empty if its firstPtr == NilListNode (or if
+ *	the list itself is NILLIST).
+ *-----------------------------------------------------------------------
+ */
+Boolean
+Lst_IsEmpty (l)
+    Lst	l;
+{
+    return ( ! LstValid (l) || LstIsEmpty(l));
+}
+
diff --git a/usr.bin/make/lst.lib/lstLast.c b/usr.bin/make/lst.lib/lstLast.c
new file mode 100644
index 000000000000..176aafb8c211
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstLast.c
@@ -0,0 +1,71 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstLast.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstLast.c --
+ *	Return the last element of a list
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Last --
+ *	Return the last node on the list l.
+ *
+ * Results:
+ *	The requested node or NILLNODE if the list is empty.
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_Last (l)
+    Lst	    l;
+{
+    if (!LstValid(l) || LstIsEmpty (l)) {
+	return (NILLNODE);
+    } else {
+	return ((LstNode)((List)l)->lastPtr);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstMember.c b/usr.bin/make/lst.lib/lstMember.c
new file mode 100644
index 000000000000..23070b7d2f1f
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstMember.c
@@ -0,0 +1,69 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstMember.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * lstMember.c --
+ *	See if a given datum is on a given list.
+ */
+
+#include    "lstInt.h"
+
+LstNode
+Lst_Member (l, d)
+    Lst	    	  	l;
+    ClientData	  	d;
+{
+    List    	  	list = (List) l;
+    register ListNode	lNode;
+
+    lNode = list->firstPtr;
+    if (lNode == NilListNode) {
+	return NILLNODE;
+    }
+    
+    do {
+	if (lNode->datum == d) {
+	    return (LstNode)lNode;
+	}
+	lNode = lNode->nextPtr;
+    } while (lNode != NilListNode && lNode != list->firstPtr);
+
+    return NILLNODE;
+}
diff --git a/usr.bin/make/lst.lib/lstNext.c b/usr.bin/make/lst.lib/lstNext.c
new file mode 100644
index 000000000000..0745b1cffccb
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstNext.c
@@ -0,0 +1,114 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstNext.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstNext.c --
+ *	Return the next node for a list.
+ *	The sequential functions access the list in a slightly different way.
+ *	CurPtr points to their idea of the current node in the list and they
+ *	access the list based on it. Because the list is circular, Lst_Next
+ *	and Lst_Prev will go around the list forever. Lst_IsAtEnd must be
+ *	used to determine when to stop.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Next --
+ *	Return the next node for the given list.
+ *
+ * Results:
+ *	The next node or NILLNODE if the list has yet to be opened. Also
+ *	if the list is non-circular and the end has been reached, NILLNODE
+ *	is returned.
+ *
+ * Side Effects:
+ *	the curPtr field is updated.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_Next (l)
+    Lst	    	  l;
+{
+    register ListNode	tln;
+    register List 	list = (List)l;
+    
+    if ((LstValid (l) == FALSE) ||
+	(list->isOpen == FALSE)) {
+	    return (NILLNODE);
+    }
+    
+    list->prevPtr = list->curPtr;
+    
+    if (list->curPtr == NilListNode) {
+	if (list->atEnd == Unknown) {
+	    /*
+	     * If we're just starting out, atEnd will be Unknown.
+	     * Then we want to start this thing off in the right
+	     * direction -- at the start with atEnd being Middle.
+	     */
+	    list->curPtr = tln = list->firstPtr;
+	    list->atEnd = Middle;
+	} else {
+	    tln = NilListNode;
+	    list->atEnd = Tail;
+	}
+    } else {
+	tln = list->curPtr->nextPtr;
+	list->curPtr = tln;
+
+	if (tln == list->firstPtr || tln == NilListNode) {
+	    /*
+	     * If back at the front, then we've hit the end...
+	     */
+	    list->atEnd = Tail;
+	} else {
+	    /*
+	     * Reset to Middle if gone past first.
+	     */
+	    list->atEnd = Middle;
+	}
+    }
+    
+    return ((LstNode)tln);
+}
+
diff --git a/usr.bin/make/lst.lib/lstOpen.c b/usr.bin/make/lst.lib/lstOpen.c
new file mode 100644
index 000000000000..f1decd7e1941
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstOpen.c
@@ -0,0 +1,81 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstOpen.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstOpen.c --
+ *	Open a list for sequential access. The sequential functions access the
+ *	list in a slightly different way. CurPtr points to their idea of the
+ *	current node in the list and they access the list based on it.
+ *	If the list is circular, Lst_Next and Lst_Prev will go around
+ *	the list forever. Lst_IsAtEnd must be used to determine when to stop.
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Open --
+ *	Open a list for sequential access. A list can still be searched,
+ *	etc., without confusing these functions.
+ *
+ * Results:
+ *	SUCCESS or FAILURE.
+ *
+ * Side Effects:
+ *	isOpen is set TRUE and curPtr is set to NilListNode so the
+ *	other sequential functions no it was just opened and can choose
+ *	the first element accessed based on this.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Open (l)
+	register Lst	l;
+{
+	if (LstValid (l) == FALSE) {
+		return (FAILURE);
+	}
+	((List) l)->isOpen = TRUE;
+	((List) l)->atEnd = LstIsEmpty (l) ? Head : Unknown;
+	((List) l)->curPtr = NilListNode;
+
+	return (SUCCESS);
+}
+
diff --git a/usr.bin/make/lst.lib/lstRemove.c b/usr.bin/make/lst.lib/lstRemove.c
new file mode 100644
index 000000000000..48a4c003cdc3
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstRemove.c
@@ -0,0 +1,131 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstRemove.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstRemove.c --
+ *	Remove an element from a list
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Remove --
+ *	Remove the given node from the given list.
+ *
+ * Results:
+ *	SUCCESS or FAILURE.
+ *
+ * Side Effects:
+ *	The list's firstPtr will be set to NilListNode 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.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Remove (l, ln)
+    Lst	    	  	l;
+    LstNode	  	ln;
+{
+    register List 	list = (List) l;
+    register ListNode	lNode = (ListNode) ln;
+
+    if (!LstValid (l) ||
+	!LstNodeValid (ln, l)) {
+	    return (FAILURE);
+    }
+    
+    /*
+     * unlink it from the list
+     */
+    if (lNode->nextPtr != NilListNode) {
+	lNode->nextPtr->prevPtr = lNode->prevPtr;
+    }
+    if (lNode->prevPtr != NilListNode) {
+	lNode->prevPtr->nextPtr = lNode->nextPtr;
+    }
+    
+    /*
+     * if either the firstPtr or lastPtr of the list point to this node,
+     * adjust them accordingly
+     */
+    if (list->firstPtr == lNode) {
+	list->firstPtr = lNode->nextPtr;
+    }
+    if (list->lastPtr == lNode) {
+	list->lastPtr = lNode->prevPtr;
+    }
+
+    /*
+     * Sequential access stuff. If the node we're removing is the current
+     * node in the list, reset the current node to the previous one. If the
+     * previous one was non-existent (prevPtr == NilListNode), we set the
+     * end to be Unknown, since it is.
+     */
+    if (list->isOpen && (list->curPtr == lNode)) {
+	list->curPtr = list->prevPtr;
+	if (list->curPtr == NilListNode) {
+	    list->atEnd = Unknown;
+	}
+    }
+
+    /*
+     * the only way firstPtr can still point to ln is if ln is the last
+     * node on the list (the list is circular, so lNode->nextptr == lNode in
+     * this case). The list is, therefore, empty and is marked as such
+     */
+    if (list->firstPtr == lNode) {
+	list->firstPtr = NilListNode;
+    }
+    
+    /*
+     * note that the datum is unmolested. The caller must free it as
+     * necessary and as expected.
+     */
+    if (lNode->useCount == 0) {
+	free ((Address)ln);
+    } else {
+	lNode->flags |= LN_DELETED;
+    }
+    
+    return (SUCCESS);
+}
+
diff --git a/usr.bin/make/lst.lib/lstReplace.c b/usr.bin/make/lst.lib/lstReplace.c
new file mode 100644
index 000000000000..344631a17e53
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstReplace.c
@@ -0,0 +1,73 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstReplace.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstReplace.c --
+ *	Replace the datum in a node with a new datum
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Replace --
+ *	Replace the datum in the given node with the new datum
+ *
+ * Results:
+ *	SUCCESS or FAILURE.
+ *
+ * Side Effects:
+ *	The datum field fo the node is altered.
+ *
+ *-----------------------------------------------------------------------
+ */
+ReturnStatus
+Lst_Replace (ln, d)
+    register LstNode	ln;
+    ClientData	  	d;
+{
+    if (ln == NILLNODE) {
+	return (FAILURE);
+    } else {
+	((ListNode) ln)->datum = d;
+	return (SUCCESS);
+    }
+}
+
diff --git a/usr.bin/make/lst.lib/lstSucc.c b/usr.bin/make/lst.lib/lstSucc.c
new file mode 100644
index 000000000000..06b354d9a030
--- /dev/null
+++ b/usr.bin/make/lst.lib/lstSucc.c
@@ -0,0 +1,73 @@
+/*
+ * 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.
+ */
+
+#ifndef lint
+static char sccsid[] = "@(#)lstSucc.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*-
+ * LstSucc.c --
+ *	return the successor to a given node
+ */
+
+#include	"lstInt.h"
+
+/*-
+ *-----------------------------------------------------------------------
+ * Lst_Succ --
+ *	Return the sucessor to the given node on its list.
+ *
+ * Results:
+ *	The successor of the node, if it exists (note that on a circular
+ *	list, if the node is the only one in the list, it is its own
+ *	successor).
+ *
+ * Side Effects:
+ *	None.
+ *
+ *-----------------------------------------------------------------------
+ */
+LstNode
+Lst_Succ (ln)
+    LstNode	ln;
+{
+    if (ln == NILLNODE) {
+	return (NILLNODE);
+    } else {
+	return ((LstNode) ((ListNode) ln)->nextPtr);
+    }
+}
+