static FTSENT	*fts_build __P((FTS *, int)); static void	 fts_lfree __P((FTSENT *)); static void	 fts_load __P((FTS *, FTSENT *)); static size_t	 fts_maxarglen __P((char * const *)); static void	 fts_padjust __P((FTS *, void *)); static int	 fts_palloc __P((FTS *, size_t)); static FTSENT	*fts_sort __P((FTS *, FTSENT *, int)); static u_short	 fts_stat __P((FTS *, FTSENT *, int)); static int	 fts_safe_changedir __P((FTS *, FTSENT *, int));  #define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))  #define	CLR(opt)	(sp->fts_options &= ~(opt)) #define	ISSET(opt)	(sp->fts_options & (opt)) #define	SET(opt)	(sp->fts_options |= (opt))  #define	CHDIR(sp, path)	(!ISSET(FTS_NOCHDIR) && chdir(path)) #define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))   #define	BCHILD		1		 #define	BNAMES		2		 #define	BREAD		3		  FTS * fts_open(argv, options, compar) char * const *argv; register int options; int (*compar) __P((const FTSENT **, const FTSENT **)); { register FTS *sp; register FTSENT *p, *root; register int nitems; FTSENT *parent, *tmp; int len;   if (options & ~FTS_OPTIONMASK) { errno = EINVAL; return (NULL); }   if ((sp = malloc((u_int)sizeof(FTS))) == NULL) return (NULL); memset(sp, 0, sizeof(FTS)); sp->fts_compar = compar; sp->fts_options = options;   if (ISSET(FTS_LOGICAL)) SET(FTS_NOCHDIR);   if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) goto mem1;   if ((parent = fts_alloc(sp, "", 0)) == NULL) goto mem2; parent->fts_level = FTS_ROOTPARENTLEVEL;   for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {  if ((len = strlen(*argv)) == 0) { errno = ENOENT; goto mem3; }  p = fts_alloc(sp, *argv, len); p->fts_level = FTS_ROOTLEVEL; p->fts_parent = parent; p->fts_accpath = p->fts_name; p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));   if (p->fts_info == FTS_DOT) p->fts_info = FTS_D;   if (compar) { p->fts_link = root; root = p; } else { p->fts_link = NULL; if (root == NULL) tmp = root = p; else { tmp->fts_link = p; tmp = p; } } } if (compar && nitems > 1) root = fts_sort(sp, root, nitems);   if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) goto mem3; sp->fts_cur->fts_link = root; sp->fts_cur->fts_info = FTS_INIT;   if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) SET(FTS_NOCHDIR);  return (sp);  mem3:	fts_lfree(root); free(parent); mem2:	free(sp->fts_path); mem1:	free(sp); return (NULL); }  static void fts_load(sp, p) FTS *sp; register FTSENT *p; { register int len; register char *cp;   len = p->fts_pathlen = p->fts_namelen; memmove(sp->fts_path, p->fts_name, len + 1); if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { len = strlen(++cp); memmove(p->fts_name, cp, len + 1); p->fts_namelen = len; } p->fts_accpath = p->fts_path = sp->fts_path; sp->fts_dev = p->fts_dev; }  int fts_close(sp) FTS *sp; { register FTSENT *freep, *p; int saved_errno;   if (sp->fts_cur) { for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { freep = p; p = p->fts_link ? p->fts_link : p->fts_parent; free(freep); } free(p); }   if (sp->fts_child) fts_lfree(sp->fts_child); if (sp->fts_array) free(sp->fts_array); free(sp->fts_path);   if (!ISSET(FTS_NOCHDIR)) { saved_errno = fchdir(sp->fts_rfd) ? errno : 0; (void)close(sp->fts_rfd); }   if (!ISSET(FTS_NOCHDIR) && saved_errno) {  free(sp); errno = saved_errno; return (-1); }   free(sp); return (0); }   #define	NAPPEND(p)							\ (p->fts_path[p->fts_pathlen - 1] == '/'				\ ? p->fts_pathlen - 1 : p->fts_pathlen)  FTSENT * fts_read(sp) register FTS *sp; { register FTSENT *p, *tmp; register int instr; register char *t; int saved_errno;   if (sp->fts_cur == NULL || ISSET(FTS_STOP)) return (NULL);   p = sp->fts_cur;   instr = p->fts_instr; p->fts_instr = FTS_NOINSTR;   if (instr == FTS_AGAIN) { p->fts_info = fts_stat(sp, p, 0); return (p); }   if (instr == FTS_FOLLOW && (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { p->fts_info = fts_stat(sp, p, 1); if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) { p->fts_errno = errno; p->fts_info = FTS_ERR; } else p->fts_flags |= FTS_SYMFOLLOW; } return (p); }   if (p->fts_info == FTS_D) {  if (instr == FTS_SKIP || (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { if (p->fts_flags & FTS_SYMFOLLOW) (void)close(p->fts_symfd); if (sp->fts_child) { fts_lfree(sp->fts_child); sp->fts_child = NULL; } p->fts_info = FTS_DP; return (p); }   if (sp->fts_child && ISSET(FTS_NAMEONLY)) { CLR(FTS_NAMEONLY); fts_lfree(sp->fts_child); sp->fts_child = NULL; }   if (sp->fts_child) { if (fts_safe_changedir(sp, p, -1)) { p->fts_errno = errno; p->fts_flags |= FTS_DONTCHDIR; for (p = sp->fts_child; p; p = p->fts_link) p->fts_accpath = p->fts_parent->fts_accpath; } } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { if (ISSET(FTS_STOP)) return (NULL); return (p); } p = sp->fts_child; sp->fts_child = NULL; goto name; }   next:	tmp = p; if ((p = p->fts_link)) { free(tmp);   if (p->fts_level == FTS_ROOTLEVEL) { if ((sp->fts_options & FTS_CHDIRROOT)) { if (chdir(p->fts_accpath)) { SET(FTS_STOP); return (NULL); } } else { if (FCHDIR(sp, sp->fts_rfd)) { SET(FTS_STOP); return (NULL); } } fts_load(sp, p); return (sp->fts_cur = p); }   if (p->fts_instr == FTS_SKIP) goto next; if (p->fts_instr == FTS_FOLLOW) { p->fts_info = fts_stat(sp, p, 1); if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) { p->fts_errno = errno; p->fts_info = FTS_ERR; } else p->fts_flags |= FTS_SYMFOLLOW; } p->fts_instr = FTS_NOINSTR; }  name:		t = sp->fts_path + NAPPEND(p->fts_parent); *t++ = '/'; memmove(t, p->fts_name, p->fts_namelen + 1); return (sp->fts_cur = p); }   p = tmp->fts_parent; free(tmp);  if (p->fts_level == FTS_ROOTPARENTLEVEL) {  free(p); errno = 0; return (sp->fts_cur = NULL); }   sp->fts_path[p->fts_pathlen] = '\0';   if (p->fts_level == FTS_ROOTLEVEL) { if ((sp->fts_options & FTS_CHDIRROOT)) { if (chdir(p->fts_accpath)) { SET(FTS_STOP); return (NULL); } } else { if (FCHDIR(sp, sp->fts_rfd)) { SET(FTS_STOP); return (NULL); } } } else if (p->fts_flags & FTS_SYMFOLLOW) { if (FCHDIR(sp, p->fts_symfd)) { saved_errno = errno; (void)close(p->fts_symfd); errno = saved_errno; SET(FTS_STOP); return (NULL); } (void)close(p->fts_symfd); } else if (!(p->fts_flags & FTS_DONTCHDIR)) { if (CHDIR(sp, "..")) { SET(FTS_STOP); return (NULL); } } p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; return (sp->fts_cur = p); }    int fts_set(sp, p, instr) FTS *sp; FTSENT *p; int instr; { if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW && instr != FTS_NOINSTR && instr != FTS_SKIP) { errno = EINVAL; return (1); } p->fts_instr = instr; return (0); }  FTSENT * fts_children(sp, instr) register FTS *sp; int instr; { register FTSENT *p; int fd;  if (instr && instr != FTS_NAMEONLY) { errno = EINVAL; return (NULL); }   p = sp->fts_cur;   errno = 0;   if (ISSET(FTS_STOP)) return (NULL);   if (p->fts_info == FTS_INIT) return (p->fts_link);   if (p->fts_info != FTS_D ) return (NULL);   if (sp->fts_child) fts_lfree(sp->fts_child);  if (instr == FTS_NAMEONLY) { SET(FTS_NAMEONLY); instr = BNAMES; } else instr = BCHILD;   if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || ISSET(FTS_NOCHDIR)) return (sp->fts_child = fts_build(sp, instr));  if ((fd = open(".", O_RDONLY, 0)) < 0) return (NULL); sp->fts_child = fts_build(sp, instr); if (fchdir(fd)) return (NULL); (void)close(fd); return (sp->fts_child); }   static FTSENT *
fts_build(sp, type)	register FTS *sp;	int type;{	register struct dirent *dp;	register FTSENT *p, *head;	register int nitems;	FTSENT *cur, *tail;	DIR *dirp;	void *adjaddr;	int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno,	    nostat;	char *cp;	/* Set current node pointer. */	cur = sp->fts_cur;	/*	 * Open the directory for reading.  If this fails, we're done.	 * If being called from fts_read, set the fts_info field.	 */#ifdef FTS_WHITEOUT	if (ISSET(FTS_WHITEOUT))		oflag = DTF_NODUP|DTF_REWIND;	else		oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;#else#define __opendir2(path, flag) opendir(path)#endif	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {		if (type == BREAD) {			cur->fts_info = FTS_DNR;			cur->fts_errno = errno;		}		return (NULL);	}	/*	 * Nlinks is the number of possible entries of type directory in the	 * directory if we're cheating on stat calls, 0 if we're not doing	 * any stat calls at all, -1 if we're doing stats on everything.	 */	if (type == BNAMES)		nlinks = 0;	else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {		nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);		nostat = 1;	} else {		nlinks = -1;		nostat = 0;	}#ifdef notdef	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));#endif	/*	 * If we're going to need to stat anything or we want to descend	 * and stay in the directory, chdir.  If this fails we keep going,	 * but set a flag so we don't chdir after the post-order visit.	 * We won't be able to stat anything, but we can still return the	 * names themselves.  Note, that since fts_read won't be able to	 * chdir into the directory, it will have to return different path	 * names than before, i.e. "a/b" instead of "b".  Since the node	 * has already been visited in pre-order, have to wait until the	 * post-order visit to return the error.  There is a special case	 * here, if there was nothing to stat then it's not an error to	 * not be able to stat.  This is all fairly nasty.  If a program	 * needed sorted entries or stat information, they had better be	 * checking FTS_NS on the returned nodes.	 */	cderrno = 0;	if (nlinks || type == BREAD) {		if (fts_safe_changedir(sp, cur, dirfd(dirp))) {			if (nlinks && type == BREAD)				cur->fts_errno = errno;			cur->fts_flags |= FTS_DONTCHDIR;			descend = 0;			cderrno = errno;			(void)closedir(dirp);			dirp = NULL;		} else			descend = 1;	} else		descend = 0;	/*	 * Figure out the max file name length that can be stored in the	 * current path -- the inner loop allocates more path as necessary.	 * We really wouldn't have to do the maxlen calculations here, we	 * could do them in fts_read before returning the path, but it's a	 * lot easier here since the length is part of the dirent structure.	 *	 * If not changing directories set a pointer so that can just append	 * each new name into the path.	 */	maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;	len = NAPPEND(cur);	if (ISSET(FTS_NOCHDIR)) {		cp = sp->fts_path + len;		*cp++ = '/';	}	level = cur->fts_level + 1;	/* Read the directory, attaching each entry to the `link' pointer. */	adjaddr = NULL;	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))			continue;		if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)			goto mem1;		if (dp->d_namlen > maxlen) {			if (fts_palloc(sp, (size_t)dp->d_namlen)) {				/*				 * No more memory for path or structures.  Save				 * errno, free up the current structure and the				 * structures already allocated.				 */mem1:				saved_errno = errno;				if (p)					free(p);				fts_lfree(head);				(void)closedir(dirp);				errno = saved_errno;				cur->fts_info = FTS_ERR;				SET(FTS_STOP);				return (NULL);			}			adjaddr = sp->fts_path;			maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;		}		p->fts_pathlen = len + dp->d_namlen + 1;		p->fts_parent = sp->fts_cur;		p->fts_level = level;#ifdef FTS_WHITEOUT		if (dp->d_type == DT_WHT)			p->fts_flags |= FTS_ISW;#endif		if (cderrno) {			if (nlinks) {				p->fts_info = FTS_NS;				p->fts_errno = cderrno;			} else				p->fts_info = FTS_NSOK;			p->fts_accpath = cur->fts_accpath;		} else if (nlinks == 0#ifdef DT_DIR		    || (nostat &&		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)#endif		    ) {			p->fts_accpath =			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;			p->fts_info = FTS_NSOK;		} else {			/* Build a file name for fts_stat to stat. */			if (ISSET(FTS_NOCHDIR)) {				p->fts_accpath = p->fts_path;				memmove(cp, p->fts_name, p->fts_namelen + 1);			} else				p->fts_accpath = p->fts_name;			/* Stat it. */			p->fts_info = fts_stat(sp, p, 0);			/* Decrement link count if applicable. */			if (nlinks > 0 && (p->fts_info == FTS_D ||			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))				--nlinks;		}		/* We walk in directory order so "ls -f" doesn't get upset. */		p->fts_link = NULL;		if (head == NULL)			head = tail = p;		else {			tail->fts_link = p;			tail = p;		}		++nitems;	}	if (dirp)		(void)closedir(dirp);	/*	 * If had to realloc the path, adjust the addresses for the rest	 * of the tree.	 */	if (adjaddr)		fts_padjust(sp, adjaddr);	/*	 * If not changing directories, reset the path back to original	 * state.	 */	if (ISSET(FTS_NOCHDIR)) {		if (len == sp->fts_pathlen)			--cp;		*cp = '\0';	}	/*	 * If descended after called from fts_children or after called from	 * fts_read and nothing found, get back.  At the root level we use	 * the saved fd; if one of fts_open()'s arguments is a relative path	 * to an empty directory, we wind up here with no other way back.  If	 * can't get back, we're done.	 */	if (descend && (type == BCHILD || !nitems) &&	    (cur->fts_level == FTS_ROOTLEVEL ?	    FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {		cur->fts_info = FTS_ERR;		SET(FTS_STOP);		return (NULL);	}	/* If didn't find anything, return NULL. */	if (!nitems) {		if (type == BREAD)			cur->fts_info = FTS_DP;		return (NULL);	}	/* Sort the entries. */	if (sp->fts_compar && nitems > 1)		head = fts_sort(sp, head, nitems);	return (head);}