xref: /titanic_51/usr/src/lib/libast/common/misc/fts.c (revision a799b1e741b6f59012a469e6b57c40cb8061127b)
1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2008 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                  Common Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *            http://www.opensource.org/licenses/cpl1.0.txt             *
11 *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
12 *                                                                      *
13 *              Information and Software Systems Research               *
14 *                            AT&T Research                             *
15 *                           Florham Park NJ                            *
16 *                                                                      *
17 *                 Glenn Fowler <gsf@research.att.com>                  *
18 *                  David Korn <dgk@research.att.com>                   *
19 *                   Phong Vo <kpv@research.att.com>                    *
20 *                                                                      *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24  * Phong Vo
25  * Glenn Fowler
26  * AT&T Research
27  *
28  * fts implementation unwound from the kpv ftwalk() of 1988-10-30
29  */
30 
31 #include <ast.h>
32 #include <ast_dir.h>
33 #include <error.h>
34 #include <fs3d.h>
35 #include <ls.h>
36 
37 struct Ftsent;
38 
39 typedef int (*Compar_f)(struct Ftsent* const*, struct Ftsent* const*);
40 typedef int (*Stat_f)(const char*, struct stat*);
41 
42 #define _FTS_PRIVATE_ \
43 	FTSENT*		parent;			/* top parent		*/ \
44 	FTSENT*		todo;			/* todo list		*/ \
45 	FTSENT*		top;			/* top element		*/ \
46 	FTSENT*		root;						   \
47 	FTSENT*		bot;			/* bottom element	*/ \
48 	FTSENT*		free;			/* free element		*/ \
49 	FTSENT*		diroot;						   \
50 	FTSENT*		curdir;						   \
51 	FTSENT*		current;		/* current element	*/ \
52 	FTSENT*		previous;		/* previous current	*/ \
53 	FTSENT*		dotdot;						   \
54 	FTSENT*		link;			/* real current fts_link*/ \
55 	FTSENT*		pwd;			/* pwd parent		*/ \
56 	DIR*		dir;			/* current dir stream	*/ \
57 	Compar_f	comparf;		/* node comparison func	*/ \
58 	int		baselen;		/* current strlen(base)	*/ \
59 	int		cd;			/* chdir status		*/ \
60 	int		cpname;						   \
61 	int		flags;			/* fts_open() flags	*/ \
62 	int		homesize;		/* sizeof(home)		*/ \
63 	int		nd;						   \
64 	unsigned char	children;					   \
65 	unsigned char	fs3d;						   \
66 	unsigned char	nostat;					   	   \
67 	unsigned char	state;			/* fts_read() state	*/ \
68 	char*		base;			/* basename in path	*/ \
69 	char*		name;						   \
70 	char*		path;			/* path workspace	*/ \
71 	char*		home;			/* home/path buffer	*/ \
72 	char*		endbase;		/* space to build paths */ \
73 	char*		endbuf;			/* space to build paths */ \
74 	char*		pad[2];			/* $0.02 to splain this	*/
75 
76 /*
77  * NOTE: <ftwalk.h> relies on status and statb being the first two elements
78  */
79 
80 #define _FTSENT_PRIVATE_ \
81 	short		status;			/* internal status	*/ \
82 	struct stat	statb;			/* fts_statp data	*/ \
83 	FTS*		fts;			/* fts_open() handle	*/ \
84 	int		nd;			/* popdir() count	*/ \
85 	FTSENT*		left;			/* left child		*/ \
86 	FTSENT*		right;			/* right child		*/ \
87 	FTSENT*		pwd;			/* pwd parent		*/ \
88 	FTSENT*		stack;			/* getlist() stack	*/ \
89 	long		nlink;			/* FTS_D link count	*/ \
90 	unsigned char	must;			/* must stat		*/ \
91 	unsigned char	type;			/* DT_* type		*/ \
92 	unsigned char	symlink;		/* originally a symlink	*/ \
93 	char		name[sizeof(int)];	/* fts_name data	*/
94 
95 #include <fts.h>
96 
97 #ifndef ENOSYS
98 #define ENOSYS		EINVAL
99 #endif
100 
101 
102 #if MAXNAMLEN > 16
103 #define MINNAME		32
104 #else
105 #define MINNAME		16
106 #endif
107 
108 #define drop(p,f)	(((f)->fts_namelen < MINNAME) ? ((f)->fts_link = (p)->free, (p)->free = (f)) : (free(f), (p)->free))
109 
110 #define ACCESS(p,f)	((p)->cd==0?(f)->fts_name:(f)->fts_path)
111 #define PATH(f,p,l)	((!((f)->flags&FTS_SEEDOTDIR)&&(l)>0&&(p)[0]=='.'&&(p)[1]=='/')?((p)+2):(p))
112 #define SAME(one,two)	((one)->st_ino==(two)->st_ino&&(one)->st_dev==(two)->st_dev)
113 #define SKIPLINK(p,f)	((f)->fts_parent->nlink == 0)
114 
115 #ifdef D_TYPE
116 #define ISTYPE(f,t)	((f)->type == (t))
117 #define TYPE(f,t)	((f)->type = (t))
118 #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)))))
119 #else
120 #undef	DT_UNKNOWN
121 #define DT_UNKNOWN	0
122 #undef	DT_LNK
123 #define DT_LNK		1
124 #define ISTYPE(f,t)	((t)==DT_UNKNOWN)
125 #define TYPE(f,d)
126 #define SKIP(p,f)	((f)->fts_parent->must == 0 && SKIPLINK(p,f))
127 #endif
128 
129 #ifndef D_FILENO
130 #define D_FILENO(d)	(1)
131 #endif
132 
133 /*
134  * NOTE: a malicious dir rename() could change .. underfoot so we
135  *	 must always verify; undef verify to enable the unsafe code
136  */
137 
138 #define verify		1
139 
140 /*
141  * FTS_NOSTAT requires a dir with
142  *	D_TYPE(&dirent_t)!=DT_UNKNOWN
143  *	    OR
144  *	st_nlink>=2
145  */
146 
147 #define FTS_children_resume	1
148 #define FTS_children_return	2
149 #define FTS_error		3
150 #define FTS_popstack		4
151 #define FTS_popstack_resume	5
152 #define FTS_popstack_return	6
153 #define FTS_preorder		7
154 #define FTS_preorder_resume	8
155 #define FTS_preorder_return	9
156 #define FTS_readdir		10
157 #define FTS_terminal		11
158 #define FTS_todo		12
159 #define FTS_top_return		13
160 
161 typedef int (*Notify_f)(FTS*, FTSENT*, void*);
162 
163 typedef struct Notify_s
164 {
165 	struct Notify_s*	next;
166 	Notify_f		notifyf;
167 	void*			context;
168 } Notify_t;
169 
170 static Notify_t*		notify;
171 
172 /*
173  * allocate an FTSENT node
174  */
175 
176 static FTSENT*
177 node(FTS* fts, FTSENT* parent, register char* name, register int namelen)
178 {
179 	register FTSENT*	f;
180 	register int		n;
181 
182 	if (fts->free && namelen < MINNAME)
183 	{
184 		f = fts->free;
185 		fts->free = f->fts_link;
186 	}
187 	else
188 	{
189 		n = (namelen < MINNAME ? MINNAME : namelen + 1) - sizeof(int);
190 		if (!(f = newof(0, FTSENT, 1, n)))
191 		{
192 			fts->fts_errno = errno;
193 			fts->state = FTS_error;
194 			return 0;
195 		}
196 		f->fts = fts;
197 	}
198 	TYPE(f, DT_UNKNOWN);
199 	f->status = 0;
200 	f->symlink = 0;
201 	f->fts_level = (f->fts_parent = parent)->fts_level + 1;
202 	f->fts_link = 0;
203 	f->fts_pointer = 0;
204 	f->fts_number = 0;
205 	f->fts_errno = 0;
206 	f->fts_namelen = namelen;
207 	f->fts_name = f->name;
208 	f->fts_statp = &f->statb;
209 	memcpy(f->fts_name, name, namelen + 1);
210 	return f;
211 }
212 
213 /*
214  * compare directories by device/inode
215  */
216 
217 static int
218 statcmp(FTSENT* const* pf1, FTSENT* const* pf2)
219 {
220 	register const FTSENT*	f1 = *pf1;
221 	register const FTSENT*	f2 = *pf2;
222 
223 	if (f1->statb.st_ino < f2->statb.st_ino)
224 		return -1;
225 	if (f1->statb.st_ino > f2->statb.st_ino)
226 		return 1;
227 	if (f1->statb.st_dev < f2->statb.st_dev)
228 		return -1;
229 	if (f1->statb.st_dev > f2->statb.st_dev)
230 		return 1;
231 
232 	/*
233 	 * hack for NFS where <dev,ino> may not uniquely identify objects
234 	 */
235 
236 	if (f1->statb.st_mtime < f2->statb.st_mtime)
237 		return -1;
238 	if (f1->statb.st_mtime > f2->statb.st_mtime)
239 		return 1;
240 	return 0;
241 }
242 
243 /*
244  * search trees with top-down splaying (a la Tarjan and Sleator)
245  * when used for insertion sort, this implements a stable sort
246  */
247 
248 #define RROTATE(r)	(t = r->left, r->left = t->right, t->right = r, r = t)
249 #define LROTATE(r)	(t = r->right, r->right = t->left, t->left = r, r = t)
250 
251 static FTSENT*
252 search(FTSENT* e, FTSENT* root, int(*comparf)(FTSENT* const*, FTSENT* const*), int insert)
253 {
254 	register int		cmp;
255 	register FTSENT*	t;
256 	register FTSENT*	left;
257 	register FTSENT*	right;
258 	register FTSENT*	lroot;
259 	register FTSENT*	rroot;
260 
261 	left = right = lroot = rroot = 0;
262 	while (root)
263 	{
264 		if (!(cmp = (*comparf)(&e, &root)) && !insert)
265 			break;
266 		if (cmp < 0)
267 		{
268 			/*
269 			 * this is the left zig-zig case
270 			 */
271 
272 			if (root->left && (cmp = (*comparf)(&e, &root->left)) <= 0)
273 			{
274 				RROTATE(root);
275 				if (!cmp && !insert)
276 					break;
277 			}
278 
279 			/*
280 			 * stick all things > e to the right tree
281 			 */
282 
283 			if (right)
284 				right->left = root;
285 			else
286 				rroot = root;
287 			right = root;
288 			root = root->left;
289 			right->left = 0;
290 		}
291 		else
292 		{
293 			/*
294 			 * this is the right zig-zig case
295 			 */
296 
297 			if (root->right && (cmp = (*comparf)(&e, &root->right)) >= 0)
298 			{
299 				LROTATE(root);
300 				if (!cmp && !insert)
301 					break;
302 			}
303 
304 			/*
305 			 * stick all things <= e to the left tree
306 			 */
307 
308 			if (left)
309 				left->right = root;
310 			else
311 				lroot = root;
312 			left = root;
313 			root = root->right;
314 			left->right = 0;
315 		}
316 	}
317 	if (!root)
318 		root = e;
319 	else
320 	{
321 		if (right)
322 			right->left = root->right;
323 		else
324 			rroot = root->right;
325 		if (left)
326 			left->right = root->left;
327 		else
328 			lroot = root->left;
329 	}
330 	root->left = lroot;
331 	root->right = rroot;
332 	return root;
333 }
334 
335 /*
336  * delete the root element from the tree
337  */
338 
339 static FTSENT*
340 deleteroot(register FTSENT* root)
341 {
342 	register FTSENT*	t;
343 	register FTSENT*	left;
344 	register FTSENT*	right;
345 
346 	right = root->right;
347 	if (!(left = root->left))
348 		root = right;
349 	else
350 	{
351 		while (left->right)
352 			LROTATE(left);
353 		left->right = right;
354 		root = left;
355 	}
356 	return root;
357 }
358 
359 /*
360  * generate ordered fts_link list from binary tree at root
361  * FTSENT.stack instead of recursion to avoid blowing the real
362  * stack on big directories
363  */
364 
365 static void
366 getlist(register FTSENT** top, register FTSENT** bot, register FTSENT* root)
367 {
368 	register FTSENT*	stack = 0;
369 
370 	for (;;)
371 	{
372 		if (root->left)
373 		{
374 			root->stack = stack;
375 			stack = root;
376 			root = root->left;
377 		}
378 		else
379 		{
380 			for (;;)
381 			{
382 				if (*top)
383 					*bot = (*bot)->fts_link = root;
384 				else
385 					*bot = *top = root;
386 				if (root->right)
387 				{
388 					root = root->right;
389 					break;
390 				}
391 				if (!(root = stack))
392 					return;
393 				stack = stack->stack;
394 			}
395 		}
396 	}
397 }
398 
399 /*
400  * set directory when curdir is lost in space
401  */
402 
403 static int
404 setdir(register char* home, register char* path)
405 {
406 	register int	cdrv;
407 
408 	if (path[0] == '/')
409 		cdrv = pathcd(path, NiL);
410 	else
411 	{
412 		/*
413 		 * note that path and home are in the same buffer
414 		 */
415 
416 		path[-1] = '/';
417 		cdrv = pathcd(home, NiL);
418 		path[-1] = 0;
419 	}
420 	if (cdrv < 0)
421 		pathcd(home, NiL);
422 	return cdrv;
423 }
424 
425 /*
426  * set to parent dir
427  */
428 
429 static int
430 setpdir(register char* home, register char* path, register char* base)
431 {
432 	register int	c;
433 	register int	cdrv;
434 
435 	if (base > path)
436 	{
437 		c = base[0];
438 		base[0] = 0;
439 		cdrv = setdir(home, path);
440 		base[0] = c;
441 	}
442 	else
443 		cdrv = pathcd(home, NiL);
444 	return cdrv;
445 }
446 
447 /*
448  * pop a set of directories
449  */
450 static int
451 popdirs(FTS* fts)
452 {
453 	register FTSENT*f;
454 	register char*	s;
455 	register char*	e;
456 #ifndef verify
457 	register int	verify;
458 #endif
459 	struct stat	sb;
460 	char		buf[PATH_MAX];
461 
462 	if (!(f = fts->curdir) || f->fts_level < 0)
463 		return -1;
464 	e = buf + sizeof(buf) - 4;
465 #ifndef verify
466 	verify = 0;
467 #endif
468 	while (fts->nd > 0)
469 	{
470 		for (s = buf; s < e && fts->nd > 0; fts->nd--)
471 		{
472 			if (fts->pwd)
473 			{
474 #ifndef verify
475 				verify |= fts->pwd->symlink;
476 #endif
477 				fts->pwd = fts->pwd->pwd;
478 			}
479 			*s++ = '.';
480 			*s++ = '.';
481 			*s++ = '/';
482 		}
483 		*s = 0;
484 		if (chdir(buf))
485 			return -1;
486 	}
487 	return (verify && (stat(".", &sb) < 0 || !SAME(&sb, f->fts_statp))) ? -1 : 0;
488 }
489 
490 /*
491  * initialize st from path and fts_info from st
492  */
493 
494 static int
495 info(FTS* fts, register FTSENT* f, const char* path, struct stat* sp, int flags)
496 {
497 	if (path)
498 	{
499 #ifdef S_ISLNK
500 		if (!f->symlink && (ISTYPE(f, DT_UNKNOWN) || ISTYPE(f, DT_LNK)))
501 		{
502 			if (lstat(path, sp) < 0)
503 				goto bad;
504 		}
505 		else
506 #endif
507 			if (stat(path, sp) < 0)
508 				goto bad;
509 	}
510 #ifdef S_ISLNK
511  again:
512 #endif
513 	if (S_ISDIR(sp->st_mode))
514 	{
515 		if ((flags & FTS_NOSTAT) && !fts->fs3d)
516 		{
517 			f->fts_parent->nlink--;
518 #ifdef D_TYPE
519 			if ((f->nlink = sp->st_nlink) < 2)
520 			{
521 				f->must = 2;
522 				f->nlink = 2;
523 			}
524 			else
525 				f->must = 0;
526 #else
527 			if ((f->nlink = sp->st_nlink) >= 2)
528 				f->must = 1;
529 			else
530 				f->must = 2;
531 #endif
532 		}
533 		else
534 			f->must = 2;
535 		TYPE(f, DT_DIR);
536 		f->fts_info = FTS_D;
537 	}
538 #ifdef S_ISLNK
539 	else if (S_ISLNK((sp)->st_mode))
540 	{
541 		struct stat	sb;
542 
543 		f->symlink = 1;
544 		if (!(flags & FTS_PHYSICAL) && stat(path, &sb) >= 0)
545 		{
546 			*sp = sb;
547 			flags = FTS_PHYSICAL;
548 			goto again;
549 		}
550 		TYPE(f, DT_LNK);
551 		f->fts_info = FTS_SL;
552 	}
553 #endif
554 	else
555 	{
556 		TYPE(f, DT_REG);
557 		f->fts_info = FTS_F;
558 	}
559 	return 0;
560  bad:
561 	TYPE(f, DT_UNKNOWN);
562 	f->fts_info = FTS_NS;
563 	return -1;
564 }
565 
566 /*
567  * get top list of elements to process
568  */
569 
570 static FTSENT*
571 toplist(FTS* fts, register char* const* pathnames)
572 {
573 	register char*		path;
574 	register struct stat*	sb;
575 	register FTSENT*	f;
576 	register FTSENT*	root;
577 	int			physical;
578 	int			metaphysical;
579 	char*			s;
580 	FTSENT*			top;
581 	FTSENT*			bot;
582 	struct stat		st;
583 
584 	if (fts->flags & FTS_NOSEEDOTDIR)
585 		fts->flags &= ~FTS_SEEDOTDIR;
586 	physical = (fts->flags & FTS_PHYSICAL);
587 	metaphysical = (fts->flags & (FTS_META|FTS_PHYSICAL)) == (FTS_META|FTS_PHYSICAL);
588 	top = bot = root = 0;
589 	while (path = *pathnames++)
590 	{
591 		/*
592 		 * make elements
593 		 */
594 
595 		if (!(f = node(fts, fts->parent, path, strlen(path))))
596 			break;
597 		path = f->fts_name;
598 		if (!physical)
599 			f->fts_namelen = (fts->flags & FTS_SEEDOTDIR) ? strlen(path) : (pathcanon(path, 0) - path);
600 		else if (*path != '.')
601 		{
602 			f->fts_namelen = strlen(path);
603 			fts->flags |= FTS_SEEDOTDIR;
604 		}
605 		else
606 		{
607 			if (fts->flags & FTS_NOSEEDOTDIR)
608 			{
609 				fts->flags &= ~FTS_SEEDOTDIR;
610 				s = path;
611 				while (*s++ == '.' && *s++ == '/')
612 				{
613 					while (*s == '/')
614 						s++;
615 					if (!*s)
616 						break;
617 					path = f->fts_name;
618 					while (*path++ = *s++);
619 					path = f->fts_name;
620 				}
621 			}
622 			else
623 				fts->flags |= FTS_SEEDOTDIR;
624 			for (s = path + strlen(path); s > path && *(s - 1) == '/'; s--);
625 			*s = 0;
626 			f->fts_namelen = s - path;
627 		}
628 		sb = f->fts_statp;
629 		if (!*path)
630 		{
631 			errno = ENOENT;
632 			f->fts_info = FTS_NS;
633 		}
634 		else
635 			info(fts, f, path, sb, fts->flags);
636 #ifdef S_ISLNK
637 
638 		/*
639 		 * don't let any standards committee get
640 		 * away with calling your idea a hack
641 		 */
642 
643 		if (metaphysical && f->fts_info == FTS_SL && stat(path, &st) >= 0)
644 		{
645 			*sb = st;
646 			info(fts, f, NiL, sb, 0);
647 		}
648 #endif
649 		if (fts->comparf)
650 			root = search(f, root, fts->comparf, 1);
651 		else if (bot)
652 		{
653 			bot->fts_link = f;
654 			bot = f;
655 		}
656 		else
657 			top = bot = f;
658 	}
659 	if (fts->comparf)
660 		getlist(&top, &bot, root);
661 	return top;
662 }
663 
664 /*
665  * resize the path buffer
666  * note that free() is not used because we may need to chdir(fts->home)
667  * if there isn't enough space to continue
668  */
669 
670 static int
671 resize(register FTS* fts, int inc)
672 {
673 	register char*	old;
674 	register char*	newp;
675 	register int	n_old;
676 
677 	/*
678 	 * add space for "/." used in testing FTS_DNX
679 	 */
680 
681 	n_old = fts->homesize;
682 	fts->homesize = ((fts->homesize + inc + 4) / PATH_MAX + 1) * PATH_MAX;
683 	if (!(newp = newof(0, char, fts->homesize, 0)))
684 	{
685 		fts->fts_errno = errno;
686 		fts->state = FTS_error;
687 		return -1;
688 	}
689 	old = fts->home;
690 	fts->home = newp;
691 	memcpy(newp, old, n_old);
692 	if (fts->endbuf)
693 		fts->endbuf = newp + fts->homesize - 4;
694 	if (fts->path)
695 		fts->path = newp + (fts->path - old);
696 	if (fts->base)
697 		fts->base = newp + (fts->base - old);
698 	free(old);
699 	return 0;
700 }
701 
702 /*
703  * open a new fts stream on pathnames
704  */
705 
706 FTS*
707 fts_open(char* const* pathnames, int flags, int (*comparf)(FTSENT* const*, FTSENT* const*))
708 {
709 	register FTS*	fts;
710 
711 	if (!(fts = newof(0, FTS, 1, sizeof(FTSENT))))
712 		return 0;
713 	fts->flags = flags;
714 	fts->cd = (flags & FTS_NOCHDIR) ? 1 : -1;
715 	fts->comparf = comparf;
716 	fts->fs3d = fs3d(FS3D_TEST);
717 
718 	/*
719 	 * set up the path work buffer
720 	 */
721 
722 	fts->homesize = 2 * PATH_MAX;
723 	for (;;)
724 	{
725 		if (!(fts->home = newof(fts->home, char, fts->homesize, 0)))
726 		{
727 			free(fts);
728 			return 0;
729 		}
730 		if (fts->cd > 0 || getcwd(fts->home, fts->homesize))
731 			break;
732 		if (errno == ERANGE)
733 			fts->homesize += PATH_MAX;
734 		else
735 			fts->cd = 1;
736 	}
737 	fts->endbuf = fts->home + fts->homesize - 4;
738 
739 	/*
740 	 * initialize the tippity-top
741 	 */
742 
743 	fts->parent = (FTSENT*)(fts + 1);
744 	fts->parent->fts_info = FTS_D;
745 	memcpy(fts->parent->fts_accpath = fts->parent->fts_path = fts->parent->fts_name = fts->parent->name, ".", 2);
746 	fts->parent->fts_level = -1;
747 	fts->parent->fts_statp = &fts->parent->statb;
748 	fts->parent->must = 2;
749 	fts->parent->type = DT_UNKNOWN;
750 	fts->path = fts->home + strlen(fts->home) + 1;
751 
752 	/*
753 	 * make the list of top elements
754 	 */
755 
756 	if (!pathnames || (flags & FTS_ONEPATH) || !*pathnames)
757 	{
758 		char*	v[2];
759 
760 		v[0] = pathnames && (flags & FTS_ONEPATH) ? (char*)pathnames : ".";
761 		v[1] = 0;
762 		fts->todo = toplist(fts, v);
763 	}
764 	else
765 		fts->todo = toplist(fts, pathnames);
766 	if (!fts->todo || fts->todo->fts_info == FTS_NS && !fts->todo->fts_link)
767 	{
768 		fts_close(fts);
769 		return 0;
770 	}
771 	return fts;
772 }
773 
774 /*
775  * return the next FTS entry
776  */
777 
778 FTSENT*
779 fts_read(register FTS* fts)
780 {
781 	register char*		s;
782 	register int		n;
783 	register FTSENT*	f;
784 	struct dirent*		d;
785 	int			i;
786 	FTSENT*			t;
787 	Notify_t*		p;
788 #ifdef verify
789 	struct stat		sb;
790 #endif
791 
792 	for (;;) switch (fts->state)
793 	{
794 
795 	case FTS_top_return:
796 
797 		f = fts->todo;
798 		t = 0;
799 		while (f)
800 			if (f->status == FTS_SKIP)
801 			{
802 				if (t)
803 				{
804 					t->fts_link = f->fts_link;
805 					drop(fts, f);
806 					f = t->fts_link;
807 				}
808 				else
809 				{
810 					fts->todo = f->fts_link;
811 					drop(fts, f);
812 					f = fts->todo;
813 				}
814 			}
815 			else
816 			{
817 				t = f;
818 				f = f->fts_link;
819 			}
820 		/*FALLTHROUGH*/
821 
822 	case 0:
823 
824 		if (!(f = fts->todo))
825 			return 0;
826 		/*FALLTHROUGH*/
827 
828 	case FTS_todo:
829 
830 		/*
831 		 * process the top object on the stack
832 		 */
833 
834 		fts->root = fts->top = fts->bot = 0;
835 
836 		/*
837 		 * initialize the top level
838 		 */
839 
840 		if (f->fts_level == 0)
841 		{
842 			fts->parent->fts_number = f->fts_number;
843 			fts->parent->fts_pointer = f->fts_pointer;
844 			fts->parent->fts_statp = f->fts_statp;
845 			fts->parent->statb = *f->fts_statp;
846 			f->fts_parent = fts->parent;
847 			fts->diroot = 0;
848 			if (fts->cd == 0)
849 				pathcd(fts->home, NiL);
850 			else if (fts->cd < 0)
851 				fts->cd = 0;
852 			fts->pwd = f->fts_parent;
853 			fts->curdir = fts->cd ? 0 : f->fts_parent;
854 			*(fts->base = fts->path) = 0;
855 		}
856 
857 		/*
858 		 * chdir to parent if asked for
859 		 */
860 
861 		if (fts->cd < 0)
862 		{
863 			fts->cd = setdir(fts->home, fts->path);
864 			fts->pwd = f->fts_parent;
865 			fts->curdir = fts->cd ? 0 : f->fts_parent;
866 		}
867 
868 		/*
869 		 * add object's name to the path
870 		 */
871 
872 		if ((fts->baselen = f->fts_namelen) >= (fts->endbuf - fts->base) && resize(fts, fts->baselen))
873 			return 0;
874 		memcpy(fts->base, f->name, fts->baselen + 1);
875 		fts->name = fts->cd ? fts->path : fts->base;
876 		/*FALLTHROUGH*/
877 
878 	case FTS_preorder:
879 
880 		/*
881 		 * check for cycle and open dir
882 		 */
883 
884 		if (f->fts_info == FTS_D)
885 		{
886 			if ((fts->diroot = search(f, fts->diroot, statcmp, 0)) != f || f->fts_level > 0 && (t = f) && statcmp(&t, &f->fts_parent) == 0)
887 			{
888 				f->fts_info = FTS_DC;
889 				f->fts_cycle = fts->diroot;
890 			}
891 			else if (!(fts->flags & FTS_TOP) && (!(fts->flags & FTS_XDEV) || f->statb.st_dev == f->fts_parent->statb.st_dev))
892 			{
893 				/*
894 				 * buffer is known to be large enough here!
895 				 */
896 
897 				if (fts->base[fts->baselen - 1] != '/')
898 					memcpy(fts->base + fts->baselen, "/.", 3);
899 				if (!(fts->dir = opendir(fts->name)))
900 					f->fts_info = FTS_DNX;
901 				fts->base[fts->baselen] = 0;
902 				if (!fts->dir && !(fts->dir = opendir(fts->name)))
903 					f->fts_info = FTS_DNR;
904 			}
905 		}
906 		f->nd = f->fts_info & ~FTS_DNX;
907 		if (f->nd || !(fts->flags & FTS_NOPREORDER))
908 		{
909 			fts->current = f;
910 			fts->link = f->fts_link;
911 			f->fts_link = 0;
912 			f->fts_path = PATH(fts, fts->path, f->fts_level);
913 			f->fts_pathlen = (fts->base - f->fts_path) + fts->baselen;
914 			f->fts_accpath = ACCESS(fts, f);
915 			fts->state = FTS_preorder_return;
916 			goto note;
917 		}
918 		/*FALLTHROUGH*/
919 
920 	case FTS_preorder_resume:
921 
922 		/*
923 		 * prune
924 		 */
925 
926 		if (!fts->dir || f->nd || f->status == FTS_SKIP)
927 		{
928 			if (fts->dir)
929 			{
930 				closedir(fts->dir);
931 				fts->dir = 0;
932 			}
933 			fts->state = FTS_popstack;
934 			continue;
935 		}
936 
937 		/*
938 		 * FTS_D or FTS_DNX, about to read children
939 		 */
940 
941 		if (fts->cd == 0)
942 		{
943 			if ((fts->cd = chdir(fts->name)) < 0)
944 				pathcd(fts->home, NiL);
945 			else if (fts->pwd != f)
946 			{
947 				f->pwd = fts->pwd;
948 				fts->pwd = f;
949 			}
950 			fts->curdir = fts->cd < 0 ? 0 : f;
951 		}
952 		fts->nostat = fts->children > 1 || f->fts_info == FTS_DNX;
953 		fts->cpname = fts->cd && !fts->nostat || !fts->children && !fts->comparf;
954 		fts->dotdot = 0;
955 		fts->endbase = fts->base + fts->baselen;
956 		if (fts->endbase[-1] != '/')
957 			*fts->endbase++ = '/';
958 		fts->current = f;
959 		/*FALLTHROUGH*/
960 
961 	case FTS_readdir:
962 
963 		while (d = readdir(fts->dir))
964 		{
965 			s = d->d_name;
966 			if (s[0] == '.')
967 			{
968 				if (s[1] == 0)
969 				{
970 					fts->current->nlink--;
971 					if (!(fts->flags & FTS_SEEDOT))
972 						continue;
973 					n = 1;
974 				}
975 				else if (s[1] == '.' && s[2] == 0)
976 				{
977 					fts->current->nlink--;
978 					if (fts->current->must == 1)
979 						fts->current->must = 0;
980 					if (!(fts->flags & FTS_SEEDOT))
981 						continue;
982 					n = 2;
983 				}
984 				else
985 					n = 0;
986 			}
987 			else
988 				n = 0;
989 
990 			/*
991 			 * make a new entry
992 			 */
993 
994 			i = D_NAMLEN(d);
995 			if (!(f = node(fts, fts->current, s, i)))
996 				return 0;
997 			TYPE(f, D_TYPE(d));
998 
999 			/*
1000 			 * check for space
1001 			 */
1002 
1003 			if (i >= fts->endbuf - fts->endbase)
1004 			{
1005 	   	   		if (resize(fts, i))
1006 					return 0;
1007 				fts->endbase = fts->base + fts->baselen;
1008 				if (fts->endbase[-1] != '/')
1009 					fts->endbase++;
1010 			}
1011 			if (fts->cpname)
1012 			{
1013 				memcpy(fts->endbase, s, i + 1);
1014 				if (fts->cd)
1015 					s = fts->path;
1016 			}
1017 			if (n)
1018 			{
1019 				/*
1020 				 * don't recurse on . and ..
1021 				 */
1022 
1023 				if (n == 1)
1024 					f->fts_statp = fts->current->fts_statp;
1025 				else
1026 				{
1027 					if (f->fts_info != FTS_NS)
1028 						fts->dotdot = f;
1029 					if (fts->current->fts_parent->fts_level < 0)
1030 					{
1031 						f->fts_statp = &fts->current->fts_parent->statb;
1032 						info(fts, f, s, f->fts_statp, 0);
1033 					}
1034 					else
1035 						f->fts_statp = fts->current->fts_parent->fts_statp;
1036 				}
1037 				f->fts_info = FTS_DOT;
1038 			}
1039 			else if ((fts->nostat || SKIP(fts, f)) && (f->fts_info = FTS_NSOK) || info(fts, f, s, &f->statb, fts->flags))
1040 				f->statb.st_ino = D_FILENO(d);
1041 			if (fts->comparf)
1042 				fts->root = search(f, fts->root, fts->comparf, 1);
1043 			else if (fts->children || f->fts_info == FTS_D || f->fts_info == FTS_SL)
1044 			{
1045 				if (fts->top)
1046 					fts->bot = fts->bot->fts_link = f;
1047 				else
1048 					fts->top = fts->bot = f;
1049 			}
1050 			else
1051 			{
1052 				/*
1053 				 * terminal node
1054 				 */
1055 
1056 				f->fts_path = PATH(fts, fts->path, 1);
1057 				f->fts_pathlen = fts->endbase - f->fts_path + f->fts_namelen;
1058 				f->fts_accpath = ACCESS(fts, f);
1059 				fts->previous = fts->current;
1060 				fts->current = f;
1061 				fts->state = FTS_terminal;
1062 				goto note;
1063 			}
1064 		}
1065 
1066 		/*
1067 		 * done with the directory
1068 		 */
1069 
1070 		closedir(fts->dir);
1071 		fts->dir = 0;
1072 		if (fts->root)
1073 			getlist(&fts->top, &fts->bot, fts->root);
1074 		if (fts->children)
1075 		{
1076 			/*
1077 			 * try moving back to parent dir
1078 			 */
1079 
1080 			fts->base[fts->baselen] = 0;
1081 			if (fts->cd <= 0)
1082 			{
1083 				f = fts->current->fts_parent;
1084 				if (fts->cd < 0
1085 				    || f != fts->curdir
1086 				    || !fts->dotdot
1087 				    || !SAME(f->fts_statp, fts->dotdot->fts_statp)
1088 				    || fts->pwd && fts->pwd->symlink
1089 				    || (fts->cd = chdir("..")) < 0
1090 #ifdef verify
1091 				    || stat(".", &sb) < 0
1092 				    || !SAME(&sb, fts->dotdot->fts_statp)
1093 #endif
1094 				    )
1095 					fts->cd = setpdir(fts->home, fts->path, fts->base);
1096 				if (fts->pwd)
1097 					fts->pwd = fts->pwd->pwd;
1098 				fts->curdir = fts->cd ? 0 : f;
1099 			}
1100 			f = fts->current;
1101 			fts->link = f->fts_link;
1102 			f->fts_link = fts->top;
1103 			f->fts_path = PATH(fts, fts->path, f->fts_level);
1104 			f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1105 			f->fts_accpath = ACCESS(fts, f);
1106 			fts->state = FTS_children_return;
1107 			goto note;
1108 		}
1109 		/*FALLTHROUGH*/
1110 
1111 	case FTS_children_resume:
1112 
1113 		fts->base[fts->baselen] = 0;
1114 		if (fts->top)
1115 		{
1116 			fts->bot->fts_link = fts->todo;
1117 			fts->todo = fts->top;
1118 			fts->top = 0;
1119 		}
1120 		/*FALLTHROUGH*/
1121 
1122 	case FTS_popstack:
1123 
1124 		/*
1125 		 * pop objects completely processed
1126 		 */
1127 
1128 		fts->nd = 0;
1129 		f = fts->current;
1130 		/*FALLTHROUGH*/
1131 
1132 	case FTS_popstack_resume:
1133 
1134 		while (fts->todo && f == fts->todo)
1135 		{
1136 			t = f->fts_parent;
1137 			if ((f->fts_info & FTS_DP) == FTS_D)
1138 			{
1139 				/*
1140 				 * delete from <dev,ino> tree
1141 				 */
1142 
1143 				if (f != fts->diroot)
1144 					fts->diroot = search(f, fts->diroot, statcmp, 0);
1145 				fts->diroot = deleteroot(fts->diroot);
1146 				if (f == fts->curdir)
1147 				{
1148 					fts->nd++;
1149 					fts->curdir = t;
1150 				}
1151 
1152 				/*
1153 				 * perform post-order processing
1154 				 */
1155 
1156 				if (!(fts->flags & FTS_NOPOSTORDER) &&
1157 				    f->status != FTS_SKIP &&
1158 				    f->status != FTS_NOPOSTORDER)
1159 				{
1160 					/*
1161 					 * move to parent dir
1162 					 */
1163 
1164 					if (fts->nd > 0)
1165 						fts->cd = popdirs(fts);
1166 					if (fts->cd < 0)
1167 						fts->cd = setpdir(fts->home, fts->path, fts->base);
1168 					fts->curdir = fts->cd ? 0 : t;
1169 					f->fts_info = FTS_DP;
1170 					f->fts_path = PATH(fts, fts->path, f->fts_level);
1171 					f->fts_pathlen = (fts->base - f->fts_path) + f->fts_namelen;
1172 					f->fts_accpath = ACCESS(fts, f);
1173 
1174 					/*
1175 					 * re-stat to update nlink/times
1176 					 */
1177 
1178 					stat(f->fts_accpath, f->fts_statp);
1179 					fts->link = f->fts_link;
1180 					f->fts_link = 0;
1181 					fts->state = FTS_popstack_return;
1182 					goto note;
1183 				}
1184 			}
1185 
1186 			/*
1187 			 * reset base
1188 			 */
1189 
1190 			if (fts->base > fts->path + t->fts_namelen)
1191 				fts->base--;
1192 			*fts->base = 0;
1193 			fts->base -= t->fts_namelen;
1194 
1195 			/*
1196 			 * try again or delete from top of stack
1197 			 */
1198 
1199 			if (f->status == FTS_AGAIN)
1200 			{
1201 				f->fts_info = FTS_D;
1202 				f->status = 0;
1203 			}
1204 			else
1205 			{
1206 				fts->todo = fts->todo->fts_link;
1207 				drop(fts, f);
1208 			}
1209 			f = t;
1210 		}
1211 
1212 		/*
1213 		 * reset current directory
1214 		 */
1215 
1216 		if (fts->nd > 0 && popdirs(fts) < 0)
1217 		{
1218 			pathcd(fts->home, NiL);
1219 			fts->curdir = 0;
1220 			fts->cd = -1;
1221 		}
1222 		if (fts->todo)
1223 		{
1224 			if (*fts->base)
1225 				fts->base += f->fts_namelen;
1226 			if (*(fts->base - 1) != '/')
1227 				*fts->base++ = '/';
1228 			*fts->base = 0;
1229 			f = fts->todo;
1230 			fts->state = FTS_todo;
1231 			continue;
1232 		}
1233 		return 0;
1234 
1235 	case FTS_children_return:
1236 
1237 		f = fts->current;
1238 		f->fts_link = fts->link;
1239 
1240 		/*
1241 		 * chdir down again
1242 		 */
1243 
1244 		i = f->fts_info != FTS_DNX;
1245 		n = f->status == FTS_SKIP;
1246 		if (!n && fts->cd == 0)
1247 		{
1248 			if ((fts->cd = chdir(fts->base)) < 0)
1249 				pathcd(fts->home, NiL);
1250 			else if (fts->pwd != f)
1251 			{
1252 				f->pwd = fts->pwd;
1253 				fts->pwd = f;
1254 			}
1255 			fts->curdir = fts->cd ? 0 : f;
1256 		}
1257 
1258 		/*
1259 		 * prune
1260 		 */
1261 
1262 		if (fts->base[fts->baselen - 1] != '/')
1263 			fts->base[fts->baselen] = '/';
1264 		for (fts->bot = 0, f = fts->top; f; )
1265 			if (n || f->status == FTS_SKIP)
1266 			{
1267 				if (fts->bot)
1268 					fts->bot->fts_link = f->fts_link;
1269 				else
1270 					fts->top = f->fts_link;
1271 				drop(fts, f);
1272 				f = fts->bot ? fts->bot->fts_link : fts->top;
1273 			}
1274 			else
1275 			{
1276 				if (fts->children > 1 && i)
1277 				{
1278 					if (f->status == FTS_STAT)
1279 						info(fts, f, NiL, f->fts_statp, 0);
1280 					else if (f->fts_info == FTS_NSOK && !SKIP(fts, f))
1281 					{
1282 						s = f->fts_name;
1283 						if (fts->cd)
1284 						{
1285 							memcpy(fts->endbase, s, f->fts_namelen + 1);
1286 							s = fts->path;
1287 						}
1288 						info(fts, f, s, f->fts_statp, fts->flags);
1289 					}
1290 				}
1291 				fts->bot = f;
1292 				f = f->fts_link;
1293 			}
1294 		fts->children = 0;
1295 		fts->state = FTS_children_resume;
1296 		continue;
1297 
1298 	case FTS_popstack_return:
1299 
1300 		f = fts->todo;
1301 		f->fts_link = fts->link;
1302 		f->fts_info = f->status == FTS_AGAIN ? FTS_DP : 0;
1303 		fts->state = FTS_popstack_resume;
1304 		continue;
1305 
1306 	case FTS_preorder_return:
1307 
1308 		f = fts->current;
1309 		f->fts_link = fts->link;
1310 
1311 		/*
1312 		 * follow symlink if asked to
1313 		 */
1314 
1315 		if (f->status == FTS_FOLLOW)
1316 		{
1317 			f->status = 0;
1318 			if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1319 			{
1320 				info(fts, f, f->fts_accpath, f->fts_statp, 0);
1321 				if (f->fts_info != FTS_SL)
1322 				{
1323 					fts->state = FTS_preorder;
1324 					continue;
1325 				}
1326 			}
1327 		}
1328 
1329 		/*
1330 		 * about to prune this f and already at home
1331 		 */
1332 
1333 		if (fts->cd == 0 && f->fts_level == 0 && f->nd)
1334 			fts->cd = -1;
1335 		fts->state = FTS_preorder_resume;
1336 		continue;
1337 
1338 	case FTS_terminal:
1339 
1340 		f = fts->current;
1341 		if (f->status == FTS_FOLLOW)
1342 		{
1343 			f->status = 0;
1344 			if (f->fts_info == FTS_SL || ISTYPE(f, DT_LNK) || f->fts_info == FTS_NSOK)
1345 			{
1346 				info(fts, f, f->fts_accpath, f->fts_statp, 0);
1347 				if (f->symlink && f->fts_info != FTS_SL)
1348 				{
1349 					if (!(f->fts_link = fts->top))
1350 						fts->bot = f;
1351 					fts->top = f;
1352 					fts->current = fts->previous;
1353 					fts->state = FTS_readdir;
1354 					continue;
1355 				}
1356 			}
1357 		}
1358 		f = f->fts_parent;
1359 		drop(fts, fts->current);
1360 		fts->current = f;
1361 		fts->state = FTS_readdir;
1362 		continue;
1363 
1364 	case FTS_error:
1365 
1366 		return 0;
1367 
1368 	default:
1369 
1370 		fts->fts_errno = EINVAL;
1371 		fts->state = FTS_error;
1372 		return 0;
1373 
1374 	}
1375  note:
1376 	for (p = notify; p; p = p->next)
1377 		if ((n = (*p->notifyf)(fts, f, p->context)) > 0)
1378 			break;
1379 		else if (n < 0)
1380 		{
1381 			fts->fts_errno = EINVAL;
1382 			fts->state = FTS_error;
1383 			return 0;
1384 		}
1385 	return f;
1386 }
1387 
1388 /*
1389  * set stream or entry flags
1390  */
1391 
1392 int
1393 fts_set(register FTS* fts, register FTSENT* f, int status)
1394 {
1395 	if (fts || !f || f->fts->current != f)
1396 		return -1;
1397 	switch (status)
1398 	{
1399 	case FTS_AGAIN:
1400 		break;
1401 	case FTS_FOLLOW:
1402 		if (!(f->fts_info & FTS_SL))
1403 			return -1;
1404 		break;
1405 	case FTS_NOPOSTORDER:
1406 		break;
1407 	case FTS_SKIP:
1408 		if ((f->fts_info & (FTS_D|FTS_P)) != FTS_D)
1409 			return -1;
1410 		break;
1411 	default:
1412 		return -1;
1413 	}
1414 	f->status = status;
1415 	return 0;
1416 }
1417 
1418 /*
1419  * return the list of child entries
1420  */
1421 
1422 FTSENT*
1423 fts_children(register FTS* fts, int flags)
1424 {
1425 	register FTSENT*	f;
1426 
1427 	switch (fts->state)
1428 	{
1429 
1430 	case 0:
1431 
1432 		fts->state = FTS_top_return;
1433 		return fts->todo;
1434 
1435 	case FTS_preorder_return:
1436 
1437 		fts->children = ((flags | fts->flags) & FTS_NOSTAT) ? 2 : 1;
1438 		if (f = fts_read(fts))
1439 			f = f->fts_link;
1440 		return f;
1441 
1442 	}
1443 	return 0;
1444 }
1445 
1446 /*
1447  * return default (FTS_LOGICAL|FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR) flags
1448  * conditioned by astconf()
1449  */
1450 
1451 int
1452 fts_flags(void)
1453 {
1454 	register char*	s;
1455 
1456 	s = astconf("PATH_RESOLVE", NiL, NiL);
1457 	if (streq(s, "logical"))
1458 		return FTS_LOGICAL;
1459 	if (streq(s, "physical"))
1460 		return FTS_PHYSICAL|FTS_SEEDOTDIR;
1461 	return FTS_META|FTS_PHYSICAL|FTS_SEEDOTDIR;
1462 }
1463 
1464 /*
1465  * return 1 if ent is mounted on a local filesystem
1466  */
1467 
1468 int
1469 fts_local(FTSENT* ent)
1470 {
1471 #ifdef ST_LOCAL
1472 	struct statvfs	fs;
1473 
1474 	return statvfs(ent->fts_path, &fs) || (fs.f_flag & ST_LOCAL);
1475 #else
1476 	return !strgrpmatch(fmtfs(ent->fts_statp), "([an]fs|samb)", NiL, 0, STR_LEFT|STR_ICASE);
1477 #endif
1478 }
1479 
1480 /*
1481  * close an open fts stream
1482  */
1483 
1484 int
1485 fts_close(register FTS* fts)
1486 {
1487 	register FTSENT*	f;
1488 	register FTSENT*	x;
1489 
1490 	if (fts->dir)
1491 		closedir(fts->dir);
1492 	if (fts->cd == 0)
1493 		pathcd(fts->home, NiL);
1494 	free(fts->home);
1495 	if (fts->state == FTS_children_return)
1496 		fts->current->fts_link = fts->link;
1497 	if (fts->top)
1498 	{
1499 		fts->bot->fts_link = fts->todo;
1500 		fts->todo = fts->top;
1501 	}
1502 	for (f = fts->todo; f; f = x)
1503 	{
1504 		x = f->fts_link;
1505 		free(f);
1506 	}
1507 	for (f = fts->free; f; f = x)
1508 	{
1509 		x = f->fts_link;
1510 		free(f);
1511 	}
1512 	free(fts);
1513 	return 0;
1514 }
1515 
1516 /*
1517  * register function to be called for each fts_read() entry
1518  * context==0 => unregister notifyf
1519  */
1520 
1521 int
1522 fts_notify(Notify_f notifyf, void* context)
1523 {
1524 	register Notify_t*	np;
1525 	register Notify_t*	pp;
1526 
1527 	if (context)
1528 	{
1529 		if (!(np = newof(0, Notify_t, 1, 0)))
1530 			return -1;
1531 		np->notifyf = notifyf;
1532 		np->context = context;
1533 		np->next = notify;
1534 		notify = np;
1535 	}
1536 	else
1537 	{
1538 		for (np = notify, pp = 0; np; pp = np, np = np->next)
1539 			if (np->notifyf == notifyf)
1540 			{
1541 				if (pp)
1542 					pp->next = np->next;
1543 				else
1544 					notify = np->next;
1545 				free(np);
1546 				return 0;
1547 			}
1548 		return -1;
1549 	}
1550 	return 0;
1551 }
1552