fts.c   [plain text]

/***********************************************************************
*                                                                      *
*               This software is part of the ast package               *
*          Copyright (c) 1985-2007 AT&T Intellectual Property          *
*                      and is licensed under the                       *
*                  Common Public License, Version 1.0                  *
*                    by AT&T Intellectual Property                     *
*                                                                      *
*                A copy of the License is available at                 *
*            http://www.opensource.org/licenses/cpl1.0.txt             *
*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
*                                                                      *
*              Information and Software Systems Research               *
*                            AT&T Research                             *
*                           Florham Park NJ                            *
*                                                                      *
*                 Glenn Fowler <gsf@research.att.com>                  *
*                  David Korn <dgk@research.att.com>                   *
*                   Phong Vo <kpv@research.att.com>                    *
*                                                                      *
***********************************************************************/
#pragma prototyped
/*
 * Phong Vo
 * Glenn Fowler
 * AT&T Research
 *
 * fts implementation unwound from the kpv ftwalk() of 1988-10-30
 */

#include <ast.h>
#include <ast_dir.h>
#include <error.h>
#include <fs3d.h>
#include <ls.h>

struct Ftsent;

typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*);
typedef int (*Stat_f)(const char*, struct stat*);

#define _FTS_PRIVATE_ \
	FTSENT*		parent;			/* top parent		*/ \
	FTSENT*		todo;			/* todo list		*/ \
	FTSENT*		top;			/* top element		*/ \
	FTSENT*		root;						   \
	FTSENT*		bot;			/* bottom element	*/ \
	FTSENT*		free;			/* free element		*/ \
	FTSENT*		diroot;						   \
	FTSENT*		curdir;						   \
	FTSENT*		current;		/* current element	*/ \
	FTSENT*		previous;		/* previous current	*/ \
	FTSENT*		dotdot;						   \
	FTSENT*		link;			/* real current fts_link*/ \
	FTSENT*		pwd;			/* pwd parent		*/ \
	DIR*		dir;			/* current dir stream	*/ \
	Compar_f	comparf;		/* node comparison func	*/ \
	int		baselen;		/* current strlen(base)	*/ \
	int		cd;			/* chdir status		*/ \
	int		cpname;						   \
	int		flags;			/* fts_open() flags	*/ \
	int		homesize;		/* sizeof(home)		*/ \
	int		nd;						   \
	unsigned char	children;					   \
	unsigned char	fs3d;						   \
	unsigned char	nostat;					   	   \
	unsigned char	state;			/* fts_read() state	*/ \
	char*		base;			/* basename in path	*/ \
	char*		name;						   \
	char*		path;			/* path workspace	*/ \
	char*		home;			/* home/path buffer	*/ \
	char*		endbase;		/* space to build paths */ \
	char*		endbuf;			/* space to build paths */ \
	char*		pad[2];			/* $0.02 to splain this	*/

/*
 * NOTE: <ftwalk.h> relies on status and statb being the first two elements
 */

#define _FTSENT_PRIVATE_ \
	short		status;			/* internal status	*/ \
	struct stat	statb;			/* fts_statp data	*/ \
	FTS*		fts;			/* fts_open() handle	*/ \
	int		nd;			/* popdir() count	*/ \
	FTSENT*		left;			/* left child		*/ \
	FTSENT*		right;			/* right child		*/ \
	FTSENT*		pwd;			/* pwd parent		*/ \
	FTSENT*		stack;			/* getlist() stack	*/ \
	long		nlink;			/* FTS_D link count	*/ \
	unsigned char	must;			/* must stat		*/ \
	unsigned char	type;			/* DT_* type		*/ \
	unsigned char	symlink;		/* originally a symlink	*/ \
	char		name[sizeof(int)];	/* fts_name data	*/

#include <fts.h>

#ifndef ENOSYS
#define ENOSYS		EINVAL
#endif


#if MAXNAMLEN > 16
#define MINNAME		32
#else
#define MINNAME		16
#endif

#define drop(p,f)	(((f)->fts_namelen < MINNAME) ? ((f)->fts_link = (p)->free, (p)->free = (f)) : (free(f), (p)->free))

#define ACCESS(p,f)	((p)->cd==0?(f)->fts_name:(f)->fts_path)
#define PATH(f,p,l)	((!((f)->flags&FTS_SEEDOTDIR)&&(l)>0&&(p)[0]=='.'&&(p)[1]=='/')?((p)+2):(p))
#define SAME(one,two)	((one)->st_ino==(two)->st_ino&&(one)->st_dev==(two)->st_dev)
#define SKIPLINK(p,f)	((f)->fts_parent->nlink == 0)

#ifdef D_TYPE
#define ISTYPE(f,t)	((f)->type == (t))
#define TYPE(f,t)	((f)->type = (t))
#define SKIP(p,f)	((f)->fts_parent->must == 0 && (((f)->type == DT_UNKNOWN) ? SKIPLINK(p,f) : ((f)->type != DT_DIR && ((f)->type != DT_LNK || ((p)->flags & FTS_PHYSICAL)))))
#else
#undef	DT_UNKNOWN
#define DT_UNKNOWN	0
#undef	DT_LNK
#define DT_LNK		1
#define ISTYPE(f,t)	((t)==DT_UNKNOWN)
#define TYPE(f,d)
#define SKIP(p,f)	((f)->fts_parent->must == 0 && SKIPLINK(p,f))
#endif

#ifndef D_FILENO
#define D_FILENO(d)	(1)
#endif

/*
 * NOTE: a malicious dir rename() could change .. underfoot so we
 *	 must always verify; undef verify to enable the unsafe code
 */

#define verify		1

/*
 * FTS_NOSTAT requires a dir with
 *	D_TYPE(&dirent_t)!=DT_UNKNOWN
 *	    OR
 *	st_nlink>=2
 */

#define FTS_children_resume	1
#define FTS_children_return	2
#define FTS_error		3
#define FTS_popstack		4
#define FTS_popstack_resume	5
#define FTS_popstack_return	6
#define FTS_preorder		7
#define FTS_preorder_resume	8
#define FTS_preorder_return	9
#define FTS_readdir		10
#define FTS_terminal		11
#define FTS_todo		12
#define FTS_top_return		13

typedef int (*Notify_f)(FTS*, FTSENT*, void*);

typedef struct Notify_s
{
	struct Notify_s*	next;
	Notify_f		notifyf;
	void*			context;
} Notify_t;

static Notify_t*		notify;

/*
 * allocate an FTSENT node
 */

static FTSENT*
node(FTS* fts, FTSENT* parent, register char* name, register int namelen)
{
	register FTSENT*	f;
	register int		n;

	if (fts->free && namelen < MINNAME)
	{
		f = fts->free;
		fts->free = f->fts_link;
	}
	else
	{
		n = (namelen < MINNAME ? MINNAME : namelen + 1) - sizeof(int);
		if (!(f = newof(0, FTSENT, 1, n)))
		{
			fts->fts_errno = errno;
			fts->state = FTS_error;
			return 0;
		}
		f->fts = fts;
	}
	TYPE(f, DT_UNKNOWN);
	f->status = 0;
	f->symlink = 0;
	f->fts_level = (f->fts_parent = parent)->fts_level + 1;
	f->fts_link = 0;
	f->fts_pointer = 0;
	f->fts_number = 0;
	f->fts_errno = 0;
	f->fts_namelen = namelen;
	f->fts_name = f->name;
	f->fts_statp = &f->statb;
	memcpy(f->fts_name, name, namelen + 1);
	return f;
}

/*
 * compare directories by device/inode
 */

static int
statcmp(FTSENT* const* pf1, FTSENT* const* pf2)
{
	register const FTSENT*	f1 = *pf1;
	register const FTSENT*	f2 = *pf2;

	if (f1->statb.st_ino < f2->statb.st_ino)
		return -1;
	if (f1->statb.st_ino > f2->statb.st_ino)
		return 1;
	if (f1->statb.st_dev < f2->statb.st_dev)
		return -1;
	if (f1->statb.st_dev > f2->statb.st_dev)
		return 1;

	/*
	 * hack for NFS where <dev,ino> may not uniquely identify objects
	 */

	if (f1->statb.st_mtime < f2->statb.st_mtime)
		return -1;
	if (f1->statb.st_mtime > f2->statb.st_mtime)
		return 1;
	return 0;
}

/*
 * search trees with top-down splaying (a la Tarjan and Sleator)
 * when used for insertion sort, this implements a stable sort
 */

#define RROTATE(r)	(t = r->left, r->left = t->right, t->right = r, r = t)
#define LROTATE(r)	(t = r->right, r->right = t->left, t->left = r, r = t)

static FTSENT*
search(FTSENT* e, FTSENT* root, int(*comparf)(FTSENT* const*, FTSENT* const*), int insert)
{
	register int		cmp;
	register FTSENT*	t;
	register FTSENT*	left;
	register FTSENT*	right;
	register FTSENT*	lroot;
	register FTSENT*	rroot;

	left = right = lroot = rroot = 0;
	while (root)
	{
		if (!(cmp = (*comparf)(&e, &root)) && !insert)
			break;
		if (cmp < 0)
		{	
			/*
			 * this is the left zig-zig case
			 */

			if (root->left && (cmp = (*comparf)(&e, &root->left)) <= 0)
			{
				RROTATE(root);
				if (!cmp && !insert)
					break;
			}

			/*
			 * stick all things > e to the right tree
			 */

			if (right)
				right->left = root;
			else
				rroot = root;
			right = root;
			root = root->left;
			right->left = 0;
		}
		else
		{	
			/*
			 * this is the right zig-zig case
			 */

			if (root->right && (cmp = (*comparf)(&e, &root->right)) >= 0)
			{
				LROTATE(root);
				if (!cmp && !insert)
					break;
			}

			/*
			 * stick all things <= e to the left tree
			 */

			if (left)
				left->right = root;
			else
				lroot = root;
			left = root;
			root = root->right;
			left->right = 0;
		}
	}
	if (!root)
		root = e;
	else
	{
		if (right)
			right->left = root->right;
		else
			rroot = root->right;
		if (left)
			left->right = root->left;
		else
			lroot = root->left;
	}
	root->left = lroot;
	root->right = rroot;
	return root;
}

/*
 * delete the root element from the tree
 */

static FTSENT*
deleteroot(register FTSENT* root)
{
	register FTSENT*	t;
	register FTSENT*	left;
	register FTSENT*	right;

	right = root->right;
	if (!(left = root->left))
		root = right;
	else
	{
		while (left->right)
			LROTATE(left);
		left->right = right;
		root = left;
	}
	return root;
}

/*
 * generate ordered fts_link list from binary tree at root
 * FTSENT.stack instead of recursion to avoid blowing the real
 * stack on big directories
 */

static void
getlist(register FTSENT** top, register FTSENT** bot, register FTSENT* root)
{
	register FTSENT*	stack = 0;

	for (;;)
	{
		if (root->left)
		{
			root->stack = stack;
			stack = root;
			root = root->left;
		}
		else
		{
			for (;;)
			{
				if (*top)
					*bot = (*bot)->fts_link = root;
				else
					*bot = *top = root;
				if (root->right)
				{
					root = root->right;
					break;
				}
				if (!(root = stack))
					return;
				stack = stack->stack;
			}
		}
	}
}

/*
 * set directory when curdir is lost in space
 */

static int
setdir(register char* home, register char* path)
{
	register int	cdrv;

	if (path[0] == '/')
		cdrv = pathcd(path, NiL);
	else
	{
		/*
		 * note that path and home are in the same buffer
		 */

		path[-1] = '/';
		cdrv = pathcd(home, NiL);
		path[-1] = 0;
	}
	if (cdrv < 0)
		pathcd(home, NiL);
	return cdrv;
}

/*
 * set to parent dir
 */

static int
setpdir(register char* home, register char* path, register char* base)
{
	register int	c;
	register int	cdrv;

	if (base > path)
	{
		c = base[0];
		base[0] = 0;
		cdrv = setdir(home, path);
		base[0] = c;
	}
	else
		cdrv = pathcd(home, NiL);
	return cdrv;
}

/*
 * pop a set of directories
 */
static int
popdirs(FTS* fts)
{
	register FTSENT*f;
	register char*	s;
	register char*	e;
#ifndef verify
	register int	verify;
#endif
	struct stat	sb;
	char		buf[PATH_MAX];

	if (!(f = fts->curdir) || f->fts_level < 0)
		return -1;
	e = buf + sizeof(buf) - 4;
#ifndef verify
	verify = 0;
#endif
	while (fts->nd > 0)
	{
		for (s = buf; s < e && fts->nd > 0; fts->nd--)
		{
			if (fts->pwd)
			{
#ifndef verify
				verify |= fts->pwd->symlink;
#endif
				fts->pwd = fts->pwd->pwd;
			}
			*s++ = '.';
			*s++ = '.';
			*s++ = '/';
		}
		*s = 0;
		if (chdir(buf))
			return -1;
	}
	return (verify && (stat(".", &sb) < 0 || !SAME(&sb, f->fts_statp))) ? -1 : 0;
}

/*
 * initialize st from path and fts_info from st
 */

static int
info(FTS* fts, register FTSENT* f, const char* path, struct stat* sp, int flags)
{
	if (path)
	{
#ifdef S_ISLNK
		if (!f->symlink && (ISTYPE(f, DT_UNKNOWN) || ISTYPE(f, DT_LNK)))
		{
			if (lstat(path, sp) < 0)
				goto bad;
		}
		else
#endif
			if (stat(path, sp) < 0)
				goto bad;
	}
#ifdef S_ISLNK
 again:
#endif
	if (S_ISDIR(sp->st_mode))
	{
		if ((flags & FTS_NOSTAT) && !fts->fs3d)
		{
			f->fts_parent->nlink--;
#ifdef D_TYPE
			f->must = 0;
			if ((f->nlink = sp->st_nlink) < 2)
				f->nlink = 2;
#else
			if ((f->nlink = sp->st_nlink) >= 2)
				f->must = 1;
			else
				f->must = 2;
#endif
		}
		else
			f->must = 2;
		TYPE(f, DT_DIR);
		f->fts_info = FTS_D;
	}
#ifdef S_ISLNK
	else if (S_ISLNK((sp)->st_mode))
	{
		struct stat	sb;

		f->symlink = 1;
		if (!(flags & FTS_PHYSICAL) && stat(path, &sb) >= 0)
		{
			*sp = sb;
			flags = FTS_PHYSICAL;
			goto again;
		}
		TYPE(f, DT_LNK);
		f->fts_info = FTS_SL;
	}
#endif
	else
	{
		TYPE(f, DT_REG);
		f->fts_info = FTS_F;
	}
	return 0;
 bad:
	TYPE(f, DT_UNKNOWN);
	f->fts_info = FTS_NS;
	return -1;
}

/*
 * get top list of elements to process
 */

static FTSENT*
toplist(FTS* fts, register char* const* pathnames)
{
	register char*		path;
	register struct stat*	sb;
	register FTSENT*	f;
	register FTSENT*	root;
	int			physical;
	int			metaphysical;
	char*			s;
	FTSENT*			top;
	FTSENT*			bot;
	struct stat		st;

	if (fts->flags & FTS_NOSEEDOTDIR)
		fts->flags &= ~FTS_SEEDOTDIR;
	physical = (fts->flags & FTS_PHYSICAL);
	metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
	top = bot = root = 0;
	while (path = *pathnames++)
	{
		/*
		 * make elements
		 */

		if (!(f = node(fts, fts->parent, path, strlen(path))))
			break;
		path = f->fts_name;
		if (!physical)
			f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, 0) - path);
		else if (*path != '.')
		{
			f->fts_namelen = strlen(path);
			fts->flags |= FTS_SEEDOTDIR;
		}
		else
		{
			if (fts->flags & FTS_NOSEEDOTDIR)
			{
				fts->flags &= ~FTS_SEEDOTDIR;
				s = path;
				while (*s++ == '.' && *s++ == '/')
				{
					while (*s == '/')
						s++;
					if (!*s)
						break;
					path = f->fts_name;
					while (*path++ = *s++);
					path = f->fts_name;
				}
			}
			else
				fts->flags |= FTS_SEEDOTDIR;
			for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
			*s = 0;
			f->fts_namelen = s - path;
		}
		sb = f->fts_statp;
		if (!*path)
		{
			errno = ENOENT;
			f->fts_info = FTS_NS;
		}
		else
			info(fts, f, path, sb, fts->flags);
#ifdef S_ISLNK

		/*
		 * don't let any standards committee get
		 * away with calling your idea a hack
		 */

		if (metaphysical && f->fts_info == FTS_SL && stat(path, &st) >= 0)
		{
			*sb = st;
			info(fts, f, NiL, sb, 0);
		}
#endif
		if (fts->comparf)
			root = search(f, root, fts->comparf, 1);
		else if (bot)
		{
			bot->fts_link = f;
			bot = f;
		}
		else
			top = bot = f;
	}
	if (fts->comparf)
		getlist(&top, &bot, root);
	return top;
}

/*
 * resize the path buffer
 * note that free() is not used because we may need to chdir(fts->home)
 * if there isn't enough space to continue
 */

static int
resize(register FTS* fts, int inc)
{
	register char*	old;
	register char*	newp;
	register int	n_old;

	/*
	 * add space for "/." used in testing FTS_DNX
	 */

	n_old = fts->homesize;
	fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
	if (!(newp = newof(0, char, fts->homesize, 0)))
	{
		fts->fts_errno = errno;
		fts->state = FTS_error;
		return -1;
	}
	old = fts->home;
	fts->home = newp;
	memcpy(newp, old, n_old);
	if (fts->endbuf)
		fts->endbuf = newp + fts->homesize - 4;
	if (fts->path)
		fts->path = newp + (fts->path - old);
	if (fts->base)
		fts->base = newp + (fts->base - old);
	free(old);
	return 0;
}

/*
 * open a new fts stream on pathnames
 */

FTS*
fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
{
	register FTS*	fts;

	if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
		return 0;
	fts->flags = flags;
	fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
	fts->comparf = comparf;
	fts->fs3d = fs3d(FS3D_TEST);

	/*
	 * set up the path work buffer
	 */

	fts->homesize = 2 * PATH_MAX;
	for (;;)
	{
		if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
		{
			free(fts);
			return 0;
		}
		if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
			break;
		if (errno == ERANGE)
			fts->homesize += PATH_MAX;
		else
			fts->cd = 1;
	}
	fts->endbuf = fts->home + fts->homesize - 4;

	/*
	 * initialize the tippity-top
	 */

	fts->parent = (FTSENT*)(fts + 1);
	fts->parent->fts_info = FTS_D;
	memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
	fts->parent->fts_level = -1;
	fts->parent->fts_statp = &fts->parent->statb;
	fts->parent->must = 2;
	fts->parent->type = DT_UNKNOWN;
	fts->path = fts->home + strlen(fts->home) + 1;

	/*
	 * make the list of top elements
	 */

	if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
	{
		char*	v[2];

		v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
		v[1] = 0;
		fts->todo = toplist(fts, v);
	}
	else
		fts->todo = toplist(fts, pathnames);
	if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
	{
		fts_close(fts);
		return 0;
	}
	return fts;
}

/*
 * return the next FTS entry
 */

FTSENT*
fts_read(register FTS* fts)
{
	register char*		s;
	register int		n;
	register FTSENT*	f;
	struct dirent*		d;
	int			i;
	FTSENT*			t;
	Notify_t*		p;
#ifdef verify
	struct stat		sb;
#endif

	for (;;) switch (fts->state)
	{

	case FTS_top_return:

		f = fts->todo;
		t = 0;
		while (f)
			if (f->status == FTS_SKIP)
			{
				if (t)
				{
					t->fts_link = f->fts_link;
					drop(fts, f);
					f = t->fts_link;
				}
				else
				{
					fts->todo = f->fts_link;
					drop(fts, f);
					f = fts->todo;
				}
			}
			else
			{
				t = f;
				f = f->fts_link;
			}
		/*FALLTHROUGH*/

	case 0:

		if (!(f = fts->todo))
			return 0;
		/*FALLTHROUGH*/

	case FTS_todo:

		/*
		 * process the top object on the stack
		 */

		fts->root = fts->top = fts->bot = 0;

		/*
		 * initialize the top level
		 */

		if (f->fts_level == 0)
		{
			fts->parent->fts_number = f->fts_number;
			fts->parent->fts_pointer = f->fts_pointer;
			fts->parent->fts_statp = f->fts_statp;
			fts->parent->statb = *f->fts_statp;
			f->fts_parent = fts->parent;
			fts->diroot = 0;
			if (fts->cd == 0)
				pathcd(fts->home, NiL);
			else if (fts->cd < 0)
				fts->cd = 0;
			fts->pwd = f->fts_parent;
			fts->curdir = fts->cd ? 0 : f->fts_parent;
			*(fts->base = fts->path) = 0;
		}

		/*
		 * chdir to parent if asked for
		 */

		if (fts->cd < 0)
		{
			fts->cd = setdir(fts->home, fts->path);
			fts->pwd = f->fts_parent;
			fts->curdir = fts->cd ? 0 : f->fts_parent;
		}

		/*
		 * add object's name to the path
		 */

		if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
			return 0;
		memcpy(fts->base, f->name, fts->baselen + 1);
		fts->name = fts->cd ? fts->path : fts->base;
		/*FALLTHROUGH*/

	case FTS_preorder:

		/*
		 * check for cycle and open dir
		 */

		if (f->fts_info == FTS_D)
		{
			if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
			{
				f->fts_info = FTS_DC;
				f->fts_cycle = fts->diroot;
			}
			else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
			{
				/*
				 * buffer is known to be large enough here!
				 */

				if (fts->base[fts->baselen - 1] != '/')
					memcpy(fts->base + fts->baselen, "/.", 3);
				if (!(fts->dir = opendir(fts->name)))
					f->fts_info = FTS_DNX;
				fts->base[fts->baselen] = 0;
				if (!fts->dir && !(fts->dir = opendir(fts->name)))
					f->fts_info = FTS_DNR;
			}
		}
		f->nd = f->fts_info & ~FTS_DNX;
		if (f->nd || !(fts->flags & FTS_NOPREORDER))
		{
			fts->current = f;
			fts->link = f->fts_link;
			f->fts_link = 0;
			f->fts_path = PATH(fts, fts->path, f->fts_level);
			f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
			f->fts_accpath = ACCESS(fts, f);
			fts->state = FTS_preorder_return;
			goto note;
		}
		/*FALLTHROUGH*/

	case FTS_preorder_resume:

		/*
		 * prune
		 */

		if (!fts->dir || f->nd || f->status == FTS_SKIP)
		{
			if (fts->dir)
			{
				closedir(fts->dir);
				fts->dir = 0;
			}
			fts->state = FTS_popstack;
			continue;
		}

		/*
		 * FTS_D or FTS_DNX, about to read children
		 */

		if (fts->cd == 0)
		{
			if ((fts->cd = chdir(fts->name)) < 0)
				pathcd(fts->home, NiL);
			else if (fts->pwd != f)
			{
				f->pwd = fts->pwd;
				fts->pwd = f;
			}
			fts->curdir = fts->cd < 0 ? 0 : f;
		}
		fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
		fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
		fts->dotdot = 0;
		fts->endbase = fts->base + fts->baselen;
		if (fts->endbase[-1] != '/')
			*fts->endbase++ = '/';
		fts->current = f;
		/*FALLTHROUGH*/

	case FTS_readdir:

		while (d = readdir(fts->dir))
		{
			s = d->d_name;
			if (s[0] == '.')
			{
				if (s[1] == 0)
				{
					fts->current->nlink--;
					if (!(fts->flags & FTS_SEEDOT))
						continue;
					n = 1;
				}
				else if (s[1] == '.' && s[2] == 0)
				{
					fts->current->nlink--;
					if (fts->current->must == 1)
						fts->current->must = 0;
					if (!(fts->flags & FTS_SEEDOT))
						continue;
					n = 2;
				}
				else
					n = 0;
			}
			else
				n = 0;

			/*
			 * make a new entry
			 */

			i = D_NAMLEN(d);
			if (!(f = node(fts, fts->current, s, i)))
				return 0;
			TYPE(f, D_TYPE(d));

			/*
			 * check for space
			 */

			if (i >= fts->endbuf - fts->endbase)
			{
	   	   		if (resize(fts, i))
					return 0;
				fts->endbase = fts->base + fts->baselen;
				if (fts->endbase[-1] != '/')
					fts->endbase++;
			}
			if (fts->cpname)
			{
				memcpy(fts->endbase, s, i + 1);
				if (fts->cd)
					s = fts->path;
			}
			if (n)
			{
				/*
				 * don't recurse on . and ..
				 */

				if (n == 1)
					f->fts_statp = fts->current->fts_statp;
				else
				{
					if (f->fts_info != FTS_NS)
						fts->dotdot = f;
					if (fts->current->fts_parent->fts_level < 0)
					{
						f->fts_statp = &fts->current->fts_parent->statb;
						info(fts, f, s, f->fts_statp, 0);
					}
					else
						f->fts_statp = fts->current->fts_parent->fts_statp;
				}
				f->fts_info = FTS_DOT;
			}
			else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
				f->statb.st_ino = D_FILENO(d);
			if (fts->comparf)
				fts->root = search(f, fts->root, fts->comparf, 1);
			else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
			{
				if (fts->top)
					fts->bot = fts->bot->fts_link = f;
				else
					fts->top = fts->bot = f;
			}
			else
			{
				/*
				 * terminal node
				 */

				f->fts_path = PATH(fts, fts->path, 1);
				f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
				f->fts_accpath = ACCESS(fts, f);
				fts->previous = fts->current;
				fts->current = f;
				fts->state = FTS_terminal;
				goto note;
			}
		}

		/*
		 * done with the directory
		 */

		closedir(fts->dir);
		fts->dir = 0;
		if (fts->root)
			getlist(&fts->top, &fts->bot, fts->root);
		if (fts->children)
		{	
			/*
			 * try moving back to parent dir
			 */

			fts->base[fts->baselen] = 0;
			if (fts->cd <= 0)
			{
				f = fts->current->fts_parent;
				if (fts->cd < 0
				    || f != fts->curdir
				    || !fts->dotdot
				    || !SAME(f->fts_statp, fts->dotdot->fts_statp)
				    || fts->pwd && fts->pwd->symlink
				    || (fts->cd = chdir("..")) < 0
#ifdef verify
				    || stat(".", &sb) < 0
				    || !SAME(&sb, fts->dotdot->fts_statp)
#endif
				    )
					fts->cd = setpdir(fts->home, fts->path, fts->base);
				if (fts->pwd)
					fts->pwd = fts->pwd->pwd;
				fts->curdir = fts->cd ? 0 : f;
			}
			f = fts->current;
			fts->link = f->fts_link;
			f->fts_link = fts->top;
			f->fts_path = PATH(fts, fts->path, f->fts_level);
			f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
			f->fts_accpath = ACCESS(fts, f);
			fts->state = FTS_children_return;
			goto note;
		}
		/*FALLTHROUGH*/

	case FTS_children_resume:

		fts->base[fts->baselen] = 0;
		if (fts->top)
		{
			fts->bot->fts_link = fts->todo;
			fts->todo = fts->top;
			fts->top = 0;
		}
		/*FALLTHROUGH*/

	case FTS_popstack:

		/*
		 * pop objects completely processed
		 */

		fts->nd = 0;
		f = fts->current;
		/*FALLTHROUGH*/

	case FTS_popstack_resume:

		while (fts->todo && f == fts->todo)
		{
			t = f->fts_parent;
			if ((f->fts_info & FTS_DP) == FTS_D)
			{
				/*
				 * delete from <dev,ino> tree
				 */

				if (f != fts->diroot)
					fts->diroot = search(f, fts->diroot, statcmp, 0);
				fts->diroot = deleteroot(fts->diroot);
				if (f == fts->curdir)
				{
					fts->nd++;
					fts->curdir = t;
				}

				/*
				 * perform post-order processing
				 */

				if (!(fts->flags & FTS_NOPOSTORDER) &&
				    f->status != FTS_SKIP &&
				    f->status != FTS_NOPOSTORDER)
				{
					/*
					 * move to parent dir
					 */

					if (fts->nd > 0)
						fts->cd = popdirs(fts);
					if (fts->cd < 0)
						fts->cd = setpdir(fts->home, fts->path, fts->base);
					fts->curdir = fts->cd ? 0 : t;
					f->fts_info = FTS_DP;
					f->fts_path = PATH(fts, fts->path, f->fts_level);
					f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
					f->fts_accpath = ACCESS(fts, f);

					/*
					 * re-stat to update nlink/times
					 */

					stat(f->fts_accpath, f->fts_statp);
					fts->link = f->fts_link;
					f->fts_link = 0;
					fts->state = FTS_popstack_return;
					goto note;
				}
			}

			/*
			 * reset base
			 */

			if (fts->base > fts->path + t->fts_namelen)
				fts->base--;
			*fts->base = 0;
			fts->base -= t->fts_namelen;

			/*
			 * try again or delete from top of stack
			 */

			if (f->status == FTS_AGAIN)
			{
				f->fts_info = FTS_D;
				f->status = 0;
			}
			else
			{
				fts->todo = fts->todo->fts_link;
				drop(fts, f);
			}
			f = t;
		}

		/*
		 * reset current directory
		 */

		if (fts->nd > 0 && popdirs(fts) < 0)
		{
			pathcd(fts->home, NiL);
			fts->curdir = 0;
			fts->cd = -1;
		}
		if (fts->todo)
		{
			if (*fts->base)
				fts->base += f->fts_namelen;
			if (*(fts->base - 1) != '/')
				*fts->base++ = '/';
			*fts->base = 0;
			f = fts->todo;
			fts->state = FTS_todo;
			continue;
		}
		return 0;

	case FTS_children_return:

		f = fts->current;
		f->fts_link = fts->link;

		/*
		 * chdir down again
		 */

		i = f->fts_info != FTS_DNX;
		n = f->status == FTS_SKIP;
		if (!n && fts->cd == 0)
		{
			if ((fts->cd = chdir(fts->base)) < 0)
				pathcd(fts->home, NiL);
			else if (fts->pwd != f)
			{
				f->pwd = fts->pwd;
				fts->pwd = f;
			}
			fts->curdir = fts->cd ? 0 : f;
		}

		/*
		 * prune
		 */

		if (fts->base[fts->baselen - 1] != '/')
			fts->base[fts->baselen] = '/';
		for (fts->bot = 0, f = fts->top; f; )
			if (n || f->status == FTS_SKIP)
			{
				if (fts->bot)
					fts->bot->fts_link = f->fts_link;
				else
					fts->top = f->fts_link;
				drop(fts, f);
				f = fts->bot ? fts->bot->fts_link : fts->top;
			}
			else
			{
				if (fts->children > 1 && i)
				{
					if (f->status == FTS_STAT)
						info(fts, f, NiL, f->fts_statp, 0);
					else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
					{
						s = f->fts_name;
						if (fts->cd)
						{
							memcpy(fts->endbase, s, f->fts_namelen + 1);
							s = fts->path;
						}
						info(fts, f, s, f->fts_statp, fts->flags);
					}
				}
				fts->bot = f;
				f = f->fts_link;
			}
		fts->children = 0;
		fts->state = FTS_children_resume;
		continue;

	case FTS_popstack_return:

		f = fts->todo;
		f->fts_link = fts->link;
		f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
		fts->state = FTS_popstack_resume;
		continue;

	case FTS_preorder_return:

		f = fts->current;
		f->fts_link = fts->link;

		/*
		 * follow symlink if asked to
		 */

		if (f->status == FTS_FOLLOW)
		{
			f->status = 0;
			if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
			{
				info(fts, f, f->fts_accpath, f->fts_statp, 0);
				if (f->fts_info != FTS_SL)
				{
					fts->state = FTS_preorder;
					continue;
				}
			}
		}

		/*
		 * about to prune this f and already at home
		 */

		if (fts->cd == 0 && f->fts_level == 0 && f->nd)
			fts->cd = -1;
		fts->state = FTS_preorder_resume;
		continue;

	case FTS_terminal:

		f = fts->current;
		if (f->status == FTS_FOLLOW)
		{
			f->status = 0;
			if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
			{
				info(fts, f, f->fts_accpath, f->fts_statp, 0);
				if (f->symlink && f->fts_info != FTS_SL)
				{
					if (!(f->fts_link = fts->top))
						fts->bot = f;
					fts->top = f;
					fts->current = fts->previous;
					fts->state = FTS_readdir;
					continue;
				}
			}
		}
		f = f->fts_parent;
		drop(fts, fts->current);
		fts->current = f;
		fts->state = FTS_readdir;
		continue;

	case FTS_error:

		return 0;

	default:

		fts->fts_errno = EINVAL;
		fts->state = FTS_error;
		return 0;

	}
 note:
	for (p = notify; p; p = p->next)
		if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
			break;
		else if (n < 0)
		{
			fts->fts_errno = EINVAL;
			fts->state = FTS_error;
			return 0;
		}
	return f;
}

/*
 * set stream or entry flags
 */

int
fts_set(register FTS* fts, register FTSENT* f, int status)
{
	if (fts || !f || f->fts->current != f)
		return -1;
	switch (status)
	{
	case FTS_AGAIN:
		break;
	case FTS_FOLLOW:
		if (!(f->fts_info & FTS_SL))
			return -1;
		break;
	case FTS_NOPOSTORDER:
		break;
	case FTS_SKIP:
		if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
			return -1;
		break;
	default:
		return -1;
	}
	f->status = status;
	return 0;
}

/*
 * return the list of child entries
 */

FTSENT*
fts_children(register FTS* fts, int flags)
{
	register FTSENT*	f;

	switch (fts->state)
	{

	case 0:

		fts->state = FTS_top_return;
		return fts->todo;

	case FTS_preorder_return:

		fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1;
		if (f = fts_read(fts))
			f = f->fts_link;
		return f;

	}
	return 0;
}

/*
 * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags
 * conditioned by astconf()
 */

int
fts_flags(void)
{
	register char*	s;
	
	s = astconf("PATH_RESOLVE", NiL, NiL);
	if (streq(s, "logical"))
		return FTS_LOGICAL;
	if (streq(s, "physical"))
		return FTS_PHYSICAL|FTS_SEEDOTDIR;
	return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR;
}

/*
 * return 1 if ent is mounted on a local filesystem
 */

int
fts_local(FTSENT* ent)
{
#ifdef ST_LOCAL
	struct statvfs	fs;

	return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL);
#else
	return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE);
#endif
}

/*
 * close an open fts stream
 */

int
fts_close(register FTS* fts)
{
	register FTSENT*	f;
	register FTSENT*	x;

	if (fts->dir)
		closedir(fts->dir);
	if (fts->cd == 0)
		pathcd(fts->home, NiL);
	free(fts->home);
	if (fts->state == FTS_children_return)
		fts->current->fts_link = fts->link;
	if (fts->top)
	{
		fts->bot->fts_link = fts->todo;
		fts->todo = fts->top;
	}
	for (f = fts->todo; f; f = x)
	{
		x = f->fts_link;
		free(f);
	}
	for (f = fts->free; f; f = x)
	{
		x = f->fts_link;
		free(f);
	}
	free(fts);
	return 0;
}

/*
 * register function to be called for each fts_read() entry
 */

int
fts_notify(Notify_f notifyf, void* context)
{
	register Notify_t*	np;

	if (!(np = newof(0, Notify_t, 1, 0)))
		return -1;
	np->notifyf = notifyf;
	np->context = context;
	np->next = notify;
	notify = np;
	return 0;
}