lib/fts.c

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /*-
  20  * Copyright (c) 1990, 1993, 1994
  21  *      The Regents of the University of California.  All rights reserved.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the above copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 4. Neither the name of the University nor the names of its contributors
  32  *    may be used to endorse or promote products derived from this software
  33  *    without specific prior written permission.
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  36  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  38  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  39  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  40  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  41  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  42  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  43  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  44  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  45  * SUCH DAMAGE.
  46  */
  47
  48 #ifdef HAVE_CONFIG_H
  49 # include <config.h>
  50 #endif
  51
  52 #if defined(LIBC_SCCS) && !defined(lint)
  53 static char sccsid[] = "@(#)fts.c       8.6 (Berkeley) 8/14/94";
  54 #endif /* LIBC_SCCS and not lint */
  55
  56 #include "fts_.h"
  57
  58 #if HAVE_SYS_PARAM_H || defined _LIBC
  59 # include <sys/param.h>
  60 #endif
  61 #ifdef _LIBC
  62 # include <include/sys/stat.h>
  63 #else
  64 # include <sys/stat.h>
  65 #endif
  66 #include <fcntl.h>
  67 #include <errno.h>
  68 #include "dirfd.h"
  69 #include <stdbool.h>
  70 #include <stdlib.h>
  71 #include <string.h>
  72 #include <unistd.h>
  73
  74 #if ! _LIBC
  75 # include "lstat.h"
  76 #endif
  77
  78 #include <dirent.h>
  79 #ifndef _D_EXACT_NAMLEN
  80 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
  81 #endif
  82
  83 #ifdef _LIBC
  84 # undef close
  85 # define close __close
  86 # undef closedir
  87 # define closedir __closedir
  88 # undef fchdir
  89 # define fchdir __fchdir
  90 # undef open
  91 # define open __open
  92 # undef opendir
  93 # define opendir __opendir
  94 # undef readdir
  95 # define readdir __readdir
  96 #else
  97 # undef internal_function
  98 # define internal_function /* empty */
  99 #endif
 100
 101 #ifndef __set_errno
 102 # define __set_errno(Val) errno = (Val)
 103 #endif
 104
 105 #ifndef __attribute__
 106 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
 107 #  define __attribute__(x) /* empty */
 108 # endif
 109 #endif
 110
 111 #ifndef ATTRIBUTE_UNUSED
 112 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
 113 #endif
 114
 115
 116 static FTSENT   *fts_alloc (FTS *, const char *, size_t) internal_function;
 117 static FTSENT   *fts_build (FTS *, int) internal_function;
 118 static void      fts_lfree (FTSENT *) internal_function;
 119 static void      fts_load (FTS *, FTSENT *) internal_function;
 120 static size_t    fts_maxarglen (char * const *) internal_function;
 121 static void      fts_padjust (FTS *, FTSENT *) internal_function;
 122 static bool      fts_palloc (FTS *, size_t) internal_function;
 123 static FTSENT   *fts_sort (FTS *, FTSENT *, size_t) internal_function;
 124 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
 125 static int      fts_safe_changedir (FTS *, FTSENT *, int, const char *)
 126      internal_function;
 127
 128 #if _LGPL_PACKAGE
 129 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
 130 static void leave_dir (FTS *fts, FTSENT *ent) {}
 131 static bool setup_dir (FTS *fts) { return true; }
 132 static void free_dir (FTS *fts) {}
 133 #else
 134 # include "fcntl--.h"
 135 # include "fts-cycle.c"
 136 #endif
 137
 138 #ifndef MAX
 139 # define MAX(a,b) ((a) > (b) ? (a) : (b))
 140 #endif
 141
 142 #ifndef SIZE_MAX
 143 # define SIZE_MAX ((size_t) -1)
 144 #endif
 145
 146 #ifndef O_DIRECTORY
 147 # define O_DIRECTORY 0
 148 #endif
 149
 150 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
 151
 152 #define CLR(opt)        (sp->fts_options &= ~(opt))
 153 #define ISSET(opt)      (sp->fts_options & (opt))
 154 #define SET(opt)        (sp->fts_options |= (opt))
 155
 156 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
 157
 158 /* fts_build flags */
 159 #define BCHILD          1               /* fts_children */
 160 #define BNAMES          2               /* fts_children, names only */
 161 #define BREAD           3               /* fts_read */
 162
 163 #if FTS_DEBUG
 164 # include <inttypes.h>
 165 # include <stdint.h>
 166 # include <stdio.h>
 167 bool fts_debug = false;
 168 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
 169 #else
 170 # define Dprintf(x)
 171 #endif
 172
 173 #define LEAVE_DIR(Fts, Ent, Tag)                                \
 174   do                                                            \
 175     {                                                           \
 176       Dprintf (("  %s-leaving: %s\n", Tag, (Ent)->fts_path));   \
 177       leave_dir (Fts, Ent);                                     \
 178     }                                                           \
 179   while (false)
 180
 181 /* Open the directory DIR if possible, and return a file
 182    descriptor.  Return -1 and set errno on failure.  It doesn't matter
 183    whether the file descriptor has read or write access.  */
 184
 185 static int
 186 internal_function
 187 diropen (char const *dir)
 188 {
 189   return open (dir, O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
 190 }
 191
 192 FTS *
 193 fts_open (char * const *argv,
 194           register int options,
 195           int (*compar) (FTSENT const **, FTSENT const **))
 196 {
 197         register FTS *sp;
 198         register FTSENT *p, *root;
 199         register size_t nitems;
 200         FTSENT *parent, *tmp = NULL;    /* pacify gcc */
 201         size_t len;
 202
 203         /* Options check. */
 204         if (options & ~FTS_OPTIONMASK) {
 205                 __set_errno (EINVAL);
 206                 return (NULL);
 207         }
 208
 209         /* Allocate/initialize the stream */
 210         if ((sp = malloc(sizeof(FTS))) == NULL)
 211                 return (NULL);
 212         memset(sp, 0, sizeof(FTS));
 213         sp->fts_compar = compar;
 214         sp->fts_options = options;
 215
 216         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 217         if (ISSET(FTS_LOGICAL))
 218                 SET(FTS_NOCHDIR);
 219
 220         /*
 221          * Start out with 1K of file name space, and enough, in any case,
 222          * to hold the user's file names.
 223          */
 224 #ifndef MAXPATHLEN
 225 # define MAXPATHLEN 1024
 226 #endif
 227         {
 228           size_t maxarglen = fts_maxarglen(argv);
 229           if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
 230                   goto mem1;
 231         }
 232
 233         /* Allocate/initialize root's parent. */
 234         if ((parent = fts_alloc(sp, "", 0)) == NULL)
 235                 goto mem2;
 236         parent->fts_level = FTS_ROOTPARENTLEVEL;
 237
 238         /* Allocate/initialize root(s). */
 239         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
 240                 /* Don't allow zero-length file names. */
 241                 if ((len = strlen(*argv)) == 0) {
 242                         __set_errno (ENOENT);
 243                         goto mem3;
 244                 }
 245
 246                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 247                         goto mem3;
 248                 p->fts_level = FTS_ROOTLEVEL;
 249                 p->fts_parent = parent;
 250                 p->fts_accpath = p->fts_name;
 251                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
 252
 253                 /* Command-line "." and ".." are real directories. */
 254                 if (p->fts_info == FTS_DOT)
 255                         p->fts_info = FTS_D;
 256
 257                 /*
 258                  * If comparison routine supplied, traverse in sorted
 259                  * order; otherwise traverse in the order specified.
 260                  */
 261                 if (compar) {
 262                         p->fts_link = root;
 263                         root = p;
 264                 } else {
 265                         p->fts_link = NULL;
 266                         if (root == NULL)
 267                                 tmp = root = p;
 268                         else {
 269                                 tmp->fts_link = p;
 270                                 tmp = p;
 271                         }
 272                 }
 273         }
 274         if (compar && nitems > 1)
 275                 root = fts_sort(sp, root, nitems);
 276
 277         /*
 278          * Allocate a dummy pointer and make fts_read think that we've just
 279          * finished the node before the root(s); set p->fts_info to FTS_INIT
 280          * so that everything about the "current" node is ignored.
 281          */
 282         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 283                 goto mem3;
 284         sp->fts_cur->fts_link = root;
 285         sp->fts_cur->fts_info = FTS_INIT;
 286         if (! setup_dir (sp))
 287           goto mem3;
 288
 289         /*
 290          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 291          * that we can get back here; this could be avoided for some file names,
 292          * but almost certainly not worth the effort.  Slashes, symbolic links,
 293          * and ".." are all fairly nasty problems.  Note, if we can't get the
 294          * descriptor we run anyway, just more slowly.
 295          */
 296         if (!ISSET(FTS_NOCHDIR)
 297             && (sp->fts_rfd = diropen (".")) < 0)
 298                 SET(FTS_NOCHDIR);
 299
 300         return (sp);
 301
 302 mem3:   fts_lfree(root);
 303         free(parent);
 304 mem2:   free(sp->fts_path);
 305 mem1:   free(sp);
 306         return (NULL);
 307 }
 308
 309 static void
 310 internal_function
 311 fts_load (FTS *sp, register FTSENT *p)
 312 {
 313         register size_t len;
 314         register char *cp;
 315
 316         /*
 317          * Load the stream structure for the next traversal.  Since we don't
 318          * actually enter the directory until after the preorder visit, set
 319          * the fts_accpath field specially so the chdir gets done to the right
 320          * place and the user can access the first node.  From fts_open it's
 321          * known that the file name will fit.
 322          */
 323         len = p->fts_pathlen = p->fts_namelen;
 324         memmove(sp->fts_path, p->fts_name, len + 1);
 325         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 326                 len = strlen(++cp);
 327                 memmove(p->fts_name, cp, len + 1);
 328                 p->fts_namelen = len;
 329         }
 330         p->fts_accpath = p->fts_path = sp->fts_path;
 331         sp->fts_dev = p->fts_statp->st_dev;
 332 }
 333
 334 int
 335 fts_close (FTS *sp)
 336 {
 337         register FTSENT *freep, *p;
 338         int saved_errno = 0;
 339
 340         /*
 341          * This still works if we haven't read anything -- the dummy structure
 342          * points to the root list, so we step through to the end of the root
 343          * list which has a valid parent pointer.
 344          */
 345         if (sp->fts_cur) {
 346                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 347                         freep = p;
 348                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 349                         free(freep);
 350                 }
 351                 free(p);
 352         }
 353
 354         /* Free up child linked list, sort array, file name buffer. */
 355         if (sp->fts_child)
 356                 fts_lfree(sp->fts_child);
 357         if (sp->fts_array)
 358                 free(sp->fts_array);
 359         free(sp->fts_path);
 360
 361         /* Return to original directory, save errno if necessary. */
 362         if (!ISSET(FTS_NOCHDIR)) {
 363                 if (fchdir(sp->fts_rfd))
 364                         saved_errno = errno;
 365                 (void)close(sp->fts_rfd);
 366         }
 367
 368         free_dir (sp);
 369
 370         /* Free up the stream pointer. */
 371         free(sp);
 372
 373         /* Set errno and return. */
 374         if (saved_errno) {
 375                 __set_errno (saved_errno);
 376                 return (-1);
 377         }
 378
 379         return (0);
 380 }
 381
 382 /*
 383  * Special case of "/" at the end of the file name so that slashes aren't
 384  * appended which would cause file names to be written as "....//foo".
 385  */
 386 #define NAPPEND(p)                                                      \
 387         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 388             ? p->fts_pathlen - 1 : p->fts_pathlen)
 389
 390 FTSENT *
 391 fts_read (register FTS *sp)
 392 {
 393         register FTSENT *p, *tmp;
 394         register unsigned short int instr;
 395         register char *t;
 396         int saved_errno;
 397
 398         /* If finished or unrecoverable error, return NULL. */
 399         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 400                 return (NULL);
 401
 402         /* Set current node pointer. */
 403         p = sp->fts_cur;
 404
 405         /* Save and zero out user instructions. */
 406         instr = p->fts_instr;
 407         p->fts_instr = FTS_NOINSTR;
 408
 409         /* Any type of file may be re-visited; re-stat and re-turn. */
 410         if (instr == FTS_AGAIN) {
 411                 p->fts_info = fts_stat(sp, p, false);
 412                 return (p);
 413         }
 414         Dprintf (("fts_read: p=%s\n",
 415                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 416
 417         /*
 418          * Following a symlink -- SLNONE test allows application to see
 419          * SLNONE and recover.  If indirecting through a symlink, have
 420          * keep a pointer to current location.  If unable to get that
 421          * pointer, follow fails.
 422          */
 423         if (instr == FTS_FOLLOW &&
 424             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 425                 p->fts_info = fts_stat(sp, p, true);
 426                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 427                         if ((p->fts_symfd = diropen (".")) < 0) {
 428                                 p->fts_errno = errno;
 429                                 p->fts_info = FTS_ERR;
 430                         } else
 431                                 p->fts_flags |= FTS_SYMFOLLOW;
 432                 }
 433                 goto check_for_dir;
 434         }
 435
 436         /* Directory in pre-order. */
 437         if (p->fts_info == FTS_D) {
 438                 /* If skipped or crossed mount point, do post-order visit. */
 439                 if (instr == FTS_SKIP ||
 440                     (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
 441                         if (p->fts_flags & FTS_SYMFOLLOW)
 442                                 (void)close(p->fts_symfd);
 443                         if (sp->fts_child) {
 444                                 fts_lfree(sp->fts_child);
 445                                 sp->fts_child = NULL;
 446                         }
 447                         p->fts_info = FTS_DP;
 448                         LEAVE_DIR (sp, p, "1");
 449                         return (p);
 450                 }
 451
 452                 /* Rebuild if only read the names and now traversing. */
 453                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 454                         CLR(FTS_NAMEONLY);
 455                         fts_lfree(sp->fts_child);
 456                         sp->fts_child = NULL;
 457                 }
 458
 459                 /*
 460                  * Cd to the subdirectory.
 461                  *
 462                  * If have already read and now fail to chdir, whack the list
 463                  * to make the names come out right, and set the parent errno
 464                  * so the application will eventually get an error condition.
 465                  * Set the FTS_DONTCHDIR flag so that when we logically change
 466                  * directories back to the parent we don't do a chdir.
 467                  *
 468                  * If haven't read do so.  If the read fails, fts_build sets
 469                  * FTS_STOP or the fts_info field of the node.
 470                  */
 471                 if (sp->fts_child != NULL) {
 472                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 473                                 p->fts_errno = errno;
 474                                 p->fts_flags |= FTS_DONTCHDIR;
 475                                 for (p = sp->fts_child; p != NULL;
 476                                      p = p->fts_link)
 477                                         p->fts_accpath =
 478                                             p->fts_parent->fts_accpath;
 479                         }
 480                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 481                         if (ISSET(FTS_STOP))
 482                                 return (NULL);
 483                         /* If fts_build's call to fts_safe_changedir failed
 484                            because it was not able to fchdir into a
 485                            subdirectory, tell the caller.  */
 486                         if (p->fts_errno)
 487                                 p->fts_info = FTS_ERR;
 488                         /* FIXME: see if this should be in an else block */
 489                         LEAVE_DIR (sp, p, "2");
 490                         return (p);
 491                 }
 492                 p = sp->fts_child;
 493                 sp->fts_child = NULL;
 494                 goto name;
 495         }
 496
 497         /* Move to the next node on this level. */
 498 next:   tmp = p;
 499         if ((p = p->fts_link) != NULL) {
 500                 free(tmp);
 501
 502                 /*
 503                  * If reached the top, return to the original directory (or
 504                  * the root of the tree), and load the file names for the next
 505                  * root.
 506                  */
 507                 if (p->fts_level == FTS_ROOTLEVEL) {
 508                         if (FCHDIR(sp, sp->fts_rfd)) {
 509                                 SET(FTS_STOP);
 510                                 sp->fts_cur = p;
 511                                 return (NULL);
 512                         }
 513                         fts_load(sp, p);
 514                         goto check_for_dir;
 515                 }
 516
 517                 /*
 518                  * User may have called fts_set on the node.  If skipped,
 519                  * ignore.  If followed, get a file descriptor so we can
 520                  * get back if necessary.
 521                  */
 522                 if (p->fts_instr == FTS_SKIP)
 523                         goto next;
 524                 if (p->fts_instr == FTS_FOLLOW) {
 525                         p->fts_info = fts_stat(sp, p, true);
 526                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 527                                 if ((p->fts_symfd = diropen (".")) < 0) {
 528                                         p->fts_errno = errno;
 529                                         p->fts_info = FTS_ERR;
 530                                 } else
 531                                         p->fts_flags |= FTS_SYMFOLLOW;
 532                         }
 533                         p->fts_instr = FTS_NOINSTR;
 534                 }
 535
 536 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 537                 *t++ = '/';
 538                 memmove(t, p->fts_name, p->fts_namelen + 1);
 539 check_for_dir:
 540                 sp->fts_cur = p;
 541                 if (p->fts_info == FTS_D)
 542                   {
 543                     Dprintf (("  %s-entering: %s\n", sp, p->fts_path));
 544                     if (! enter_dir (sp, p))
 545                       {
 546                         __set_errno (ENOMEM);
 547                         return NULL;
 548                       }
 549                   }
 550                 return p;
 551         }
 552
 553         /* Move up to the parent node. */
 554         p = tmp->fts_parent;
 555         free(tmp);
 556
 557         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 558                 /*
 559                  * Done; free everything up and set errno to 0 so the user
 560                  * can distinguish between error and EOF.
 561                  */
 562                 free(p);
 563                 __set_errno (0);
 564                 return (sp->fts_cur = NULL);
 565         }
 566
 567         /* NUL terminate the file name.  */
 568         sp->fts_path[p->fts_pathlen] = '\0';
 569
 570         /*
 571          * Return to the parent directory.  If at a root node or came through
 572          * a symlink, go back through the file descriptor.  Otherwise, cd up
 573          * one directory.
 574          */
 575         if (p->fts_level == FTS_ROOTLEVEL) {
 576                 if (FCHDIR(sp, sp->fts_rfd)) {
 577                         p->fts_errno = errno;
 578                         SET(FTS_STOP);
 579                 }
 580         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 581                 if (FCHDIR(sp, p->fts_symfd)) {
 582                         saved_errno = errno;
 583                         (void)close(p->fts_symfd);
 584                         __set_errno (saved_errno);
 585                         p->fts_errno = errno;
 586                         SET(FTS_STOP);
 587                 }
 588                 (void)close(p->fts_symfd);
 589         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 590                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 591                 p->fts_errno = errno;
 592                 SET(FTS_STOP);
 593         }
 594         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 595         if (p->fts_errno == 0)
 596                 LEAVE_DIR (sp, p, "3");
 597         sp->fts_cur = p;
 598         return ISSET(FTS_STOP) ? NULL : p;
 599 }
 600
 601 /*
 602  * Fts_set takes the stream as an argument although it's not used in this
 603  * implementation; it would be necessary if anyone wanted to add global
 604  * semantics to fts using fts_set.  An error return is allowed for similar
 605  * reasons.
 606  */
 607 /* ARGSUSED */
 608 int
 609 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 610 {
 611         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 612             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 613                 __set_errno (EINVAL);
 614                 return (1);
 615         }
 616         p->fts_instr = instr;
 617         return (0);
 618 }
 619
 620 FTSENT *
 621 fts_children (register FTS *sp, int instr)
 622 {
 623         register FTSENT *p;
 624         int fd;
 625
 626         if (instr != 0 && instr != FTS_NAMEONLY) {
 627                 __set_errno (EINVAL);
 628                 return (NULL);
 629         }
 630
 631         /* Set current node pointer. */
 632         p = sp->fts_cur;
 633
 634         /*
 635          * Errno set to 0 so user can distinguish empty directory from
 636          * an error.
 637          */
 638         __set_errno (0);
 639
 640         /* Fatal errors stop here. */
 641         if (ISSET(FTS_STOP))
 642                 return (NULL);
 643
 644         /* Return logical hierarchy of user's arguments. */
 645         if (p->fts_info == FTS_INIT)
 646                 return (p->fts_link);
 647
 648         /*
 649          * If not a directory being visited in pre-order, stop here.  Could
 650          * allow FTS_DNR, assuming the user has fixed the problem, but the
 651          * same effect is available with FTS_AGAIN.
 652          */
 653         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 654                 return (NULL);
 655
 656         /* Free up any previous child list. */
 657         if (sp->fts_child != NULL)
 658                 fts_lfree(sp->fts_child);
 659
 660         if (instr == FTS_NAMEONLY) {
 661                 SET(FTS_NAMEONLY);
 662                 instr = BNAMES;
 663         } else
 664                 instr = BCHILD;
 665
 666         /*
 667          * If using chdir on a relative file name and called BEFORE fts_read
 668          * does its chdir to the root of a traversal, we can lose -- we need to
 669          * chdir into the subdirectory, and we don't know where the current
 670          * directory is, so we can't get back so that the upcoming chdir by
 671          * fts_read will work.
 672          */
 673         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 674             ISSET(FTS_NOCHDIR))
 675                 return (sp->fts_child = fts_build(sp, instr));
 676
 677         if ((fd = diropen (".")) < 0)
 678                 return (sp->fts_child = NULL);
 679         sp->fts_child = fts_build(sp, instr);
 680         if (fchdir(fd)) {
 681                 int saved_errno = errno;
 682                 (void)close(fd);
 683                 __set_errno (saved_errno);
 684                 return (NULL);
 685         }
 686         (void)close(fd);
 687         return (sp->fts_child);
 688 }
 689
 690 /*
 691  * This is the tricky part -- do not casually change *anything* in here.  The
 692  * idea is to build the linked list of entries that are used by fts_children
 693  * and fts_read.  There are lots of special cases.
 694  *
 695  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
 696  * set and it's a physical walk (so that symbolic links can't be directories),
 697  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
 698  * of the file is in the directory entry.  Otherwise, we assume that the number
 699  * of subdirectories in a node is equal to the number of links to the parent.
 700  * The former skips all stat calls.  The latter skips stat calls in any leaf
 701  * directories and for any files after the subdirectories in the directory have
 702  * been found, cutting the stat calls by about 2/3.
 703  */
 704 static FTSENT *
 705 internal_function
 706 fts_build (register FTS *sp, int type)
 707 {
 708         register struct dirent *dp;
 709         register FTSENT *p, *head;
 710         register size_t nitems;
 711         FTSENT *cur, *tail;
 712         DIR *dirp;
 713         void *oldaddr;
 714         int cderrno;
 715         int saved_errno;
 716         bool descend;
 717         bool doadjust;
 718         ptrdiff_t level;
 719         nlink_t nlinks;
 720         bool nostat;
 721         size_t len, maxlen, new_len;
 722         char *cp;
 723
 724         /* Set current node pointer. */
 725         cur = sp->fts_cur;
 726
 727         /*
 728          * Open the directory for reading.  If this fails, we're done.
 729          * If being called from fts_read, set the fts_info field.
 730          */
 731 #if defined FTS_WHITEOUT && 0
 732         if (ISSET(FTS_WHITEOUT))
 733                 oflag = DTF_NODUP|DTF_REWIND;
 734         else
 735                 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
 736 #else
 737 # define __opendir2(file, flag) opendir(file)
 738 #endif
 739        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
 740                 if (type == BREAD) {
 741                         cur->fts_info = FTS_DNR;
 742                         cur->fts_errno = errno;
 743                 }
 744                 return (NULL);
 745         }
 746
 747         /*
 748          * Nlinks is the number of possible entries of type directory in the
 749          * directory if we're cheating on stat calls, 0 if we're not doing
 750          * any stat calls at all, (nlink_t) -1 if we're statting everything.
 751          */
 752         if (type == BNAMES) {
 753                 nlinks = 0;
 754                 /* Be quiet about nostat, GCC. */
 755                 nostat = false;
 756         } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
 757                 nlinks = (cur->fts_statp->st_nlink
 758                           - (ISSET(FTS_SEEDOT) ? 0 : 2));
 759                 nostat = true;
 760         } else {
 761                 nlinks = -1;
 762                 nostat = false;
 763         }
 764
 765         /*
 766          * If we're going to need to stat anything or we want to descend
 767          * and stay in the directory, chdir.  If this fails we keep going,
 768          * but set a flag so we don't chdir after the post-order visit.
 769          * We won't be able to stat anything, but we can still return the
 770          * names themselves.  Note, that since fts_read won't be able to
 771          * chdir into the directory, it will have to return different file
 772          * names than before, i.e. "a/b" instead of "b".  Since the node
 773          * has already been visited in pre-order, have to wait until the
 774          * post-order visit to return the error.  There is a special case
 775          * here, if there was nothing to stat then it's not an error to
 776          * not be able to stat.  This is all fairly nasty.  If a program
 777          * needed sorted entries or stat information, they had better be
 778          * checking FTS_NS on the returned nodes.
 779          */
 780         cderrno = 0;
 781         if (nlinks || type == BREAD) {
 782                 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
 783                         if (nlinks && type == BREAD)
 784                                 cur->fts_errno = errno;
 785                         cur->fts_flags |= FTS_DONTCHDIR;
 786                         descend = false;
 787                         cderrno = errno;
 788                         closedir(dirp);
 789                         dirp = NULL;
 790                 } else
 791                         descend = true;
 792         } else
 793                 descend = false;
 794
 795         /*
 796          * Figure out the max file name length that can be stored in the
 797          * current buffer -- the inner loop allocates more space as necessary.
 798          * We really wouldn't have to do the maxlen calculations here, we
 799          * could do them in fts_read before returning the name, but it's a
 800          * lot easier here since the length is part of the dirent structure.
 801          *
 802          * If not changing directories set a pointer so that can just append
 803          * each new component into the file name.
 804          */
 805         len = NAPPEND(cur);
 806         if (ISSET(FTS_NOCHDIR)) {
 807                 cp = sp->fts_path + len;
 808                 *cp++ = '/';
 809         } else {
 810                 /* GCC, you're too verbose. */
 811                 cp = NULL;
 812         }
 813         len++;
 814         maxlen = sp->fts_pathlen - len;
 815
 816         level = cur->fts_level + 1;
 817
 818         /* Read the directory, attaching each entry to the `link' pointer. */
 819         doadjust = false;
 820         for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
 821                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
 822                         continue;
 823
 824                 if ((p = fts_alloc (sp, dp->d_name,
 825                                     _D_EXACT_NAMLEN (dp))) == NULL)
 826                         goto mem1;
 827                 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
 828                         /* include space for NUL */
 829                         oldaddr = sp->fts_path;
 830                         if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
 831                                 /*
 832                                  * No more memory.  Save
 833                                  * errno, free up the current structure and the
 834                                  * structures already allocated.
 835                                  */
 836 mem1:                           saved_errno = errno;
 837                                 if (p)
 838                                         free(p);
 839                                 fts_lfree(head);
 840                                 closedir(dirp);
 841                                 cur->fts_info = FTS_ERR;
 842                                 SET(FTS_STOP);
 843                                 __set_errno (saved_errno);
 844                                 return (NULL);
 845                         }
 846                         /* Did realloc() change the pointer? */
 847                         if (oldaddr != sp->fts_path) {
 848                                 doadjust = true;
 849                                 if (ISSET(FTS_NOCHDIR))
 850                                         cp = sp->fts_path + len;
 851                         }
 852                         maxlen = sp->fts_pathlen - len;
 853                 }
 854
 855                 new_len = len + _D_EXACT_NAMLEN (dp);
 856                 if (new_len < len) {
 857                         /*
 858                          * In the unlikely even that we would end up
 859                          * with a file name longer than SIZE_MAX, free up
 860                          * the current structure and the structures already
 861                          * allocated, then error out with ENAMETOOLONG.
 862                          */
 863                         free(p);
 864                         fts_lfree(head);
 865                         closedir(dirp);
 866                         cur->fts_info = FTS_ERR;
 867                         SET(FTS_STOP);
 868                         __set_errno (ENAMETOOLONG);
 869                         return (NULL);
 870                 }
 871                 p->fts_level = level;
 872                 p->fts_parent = sp->fts_cur;
 873                 p->fts_pathlen = new_len;
 874
 875 #if defined FTS_WHITEOUT && 0
 876                 if (dp->d_type == DT_WHT)
 877                         p->fts_flags |= FTS_ISW;
 878 #endif
 879
 880                 if (cderrno) {
 881                         if (nlinks) {
 882                                 p->fts_info = FTS_NS;
 883                                 p->fts_errno = cderrno;
 884                         } else
 885                                 p->fts_info = FTS_NSOK;
 886                         p->fts_accpath = cur->fts_accpath;
 887                 } else if (nlinks == 0
 888 #if HAVE_STRUCT_DIRENT_D_TYPE
 889                            || (nostat &&
 890                                dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
 891 #endif
 892                     ) {
 893                         p->fts_accpath =
 894                             ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
 895                         p->fts_info = FTS_NSOK;
 896                 } else {
 897                         /* Build a file name for fts_stat to stat. */
 898                         if (ISSET(FTS_NOCHDIR)) {
 899                                 p->fts_accpath = p->fts_path;
 900                                 memmove(cp, p->fts_name, p->fts_namelen + 1);
 901                         } else
 902                                 p->fts_accpath = p->fts_name;
 903                         /* Stat it. */
 904                         p->fts_info = fts_stat(sp, p, false);
 905
 906                         /* Decrement link count if applicable. */
 907                         if (nlinks > 0 && (p->fts_info == FTS_D ||
 908                             p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
 909                                 nlinks -= nostat;
 910                 }
 911
 912                 /* We walk in directory order so "ls -f" doesn't get upset. */
 913                 p->fts_link = NULL;
 914                 if (head == NULL)
 915                         head = tail = p;
 916                 else {
 917                         tail->fts_link = p;
 918                         tail = p;
 919                 }
 920                 ++nitems;
 921         }
 922         if (dirp)
 923                 closedir(dirp);
 924
 925         /*
 926          * If realloc() changed the address of the file name, adjust the
 927          * addresses for the rest of the tree and the dir list.
 928          */
 929         if (doadjust)
 930                 fts_padjust(sp, head);
 931
 932         /*
 933          * If not changing directories, reset the file name back to original
 934          * state.
 935          */
 936         if (ISSET(FTS_NOCHDIR)) {
 937                 if (len == sp->fts_pathlen || nitems == 0)
 938                         --cp;
 939                 *cp = '\0';
 940         }
 941
 942         /*
 943          * If descended after called from fts_children or after called from
 944          * fts_read and nothing found, get back.  At the root level we use
 945          * the saved fd; if one of fts_open()'s arguments is a relative name
 946          * to an empty directory, we wind up here with no other way back.  If
 947          * can't get back, we're done.
 948          */
 949         if (descend && (type == BCHILD || !nitems) &&
 950             (cur->fts_level == FTS_ROOTLEVEL ?
 951              FCHDIR(sp, sp->fts_rfd) :
 952              fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
 953                 cur->fts_info = FTS_ERR;
 954                 SET(FTS_STOP);
 955                 return (NULL);
 956         }
 957
 958         /* If didn't find anything, return NULL. */
 959         if (!nitems) {
 960                 if (type == BREAD)
 961                         cur->fts_info = FTS_DP;
 962                 return (NULL);
 963         }
 964
 965         /* Sort the entries. */
 966         if (sp->fts_compar && nitems > 1)
 967                 head = fts_sort(sp, head, nitems);
 968         return (head);
 969 }
 970
 971 #if FTS_DEBUG
 972
 973 /* Walk ->fts_parent links starting at E_CURR, until the root of the
 974    current hierarchy.  There should be a directory with dev/inode
 975    matching those of AD.  If not, print a lot of diagnostics.  */
 976 static void
 977 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
 978 {
 979   FTSENT const *ent;
 980   for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
 981     {
 982       if (ad->ino == ent->fts_statp->st_ino
 983           && ad->dev == ent->fts_statp->st_dev)
 984         return;
 985     }
 986   printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
 987   printf ("active dirs:\n");
 988   for (ent = e_curr;
 989        ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
 990     printf ("  %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
 991             ad->fts_ent->fts_accpath,
 992             (uintmax_t) ad->dev,
 993             (uintmax_t) ad->ino,
 994             ent->fts_accpath,
 995             (uintmax_t) ent->fts_statp->st_dev,
 996             (uintmax_t) ent->fts_statp->st_ino);
 997 }
 998
 999 void
1000 fts_cross_check (FTS const *sp)
1001 {
1002   FTSENT const *ent = sp->fts_cur;
1003   FTSENT const *t;
1004   if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1005     return;
1006
1007   Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1008   /* Make sure every parent dir is in the tree.  */
1009   for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1010     {
1011       struct Active_dir ad;
1012       ad.ino = t->fts_statp->st_ino;
1013       ad.dev = t->fts_statp->st_dev;
1014       if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1015         printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1016     }
1017
1018   /* Make sure every dir in the tree is an active dir.
1019      But ENT is not necessarily a directory.  If so, just skip this part. */
1020   if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1021       && (ent->fts_info == FTS_DP
1022           || ent->fts_info == FTS_D))
1023     {
1024       struct Active_dir *ad;
1025       for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1026            ad = hash_get_next (sp->fts_cycle.ht, ad))
1027         {
1028           find_matching_ancestor (ent, ad);
1029         }
1030     }
1031 }
1032 #endif
1033
1034 static unsigned short int
1035 internal_function
1036 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1037 {
1038         struct stat *sbp = p->fts_statp;
1039         int saved_errno;
1040
1041 #if defined FTS_WHITEOUT && 0
1042         /* check for whiteout */
1043         if (p->fts_flags & FTS_ISW) {
1044                 memset(sbp, '\0', sizeof (*sbp));
1045                 sbp->st_mode = S_IFWHT;
1046                 return (FTS_W);
1047        }
1048 #endif
1049
1050         /*
1051          * If doing a logical walk, or application requested FTS_FOLLOW, do
1052          * a stat(2).  If that fails, check for a non-existent symlink.  If
1053          * fail, set the errno from the stat call.
1054          */
1055         if (ISSET(FTS_LOGICAL) || follow) {
1056                 if (stat(p->fts_accpath, sbp)) {
1057                         saved_errno = errno;
1058                         if (errno == ENOENT
1059                             && lstat(p->fts_accpath, sbp) == 0) {
1060                                 __set_errno (0);
1061                                 return (FTS_SLNONE);
1062                         }
1063                         p->fts_errno = saved_errno;
1064                         goto err;
1065                 }
1066         } else if (lstat(p->fts_accpath, sbp)) {
1067                 p->fts_errno = errno;
1068 err:            memset(sbp, 0, sizeof(struct stat));
1069                 return (FTS_NS);
1070         }
1071
1072         if (S_ISDIR(sbp->st_mode)) {
1073                 if (ISDOT(p->fts_name))
1074                         return (FTS_DOT);
1075
1076 #if _LGPL_PACKAGE
1077                 {
1078                   /*
1079                    * Cycle detection is done by brute force when the directory
1080                    * is first encountered.  If the tree gets deep enough or the
1081                    * number of symbolic links to directories is high enough,
1082                    * something faster might be worthwhile.
1083                    */
1084                   FTSENT *t;
1085
1086                   for (t = p->fts_parent;
1087                        t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1088                     if (sbp->st_ino == t->fts_statp->st_ino
1089                         && sbp->st_dev == t->fts_statp->st_dev)
1090                       {
1091                         p->fts_cycle = t;
1092                         return (FTS_DC);
1093                       }
1094                 }
1095 #endif
1096
1097                 return (FTS_D);
1098         }
1099         if (S_ISLNK(sbp->st_mode))
1100                 return (FTS_SL);
1101         if (S_ISREG(sbp->st_mode))
1102                 return (FTS_F);
1103         return (FTS_DEFAULT);
1104 }
1105
1106 static int
1107 fts_compar (void const *a, void const *b)
1108 {
1109   /* Convert A and B to the correct types, to pacify the compiler, and
1110      for portability to bizarre hosts where "void const *" and "FTSENT
1111      const **" differ in runtime representation.  The comparison
1112      function cannot modify *a and *b, but there is no compile-time
1113      check for this.  */
1114   FTSENT const **pa = (FTSENT const **) a;
1115   FTSENT const **pb = (FTSENT const **) b;
1116   return pa[0]->fts_fts->fts_compar (pa, pb);
1117 }
1118
1119 static FTSENT *
1120 internal_function
1121 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1122 {
1123         register FTSENT **ap, *p;
1124
1125         /* On most modern hosts, void * and FTSENT ** have the same
1126            run-time representation, and one can convert sp->fts_compar to
1127            the type qsort expects without problem.  Use the heuristic that
1128            this is OK if the two pointer types are the same size, and if
1129            converting FTSENT ** to long int is the same as converting
1130            FTSENT ** to void * and then to long int.  This heuristic isn't
1131            valid in general but we don't know of any counterexamples.  */
1132         FTSENT *dummy;
1133         int (*compare) (void const *, void const *) =
1134           ((sizeof &dummy == sizeof (void *)
1135             && (long int) &dummy == (long int) (void *) &dummy)
1136            ? (int (*) (void const *, void const *)) sp->fts_compar
1137            : fts_compar);
1138
1139         /*
1140          * Construct an array of pointers to the structures and call qsort(3).
1141          * Reassemble the array in the order returned by qsort.  If unable to
1142          * sort for memory reasons, return the directory entries in their
1143          * current order.  Allocate enough space for the current needs plus
1144          * 40 so don't realloc one entry at a time.
1145          */
1146         if (nitems > sp->fts_nitems) {
1147                 struct _ftsent **a;
1148
1149                 sp->fts_nitems = nitems + 40;
1150                 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1151                     || ! (a = realloc (sp->fts_array,
1152                                        sp->fts_nitems * sizeof *a))) {
1153                         free(sp->fts_array);
1154                         sp->fts_array = NULL;
1155                         sp->fts_nitems = 0;
1156                         return (head);
1157                 }
1158                 sp->fts_array = a;
1159         }
1160         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1161                 *ap++ = p;
1162         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1163         for (head = *(ap = sp->fts_array); --nitems; ++ap)
1164                 ap[0]->fts_link = ap[1];
1165         ap[0]->fts_link = NULL;
1166         return (head);
1167 }
1168
1169 static FTSENT *
1170 internal_function
1171 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1172 {
1173         register FTSENT *p;
1174         size_t len;
1175
1176         /*
1177          * The file name is a variable length array.  Allocate the FTSENT
1178          * structure and the file name in one chunk.
1179          */
1180         len = sizeof(FTSENT) + namelen;
1181         if ((p = malloc(len)) == NULL)
1182                 return (NULL);
1183
1184         /* Copy the name and guarantee NUL termination. */
1185         memmove(p->fts_name, name, namelen);
1186         p->fts_name[namelen] = '\0';
1187
1188         p->fts_namelen = namelen;
1189         p->fts_fts = sp;
1190         p->fts_path = sp->fts_path;
1191         p->fts_errno = 0;
1192         p->fts_flags = 0;
1193         p->fts_instr = FTS_NOINSTR;
1194         p->fts_number = 0;
1195         p->fts_pointer = NULL;
1196         return (p);
1197 }
1198
1199 static void
1200 internal_function
1201 fts_lfree (register FTSENT *head)
1202 {
1203         register FTSENT *p;
1204
1205         /* Free a linked list of structures. */
1206         while ((p = head)) {
1207                 head = head->fts_link;
1208                 free(p);
1209         }
1210 }
1211
1212 /*
1213  * Allow essentially unlimited file name lengths; find, rm, ls should
1214  * all work on any tree.  Most systems will allow creation of file
1215  * names much longer than MAXPATHLEN, even though the kernel won't
1216  * resolve them.  Add the size (not just what's needed) plus 256 bytes
1217  * so don't realloc the file name 2 bytes at a time.
1218  */
1219 static bool
1220 internal_function
1221 fts_palloc (FTS *sp, size_t more)
1222 {
1223         char *p;
1224         size_t new_len = sp->fts_pathlen + more + 256;
1225
1226         /*
1227          * See if fts_pathlen would overflow.
1228          */
1229         if (new_len < sp->fts_pathlen) {
1230                 if (sp->fts_path) {
1231                         free(sp->fts_path);
1232                         sp->fts_path = NULL;
1233                 }
1234                 sp->fts_path = NULL;
1235                 __set_errno (ENAMETOOLONG);
1236                 return false;
1237         }
1238         sp->fts_pathlen = new_len;
1239         p = realloc(sp->fts_path, sp->fts_pathlen);
1240         if (p == NULL) {
1241                 free(sp->fts_path);
1242                 sp->fts_path = NULL;
1243                 return false;
1244         }
1245         sp->fts_path = p;
1246         return true;
1247 }
1248
1249 /*
1250  * When the file name is realloc'd, have to fix all of the pointers in
1251  *  structures already returned.
1252  */
1253 static void
1254 internal_function
1255 fts_padjust (FTS *sp, FTSENT *head)
1256 {
1257         FTSENT *p;
1258         char *addr = sp->fts_path;
1259
1260 #define ADJUST(p) do {                                                  \
1261         if ((p)->fts_accpath != (p)->fts_name) {                        \
1262                 (p)->fts_accpath =                                      \
1263                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1264         }                                                               \
1265         (p)->fts_path = addr;                                           \
1266 } while (0)
1267         /* Adjust the current set of children. */
1268         for (p = sp->fts_child; p; p = p->fts_link)
1269                 ADJUST(p);
1270
1271         /* Adjust the rest of the tree, including the current level. */
1272         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1273                 ADJUST(p);
1274                 p = p->fts_link ? p->fts_link : p->fts_parent;
1275         }
1276 }
1277
1278 static size_t
1279 internal_function
1280 fts_maxarglen (char * const *argv)
1281 {
1282         size_t len, max;
1283
1284         for (max = 0; *argv; ++argv)
1285                 if ((len = strlen(*argv)) > max)
1286                         max = len;
1287         return (max + 1);
1288 }
1289
1290 /*
1291  * Change to dir specified by fd or file name without getting
1292  * tricked by someone changing the world out from underneath us.
1293  * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1294  */
1295 static int
1296 internal_function
1297 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1298 {
1299         int ret, oerrno, newfd;
1300         struct stat sb;
1301
1302         newfd = fd;
1303         if (ISSET(FTS_NOCHDIR))
1304                 return (0);
1305         if (fd < 0 && (newfd = diropen (dir)) < 0)
1306                 return (-1);
1307         if (fstat(newfd, &sb)) {
1308                 ret = -1;
1309                 goto bail;
1310         }
1311         if (p->fts_statp->st_dev != sb.st_dev
1312             || p->fts_statp->st_ino != sb.st_ino) {
1313                 __set_errno (ENOENT);           /* disinformation */
1314                 ret = -1;
1315                 goto bail;
1316         }
1317         ret = fchdir(newfd);
1318 bail:
1319         oerrno = errno;
1320         if (fd < 0)
1321                 (void)close(newfd);
1322         __set_errno (oerrno);
1323         return (ret);
1324 }