bsdtar now uses the "tree" package instead of "fts" for walking

directory heirarchies.

7 files changed, 743 insertions, 1518 deletions

diff --git a/usr.bin/tar/Makefile b/usr.bin/tar/Makefile
index 1e5c25e..578c044 100644
--- a/usr.bin/tar/Makefile
+++ b/usr.bin/tar/Makefile
@@ -6,8 +6,8 @@
 #
 
 PROG=	bsdtar
-VERSION=	1.01.023
-DIST_SRCS=	bsdtar.c getdate.y matching.c read.c util.c write.c
+VERSION=	1.02.022
+DIST_SRCS=	bsdtar.c getdate.y matching.c read.c tree.c util.c write.c
 SRCS=	${DIST_SRCS}
 WARNS?=	5
 DPADD=	${LIBARCHIVE} ${LIBBZ2} ${LIBZ}
@@ -25,7 +25,7 @@ DIST_FILES=	${DIST_SRCS}
 DIST_FILES+=	${MAN}
 DIST_FILES+=	bsdtar.h bsdtar_platform.h
 DIST_FILES+=	Makefile.am
-DIST_FILES+=	fts.c fts.h
+DIST_FILES+=	tree.h
 
 distfile:
 	rm -rf ${DIST_BUILD_DIR}
diff --git a/usr.bin/tar/Makefile.am b/usr.bin/tar/Makefile.am
index 85175c8..ce565c0 100644
--- a/usr.bin/tar/Makefile.am
+++ b/usr.bin/tar/Makefile.am
@@ -7,11 +7,11 @@ bsdtar_SOURCES=				\
 		bsdtar.c		\
 		bsdtar.h		\
 		bsdtar_platform.h	\
-		fts.c			\
-		fts.h			\
 		getdate.y		\
 		matching.c		\
 		read.c			\
+		tree.c			\
+		tree.h			\
 		util.c			\
 		write.c
 bsdtar_LDADD=	-larchive -lbz2 -lz
diff --git a/usr.bin/tar/fts.c b/usr.bin/tar/fts.c
deleted file mode 100644
index f512c11..0000000
--- a/usr.bin/tar/fts.c
+++ /dev/null
@@ -1,1191 +0,0 @@
-/*-
- * This file is not used on BSD systems, because the libc version
- * works.  On Linux, the fts in libc is compiled for a 32-bit
- * off_t, which doesn't match the 64-bit off_t used by the rest
- * of bsdtar.  <sigh>
- *
- * bsdtar_platform.h defines _FILE_OFFSET_BITS=64 so this will
- * be compiled for 64-bit off_t.
- *
- * This file is mostly unchanged from:
- * FreeBSD: src/lib/libc/gen/fts.c,v 1.22 2003/01/03 23:25:25 tjr Exp
- * except for a few minor Linux-isms which are commented with "bsdtar:"
- * below.
- */
-
-/*-
- * Copyright (c) 1990, 1993, 1994
- *	The Regents of the University of California.  All rights reserved.
- *
- * 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.
- *
- * From: $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
- * From: $
- */
-
-#if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)fts.c	8.6 (Berkeley) 8/14/94";
-#endif /* LIBC_SCCS and not lint */
-#include "bsdtar_platform.h" /* bsdtar: need platform-specific definitions. */
-__FBSDID("$FreeBSD$");
-
-#ifndef __FreeBSD__  /* bsdtar: Don't use FreeBSD names on non-FreeBSD. */
-#define _open open
-#define _close close
-#define _fstat fstat
-#endif
-
-/* #include "namespace.h" */ /* bsdtar: Don't use namespace.h. */
-#include <sys/types.h>
-#include <sys/param.h>
-#include <sys/stat.h>
-/* #include <dirent.h> */ /* bsdtar: see bsdtar_platform.h */
-#include <errno.h>
-#include <fcntl.h>
-#include <fts.h>
-#undef FTS_WHITEOUT	/* bsdtar: Not all platforms support this. */
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-/* #include "un-namespace.h" */ /* bsdtar: Don't use namespace.h. */
-
-static FTSENT	*fts_alloc(FTS *, char *, int);
-static FTSENT	*fts_build(FTS *, int);
-static void	 fts_lfree(FTSENT *);
-static void	 fts_load(FTS *, FTSENT *);
-static size_t	 fts_maxarglen(char * const *);
-static void	 fts_padjust(FTS *, FTSENT *);
-static int	 fts_palloc(FTS *, size_t);
-static FTSENT	*fts_sort(FTS *, FTSENT *, int);
-static u_short	 fts_stat(FTS *, FTSENT *, int);
-static int	 fts_safe_changedir(FTS *, FTSENT *, int, char *);
-
-#define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
-
-#define	CLR(opt)	(sp->fts_options &= ~(opt))
-#define	ISSET(opt)	(sp->fts_options & (opt))
-#define	SET(opt)	(sp->fts_options |= (opt))
-
-#define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))
-
-/* fts_build flags */
-#define	BCHILD		1		/* fts_children */
-#define	BNAMES		2		/* fts_children, names only */
-#define	BREAD		3		/* fts_read */
-
-#ifndef HAVE_REALLOCF  /* bsdtar: Define reallocf for non-BSD platforms. */
-static void *
-reallocf(ptr, size)
-	void *ptr;
-	size_t size;
-{
-	void *ret = realloc(ptr, size);
-	if (!ret)
-		free(ptr);
-	return ret;
-}
-#endif
-
-FTS *
-fts_open(argv, options, compar)
-	char * const *argv;
-	int options;
-	int (*compar)(const FTSENT * const *, const FTSENT * const *);
-{
-	FTS *sp;
-	FTSENT *p, *root;
-	int nitems;
-	FTSENT *parent, *tmp;
-	int len;
-
-	/* Options check. */
-	if (options & ~FTS_OPTIONMASK) {
-		errno = EINVAL;
-		return (NULL);
-	}
-
-	/* Allocate/initialize the stream */
-	if ((sp = malloc(sizeof(FTS))) == NULL)
-		return (NULL);
-	memset(sp, 0, sizeof(FTS));
-	sp->fts_compar = compar;
-	sp->fts_options = options;
-
-	/* Shush, GCC. */
-	tmp = NULL;
-
-	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
-	if (ISSET(FTS_LOGICAL))
-		SET(FTS_NOCHDIR);
-
-	/*
-	 * Start out with 1K of path space, and enough, in any case,
-	 * to hold the user's paths.
-	 */
-	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
-		goto mem1;
-
-	/* Allocate/initialize root's parent. */
-	if ((parent = fts_alloc(sp, "", 0)) == NULL)
-		goto mem2;
-	parent->fts_level = FTS_ROOTPARENTLEVEL;
-
-	/* Allocate/initialize root(s). */
-	for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
-		/* Don't allow zero-length paths. */
-		if ((len = strlen(*argv)) == 0) {
-			errno = ENOENT;
-			goto mem3;
-		}
-
-		p = fts_alloc(sp, *argv, len);
-		p->fts_level = FTS_ROOTLEVEL;
-		p->fts_parent = parent;
-		p->fts_accpath = p->fts_name;
-		p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
-
-		/* Command-line "." and ".." are real directories. */
-		if (p->fts_info == FTS_DOT)
-			p->fts_info = FTS_D;
-
-		/*
-		 * If comparison routine supplied, traverse in sorted
-		 * order; otherwise traverse in the order specified.
-		 */
-		if (compar) {
-			p->fts_link = root;
-			root = p;
-		} else {
-			p->fts_link = NULL;
-			if (root == NULL)
-				tmp = root = p;
-			else {
-				tmp->fts_link = p;
-				tmp = p;
-			}
-		}
-	}
-	if (compar && nitems > 1)
-		root = fts_sort(sp, root, nitems);
-
-	/*
-	 * Allocate a dummy pointer and make fts_read think that we've just
-	 * finished the node before the root(s); set p->fts_info to FTS_INIT
-	 * so that everything about the "current" node is ignored.
-	 */
-	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
-		goto mem3;
-	sp->fts_cur->fts_link = root;
-	sp->fts_cur->fts_info = FTS_INIT;
-
-	/*
-	 * If using chdir(2), grab a file descriptor pointing to dot to ensure
-	 * that we can get back here; this could be avoided for some paths,
-	 * but almost certainly not worth the effort.  Slashes, symbolic links,
-	 * and ".." are all fairly nasty problems.  Note, if we can't get the
-	 * descriptor we run anyway, just more slowly.
-	 */
-	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = _open(".", O_RDONLY, 0)) < 0)
-		SET(FTS_NOCHDIR);
-
-	return (sp);
-
-mem3:	fts_lfree(root);
-	free(parent);
-mem2:	free(sp->fts_path);
-mem1:	free(sp);
-	return (NULL);
-}
-
-static void
-fts_load(sp, p)
-	FTS *sp;
-	FTSENT *p;
-{
-	int len;
-	char *cp;
-
-	/*
-	 * Load the stream structure for the next traversal.  Since we don't
-	 * actually enter the directory until after the preorder visit, set
-	 * the fts_accpath field specially so the chdir gets done to the right
-	 * place and the user can access the first node.  From fts_open it's
-	 * known that the path will fit.
-	 */
-	len = p->fts_pathlen = p->fts_namelen;
-	memmove(sp->fts_path, p->fts_name, len + 1);
-	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
-		len = strlen(++cp);
-		memmove(p->fts_name, cp, len + 1);
-		p->fts_namelen = len;
-	}
-	p->fts_accpath = p->fts_path = sp->fts_path;
-	sp->fts_dev = p->fts_dev;
-}
-
-int
-fts_close(sp)
-	FTS *sp;
-{
-	FTSENT *freep, *p;
-	int saved_errno;
-
-	/*
-	 * This still works if we haven't read anything -- the dummy structure
-	 * points to the root list, so we step through to the end of the root
-	 * list which has a valid parent pointer.
-	 */
-	if (sp->fts_cur) {
-		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
-			freep = p;
-			p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
-			free(freep);
-		}
-		free(p);
-	}
-
-	/* Free up child linked list, sort array, path buffer. */
-	if (sp->fts_child)
-		fts_lfree(sp->fts_child);
-	if (sp->fts_array)
-		free(sp->fts_array);
-	free(sp->fts_path);
-
-	/* Return to original directory, save errno if necessary. */
-	if (!ISSET(FTS_NOCHDIR)) {
-		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
-		(void)_close(sp->fts_rfd);
-
-		/* Set errno and return. */
-		if (saved_errno != 0) {
-			/* Free up the stream pointer. */
-			free(sp);
-			errno = saved_errno;
-			return (-1);
-		}
-	}
-
-	/* Free up the stream pointer. */
-	free(sp);
-	return (0);
-}
-
-/*
- * Special case of "/" at the end of the path so that slashes aren't
- * appended which would cause paths to be written as "....//foo".
- */
-#define	NAPPEND(p)							\
-	(p->fts_path[p->fts_pathlen - 1] == '/'				\
-	    ? p->fts_pathlen - 1 : p->fts_pathlen)
-
-FTSENT *
-fts_read(sp)
-	FTS *sp;
-{
-	FTSENT *p, *tmp;
-	int instr;
-	char *t;
-	int saved_errno;
-
-	/* If finished or unrecoverable error, return NULL. */
-	if (sp->fts_cur == NULL || ISSET(FTS_STOP))
-		return (NULL);
-
-	/* Set current node pointer. */
-	p = sp->fts_cur;
-
-	/* Save and zero out user instructions. */
-	instr = p->fts_instr;
-	p->fts_instr = FTS_NOINSTR;
-
-	/* Any type of file may be re-visited; re-stat and re-turn. */
-	if (instr == FTS_AGAIN) {
-		p->fts_info = fts_stat(sp, p, 0);
-		return (p);
-	}
-
-	/*
-	 * Following a symlink -- SLNONE test allows application to see
-	 * SLNONE and recover.  If indirecting through a symlink, have
-	 * keep a pointer to current location.  If unable to get that
-	 * pointer, follow fails.
-	 */
-	if (instr == FTS_FOLLOW &&
-	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
-		p->fts_info = fts_stat(sp, p, 1);
-		if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
-			if ((p->fts_symfd = _open(".", O_RDONLY, 0)) < 0) {
-				p->fts_errno = errno;
-				p->fts_info = FTS_ERR;
-			} else
-				p->fts_flags |= FTS_SYMFOLLOW;
-		}
-		return (p);
-	}
-
-	/* Directory in pre-order. */
-	if (p->fts_info == FTS_D) {
-		/* If skipped or crossed mount point, do post-order visit. */
-		if (instr == FTS_SKIP ||
-		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
-			if (p->fts_flags & FTS_SYMFOLLOW)
-				(void)_close(p->fts_symfd);
-			if (sp->fts_child) {
-				fts_lfree(sp->fts_child);
-				sp->fts_child = NULL;
-			}
-			p->fts_info = FTS_DP;
-			return (p);
-		}
-
-		/* Rebuild if only read the names and now traversing. */
-		if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
-			CLR(FTS_NAMEONLY);
-			fts_lfree(sp->fts_child);
-			sp->fts_child = NULL;
-		}
-
-		/*
-		 * Cd to the subdirectory.
-		 *
-		 * If have already read and now fail to chdir, whack the list
-		 * to make the names come out right, and set the parent errno
-		 * so the application will eventually get an error condition.
-		 * Set the FTS_DONTCHDIR flag so that when we logically change
-		 * directories back to the parent we don't do a chdir.
-		 *
-		 * If haven't read do so.  If the read fails, fts_build sets
-		 * FTS_STOP or the fts_info field of the node.
-		 */
-		if (sp->fts_child != NULL) {
-			if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
-				p->fts_errno = errno;
-				p->fts_flags |= FTS_DONTCHDIR;
-				for (p = sp->fts_child; p != NULL; 
-				    p = p->fts_link)
-					p->fts_accpath =
-					    p->fts_parent->fts_accpath;
-			}
-		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
-			if (ISSET(FTS_STOP))
-				return (NULL);
-			return (p);
-		}
-		p = sp->fts_child;
-		sp->fts_child = NULL;
-		goto name;
-	}
-
-	/* Move to the next node on this level. */
-next:	tmp = p;
-	if ((p = p->fts_link) != NULL) {
-		free(tmp);
-
-		/*
-		 * If reached the top, return to the original directory (or
-		 * the root of the tree), and load the paths for the next root.
-		 */
-		if (p->fts_level == FTS_ROOTLEVEL) {
-			if (FCHDIR(sp, sp->fts_rfd)) {
-				SET(FTS_STOP);
-				return (NULL);
-			}
-			fts_load(sp, p);
-			return (sp->fts_cur = p);
-		}
-
-		/*
-		 * User may have called fts_set on the node.  If skipped,
-		 * ignore.  If followed, get a file descriptor so we can
-		 * get back if necessary.
-		 */
-		if (p->fts_instr == FTS_SKIP)
-			goto next;
-		if (p->fts_instr == FTS_FOLLOW) {
-			p->fts_info = fts_stat(sp, p, 1);
-			if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
-				if ((p->fts_symfd =
-				    _open(".", O_RDONLY, 0)) < 0) {
-					p->fts_errno = errno;
-					p->fts_info = FTS_ERR;
-				} else
-					p->fts_flags |= FTS_SYMFOLLOW;
-			}
-			p->fts_instr = FTS_NOINSTR;
-		}
-
-name:		t = sp->fts_path + NAPPEND(p->fts_parent);
-		*t++ = '/';
-		memmove(t, p->fts_name, p->fts_namelen + 1);
-		return (sp->fts_cur = p);
-	}
-
-	/* Move up to the parent node. */
-	p = tmp->fts_parent;
-	free(tmp);
-
-	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
-		/*
-		 * Done; free everything up and set errno to 0 so the user
-		 * can distinguish between error and EOF.
-		 */
-		free(p);
-		errno = 0;
-		return (sp->fts_cur = NULL);
-	}
-
-	/* NUL terminate the pathname. */
-	sp->fts_path[p->fts_pathlen] = '\0';
-
-	/*
-	 * Return to the parent directory.  If at a root node or came through
-	 * a symlink, go back through the file descriptor.  Otherwise, cd up
-	 * one directory.
-	 */
-	if (p->fts_level == FTS_ROOTLEVEL) {
-		if (FCHDIR(sp, sp->fts_rfd)) {
-			SET(FTS_STOP);
-			return (NULL);
-		}
-	} else if (p->fts_flags & FTS_SYMFOLLOW) {
-		if (FCHDIR(sp, p->fts_symfd)) {
-			saved_errno = errno;
-			(void)_close(p->fts_symfd);
-			errno = saved_errno;
-			SET(FTS_STOP);
-			return (NULL);
-		}
-		(void)_close(p->fts_symfd);
-	} else if (!(p->fts_flags & FTS_DONTCHDIR) &&
-		   fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
-		SET(FTS_STOP);
-		return (NULL);
-	}
-	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
-	return (sp->fts_cur = p);
-}
-
-/*
- * Fts_set takes the stream as an argument although it's not used in this
- * implementation; it would be necessary if anyone wanted to add global
- * semantics to fts using fts_set.  An error return is allowed for similar
- * reasons.
- */
-/* ARGSUSED */
-int
-fts_set(sp, p, instr)
-	FTS *sp;
-	FTSENT *p;
-	int instr;
-{
-	if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
-	    instr != FTS_NOINSTR && instr != FTS_SKIP) {
-		errno = EINVAL;
-		return (1);
-	}
-	p->fts_instr = instr;
-	return (0);
-}
-
-FTSENT *
-fts_children(sp, instr)
-	FTS *sp;
-	int instr;
-{
-	FTSENT *p;
-	int fd;
-
-	if (instr != 0 && instr != FTS_NAMEONLY) {
-		errno = EINVAL;
-		return (NULL);
-	}
-
-	/* Set current node pointer. */
-	p = sp->fts_cur;
-
-	/*
-	 * Errno set to 0 so user can distinguish empty directory from
-	 * an error.
-	 */
-	errno = 0;
-
-	/* Fatal errors stop here. */
-	if (ISSET(FTS_STOP))
-		return (NULL);
-
-	/* Return logical hierarchy of user's arguments. */
-	if (p->fts_info == FTS_INIT)
-		return (p->fts_link);
-
-	/*
-	 * If not a directory being visited in pre-order, stop here.  Could
-	 * allow FTS_DNR, assuming the user has fixed the problem, but the
-	 * same effect is available with FTS_AGAIN.
-	 */
-	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
-		return (NULL);
-
-	/* Free up any previous child list. */
-	if (sp->fts_child != NULL)
-		fts_lfree(sp->fts_child);
-
-	if (instr == FTS_NAMEONLY) {
-		SET(FTS_NAMEONLY);
-		instr = BNAMES;
-	} else
-		instr = BCHILD;
-
-	/*
-	 * If using chdir on a relative path and called BEFORE fts_read does
-	 * its chdir to the root of a traversal, we can lose -- we need to
-	 * chdir into the subdirectory, and we don't know where the current
-	 * directory is, so we can't get back so that the upcoming chdir by
-	 * fts_read will work.
-	 */
-	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
-	    ISSET(FTS_NOCHDIR))
-		return (sp->fts_child = fts_build(sp, instr));
-
-	if ((fd = _open(".", O_RDONLY, 0)) < 0)
-		return (NULL);
-	sp->fts_child = fts_build(sp, instr);
-	if (fchdir(fd))
-		return (NULL);
-	(void)_close(fd);
-	return (sp->fts_child);
-}
-
-#ifndef fts_get_clientptr
-#error "fts_get_clientptr not defined"
-#endif
-
-void *
-(fts_get_clientptr)(FTS *sp)
-{
-
-	return (fts_get_clientptr(sp));
-}
-
-#ifndef fts_get_stream
-#error "fts_get_stream not defined"
-#endif
-
-FTS *
-(fts_get_stream)(FTSENT *p)
-{
-	return (fts_get_stream(p));
-}
-
-void
-fts_set_clientptr(FTS *sp, void *clientptr)
-{
-
-	sp->fts_clientptr = clientptr;
-}
-
-/*
- * This is the tricky part -- do not casually change *anything* in here.  The
- * idea is to build the linked list of entries that are used by fts_children
- * and fts_read.  There are lots of special cases.
- *
- * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
- * set and it's a physical walk (so that symbolic links can't be directories),
- * we can do things quickly.  First, if it's a 4.4BSD file system, the type
- * of the file is in the directory entry.  Otherwise, we assume that the number
- * of subdirectories in a node is equal to the number of links to the parent.
- * The former skips all stat calls.  The latter skips stat calls in any leaf
- * directories and for any files after the subdirectories in the directory have
- * been found, cutting the stat calls by about 2/3.
- */
-static FTSENT *
-fts_build(sp, type)
-	FTS *sp;
-	int type;
-{
-	struct dirent *dp;
-	FTSENT *p, *head;
-	int nitems;
-	FTSENT *cur, *tail;
-	DIR *dirp;
-	void *oldaddr;
-	int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno,
-	    nostat, doadjust;
-	char *cp;
-
-	/* Set current node pointer. */
-	cur = sp->fts_cur;
-
-	/*
-	 * Open the directory for reading.  If this fails, we're done.
-	 * If being called from fts_read, set the fts_info field.
-	 */
-#ifdef FTS_WHITEOUT
-	if (ISSET(FTS_WHITEOUT))
-		oflag = DTF_NODUP|DTF_REWIND;
-	else
-		oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
-#else
-#define __opendir2(path, flag) opendir(path)
-#endif
-	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
-		if (type == BREAD) {
-			cur->fts_info = FTS_DNR;
-			cur->fts_errno = errno;
-		}
-		return (NULL);
-	}
-
-	/*
-	 * Nlinks is the number of possible entries of type directory in the
-	 * directory if we're cheating on stat calls, 0 if we're not doing
-	 * any stat calls at all, -1 if we're doing stats on everything.
-	 */
-	if (type == BNAMES) {
-		nlinks = 0;
-		/* Be quiet about nostat, GCC. */
-		nostat = 0;
-	} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
-		nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
-		nostat = 1;
-	} else {
-		nlinks = -1;
-		nostat = 0;
-	}
-
-#ifdef notdef
-	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
-	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
-	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
-#endif
-	/*
-	 * If we're going to need to stat anything or we want to descend
-	 * and stay in the directory, chdir.  If this fails we keep going,
-	 * but set a flag so we don't chdir after the post-order visit.
-	 * We won't be able to stat anything, but we can still return the
-	 * names themselves.  Note, that since fts_read won't be able to
-	 * chdir into the directory, it will have to return different path
-	 * names than before, i.e. "a/b" instead of "b".  Since the node
-	 * has already been visited in pre-order, have to wait until the
-	 * post-order visit to return the error.  There is a special case
-	 * here, if there was nothing to stat then it's not an error to
-	 * not be able to stat.  This is all fairly nasty.  If a program
-	 * needed sorted entries or stat information, they had better be
-	 * checking FTS_NS on the returned nodes.
-	 */
-	cderrno = 0;
-	if (nlinks || type == BREAD) {
-		if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
-			if (nlinks && type == BREAD)
-				cur->fts_errno = errno;
-			cur->fts_flags |= FTS_DONTCHDIR;
-			descend = 0;
-			cderrno = errno;
-			(void)closedir(dirp);
-			dirp = NULL;
-		} else
-			descend = 1;
-	} else
-		descend = 0;
-
-	/*
-	 * Figure out the max file name length that can be stored in the
-	 * current path -- the inner loop allocates more path as necessary.
-	 * We really wouldn't have to do the maxlen calculations here, we
-	 * could do them in fts_read before returning the path, but it's a
-	 * lot easier here since the length is part of the dirent structure.
-	 *
-	 * If not changing directories set a pointer so that can just append
-	 * each new name into the path.
-	 */
-	len = NAPPEND(cur);
-	if (ISSET(FTS_NOCHDIR)) {
-		cp = sp->fts_path + len;
-		*cp++ = '/';
-	} else {
-		/* GCC, you're too verbose. */
-		cp = NULL;
-	}
-	len++;
-	maxlen = sp->fts_pathlen - len;
-
-	level = cur->fts_level + 1;
-
-	/* Read the directory, attaching each entry to the `link' pointer. */
-	doadjust = 0;
-	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
-		/* See bsdtar_platform.h for DIRENT_NAMLEN. */
-		int dnamlen = DIRENT_NAMLEN(dp);
-		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
-			continue;
-
-		if ((p = fts_alloc(sp, dp->d_name, dnamlen)) == NULL)
-			goto mem1;
-		if (dnamlen >= maxlen) {	/* include space for NUL */
-			oldaddr = sp->fts_path;
-			if (fts_palloc(sp, dnamlen + len + 1)) {
-				/*
-				 * No more memory for path or structures.  Save
-				 * errno, free up the current structure and the
-				 * structures already allocated.
-				 */
-mem1:				saved_errno = errno;
-				if (p)
-					free(p);
-				fts_lfree(head);
-				(void)closedir(dirp);
-				cur->fts_info = FTS_ERR;
-				SET(FTS_STOP);
-				errno = saved_errno;
-				return (NULL);
-			}
-			/* Did realloc() change the pointer? */
-			if (oldaddr != sp->fts_path) {
-				doadjust = 1;
-				if (ISSET(FTS_NOCHDIR))
-					cp = sp->fts_path + len;
-			}
-			maxlen = sp->fts_pathlen - len;
-		}
-
-		if (len + dnamlen >= USHRT_MAX) {
-			/*
-			 * In an FTSENT, fts_pathlen is a u_short so it is
-			 * possible to wraparound here.  If we do, free up
-			 * the current structure and the structures already
-			 * allocated, then error out with ENAMETOOLONG.
-			 */
-			free(p);
-			fts_lfree(head);
-			(void)closedir(dirp);
-			cur->fts_info = FTS_ERR;
-			SET(FTS_STOP);
-			errno = ENAMETOOLONG;
-			return (NULL);
-		}
-		p->fts_level = level;
-		p->fts_parent = sp->fts_cur;
-		p->fts_pathlen = len + dnamlen;
-
-#ifdef FTS_WHITEOUT
-		if (dp->d_type == DT_WHT)
-			p->fts_flags |= FTS_ISW;
-#endif
-
-		if (cderrno) {
-			if (nlinks) {
-				p->fts_info = FTS_NS;
-				p->fts_errno = cderrno;
-			} else
-				p->fts_info = FTS_NSOK;
-			p->fts_accpath = cur->fts_accpath;
-		} else if (nlinks == 0
-#ifdef DT_DIR
-		    || (nostat &&
-		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
-#endif
-		    ) {
-			p->fts_accpath =
-			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
-			p->fts_info = FTS_NSOK;
-		} else {
-			/* Build a file name for fts_stat to stat. */
-			if (ISSET(FTS_NOCHDIR)) {
-				p->fts_accpath = p->fts_path;
-				memmove(cp, p->fts_name, p->fts_namelen + 1);
-			} else
-				p->fts_accpath = p->fts_name;
-			/* Stat it. */
-			p->fts_info = fts_stat(sp, p, 0);
-
-			/* Decrement link count if applicable. */
-			if (nlinks > 0 && (p->fts_info == FTS_D ||
-			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
-				--nlinks;
-		}
-
-		/* We walk in directory order so "ls -f" doesn't get upset. */
-		p->fts_link = NULL;
-		if (head == NULL)
-			head = tail = p;
-		else {
-			tail->fts_link = p;
-			tail = p;
-		}
-		++nitems;
-	}
-	if (dirp)
-		(void)closedir(dirp);
-
-	/*
-	 * If realloc() changed the address of the path, adjust the
-	 * addresses for the rest of the tree and the dir list.
-	 */
-	if (doadjust)
-		fts_padjust(sp, head);
-
-	/*
-	 * If not changing directories, reset the path back to original
-	 * state.
-	 */
-	if (ISSET(FTS_NOCHDIR)) {
-		if (len == sp->fts_pathlen || nitems == 0)
-			--cp;
-		*cp = '\0';
-	}
-
-	/*
-	 * If descended after called from fts_children or after called from
-	 * fts_read and nothing found, get back.  At the root level we use
-	 * the saved fd; if one of fts_open()'s arguments is a relative path
-	 * to an empty directory, we wind up here with no other way back.  If
-	 * can't get back, we're done.
-	 */
-	if (descend && (type == BCHILD || !nitems) &&
-	    (cur->fts_level == FTS_ROOTLEVEL ?
-	    FCHDIR(sp, sp->fts_rfd) :
-	    fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
-		cur->fts_info = FTS_ERR;
-		SET(FTS_STOP);
-		return (NULL);
-	}
-
-	/* If didn't find anything, return NULL. */
-	if (!nitems) {
-		if (type == BREAD)
-			cur->fts_info = FTS_DP;
-		return (NULL);
-	}
-
-	/* Sort the entries. */
-	if (sp->fts_compar && nitems > 1)
-		head = fts_sort(sp, head, nitems);
-	return (head);
-}
-
-static u_short
-fts_stat(sp, p, follow)
-	FTS *sp;
-	FTSENT *p;
-	int follow;
-{
-	FTSENT *t;
-	dev_t dev;
-	ino_t ino;
-	struct stat *sbp, sb;
-	int saved_errno;
-
-	/* If user needs stat info, stat buffer already allocated. */
-	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
-
-#ifdef FTS_WHITEOUT
-	/* check for whiteout */
-	if (p->fts_flags & FTS_ISW) {
-		if (sbp != &sb) {
-			memset(sbp, '\0', sizeof (*sbp));
-			sbp->st_mode = S_IFWHT;
-		}
-		return (FTS_W);
-	}
-#endif
-
-	/*
-	 * If doing a logical walk, or application requested FTS_FOLLOW, do
-	 * a stat(2).  If that fails, check for a non-existent symlink.  If
-	 * fail, set the errno from the stat call.
-	 */
-	if (ISSET(FTS_LOGICAL) || follow) {
-		if (stat(p->fts_accpath, sbp)) {
-			saved_errno = errno;
-			if (!lstat(p->fts_accpath, sbp)) {
-				errno = 0;
-				return (FTS_SLNONE);
-			}
-			p->fts_errno = saved_errno;
-			goto err;
-		}
-	} else if (lstat(p->fts_accpath, sbp)) {
-		p->fts_errno = errno;
-err:		memset(sbp, 0, sizeof(struct stat));
-		return (FTS_NS);
-	}
-
-	if (S_ISDIR(sbp->st_mode)) {
-		/*
-		 * Set the device/inode.  Used to find cycles and check for
-		 * crossing mount points.  Also remember the link count, used
-		 * in fts_build to limit the number of stat calls.  It is
-		 * understood that these fields are only referenced if fts_info
-		 * is set to FTS_D.
-		 */
-		dev = p->fts_dev = sbp->st_dev;
-		ino = p->fts_ino = sbp->st_ino;
-		p->fts_nlink = sbp->st_nlink;
-
-		if (ISDOT(p->fts_name))
-			return (FTS_DOT);
-
-		/*
-		 * Cycle detection is done by brute force when the directory
-		 * is first encountered.  If the tree gets deep enough or the
-		 * number of symbolic links to directories is high enough,
-		 * something faster might be worthwhile.
-		 */
-		for (t = p->fts_parent;
-		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
-			if (ino == t->fts_ino && dev == t->fts_dev) {
-				p->fts_cycle = t;
-				return (FTS_DC);
-			}
-		return (FTS_D);
-	}
-	if (S_ISLNK(sbp->st_mode))
-		return (FTS_SL);
-	if (S_ISREG(sbp->st_mode))
-		return (FTS_F);
-	return (FTS_DEFAULT);
-}
-
-/*
- * The comparison function takes pointers to pointers to FTSENT structures.
- * Qsort wants a comparison function that takes pointers to void.
- * (Both with appropriate levels of const-poisoning, of course!)
- * Use a trampoline function to deal with the difference.
- */
-static int
-fts_compar(const void *a, const void *b)
-{
-	FTS *parent;
-
-	parent = (*(const FTSENT * const *)a)->fts_fts;
-	return (*parent->fts_compar)(a, b);
-}
-
-static FTSENT *
-fts_sort(sp, head, nitems)
-	FTS *sp;
-	FTSENT *head;
-	int nitems;
-{
-	FTSENT **ap, *p;
-
-	/*
-	 * Construct an array of pointers to the structures and call qsort(3).
-	 * Reassemble the array in the order returned by qsort.  If unable to
-	 * sort for memory reasons, return the directory entries in their
-	 * current order.  Allocate enough space for the current needs plus
-	 * 40 so don't realloc one entry at a time.
-	 */
-	if (nitems > sp->fts_nitems) {
-		sp->fts_nitems = nitems + 40;
-		if ((sp->fts_array = reallocf(sp->fts_array,
-		    sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
-			sp->fts_nitems = 0;
-			return (head);
-		}
-	}
-	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
-		*ap++ = p;
-	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
-	for (head = *(ap = sp->fts_array); --nitems; ++ap)
-		ap[0]->fts_link = ap[1];
-	ap[0]->fts_link = NULL;
-	return (head);
-}
-
-static FTSENT *
-fts_alloc(sp, name, namelen)
-	FTS *sp;
-	char *name;
-	int namelen;
-{
-	FTSENT *p;
-	size_t len;
-
-	struct ftsent_withstat {
-		FTSENT	ent;
-		struct	stat statbuf;
-	};
-
-	/*
-	 * The file name is a variable length array and no stat structure is
-	 * necessary if the user has set the nostat bit.  Allocate the FTSENT
-	 * structure, the file name and the stat structure in one chunk, but
-	 * be careful that the stat structure is reasonably aligned.
-	 */
-	if (ISSET(FTS_NOSTAT))
-		len = sizeof(FTSENT) + namelen + 1;
-	else
-		len = sizeof(struct ftsent_withstat) + namelen + 1;
-
-	if ((p = malloc(len)) == NULL)
-		return (NULL);
-
-	if (ISSET(FTS_NOSTAT)) {
-		p->fts_name = (char *)(p + 1);
-		p->fts_statp = NULL;
-	} else {
-		p->fts_name = (char *)((struct ftsent_withstat *)p + 1);
-		p->fts_statp = &((struct ftsent_withstat *)p)->statbuf;
-	}
-
-	/* Copy the name and guarantee NUL termination. */
-	memcpy(p->fts_name, name, namelen);
-	p->fts_name[namelen] = '\0';
-	p->fts_namelen = namelen;
-	p->fts_path = sp->fts_path;
-	p->fts_errno = 0;
-	p->fts_flags = 0;
-	p->fts_instr = FTS_NOINSTR;
-	p->fts_number = 0;
-	p->fts_pointer = NULL;
-	p->fts_fts = sp;
-	return (p);
-}
-
-static void
-fts_lfree(head)
-	FTSENT *head;
-{
-	FTSENT *p;
-
-	/* Free a linked list of structures. */
-	while ((p = head)) {
-		head = head->fts_link;
-		free(p);
-	}
-}
-
-/*
- * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
- * Most systems will allow creation of paths much longer than MAXPATHLEN, even
- * though the kernel won't resolve them.  Add the size (not just what's needed)
- * plus 256 bytes so don't realloc the path 2 bytes at a time.
- */
-static int
-fts_palloc(sp, more)
-	FTS *sp;
-	size_t more;
-{
-
-	sp->fts_pathlen += more + 256;
-	/*
-	 * Check for possible wraparound.  In an FTS, fts_pathlen is
-	 * a signed int but in an FTSENT it is an unsigned short.
-	 * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
-	 */
-	if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
-		if (sp->fts_path)
-			free(sp->fts_path);
-		sp->fts_path = NULL;
-		errno = ENAMETOOLONG;
-		return (1);
-	}
-	sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
-	return (sp->fts_path == NULL);
-}
-
-/*
- * When the path is realloc'd, have to fix all of the pointers in structures
- * already returned.
- */
-static void
-fts_padjust(sp, head)
-	FTS *sp;
-	FTSENT *head;
-{
-	FTSENT *p;
-	char *addr = sp->fts_path;
-
-#define	ADJUST(p) do {							\
-	if ((p)->fts_accpath != (p)->fts_name) {			\
-		(p)->fts_accpath =					\
-		    (char *)addr + ((p)->fts_accpath - (p)->fts_path);	\
-	}								\
-	(p)->fts_path = addr;						\
-} while (0)
-	/* Adjust the current set of children. */
-	for (p = sp->fts_child; p; p = p->fts_link)
-		ADJUST(p);
-
-	/* Adjust the rest of the tree, including the current level. */
-	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
-		ADJUST(p);
-		p = p->fts_link ? p->fts_link : p->fts_parent;
-	}
-}
-
-static size_t
-fts_maxarglen(argv)
-	char * const *argv;
-{
-	size_t len, max;
-
-	for (max = 0; *argv; ++argv)
-		if ((len = strlen(*argv)) > max)
-			max = len;
-	return (max + 1);
-}
-
-/*
- * Change to dir specified by fd or p->fts_accpath without getting
- * tricked by someone changing the world out from underneath us.
- * Assumes p->fts_dev and p->fts_ino are filled in.
- */
-static int
-fts_safe_changedir(sp, p, fd, path)
-	FTS *sp;
-	FTSENT *p;
-	int fd;
-	char *path;
-{
-	int ret, oerrno, newfd;
-	struct stat sb;
-
-	newfd = fd;
-	if (ISSET(FTS_NOCHDIR))
-		return (0);
-	if (fd < 0 && (newfd = _open(path, O_RDONLY, 0)) < 0)
-		return (-1);
-	if (_fstat(newfd, &sb)) {
-		ret = -1;
-		goto bail;
-	}
-	if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
-		errno = ENOENT;		/* disinformation */
-		ret = -1;
-		goto bail;
-	}
-	ret = fchdir(newfd);
-bail:
-	oerrno = errno;
-	if (fd < 0)
-		(void)_close(newfd);
-	errno = oerrno;
-	return (ret);
-}
diff --git a/usr.bin/tar/fts.h b/usr.bin/tar/fts.h
deleted file mode 100644
index f47a344..0000000
--- a/usr.bin/tar/fts.h
+++ /dev/null
@@ -1,147 +0,0 @@
-/*-
- * This file is not used on BSD systems, because the libc version
- * works.  On Linux, the fts in libc is compiled for a 32-bit
- * off_t, which doesn't match the 64-bit off_t used by the rest
- * of bsdtar.
- *
- * The remainder of this file is an exact copy of:
- * FreeBSD: src/include/fts.h,v 1.7 2002/09/21 01:28:36 wollman Exp
- */
-
-/*
- * Copyright (c) 1989, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * 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.
- *
- *	@(#)fts.h	8.3 (Berkeley) 8/14/94
- * $FreeBSD$
- */
-
-#ifndef	_FTS_H_
-#define	_FTS_H_
-
-typedef struct {
-	struct _ftsent *fts_cur;	/* current node */
-	struct _ftsent *fts_child;	/* linked list of children */
-	struct _ftsent **fts_array;	/* sort array */
-	dev_t fts_dev;			/* starting device # */
-	char *fts_path;			/* path for this descent */
-	int fts_rfd;			/* fd for root */
-	int fts_pathlen;		/* sizeof(path) */
-	int fts_nitems;			/* elements in the sort array */
-	int (*fts_compar)		/* compare function */
-	    (const struct _ftsent * const *, const struct _ftsent * const *);
-
-#define	FTS_COMFOLLOW	0x001		/* follow command line symlinks */
-#define	FTS_LOGICAL	0x002		/* logical walk */
-#define	FTS_NOCHDIR	0x004		/* don't change directories */
-#define	FTS_NOSTAT	0x008		/* don't get stat info */
-#define	FTS_PHYSICAL	0x010		/* physical walk */
-#define	FTS_SEEDOT	0x020		/* return dot and dot-dot */
-#define	FTS_XDEV	0x040		/* don't cross devices */
-#define	FTS_WHITEOUT	0x080		/* return whiteout information */
-#define	FTS_OPTIONMASK	0x0ff		/* valid user option mask */
-
-#define	FTS_NAMEONLY	0x100		/* (private) child names only */
-#define	FTS_STOP	0x200		/* (private) unrecoverable error */
-	int fts_options;		/* fts_open options, global flags */
-	void *fts_clientptr;		/* thunk for sort function */
-} FTS;
-
-typedef struct _ftsent {
-	struct _ftsent *fts_cycle;	/* cycle node */
-	struct _ftsent *fts_parent;	/* parent directory */
-	struct _ftsent *fts_link;	/* next file in directory */
-	long fts_number;	        /* local numeric value */
-	void *fts_pointer;	        /* local address value */
-	char *fts_accpath;		/* access path */
-	char *fts_path;			/* root path */
-	int fts_errno;			/* errno for this node */
-	int fts_symfd;			/* fd for symlink */
-	u_short fts_pathlen;		/* strlen(fts_path) */
-	u_short fts_namelen;		/* strlen(fts_name) */
-
-	ino_t fts_ino;			/* inode */
-	dev_t fts_dev;			/* device */
-	nlink_t fts_nlink;		/* link count */
-
-#define	FTS_ROOTPARENTLEVEL	-1
-#define	FTS_ROOTLEVEL		 0
-	short fts_level;		/* depth (-1 to N) */
-
-#define	FTS_D		 1		/* preorder directory */
-#define	FTS_DC		 2		/* directory that causes cycles */
-#define	FTS_DEFAULT	 3		/* none of the above */
-#define	FTS_DNR		 4		/* unreadable directory */
-#define	FTS_DOT		 5		/* dot or dot-dot */
-#define	FTS_DP		 6		/* postorder directory */
-#define	FTS_ERR		 7		/* error; errno is set */
-#define	FTS_F		 8		/* regular file */
-#define	FTS_INIT	 9		/* initialized only */
-#define	FTS_NS		10		/* stat(2) failed */
-#define	FTS_NSOK	11		/* no stat(2) requested */
-#define	FTS_SL		12		/* symbolic link */
-#define	FTS_SLNONE	13		/* symbolic link without target */
-#define	FTS_W		14		/* whiteout object */
-	u_short fts_info;		/* user flags for FTSENT structure */
-
-#define	FTS_DONTCHDIR	 0x01		/* don't chdir .. to the parent */
-#define	FTS_SYMFOLLOW	 0x02		/* followed a symlink to get here */
-#define	FTS_ISW		 0x04		/* this is a whiteout object */
-	u_short fts_flags;		/* private flags for FTSENT structure */
-
-#define	FTS_AGAIN	 1		/* read node again */
-#define	FTS_FOLLOW	 2		/* follow symbolic link */
-#define	FTS_NOINSTR	 3		/* no instructions */
-#define	FTS_SKIP	 4		/* discard node */
-	u_short fts_instr;		/* fts_set() instructions */
-
-	struct stat *fts_statp;		/* stat(2) information */
-	char *fts_name;			/* file name */
-	FTS *fts_fts;			/* back pointer to main FTS */
-} FTSENT;
-
-#include <sys/cdefs.h>
-
-__BEGIN_DECLS
-FTSENT	*fts_children(FTS *, int);
-int	 fts_close(FTS *);
-void	*fts_get_clientptr(FTS *);
-#define	 fts_get_clientptr(fts)	((fts)->fts_clientptr)
-FTS	*fts_get_stream(FTSENT *);
-#define	 fts_get_stream(ftsent)	((ftsent)->fts_fts)
-FTS	*fts_open(char * const *, int,
-	    int (*)(const FTSENT * const *, const FTSENT * const *));
-FTSENT	*fts_read(FTS *);
-int	 fts_set(FTS *, FTSENT *, int);
-void	 fts_set_clientptr(FTS *, void *);
-__END_DECLS
-
-#endif /* !_FTS_H_ */
diff --git a/usr.bin/tar/tree.c b/usr.bin/tar/tree.c
new file mode 100644
index 0000000..0fc3584
--- /dev/null
+++ b/usr.bin/tar/tree.c
@@ -0,0 +1,506 @@
+/*-
+ * Copyright (c) 2003-2004 Tim Kientzle
+ * All rights reserved.
+ *
+ * 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
+ *    in this position and unchanged.
+ * 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) 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.
+ */
+
+/*-
+ * This is a new directory-walking system that addresses a number
+ * of problems I've had with fts(3).  In particular, it has no
+ * pathname-length limits (other than the size of 'int'), handles
+ * deep logical traversals, uses considerably less memory, and has
+ * an opaque interface (easier to modify in the future).
+ *
+ * Internally, it keeps a single list of "tree_entry" items that
+ * represent filesystem objects that require further attention.
+ * Non-directories are not kept in memory: they are pulled from
+ * readdir(), returned to the client, then freed as soon as possible.
+ * Any directory entry to be traversed gets pushed onto the stack.
+ *
+ * There is surprisingly little information that needs to be kept for
+ * each item on the stack.  Just the name, depth (represented here as the
+ * string length of the parent directory's pathname), and some markers
+ * indicating how to get back to the parent (via chdir("..") for a
+ * regular dir or via fchdir(2) for a symlink).
+ */
+#include "bsdtar_platform.h"
+__FBSDID("$FreeBSD$");
+
+#include <sys/stat.h>
+#include <dirent.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "tree.h"
+
+/*
+ * TODO:
+ *    1) Loop checking.
+ *    3) Arbitrary logical traversals by closing/reopening intermediate fds.
+ */
+
+struct tree_entry {
+	struct tree_entry *next;
+	struct tree_entry *parent;
+	char *name;
+	size_t dirname_length;
+	dev_t dev;
+	ino_t ino;
+	int fd;
+	int flags;
+};
+
+/* Definitions for tree_entry.flags bitmap. */
+#define	isDir 1 /* This entry is a regular directory. */
+#define	isDirLink 2 /* This entry is a symbolic link to a directory. */
+#define	needsPreVisit 4 /* This entry needs to be previsited. */
+#define	needsPostVisit 8 /* This entry needs to be postvisited. */
+
+/*
+ * Local data for this package.
+ */
+struct tree {
+	struct tree_entry	*stack;
+	struct tree_entry	*current;
+	DIR	*d;
+	int	 initialDirFd;
+	int	 flags;
+	int	 visit_type;
+	int	 tree_errno; /* Error code from last failed operation. */
+
+	char	*buff;
+	const char	*basename;
+	size_t	 buff_length;
+	size_t	 path_length;
+	size_t	 dirname_length;
+
+	int	 depth;
+	int	 openCount;
+	int	 maxOpenCount;
+
+	struct stat	lst;
+	struct stat	st;
+};
+
+/* Definitions for tree.flags bitmap. */
+#define needsReturn 8  /* Marks first entry as not having been returned yet. */
+#define hasStat 16  /* The st entry is set. */
+#define hasLstat 32 /* The lst entry is set. */
+
+
+#ifdef HAVE_DIRENT_D_NAMLEN
+/* BSD extension; avoids need for a strlen() call. */
+#define D_NAMELEN(dp)	(dp)->d_namlen
+#else
+#define D_NAMELEN(dp)	(strlen((dp)->d_name))
+#endif
+
+#if 0
+#include <stdio.h>
+void
+tree_dump(struct tree *t, FILE *out)
+{
+	struct tree_entry *te;
+
+	fprintf(out, "\tdepth: %d\n", t->depth);
+	fprintf(out, "\tbuff: %s\n", t->buff);
+	fprintf(out, "\tpwd: "); fflush(stdout); system("pwd");
+	fprintf(out, "\taccess: %s\n", t->basename);
+	fprintf(out, "\tstack:\n");
+	for(te = t->stack; te != NULL; te = te->next) {
+		fprintf(out, "\t\tte->name: %s%s%s\n", te->name,
+		    te->flags & needsPreVisit ? "" : " *",
+		    t->current == te ? " (current)" : "");
+	}
+}
+#endif
+
+/*
+ * Add a directory path to the current stack.
+ */
+static void
+tree_push(struct tree *t, const char *path)
+{
+	struct tree_entry *te;
+
+	te = malloc(sizeof(*te));
+	memset(te, 0, sizeof(*te));
+	te->next = t->stack;
+	t->stack = te;
+	te->fd = -1;
+	te->name = strdup(path);
+	te->flags = needsPreVisit | needsPostVisit;
+	te->dirname_length = t->dirname_length;
+}
+
+/*
+ * Append a name to the current path.
+ */
+static void
+tree_append(struct tree *t, const char *name, size_t name_length)
+{
+	char *p;
+
+	if (t->buff != NULL)
+		t->buff[t->dirname_length] = '\0';
+	/* Strip trailing '/' from name, unless entire name is "/". */
+	while (name_length > 1 && name[name_length - 1] == '/')
+		name_length--;
+
+	/* Resize pathname buffer as needed. */
+	while (name_length + 1 + t->dirname_length >= t->buff_length) {
+		t->buff_length *= 2;
+		if (t->buff_length < 1024)
+			t->buff_length = 1024;
+		t->buff = realloc(t->buff, t->buff_length);
+	}
+	p = t->buff + t->dirname_length;
+	t->path_length = t->dirname_length + name_length;
+	/* Add a separating '/' if it's needed. */
+	if (t->dirname_length > 0 && p[-1] != '/') {
+		*p++ = '/';
+		t->path_length ++;
+	}
+	strncpy(p, name, name_length);
+	p[name_length] = '\0';
+	t->basename = p;
+}
+
+/*
+ * Open a directory tree for traversal.
+ */
+struct tree *
+tree_open(const char *path)
+{
+	struct tree *t;
+
+	t = malloc(sizeof(*t));
+	memset(t, 0, sizeof(*t));
+	tree_append(t, path, strlen(path));
+	t->initialDirFd = open(".", O_RDONLY);
+	/*
+	 * During most of the traversal, items are set up and then
+	 * returned immediately from tree_next().  That doesn't work
+	 * for the very first entry, so we set a flag for this special
+	 * case.
+	 */
+	t->flags = needsReturn;
+	return (t);
+}
+
+/*
+ * We've finished a directory; ascend back to the parent.
+ */
+static void
+tree_ascend(struct tree *t)
+{
+	struct tree_entry *te;
+
+	te = t->stack;
+	t->depth--;
+	if (te->flags & isDirLink) {
+		fchdir(te->fd);
+		close(te->fd);
+		t->openCount--;
+	} else {
+		chdir("..");
+	}
+}
+
+/*
+ * Pop the working stack.
+ */
+static void
+tree_pop(struct tree *t)
+{
+	struct tree_entry *te;
+
+	t->buff[t->dirname_length] = '\0';
+	if (t->stack == t->current && t->current != NULL)
+		t->current = t->current->parent;
+	te = t->stack;
+	t->stack = te->next;
+	t->dirname_length = te->dirname_length;
+	t->basename = t->buff + t->dirname_length;
+	/* Special case: starting dir doesn't skip leading '/'. */
+	if (t->dirname_length > 0)
+		t->basename++;
+	free(te->name);
+	free(te);
+}
+
+/*
+ * Get the next item in the tree traversal.
+ */
+int
+tree_next(struct tree *t)
+{
+	struct dirent *de = NULL;
+
+	/* Handle the startup case by returning the initial entry. */
+	if (t->flags & needsReturn) {
+		t->flags &= ~needsReturn;
+		return (t->visit_type = TREE_REGULAR);
+	}
+
+	while (t->stack != NULL) {
+		/* If there's an open dir, get the next entry from there. */
+		while (t->d != NULL) {
+			de = readdir(t->d);
+			if (de == NULL) {
+				closedir(t->d);
+				t->d = NULL;
+			} else if (de->d_name[0] == '.'
+			    && de->d_name[1] == '\0') {
+				/* Skip '.' */
+			} else if (de->d_name[0] == '.'
+			    && de->d_name[1] == '.'
+			    && de->d_name[2] == '\0') {
+				/* Skip '..' */
+			} else {
+				/*
+				 * Append the path to the current path
+				 * and return it.
+				 */
+				tree_append(t, de->d_name, D_NAMELEN(de));
+				t->flags &= ~hasLstat;
+				t->flags &= ~hasStat;
+				return (t->visit_type = TREE_REGULAR);
+			}
+		}
+
+		/* If the current dir needs to be visited, set it up. */
+		if (t->stack->flags & needsPreVisit) {
+			t->current = t->stack;
+			tree_append(t, t->stack->name, strlen(t->stack->name));
+			t->stack->flags &= ~needsPreVisit;
+			/* If it is a link, set up fd for the ascent. */
+			if (t->stack->flags & isDirLink) {
+				t->stack->fd = open(".", O_RDONLY);
+				t->openCount++;
+				if (t->openCount > t->maxOpenCount)
+					t->maxOpenCount = t->openCount;
+			}
+			t->dirname_length = t->path_length;
+			if (chdir(t->stack->name) != 0) {
+				/* chdir() failed; return error */
+				tree_pop(t);
+				t->tree_errno = errno;
+				return (t->visit_type = TREE_ERROR);
+			}
+			t->d = opendir(".");
+			if (t->d == NULL) {
+				tree_pop(t);
+				t->tree_errno = errno;
+				return (t->visit_type = TREE_ERROR);
+			}
+			t->depth++;
+			t->flags &= ~hasLstat;
+			t->flags &= ~hasStat;
+			t->basename = ".";
+			return (t->visit_type = TREE_POSTDESCENT);
+		}
+
+		/* We've done everything necessary for the top stack entry. */
+		if (t->stack->flags & needsPostVisit) {
+			tree_ascend(t);
+			tree_pop(t);
+			t->flags &= ~hasLstat;
+			t->flags &= ~hasStat;
+			return (t->visit_type = TREE_POSTASCENT);
+		}
+	}
+	return (t->visit_type = 0);
+}
+
+/*
+ * Return error code.
+ */
+int
+tree_errno(struct tree *t)
+{
+	return (t->tree_errno);
+}
+
+/*
+ * Called by the client to mark the directory just returned from
+ * tree_next() as needing to be visited.
+ */
+void
+tree_descend(struct tree *t)
+{
+	if (t->visit_type != TREE_REGULAR)
+		return;
+
+	if (tree_current_is_physical_dir(t)) {
+		tree_push(t, t->basename);
+		t->stack->flags |= isDir;
+	} else if (tree_current_is_dir(t)) {
+		tree_push(t, t->basename);
+		t->stack->flags |= isDirLink;
+	}
+}
+
+/*
+ * Get the stat() data for the entry just returned from tree_next().
+ */
+const struct stat *
+tree_current_stat(struct tree *t)
+{
+	if (!(t->flags & hasStat)) {
+		if (stat(t->basename, &t->st) != 0)
+			return NULL;
+		t->flags |= hasStat;
+	}
+	return (&t->st);
+}
+
+/*
+ * Get the lstat() data for the entry just returned from tree_next().
+ */
+const struct stat *
+tree_current_lstat(struct tree *t)
+{
+	if (!(t->flags & hasLstat)) {
+		if (lstat(t->basename, &t->lst) != 0)
+			return NULL;
+		t->flags |= hasLstat;
+	}
+	return (&t->lst);
+}
+
+/*
+ * Test whether current entry is a dir or dir link.
+ */
+int
+tree_current_is_dir(struct tree *t)
+{
+	/* If we've already pulled stat(), just use that. */
+	if (t->flags & hasStat)
+		return (S_ISDIR(tree_current_stat(t)->st_mode));
+
+	/* If we've already pulled lstat(), we may be able to use that. */
+	if (t->flags & hasLstat) {
+		/* If lstat() says it's a dir, it must be a dir. */
+		if (S_ISDIR(tree_current_lstat(t)->st_mode))
+			return 1;
+		/* If it's not a dir and not a link, we're done. */
+		if (!S_ISLNK(tree_current_lstat(t)->st_mode))
+			return 0;
+		/*
+		 * If the above two tests fail, then it's a link, but
+		 * we don't know whether it's a link to a dir or a
+		 * non-dir.
+		 */
+	}
+
+	/* TODO: Use a more efficient mechanism when available. */
+	return (S_ISDIR(tree_current_stat(t)->st_mode));
+}
+
+/*
+ * Test whether current entry is a physical directory.
+ */
+int
+tree_current_is_physical_dir(struct tree *t)
+{
+	/* If we've already pulled lstat(), just use that. */
+	if (t->flags & hasLstat)
+		return (S_ISDIR(tree_current_lstat(t)->st_mode));
+
+	/* TODO: Use a more efficient mechanism when available. */
+	return (S_ISDIR(tree_current_lstat(t)->st_mode));
+}
+
+/*
+ * Test whether current entry is a symbolic link.
+ */
+int
+tree_current_is_physical_link(struct tree *t)
+{
+	/* If we've already pulled lstat(), just use that. */
+	if (t->flags & hasLstat)
+		return (S_ISLNK(tree_current_lstat(t)->st_mode));
+
+	/* TODO: Use a more efficient mechanism when available. */
+	return (S_ISLNK(tree_current_lstat(t)->st_mode));
+}
+
+/*
+ * Return the access path for the entry just returned from tree_next().
+ */
+const char *
+tree_current_access_path(struct tree *t)
+{
+	return (t->basename);
+}
+
+/*
+ * Return the full path for the entry just returned from tree_next().
+ */
+const char *
+tree_current_path(struct tree *t)
+{
+	return (t->buff);
+}
+
+/*
+ * Return the length of the path for the entry just returned from tree_next().
+ */
+size_t
+tree_current_pathlen(struct tree *t)
+{
+	return (t->path_length);
+}
+
+/*
+ * Return the nesting depth of the entry just returned from tree_next().
+ */
+int
+tree_current_depth(struct tree *t)
+{
+	return (t->depth);
+}
+
+/*
+ * Terminate the traversal and release any resources.
+ */
+void
+tree_close(struct tree *t)
+{
+	/* Release anything remaining in the stack. */
+	while (t->stack != NULL)
+		tree_pop(t);
+	if (t->buff)
+		free(t->buff);
+	/* chdir() back to where we started. */
+	if (t->initialDirFd >= 0) {
+		fchdir(t->initialDirFd);
+		close(t->initialDirFd);
+		t->initialDirFd = -1;
+	}
+	free(t);
+}
diff --git a/usr.bin/tar/tree.h b/usr.bin/tar/tree.h
new file mode 100644
index 0000000..95dad6b
--- /dev/null
+++ b/usr.bin/tar/tree.h
@@ -0,0 +1,116 @@
+/*-
+ * Copyright (c) 2003-2004 Tim Kientzle
+ * All rights reserved.
+ *
+ * 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
+ *    in this position and unchanged.
+ * 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``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 AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/*-
+ * A set of routines for traversing directory trees.
+ * Similar in concept to the fts library, but with a few
+ * important differences:
+ *    * Uses less memory.  In particular, fts stores an entire directory
+ *      in memory at a time.  This package only keeps enough subdirectory
+ *      information in memory to track the traversal.  Information
+ *      about non-directories is discarded as soon as possible.
+ *    * Supports very deep logical traversals.  The fts package
+ *      uses "non-chdir" approach for logical traversals.  This
+ *      package does use a chdir approach for logical traversals
+ *      and can therefore handle pathnames much longer than
+ *      PATH_MAX.
+ *    * Supports deep physical traversals "out of the box."
+ *      Due to the memory optimizations above, there's no need to
+ *      limit dir names to 32k.
+ */
+
+#include <sys/stat.h>
+#include <stdio.h>
+
+struct tree;
+
+/* Initiate/terminate a tree traversal. */
+struct tree *tree_open(const char * /* pathname */);
+void tree_close(struct tree *);
+
+/*
+ * tree_next() returns Zero if there is no next entry, non-zero if there is.
+ * Note that directories are potentially visited three times.  The first
+ * time as "regular" file.  If tree_descend() is invoked at that time,
+ * the directory is added to a work list and will be visited two more
+ * times:  once just after descending into the directory and again
+ * just after ascending back to the parent.
+ *
+ * TREE_ERROR is returned if the descent failed (because the
+ * directory couldn't be opened, for instance).  This is returned
+ * instead of TREE_PREVISIT/TREE_POSTVISIT.
+ */
+#define	TREE_REGULAR	1
+#define	TREE_POSTDESCENT	2
+#define	TREE_POSTASCENT	3
+#define	TREE_ERROR	-1
+int tree_next(struct tree *);
+
+int tree_errno(struct tree *);
+
+/*
+ * Request that current entry be visited.  If you invoke it on every
+ * directory, you'll get a physical traversal.  This is ignored if the
+ * current entry isn't a directory or a link to a directory.  So, if
+ * you invoke this on every returned path, you'll get a full logical
+ * traversal.
+ */
+void tree_descend(struct tree *);
+
+/*
+ * Return information about the current entry.
+ */
+
+int tree_current_depth(struct tree *);
+/*
+ * The current full pathname, length of the full pathname,
+ * and a name that can be used to access the file.
+ * Because tree does use chdir extensively, the access path is
+ * almost never the same as the full current path.
+ */
+const char *tree_current_path(struct tree *);
+size_t tree_current_pathlen(struct tree *);
+const char *tree_current_access_path(struct tree *);
+/*
+ * Request the lstat() or stat() data for the current path.  Since the
+ * tree package needs to do some of this anyway, and caches the
+ * results, you should take advantage of it here if you need it rather
+ * than make a redundant stat() or lstat() call of your own.
+ */
+const struct stat *tree_current_stat(struct tree *);
+const struct stat *tree_current_lstat(struct tree *);
+/* The following tests may use mechanisms much faster than stat()/lstat(). */
+/* "is_physical_dir" is equivalent to S_ISDIR(tree_current_lstat()->st_mode) */
+int tree_current_is_physical_dir(struct tree *);
+/* "is_physical_link" is equivalent to S_ISLNK(tree_current_lstat()->st_mode) */
+int tree_current_is_physical_link(struct tree *);
+/* "is_dir" is equivalent to S_ISDIR(tree_current_stat()->st_mode) */
+int tree_current_is_dir(struct tree *);
+
+/* For testing/debugging: Dump the internal status to the given filehandle. */
+void tree_dump(struct tree *, FILE *);
diff --git a/usr.bin/tar/write.c b/usr.bin/tar/write.c
index dfcbcba..3d833e9 100644
--- a/usr.bin/tar/write.c
+++ b/usr.bin/tar/write.c
@@ -37,7 +37,6 @@ __FBSDID("$FreeBSD$");
 #include <errno.h>
 #include <fcntl.h>
 #include <fnmatch.h>
-#include <fts.h>
 #include <grp.h>
 #include <limits.h>
 #include <pwd.h>
@@ -51,6 +50,7 @@ __FBSDID("$FreeBSD$");
 #endif
 
 #include "bsdtar.h"
+#include "tree.h"
 
 /* Fixed size of uname/gname caches. */
 #define	name_cache_size 101
@@ -514,205 +514,146 @@ append_archive(struct bsdtar *bsdtar, struct archive *a, const char *filename)
 static void
 write_hierarchy(struct bsdtar *bsdtar, struct archive *a, const char *path)
 {
-	FTS	*fts;
-	FTSENT	*ftsent;
-	int	 ftsoptions;
-	char	*fts_argv[2];
+	struct tree *tree;
+	char symlink_mode = bsdtar->symlink_mode;
+	dev_t first_dev = 0;
+	int dev_recorded = 0;
+	int tree_ret;
 #ifdef __linux
 	int	 fd, r;
 	unsigned long fflags;
 #endif
 
-	/*
-	 * Sigh: fts_open modifies it's first parameter, so we have to
-	 * copy 'path' to mutable storage.
-	 */
-	fts_argv[0] = strdup(path);
-	if (fts_argv[0] == NULL)
-		bsdtar_errc(bsdtar, 1, ENOMEM, "Can't open %s", path);
-	fts_argv[1] = NULL;
-	ftsoptions = FTS_PHYSICAL;
-	switch (bsdtar->symlink_mode) {
-	case 'H':
-		ftsoptions |= FTS_COMFOLLOW;
-		break;
-	case 'L':
-		ftsoptions = FTS_COMFOLLOW | FTS_LOGICAL;
-		break;
-	}
-	if (bsdtar->option_dont_traverse_mounts)
-		ftsoptions |= FTS_XDEV;
-
-	fts = fts_open(fts_argv, ftsoptions, NULL);
+	tree = tree_open(path);
 
-
-	if (!fts) {
+	if (!tree) {
 		bsdtar_warnc(bsdtar, errno, "%s: Cannot open", path);
 		bsdtar->return_value = 1;
 		return;
 	}
 
-	while ((ftsent = fts_read(fts))) {
-		switch (ftsent->fts_info) {
-		case FTS_NS:
-			bsdtar_warnc(bsdtar, ftsent->fts_errno,
-			    "%s: Could not stat", ftsent->fts_path);
-			bsdtar->return_value = 1;
-			break;
-		case FTS_ERR:
-			bsdtar_warnc(bsdtar, ftsent->fts_errno, "%s",
-			    ftsent->fts_path);
-			bsdtar->return_value = 1;
-			break;
-		case FTS_DNR:
-			bsdtar_warnc(bsdtar, ftsent->fts_errno,
-			    "%s: Cannot read directory contents",
-			    ftsent->fts_path);
-			bsdtar->return_value = 1;
-			break;
-		case FTS_W:  /* Skip Whiteout entries */
-			break;
-		case FTS_DC: /* Directory that causes cycle */
-			/* XXX Does this need special handling ? */
-			break;
-		case FTS_D:
-			/*
-			 * If this dir is flagged "nodump" and we're
-			 * honoring such flags, tell FTS to skip the
-			 * entire tree and don't write the entry for the
-			 * directory itself.
-			 */
-#ifdef HAVE_CHFLAGS
-			if (bsdtar->option_honor_nodump &&
-			    (ftsent->fts_statp->st_flags & UF_NODUMP)) {
-				fts_set(fts, ftsent, FTS_SKIP);
-				break;
-			}
-#endif
-
-#ifdef __linux
-			/*
-			 * Linux has a nodump flag too but to read it
-			 * we have to open() the dir and do an ioctl on it...
-			 */
-			if (bsdtar->option_honor_nodump &&
-			    ((fd = open(ftsent->fts_name, O_RDONLY|O_NONBLOCK)) >= 0) &&
-			    ((r = ioctl(fd, EXT2_IOC_GETFLAGS, &fflags)),
-			    close(fd), r) >= 0 &&
-			    (fflags & EXT2_NODUMP_FL)) {
-				fts_set(fts, ftsent, FTS_SKIP);
-				break;
-			}
-#endif
-
-			/*
-			 * In -u mode, we need to check whether this
-			 * is newer than what's already in the archive.
-			 * In all modes, we need to obey --newerXXX flags.
-			 */
-			if (!new_enough(bsdtar, ftsent->fts_path,
-				ftsent->fts_statp))
-				break;
-			/*
-			 * If this dir is excluded by a filename
-			 * pattern, tell FTS to skip the entire tree
-			 * and don't write the entry for the directory
-			 * itself.
-			 */
-			if (excluded(bsdtar, ftsent->fts_path)) {
-				fts_set(fts, ftsent, FTS_SKIP);
-				break;
-			}
+	while ((tree_ret = tree_next(tree))) {
+		const char *name = tree_current_path(tree);
+		const struct stat *st = NULL, *lst = NULL;
+		int descend;
 
-			/*
-			 * If the user vetoes the directory, skip
-			 * the whole thing.
-			 */
-			if (bsdtar->option_interactive &&
-			    !yes("add '%s'", ftsent->fts_path)) {
-				fts_set(fts, ftsent, FTS_SKIP);
-				break;
-			}
+		if (tree_ret == TREE_ERROR)
+			bsdtar_warnc(bsdtar, errno, "%s", name);
+		if (tree_ret != TREE_REGULAR)
+			continue;
+		lst = tree_current_lstat(tree);
+		if (lst == NULL) {
+			/* Couldn't lstat(); must not exist. */
+			bsdtar_warnc(bsdtar, errno, "%s: Cannot open", path);
+			bsdtar->return_value = 1;
+			continue;
+		}
+		if (S_ISLNK(lst->st_mode))
+			st = tree_current_stat(tree);
+		/* Default: descend into any dir or symlink to dir. */
+		/* We'll adjust this later on. */
+		descend = 0;
+		if ((st != NULL) && S_ISDIR(st->st_mode))
+			descend = 1;
+		if ((lst != NULL) && S_ISDIR(lst->st_mode))
+			descend = 1;
+
+		/*
+		 * If user has asked us not to cross mount points,
+		 * then don't descend into into a dir on a different
+		 * device.
+		 */
+		if (!dev_recorded) {
+			first_dev = lst->st_dev;
+			dev_recorded = 1;
+		}
+		if (bsdtar->option_dont_traverse_mounts) {
+			if (lst != NULL && lst->st_dev != first_dev)
+				descend = 0;
+		}
 
-			/*
-			 * If we're not recursing, tell FTS to skip the
-			 * tree but do fall through and write the entry
-			 * for the dir itself.
-			 */
-			if (bsdtar->option_no_subdirs)
-				fts_set(fts, ftsent, FTS_SKIP);
-			write_entry(bsdtar, a, ftsent->fts_statp,
-			    ftsent->fts_path, ftsent->fts_pathlen,
-			    ftsent->fts_accpath);
-			break;
-		case FTS_F:
-		case FTS_SL:
-		case FTS_SLNONE:
-		case FTS_DEFAULT:
-			/*
-			 * Skip this file if it's flagged "nodump" and we're
-			 * honoring that flag.
-			 */
-#if defined(HAVE_CHFLAGS) && defined(UF_NODUMP)
-			if (bsdtar->option_honor_nodump &&
-			    (ftsent->fts_statp->st_flags & UF_NODUMP))
-				break;
+		/*
+		 * If this file/dir is flagged "nodump" and we're
+		 * honoring such flags, skip this file/dir.
+		 */
+#ifdef HAVE_CHFLAGS
+		if (bsdtar->option_honor_nodump &&
+		    (lst->st_flags & UF_NODUMP))
+			continue;
 #endif
 
 #ifdef __linux
-			/*
-			 * Linux has a nodump flag too but to read it
-			 * we have to open() the file and do an ioctl on it...
-			 */
-			if (bsdtar->option_honor_nodump &&
-			    S_ISREG(ftsent->fts_statp->st_mode) &&
-			    ((fd = open(ftsent->fts_name, O_RDONLY|O_NONBLOCK)) >= 0) &&
-			    ((r = ioctl(fd, EXT2_IOC_GETFLAGS, &fflags)),
-			    close(fd), r) >= 0 &&
-			    (fflags & EXT2_NODUMP_FL))
-				break;
+		/*
+		 * Linux has a nodump flag too but to read it
+		 * we have to open() the file/dir and do an ioctl on it...
+		 */
+		if (bsdtar->option_honor_nodump &&
+		    ((fd = open(name, O_RDONLY|O_NONBLOCK)) >= 0) &&
+		    ((r = ioctl(fd, EXT2_IOC_GETFLAGS, &fflags)),
+			close(fd), r) >= 0 &&
+		    (fflags & EXT2_NODUMP_FL))
+			continue;
 #endif
 
-			/*
-			 * Skip this file if it's excluded by a
-			 * filename pattern.
-			 */
-			if (excluded(bsdtar, ftsent->fts_path))
-				break;
-
-			/*
-			 * In -u mode, we need to check whether this
-			 * is newer than what's already in the archive.
-			 */
-			if (!new_enough(bsdtar, ftsent->fts_path,
-				ftsent->fts_statp))
-				break;
+		/*
+		 * If this file/dir is excluded by a filename
+		 * pattern, skip it.
+		 */
+		if (excluded(bsdtar, name))
+			continue;
 
-			if (bsdtar->option_interactive &&
-			    !yes("add '%s'", ftsent->fts_path)) {
-				break;
-			}
+		/*
+		 * If the user vetoes this file/directory, skip it.
+		 */
+		if (bsdtar->option_interactive &&
+		    !yes("add '%s'", name))
+			continue;
 
-			write_entry(bsdtar, a, ftsent->fts_statp,
-			    ftsent->fts_path, ftsent->fts_pathlen,
-			    ftsent->fts_accpath);
+		/*
+		 * If this is a dir, decide whether or not to recurse.
+		 */
+		if (bsdtar->option_no_subdirs)
+			descend = 0;
+
+		/*
+		 * Distinguish 'L'/'P'/'H' symlink following.
+		 */
+		switch(symlink_mode) {
+		case 'H':
+			/* 'H': First item (from command line) like 'L'. */
+			lst = tree_current_stat(tree);
+			/* 'H': After the first item, rest like 'P'. */
+			symlink_mode = 'P';
 			break;
-		case FTS_DP:
+		case 'L':
+			/* 'L': Do descend through a symlink to dir. */
+			/* 'L': Archive symlink to file as file. */
+			lst = tree_current_stat(tree);
 			break;
 		default:
-			bsdtar_warnc(bsdtar, 0,
-			    "%s: Hierarchy traversal error %d\n",
-			    ftsent->fts_path,
-			    ftsent->fts_info);
+			/* 'P': Don't descend through a symlink to dir. */
+			if (!S_ISDIR(lst->st_mode))
+				descend = 0;
+			/* 'P': Archive symlink to file as symlink. */
+			/* lst = tree_current_lstat(tree); */
 			break;
 		}
 
+		if (descend)
+			tree_descend(tree);
+
+		/*
+		 * In -u mode, we need to check whether this
+		 * is newer than what's already in the archive.
+		 * In all modes, we need to obey --newerXXX flags.
+		 */
+		if (new_enough(bsdtar, name, lst)) {
+			write_entry(bsdtar, a, lst, name,
+			    tree_current_pathlen(tree),
+			    tree_current_access_path(tree));
+		}
 	}
-	if (errno)
-		bsdtar_warnc(bsdtar, errno, "%s", path);
-	if (fts_close(fts))
-		bsdtar_warnc(bsdtar, errno, "fts_close failed");
-	free(fts_argv[0]);
+	tree_close(tree);
 }
 
 /*
@@ -750,7 +691,7 @@ write_entry(struct bsdtar *bsdtar, struct archive *a, const struct stat *st,
 
 	/* Display entry as we process it. This format is required by SUSv2. */
 	if (bsdtar->verbose)
-		safe_fprintf(stderr, "a %s", pathname);
+		safe_fprintf(stderr, "a %s", archive_entry_pathname(entry));
 
 	/* Read symbolic link information. */
 	if ((st->st_mode & S_IFMT) == S_IFLNK) {
@@ -784,7 +725,7 @@ write_entry(struct bsdtar *bsdtar, struct archive *a, const struct stat *st,
 #ifdef __linux
 	if ((S_ISREG(st->st_mode) || S_ISDIR(st->st_mode)) &&
 	    ((fd = open(accpath, O_RDONLY|O_NONBLOCK)) >= 0) &&
-	    ((r = ioctl(fd, EXT2_IOC_GETFLAGS, &stflags)), close(fd), r) >= 0 &&
+	    ((r = ioctl(fd, EXT2_IOC_GETFLAGS, &stflags)), close(fd), (fd = -1), r) >= 0 &&
 	    stflags) {
 		archive_entry_set_fflags(entry, stflags, 0);
 	}