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