4 /*-
65 #define	CLR(opt)	(sp->fts_options &= ~(opt))
66 #define	ISSET(opt)	(sp->fts_options & (opt))
67 #define	SET(opt)	(sp->fts_options |= (opt))
93 	sp->fts_compar = compar;  in fts_open()
94 	sp->fts_options = options;  in fts_open()
106 	parent->fts_level = FTS_ROOTPARENTLEVEL;  in fts_open()
112 		p->fts_level = FTS_ROOTLEVEL;  in fts_open()
113 		p->fts_parent = parent;  in fts_open()
114 		p->fts_accpath = p->fts_name;  in fts_open()
115 		p->fts_info = fts_stat(sp, p);  in fts_open()
117 		/* Command-line "." and ".." are real directories. */  in fts_open()
118 		if (p->fts_info == FTS_DOT)  in fts_open()
119 			p->fts_info = FTS_D;  in fts_open()
126 			p->fts_link = root;  in fts_open()
129 			p->fts_link = NULL;  in fts_open()
133 				prev->fts_link = p;  in fts_open()
142 	 * finished the node before the root(s); set p->fts_info to FTS_INIT  in fts_open()
145 	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)  in fts_open()
147 	sp->fts_cur->fts_link = root;  in fts_open()
148 	sp->fts_cur->fts_info = FTS_INIT;  in fts_open()
157 mem2:	free(sp->fts_path);  in fts_open()
169 	 * Load the stream structure for the next traversal.  Since we don't  in fts_load()
175 	len = p->fts_pathlen = p->fts_namelen;  in fts_load()
176 	memmove(sp->fts_path, p->fts_name, len + 1);  in fts_load()
177 	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {  in fts_load()
179 		memmove(p->fts_name, cp, len + 1);  in fts_load()
180 		p->fts_namelen = len;  in fts_load()
182 	p->fts_accpath = p->fts_path = sp->fts_path;  in fts_load()
183 	sp->fts_dev = p->fts_dev;  in fts_load()
192 	 * This still works if we haven't read anything -- the dummy structure  in fts_close()
196 	if (sp->fts_cur) {  in fts_close()
197 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {  in fts_close()
199 			p = p->fts_link ? p->fts_link : p->fts_parent;  in fts_close()
206 	if (sp->fts_child)  in fts_close()
207 		fts_lfree(sp->fts_child);  in fts_close()
208 	free(sp->fts_array);  in fts_close()
209 	free(sp->fts_path);  in fts_close()
216  * Special case of "/" at the end of the path so that slashes aren't
220 	(p->fts_path[p->fts_pathlen - 1] == '/'				\
221 	    ? p->fts_pathlen - 1 : p->fts_pathlen)
228 	char *t;  in fts_read()  local
231 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))  in fts_read()
235 	p = sp->fts_cur;  in fts_read()
238 	instr = p->fts_instr;  in fts_read()
239 	p->fts_instr = FTS_NOINSTR;  in fts_read()
241 	/* Directory in pre-order. */  in fts_read()
242 	if (p->fts_info == FTS_D) {  in fts_read()
243 		/* If skipped or crossed mount point, do post-order visit. */  in fts_read()
245 		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {  in fts_read()
246 			if (sp->fts_child) {  in fts_read()
247 				fts_lfree(sp->fts_child);  in fts_read()
248 				sp->fts_child = NULL;  in fts_read()
250 			p->fts_info = FTS_DP;  in fts_read()
255 		 * If haven't read do so.  If the read fails, fts_build sets  in fts_read()
258 		if (sp->fts_child) {  in fts_read()
260 		} else if ((sp->fts_child = fts_build(sp)) == NULL) {  in fts_read()
265 		p = sp->fts_child;  in fts_read()
266 		sp->fts_child = NULL;  in fts_read()
272 	if ((p = p->fts_link)) {  in fts_read()
279 		if (p->fts_level == FTS_ROOTLEVEL) {  in fts_read()
281 			return (sp->fts_cur = p);  in fts_read()
289 		if (p->fts_instr == FTS_SKIP)  in fts_read()
292 name:		t = sp->fts_path + NAPPEND(p->fts_parent);  in fts_read()
293 		*t++ = '/';  in fts_read()
294 		memmove(t, p->fts_name, p->fts_namelen + 1);  in fts_read()
295 		return (sp->fts_cur = p);  in fts_read()
299 	p = tmp->fts_parent;  in fts_read()
302 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {  in fts_read()
309 		return (sp->fts_cur = NULL);  in fts_read()
313 	sp->fts_path[p->fts_pathlen] = '\0';  in fts_read()
315 	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;  in fts_read()
316 	return (sp->fts_cur = p);  in fts_read()
332 	p->fts_instr = instr;  in fts_set()
337  * This is the tricky part -- do not casually change *anything* in here.  The
342  * set and it's a physical walk (so that symbolic links can't be directories),
354 	FTSENT *p, *head;  in fts_build()  local
364 	cur = sp->fts_cur;  in fts_build()
370 	if ((dirp = opendir(cur->fts_accpath)) == NULL) {  in fts_build()
371 		cur->fts_info = FTS_DNR;  in fts_build()
372 		cur->fts_errno = errno;  in fts_build()
378 	 * current path -- the inner loop allocates more path as necessary.  in fts_build()
379 	 * We really wouldn't have to do the maxlen calculations here, we  in fts_build()
387 	cp = sp->fts_path + len;  in fts_build()
390 	maxlen = sp->fts_pathlen - len;  in fts_build()
396 	level = cur->fts_level;  in fts_build()
402 	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {  in fts_build()
403 		if (ISDOT(dp->d_name))  in fts_build()
407 		dlen = dp->d_namlen;  in fts_build()
409 		dlen = strlen(dp->d_name);  in fts_build()
412 		if (!(p = fts_alloc(sp, dp->d_name, dlen)))  in fts_build()
415 			oldaddr = sp->fts_path;  in fts_build()
424 				fts_lfree(head);  in fts_build()
426 				cur->fts_info = FTS_ERR;  in fts_build()
432 			if (oldaddr != sp->fts_path) {  in fts_build()
434 				cp = sp->fts_path + len;  in fts_build()
436 			maxlen = sp->fts_pathlen - len;  in fts_build()
439 		p->fts_level = level;  in fts_build()
440 		p->fts_parent = sp->fts_cur;  in fts_build()
441 		p->fts_pathlen = len + dlen;  in fts_build()
442 		if (p->fts_pathlen < len) {  in fts_build()
449 			fts_lfree(head);  in fts_build()
451 			cur->fts_info = FTS_ERR;  in fts_build()
458 		p->fts_accpath = p->fts_path;  in fts_build()
459 		memmove(cp, p->fts_name, p->fts_namelen + 1);  in fts_build()
461 		p->fts_info = fts_stat(sp, p);  in fts_build()
463 		/* We walk in directory order so "ls -f" doesn't get upset. */  in fts_build()
464 		p->fts_link = NULL;  in fts_build()
465 		if (head == NULL)  in fts_build()
466 			head = tail = p;  in fts_build()
468 			tail->fts_link = p;  in fts_build()
481 		fts_padjust(sp, head);  in fts_build()
487 	if (len == sp->fts_pathlen || nitems == 0)  in fts_build()
488 		--cp;  in fts_build()
491 	/* If didn't find anything, return NULL. */  in fts_build()
493 		cur->fts_info = FTS_DP;  in fts_build()
498 	if (sp->fts_compar && nitems > 1)  in fts_build()
499 		head = fts_sort(sp, head, nitems);  in fts_build()
500 	return (head);  in fts_build()
506 	FTSENT *t;  in fts_stat()  local
512 	sbp = p->fts_statp;  in fts_stat()
514 	if (lstat(p->fts_accpath, sbp)) {  in fts_stat()
515 		p->fts_errno = errno;  in fts_stat()
520 	if (S_ISDIR(sbp->st_mode)) {  in fts_stat()
528 		dev = p->fts_dev = sbp->st_dev;  in fts_stat()
529 		ino = p->fts_ino = sbp->st_ino;  in fts_stat()
530 		p->fts_nlink = sbp->st_nlink;  in fts_stat()
532 		if (ISDOT(p->fts_name))  in fts_stat()
541 		for (t = p->fts_parent;  in fts_stat()
542 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)  in fts_stat()
543 			if (ino == t->fts_ino && dev == t->fts_dev) {  in fts_stat()
544 				p->fts_cycle = t;  in fts_stat()
549 	if (S_ISLNK(sbp->st_mode))  in fts_stat()
551 	if (S_ISREG(sbp->st_mode))  in fts_stat()
557 fts_sort(FTS *sp, FTSENT *head, int nitems)  in fts_sort()  argument
566 	 * 40 so don't realloc one entry at a time.  in fts_sort()
568 	if (nitems > sp->fts_nitems) {  in fts_sort()
571 		if ((a = reallocarray(sp->fts_array,  in fts_sort()
573 			free(sp->fts_array);  in fts_sort()
574 			sp->fts_array = NULL;  in fts_sort()
575 			sp->fts_nitems = 0;  in fts_sort()
576 			return (head);  in fts_sort()
578 		sp->fts_nitems = nitems + 40;  in fts_sort()
579 		sp->fts_array = a;  in fts_sort()
581 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)  in fts_sort()
583 	qsort(sp->fts_array, nitems, sizeof(FTSENT *),  in fts_sort()
584 	    (qsort_compar_proto)sp->fts_compar);  in fts_sort()
585 	for (head = *(ap = sp->fts_array); --nitems; ++ap)  in fts_sort()
586 		ap[0]->fts_link = ap[1];  in fts_sort()
587 	ap[0]->fts_link = NULL;  in fts_sort()
588 	return (head);  in fts_sort()
601 	p->fts_path = sp->fts_path;  in fts_alloc()
602 	p->fts_namelen = namelen;  in fts_alloc()
603 	p->fts_instr = FTS_NOINSTR;  in fts_alloc()
604 	p->fts_statp = malloc(sizeof(struct stat));  in fts_alloc()
605 	if (p->fts_statp == NULL) {  in fts_alloc()
609 	memcpy(p->fts_name, name, namelen);  in fts_alloc()
615 fts_lfree(FTSENT *head)  in fts_lfree()  argument
620 	while ((p = head)) {  in fts_lfree()
621 		head = head->fts_link;  in fts_lfree()
629  * though the kernel won't resolve them.  Add the size (not just what's needed)
630  * plus 256 bytes so don't realloc the path 2 bytes at a time.
641 	if (sp->fts_pathlen + more < sp->fts_pathlen) {  in fts_palloc()
642 		free(sp->fts_path);  in fts_palloc()
643 		sp->fts_path = NULL;  in fts_palloc()
647 	p = recallocarray(sp->fts_path, sp->fts_pathlen,  in fts_palloc()
648 	    sp->fts_pathlen + more, 1);  in fts_palloc()
650 		free(sp->fts_path);  in fts_palloc()
651 		sp->fts_path = NULL;  in fts_palloc()
654 	sp->fts_pathlen += more;  in fts_palloc()
655 	sp->fts_path = p;  in fts_palloc()
664 fts_padjust(FTS *sp, FTSENT *head)  in fts_padjust()  argument
667 	char *addr = sp->fts_path;  in fts_padjust()
670 	if ((p)->fts_accpath != (p)->fts_name) {			\  in fts_padjust()
671 		(p)->fts_accpath =					\  in fts_padjust()
672 		    (char *)addr + ((p)->fts_accpath - (p)->fts_path);	\  in fts_padjust()
674 	(p)->fts_path = addr;						\  in fts_padjust()
677 	for (p = sp->fts_child; p; p = p->fts_link)  in fts_padjust()
681 	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {  in fts_padjust()
683 		p = p->fts_link ? p->fts_link : p->fts_parent;  in fts_padjust()