lib/fts.c

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