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