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;   cur = sp->fts_cur;   #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); }   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  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;   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;   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)) {  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 {  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;  p->fts_info = fts_stat(sp, p, 0);   if (nlinks > 0 && (p->fts_info == FTS_D || p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) --nlinks; }   p->fts_link = NULL; if (head == NULL) head = tail = p; else { tail->fts_link = p; tail = p; } ++nitems; } if (dirp) (void)closedir(dirp);   if (adjaddr) fts_padjust(sp, adjaddr);   if (ISSET(FTS_NOCHDIR)) { if (len == sp->fts_pathlen) --cp; *cp = '\0'; }   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 (!nitems) { if (type == BREAD) cur->fts_info = FTS_DP; return (NULL); }   if (sp->fts_compar && nitems > 1) head = fts_sort(sp, head, nitems); return (head); }  static u_short fts_stat(sp, p, follow) FTS *sp; register FTSENT *p; int follow; { register FTSENT *t; register dev_t dev; register ino_t ino; struct stat *sbp, sb; int saved_errno;   sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;  #ifdef FTS_WHITEOUT  if (p->fts_flags & FTS_ISW) { if (sbp != &sb) { memset(sbp, '\0', sizeof (*sbp)); sbp->st_mode = S_IFWHT; } return (FTS_W); } #endif   if (ISSET(FTS_LOGICAL) || follow) { if (stat(p->fts_accpath, sbp)) { saved_errno = errno; if (!lstat(p->fts_accpath, sbp)) { errno = 0; return (FTS_SLNONE); } p->fts_errno = saved_errno; goto err; } } else if (lstat(p->fts_accpath, sbp)) { p->fts_errno = errno; err:		memset(sbp, 0, sizeof(struct stat)); return (FTS_NS); }  if (S_ISDIR(sbp->st_mode)) {  dev = p->fts_dev = sbp->st_dev; ino = p->fts_ino = sbp->st_ino; p->fts_nlink = sbp->st_nlink;  if (ISDOT(p->fts_name)) return (FTS_DOT);   for (t = p->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) if (ino == t->fts_ino && dev == t->fts_dev) { p->fts_cycle = t; return (FTS_DC); } return (FTS_D); } if (S_ISLNK(sbp->st_mode)) return (FTS_SL); if (S_ISREG(sbp->st_mode)) return (FTS_F); return (FTS_DEFAULT); }  static FTSENT *
fts_sort(sp, head, nitems)	FTS *sp;	FTSENT *head;	register int nitems;{	register FTSENT **ap, *p;	/*	 * Construct an array of pointers to the structures and call qsort(3).	 * Reassemble the array in the order returned by qsort.  If unable to	 * sort for memory reasons, return the directory entries in their	 * current order.  Allocate enough space for the current needs plus	 * 40 so don't realloc one entry at a time.	 */	if (nitems > sp->fts_nitems) {		struct _ftsent **a;		sp->fts_nitems = nitems + 40;		if ((a = realloc(sp->fts_array,		    (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {			if (sp->fts_array)				free(sp->fts_array);			sp->fts_array = NULL;			sp->fts_nitems = 0;			return (head);		}		sp->fts_array = a;	}	for (ap = sp->fts_array, p = head; p; p = p->fts_link)		*ap++ = p;	qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);	for (head = *(ap = sp->fts_array); --nitems; ++ap)		ap[0]->fts_link = ap[1];	ap[0]->fts_link = NULL;	return (head);}