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 defined _LIBC
  79 # include <dirent.h>
  80 # define NAMLEN(dirent) _D_EXACT_NAMLEN (dirent)
  81 #else
  82 # if HAVE_DIRENT_H
  83 #  include <dirent.h>
  84 #  define NAMLEN(dirent) strlen ((dirent)->d_name)
  85 # else
  86 #  define dirent direct
  87 #  define NAMLEN(dirent) (dirent)->d_namlen
  88 #  if HAVE_SYS_NDIR_H
  89 #   include <sys/ndir.h>
  90 #  endif
  91 #  if HAVE_SYS_DIR_H
  92 #   include <sys/dir.h>
  93 #  endif
  94 #  if HAVE_NDIR_H
  95 #   include <ndir.h>
  96 #  endif
  97 # endif
  98 #endif
  99
 100 #ifdef _LIBC
 101 # undef close
 102 # define close __close
 103 # undef closedir
 104 # define closedir __closedir
 105 # undef fchdir
 106 # define fchdir __fchdir
 107 # undef open
 108 # define open __open
 109 # undef opendir
 110 # define opendir __opendir
 111 # undef readdir
 112 # define readdir __readdir
 113 #else
 114 # undef internal_function
 115 # define internal_function /* empty */
 116 #endif
 117
 118 #ifndef __set_errno
 119 # define __set_errno(Val) errno = (Val)
 120 #endif
 121
 122 #ifndef __attribute__
 123 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
 124 #  define __attribute__(x) /* empty */
 125 # endif
 126 #endif
 127
 128 #ifndef ATTRIBUTE_UNUSED
 129 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
 130 #endif
 131
 132
 133 static FTSENT   *fts_alloc (FTS *, const char *, size_t) internal_function;
 134 static FTSENT   *fts_build (FTS *, int) internal_function;
 135 static void      fts_lfree (FTSENT *) internal_function;
 136 static void      fts_load (FTS *, FTSENT *) internal_function;
 137 static size_t    fts_maxarglen (char * const *) internal_function;
 138 static void      fts_padjust (FTS *, FTSENT *) internal_function;
 139 static bool      fts_palloc (FTS *, size_t) internal_function;
 140 static FTSENT   *fts_sort (FTS *, FTSENT *, size_t) internal_function;
 141 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
 142 static int      fts_safe_changedir (FTS *, FTSENT *, int, const char *)
 143      internal_function;
 144
 145 #if _LGPL_PACKAGE
 146 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
 147 static void leave_dir (FTS *fts, FTSENT *ent) {}
 148 static bool setup_dir (FTS *fts) { return true; }
 149 static void free_dir (FTS *fts) {}
 150 #else
 151 # include "fcntl--.h"
 152 # include "fts-cycle.c"
 153 #endif
 154
 155 #ifndef MAX
 156 # define MAX(a,b) ((a) > (b) ? (a) : (b))
 157 #endif
 158
 159 #ifndef SIZE_MAX
 160 # define SIZE_MAX ((size_t) -1)
 161 #endif
 162
 163 #ifndef O_DIRECTORY
 164 # define O_DIRECTORY 0
 165 #endif
 166
 167 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
 168
 169 #define CLR(opt)        (sp->fts_options &= ~(opt))
 170 #define ISSET(opt)      (sp->fts_options & (opt))
 171 #define SET(opt)        (sp->fts_options |= (opt))
 172
 173 #define FCHDIR(sp, fd)  (!ISSET(FTS_NOCHDIR) && fchdir(fd))
 174
 175 /* fts_build flags */
 176 #define BCHILD          1               /* fts_children */
 177 #define BNAMES          2               /* fts_children, names only */
 178 #define BREAD           3               /* fts_read */
 179
 180 #if FTS_DEBUG
 181 # include <inttypes.h>
 182 # include <stdint.h>
 183 # include <stdio.h>
 184 bool fts_debug = false;
 185 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
 186 #else
 187 # define Dprintf(x)
 188 #endif
 189
 190 #define LEAVE_DIR(Fts, Ent, Tag)                                \
 191   do                                                            \
 192     {                                                           \
 193       Dprintf (("  %s-leaving: %s\n", Tag, (Ent)->fts_path));   \
 194       leave_dir (Fts, Ent);                                     \
 195     }                                                           \
 196   while (false)
 197
 198 /* Open the directory DIR if possible, and return a file
 199    descriptor.  Return -1 and set errno on failure.  It doesn't matter
 200    whether the file descriptor has read or write access.  */
 201
 202 static int
 203 internal_function
 204 diropen (char const *dir)
 205 {
 206   int fd = open (dir, O_RDONLY | O_DIRECTORY);
 207   if (fd < 0)
 208     fd = open (dir, O_WRONLY | O_DIRECTORY);
 209   return fd;
 210 }
 211
 212 FTS *
 213 fts_open (char * const *argv,
 214           register int options,
 215           int (*compar) (FTSENT const **, FTSENT const **))
 216 {
 217         register FTS *sp;
 218         register FTSENT *p, *root;
 219         register size_t nitems;
 220         FTSENT *parent, *tmp = NULL;    /* pacify gcc */
 221         size_t len;
 222
 223         /* Options check. */
 224         if (options & ~FTS_OPTIONMASK) {
 225                 __set_errno (EINVAL);
 226                 return (NULL);
 227         }
 228
 229         /* Allocate/initialize the stream */
 230         if ((sp = malloc(sizeof(FTS))) == NULL)
 231                 return (NULL);
 232         memset(sp, 0, sizeof(FTS));
 233         sp->fts_compar = compar;
 234         sp->fts_options = options;
 235
 236         /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
 237         if (ISSET(FTS_LOGICAL))
 238                 SET(FTS_NOCHDIR);
 239
 240         /*
 241          * Start out with 1K of file name space, and enough, in any case,
 242          * to hold the user's file names.
 243          */
 244 #ifndef MAXPATHLEN
 245 # define MAXPATHLEN 1024
 246 #endif
 247         {
 248           size_t maxarglen = fts_maxarglen(argv);
 249           if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
 250                   goto mem1;
 251         }
 252
 253         /* Allocate/initialize root's parent. */
 254         if ((parent = fts_alloc(sp, "", 0)) == NULL)
 255                 goto mem2;
 256         parent->fts_level = FTS_ROOTPARENTLEVEL;
 257
 258         /* Allocate/initialize root(s). */
 259         for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
 260                 /* Don't allow zero-length file names. */
 261                 if ((len = strlen(*argv)) == 0) {
 262                         __set_errno (ENOENT);
 263                         goto mem3;
 264                 }
 265
 266                 if ((p = fts_alloc(sp, *argv, len)) == NULL)
 267                         goto mem3;
 268                 p->fts_level = FTS_ROOTLEVEL;
 269                 p->fts_parent = parent;
 270                 p->fts_accpath = p->fts_name;
 271                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
 272
 273                 /* Command-line "." and ".." are real directories. */
 274                 if (p->fts_info == FTS_DOT)
 275                         p->fts_info = FTS_D;
 276
 277                 /*
 278                  * If comparison routine supplied, traverse in sorted
 279                  * order; otherwise traverse in the order specified.
 280                  */
 281                 if (compar) {
 282                         p->fts_link = root;
 283                         root = p;
 284                 } else {
 285                         p->fts_link = NULL;
 286                         if (root == NULL)
 287                                 tmp = root = p;
 288                         else {
 289                                 tmp->fts_link = p;
 290                                 tmp = p;
 291                         }
 292                 }
 293         }
 294         if (compar && nitems > 1)
 295                 root = fts_sort(sp, root, nitems);
 296
 297         /*
 298          * Allocate a dummy pointer and make fts_read think that we've just
 299          * finished the node before the root(s); set p->fts_info to FTS_INIT
 300          * so that everything about the "current" node is ignored.
 301          */
 302         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
 303                 goto mem3;
 304         sp->fts_cur->fts_link = root;
 305         sp->fts_cur->fts_info = FTS_INIT;
 306         if (! setup_dir (sp))
 307           goto mem3;
 308
 309         /*
 310          * If using chdir(2), grab a file descriptor pointing to dot to ensure
 311          * that we can get back here; this could be avoided for some file names,
 312          * but almost certainly not worth the effort.  Slashes, symbolic links,
 313          * and ".." are all fairly nasty problems.  Note, if we can't get the
 314          * descriptor we run anyway, just more slowly.
 315          */
 316         if (!ISSET(FTS_NOCHDIR)
 317             && (sp->fts_rfd = diropen (".")) < 0)
 318                 SET(FTS_NOCHDIR);
 319
 320         return (sp);
 321
 322 mem3:   fts_lfree(root);
 323         free(parent);
 324 mem2:   free(sp->fts_path);
 325 mem1:   free(sp);
 326         return (NULL);
 327 }
 328
 329 static void
 330 internal_function
 331 fts_load (FTS *sp, register FTSENT *p)
 332 {
 333         register size_t len;
 334         register char *cp;
 335
 336         /*
 337          * Load the stream structure for the next traversal.  Since we don't
 338          * actually enter the directory until after the preorder visit, set
 339          * the fts_accpath field specially so the chdir gets done to the right
 340          * place and the user can access the first node.  From fts_open it's
 341          * known that the file name will fit.
 342          */
 343         len = p->fts_pathlen = p->fts_namelen;
 344         memmove(sp->fts_path, p->fts_name, len + 1);
 345         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
 346                 len = strlen(++cp);
 347                 memmove(p->fts_name, cp, len + 1);
 348                 p->fts_namelen = len;
 349         }
 350         p->fts_accpath = p->fts_path = sp->fts_path;
 351         sp->fts_dev = p->fts_statp->st_dev;
 352 }
 353
 354 int
 355 fts_close (FTS *sp)
 356 {
 357         register FTSENT *freep, *p;
 358         int saved_errno = 0;
 359
 360         /*
 361          * This still works if we haven't read anything -- the dummy structure
 362          * points to the root list, so we step through to the end of the root
 363          * list which has a valid parent pointer.
 364          */
 365         if (sp->fts_cur) {
 366                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
 367                         freep = p;
 368                         p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
 369                         free(freep);
 370                 }
 371                 free(p);
 372         }
 373
 374         /* Free up child linked list, sort array, file name buffer. */
 375         if (sp->fts_child)
 376                 fts_lfree(sp->fts_child);
 377         if (sp->fts_array)
 378                 free(sp->fts_array);
 379         free(sp->fts_path);
 380
 381         /* Return to original directory, save errno if necessary. */
 382         if (!ISSET(FTS_NOCHDIR)) {
 383                 if (fchdir(sp->fts_rfd))
 384                         saved_errno = errno;
 385                 (void)close(sp->fts_rfd);
 386         }
 387
 388         free_dir (sp);
 389
 390         /* Free up the stream pointer. */
 391         free(sp);
 392
 393         /* Set errno and return. */
 394         if (saved_errno) {
 395                 __set_errno (saved_errno);
 396                 return (-1);
 397         }
 398
 399         return (0);
 400 }
 401
 402 /*
 403  * Special case of "/" at the end of the file name so that slashes aren't
 404  * appended which would cause file names to be written as "....//foo".
 405  */
 406 #define NAPPEND(p)                                                      \
 407         (p->fts_path[p->fts_pathlen - 1] == '/'                         \
 408             ? p->fts_pathlen - 1 : p->fts_pathlen)
 409
 410 FTSENT *
 411 fts_read (register FTS *sp)
 412 {
 413         register FTSENT *p, *tmp;
 414         register unsigned short int instr;
 415         register char *t;
 416         int saved_errno;
 417
 418         /* If finished or unrecoverable error, return NULL. */
 419         if (sp->fts_cur == NULL || ISSET(FTS_STOP))
 420                 return (NULL);
 421
 422         /* Set current node pointer. */
 423         p = sp->fts_cur;
 424
 425         /* Save and zero out user instructions. */
 426         instr = p->fts_instr;
 427         p->fts_instr = FTS_NOINSTR;
 428
 429         /* Any type of file may be re-visited; re-stat and re-turn. */
 430         if (instr == FTS_AGAIN) {
 431                 p->fts_info = fts_stat(sp, p, false);
 432                 return (p);
 433         }
 434         Dprintf (("fts_read: p=%s\n",
 435                   p->fts_info == FTS_INIT ? "" : p->fts_path));
 436
 437         /*
 438          * Following a symlink -- SLNONE test allows application to see
 439          * SLNONE and recover.  If indirecting through a symlink, have
 440          * keep a pointer to current location.  If unable to get that
 441          * pointer, follow fails.
 442          */
 443         if (instr == FTS_FOLLOW &&
 444             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
 445                 p->fts_info = fts_stat(sp, p, true);
 446                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 447                         if ((p->fts_symfd = diropen (".")) < 0) {
 448                                 p->fts_errno = errno;
 449                                 p->fts_info = FTS_ERR;
 450                         } else
 451                                 p->fts_flags |= FTS_SYMFOLLOW;
 452                 }
 453                 goto check_for_dir;
 454         }
 455
 456         /* Directory in pre-order. */
 457         if (p->fts_info == FTS_D) {
 458                 /* If skipped or crossed mount point, do post-order visit. */
 459                 if (instr == FTS_SKIP ||
 460                     (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
 461                         if (p->fts_flags & FTS_SYMFOLLOW)
 462                                 (void)close(p->fts_symfd);
 463                         if (sp->fts_child) {
 464                                 fts_lfree(sp->fts_child);
 465                                 sp->fts_child = NULL;
 466                         }
 467                         p->fts_info = FTS_DP;
 468                         LEAVE_DIR (sp, p, "1");
 469                         return (p);
 470                 }
 471
 472                 /* Rebuild if only read the names and now traversing. */
 473                 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
 474                         CLR(FTS_NAMEONLY);
 475                         fts_lfree(sp->fts_child);
 476                         sp->fts_child = NULL;
 477                 }
 478
 479                 /*
 480                  * Cd to the subdirectory.
 481                  *
 482                  * If have already read and now fail to chdir, whack the list
 483                  * to make the names come out right, and set the parent errno
 484                  * so the application will eventually get an error condition.
 485                  * Set the FTS_DONTCHDIR flag so that when we logically change
 486                  * directories back to the parent we don't do a chdir.
 487                  *
 488                  * If haven't read do so.  If the read fails, fts_build sets
 489                  * FTS_STOP or the fts_info field of the node.
 490                  */
 491                 if (sp->fts_child != NULL) {
 492                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
 493                                 p->fts_errno = errno;
 494                                 p->fts_flags |= FTS_DONTCHDIR;
 495                                 for (p = sp->fts_child; p != NULL;
 496                                      p = p->fts_link)
 497                                         p->fts_accpath =
 498                                             p->fts_parent->fts_accpath;
 499                         }
 500                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
 501                         if (ISSET(FTS_STOP))
 502                                 return (NULL);
 503                         /* If fts_build's call to fts_safe_changedir failed
 504                            because it was not able to fchdir into a
 505                            subdirectory, tell the caller.  */
 506                         if (p->fts_errno)
 507                                 p->fts_info = FTS_ERR;
 508                         /* FIXME: see if this should be in an else block */
 509                         LEAVE_DIR (sp, p, "2");
 510                         return (p);
 511                 }
 512                 p = sp->fts_child;
 513                 sp->fts_child = NULL;
 514                 goto name;
 515         }
 516
 517         /* Move to the next node on this level. */
 518 next:   tmp = p;
 519         if ((p = p->fts_link) != NULL) {
 520                 free(tmp);
 521
 522                 /*
 523                  * If reached the top, return to the original directory (or
 524                  * the root of the tree), and load the file names for the next
 525                  * root.
 526                  */
 527                 if (p->fts_level == FTS_ROOTLEVEL) {
 528                         if (FCHDIR(sp, sp->fts_rfd)) {
 529                                 SET(FTS_STOP);
 530                                 sp->fts_cur = p;
 531                                 return (NULL);
 532                         }
 533                         fts_load(sp, p);
 534                         goto check_for_dir;
 535                 }
 536
 537                 /*
 538                  * User may have called fts_set on the node.  If skipped,
 539                  * ignore.  If followed, get a file descriptor so we can
 540                  * get back if necessary.
 541                  */
 542                 if (p->fts_instr == FTS_SKIP)
 543                         goto next;
 544                 if (p->fts_instr == FTS_FOLLOW) {
 545                         p->fts_info = fts_stat(sp, p, true);
 546                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
 547                                 if ((p->fts_symfd = diropen (".")) < 0) {
 548                                         p->fts_errno = errno;
 549                                         p->fts_info = FTS_ERR;
 550                                 } else
 551                                         p->fts_flags |= FTS_SYMFOLLOW;
 552                         }
 553                         p->fts_instr = FTS_NOINSTR;
 554                 }
 555
 556 name:           t = sp->fts_path + NAPPEND(p->fts_parent);
 557                 *t++ = '/';
 558                 memmove(t, p->fts_name, p->fts_namelen + 1);
 559 check_for_dir:
 560                 sp->fts_cur = p;
 561                 if (p->fts_info == FTS_D)
 562                   {
 563                     Dprintf (("  %s-entering: %s\n", sp, p->fts_path));
 564                     if (! enter_dir (sp, p))
 565                       {
 566                         __set_errno (ENOMEM);
 567                         return NULL;
 568                       }
 569                   }
 570                 return p;
 571         }
 572
 573         /* Move up to the parent node. */
 574         p = tmp->fts_parent;
 575         free(tmp);
 576
 577         if (p->fts_level == FTS_ROOTPARENTLEVEL) {
 578                 /*
 579                  * Done; free everything up and set errno to 0 so the user
 580                  * can distinguish between error and EOF.
 581                  */
 582                 free(p);
 583                 __set_errno (0);
 584                 return (sp->fts_cur = NULL);
 585         }
 586
 587         /* NUL terminate the file name.  */
 588         sp->fts_path[p->fts_pathlen] = '\0';
 589
 590         /*
 591          * Return to the parent directory.  If at a root node or came through
 592          * a symlink, go back through the file descriptor.  Otherwise, cd up
 593          * one directory.
 594          */
 595         if (p->fts_level == FTS_ROOTLEVEL) {
 596                 if (FCHDIR(sp, sp->fts_rfd)) {
 597                         p->fts_errno = errno;
 598                         SET(FTS_STOP);
 599                 }
 600         } else if (p->fts_flags & FTS_SYMFOLLOW) {
 601                 if (FCHDIR(sp, p->fts_symfd)) {
 602                         saved_errno = errno;
 603                         (void)close(p->fts_symfd);
 604                         __set_errno (saved_errno);
 605                         p->fts_errno = errno;
 606                         SET(FTS_STOP);
 607                 }
 608                 (void)close(p->fts_symfd);
 609         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
 610                    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
 611                 p->fts_errno = errno;
 612                 SET(FTS_STOP);
 613         }
 614         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
 615         if (p->fts_errno == 0)
 616                 LEAVE_DIR (sp, p, "3");
 617         sp->fts_cur = p;
 618         return ISSET(FTS_STOP) ? NULL : p;
 619 }
 620
 621 /*
 622  * Fts_set takes the stream as an argument although it's not used in this
 623  * implementation; it would be necessary if anyone wanted to add global
 624  * semantics to fts using fts_set.  An error return is allowed for similar
 625  * reasons.
 626  */
 627 /* ARGSUSED */
 628 int
 629 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
 630 {
 631         if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
 632             instr != FTS_NOINSTR && instr != FTS_SKIP) {
 633                 __set_errno (EINVAL);
 634                 return (1);
 635         }
 636         p->fts_instr = instr;
 637         return (0);
 638 }
 639
 640 FTSENT *
 641 fts_children (register FTS *sp, int instr)
 642 {
 643         register FTSENT *p;
 644         int fd;
 645
 646         if (instr != 0 && instr != FTS_NAMEONLY) {
 647                 __set_errno (EINVAL);
 648                 return (NULL);
 649         }
 650
 651         /* Set current node pointer. */
 652         p = sp->fts_cur;
 653
 654         /*
 655          * Errno set to 0 so user can distinguish empty directory from
 656          * an error.
 657          */
 658         __set_errno (0);
 659
 660         /* Fatal errors stop here. */
 661         if (ISSET(FTS_STOP))
 662                 return (NULL);
 663
 664         /* Return logical hierarchy of user's arguments. */
 665         if (p->fts_info == FTS_INIT)
 666                 return (p->fts_link);
 667
 668         /*
 669          * If not a directory being visited in pre-order, stop here.  Could
 670          * allow FTS_DNR, assuming the user has fixed the problem, but the
 671          * same effect is available with FTS_AGAIN.
 672          */
 673         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
 674                 return (NULL);
 675
 676         /* Free up any previous child list. */
 677         if (sp->fts_child != NULL)
 678                 fts_lfree(sp->fts_child);
 679
 680         if (instr == FTS_NAMEONLY) {
 681                 SET(FTS_NAMEONLY);
 682                 instr = BNAMES;
 683         } else
 684                 instr = BCHILD;
 685
 686         /*
 687          * If using chdir on a relative file name and called BEFORE fts_read
 688          * does its chdir to the root of a traversal, we can lose -- we need to
 689          * chdir into the subdirectory, and we don't know where the current
 690          * directory is, so we can't get back so that the upcoming chdir by
 691          * fts_read will work.
 692          */
 693         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
 694             ISSET(FTS_NOCHDIR))
 695                 return (sp->fts_child = fts_build(sp, instr));
 696
 697         if ((fd = diropen (".")) < 0)
 698                 return (sp->fts_child = NULL);
 699         sp->fts_child = fts_build(sp, instr);
 700         if (fchdir(fd)) {
 701                 int saved_errno = errno;
 702                 (void)close(fd);
 703                 __set_errno (saved_errno);
 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->fts_cycle.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->fts_cycle.ht); ad != NULL;
1044            ad = hash_get_next (sp->fts_cycle.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 (errno == ENOENT
1077                             && lstat(p->fts_accpath, sbp) == 0) {
1078                                 __set_errno (0);
1079                                 return (FTS_SLNONE);
1080                         }
1081                         p->fts_errno = saved_errno;
1082                         goto err;
1083                 }
1084         } else if (lstat(p->fts_accpath, sbp)) {
1085                 p->fts_errno = errno;
1086 err:            memset(sbp, 0, sizeof(struct stat));
1087                 return (FTS_NS);
1088         }
1089
1090         if (S_ISDIR(sbp->st_mode)) {
1091                 if (ISDOT(p->fts_name))
1092                         return (FTS_DOT);
1093
1094 #if _LGPL_PACKAGE
1095                 {
1096                   /*
1097                    * Cycle detection is done by brute force when the directory
1098                    * is first encountered.  If the tree gets deep enough or the
1099                    * number of symbolic links to directories is high enough,
1100                    * something faster might be worthwhile.
1101                    */
1102                   FTSENT *t;
1103
1104                   for (t = p->fts_parent;
1105                        t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1106                     if (sbp->st_ino == t->fts_statp->st_ino
1107                         && sbp->st_dev == t->fts_statp->st_dev)
1108                       {
1109                         p->fts_cycle = t;
1110                         return (FTS_DC);
1111                       }
1112                 }
1113 #endif
1114
1115                 return (FTS_D);
1116         }
1117         if (S_ISLNK(sbp->st_mode))
1118                 return (FTS_SL);
1119         if (S_ISREG(sbp->st_mode))
1120                 return (FTS_F);
1121         return (FTS_DEFAULT);
1122 }
1123
1124 static int
1125 fts_compar (void const *a, void const *b)
1126 {
1127   /* Convert A and B to the correct types, to pacify the compiler, and
1128      for portability to bizarre hosts where "void const *" and "FTSENT
1129      const **" differ in runtime representation.  The comparison
1130      function cannot modify *a and *b, but there is no compile-time
1131      check for this.  */
1132   FTSENT const **pa = (FTSENT const **) a;
1133   FTSENT const **pb = (FTSENT const **) b;
1134   return pa[0]->fts_fts->fts_compar (pa, pb);
1135 }
1136
1137 static FTSENT *
1138 internal_function
1139 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1140 {
1141         register FTSENT **ap, *p;
1142
1143         /* On most modern hosts, void * and FTSENT ** have the same
1144            run-time representation, and one can convert sp->fts_compar to
1145            the type qsort expects without problem.  Use the heuristic that
1146            this is OK if the two pointer types are the same size, and if
1147            converting FTSENT ** to long int is the same as converting
1148            FTSENT ** to void * and then to long int.  This heuristic isn't
1149            valid in general but we don't know of any counterexamples.  */
1150         FTSENT *dummy;
1151         int (*compare) (void const *, void const *) =
1152           ((sizeof &dummy == sizeof (void *)
1153             && (long int) &dummy == (long int) (void *) &dummy)
1154            ? (int (*) (void const *, void const *)) sp->fts_compar
1155            : fts_compar);
1156
1157         /*
1158          * Construct an array of pointers to the structures and call qsort(3).
1159          * Reassemble the array in the order returned by qsort.  If unable to
1160          * sort for memory reasons, return the directory entries in their
1161          * current order.  Allocate enough space for the current needs plus
1162          * 40 so don't realloc one entry at a time.
1163          */
1164         if (nitems > sp->fts_nitems) {
1165                 struct _ftsent **a;
1166
1167                 sp->fts_nitems = nitems + 40;
1168                 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1169                     || ! (a = realloc (sp->fts_array,
1170                                        sp->fts_nitems * sizeof *a))) {
1171                         free(sp->fts_array);
1172                         sp->fts_array = NULL;
1173                         sp->fts_nitems = 0;
1174                         return (head);
1175                 }
1176                 sp->fts_array = a;
1177         }
1178         for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1179                 *ap++ = p;
1180         qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1181         for (head = *(ap = sp->fts_array); --nitems; ++ap)
1182                 ap[0]->fts_link = ap[1];
1183         ap[0]->fts_link = NULL;
1184         return (head);
1185 }
1186
1187 static FTSENT *
1188 internal_function
1189 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1190 {
1191         register FTSENT *p;
1192         size_t len;
1193
1194         /*
1195          * The file name is a variable length array.  Allocate the FTSENT
1196          * structure and the file name in one chunk.
1197          */
1198         len = sizeof(FTSENT) + namelen;
1199         if ((p = malloc(len)) == NULL)
1200                 return (NULL);
1201
1202         /* Copy the name and guarantee NUL termination. */
1203         memmove(p->fts_name, name, namelen);
1204         p->fts_name[namelen] = '\0';
1205
1206         p->fts_namelen = namelen;
1207         p->fts_fts = sp;
1208         p->fts_path = sp->fts_path;
1209         p->fts_errno = 0;
1210         p->fts_flags = 0;
1211         p->fts_instr = FTS_NOINSTR;
1212         p->fts_number = 0;
1213         p->fts_pointer = NULL;
1214         return (p);
1215 }
1216
1217 static void
1218 internal_function
1219 fts_lfree (register FTSENT *head)
1220 {
1221         register FTSENT *p;
1222
1223         /* Free a linked list of structures. */
1224         while ((p = head)) {
1225                 head = head->fts_link;
1226                 free(p);
1227         }
1228 }
1229
1230 /*
1231  * Allow essentially unlimited file name lengths; find, rm, ls should
1232  * all work on any tree.  Most systems will allow creation of file
1233  * names much longer than MAXPATHLEN, even though the kernel won't
1234  * resolve them.  Add the size (not just what's needed) plus 256 bytes
1235  * so don't realloc the file name 2 bytes at a time.
1236  */
1237 static bool
1238 internal_function
1239 fts_palloc (FTS *sp, size_t more)
1240 {
1241         char *p;
1242         size_t new_len = sp->fts_pathlen + more + 256;
1243
1244         /*
1245          * See if fts_pathlen would overflow.
1246          */
1247         if (new_len < sp->fts_pathlen) {
1248                 if (sp->fts_path) {
1249                         free(sp->fts_path);
1250                         sp->fts_path = NULL;
1251                 }
1252                 sp->fts_path = NULL;
1253                 __set_errno (ENAMETOOLONG);
1254                 return false;
1255         }
1256         sp->fts_pathlen = new_len;
1257         p = realloc(sp->fts_path, sp->fts_pathlen);
1258         if (p == NULL) {
1259                 free(sp->fts_path);
1260                 sp->fts_path = NULL;
1261                 return false;
1262         }
1263         sp->fts_path = p;
1264         return true;
1265 }
1266
1267 /*
1268  * When the file name is realloc'd, have to fix all of the pointers in
1269  *  structures already returned.
1270  */
1271 static void
1272 internal_function
1273 fts_padjust (FTS *sp, FTSENT *head)
1274 {
1275         FTSENT *p;
1276         char *addr = sp->fts_path;
1277
1278 #define ADJUST(p) do {                                                  \
1279         if ((p)->fts_accpath != (p)->fts_name) {                        \
1280                 (p)->fts_accpath =                                      \
1281                     (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
1282         }                                                               \
1283         (p)->fts_path = addr;                                           \
1284 } while (0)
1285         /* Adjust the current set of children. */
1286         for (p = sp->fts_child; p; p = p->fts_link)
1287                 ADJUST(p);
1288
1289         /* Adjust the rest of the tree, including the current level. */
1290         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1291                 ADJUST(p);
1292                 p = p->fts_link ? p->fts_link : p->fts_parent;
1293         }
1294 }
1295
1296 static size_t
1297 internal_function
1298 fts_maxarglen (char * const *argv)
1299 {
1300         size_t len, max;
1301
1302         for (max = 0; *argv; ++argv)
1303                 if ((len = strlen(*argv)) > max)
1304                         max = len;
1305         return (max + 1);
1306 }
1307
1308 /*
1309  * Change to dir specified by fd or file name without getting
1310  * tricked by someone changing the world out from underneath us.
1311  * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1312  */
1313 static int
1314 internal_function
1315 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1316 {
1317         int ret, oerrno, newfd;
1318         struct stat sb;
1319
1320         newfd = fd;
1321         if (ISSET(FTS_NOCHDIR))
1322                 return (0);
1323         if (fd < 0 && (newfd = diropen (dir)) < 0)
1324                 return (-1);
1325         if (fstat(newfd, &sb)) {
1326                 ret = -1;
1327                 goto bail;
1328         }
1329         if (p->fts_statp->st_dev != sb.st_dev
1330             || p->fts_statp->st_ino != sb.st_ino) {
1331                 __set_errno (ENOENT);           /* disinformation */
1332                 ret = -1;
1333                 goto bail;
1334         }
1335         ret = fchdir(newfd);
1336 bail:
1337         oerrno = errno;
1338         if (fd < 0)
1339                 (void)close(newfd);
1340         __set_errno (oerrno);
1341         return (ret);
1342 }