1da2e3ebdSchin /***********************************************************************
2da2e3ebdSchin *                                                                      *
3da2e3ebdSchin *               This software is part of the ast package               *
4*b30d1939SAndy Fiddaman *          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5da2e3ebdSchin *                      and is licensed under the                       *
6*b30d1939SAndy Fiddaman *                 Eclipse Public License, Version 1.0                  *
77c2fbfb3SApril Chin *                    by AT&T Intellectual Property                     *
8da2e3ebdSchin *                                                                      *
9da2e3ebdSchin *                A copy of the License is available at                 *
10*b30d1939SAndy Fiddaman *          http://www.eclipse.org/org/documents/epl-v10.html           *
11*b30d1939SAndy Fiddaman *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
12da2e3ebdSchin *                                                                      *
13da2e3ebdSchin *              Information and Software Systems Research               *
14da2e3ebdSchin *                            AT&T Research                             *
15da2e3ebdSchin *                           Florham Park NJ                            *
16da2e3ebdSchin *                                                                      *
17da2e3ebdSchin *                 Glenn Fowler <gsf@research.att.com>                  *
18da2e3ebdSchin *                  David Korn <dgk@research.att.com>                   *
19da2e3ebdSchin *                   Phong Vo <kpv@research.att.com>                    *
20da2e3ebdSchin *                                                                      *
21da2e3ebdSchin ***********************************************************************/
22da2e3ebdSchin #pragma prototyped
23da2e3ebdSchin /*
24da2e3ebdSchin  * Phong Vo
25da2e3ebdSchin  * Glenn Fowler
26da2e3ebdSchin  * AT&T Research
27da2e3ebdSchin  *
28da2e3ebdSchin  * fts implementation unwound from the kpv ftwalk() of 1988-10-30
29da2e3ebdSchin  */
30da2e3ebdSchin 
31da2e3ebdSchin #include <ast.h>
32da2e3ebdSchin #include <ast_dir.h>
33da2e3ebdSchin #include <error.h>
34da2e3ebdSchin #include <fs3d.h>
357c2fbfb3SApril Chin #include <ls.h>
36da2e3ebdSchin 
37da2e3ebdSchin struct Ftsent;
38da2e3ebdSchin 
39da2e3ebdSchin typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*);
40da2e3ebdSchin typedef int (*Stat_f)(const char*, struct stat*);
41da2e3ebdSchin 
4234f9b3eeSRoland Mainz #define _fts_status	status
4334f9b3eeSRoland Mainz #define _fts_statb	statb
4434f9b3eeSRoland Mainz 
45da2e3ebdSchin #define _FTS_PRIVATE_ \
46da2e3ebdSchin 	FTSENT*		parent;			/* top parent		*/ \
47da2e3ebdSchin 	FTSENT*		todo;			/* todo list		*/ \
48da2e3ebdSchin 	FTSENT*		top;			/* top element		*/ \
49da2e3ebdSchin 	FTSENT*		root;						   \
50da2e3ebdSchin 	FTSENT*		bot;			/* bottom element	*/ \
51da2e3ebdSchin 	FTSENT*		free;			/* free element		*/ \
52da2e3ebdSchin 	FTSENT*		diroot;						   \
53da2e3ebdSchin 	FTSENT*		curdir;						   \
54da2e3ebdSchin 	FTSENT*		current;		/* current element	*/ \
55da2e3ebdSchin 	FTSENT*		previous;		/* previous current	*/ \
56da2e3ebdSchin 	FTSENT*		dotdot;						   \
57da2e3ebdSchin 	FTSENT*		link;			/* real current fts_link*/ \
58da2e3ebdSchin 	FTSENT*		pwd;			/* pwd parent		*/ \
59da2e3ebdSchin 	DIR*		dir;			/* current dir stream	*/ \
60da2e3ebdSchin 	Compar_f	comparf;		/* node comparison func	*/ \
6134f9b3eeSRoland Mainz 	size_t		baselen;		/* current strlen(base)	*/ \
6234f9b3eeSRoland Mainz 	size_t		homesize;		/* sizeof(home)		*/ \
63da2e3ebdSchin 	int		cd;			/* chdir status		*/ \
64da2e3ebdSchin 	int		cpname;						   \
65da2e3ebdSchin 	int		flags;			/* fts_open() flags	*/ \
66da2e3ebdSchin 	int		nd;						   \
67da2e3ebdSchin 	unsigned char	children;					   \
68da2e3ebdSchin 	unsigned char	fs3d;						   \
69da2e3ebdSchin 	unsigned char	nostat;					   	   \
70da2e3ebdSchin 	unsigned char	state;			/* fts_read() state	*/ \
71da2e3ebdSchin 	char*		base;			/* basename in path	*/ \
72da2e3ebdSchin 	char*		name;						   \
73da2e3ebdSchin 	char*		path;			/* path workspace	*/ \
74da2e3ebdSchin 	char*		home;			/* home/path buffer	*/ \
75da2e3ebdSchin 	char*		endbase;		/* space to build paths */ \
76da2e3ebdSchin 	char*		endbuf;			/* space to build paths */ \
777c2fbfb3SApril Chin 	char*		pad[2];			/* $0.02 to splain this	*/
78da2e3ebdSchin 
79da2e3ebdSchin /*
80da2e3ebdSchin  * NOTE: <ftwalk.h> relies on status and statb being the first two elements
81da2e3ebdSchin  */
82da2e3ebdSchin 
83da2e3ebdSchin #define _FTSENT_PRIVATE_ \
84da2e3ebdSchin 	int		nd;			/* popdir() count	*/ \
85da2e3ebdSchin 	FTSENT*		left;			/* left child		*/ \
86da2e3ebdSchin 	FTSENT*		right;			/* right child		*/ \
87da2e3ebdSchin 	FTSENT*		pwd;			/* pwd parent		*/ \
88da2e3ebdSchin 	FTSENT*		stack;			/* getlist() stack	*/ \
89da2e3ebdSchin 	long		nlink;			/* FTS_D link count	*/ \
90da2e3ebdSchin 	unsigned char	must;			/* must stat		*/ \
91da2e3ebdSchin 	unsigned char	type;			/* DT_* type		*/ \
92da2e3ebdSchin 	unsigned char	symlink;		/* originally a symlink	*/ \
93da2e3ebdSchin 	char		name[sizeof(int)];	/* fts_name data	*/
94da2e3ebdSchin 
95da2e3ebdSchin #include <fts.h>
96da2e3ebdSchin 
97da2e3ebdSchin #ifndef ENOSYS
98da2e3ebdSchin #define ENOSYS		EINVAL
99da2e3ebdSchin #endif
100da2e3ebdSchin 
101da2e3ebdSchin 
102da2e3ebdSchin #if MAXNAMLEN > 16
103da2e3ebdSchin #define MINNAME		32
104da2e3ebdSchin #else
105da2e3ebdSchin #define MINNAME		16
106da2e3ebdSchin #endif
107da2e3ebdSchin 
108da2e3ebdSchin #define drop(p,f)	(((f)->fts_namelen < MINNAME) ? ((f)->fts_link = (p)->free, (p)->free = (f)) : (free(f), (p)->free))
109da2e3ebdSchin 
110da2e3ebdSchin #define ACCESS(p,f)	((p)->cd==0?(f)->fts_name:(f)->fts_path)
111da2e3ebdSchin #define PATH(f,p,l)	((!((f)->flags&FTS_SEEDOTDIR)&&(l)>0&&(p)[0]=='.'&&(p)[1]=='/')?((p)+2):(p))
112da2e3ebdSchin #define SAME(one,two)	((one)->st_ino==(two)->st_ino&&(one)->st_dev==(two)->st_dev)
113da2e3ebdSchin #define SKIPLINK(p,f)	((f)->fts_parent->nlink == 0)
114da2e3ebdSchin 
115da2e3ebdSchin #ifdef D_TYPE
116da2e3ebdSchin #define ISTYPE(f,t)	((f)->type == (t))
117da2e3ebdSchin #define TYPE(f,t)	((f)->type = (t))
118da2e3ebdSchin #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)))))
119da2e3ebdSchin #else
120da2e3ebdSchin #undef	DT_UNKNOWN
121da2e3ebdSchin #define DT_UNKNOWN	0
122da2e3ebdSchin #undef	DT_LNK
123da2e3ebdSchin #define DT_LNK		1
124da2e3ebdSchin #define ISTYPE(f,t)	((t)==DT_UNKNOWN)
125da2e3ebdSchin #define TYPE(f,d)
126da2e3ebdSchin #define SKIP(p,f)	((f)->fts_parent->must == 0 && SKIPLINK(p,f))
127da2e3ebdSchin #endif
128da2e3ebdSchin 
129da2e3ebdSchin #ifndef D_FILENO
130da2e3ebdSchin #define D_FILENO(d)	(1)
131da2e3ebdSchin #endif
132da2e3ebdSchin 
133da2e3ebdSchin /*
134da2e3ebdSchin  * NOTE: a malicious dir rename() could change .. underfoot so we
135da2e3ebdSchin  *	 must always verify; undef verify to enable the unsafe code
136da2e3ebdSchin  */
137da2e3ebdSchin 
138da2e3ebdSchin #define verify		1
139da2e3ebdSchin 
140da2e3ebdSchin /*
141da2e3ebdSchin  * FTS_NOSTAT requires a dir with
142da2e3ebdSchin  *	D_TYPE(&dirent_t)!=DT_UNKNOWN
143da2e3ebdSchin  *	    OR
144da2e3ebdSchin  *	st_nlink>=2
145da2e3ebdSchin  */
146da2e3ebdSchin 
147da2e3ebdSchin #define FTS_children_resume	1
148da2e3ebdSchin #define FTS_children_return	2
149da2e3ebdSchin #define FTS_error		3
150da2e3ebdSchin #define FTS_popstack		4
151da2e3ebdSchin #define FTS_popstack_resume	5
152da2e3ebdSchin #define FTS_popstack_return	6
153da2e3ebdSchin #define FTS_preorder		7
154da2e3ebdSchin #define FTS_preorder_resume	8
155da2e3ebdSchin #define FTS_preorder_return	9
156da2e3ebdSchin #define FTS_readdir		10
157da2e3ebdSchin #define FTS_terminal		11
158da2e3ebdSchin #define FTS_todo		12
159da2e3ebdSchin #define FTS_top_return		13
160da2e3ebdSchin 
161da2e3ebdSchin typedef int (*Notify_f)(FTS*, FTSENT*, void*);
162da2e3ebdSchin 
163da2e3ebdSchin typedef struct Notify_s
164da2e3ebdSchin {
165da2e3ebdSchin 	struct Notify_s*	next;
166da2e3ebdSchin 	Notify_f		notifyf;
167da2e3ebdSchin 	void*			context;
168da2e3ebdSchin } Notify_t;
169da2e3ebdSchin 
170da2e3ebdSchin static Notify_t*		notify;
171da2e3ebdSchin 
172da2e3ebdSchin /*
173da2e3ebdSchin  * allocate an FTSENT node
174da2e3ebdSchin  */
175da2e3ebdSchin 
176da2e3ebdSchin static FTSENT*
node(FTS * fts,FTSENT * parent,register char * name,register size_t namelen)17734f9b3eeSRoland Mainz node(FTS* fts, FTSENT* parent, register char* name, register size_t namelen)
178da2e3ebdSchin {
179da2e3ebdSchin 	register FTSENT*	f;
18034f9b3eeSRoland Mainz 	register size_t		n;
181da2e3ebdSchin 
182da2e3ebdSchin 	if (fts->free && namelen < MINNAME)
183da2e3ebdSchin 	{
184da2e3ebdSchin 		f = fts->free;
185da2e3ebdSchin 		fts->free = f->fts_link;
186da2e3ebdSchin 	}
187da2e3ebdSchin 	else
188da2e3ebdSchin 	{
189da2e3ebdSchin 		n = (namelen < MINNAME ? MINNAME : namelen + 1) - sizeof(int);
190da2e3ebdSchin 		if (!(f = newof(0, FTSENT, 1, n)))
191da2e3ebdSchin 		{
192da2e3ebdSchin 			fts->fts_errno = errno;
193da2e3ebdSchin 			fts->state = FTS_error;
194da2e3ebdSchin 			return 0;
195da2e3ebdSchin 		}
196da2e3ebdSchin 		f->fts = fts;
197da2e3ebdSchin 	}
198da2e3ebdSchin 	TYPE(f, DT_UNKNOWN);
199da2e3ebdSchin 	f->status = 0;
200da2e3ebdSchin 	f->symlink = 0;
201da2e3ebdSchin 	f->fts_level = (f->fts_parent = parent)->fts_level + 1;
20234f9b3eeSRoland Mainz #if __OBSOLETE__ < 20140101
20334f9b3eeSRoland Mainz 	f->_fts_level = (short)f->fts_level;
20434f9b3eeSRoland Mainz #endif
205da2e3ebdSchin 	f->fts_link = 0;
206da2e3ebdSchin 	f->fts_pointer = 0;
207da2e3ebdSchin 	f->fts_number = 0;
208da2e3ebdSchin 	f->fts_errno = 0;
209da2e3ebdSchin 	f->fts_namelen = namelen;
21034f9b3eeSRoland Mainz #if __OBSOLETE__ < 20140101
21134f9b3eeSRoland Mainz 	f->_fts_namelen = (unsigned short)f->fts_namelen;
21234f9b3eeSRoland Mainz #endif
213da2e3ebdSchin 	f->fts_name = f->name;
214da2e3ebdSchin 	f->fts_statp = &f->statb;
215da2e3ebdSchin 	memcpy(f->fts_name, name, namelen + 1);
216da2e3ebdSchin 	return f;
217da2e3ebdSchin }
218da2e3ebdSchin 
219da2e3ebdSchin /*
220da2e3ebdSchin  * compare directories by device/inode
221da2e3ebdSchin  */
222da2e3ebdSchin 
223da2e3ebdSchin static int
statcmp(FTSENT * const * pf1,FTSENT * const * pf2)224da2e3ebdSchin statcmp(FTSENT* const* pf1, FTSENT* const* pf2)
225da2e3ebdSchin {
226da2e3ebdSchin 	register const FTSENT*	f1 = *pf1;
227da2e3ebdSchin 	register const FTSENT*	f2 = *pf2;
228da2e3ebdSchin 
229da2e3ebdSchin 	if (f1->statb.st_ino < f2->statb.st_ino)
230da2e3ebdSchin 		return -1;
231da2e3ebdSchin 	if (f1->statb.st_ino > f2->statb.st_ino)
232da2e3ebdSchin 		return 1;
233da2e3ebdSchin 	if (f1->statb.st_dev < f2->statb.st_dev)
234da2e3ebdSchin 		return -1;
235da2e3ebdSchin 	if (f1->statb.st_dev > f2->statb.st_dev)
236da2e3ebdSchin 		return 1;
237da2e3ebdSchin 
238da2e3ebdSchin 	/*
239da2e3ebdSchin 	 * hack for NFS where <dev,ino> may not uniquely identify objects
240da2e3ebdSchin 	 */
241da2e3ebdSchin 
242da2e3ebdSchin 	if (f1->statb.st_mtime < f2->statb.st_mtime)
243da2e3ebdSchin 		return -1;
244da2e3ebdSchin 	if (f1->statb.st_mtime > f2->statb.st_mtime)
245da2e3ebdSchin 		return 1;
246da2e3ebdSchin 	return 0;
247da2e3ebdSchin }
248da2e3ebdSchin 
249da2e3ebdSchin /*
250da2e3ebdSchin  * search trees with top-down splaying (a la Tarjan and Sleator)
251da2e3ebdSchin  * when used for insertion sort, this implements a stable sort
252da2e3ebdSchin  */
253da2e3ebdSchin 
254da2e3ebdSchin #define RROTATE(r)	(t = r->left, r->left = t->right, t->right = r, r = t)
255da2e3ebdSchin #define LROTATE(r)	(t = r->right, r->right = t->left, t->left = r, r = t)
256da2e3ebdSchin 
257da2e3ebdSchin static FTSENT*
search(FTSENT * e,FTSENT * root,int (* comparf)(FTSENT * const *,FTSENT * const *),int insert)258da2e3ebdSchin search(FTSENT* e, FTSENT* root, int(*comparf)(FTSENT* const*, FTSENT* const*), int insert)
259da2e3ebdSchin {
260da2e3ebdSchin 	register int		cmp;
261da2e3ebdSchin 	register FTSENT*	t;
262da2e3ebdSchin 	register FTSENT*	left;
263da2e3ebdSchin 	register FTSENT*	right;
264da2e3ebdSchin 	register FTSENT*	lroot;
265da2e3ebdSchin 	register FTSENT*	rroot;
266da2e3ebdSchin 
267da2e3ebdSchin 	left = right = lroot = rroot = 0;
268da2e3ebdSchin 	while (root)
269da2e3ebdSchin 	{
270da2e3ebdSchin 		if (!(cmp = (*comparf)(&e, &root)) && !insert)
271da2e3ebdSchin 			break;
272da2e3ebdSchin 		if (cmp < 0)
273da2e3ebdSchin 		{
274da2e3ebdSchin 			/*
275da2e3ebdSchin 			 * this is the left zig-zig case
276da2e3ebdSchin 			 */
277da2e3ebdSchin 
278da2e3ebdSchin 			if (root->left && (cmp = (*comparf)(&e, &root->left)) <= 0)
279da2e3ebdSchin 			{
280da2e3ebdSchin 				RROTATE(root);
281da2e3ebdSchin 				if (!cmp && !insert)
282da2e3ebdSchin 					break;
283da2e3ebdSchin 			}
284da2e3ebdSchin 
285da2e3ebdSchin 			/*
286da2e3ebdSchin 			 * stick all things > e to the right tree
287da2e3ebdSchin 			 */
288da2e3ebdSchin 
289da2e3ebdSchin 			if (right)
290da2e3ebdSchin 				right->left = root;
291da2e3ebdSchin 			else
292da2e3ebdSchin 				rroot = root;
293da2e3ebdSchin 			right = root;
294da2e3ebdSchin 			root = root->left;
295da2e3ebdSchin 			right->left = 0;
296da2e3ebdSchin 		}
297da2e3ebdSchin 		else
298da2e3ebdSchin 		{
299da2e3ebdSchin 			/*
300da2e3ebdSchin 			 * this is the right zig-zig case
301da2e3ebdSchin 			 */
302da2e3ebdSchin 
303da2e3ebdSchin 			if (root->right && (cmp = (*comparf)(&e, &root->right)) >= 0)
304da2e3ebdSchin 			{
305da2e3ebdSchin 				LROTATE(root);
306da2e3ebdSchin 				if (!cmp && !insert)
307da2e3ebdSchin 					break;
308da2e3ebdSchin 			}
309da2e3ebdSchin 
310da2e3ebdSchin 			/*
311da2e3ebdSchin 			 * stick all things <= e to the left tree
312da2e3ebdSchin 			 */
313da2e3ebdSchin 
314da2e3ebdSchin 			if (left)
315da2e3ebdSchin 				left->right = root;
316da2e3ebdSchin 			else
317da2e3ebdSchin 				lroot = root;
318da2e3ebdSchin 			left = root;
319da2e3ebdSchin 			root = root->right;
320da2e3ebdSchin 			left->right = 0;
321da2e3ebdSchin 		}
322da2e3ebdSchin 	}
323da2e3ebdSchin 	if (!root)
324da2e3ebdSchin 		root = e;
325da2e3ebdSchin 	else
326da2e3ebdSchin 	{
327da2e3ebdSchin 		if (right)
328da2e3ebdSchin 			right->left = root->right;
329da2e3ebdSchin 		else
330da2e3ebdSchin 			rroot = root->right;
331da2e3ebdSchin 		if (left)
332da2e3ebdSchin 			left->right = root->left;
333da2e3ebdSchin 		else
334da2e3ebdSchin 			lroot = root->left;
335da2e3ebdSchin 	}
336da2e3ebdSchin 	root->left = lroot;
337da2e3ebdSchin 	root->right = rroot;
338da2e3ebdSchin 	return root;
339da2e3ebdSchin }
340da2e3ebdSchin 
341da2e3ebdSchin /*
342da2e3ebdSchin  * delete the root element from the tree
343da2e3ebdSchin  */
344da2e3ebdSchin 
345da2e3ebdSchin static FTSENT*
deleteroot(register FTSENT * root)346da2e3ebdSchin deleteroot(register FTSENT* root)
347da2e3ebdSchin {
348da2e3ebdSchin 	register FTSENT*	t;
349da2e3ebdSchin 	register FTSENT*	left;
350da2e3ebdSchin 	register FTSENT*	right;
351da2e3ebdSchin 
352da2e3ebdSchin 	right = root->right;
353da2e3ebdSchin 	if (!(left = root->left))
354da2e3ebdSchin 		root = right;
355da2e3ebdSchin 	else
356da2e3ebdSchin 	{
357da2e3ebdSchin 		while (left->right)
358da2e3ebdSchin 			LROTATE(left);
359da2e3ebdSchin 		left->right = right;
360da2e3ebdSchin 		root = left;
361da2e3ebdSchin 	}
362da2e3ebdSchin 	return root;
363da2e3ebdSchin }
364da2e3ebdSchin 
365da2e3ebdSchin /*
366da2e3ebdSchin  * generate ordered fts_link list from binary tree at root
367da2e3ebdSchin  * FTSENT.stack instead of recursion to avoid blowing the real
368da2e3ebdSchin  * stack on big directories
369da2e3ebdSchin  */
370da2e3ebdSchin 
371da2e3ebdSchin static void
getlist(register FTSENT ** top,register FTSENT ** bot,register FTSENT * root)372da2e3ebdSchin getlist(register FTSENT** top, register FTSENT** bot, register FTSENT* root)
373da2e3ebdSchin {
374da2e3ebdSchin 	register FTSENT*	stack = 0;
375da2e3ebdSchin 
376da2e3ebdSchin 	for (;;)
377da2e3ebdSchin 	{
378da2e3ebdSchin 		if (root->left)
379da2e3ebdSchin 		{
380da2e3ebdSchin 			root->stack = stack;
381da2e3ebdSchin 			stack = root;
382da2e3ebdSchin 			root = root->left;
383da2e3ebdSchin 		}
384da2e3ebdSchin 		else
385da2e3ebdSchin 		{
386da2e3ebdSchin 			for (;;)
387da2e3ebdSchin 			{
388da2e3ebdSchin 				if (*top)
389da2e3ebdSchin 					*bot = (*bot)->fts_link = root;
390da2e3ebdSchin 				else
391da2e3ebdSchin 					*bot = *top = root;
392da2e3ebdSchin 				if (root->right)
393da2e3ebdSchin 				{
394da2e3ebdSchin 					root = root->right;
395da2e3ebdSchin 					break;
396da2e3ebdSchin 				}
397da2e3ebdSchin 				if (!(root = stack))
39834f9b3eeSRoland Mainz 				{
39934f9b3eeSRoland Mainz 					(*bot)->fts_link = 0;
400da2e3ebdSchin 					return;
40134f9b3eeSRoland Mainz 				}
402da2e3ebdSchin 				stack = stack->stack;
403da2e3ebdSchin 			}
404da2e3ebdSchin 		}
405da2e3ebdSchin 	}
406da2e3ebdSchin }
407da2e3ebdSchin 
408da2e3ebdSchin /*
409da2e3ebdSchin  * set directory when curdir is lost in space
410da2e3ebdSchin  */
411da2e3ebdSchin 
412da2e3ebdSchin static int
setdir(register char * home,register char * path)413da2e3ebdSchin setdir(register char* home, register char* path)
414da2e3ebdSchin {
415da2e3ebdSchin 	register int	cdrv;
416da2e3ebdSchin 
417da2e3ebdSchin 	if (path[0] == '/')
418da2e3ebdSchin 		cdrv = pathcd(path, NiL);
419da2e3ebdSchin 	else
420da2e3ebdSchin 	{
421da2e3ebdSchin 		/*
422da2e3ebdSchin 		 * note that path and home are in the same buffer
423da2e3ebdSchin 		 */
424da2e3ebdSchin 
425da2e3ebdSchin 		path[-1] = '/';
426da2e3ebdSchin 		cdrv = pathcd(home, NiL);
427da2e3ebdSchin 		path[-1] = 0;
428da2e3ebdSchin 	}
429da2e3ebdSchin 	if (cdrv < 0)
430da2e3ebdSchin 		pathcd(home, NiL);
431da2e3ebdSchin 	return cdrv;
432da2e3ebdSchin }
433da2e3ebdSchin 
434da2e3ebdSchin /*
435da2e3ebdSchin  * set to parent dir
436da2e3ebdSchin  */
437da2e3ebdSchin 
438da2e3ebdSchin static int
setpdir(register char * home,register char * path,register char * base)439da2e3ebdSchin setpdir(register char* home, register char* path, register char* base)
440da2e3ebdSchin {
441da2e3ebdSchin 	register int	c;
442da2e3ebdSchin 	register int	cdrv;
443da2e3ebdSchin 
444da2e3ebdSchin 	if (base > path)
445da2e3ebdSchin 	{
446da2e3ebdSchin 		c = base[0];
447da2e3ebdSchin 		base[0] = 0;
448da2e3ebdSchin 		cdrv = setdir(home, path);
449da2e3ebdSchin 		base[0] = c;
450da2e3ebdSchin 	}
451da2e3ebdSchin 	else
452da2e3ebdSchin 		cdrv = pathcd(home, NiL);
453da2e3ebdSchin 	return cdrv;
454da2e3ebdSchin }
455da2e3ebdSchin 
456da2e3ebdSchin /*
457da2e3ebdSchin  * pop a set of directories
458da2e3ebdSchin  */
459da2e3ebdSchin static int
popdirs(FTS * fts)460da2e3ebdSchin popdirs(FTS* fts)
461da2e3ebdSchin {
462da2e3ebdSchin 	register FTSENT*f;
463da2e3ebdSchin 	register char*	s;
464da2e3ebdSchin 	register char*	e;
465da2e3ebdSchin #ifndef verify
466da2e3ebdSchin 	register int	verify;
467da2e3ebdSchin #endif
468da2e3ebdSchin 	struct stat	sb;
469da2e3ebdSchin 	char		buf[PATH_MAX];
470da2e3ebdSchin 
471da2e3ebdSchin 	if (!(f = fts->curdir) || f->fts_level < 0)
472da2e3ebdSchin 		return -1;
473da2e3ebdSchin 	e = buf + sizeof(buf) - 4;
474da2e3ebdSchin #ifndef verify
475da2e3ebdSchin 	verify = 0;
476da2e3ebdSchin #endif
477da2e3ebdSchin 	while (fts->nd > 0)
478da2e3ebdSchin 	{
479da2e3ebdSchin 		for (s = buf; s < e && fts->nd > 0; fts->nd--)
480da2e3ebdSchin 		{
481da2e3ebdSchin 			if (fts->pwd)
482da2e3ebdSchin 			{
483da2e3ebdSchin #ifndef verify
484da2e3ebdSchin 				verify |= fts->pwd->symlink;
485da2e3ebdSchin #endif
486da2e3ebdSchin 				fts->pwd = fts->pwd->pwd;
487da2e3ebdSchin 			}
488da2e3ebdSchin 			*s++ = '.';
489da2e3ebdSchin 			*s++ = '.';
490da2e3ebdSchin 			*s++ = '/';
491da2e3ebdSchin 		}
492da2e3ebdSchin 		*s = 0;
493da2e3ebdSchin 		if (chdir(buf))
494da2e3ebdSchin 			return -1;
495da2e3ebdSchin 	}
496da2e3ebdSchin 	return (verify && (stat(".", &sb) < 0 || !SAME(&sb, f->fts_statp))) ? -1 : 0;
497da2e3ebdSchin }
498da2e3ebdSchin 
499da2e3ebdSchin /*
500da2e3ebdSchin  * initialize st from path and fts_info from st
501da2e3ebdSchin  */
502da2e3ebdSchin 
503da2e3ebdSchin static int
info(FTS * fts,register FTSENT * f,const char * path,struct stat * sp,int flags)504da2e3ebdSchin info(FTS* fts, register FTSENT* f, const char* path, struct stat* sp, int flags)
505da2e3ebdSchin {
506da2e3ebdSchin 	if (path)
507da2e3ebdSchin 	{
508da2e3ebdSchin #ifdef S_ISLNK
509da2e3ebdSchin 		if (!f->symlink && (ISTYPE(f, DT_UNKNOWN) || ISTYPE(f, DT_LNK)))
510da2e3ebdSchin 		{
511da2e3ebdSchin 			if (lstat(path, sp) < 0)
512da2e3ebdSchin 				goto bad;
513da2e3ebdSchin 		}
514da2e3ebdSchin 		else
515da2e3ebdSchin #endif
516da2e3ebdSchin 			if (stat(path, sp) < 0)
517da2e3ebdSchin 				goto bad;
518da2e3ebdSchin 	}
519da2e3ebdSchin #ifdef S_ISLNK
520da2e3ebdSchin  again:
521da2e3ebdSchin #endif
522da2e3ebdSchin 	if (S_ISDIR(sp->st_mode))
523da2e3ebdSchin 	{
524da2e3ebdSchin 		if ((flags & FTS_NOSTAT) && !fts->fs3d)
525da2e3ebdSchin 		{
526da2e3ebdSchin 			f->fts_parent->nlink--;
527da2e3ebdSchin #ifdef D_TYPE
528da2e3ebdSchin 			if ((f->nlink = sp->st_nlink) < 2)
5297c2fbfb3SApril Chin 			{
5307c2fbfb3SApril Chin 				f->must = 2;
531da2e3ebdSchin 				f->nlink = 2;
5327c2fbfb3SApril Chin 			}
5337c2fbfb3SApril Chin 			else
5347c2fbfb3SApril Chin 				f->must = 0;
535da2e3ebdSchin #else
536da2e3ebdSchin 			if ((f->nlink = sp->st_nlink) >= 2)
537da2e3ebdSchin 				f->must = 1;
538da2e3ebdSchin 			else
539da2e3ebdSchin 				f->must = 2;
540da2e3ebdSchin #endif
541da2e3ebdSchin 		}
542da2e3ebdSchin 		else
543da2e3ebdSchin 			f->must = 2;
544da2e3ebdSchin 		TYPE(f, DT_DIR);
545da2e3ebdSchin 		f->fts_info = FTS_D;
546da2e3ebdSchin 	}
547da2e3ebdSchin #ifdef S_ISLNK
548da2e3ebdSchin 	else if (S_ISLNK((sp)->st_mode))
549da2e3ebdSchin 	{
550da2e3ebdSchin 		struct stat	sb;
551da2e3ebdSchin 
552da2e3ebdSchin 		f->symlink = 1;
553*b30d1939SAndy Fiddaman 		if (flags & FTS_PHYSICAL)
554*b30d1939SAndy Fiddaman 		{
555*b30d1939SAndy Fiddaman 			TYPE(f, DT_LNK);
556*b30d1939SAndy Fiddaman 			f->fts_info = FTS_SL;
557*b30d1939SAndy Fiddaman 		}
558*b30d1939SAndy Fiddaman 		else if (stat(path, &sb) >= 0)
559da2e3ebdSchin 		{
560da2e3ebdSchin 			*sp = sb;
561da2e3ebdSchin 			flags = FTS_PHYSICAL;
562da2e3ebdSchin 			goto again;
563da2e3ebdSchin 		}
564*b30d1939SAndy Fiddaman 		else
565*b30d1939SAndy Fiddaman 		{
566*b30d1939SAndy Fiddaman 			TYPE(f, DT_LNK);
567*b30d1939SAndy Fiddaman 			f->fts_info = FTS_SLNONE;
568*b30d1939SAndy Fiddaman 		}
569da2e3ebdSchin 	}
570da2e3ebdSchin #endif
571da2e3ebdSchin 	else
572da2e3ebdSchin 	{
573da2e3ebdSchin 		TYPE(f, DT_REG);
574da2e3ebdSchin 		f->fts_info = FTS_F;
575da2e3ebdSchin 	}
576da2e3ebdSchin 	return 0;
577da2e3ebdSchin  bad:
578da2e3ebdSchin 	TYPE(f, DT_UNKNOWN);
579da2e3ebdSchin 	f->fts_info = FTS_NS;
580da2e3ebdSchin 	return -1;
581da2e3ebdSchin }
582da2e3ebdSchin 
583da2e3ebdSchin /*
584da2e3ebdSchin  * get top list of elements to process
58534f9b3eeSRoland Mainz  * ordering delayed until first fts_read()
58634f9b3eeSRoland Mainz  * to give caller a chance to set fts->handle
587da2e3ebdSchin  */
588da2e3ebdSchin 
589da2e3ebdSchin static FTSENT*
toplist(FTS * fts,register char * const * pathnames)590da2e3ebdSchin toplist(FTS* fts, register char* const* pathnames)
591da2e3ebdSchin {
592da2e3ebdSchin 	register char*		path;
593da2e3ebdSchin 	register FTSENT*	f;
59434f9b3eeSRoland Mainz 	register FTSENT*	top;
59534f9b3eeSRoland Mainz 	register FTSENT*	bot;
596da2e3ebdSchin 	int			physical;
597da2e3ebdSchin 	int			metaphysical;
598da2e3ebdSchin 	char*			s;
599da2e3ebdSchin 	struct stat		st;
600da2e3ebdSchin 
601da2e3ebdSchin 	if (fts->flags & FTS_NOSEEDOTDIR)
602da2e3ebdSchin 		fts->flags &= ~FTS_SEEDOTDIR;
603da2e3ebdSchin 	physical = (fts->flags & FTS_PHYSICAL);
604da2e3ebdSchin 	metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
60534f9b3eeSRoland Mainz 	top = bot = 0;
606da2e3ebdSchin 	while (path = *pathnames++)
607da2e3ebdSchin 	{
608da2e3ebdSchin 		/*
609da2e3ebdSchin 		 * make elements
610da2e3ebdSchin 		 */
611da2e3ebdSchin 
612da2e3ebdSchin 		if (!(f = node(fts, fts->parent, path, strlen(path))))
613da2e3ebdSchin 			break;
614da2e3ebdSchin 		path = f->fts_name;
615da2e3ebdSchin 		if (!physical)
616*b30d1939SAndy Fiddaman 			f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, strlen(path) + 1, 0) - path);
617da2e3ebdSchin 		else if (*path != '.')
618da2e3ebdSchin 		{
619da2e3ebdSchin 			f->fts_namelen = strlen(path);
620da2e3ebdSchin 			fts->flags |= FTS_SEEDOTDIR;
621da2e3ebdSchin 		}
622da2e3ebdSchin 		else
623da2e3ebdSchin 		{
624da2e3ebdSchin 			if (fts->flags & FTS_NOSEEDOTDIR)
625da2e3ebdSchin 			{
626da2e3ebdSchin 				fts->flags &= ~FTS_SEEDOTDIR;
627da2e3ebdSchin 				s = path;
628da2e3ebdSchin 				while (*s++ == '.' && *s++ == '/')
629da2e3ebdSchin 				{
630da2e3ebdSchin 					while (*s == '/')
631da2e3ebdSchin 						s++;
632da2e3ebdSchin 					if (!*s)
633da2e3ebdSchin 						break;
634da2e3ebdSchin 					path = f->fts_name;
635da2e3ebdSchin 					while (*path++ = *s++);
636da2e3ebdSchin 					path = f->fts_name;
637da2e3ebdSchin 				}
638da2e3ebdSchin 			}
639da2e3ebdSchin 			else
640da2e3ebdSchin 				fts->flags |= FTS_SEEDOTDIR;
641da2e3ebdSchin 			for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
642da2e3ebdSchin 			*s = 0;
643da2e3ebdSchin 			f->fts_namelen = s - path;
644da2e3ebdSchin 		}
64534f9b3eeSRoland Mainz #if __OBSOLETE__ < 20140101
64634f9b3eeSRoland Mainz 		f->_fts_namelen = (unsigned short)f->fts_namelen;
64734f9b3eeSRoland Mainz #endif
648da2e3ebdSchin 		if (!*path)
649da2e3ebdSchin 		{
650da2e3ebdSchin 			errno = ENOENT;
651da2e3ebdSchin 			f->fts_info = FTS_NS;
652da2e3ebdSchin 		}
653da2e3ebdSchin 		else
65434f9b3eeSRoland Mainz 			info(fts, f, path, f->fts_statp, fts->flags);
655da2e3ebdSchin #ifdef S_ISLNK
656da2e3ebdSchin 
657da2e3ebdSchin 		/*
658da2e3ebdSchin 		 * don't let any standards committee get
659da2e3ebdSchin 		 * away with calling your idea a hack
660da2e3ebdSchin 		 */
661da2e3ebdSchin 
662*b30d1939SAndy Fiddaman 		if (metaphysical && f->fts_info == FTS_SL)
663da2e3ebdSchin 		{
664*b30d1939SAndy Fiddaman 			if (stat(path, &st) >= 0)
665*b30d1939SAndy Fiddaman 			{
666*b30d1939SAndy Fiddaman 				*f->fts_statp = st;
667*b30d1939SAndy Fiddaman 				info(fts, f, NiL, f->fts_statp, 0);
668*b30d1939SAndy Fiddaman 			}
669*b30d1939SAndy Fiddaman 			else
670*b30d1939SAndy Fiddaman 				f->fts_info = FTS_SLNONE;
671da2e3ebdSchin 		}
672da2e3ebdSchin #endif
67334f9b3eeSRoland Mainz 		if (bot)
674da2e3ebdSchin 		{
675da2e3ebdSchin 			bot->fts_link = f;
676da2e3ebdSchin 			bot = f;
677da2e3ebdSchin 		}
678da2e3ebdSchin 		else
679da2e3ebdSchin 			top = bot = f;
680da2e3ebdSchin 	}
681da2e3ebdSchin 	return top;
682da2e3ebdSchin }
683da2e3ebdSchin 
68434f9b3eeSRoland Mainz /*
68534f9b3eeSRoland Mainz  * order fts->todo if fts->comparf != 0
68634f9b3eeSRoland Mainz  */
68734f9b3eeSRoland Mainz 
68834f9b3eeSRoland Mainz static void
order(FTS * fts)68934f9b3eeSRoland Mainz order(FTS* fts)
69034f9b3eeSRoland Mainz {
69134f9b3eeSRoland Mainz 	register FTSENT*	f;
69234f9b3eeSRoland Mainz 	register FTSENT*	root;
69334f9b3eeSRoland Mainz 	FTSENT*			top;
69434f9b3eeSRoland Mainz 	FTSENT*			bot;
69534f9b3eeSRoland Mainz 
69634f9b3eeSRoland Mainz 	top = bot = root = 0;
69734f9b3eeSRoland Mainz 	for (f = fts->todo; f; f = f->fts_link)
69834f9b3eeSRoland Mainz 		root = search(f, root, fts->comparf, 1);
69934f9b3eeSRoland Mainz 	getlist(&top, &bot, root);
70034f9b3eeSRoland Mainz 	fts->todo = top;
70134f9b3eeSRoland Mainz }
70234f9b3eeSRoland Mainz 
703da2e3ebdSchin /*
704da2e3ebdSchin  * resize the path buffer
705da2e3ebdSchin  * note that free() is not used because we may need to chdir(fts->home)
706da2e3ebdSchin  * if there isn't enough space to continue
707da2e3ebdSchin  */
708da2e3ebdSchin 
709da2e3ebdSchin static int
resize(register FTS * fts,size_t inc)71034f9b3eeSRoland Mainz resize(register FTS* fts, size_t inc)
711da2e3ebdSchin {
712da2e3ebdSchin 	register char*	old;
713da2e3ebdSchin 	register char*	newp;
71434f9b3eeSRoland Mainz 	register size_t	n_old;
715da2e3ebdSchin 
716da2e3ebdSchin 	/*
717da2e3ebdSchin 	 * add space for "/." used in testing FTS_DNX
718da2e3ebdSchin 	 */
719da2e3ebdSchin 
720da2e3ebdSchin 	n_old = fts->homesize;
721da2e3ebdSchin 	fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
722da2e3ebdSchin 	if (!(newp = newof(0, char, fts->homesize, 0)))
723da2e3ebdSchin 	{
724da2e3ebdSchin 		fts->fts_errno = errno;
725da2e3ebdSchin 		fts->state = FTS_error;
726da2e3ebdSchin 		return -1;
727da2e3ebdSchin 	}
728da2e3ebdSchin 	old = fts->home;
729da2e3ebdSchin 	fts->home = newp;
730da2e3ebdSchin 	memcpy(newp, old, n_old);
731da2e3ebdSchin 	if (fts->endbuf)
732da2e3ebdSchin 		fts->endbuf = newp + fts->homesize - 4;
733da2e3ebdSchin 	if (fts->path)
734da2e3ebdSchin 		fts->path = newp + (fts->path - old);
735da2e3ebdSchin 	if (fts->base)
736da2e3ebdSchin 		fts->base = newp + (fts->base - old);
737da2e3ebdSchin 	free(old);
738da2e3ebdSchin 	return 0;
739da2e3ebdSchin }
740da2e3ebdSchin 
741da2e3ebdSchin /*
742da2e3ebdSchin  * open a new fts stream on pathnames
743da2e3ebdSchin  */
744da2e3ebdSchin 
745da2e3ebdSchin FTS*
fts_open(char * const * pathnames,int flags,int (* comparf)(FTSENT * const *,FTSENT * const *))746da2e3ebdSchin fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
747da2e3ebdSchin {
748da2e3ebdSchin 	register FTS*	fts;
749da2e3ebdSchin 
750da2e3ebdSchin 	if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
751da2e3ebdSchin 		return 0;
752da2e3ebdSchin 	fts->flags = flags;
753da2e3ebdSchin 	fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
754da2e3ebdSchin 	fts->comparf = comparf;
755da2e3ebdSchin 	fts->fs3d = fs3d(FS3D_TEST);
756da2e3ebdSchin 
757da2e3ebdSchin 	/*
758da2e3ebdSchin 	 * set up the path work buffer
759da2e3ebdSchin 	 */
760da2e3ebdSchin 
761da2e3ebdSchin 	fts->homesize = 2 * PATH_MAX;
762da2e3ebdSchin 	for (;;)
763da2e3ebdSchin 	{
764da2e3ebdSchin 		if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
765da2e3ebdSchin 		{
766da2e3ebdSchin 			free(fts);
767da2e3ebdSchin 			return 0;
768da2e3ebdSchin 		}
769da2e3ebdSchin 		if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
770da2e3ebdSchin 			break;
771da2e3ebdSchin 		if (errno == ERANGE)
772da2e3ebdSchin 			fts->homesize += PATH_MAX;
773da2e3ebdSchin 		else
774da2e3ebdSchin 			fts->cd = 1;
775da2e3ebdSchin 	}
776da2e3ebdSchin 	fts->endbuf = fts->home + fts->homesize - 4;
777da2e3ebdSchin 
778da2e3ebdSchin 	/*
779da2e3ebdSchin 	 * initialize the tippity-top
780da2e3ebdSchin 	 */
781da2e3ebdSchin 
782da2e3ebdSchin 	fts->parent = (FTSENT*)(fts + 1);
783da2e3ebdSchin 	fts->parent->fts_info = FTS_D;
784da2e3ebdSchin 	memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
785da2e3ebdSchin 	fts->parent->fts_level = -1;
78634f9b3eeSRoland Mainz #if __OBSOLETE__ < 20140101
78734f9b3eeSRoland Mainz 	fts->parent->_fts_level = (short)fts->parent->fts_level;
78834f9b3eeSRoland Mainz #endif
789da2e3ebdSchin 	fts->parent->fts_statp = &fts->parent->statb;
790da2e3ebdSchin 	fts->parent->must = 2;
791da2e3ebdSchin 	fts->parent->type = DT_UNKNOWN;
792da2e3ebdSchin 	fts->path = fts->home + strlen(fts->home) + 1;
793da2e3ebdSchin 
794da2e3ebdSchin 	/*
795da2e3ebdSchin 	 * make the list of top elements
796da2e3ebdSchin 	 */
797da2e3ebdSchin 
798da2e3ebdSchin 	if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
799da2e3ebdSchin 	{
800da2e3ebdSchin 		char*	v[2];
801da2e3ebdSchin 
802da2e3ebdSchin 		v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
803da2e3ebdSchin 		v[1] = 0;
804da2e3ebdSchin 		fts->todo = toplist(fts, v);
805da2e3ebdSchin 	}
806da2e3ebdSchin 	else
807da2e3ebdSchin 		fts->todo = toplist(fts, pathnames);
808*b30d1939SAndy Fiddaman #if _HUH_1997_01_07
809da2e3ebdSchin 	if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
810*b30d1939SAndy Fiddaman #else
811*b30d1939SAndy Fiddaman 	if (!fts->todo)
812*b30d1939SAndy Fiddaman #endif
813da2e3ebdSchin 	{
814da2e3ebdSchin 		fts_close(fts);
815da2e3ebdSchin 		return 0;
816da2e3ebdSchin 	}
817da2e3ebdSchin 	return fts;
818da2e3ebdSchin }
819da2e3ebdSchin 
820da2e3ebdSchin /*
821da2e3ebdSchin  * return the next FTS entry
822da2e3ebdSchin  */
823da2e3ebdSchin 
824da2e3ebdSchin FTSENT*
fts_read(register FTS * fts)825da2e3ebdSchin fts_read(register FTS* fts)
826da2e3ebdSchin {
827da2e3ebdSchin 	register char*		s;
828da2e3ebdSchin 	register int		n;
829da2e3ebdSchin 	register FTSENT*	f;
830da2e3ebdSchin 	struct dirent*		d;
83134f9b3eeSRoland Mainz 	size_t			i;
832da2e3ebdSchin 	FTSENT*			t;
833da2e3ebdSchin 	Notify_t*		p;
834da2e3ebdSchin #ifdef verify
835da2e3ebdSchin 	struct stat		sb;
836da2e3ebdSchin #endif
837da2e3ebdSchin 
83834f9b3eeSRoland Mainz 	for (;;)
83934f9b3eeSRoland Mainz 		switch (fts->state)
84034f9b3eeSRoland Mainz 		{
841da2e3ebdSchin 
84234f9b3eeSRoland Mainz 		case FTS_top_return:
843da2e3ebdSchin 
84434f9b3eeSRoland Mainz 			f = fts->todo;
84534f9b3eeSRoland Mainz 			t = 0;
84634f9b3eeSRoland Mainz 			while (f)
84734f9b3eeSRoland Mainz 				if (f->status == FTS_SKIP)
848da2e3ebdSchin 				{
84934f9b3eeSRoland Mainz 					if (t)
85034f9b3eeSRoland Mainz 					{
85134f9b3eeSRoland Mainz 						t->fts_link = f->fts_link;
85234f9b3eeSRoland Mainz 						drop(fts, f);
85334f9b3eeSRoland Mainz 						f = t->fts_link;
85434f9b3eeSRoland Mainz 					}
85534f9b3eeSRoland Mainz 					else
85634f9b3eeSRoland Mainz 					{
85734f9b3eeSRoland Mainz 						fts->todo = f->fts_link;
85834f9b3eeSRoland Mainz 						drop(fts, f);
85934f9b3eeSRoland Mainz 						f = fts->todo;
86034f9b3eeSRoland Mainz 					}
861da2e3ebdSchin 				}
862da2e3ebdSchin 				else
863da2e3ebdSchin 				{
86434f9b3eeSRoland Mainz 					t = f;
86534f9b3eeSRoland Mainz 					f = f->fts_link;
866da2e3ebdSchin 				}
86734f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
868da2e3ebdSchin 
86934f9b3eeSRoland Mainz 		case 0:
870da2e3ebdSchin 
87134f9b3eeSRoland Mainz 			if (!fts->state && fts->comparf)
87234f9b3eeSRoland Mainz 				order(fts);
87334f9b3eeSRoland Mainz 			if (!(f = fts->todo))
87434f9b3eeSRoland Mainz 				return 0;
87534f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
876da2e3ebdSchin 
87734f9b3eeSRoland Mainz 		case FTS_todo:
878da2e3ebdSchin 
87934f9b3eeSRoland Mainz 			/*
88034f9b3eeSRoland Mainz 			 * process the top object on the stack
88134f9b3eeSRoland Mainz 			 */
882da2e3ebdSchin 
88334f9b3eeSRoland Mainz 			fts->root = fts->top = fts->bot = 0;
884da2e3ebdSchin 
88534f9b3eeSRoland Mainz 			/*
88634f9b3eeSRoland Mainz 			 * initialize the top level
88734f9b3eeSRoland Mainz 			 */
888da2e3ebdSchin 
88934f9b3eeSRoland Mainz 			if (f->fts_level == 0)
89034f9b3eeSRoland Mainz 			{
89134f9b3eeSRoland Mainz 				fts->parent->fts_number = f->fts_number;
89234f9b3eeSRoland Mainz 				fts->parent->fts_pointer = f->fts_pointer;
89334f9b3eeSRoland Mainz 				fts->parent->fts_statp = f->fts_statp;
89434f9b3eeSRoland Mainz 				fts->parent->statb = *f->fts_statp;
89534f9b3eeSRoland Mainz 				f->fts_parent = fts->parent;
89634f9b3eeSRoland Mainz 				fts->diroot = 0;
89734f9b3eeSRoland Mainz 				if (fts->cd == 0)
89834f9b3eeSRoland Mainz 					pathcd(fts->home, NiL);
89934f9b3eeSRoland Mainz 				else if (fts->cd < 0)
90034f9b3eeSRoland Mainz 					fts->cd = 0;
90134f9b3eeSRoland Mainz 				fts->pwd = f->fts_parent;
90234f9b3eeSRoland Mainz 				fts->curdir = fts->cd ? 0 : f->fts_parent;
90334f9b3eeSRoland Mainz 				*(fts->base = fts->path) = 0;
90434f9b3eeSRoland Mainz 			}
905da2e3ebdSchin 
90634f9b3eeSRoland Mainz 			/*
90734f9b3eeSRoland Mainz 			 * chdir to parent if asked for
90834f9b3eeSRoland Mainz 			 */
909da2e3ebdSchin 
91034f9b3eeSRoland Mainz 			if (fts->cd < 0)
91134f9b3eeSRoland Mainz 			{
91234f9b3eeSRoland Mainz 				fts->cd = setdir(fts->home, fts->path);
91334f9b3eeSRoland Mainz 				fts->pwd = f->fts_parent;
91434f9b3eeSRoland Mainz 				fts->curdir = fts->cd ? 0 : f->fts_parent;
91534f9b3eeSRoland Mainz 			}
916da2e3ebdSchin 
91734f9b3eeSRoland Mainz 			/*
91834f9b3eeSRoland Mainz 			 * add object's name to the path
91934f9b3eeSRoland Mainz 			 */
920da2e3ebdSchin 
92134f9b3eeSRoland Mainz 			if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
92234f9b3eeSRoland Mainz 				return 0;
92334f9b3eeSRoland Mainz 			memcpy(fts->base, f->name, fts->baselen + 1);
92434f9b3eeSRoland Mainz 			fts->name = fts->cd ? fts->path : fts->base;
92534f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
926da2e3ebdSchin 
92734f9b3eeSRoland Mainz 		case FTS_preorder:
928da2e3ebdSchin 
92934f9b3eeSRoland Mainz 			/*
93034f9b3eeSRoland Mainz 			 * check for cycle and open dir
93134f9b3eeSRoland Mainz 			 */
932da2e3ebdSchin 
93334f9b3eeSRoland Mainz 			if (f->fts_info == FTS_D)
934da2e3ebdSchin 			{
93534f9b3eeSRoland Mainz 				if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
93634f9b3eeSRoland Mainz 				{
93734f9b3eeSRoland Mainz 					f->fts_info = FTS_DC;
93834f9b3eeSRoland Mainz 					f->fts_cycle = fts->diroot;
93934f9b3eeSRoland Mainz 				}
94034f9b3eeSRoland Mainz 				else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
94134f9b3eeSRoland Mainz 				{
94234f9b3eeSRoland Mainz 					/*
94334f9b3eeSRoland Mainz 					 * buffer is known to be large enough here!
94434f9b3eeSRoland Mainz 					 */
94534f9b3eeSRoland Mainz 
94634f9b3eeSRoland Mainz 					if (fts->base[fts->baselen - 1] != '/')
94734f9b3eeSRoland Mainz 						memcpy(fts->base + fts->baselen, "/.", 3);
94834f9b3eeSRoland Mainz 					if (!(fts->dir = opendir(fts->name)))
94934f9b3eeSRoland Mainz 						f->fts_info = FTS_DNX;
95034f9b3eeSRoland Mainz 					fts->base[fts->baselen] = 0;
95134f9b3eeSRoland Mainz 					if (!fts->dir && !(fts->dir = opendir(fts->name)))
95234f9b3eeSRoland Mainz 						f->fts_info = FTS_DNR;
95334f9b3eeSRoland Mainz 				}
954da2e3ebdSchin 			}
95534f9b3eeSRoland Mainz 			f->nd = f->fts_info & ~FTS_DNX;
95634f9b3eeSRoland Mainz 			if (f->nd || !(fts->flags & FTS_NOPREORDER))
957da2e3ebdSchin 			{
95834f9b3eeSRoland Mainz 				fts->current = f;
95934f9b3eeSRoland Mainz 				fts->link = f->fts_link;
96034f9b3eeSRoland Mainz 				f->fts_link = 0;
96134f9b3eeSRoland Mainz 				f->fts_path = PATH(fts, fts->path, f->fts_level);
96234f9b3eeSRoland Mainz 				f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
96334f9b3eeSRoland Mainz 				f->fts_accpath = ACCESS(fts, f);
96434f9b3eeSRoland Mainz 				fts->state = FTS_preorder_return;
96534f9b3eeSRoland Mainz 				goto note;
966da2e3ebdSchin 			}
96734f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
968da2e3ebdSchin 
96934f9b3eeSRoland Mainz 		case FTS_preorder_resume:
970da2e3ebdSchin 
97134f9b3eeSRoland Mainz 			/*
97234f9b3eeSRoland Mainz 			 * prune
97334f9b3eeSRoland Mainz 			 */
974da2e3ebdSchin 
97534f9b3eeSRoland Mainz 			if (!fts->dir || f->nd || f->status == FTS_SKIP)
976da2e3ebdSchin 			{
97734f9b3eeSRoland Mainz 				if (fts->dir)
97834f9b3eeSRoland Mainz 				{
97934f9b3eeSRoland Mainz 					closedir(fts->dir);
98034f9b3eeSRoland Mainz 					fts->dir = 0;
98134f9b3eeSRoland Mainz 				}
98234f9b3eeSRoland Mainz 				fts->state = FTS_popstack;
98334f9b3eeSRoland Mainz 				continue;
984da2e3ebdSchin 			}
985da2e3ebdSchin 
98634f9b3eeSRoland Mainz 			/*
98734f9b3eeSRoland Mainz 			 * FTS_D or FTS_DNX, about to read children
98834f9b3eeSRoland Mainz 			 */
989da2e3ebdSchin 
99034f9b3eeSRoland Mainz 			if (fts->cd == 0)
991da2e3ebdSchin 			{
99234f9b3eeSRoland Mainz 				if ((fts->cd = chdir(fts->name)) < 0)
99334f9b3eeSRoland Mainz 					pathcd(fts->home, NiL);
99434f9b3eeSRoland Mainz 				else if (fts->pwd != f)
995da2e3ebdSchin 				{
99634f9b3eeSRoland Mainz 					f->pwd = fts->pwd;
99734f9b3eeSRoland Mainz 					fts->pwd = f;
998da2e3ebdSchin 				}
99934f9b3eeSRoland Mainz 				fts->curdir = fts->cd < 0 ? 0 : f;
100034f9b3eeSRoland Mainz 			}
100134f9b3eeSRoland Mainz 			fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
100234f9b3eeSRoland Mainz 			fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
100334f9b3eeSRoland Mainz 			fts->dotdot = 0;
100434f9b3eeSRoland Mainz 			fts->endbase = fts->base + fts->baselen;
100534f9b3eeSRoland Mainz 			if (fts->endbase[-1] != '/')
100634f9b3eeSRoland Mainz 				*fts->endbase++ = '/';
100734f9b3eeSRoland Mainz 			fts->current = f;
100834f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
100934f9b3eeSRoland Mainz 
101034f9b3eeSRoland Mainz 		case FTS_readdir:
101134f9b3eeSRoland Mainz 
101234f9b3eeSRoland Mainz 			while (d = readdir(fts->dir))
101334f9b3eeSRoland Mainz 			{
101434f9b3eeSRoland Mainz 				s = d->d_name;
101534f9b3eeSRoland Mainz 				if (s[0] == '.')
1016da2e3ebdSchin 				{
101734f9b3eeSRoland Mainz 					if (s[1] == 0)
101834f9b3eeSRoland Mainz 					{
101934f9b3eeSRoland Mainz 						fts->current->nlink--;
102034f9b3eeSRoland Mainz 						if (!(fts->flags & FTS_SEEDOT))
102134f9b3eeSRoland Mainz 							continue;
102234f9b3eeSRoland Mainz 						n = 1;
102334f9b3eeSRoland Mainz 					}
102434f9b3eeSRoland Mainz 					else if (s[1] == '.' && s[2] == 0)
102534f9b3eeSRoland Mainz 					{
102634f9b3eeSRoland Mainz 						fts->current->nlink--;
102734f9b3eeSRoland Mainz 						if (fts->current->must == 1)
102834f9b3eeSRoland Mainz 							fts->current->must = 0;
102934f9b3eeSRoland Mainz 						if (!(fts->flags & FTS_SEEDOT))
103034f9b3eeSRoland Mainz 							continue;
103134f9b3eeSRoland Mainz 						n = 2;
103234f9b3eeSRoland Mainz 					}
103334f9b3eeSRoland Mainz 					else
103434f9b3eeSRoland Mainz 						n = 0;
1035da2e3ebdSchin 				}
1036da2e3ebdSchin 				else
1037da2e3ebdSchin 					n = 0;
1038da2e3ebdSchin 
103934f9b3eeSRoland Mainz 				/*
104034f9b3eeSRoland Mainz 				 * make a new entry
104134f9b3eeSRoland Mainz 				 */
1042da2e3ebdSchin 
104334f9b3eeSRoland Mainz 				i = D_NAMLEN(d);
104434f9b3eeSRoland Mainz 				if (!(f = node(fts, fts->current, s, i)))
1045da2e3ebdSchin 					return 0;
104634f9b3eeSRoland Mainz 				TYPE(f, D_TYPE(d));
104734f9b3eeSRoland Mainz 
1048da2e3ebdSchin 				/*
104934f9b3eeSRoland Mainz 				 * check for space
1050da2e3ebdSchin 				 */
1051da2e3ebdSchin 
105234f9b3eeSRoland Mainz 				if (i >= fts->endbuf - fts->endbase)
1053da2e3ebdSchin 				{
105434f9b3eeSRoland Mainz 		   	   		if (resize(fts, i))
105534f9b3eeSRoland Mainz 						return 0;
105634f9b3eeSRoland Mainz 					fts->endbase = fts->base + fts->baselen;
105734f9b3eeSRoland Mainz 					if (fts->endbase[-1] != '/')
105834f9b3eeSRoland Mainz 						fts->endbase++;
105934f9b3eeSRoland Mainz 				}
106034f9b3eeSRoland Mainz 				if (fts->cpname)
106134f9b3eeSRoland Mainz 				{
106234f9b3eeSRoland Mainz 					memcpy(fts->endbase, s, i + 1);
106334f9b3eeSRoland Mainz 					if (fts->cd)
106434f9b3eeSRoland Mainz 						s = fts->path;
106534f9b3eeSRoland Mainz 				}
106634f9b3eeSRoland Mainz 				if (n)
106734f9b3eeSRoland Mainz 				{
106834f9b3eeSRoland Mainz 					/*
106934f9b3eeSRoland Mainz 					 * don't recurse on . and ..
107034f9b3eeSRoland Mainz 					 */
107134f9b3eeSRoland Mainz 
107234f9b3eeSRoland Mainz 					if (n == 1)
107334f9b3eeSRoland Mainz 						f->fts_statp = fts->current->fts_statp;
107434f9b3eeSRoland Mainz 					else
1075da2e3ebdSchin 					{
107634f9b3eeSRoland Mainz 						if (f->fts_info != FTS_NS)
107734f9b3eeSRoland Mainz 							fts->dotdot = f;
107834f9b3eeSRoland Mainz 						if (fts->current->fts_parent->fts_level < 0)
107934f9b3eeSRoland Mainz 						{
108034f9b3eeSRoland Mainz 							f->fts_statp = &fts->current->fts_parent->statb;
108134f9b3eeSRoland Mainz 							info(fts, f, s, f->fts_statp, 0);
108234f9b3eeSRoland Mainz 						}
108334f9b3eeSRoland Mainz 						else
108434f9b3eeSRoland Mainz 							f->fts_statp = fts->current->fts_parent->fts_statp;
1085da2e3ebdSchin 					}
108634f9b3eeSRoland Mainz 					f->fts_info = FTS_DOT;
108734f9b3eeSRoland Mainz 				}
108834f9b3eeSRoland Mainz 				else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
108934f9b3eeSRoland Mainz 					f->statb.st_ino = D_FILENO(d);
109034f9b3eeSRoland Mainz 				if (fts->comparf)
109134f9b3eeSRoland Mainz 					fts->root = search(f, fts->root, fts->comparf, 1);
109234f9b3eeSRoland Mainz 				else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
109334f9b3eeSRoland Mainz 				{
109434f9b3eeSRoland Mainz 					if (fts->top)
109534f9b3eeSRoland Mainz 						fts->bot = fts->bot->fts_link = f;
1096da2e3ebdSchin 					else
109734f9b3eeSRoland Mainz 						fts->top = fts->bot = f;
1098da2e3ebdSchin 				}
1099da2e3ebdSchin 				else
110034f9b3eeSRoland Mainz 				{
110134f9b3eeSRoland Mainz 					/*
110234f9b3eeSRoland Mainz 					 * terminal node
110334f9b3eeSRoland Mainz 					 */
110434f9b3eeSRoland Mainz 
110534f9b3eeSRoland Mainz 					f->fts_path = PATH(fts, fts->path, 1);
110634f9b3eeSRoland Mainz 					f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
110734f9b3eeSRoland Mainz 					f->fts_accpath = ACCESS(fts, f);
110834f9b3eeSRoland Mainz 					fts->previous = fts->current;
110934f9b3eeSRoland Mainz 					fts->current = f;
111034f9b3eeSRoland Mainz 					fts->state = FTS_terminal;
111134f9b3eeSRoland Mainz 					goto note;
111234f9b3eeSRoland Mainz 				}
1113da2e3ebdSchin 			}
111434f9b3eeSRoland Mainz 
111534f9b3eeSRoland Mainz 			/*
111634f9b3eeSRoland Mainz 			 * done with the directory
111734f9b3eeSRoland Mainz 			 */
111834f9b3eeSRoland Mainz 
111934f9b3eeSRoland Mainz 			closedir(fts->dir);
112034f9b3eeSRoland Mainz 			fts->dir = 0;
112134f9b3eeSRoland Mainz 			if (fts->root)
112234f9b3eeSRoland Mainz 				getlist(&fts->top, &fts->bot, fts->root);
112334f9b3eeSRoland Mainz 			if (fts->children)
112434f9b3eeSRoland Mainz 			{
1125da2e3ebdSchin 				/*
112634f9b3eeSRoland Mainz 				 * try moving back to parent dir
1127da2e3ebdSchin 				 */
1128da2e3ebdSchin 
112934f9b3eeSRoland Mainz 				fts->base[fts->baselen] = 0;
113034f9b3eeSRoland Mainz 				if (fts->cd <= 0)
113134f9b3eeSRoland Mainz 				{
113234f9b3eeSRoland Mainz 					f = fts->current->fts_parent;
113334f9b3eeSRoland Mainz 					if (fts->cd < 0
113434f9b3eeSRoland Mainz 					    || f != fts->curdir
113534f9b3eeSRoland Mainz 					    || !fts->dotdot
113634f9b3eeSRoland Mainz 					    || !SAME(f->fts_statp, fts->dotdot->fts_statp)
113734f9b3eeSRoland Mainz 					    || fts->pwd && fts->pwd->symlink
113834f9b3eeSRoland Mainz 					    || (fts->cd = chdir("..")) < 0
113934f9b3eeSRoland Mainz #ifdef verify
114034f9b3eeSRoland Mainz 					    || stat(".", &sb) < 0
114134f9b3eeSRoland Mainz 					    || !SAME(&sb, fts->dotdot->fts_statp)
114234f9b3eeSRoland Mainz #endif
114334f9b3eeSRoland Mainz 					    )
114434f9b3eeSRoland Mainz 						fts->cd = setpdir(fts->home, fts->path, fts->base);
114534f9b3eeSRoland Mainz 					if (fts->pwd)
114634f9b3eeSRoland Mainz 						fts->pwd = fts->pwd->pwd;
114734f9b3eeSRoland Mainz 					fts->curdir = fts->cd ? 0 : f;
114834f9b3eeSRoland Mainz 				}
114934f9b3eeSRoland Mainz 				f = fts->current;
115034f9b3eeSRoland Mainz 				fts->link = f->fts_link;
115134f9b3eeSRoland Mainz 				f->fts_link = fts->top;
115234f9b3eeSRoland Mainz 				f->fts_path = PATH(fts, fts->path, f->fts_level);
115334f9b3eeSRoland Mainz 				f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1154da2e3ebdSchin 				f->fts_accpath = ACCESS(fts, f);
115534f9b3eeSRoland Mainz 				fts->state = FTS_children_return;
1156da2e3ebdSchin 				goto note;
1157da2e3ebdSchin 			}
115834f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
1159da2e3ebdSchin 
116034f9b3eeSRoland Mainz 		case FTS_children_resume:
1161da2e3ebdSchin 
1162da2e3ebdSchin 			fts->base[fts->baselen] = 0;
116334f9b3eeSRoland Mainz 			if (fts->top)
1164da2e3ebdSchin 			{
116534f9b3eeSRoland Mainz 				fts->bot->fts_link = fts->todo;
116634f9b3eeSRoland Mainz 				fts->todo = fts->top;
116734f9b3eeSRoland Mainz 				fts->top = 0;
1168da2e3ebdSchin 			}
116934f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
1170da2e3ebdSchin 
117134f9b3eeSRoland Mainz 		case FTS_popstack:
1172da2e3ebdSchin 
117334f9b3eeSRoland Mainz 			/*
117434f9b3eeSRoland Mainz 			 * pop objects completely processed
117534f9b3eeSRoland Mainz 			 */
1176da2e3ebdSchin 
117734f9b3eeSRoland Mainz 			fts->nd = 0;
117834f9b3eeSRoland Mainz 			f = fts->current;
117934f9b3eeSRoland Mainz 			/*FALLTHROUGH*/
1180da2e3ebdSchin 
118134f9b3eeSRoland Mainz 		case FTS_popstack_resume:
1182da2e3ebdSchin 
118334f9b3eeSRoland Mainz 			while (fts->todo && f == fts->todo)
1184da2e3ebdSchin 			{
118534f9b3eeSRoland Mainz 				t = f->fts_parent;
118634f9b3eeSRoland Mainz 				if ((f->fts_info & FTS_DP) == FTS_D)
1187da2e3ebdSchin 				{
1188da2e3ebdSchin 					/*
118934f9b3eeSRoland Mainz 					 * delete from <dev,ino> tree
1190da2e3ebdSchin 					 */
1191da2e3ebdSchin 
119234f9b3eeSRoland Mainz 					if (f != fts->diroot)
119334f9b3eeSRoland Mainz 						fts->diroot = search(f, fts->diroot, statcmp, 0);
119434f9b3eeSRoland Mainz 					fts->diroot = deleteroot(fts->diroot);
119534f9b3eeSRoland Mainz 					if (f == fts->curdir)
119634f9b3eeSRoland Mainz 					{
119734f9b3eeSRoland Mainz 						fts->nd++;
119834f9b3eeSRoland Mainz 						fts->curdir = t;
119934f9b3eeSRoland Mainz 					}
1200da2e3ebdSchin 
1201da2e3ebdSchin 					/*
120234f9b3eeSRoland Mainz 					 * perform post-order processing
1203da2e3ebdSchin 					 */
1204da2e3ebdSchin 
120534f9b3eeSRoland Mainz 					if (!(fts->flags & FTS_NOPOSTORDER) &&
120634f9b3eeSRoland Mainz 					    f->status != FTS_SKIP &&
120734f9b3eeSRoland Mainz 					    f->status != FTS_NOPOSTORDER)
120834f9b3eeSRoland Mainz 					{
120934f9b3eeSRoland Mainz 						/*
121034f9b3eeSRoland Mainz 						 * move to parent dir
121134f9b3eeSRoland Mainz 						 */
121234f9b3eeSRoland Mainz 
121334f9b3eeSRoland Mainz 						if (fts->nd > 0)
121434f9b3eeSRoland Mainz 							fts->cd = popdirs(fts);
121534f9b3eeSRoland Mainz 						if (fts->cd < 0)
121634f9b3eeSRoland Mainz 							fts->cd = setpdir(fts->home, fts->path, fts->base);
121734f9b3eeSRoland Mainz 						fts->curdir = fts->cd ? 0 : t;
121834f9b3eeSRoland Mainz 						f->fts_info = FTS_DP;
121934f9b3eeSRoland Mainz 						f->fts_path = PATH(fts, fts->path, f->fts_level);
122034f9b3eeSRoland Mainz 						f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
122134f9b3eeSRoland Mainz 						f->fts_accpath = ACCESS(fts, f);
122234f9b3eeSRoland Mainz 
122334f9b3eeSRoland Mainz 						/*
122434f9b3eeSRoland Mainz 						 * re-stat to update nlink/times
122534f9b3eeSRoland Mainz 						 */
122634f9b3eeSRoland Mainz 
122734f9b3eeSRoland Mainz 						stat(f->fts_accpath, f->fts_statp);
122834f9b3eeSRoland Mainz 						fts->link = f->fts_link;
122934f9b3eeSRoland Mainz 						f->fts_link = 0;
123034f9b3eeSRoland Mainz 						fts->state = FTS_popstack_return;
123134f9b3eeSRoland Mainz 						goto note;
123234f9b3eeSRoland Mainz 					}
1233da2e3ebdSchin 				}
1234da2e3ebdSchin 
123534f9b3eeSRoland Mainz 				/*
123634f9b3eeSRoland Mainz 				 * reset base
123734f9b3eeSRoland Mainz 				 */
1238da2e3ebdSchin 
123934f9b3eeSRoland Mainz 				if (fts->base > fts->path + t->fts_namelen)
124034f9b3eeSRoland Mainz 					fts->base--;
124134f9b3eeSRoland Mainz 				*fts->base = 0;
124234f9b3eeSRoland Mainz 				fts->base -= t->fts_namelen;
124334f9b3eeSRoland Mainz 
124434f9b3eeSRoland Mainz 				/*
124534f9b3eeSRoland Mainz 				 * try again or delete from top of stack
124634f9b3eeSRoland Mainz 				 */
124734f9b3eeSRoland Mainz 
124834f9b3eeSRoland Mainz 				if (f->status == FTS_AGAIN)
124934f9b3eeSRoland Mainz 				{
125034f9b3eeSRoland Mainz 					f->fts_info = FTS_D;
125134f9b3eeSRoland Mainz 					f->status = 0;
125234f9b3eeSRoland Mainz 				}
125334f9b3eeSRoland Mainz 				else
125434f9b3eeSRoland Mainz 				{
125534f9b3eeSRoland Mainz 					fts->todo = fts->todo->fts_link;
125634f9b3eeSRoland Mainz 					drop(fts, f);
125734f9b3eeSRoland Mainz 				}
125834f9b3eeSRoland Mainz 				f = t;
125934f9b3eeSRoland Mainz 			}
1260da2e3ebdSchin 
1261da2e3ebdSchin 			/*
126234f9b3eeSRoland Mainz 			 * reset current directory
1263da2e3ebdSchin 			 */
1264da2e3ebdSchin 
126534f9b3eeSRoland Mainz 			if (fts->nd > 0 && popdirs(fts) < 0)
1266da2e3ebdSchin 			{
126734f9b3eeSRoland Mainz 				pathcd(fts->home, NiL);
126834f9b3eeSRoland Mainz 				fts->curdir = 0;
126934f9b3eeSRoland Mainz 				fts->cd = -1;
1270da2e3ebdSchin 			}
127134f9b3eeSRoland Mainz 			if (fts->todo)
1272da2e3ebdSchin 			{
127334f9b3eeSRoland Mainz 				if (*fts->base)
127434f9b3eeSRoland Mainz 					fts->base += f->fts_namelen;
127534f9b3eeSRoland Mainz 				if (*(fts->base - 1) != '/')
127634f9b3eeSRoland Mainz 					*fts->base++ = '/';
127734f9b3eeSRoland Mainz 				*fts->base = 0;
127834f9b3eeSRoland Mainz 				f = fts->todo;
127934f9b3eeSRoland Mainz 				fts->state = FTS_todo;
128034f9b3eeSRoland Mainz 				continue;
1281da2e3ebdSchin 			}
128234f9b3eeSRoland Mainz 			return 0;
1283da2e3ebdSchin 
128434f9b3eeSRoland Mainz 		case FTS_children_return:
1285da2e3ebdSchin 
128634f9b3eeSRoland Mainz 			f = fts->current;
128734f9b3eeSRoland Mainz 			f->fts_link = fts->link;
1288da2e3ebdSchin 
128934f9b3eeSRoland Mainz 			/*
129034f9b3eeSRoland Mainz 			 * chdir down again
129134f9b3eeSRoland Mainz 			 */
1292da2e3ebdSchin 
129334f9b3eeSRoland Mainz 			i = f->fts_info != FTS_DNX;
129434f9b3eeSRoland Mainz 			n = f->status == FTS_SKIP;
129534f9b3eeSRoland Mainz 			if (!n && fts->cd == 0)
1296da2e3ebdSchin 			{
129734f9b3eeSRoland Mainz 				if ((fts->cd = chdir(fts->base)) < 0)
129834f9b3eeSRoland Mainz 					pathcd(fts->home, NiL);
129934f9b3eeSRoland Mainz 				else if (fts->pwd != f)
130034f9b3eeSRoland Mainz 				{
130134f9b3eeSRoland Mainz 					f->pwd = fts->pwd;
130234f9b3eeSRoland Mainz 					fts->pwd = f;
130334f9b3eeSRoland Mainz 				}
130434f9b3eeSRoland Mainz 				fts->curdir = fts->cd ? 0 : f;
1305da2e3ebdSchin 			}
1306da2e3ebdSchin 
130734f9b3eeSRoland Mainz 			/*
130834f9b3eeSRoland Mainz 			 * prune
130934f9b3eeSRoland Mainz 			 */
1310da2e3ebdSchin 
131134f9b3eeSRoland Mainz 			if (fts->base[fts->baselen - 1] != '/')
131234f9b3eeSRoland Mainz 				fts->base[fts->baselen] = '/';
131334f9b3eeSRoland Mainz 			for (fts->bot = 0, f = fts->top; f; )
131434f9b3eeSRoland Mainz 				if (n || f->status == FTS_SKIP)
131534f9b3eeSRoland Mainz 				{
131634f9b3eeSRoland Mainz 					if (fts->bot)
131734f9b3eeSRoland Mainz 						fts->bot->fts_link = f->fts_link;
131834f9b3eeSRoland Mainz 					else
131934f9b3eeSRoland Mainz 						fts->top = f->fts_link;
132034f9b3eeSRoland Mainz 					drop(fts, f);
132134f9b3eeSRoland Mainz 					f = fts->bot ? fts->bot->fts_link : fts->top;
132234f9b3eeSRoland Mainz 				}
1323da2e3ebdSchin 				else
1324da2e3ebdSchin 				{
132534f9b3eeSRoland Mainz 					if (fts->children > 1 && i)
1326da2e3ebdSchin 					{
132734f9b3eeSRoland Mainz 						if (f->status == FTS_STAT)
132834f9b3eeSRoland Mainz 							info(fts, f, NiL, f->fts_statp, 0);
132934f9b3eeSRoland Mainz 						else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
1330da2e3ebdSchin 						{
133134f9b3eeSRoland Mainz 							s = f->fts_name;
133234f9b3eeSRoland Mainz 							if (fts->cd)
133334f9b3eeSRoland Mainz 							{
133434f9b3eeSRoland Mainz 								memcpy(fts->endbase, s, f->fts_namelen + 1);
133534f9b3eeSRoland Mainz 								s = fts->path;
133634f9b3eeSRoland Mainz 							}
133734f9b3eeSRoland Mainz 							info(fts, f, s, f->fts_statp, fts->flags);
1338da2e3ebdSchin 						}
1339da2e3ebdSchin 					}
134034f9b3eeSRoland Mainz 					fts->bot = f;
134134f9b3eeSRoland Mainz 					f = f->fts_link;
1342da2e3ebdSchin 				}
134334f9b3eeSRoland Mainz 			fts->children = 0;
134434f9b3eeSRoland Mainz 			fts->state = FTS_children_resume;
134534f9b3eeSRoland Mainz 			continue;
1346da2e3ebdSchin 
134734f9b3eeSRoland Mainz 		case FTS_popstack_return:
1348da2e3ebdSchin 
134934f9b3eeSRoland Mainz 			f = fts->todo;
135034f9b3eeSRoland Mainz 			f->fts_link = fts->link;
135134f9b3eeSRoland Mainz 			f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
135234f9b3eeSRoland Mainz 			fts->state = FTS_popstack_resume;
135334f9b3eeSRoland Mainz 			continue;
1354da2e3ebdSchin 
135534f9b3eeSRoland Mainz 		case FTS_preorder_return:
1356da2e3ebdSchin 
135734f9b3eeSRoland Mainz 			f = fts->current;
135834f9b3eeSRoland Mainz 			f->fts_link = fts->link;
1359da2e3ebdSchin 
136034f9b3eeSRoland Mainz 			/*
136134f9b3eeSRoland Mainz 			 * follow symlink if asked to
136234f9b3eeSRoland Mainz 			 */
1363da2e3ebdSchin 
136434f9b3eeSRoland Mainz 			if (f->status == FTS_FOLLOW)
1365da2e3ebdSchin 			{
136634f9b3eeSRoland Mainz 				f->status = 0;
136734f9b3eeSRoland Mainz 				if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1368da2e3ebdSchin 				{
136934f9b3eeSRoland Mainz 					info(fts, f, f->fts_accpath, f->fts_statp, 0);
137034f9b3eeSRoland Mainz 					if (f->fts_info != FTS_SL)
137134f9b3eeSRoland Mainz 					{
137234f9b3eeSRoland Mainz 						fts->state = FTS_preorder;
137334f9b3eeSRoland Mainz 						continue;
137434f9b3eeSRoland Mainz 					}
1375da2e3ebdSchin 				}
1376da2e3ebdSchin 			}
1377da2e3ebdSchin 
137834f9b3eeSRoland Mainz 			/*
137934f9b3eeSRoland Mainz 			 * about to prune this f and already at home
138034f9b3eeSRoland Mainz 			 */
1381da2e3ebdSchin 
138234f9b3eeSRoland Mainz 			if (fts->cd == 0 && f->fts_level == 0 && f->nd)
138334f9b3eeSRoland Mainz 				fts->cd = -1;
138434f9b3eeSRoland Mainz 			fts->state = FTS_preorder_resume;
138534f9b3eeSRoland Mainz 			continue;
1386da2e3ebdSchin 
138734f9b3eeSRoland Mainz 		case FTS_terminal:
1388da2e3ebdSchin 
138934f9b3eeSRoland Mainz 			f = fts->current;
139034f9b3eeSRoland Mainz 			if (f->status == FTS_FOLLOW)
1391da2e3ebdSchin 			{
139234f9b3eeSRoland Mainz 				f->status = 0;
139334f9b3eeSRoland Mainz 				if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1394da2e3ebdSchin 				{
139534f9b3eeSRoland Mainz 					info(fts, f, f->fts_accpath, f->fts_statp, 0);
139634f9b3eeSRoland Mainz 					if (f->symlink && f->fts_info != FTS_SL)
139734f9b3eeSRoland Mainz 					{
139834f9b3eeSRoland Mainz 						if (!(f->fts_link = fts->top))
139934f9b3eeSRoland Mainz 							fts->bot = f;
140034f9b3eeSRoland Mainz 						fts->top = f;
140134f9b3eeSRoland Mainz 						fts->current = fts->previous;
140234f9b3eeSRoland Mainz 						fts->state = FTS_readdir;
140334f9b3eeSRoland Mainz 						continue;
140434f9b3eeSRoland Mainz 					}
1405da2e3ebdSchin 				}
1406da2e3ebdSchin 			}
140734f9b3eeSRoland Mainz 			f = f->fts_parent;
140834f9b3eeSRoland Mainz 			drop(fts, fts->current);
140934f9b3eeSRoland Mainz 			fts->current = f;
141034f9b3eeSRoland Mainz 			fts->state = FTS_readdir;
141134f9b3eeSRoland Mainz 			continue;
1412da2e3ebdSchin 
141334f9b3eeSRoland Mainz 		case FTS_error:
1414da2e3ebdSchin 
141534f9b3eeSRoland Mainz 			return 0;
1416da2e3ebdSchin 
141734f9b3eeSRoland Mainz 		default:
1418da2e3ebdSchin 
141934f9b3eeSRoland Mainz 			fts->fts_errno = EINVAL;
142034f9b3eeSRoland Mainz 			fts->state = FTS_error;
142134f9b3eeSRoland Mainz 			return 0;
1422da2e3ebdSchin 
142334f9b3eeSRoland Mainz 		}
1424da2e3ebdSchin  note:
142534f9b3eeSRoland Mainz #if __OBSOLETE__ < 20140101
142634f9b3eeSRoland Mainz 	f->_fts_pathlen = (unsigned short)f->fts_pathlen;
142734f9b3eeSRoland Mainz #endif
1428da2e3ebdSchin 	for (p = notify; p; p = p->next)
1429da2e3ebdSchin 		if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
1430da2e3ebdSchin 			break;
1431da2e3ebdSchin 		else if (n < 0)
1432da2e3ebdSchin 		{
1433da2e3ebdSchin 			fts->fts_errno = EINVAL;
1434da2e3ebdSchin 			fts->state = FTS_error;
1435da2e3ebdSchin 			return 0;
1436da2e3ebdSchin 		}
1437da2e3ebdSchin 	return f;
1438da2e3ebdSchin }
1439da2e3ebdSchin 
1440da2e3ebdSchin /*
1441da2e3ebdSchin  * set stream or entry flags
1442da2e3ebdSchin  */
1443da2e3ebdSchin 
1444da2e3ebdSchin int
fts_set(register FTS * fts,register FTSENT * f,int status)1445da2e3ebdSchin fts_set(register FTS* fts, register FTSENT* f, int status)
1446da2e3ebdSchin {
1447da2e3ebdSchin 	if (fts || !f || f->fts->current != f)
1448da2e3ebdSchin 		return -1;
1449da2e3ebdSchin 	switch (status)
1450da2e3ebdSchin 	{
1451da2e3ebdSchin 	case FTS_AGAIN:
1452da2e3ebdSchin 		break;
1453da2e3ebdSchin 	case FTS_FOLLOW:
1454da2e3ebdSchin 		if (!(f->fts_info & FTS_SL))
1455da2e3ebdSchin 			return -1;
1456da2e3ebdSchin 		break;
1457da2e3ebdSchin 	case FTS_NOPOSTORDER:
1458da2e3ebdSchin 		break;
1459da2e3ebdSchin 	case FTS_SKIP:
1460da2e3ebdSchin 		if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
1461da2e3ebdSchin 			return -1;
1462da2e3ebdSchin 		break;
1463da2e3ebdSchin 	default:
1464da2e3ebdSchin 		return -1;
1465da2e3ebdSchin 	}
1466da2e3ebdSchin 	f->status = status;
1467da2e3ebdSchin 	return 0;
1468da2e3ebdSchin }
1469da2e3ebdSchin 
1470da2e3ebdSchin /*
1471da2e3ebdSchin  * return the list of child entries
1472da2e3ebdSchin  */
1473da2e3ebdSchin 
1474da2e3ebdSchin FTSENT*
fts_children(register FTS * fts,int flags)1475da2e3ebdSchin fts_children(register FTS* fts, int flags)
1476da2e3ebdSchin {
1477da2e3ebdSchin 	register FTSENT*	f;
1478da2e3ebdSchin 
1479da2e3ebdSchin 	switch (fts->state)
1480da2e3ebdSchin 	{
1481da2e3ebdSchin 
1482da2e3ebdSchin 	case 0:
1483da2e3ebdSchin 
148434f9b3eeSRoland Mainz 		if (fts->comparf)
148534f9b3eeSRoland Mainz 			order(fts);
1486da2e3ebdSchin 		fts->