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