Make paths an explicite datatype instead of using the generic Lst.

A Path is now a TAILQ of PathElements each of which just points to
a reference counted directory. Rename all functions dealing with Paths
from the Dir_ prefix to a Path_ prefix.

10 files changed, 273 insertions, 293 deletions

diff --git a/usr.bin/make/arch.c b/usr.bin/make/arch.c
index 6cc89b7..9b993df 100644
--- a/usr.bin/make/arch.c
+++ b/usr.bin/make/arch.c
@@ -336,7 +336,7 @@ Arch_ParseArchive(char **linePtr, Lst *nodeLst, GNode *ctxt)
 
 			nameBuf = emalloc(sz);
 
-			Dir_Expand(memName, &dirSearchPath, &members);
+			Path_Expand(memName, &dirSearchPath, &members);
 			while (!Lst_IsEmpty(&members)) {
 				member = Lst_DeQueue(&members);
 				nsz = strlen(libName) + strlen(member) + 3;
@@ -1054,7 +1054,7 @@ Arch_MemMTime(GNode *gn)
  *-----------------------------------------------------------------------
  */
 void
-Arch_FindLib(GNode *gn, Lst *path)
+Arch_FindLib(GNode *gn, struct Path *path)
 {
 	char	*libName;	/* file name for archive */
 	size_t	sz;
@@ -1063,7 +1063,7 @@ Arch_FindLib(GNode *gn, Lst *path)
 	libName = emalloc(sz);
 	snprintf(libName, sz, "lib%s.a", &gn->name[2]);
 
-	gn->path = Dir_FindFile(libName, path);
+	gn->path = Path_FindFile(libName, path);
 
 	free(libName);
 
diff --git a/usr.bin/make/arch.h b/usr.bin/make/arch.h
index 3b95563..d3f4ba9 100644
--- a/usr.bin/make/arch.h
+++ b/usr.bin/make/arch.h
@@ -45,13 +45,14 @@
 
 struct GNode;
 struct Lst;
+struct Path;
 
 ReturnStatus Arch_ParseArchive(char **, struct Lst *, struct GNode *);
 void Arch_Touch(struct GNode *);
 void Arch_TouchLib(struct GNode *);
 int Arch_MTime(struct GNode *);
 int Arch_MemMTime(struct GNode *);
-void Arch_FindLib(struct GNode *, struct Lst *);
+void Arch_FindLib(struct GNode *, struct Path *);
 Boolean Arch_LibOODate(struct GNode *);
 void Arch_Init(void);
 
diff --git a/usr.bin/make/cond.c b/usr.bin/make/cond.c
index 235203f..22dc975 100644
--- a/usr.bin/make/cond.c
+++ b/usr.bin/make/cond.c
@@ -356,7 +356,7 @@ CondDoExists(int argLen, char *arg)
     char    *path;
 
     arg[argLen] = '\0';
-    path = Dir_FindFile(arg, &dirSearchPath);
+    path = Path_FindFile(arg, &dirSearchPath);
     if (path != NULL) {
 	result = TRUE;
 	free(path);
diff --git a/usr.bin/make/dir.c b/usr.bin/make/dir.c
index fb6aa9d..c66b2bf 100644
--- a/usr.bin/make/dir.c
+++ b/usr.bin/make/dir.c
@@ -54,10 +54,10 @@ __FBSDID("$FreeBSD$");
  *	Dir_HasWildcards Returns TRUE if the name given it needs to
  *			be wildcard-expanded.
  *
- *	Dir_Expand	Given a pattern and a path, return a Lst of names
+ *	Path_Expand	Given a pattern and a path, return a Lst of names
  *			which match the pattern on the search path.
  *
- *	Dir_FindFile	Searches for a file on a given search path.
+ *	Path_FindFile	Searches for a file on a given search path.
  *			If it exists, the entire path is returned.
  *			Otherwise NULL is returned.
  *
@@ -65,7 +65,7 @@ __FBSDID("$FreeBSD$");
  *			is searched for along the default search path.
  *			The path and mtime fields of the node are filled in.
  *
- *	Dir_AddDir	Add a directory to a search path.
+ *	Path_AddDir	Add a directory to a search path.
  *
  *	Dir_MakeFlags	Given a search path and a command flag, create
  *			a string with each of the directories in the path
@@ -104,7 +104,7 @@ __FBSDID("$FreeBSD$");
 #include "util.h"
 
 /*
- *	A search path consists of a Lst of Dir structures. A Dir structure
+ *	A search path consists of a list of Dir structures. A Dir structure
  *	has in it the name of the directory and a hash table of all the files
  *	in the directory. This is used to cut down on the number of system
  *	calls necessary to find implicit dependents and their like. Since
@@ -113,7 +113,7 @@ __FBSDID("$FreeBSD$");
  *	hampers the style of some makefiles, they must be changed.
  *
  *	A list of all previously-read directories is kept in the
- *	openDirectories Lst. This list is checked first before a directory
+ *	openDirectories list. This list is checked first before a directory
  *	is opened.
  *
  *	The need for the caching of whole directories is brought about by
@@ -163,7 +163,7 @@ __FBSDID("$FreeBSD$");
  *
  *	Another data structure maintained by this module is an mtime
  *	cache used when the searching of cached directories fails to find
- *	a file. In the past, Dir_FindFile would simply perform an access()
+ *	a file. In the past, Path_FindFile would simply perform an access()
  *	call in such a case to determine if the file could be found using
  *	just the name given. When this hit, however, all that was gained
  *	was the knowledge that the file existed. Given that an access() is
@@ -178,14 +178,24 @@ typedef struct Dir {
 	int	refCount;	/* No. of paths with this directory */
 	int	hits;		/* No. of times a file has been found here */
 	Hash_Table files;	/* Hash table of files in directory */
+	TAILQ_ENTRY(Dir) link;	/* allDirs link */
 } Dir;
 
+/*
+ * A path is a list of pointers to directories. These directories are
+ * reference counted so a directory can be on more than one path.
+ */
+struct PathElement {
+	struct Dir	*dir;	/* pointer to the directory */
+	TAILQ_ENTRY(PathElement) link;	/* path link */
+};
 
 /* main search path */
-Lst dirSearchPath = Lst_Initializer(dirSearchPath);
+struct Path dirSearchPath = TAILQ_HEAD_INITIALIZER(dirSearchPath);
 
 /* the list of all open directories */
-static Lst openDirectories = Lst_Initializer(openDirectories);
+static TAILQ_HEAD(, Dir) openDirectories =
+    TAILQ_HEAD_INITIALIZER(openDirectories);
 
 /*
  * Variables for gathering statistics on the efficiency of the hashing
@@ -198,7 +208,7 @@ static int bigmisses;	/* Sought by itself */
 
 static Dir *dot;	    /* contents of current directory */
 
-/* Results of doing a last-resort stat in Dir_FindFile --
+/* Results of doing a last-resort stat in Path_FindFile --
  * if we have to go to the system to find the file, we might as well
  * have its mtime on record.
  * XXX: If this is done way early, there's a chance other rules will
@@ -242,12 +252,10 @@ Dir_Init(void)
 void
 Dir_InitDot(void)
 {
-	LstNode *ln;
 
-	Dir_AddDir(&openDirectories, ".");
-	if ((ln = Lst_Last(&openDirectories)) == NULL)
+	dot = Path_AddDir(NULL, ".");
+	if (dot == NULL)
 		err(1, "cannot open current directory");
-	dot = Lst_Datum(ln);
 
 	/*
 	 * We always need to have dot around, so we increment its
@@ -367,7 +375,8 @@ DirMatchFiles(const char *pattern, const Dir *p, Lst *expansions)
  *-----------------------------------------------------------------------
  */
 static void
-DirExpandCurly(const char *word, const char *brace, Lst *path, Lst *expansions)
+DirExpandCurly(const char *word, const char *brace, struct Path *path,
+    Lst *expansions)
 {
 	const char *end;	/* Character after the closing brace */
 	const char *cp;		/* Current position in brace clause */
@@ -434,7 +443,7 @@ DirExpandCurly(const char *word, const char *brace, Lst *path, Lst *expansions)
 			case '?':
 			case '{':
 			case '[':
-				Dir_Expand(file, path, expansions);
+				Path_Expand(file, path, expansions);
 				goto next;
 			default:
 				break;
@@ -471,12 +480,12 @@ DirExpandCurly(const char *word, const char *brace, Lst *path, Lst *expansions)
  *-----------------------------------------------------------------------
  */
 static void
-DirExpandInt(const char *word, const Lst *path, Lst *expansions)
+DirExpandInt(const char *word, const struct Path *path, Lst *expansions)
 {
-	LstNode *ln;	    /* Current node */
+	struct PathElement *pe;
 
-	LST_FOREACH(ln, path)
-		DirMatchFiles(word, (Dir *)Lst_Datum(ln), expansions);
+	TAILQ_FOREACH(pe, path, link)
+		DirMatchFiles(word, pe->dir, expansions);
 }
 
 /*-
@@ -494,7 +503,7 @@ DirExpandInt(const char *word, const Lst *path, Lst *expansions)
  *-----------------------------------------------------------------------
  */
 void
-Dir_Expand(char *word, Lst *path, Lst *expansions)
+Path_Expand(char *word, struct Path *path, Lst *expansions)
 {
 	LstNode *ln;
 	char *cp;
@@ -542,12 +551,12 @@ Dir_Expand(char *word, Lst *path, Lst *expansions)
 					 */
 					sc = cp[1];
 					cp[1] = '\0';
-					dirpath = Dir_FindFile(word, path);
+					dirpath = Path_FindFile(word, path);
 					cp[1] = sc;
 					/*
 					 * dirpath is null if can't find the
 					 * leading component
-					 * XXX: Dir_FindFile won't find internal
+					 * XXX: Path_FindFile won't find internal
 					 * components. i.e. if the path contains
 					 * ../Etc/Object and we're looking for
 					 * Etc, * it won't be found. Ah well.
@@ -557,14 +566,15 @@ Dir_Expand(char *word, Lst *path, Lst *expansions)
 						char *dp =
 						    &dirpath[strlen(dirpath)
 						    - 1];
-						Lst tp = Lst_Initializer(tp);
+						struct Path tp =
+						    TAILQ_HEAD_INITIALIZER(tp);
 
 						if (*dp == '/')
 							*dp = '\0';
-						Dir_AddDir(&tp, dirpath);
+						Path_AddDir(&tp, dirpath);
 						DirExpandInt(cp + 1, &tp,
 						    expansions);
-						Lst_Destroy(&tp, NOFREE);
+						Path_Clear(&tp);
 					}
 				} else {
 					/*
@@ -598,9 +608,8 @@ Dir_Expand(char *word, Lst *path, Lst *expansions)
 	}
 }
 
-/*-
- *-----------------------------------------------------------------------
- * Dir_FindFile  --
+/**
+ * Path_FindFile
  *	Find the file with the given name along the given search path.
  *
  * Results:
@@ -614,16 +623,14 @@ Dir_Expand(char *word, Lst *path, Lst *expansions)
  *	already on the search path), its directory is added to the end
  *	of the path on the assumption that there will be more files in
  *	that directory later on. Sometimes this is true. Sometimes not.
- *-----------------------------------------------------------------------
  */
 char *
-Dir_FindFile(char *name, Lst *path)
+Path_FindFile(char *name, struct Path *path)
 {
 	char *p1;		/* pointer into p->name */
 	char *p2;		/* pointer into name */
-	LstNode *ln;		/* a list element */
 	char *file;		/* the current filename to check */
-	Dir *p;			/* current path member */
+	const struct PathElement *pe;	/* current path member */
 	char *cp;		/* final component of the name */
 	Boolean hasSlash;	/* true if 'name' contains a / */
 	struct stat stb;	/* Buffer for stat, if necessary */
@@ -665,10 +672,9 @@ Dir_FindFile(char *name, Lst *path)
 	 * and return the resulting string. If we don't find any such thing,
 	 * we go on to phase two...
 	 */
-	LST_FOREACH(ln, path) {
-		p = Lst_Datum(ln);
-		DEBUGF(DIR, ("%s...", p->name));
-		if (Hash_FindEntry(&p->files, cp) != NULL) {
+	TAILQ_FOREACH(pe, path, link) {
+		DEBUGF(DIR, ("%s...", pe->dir->name));
+		if (Hash_FindEntry(&pe->dir->files, cp) != NULL) {
 			DEBUGF(DIR, ("here..."));
 			if (hasSlash) {
 				/*
@@ -681,22 +687,22 @@ Dir_FindFile(char *name, Lst *path)
 				 * part of one of the components of p
 				 * along with all the rest of them (*p1 != '/').
 				 */
-				p1 = p->name + strlen(p->name) - 1;
+				p1 = pe->dir->name + strlen(pe->dir->name) - 1;
 				p2 = cp - 2;
-				while (p2 >= name && p1 >= p->name &&
+				while (p2 >= name && p1 >= pe->dir->name &&
 				    *p1 == *p2) {
 					p1 -= 1; p2 -= 1;
 				}
-				if (p2 >= name || (p1 >= p->name &&
+				if (p2 >= name || (p1 >= pe->dir->name &&
 				    *p1 != '/')) {
 					DEBUGF(DIR, ("component mismatch -- "
 					    "continuing..."));
 					continue;
 				}
 			}
-			file = str_concat(p->name, cp, STR_ADDSLASH);
+			file = str_concat(pe->dir->name, cp, STR_ADDSLASH);
 			DEBUGF(DIR, ("returning %s\n", file));
-			p->hits += 1;
+			pe->dir->hits += 1;
 			hits += 1;
 			return (file);
 		} else if (hasSlash) {
@@ -706,7 +712,7 @@ Dir_FindFile(char *name, Lst *path)
 			 * current search directory, we assume the file
 			 * doesn't exist and return NULL.
 			 */
-			for (p1 = p->name, p2 = name; *p1 && *p1 == *p2;
+			for (p1 = pe->dir->name, p2 = name; *p1 && *p1 == *p2;
 			    p1++, p2++)
 				continue;
 			if (*p1 == '\0' && p2 == cp - 1) {
@@ -744,10 +750,10 @@ Dir_FindFile(char *name, Lst *path)
 		Boolean	checkedDot = FALSE;
 
 		DEBUGF(DIR, ("failed. Trying subdirectories..."));
-		LST_FOREACH(ln, path) {
-			p = Lst_Datum(ln);
-			if (p != dot) {
-				file = str_concat(p->name, name, STR_ADDSLASH);
+		TAILQ_FOREACH(pe, path, link) {
+			if (pe->dir != dot) {
+				file = str_concat(pe->dir->name,
+				    name, STR_ADDSLASH);
 			} else {
 				/*
 				 * Checking in dot -- DON'T put a leading ./
@@ -765,7 +771,7 @@ Dir_FindFile(char *name, Lst *path)
 				 * We've found another directory to search. We
 				 * know there's a slash in 'file' because we put
 				 * one there. We nuke it after finding it and
-				 * call Dir_AddDir to add this new directory
+				 * call Path_AddDir to add this new directory
 				 * onto the existing search path. Once that's
 				 * done, we restore the slash and triumphantly
 				 * return the file name, knowing that should a
@@ -776,7 +782,7 @@ Dir_FindFile(char *name, Lst *path)
 				 */
 				cp = strrchr(file, '/');
 				*cp = '\0';
-				Dir_AddDir(path, file);
+				Path_AddDir(path, file);
 				*cp = '/';
 
 				/*
@@ -828,17 +834,15 @@ Dir_FindFile(char *name, Lst *path)
 	 */
 #ifdef notdef
 	cp[-1] = '\0';
-	Dir_AddDir(path, name);
+	Path_AddDir(path, name);
 	cp[-1] = '/';
 
 	bigmisses += 1;
-	ln = Lst_Last(path);
-	if (ln == NULL)
+	pe = TAILQ_LAST(path, Path);
+	if (pe == NULL)
 		return (NULL);
 
-	p = Lst_Datum(ln);
-
-	if (Hash_FindEntry(&p->files, cp) != NULL) {
+	if (Hash_FindEntry(&pe->dir->files, cp) != NULL) {
 		return (estrdup(name));
 
 	return (NULL);
@@ -889,7 +893,7 @@ Dir_MTime(GNode *gn)
 		return (Arch_MTime(gn));
 
 	else if (gn->path == NULL)
-		fullName = Dir_FindFile(gn->name, &dirSearchPath);
+		fullName = Path_FindFile(gn->name, &dirSearchPath);
 	else
 		fullName = gn->path;
 
@@ -926,7 +930,7 @@ Dir_MTime(GNode *gn)
 
 /*-
  *-----------------------------------------------------------------------
- * Dir_AddDir --
+ * Path_AddDir --
  *	Add the given name to the end of the given path.
  *
  * Results:
@@ -937,93 +941,109 @@ Dir_MTime(GNode *gn)
  *	read and hashed.
  *-----------------------------------------------------------------------
  */
-void
-Dir_AddDir(Lst *path, const char *name)
+struct Dir *
+Path_AddDir(struct Path *path, const char *name)
 {
-	LstNode *ln;		/* node in case Dir structure is found */
-	Dir *p;			/* pointer to new Path structure */
-	DIR *d;			/* for reading directory */
+	Dir *d;			/* pointer to new Path structure */
+	DIR *dir;		/* for reading directory */
+	struct PathElement *pe;
 	struct dirent *dp;	/* entry in directory */
 
-	LST_FOREACH(ln, &openDirectories)
-		if (strcmp(((const Dir *)Lst_Datum(ln))->name, name) == 0)
-			break;
-	if (ln != NULL) {
-		p = Lst_Datum(ln);
-		if (Lst_Member(path, p) == NULL) {
-			p->refCount += 1;
-			Lst_AtEnd(path, p);
+	/* check whether we know this directory */
+	TAILQ_FOREACH(d, &openDirectories, link) {
+		if (strcmp(d->name, name) == 0) {
+			/* Found it. */
+			if (path == NULL)
+				return (d);
+
+			/* Check whether its already on the path. */
+			TAILQ_FOREACH(pe, path, link) {
+				if (pe->dir == d)
+					return (d);
+			}
+			/* Add it to the path */
+			d->refCount += 1;
+			pe = emalloc(sizeof(*pe));
+			pe->dir = d;
+			TAILQ_INSERT_TAIL(path, pe, link);
+			return (d);
 		}
-	} else {
-		DEBUGF(DIR, ("Caching %s...", name));
+	}
+
+	DEBUGF(DIR, ("Caching %s...", name));
+
+	if ((dir = opendir(name)) == NULL) {
+		DEBUGF(DIR, (" cannot open\n"));
+		return (NULL);
+	}
 
-		if ((d = opendir(name)) != NULL) {
-			p = emalloc(sizeof(Dir));
-			p->name = estrdup(name);
-			p->hits = 0;
-			p->refCount = 1;
-			Hash_InitTable(&p->files, -1);
+	d = emalloc(sizeof(*d));
+	d->name = estrdup(name);
+	d->hits = 0;
+	d->refCount = 1;
+	Hash_InitTable(&d->files, -1);
 
-			while ((dp = readdir(d)) != NULL) {
+	while ((dp = readdir(dir)) != NULL) {
 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define	for d_fileno */
-				/*
-				 * The sun directory library doesn't check for
-				 * a 0 inode (0-inode slots just take up space),
-				 * so we have to do it ourselves.
-				 */
-				if (dp->d_fileno == 0)
-					continue;
+		/*
+		 * The sun directory library doesn't check for
+		 * a 0 inode (0-inode slots just take up space),
+		 * so we have to do it ourselves.
+		 */
+		if (dp->d_fileno == 0)
+			continue;
 #endif /* sun && d_ino */
 
-				/* Skip the '.' and '..' entries by checking
-				 * for them specifically instead of assuming
-				 * readdir() reuturns them in that order when
-				 * first going through a directory.  This is
-				 * needed for XFS over NFS filesystems since
-				 * SGI does not guarantee that these are the
-				 * first two entries returned from readdir().
-				 */
-				if (ISDOT(dp->d_name) || ISDOTDOT(dp->d_name))
-					continue;
+		/* Skip the '.' and '..' entries by checking
+		 * for them specifically instead of assuming
+		 * readdir() reuturns them in that order when
+		 * first going through a directory.  This is
+		 * needed for XFS over NFS filesystems since
+		 * SGI does not guarantee that these are the
+		 * first two entries returned from readdir().
+		 */
+		if (ISDOT(dp->d_name) || ISDOTDOT(dp->d_name))
+			continue;
 
-				Hash_CreateEntry(&p->files, dp->d_name,
-				    (Boolean *)NULL);
-			}
-			closedir(d);
-			Lst_AtEnd(&openDirectories, p);
-			if (path != &openDirectories)
-				Lst_AtEnd(path, p);
-		}
-		DEBUGF(DIR, ("done\n"));
+		Hash_CreateEntry(&d->files, dp->d_name, (Boolean *)NULL);
+	}
+	closedir(dir);
+
+	if (path != NULL) {
+		/* Add it to the path */
+		d->refCount += 1;
+		pe = emalloc(sizeof(*pe));
+		pe->dir = d;
+		TAILQ_INSERT_TAIL(path, pe, link);
 	}
+
+	/* Add to list of all directories */
+	TAILQ_INSERT_TAIL(&openDirectories, d, link);
+
+	DEBUGF(DIR, ("done\n"));
+
+	return (d);
 }
 
-/*-
- *-----------------------------------------------------------------------
- * Dir_CopyDir --
- *	Callback function for duplicating a search path via Lst_Duplicate.
- *	Ups the reference count for the directory.
- *
- * Results:
- *	Returns the Dir it was given.
- *
- * Side Effects:
- *	The refCount of the path is incremented.
- *
- *-----------------------------------------------------------------------
+/**
+ * Path_Duplicate
+ *	Duplicate a path. Ups the reference count for the directories.
  */
-void *
-Dir_CopyDir(void *p)
+void
+Path_Duplicate(struct Path *dst, const struct Path *src)
 {
+	struct PathElement *ped, *pes;
 
-	((Dir *)p)->refCount += 1;
-
-	return (p);
+	TAILQ_FOREACH(pes, src, link) {
+		ped = emalloc(sizeof(*ped));
+		ped->dir = pes->dir;
+		ped->dir->refCount++;
+		TAILQ_INSERT_TAIL(dst, ped, link);
+	}
 }
 
-/*-
- *-----------------------------------------------------------------------
- * Dir_MakeFlags --
+/**
+ * Path_MakeFlags
  *	Make a string by taking all the directories in the given search
  *	path and preceding them by the given flag. Used by the suffix
  *	module to create variables for compilers based on suffix search
@@ -1033,25 +1053,19 @@ Dir_CopyDir(void *p)
  *	The string mentioned above. Note that there is no space between
  *	the given flag and each directory. The empty string is returned if
  *	Things don't go well.
- *
- * Side Effects:
- *	None
- *-----------------------------------------------------------------------
  */
 char *
-Dir_MakeFlags(const char *flag, const Lst *path)
+Path_MakeFlags(const char *flag, const struct Path *path)
 {
 	char *str;	/* the string which will be returned */
 	char *tstr;	/* the current directory preceded by 'flag' */
 	char *nstr;
-	LstNode *ln;	/* the node of the current directory */
-	Dir *p;		/* the structure describing the current directory */
+	const struct PathElement *pe;
 
 	str = estrdup("");
 
-	LST_FOREACH(ln, path) {
-		p = Lst_Datum(ln);
-		tstr = str_concat(flag, p->name, 0);
+	TAILQ_FOREACH(pe, path, link) {
+		tstr = str_concat(flag, pe->dir->name, 0);
 		nstr = str_concat(str, tstr, STR_ADDSPACE);
 		free(str);
 		free(tstr);
@@ -1061,91 +1075,55 @@ Dir_MakeFlags(const char *flag, const Lst *path)
 	return (str);
 }
 
-/*-
- *-----------------------------------------------------------------------
- * Dir_Destroy --
- *	Nuke a directory descriptor, if possible. Callback procedure
- *	for the suffixes module when destroying a search path.
- *
- * Results:
- *	None.
- *
- * Side Effects:
- *	If no other path references this directory (refCount == 0),
- *	the Dir and all its data are freed.
+/**
+ * Path_Clear
  *
- *-----------------------------------------------------------------------
+ *	Destroy a path. This decrements the reference counts of all
+ *	directories of this path and, if a reference count goes 0,
+ *	destroys the directory object.
  */
 void
-Dir_Destroy(void *pp)
+Path_Clear(struct Path *path)
 {
-	Dir *p = pp;
-
-	p->refCount -= 1;
-
-	if (p->refCount == 0) {
-		LstNode *ln;
-
-		if ((ln = Lst_Member(&openDirectories, p)) != NULL)
-			Lst_Remove(&openDirectories, ln);
-
-		Hash_DeleteTable(&p->files);
-		free(p->name);
-		free(p);
+	struct PathElement *pe;
+
+	while ((pe = TAILQ_FIRST(path)) != NULL) {
+		pe->dir->refCount--;
+		TAILQ_REMOVE(path, pe, link);
+		if (pe->dir->refCount == 0) {
+			TAILQ_REMOVE(&openDirectories, pe->dir, link);
+			Hash_DeleteTable(&pe->dir->files);
+			free(pe->dir->name);
+			free(pe->dir);
+		}
+		free(pe);
 	}
 }
 
-/*-
- *-----------------------------------------------------------------------
- * Dir_ClearPath --
- *	Clear out all elements of the given search path. This is different
- *	from destroying the list, notice.
- *
- * Results:
- *	None.
+/**
+ * Path_Concat
  *
- * Side Effects:
- *	The path is set to the empty list.
- *
- *-----------------------------------------------------------------------
- */
-void
-Dir_ClearPath(Lst *path)
-{
-	Dir *p;
-
-	while (!Lst_IsEmpty(path)) {
-		p = Lst_DeQueue(path);
-		Dir_Destroy(p);
-	}
-}
-
-
-/*-
- *-----------------------------------------------------------------------
- * Dir_Concat --
  *	Concatenate two paths, adding the second to the end of the first.
- *	Makes sure to avoid duplicates.
- *
- * Results:
- *	None
+ *	Make sure to avoid duplicates.
  *
  * Side Effects:
  *	Reference counts for added dirs are upped.
- *
- *-----------------------------------------------------------------------
  */
 void
-Dir_Concat(Lst *path1, Lst *path2)
+Path_Concat(struct Path *path1, const struct Path *path2)
 {
-	LstNode *ln;
-	Dir *p;
+	struct PathElement *p1, *p2;
 
-	LST_FOREACH(ln, path2) {
-		p = Lst_Datum(ln);
-		if (Lst_Member(path1, p) == NULL) {
-			p->refCount += 1;
-			Lst_AtEnd(path1, p);
+	TAILQ_FOREACH(p2, path2, link) {
+		TAILQ_FOREACH(p1, path1, link) {
+			if (p1->dir == p2->dir)
+				break;
+		}
+		if (p1 == NULL) {
+			p1 = emalloc(sizeof(*p1));
+			p1->dir = p2->dir;
+			p1->dir->refCount++;
+			TAILQ_INSERT_TAIL(path1, p1, link);
 		}
 	}
 }
@@ -1154,8 +1132,7 @@ Dir_Concat(Lst *path1, Lst *path2)
 void
 Dir_PrintDirectories(void)
 {
-	const LstNode *ln;
-	const Dir *p;
+	const Dir *d;
 
 	printf("#*** Directory Cache:\n");
 	printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
@@ -1163,17 +1140,15 @@ Dir_PrintDirectories(void)
 	    (hits + bigmisses + nearmisses ?
 	    hits * 100 / (hits + bigmisses + nearmisses) : 0));
 	printf("# %-20s referenced\thits\n", "directory");
-	LST_FOREACH(ln, &openDirectories) {
-		p = Lst_Datum(ln);
-		printf("# %-20s %10d\t%4d\n", p->name, p->refCount, p->hits);
-	}
+	TAILQ_FOREACH(d, &openDirectories, link)
+		printf("# %-20s %10d\t%4d\n", d->name, d->refCount, d->hits);
 }
 
 void
-Dir_PrintPath(const Lst *path)
+Path_Print(const struct Path *path)
 {
-	const LstNode *ln;
+	const struct PathElement *p;
 
-	LST_FOREACH(ln, path)
-		printf("%s ", ((const Dir *)Lst_Datum(ln))->name);
+	TAILQ_FOREACH(p, path, link)
+		printf("%s ", p->dir->name);
 }
diff --git a/usr.bin/make/dir.h b/usr.bin/make/dir.h
index d63e59d..03481b8 100644
--- a/usr.bin/make/dir.h
+++ b/usr.bin/make/dir.h
@@ -43,24 +43,29 @@
 #ifndef dir_h_6002e3b8
 #define	dir_h_6002e3b8
 
+#include <sys/queue.h>
 #include "hash.h"
 
 struct GNode;
 struct Lst;
+struct Dir;
+
+struct PathElement;
+TAILQ_HEAD(Path, PathElement);
 
 void Dir_Init(void);
 void Dir_InitDot(void);
 Boolean Dir_HasWildcards(const char *);
-void Dir_Expand(char *, struct Lst *, struct Lst *);
-char *Dir_FindFile(char *, struct Lst *);
 int Dir_MTime(struct GNode *);
-void Dir_AddDir(struct Lst *, const char *);
-char *Dir_MakeFlags(const char *, const struct Lst *);
-void Dir_ClearPath(struct Lst *);
-void Dir_Concat(struct Lst *, struct Lst *);
 void Dir_PrintDirectories(void);
-void Dir_PrintPath(const struct Lst *);
-void Dir_Destroy(void *);
-void *Dir_CopyDir(void *);
+
+struct Dir *Path_AddDir(struct Path *, const char *);
+void Path_Clear(struct Path *);
+void Path_Concat(struct Path *, const struct Path *);
+void Path_Duplicate(struct Path *, const struct Path *);
+void Path_Expand(char *, struct Path *, struct Lst *);
+char *Path_FindFile(char *, struct Path *);
+char *Path_MakeFlags(const char *, const struct Path *);
+void Path_Print(const struct Path *);
 
 #endif /* dir_h_6002e3b8 */
diff --git a/usr.bin/make/globals.h b/usr.bin/make/globals.h
index c9b3877..c0b5050 100644
--- a/usr.bin/make/globals.h
+++ b/usr.bin/make/globals.h
@@ -52,6 +52,7 @@
 
 struct GNode;
 struct IFile;
+struct Path;
 
 /*
  * The list of target names specified on the command line.
@@ -60,12 +61,15 @@ struct IFile;
 extern Lst create;
 
 /* The list of directories to search when looking for targets */
-extern Lst dirSearchPath;
+extern struct Path dirSearchPath;
 
 extern struct IFile curFile;	/* current makefile */
 
 /* The list of directories to search when looking for includes */
-extern Lst parseIncPath;
+extern struct Path parseIncPath;
+
+/* The system include path. */
+extern struct Path sysIncPath;
 
 extern Boolean	jobsRunning;	/* True if jobs are running */
 extern Boolean	compatMake;	/* True if we are make compatible */
@@ -116,9 +120,6 @@ extern time_t	now;
 
 extern Boolean	oldVars;	/* Do old-style variable substitution */
 
-/* The system include path. */
-extern Lst	sysIncPath;
-
 extern int debug;
 
 #endif /* globals_h_1c1edb96 */
diff --git a/usr.bin/make/main.c b/usr.bin/make/main.c
index e395915..b2c3379 100644
--- a/usr.bin/make/main.c
+++ b/usr.bin/make/main.c
@@ -67,6 +67,7 @@ __FBSDID("$FreeBSD$");
 #include <sys/stat.h>
 #include <sys/sysctl.h>
 #include <sys/time.h>
+#include <sys/queue.h>
 #include <sys/resource.h>
 #include <sys/wait.h>
 #include <err.h>
@@ -310,7 +311,7 @@ rearg:	while((c = getopt(argc, argv, OPTFLAGS)) != -1) {
 			MFLAGS_append("-k", NULL);
 			break;
 		case 'm':
-			Dir_AddDir(&sysIncPath, optarg);
+			Path_AddDir(&sysIncPath, optarg);
 			MFLAGS_append("-m", optarg);
 			break;
 		case 'n':
@@ -703,7 +704,7 @@ main(int argc, char **argv)
 	}
 	Dir_InitDot();		/* Initialize the "." directory */
 	if (objdir != curdir)
-		Dir_AddDir(&dirSearchPath, curdir);
+		Path_AddDir(&dirSearchPath, curdir);
 	Var_Set(".CURDIR", curdir, VAR_GLOBAL);
 	Var_Set(".OBJDIR", objdir, VAR_GLOBAL);
 
@@ -749,15 +750,15 @@ main(int argc, char **argv)
 	 * add the directories from the DEFSYSPATH (more than one may be given
 	 * as dir1:...:dirn) to the system include path.
 	 */
-	if (Lst_IsEmpty(&sysIncPath)) {
+	if (TAILQ_EMPTY(&sysIncPath)) {
 		for (start = syspath; *start != '\0'; start = cp) {
 			for (cp = start; *cp != '\0' && *cp != ':'; cp++)
 				continue;
 			if (*cp == '\0') {
-				Dir_AddDir(&sysIncPath, start);
+				Path_AddDir(&sysIncPath, start);
 			} else {
 				*cp++ = '\0';
-				Dir_AddDir(&sysIncPath, start);
+				Path_AddDir(&sysIncPath, start);
 			}
 		}
 	}
@@ -772,7 +773,7 @@ main(int argc, char **argv)
 		Lst sysMkPath = Lst_Initializer(sysMkPath);
 		LstNode *ln;
 
-		Dir_Expand(PATH_DEFSYSMK, &sysIncPath, &sysMkPath);
+		Path_Expand(PATH_DEFSYSMK, &sysIncPath, &sysMkPath);
 		if (Lst_IsEmpty(&sysMkPath))
 			Fatal("make: no system rules (%s).", PATH_DEFSYSMK);
 		LST_FOREACH(ln, &sysMkPath) {
@@ -835,7 +836,7 @@ main(int argc, char **argv)
 			*ptr = '\0';
 
 			/* Add directory to search path */
-			Dir_AddDir(&dirSearchPath, vpath);
+			Path_AddDir(&dirSearchPath, vpath);
 
 			vpath = ptr + 1;
 		} while (savec != '\0');
@@ -1014,9 +1015,9 @@ ReadMakefile(const char *p)
 		}
 #endif
 		/* look in -I and system include directories. */
-		name = Dir_FindFile(fname, &parseIncPath);
+		name = Path_FindFile(fname, &parseIncPath);
 		if (!name)
-			name = Dir_FindFile(fname, &sysIncPath);
+			name = Path_FindFile(fname, &sysIncPath);
 		if (!name || !(stream = fopen(name, "r")))
 			return (FALSE);
 		MAKEFILE = fname = name;
diff --git a/usr.bin/make/parse.c b/usr.bin/make/parse.c
index b42f427..09d38c7 100644
--- a/usr.bin/make/parse.c
+++ b/usr.bin/make/parse.c
@@ -131,10 +131,10 @@ IFile	    	curFile;	/* current makefile */
 static Lst includes = Lst_Initializer(includes);
 
 /* list of directories for "..." includes */
-Lst parseIncPath = Lst_Initializer(parseIncPath);
+struct Path parseIncPath = TAILQ_HEAD_INITIALIZER(parseIncPath);
 
 /* list of directories for <...> includes */
-Lst sysIncPath = Lst_Initializer(sysIncPath);
+struct Path sysIncPath = TAILQ_HEAD_INITIALIZER(sysIncPath);
 
 /*-
  * specType contains the SPECial TYPE of the current target. It is
@@ -783,7 +783,7 @@ ParseDoDependency(char *line)
 		 * Call on the suffix module to give us a path to
 		 * modify.
 		 */
-		Lst *path;
+		struct Path *path;
 
 		specType = ExPath;
 		path = Suff_GetPath(&line[5]);
@@ -812,11 +812,11 @@ ParseDoDependency(char *line)
 		 * use Dir_Destroy in the destruction of the path as the
 		 * Dir module could have added a directory to the path...
 		 */
-		Lst emptyPath = Lst_Initializer(emptyPath);
+		struct Path emptyPath = TAILQ_HEAD_INITIALIZER(emptyPath);
 
-		Dir_Expand(line, &emptyPath, &curTargs);
+		Path_Expand(line, &emptyPath, &curTargs);
+		Path_Clear(&emptyPath);
 
-		Lst_Destroy(&emptyPath, Dir_Destroy);
 	    } else {
 		/*
 		 * No wildcards, but we want to avoid code duplication,
@@ -941,7 +941,7 @@ ParseDoDependency(char *line)
 		break;
 	    case ExPath:
 		LST_FOREACH(ln, &paths)
-		    Dir_ClearPath(Lst_Datum(ln));
+		    Path_Clear(Lst_Datum(ln));
 		break;
 	    case Posix:
 		Var_Set("%POSIX", "1003.2", VAR_GLOBAL);
@@ -1011,7 +1011,7 @@ ParseDoDependency(char *line)
 		    break;
 		case ExPath:
 		    LST_FOREACH(ln, &paths)
-			Dir_AddDir(Lst_Datum(ln), line);
+			Path_AddDir(Lst_Datum(ln), line);
 		    break;
 		case Includes:
 		    Suff_AddInclude(line);
@@ -1425,7 +1425,7 @@ void
 Parse_AddIncludeDir(char *dir)
 {
 
-    Dir_AddDir(&parseIncPath, dir);
+    Path_AddDir(&parseIncPath, dir);
 }
 
 /*---------------------------------------------------------------------
@@ -1591,9 +1591,9 @@ ParseDoInclude(char *file)
 		newName = estrdup(file);
 	    else
 		newName = str_concat(Fname, file, STR_ADDSLASH);
-	    fullname = Dir_FindFile(newName, &parseIncPath);
+	    fullname = Path_FindFile(newName, &parseIncPath);
 	    if (fullname == NULL) {
-		fullname = Dir_FindFile(newName, &dirSearchPath);
+		fullname = Path_FindFile(newName, &dirSearchPath);
 	    }
 	    free(newName);
 	    *prefEnd = '/';
@@ -1612,9 +1612,9 @@ ParseDoInclude(char *file)
 	 * then on the .PATH search path, if not found in a -I directory.
 	 * XXX: Suffix specific?
 	 */
-	fullname = Dir_FindFile(file, &parseIncPath);
+	fullname = Path_FindFile(file, &parseIncPath);
 	if (fullname == NULL) {
-	    fullname = Dir_FindFile(file, &dirSearchPath);
+	    fullname = Path_FindFile(file, &dirSearchPath);
 	}
     }
 
@@ -1623,7 +1623,7 @@ ParseDoInclude(char *file)
 	 * Still haven't found the makefile. Look for it on the system
 	 * path as a last resort.
 	 */
-	fullname = Dir_FindFile(file, &sysIncPath);
+	fullname = Path_FindFile(file, &sysIncPath);
     }
 
     if (fullname == NULL) {
@@ -1760,9 +1760,9 @@ ParseTraditionalInclude(char *file)
      * Search for it first on the -I search path, then on the .PATH
      * search path, if not found in a -I directory.
      */
-    fullname = Dir_FindFile(file, &parseIncPath);
+    fullname = Path_FindFile(file, &parseIncPath);
     if (fullname == NULL) {
-        fullname = Dir_FindFile(file, &dirSearchPath);
+        fullname = Path_FindFile(file, &dirSearchPath);
     }
 
     if (fullname == NULL) {
@@ -1770,7 +1770,7 @@ ParseTraditionalInclude(char *file)
 	 * Still haven't found the makefile. Look for it on the system
 	 * path as a last resort.
 	 */
-	fullname = Dir_FindFile(file, &sysIncPath);
+	fullname = Path_FindFile(file, &sysIncPath);
     }
 
     if (fullname == NULL) {
diff --git a/usr.bin/make/suff.c b/usr.bin/make/suff.c
index f4d5306..94277d8 100644
--- a/usr.bin/make/suff.c
+++ b/usr.bin/make/suff.c
@@ -90,6 +90,7 @@ __FBSDID("$FreeBSD$");
  *	    	  	    	if the target had no implicit sources.
  */
 
+#include <sys/queue.h>
 #include <assert.h>
 #include <string.h>
 #include <stdlib.h>
@@ -134,7 +135,7 @@ typedef struct Suff {
 #define	SUFF_INCLUDE	0x01	/* One which is #include'd */
 #define	SUFF_LIBRARY	0x02	/* One which contains a library */
 #define	SUFF_NULL	0x04	/* The empty suffix */
-	Lst	searchPath;	/* Path for files with this suffix */
+	struct Path searchPath;	/* Path for files with this suffix */
 	int	sNum;		/* The suffix number */
 	int	refCount;	/* Reference count of list membership */
 	Lst	parents;	/* Suffixes we have a transformation to */
@@ -696,7 +697,7 @@ Suff_AddSuffix(char *str)
 
 	s->name = estrdup(str);
 	s->nameLen = strlen(s->name);
-	Lst_Init(&s->searchPath);
+	TAILQ_INIT(&s->searchPath);
 	Lst_Init(&s->children);
 	Lst_Init(&s->parents);
 	Lst_Init(&s->ref);
@@ -727,7 +728,7 @@ Suff_AddSuffix(char *str)
  *	None
  *-----------------------------------------------------------------------
  */
-Lst *
+struct Path *
 Suff_GetPath(char *sname)
 {
 	Suff	*s;
@@ -762,42 +763,37 @@ Suff_DoPaths(void)
 	Suff	*s;
 	LstNode	*ln;
 	char	*ptr;
-	Lst	inIncludes;	/* Cumulative .INCLUDES path */
-	Lst	inLibs;		/* Cumulative .LIBS path */
+	struct Path inIncludes;	/* Cumulative .INCLUDES path */
+	struct Path inLibs;	/* Cumulative .LIBS path */
 
-	Lst_Init(&inIncludes);
-	Lst_Init(&inLibs);
+	TAILQ_INIT(&inIncludes);
+	TAILQ_INIT(&inLibs);
 
 	for (ln = Lst_First(&sufflist); ln != NULL; ln = Lst_Succ(ln)) {
 		s = Lst_Datum(ln);
-		if (!Lst_IsEmpty(&s->searchPath)) {
 #ifdef INCLUDES
-			if (s->flags & SUFF_INCLUDE) {
-				Dir_Concat(&inIncludes, &s->searchPath);
-			}
+		if (s->flags & SUFF_INCLUDE) {
+			Path_Concat(&inIncludes, &s->searchPath);
+		}
 #endif /* INCLUDES */
 #ifdef LIBRARIES
-			if (s->flags & SUFF_LIBRARY) {
-				Dir_Concat(&inLibs, &s->searchPath);
-			}
-#endif /* LIBRARIES */
-			Dir_Concat(&s->searchPath, &dirSearchPath);
-		} else {
-			Lst_Destroy(&s->searchPath, Dir_Destroy);
-			Lst_Duplicate(&s->searchPath, &dirSearchPath,
-			    Dir_CopyDir);
+		if (s->flags & SUFF_LIBRARY) {
+			Path_Concat(&inLibs, &s->searchPath);
 		}
+#endif /* LIBRARIES */
+		Path_Concat(&s->searchPath, &dirSearchPath);
 	}
 
-	Var_Set(".INCLUDES", ptr = Dir_MakeFlags("-I", &inIncludes),
-	    VAR_GLOBAL);
+	ptr = Path_MakeFlags("-I", &inIncludes);
+	Var_Set(".INCLUDES", ptr, VAR_GLOBAL);
 	free(ptr);
-	Var_Set(".LIBS", ptr = Dir_MakeFlags("-L", &inLibs),
-	    VAR_GLOBAL);
+
+	ptr = Path_MakeFlags("-L", &inLibs);
+	Var_Set(".LIBS", ptr, VAR_GLOBAL);
 	free(ptr);
 
-	Lst_Destroy(&inIncludes, Dir_Destroy);
-	Lst_Destroy(&inLibs, Dir_Destroy);
+	Path_Clear(&inIncludes);
+	Path_Clear(&inLibs);
 }
 
 /*-
@@ -1041,7 +1037,7 @@ SuffFindThem(Lst *srcs, Lst *slst)
 			break;
 		}
 
-		if ((ptr = Dir_FindFile(s->file,
+		if ((ptr = Path_FindFile(s->file,
 		    &s->suff->searchPath)) != NULL) {
 			rs = s;
 #ifdef DEBUG_SRC
@@ -1247,7 +1243,7 @@ SuffExpandWildcards(GNode *child, Lst *members)
 	char	*cp;
 	Lst	exp;	/* List of expansions */
 	LstNode	*ln;
-	Lst	*path;	/* Search path along which to expand */
+	struct Path *path;	/* Search path along which to expand */
 
 	Lst_Init(members);
 
@@ -1282,7 +1278,7 @@ SuffExpandWildcards(GNode *child, Lst *members)
 	 * Expand the word along the chosen path
 	 */
 	Lst_Init(&exp);
-	Dir_Expand(child->name, path, &exp);
+	Path_Expand(child->name, path, &exp);
 
 	while (!Lst_IsEmpty(&exp)) {
 		/*
@@ -1812,7 +1808,7 @@ SuffFindNormalDeps(GNode *gn, Lst *slst)
 		 */
 		if (OP_NOP(gn->type) || (Lst_IsEmpty(&gn->children) &&
 		    Lst_IsEmpty(&gn->commands))) {
-			gn->path = Dir_FindFile(gn->name,
+			gn->path = Path_FindFile(gn->name,
 			    (targ == NULL ? &dirSearchPath :
 			    &targ->suff->searchPath));
 			if (gn->path != NULL) {
@@ -2149,8 +2145,8 @@ Suff_Init(void)
 
 	suffNull->name = estrdup("");
 	suffNull->nameLen = 0;
-	Lst_Init(&suffNull->searchPath);
-	Dir_Concat(&suffNull->searchPath, &dirSearchPath);
+	TAILQ_INIT(&suffNull->searchPath);
+	Path_Concat(&suffNull->searchPath, &dirSearchPath);
 	Lst_Init(&suffNull->children);
 	Lst_Init(&suffNull->parents);
 	Lst_Init(&suffNull->ref);
@@ -2195,7 +2191,7 @@ Suff_PrintAll(void)
 			printf("`%s' ", ((const Suff *)Lst_Datum(tln))->name);
 
 		printf("\n#\tSearch Path: ");
-		Dir_PrintPath(&s->searchPath);
+		Path_Print(&s->searchPath);
 
 		printf("\n");
 	}
diff --git a/usr.bin/make/suff.h b/usr.bin/make/suff.h
index 8e1b406..9982ab4 100644
--- a/usr.bin/make/suff.h
+++ b/usr.bin/make/suff.h
@@ -42,13 +42,14 @@
 #define	suff_h_2d5a821c
 
 struct GNode;
+struct Path;
 
 void Suff_ClearSuffixes(void);
 Boolean Suff_IsTransform(char *);
 struct GNode *Suff_AddTransform(char *);
 void Suff_EndTransform(const struct GNode *);
 void Suff_AddSuffix(char *);
-Lst *Suff_GetPath(char *);
+struct Path *Suff_GetPath(char *);
 void Suff_DoPaths(void);
 void Suff_AddInclude(char *);
 void Suff_AddLib(char *);