+/* link-count-optimization entry:
+ map a stat.st_dev number to a boolean: leaf_optimization_works */
+struct LCO_ent
+{
+ dev_t st_dev;
+ bool opt_ok;
+};
+
+/* Use a tiny initial size. If a traversal encounters more than
+ a few devices, the cost of growing/rehashing this table will be
+ rendered negligible by the number of inodes processed. */
+enum { LCO_HT_INITIAL_SIZE = 13 };
+
+static size_t
+LCO_hash (void const *x, size_t table_size)
+{
+ struct LCO_ent const *ax = x;
+ return (uintmax_t) ax->st_dev % table_size;
+}
+
+static bool
+LCO_compare (void const *x, void const *y)
+{
+ struct LCO_ent const *ax = x;
+ struct LCO_ent const *ay = y;
+ return ax->st_dev == ay->st_dev;
+}
+
+/* Ask the same question as leaf_optimization_applies, but query
+ the cache first (FTS.fts_leaf_optimization_works_ht), and if necessary,
+ update that cache. */
+static bool
+link_count_optimize_ok (FTSENT const *p)
+{
+ FTS *sp = p->fts_fts;
+ Hash_table *h = sp->fts_leaf_optimization_works_ht;
+ struct LCO_ent tmp;
+ struct LCO_ent *ent;
+ bool opt_ok;
+ struct LCO_ent *t2;
+
+ /* If we're not in CWDFD mode, don't bother with this optimization,
+ since the caller is not serious about performance. */
+ if (!ISSET(FTS_CWDFD))
+ return false;
+
+ /* map st_dev to the boolean, leaf_optimization_works */
+ if (h == NULL)
+ {
+ h = sp->fts_leaf_optimization_works_ht
+ = hash_initialize (LCO_HT_INITIAL_SIZE, NULL, LCO_hash,
+ LCO_compare, free);
+ if (h == NULL)
+ return false;
+ }
+ tmp.st_dev = p->fts_statp->st_dev;
+ ent = hash_lookup (h, &tmp);
+ if (ent)
+ return ent->opt_ok;
+
+ /* Look-up failed. Query directly and cache the result. */
+ t2 = malloc (sizeof *t2);
+ if (t2 == NULL)
+ return false;
+
+ /* Is it ok to perform the optimization in the dir, FTS_CWD_FD? */
+ opt_ok = leaf_optimization_applies (sp->fts_cwd_fd);
+ t2->opt_ok = opt_ok;
+ t2->st_dev = p->fts_statp->st_dev;
+
+ ent = hash_insert (h, t2);
+ if (ent == NULL)
+ {
+ /* insertion failed */
+ free (t2);
+ return false;
+ }
+ fts_assert (ent == t2);
+
+ return opt_ok;
+}
+
+/*
+ * Special case of "/" at the end of the file name so that slashes aren't
+ * appended which would cause file names to be written as "....//foo".
+ */
+#define NAPPEND(p) \
+ (p->fts_path[p->fts_pathlen - 1] == '/' \
+ ? p->fts_pathlen - 1 : p->fts_pathlen)
+
+FTSENT *
+fts_read (register FTS *sp)
+{
+ register FTSENT *p, *tmp;
+ register unsigned short int instr;
+ register char *t;
+
+ /* If finished or unrecoverable error, return NULL. */
+ if (sp->fts_cur == NULL || ISSET(FTS_STOP))
+ return (NULL);
+
+ /* Set current node pointer. */
+ p = sp->fts_cur;
+
+ /* Save and zero out user instructions. */
+ instr = p->fts_instr;
+ p->fts_instr = FTS_NOINSTR;
+
+ /* Any type of file may be re-visited; re-stat and re-turn. */
+ if (instr == FTS_AGAIN) {
+ p->fts_info = fts_stat(sp, p, false);
+ return (p);
+ }
+ Dprintf (("fts_read: p=%s\n",
+ p->fts_info == FTS_INIT ? "" : p->fts_path));
+
+ /*
+ * Following a symlink -- SLNONE test allows application to see
+ * SLNONE and recover. If indirecting through a symlink, have
+ * keep a pointer to current location. If unable to get that
+ * pointer, follow fails.
+ */
+ if (instr == FTS_FOLLOW &&
+ (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
+ p->fts_info = fts_stat(sp, p, true);
+ if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
+ if ((p->fts_symfd = diropen (sp, ".")) < 0) {
+ p->fts_errno = errno;
+ p->fts_info = FTS_ERR;
+ } else
+ p->fts_flags |= FTS_SYMFOLLOW;
+ }
+ goto check_for_dir;
+ }
+
+ /* Directory in pre-order. */
+ if (p->fts_info == FTS_D) {
+ /* If skipped or crossed mount point, do post-order visit. */
+ if (instr == FTS_SKIP ||
+ (ISSET(FTS_XDEV) && p->fts_statp->st_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;
+ LEAVE_DIR (sp, p, "1");
+ return (p);
+ }
+
+ /* Rebuild if only read the names and now traversing. */
+ if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
+ CLR(FTS_NAMEONLY);
+ fts_lfree(sp->fts_child);
+ sp->fts_child = NULL;
+ }
+
+ /*
+ * Cd to the subdirectory.
+ *
+ * If have already read and now fail to chdir, whack the list
+ * to make the names come out right, and set the parent errno
+ * so the application will eventually get an error condition.
+ * Set the FTS_DONTCHDIR flag so that when we logically change
+ * directories back to the parent we don't do a chdir.
+ *
+ * If haven't read do so. If the read fails, fts_build sets
+ * FTS_STOP or the fts_info field of the node.
+ */
+ if (sp->fts_child != NULL) {
+ if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
+ p->fts_errno = errno;
+ p->fts_flags |= FTS_DONTCHDIR;
+ for (p = sp->fts_child; p != NULL;
+ 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);
+ /* If fts_build's call to fts_safe_changedir failed
+ because it was not able to fchdir into a
+ subdirectory, tell the caller. */
+ if (p->fts_errno && p->fts_info != FTS_DNR)
+ p->fts_info = FTS_ERR;
+ LEAVE_DIR (sp, p, "2");
+ return (p);
+ }
+ p = sp->fts_child;
+ sp->fts_child = NULL;
+ goto name;
+ }
+
+ /* Move to the next node on this level. */
+next: tmp = p;
+ if ((p = p->fts_link) != NULL) {
+ sp->fts_cur = p;
+ free(tmp);
+
+ /*
+ * If reached the top, return to the original directory (or
+ * the root of the tree), and load the file names for the next
+ * root.
+ */
+ if (p->fts_level == FTS_ROOTLEVEL) {
+ if (RESTORE_INITIAL_CWD(sp)) {
+ SET(FTS_STOP);
+ return (NULL);
+ }
+ free_dir(sp);
+ fts_load(sp, p);
+ setup_dir(sp);
+ goto check_for_dir;
+ }
+
+ /*
+ * User may have called fts_set on the node. If skipped,
+ * ignore. If followed, get a file descriptor so we can
+ * get back if necessary.
+ */
+ if (p->fts_instr == FTS_SKIP)
+ goto next;
+ if (p->fts_instr == FTS_FOLLOW) {
+ p->fts_info = fts_stat(sp, p, true);
+ if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
+ if ((p->fts_symfd = diropen (sp, ".")) < 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);
+check_for_dir:
+ sp->fts_cur = p;
+ if (p->fts_info == FTS_NSOK)
+ {
+ if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
+ {
+ FTSENT *parent = p->fts_parent;
+ if (FTS_ROOTLEVEL < p->fts_level
+ /* ->fts_n_dirs_remaining is not valid
+ for command-line-specified names. */
+ && parent->fts_n_dirs_remaining == 0
+ && ISSET(FTS_NOSTAT)
+ && ISSET(FTS_PHYSICAL)
+ && link_count_optimize_ok (parent))
+ {
+ /* nothing more needed */
+ }
+ else
+ {
+ p->fts_info = fts_stat(sp, p, false);
+ if (S_ISDIR(p->fts_statp->st_mode)
+ && p->fts_level != FTS_ROOTLEVEL
+ && parent->fts_n_dirs_remaining)
+ parent->fts_n_dirs_remaining--;
+ }
+ }
+ else
+ fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
+ }
+
+ if (p->fts_info == FTS_D)
+ {
+ /* Now that P->fts_statp is guaranteed to be valid,
+ if this is a command-line directory, record its
+ device number, to be used for FTS_XDEV. */
+ if (p->fts_level == FTS_ROOTLEVEL)
+ sp->fts_dev = p->fts_statp->st_dev;
+ Dprintf ((" entering: %s\n", p->fts_path));
+ if (! enter_dir (sp, p))
+ {
+ __set_errno (ENOMEM);
+ return NULL;
+ }
+ }
+ return p;
+ }
+
+ /* Move up to the parent node. */
+ p = tmp->fts_parent;
+ sp->fts_cur = p;
+ free(tmp);
+
+ if (p->fts_level == FTS_ROOTPARENTLEVEL) {
+ /*
+ * Done; free everything up and set errno to 0 so the user
+ * can distinguish between error and EOF.
+ */
+ free(p);
+ __set_errno (0);
+ return (sp->fts_cur = NULL);
+ }
+
+ fts_assert (p->fts_info != FTS_NSOK);
+
+ /* NUL terminate the file name. */
+ sp->fts_path[p->fts_pathlen] = '\0';
+
+ /*
+ * Return to the parent directory. If at a root node, restore
+ * the initial working directory. If we came through a symlink,
+ * go back through the file descriptor. Otherwise, move up
+ * one level, via "..".
+ */
+ if (p->fts_level == FTS_ROOTLEVEL) {
+ if (RESTORE_INITIAL_CWD(sp)) {
+ p->fts_errno = errno;
+ SET(FTS_STOP);
+ }
+ } else if (p->fts_flags & FTS_SYMFOLLOW) {
+ if (FCHDIR(sp, p->fts_symfd)) {
+ int saved_errno = errno;
+ (void)close(p->fts_symfd);
+ __set_errno (saved_errno);
+ p->fts_errno = errno;
+ SET(FTS_STOP);
+ }
+ (void)close(p->fts_symfd);
+ } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
+ fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
+ p->fts_errno = errno;
+ SET(FTS_STOP);
+ }
+ p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
+ if (p->fts_errno == 0)
+ LEAVE_DIR (sp, p, "3");
+ return ISSET(FTS_STOP) ? NULL : p;
+}
+
+/*
+ * Fts_set takes the stream as an argument although it's not used in this
+ * implementation; it would be necessary if anyone wanted to add global
+ * semantics to fts using fts_set. An error return is allowed for similar
+ * reasons.
+ */
+/* ARGSUSED */
+int
+fts_set(FTS *sp _GL_UNUSED, FTSENT *p, int instr)
+{
+ if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
+ instr != FTS_NOINSTR && instr != FTS_SKIP) {
+ __set_errno (EINVAL);
+ return (1);
+ }
+ p->fts_instr = instr;
+ return (0);
+}
+
+FTSENT *
+fts_children (register FTS *sp, int instr)
+{
+ register FTSENT *p;
+ int fd;
+
+ if (instr != 0 && instr != FTS_NAMEONLY) {
+ __set_errno (EINVAL);
+ return (NULL);
+ }
+
+ /* Set current node pointer. */
+ p = sp->fts_cur;
+
+ /*
+ * Errno set to 0 so user can distinguish empty directory from
+ * an error.
+ */
+ __set_errno (0);
+
+ /* Fatal errors stop here. */
+ if (ISSET(FTS_STOP))
+ return (NULL);
+
+ /* Return logical hierarchy of user's arguments. */
+ if (p->fts_info == FTS_INIT)
+ return (p->fts_link);
+
+ /*
+ * If not a directory being visited in pre-order, stop here. Could
+ * allow FTS_DNR, assuming the user has fixed the problem, but the
+ * same effect is available with FTS_AGAIN.
+ */
+ if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
+ return (NULL);
+
+ /* Free up any previous child list. */
+ if (sp->fts_child != NULL)
+ fts_lfree(sp->fts_child);
+
+ if (instr == FTS_NAMEONLY) {
+ SET(FTS_NAMEONLY);
+ instr = BNAMES;
+ } else
+ instr = BCHILD;
+
+ /*
+ * If using chdir on a relative file name and called BEFORE fts_read
+ * does its chdir to the root of a traversal, we can lose -- we need to
+ * chdir into the subdirectory, and we don't know where the current
+ * directory is, so we can't get back so that the upcoming chdir by
+ * fts_read will work.
+ */
+ if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
+ ISSET(FTS_NOCHDIR))
+ return (sp->fts_child = fts_build(sp, instr));
+
+ if ((fd = diropen (sp, ".")) < 0)
+ return (sp->fts_child = NULL);
+ sp->fts_child = fts_build(sp, instr);
+ if (ISSET(FTS_CWDFD))
+ {
+ cwd_advance_fd (sp, fd, true);
+ }
+ else
+ {
+ if (fchdir(fd))
+ {
+ int saved_errno = errno;
+ close (fd);
+ __set_errno (saved_errno);
+ return NULL;
+ }
+ close (fd);
+ }
+ return (sp->fts_child);
+}
+