lib/fts_.h

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004-2017 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 3 of the License, or
   8    (at your option) 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, see <http://www.gnu.org/licenses/>.  */
  17
  18 /*
  19  * Copyright (c) 1989, 1993
  20  *      The Regents of the University of California.  All rights reserved.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the above copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 4. Neither the name of the University nor the names of its contributors
  31  *    may be used to endorse or promote products derived from this software
  32  *    without specific prior written permission.
  33  *
  34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND
  35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44  * SUCH DAMAGE.
  45  *
  46  *      @(#)fts.h       8.3 (Berkeley) 8/14/94
  47  */
  48
  49 #ifndef _FTS_H
  50 # define _FTS_H 1
  51
  52 # ifdef _LIBC
  53 #  include <features.h>
  54 #  if __STDC_VERSION__ < 199901L
  55 #   define __FLEXIBLE_ARRAY_MEMBER 1
  56 #  else
  57 #   define __FLEXIBLE_ARRAY_MEMBER
  58 #  endif
  59 # else
  60 #  define __FLEXIBLE_ARRAY_MEMBER FLEXIBLE_ARRAY_MEMBER
  61 #  undef __THROW
  62 #  define __THROW
  63 #  undef __BEGIN_DECLS
  64 #  undef __END_DECLS
  65 #  ifdef __cplusplus
  66 #   define __BEGIN_DECLS extern "C" {
  67 #   define __END_DECLS }
  68 #  else
  69 #   define __BEGIN_DECLS
  70 #   define __END_DECLS
  71 #  endif
  72 # endif
  73
  74 # include <stddef.h>
  75 # include <sys/types.h>
  76 # include <dirent.h>
  77 # include <sys/stat.h>
  78 # include "i-ring.h"
  79
  80 typedef struct {
  81         struct _ftsent *fts_cur;        /* current node */
  82         struct _ftsent *fts_child;      /* linked list of children */
  83         struct _ftsent **fts_array;     /* sort array */
  84         dev_t fts_dev;                  /* starting device # */
  85         char *fts_path;                 /* file name for this descent */
  86         int fts_rfd;                    /* fd for root */
  87         int fts_cwd_fd;                 /* the file descriptor on which the
  88                                            virtual cwd is open, or AT_FDCWD */
  89         size_t fts_pathlen;             /* sizeof(path) */
  90         size_t fts_nitems;              /* elements in the sort array */
  91         int (*fts_compar) (struct _ftsent const **, struct _ftsent const **);
  92                                         /* compare fn */
  93
  94 # define FTS_COMFOLLOW  0x0001          /* follow command line symlinks */
  95 # define FTS_LOGICAL    0x0002          /* logical walk */
  96 # define FTS_NOCHDIR    0x0004          /* don't change directories */
  97 # define FTS_NOSTAT     0x0008          /* don't get stat info */
  98 # define FTS_PHYSICAL   0x0010          /* physical walk */
  99 # define FTS_SEEDOT     0x0020          /* return dot and dot-dot */
 100 # define FTS_XDEV       0x0040          /* don't cross devices */
 101 # define FTS_WHITEOUT   0x0080          /* return whiteout information */
 102
 103   /* There are two ways to detect cycles.
 104      The lazy way (which works only with FTS_PHYSICAL),
 105      with which one may process a directory that is a
 106      part of the cycle several times before detecting the cycle.
 107      The "tight" way, whereby fts uses more memory (proportional
 108      to number of "active" directories, aka distance from root
 109      of current tree to current directory -- see active_dir_ht)
 110      to detect any cycle right away.  For example, du must use
 111      this option to avoid counting disk space in a cycle multiple
 112      times, but chown -R need not.
 113      The default is to use the constant-memory lazy way, when possible
 114      (see below).
 115
 116      However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
 117      using lazy cycle detection is inadequate.  For example, traversing
 118      a directory containing a symbolic link to a peer directory, it is
 119      possible to encounter the same directory twice even though there
 120      is no cycle:
 121      dir
 122      ...
 123      slink -> dir
 124      So, when FTS_LOGICAL is selected, we have to use a different
 125      mode of cycle detection: FTS_TIGHT_CYCLE_CHECK.  */
 126 # define FTS_TIGHT_CYCLE_CHECK  0x0100
 127
 128   /* Use this flag to enable semantics with which the parent
 129      application may be made both more efficient and more robust.
 130      Whereas the default is to visit each directory in a recursive
 131      traversal (via chdir), using this flag makes it so the initial
 132      working directory is never changed.  Instead, these functions
 133      perform the traversal via a virtual working directory, maintained
 134      through the file descriptor member, fts_cwd_fd.  */
 135 # define FTS_CWDFD              0x0200
 136
 137   /* Historically, for each directory that fts initially encounters, it would
 138      open it, read all entries, and stat each entry, storing the results, and
 139      then it would process the first entry.  But that behavior is bad for
 140      locality of reference, and also causes trouble with inode-simulating
 141      file systems like FAT, CIFS, FUSE-based ones, etc., when entries from
 142      their name/inode cache are flushed too early.
 143      Use this flag to make fts_open and fts_read defer the stat/lstat/fststat
 144      of each entry until it is actually processed.  However, note that if you
 145      use this option and also specify a comparison function, that function may
 146      not examine any data via fts_statp.  However, when fts_statp->st_mode is
 147      nonzero, the S_IFMT type bits are valid, with mapped dirent.d_type data.
 148      Of course, that happens only on file systems that provide useful
 149      dirent.d_type data.  */
 150 # define FTS_DEFER_STAT         0x0400
 151
 152 # define FTS_NOATIME    0x0800          /* use O_NOATIME during traversal */
 153
 154   /* Use this flag to disable stripping of trailing slashes
 155      from input path names during fts_open initialization.  */
 156 # define FTS_VERBATIM   0x1000
 157
 158 # define FTS_OPTIONMASK 0x1fff          /* valid user option mask */
 159
 160 # define FTS_NAMEONLY   0x2000          /* (private) child names only */
 161 # define FTS_STOP       0x4000          /* (private) unrecoverable error */
 162         int fts_options;                /* fts_open options, global flags */
 163
 164         /* Map a directory's device number to a boolean.  The boolean is
 165            true if for that file system (type determined by a single fstatfs
 166            call per FS) st_nlink can be used to calculate the number of
 167            sub-directory entries in a directory.
 168            Using this table is an optimization that permits us to look up
 169            file system type on a per-inode basis at the minimal cost of
 170            calling fstatfs only once per traversed device.  */
 171         struct hash_table *fts_leaf_optimization_works_ht;
 172
 173         union {
 174                 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
 175                    specified.  It records the directories between a starting
 176                    point and the current directory.  I.e., a directory is
 177                    recorded here IFF we have visited it once, but we have not
 178                    yet completed processing of all its entries.  Every time we
 179                    visit a new directory, we add that directory to this set.
 180                    When we finish with a directory (usually by visiting it a
 181                    second time), we remove it from this set.  Each entry in
 182                    this data structure is a device/inode pair.  This data
 183                    structure is used to detect directory cycles efficiently and
 184                    promptly even when the depth of a hierarchy is in the tens
 185                    of thousands.  */
 186                 struct hash_table *ht;
 187
 188                 /* FIXME: rename these two members to have the fts_ prefix */
 189                 /* This data structure uses a lazy cycle-detection algorithm,
 190                    as done by rm via cycle-check.c.  It's the default,
 191                    but it's not appropriate for programs like du.  */
 192                 struct cycle_check_state *state;
 193         } fts_cycle;
 194
 195         /* A stack of the file descriptors corresponding to the
 196            most-recently traversed parent directories.
 197            Currently used only in FTS_CWDFD mode.  */
 198         I_ring fts_fd_ring;
 199 } FTS;
 200
 201 typedef struct _ftsent {
 202         struct _ftsent *fts_cycle;      /* cycle node */
 203         struct _ftsent *fts_parent;     /* parent directory */
 204         struct _ftsent *fts_link;       /* next file in directory */
 205         DIR *fts_dirp;                  /* Dir pointer for any directory
 206                                            containing more entries than we
 207                                            read at one time.  */
 208         long fts_number;                /* local numeric value */
 209         void *fts_pointer;              /* local address value */
 210         char *fts_accpath;              /* access file name */
 211         char *fts_path;                 /* root name; == fts_fts->fts_path */
 212         int fts_errno;                  /* errno for this node */
 213         int fts_symfd;                  /* fd for symlink */
 214         size_t fts_pathlen;             /* strlen(fts_path) */
 215
 216         FTS *fts_fts;                   /* the file hierarchy itself */
 217
 218 # define FTS_ROOTPARENTLEVEL    (-1)
 219 # define FTS_ROOTLEVEL           0
 220         ptrdiff_t fts_level;            /* depth (-1 to N) */
 221
 222         size_t fts_namelen;             /* strlen(fts_name) */
 223
 224         /* If not (nlink_t) -1, an upper bound on the number of
 225            remaining subdirectories of interest.  If this becomes
 226            zero, some work can be avoided.  */
 227         nlink_t fts_n_dirs_remaining;
 228
 229 # define FTS_D           1              /* preorder directory */
 230 # define FTS_DC          2              /* directory that causes cycles */
 231 # define FTS_DEFAULT     3              /* none of the above */
 232 # define FTS_DNR         4              /* unreadable directory */
 233 # define FTS_DOT         5              /* dot or dot-dot */
 234 # define FTS_DP          6              /* postorder directory */
 235 # define FTS_ERR         7              /* error; errno is set */
 236 # define FTS_F           8              /* regular file */
 237 # define FTS_INIT        9              /* initialized only */
 238 # define FTS_NS         10              /* stat(2) failed */
 239 # define FTS_NSOK       11              /* no stat(2) requested */
 240 # define FTS_SL         12              /* symbolic link */
 241 # define FTS_SLNONE     13              /* symbolic link without target */
 242 # define FTS_W          14              /* whiteout object */
 243         unsigned short int fts_info;    /* user flags for FTSENT structure */
 244
 245 # define FTS_DONTCHDIR   0x01           /* don't chdir .. to the parent */
 246 # define FTS_SYMFOLLOW   0x02           /* followed a symlink to get here */
 247         unsigned short int fts_flags;   /* private flags for FTSENT structure */
 248
 249 # define FTS_AGAIN       1              /* read node again */
 250 # define FTS_FOLLOW      2              /* follow symbolic link */
 251 # define FTS_NOINSTR     3              /* no instructions */
 252 # define FTS_SKIP        4              /* discard node */
 253         unsigned short int fts_instr;   /* fts_set() instructions */
 254
 255         struct stat fts_statp[1];       /* stat(2) information */
 256         char fts_name[__FLEXIBLE_ARRAY_MEMBER]; /* file name */
 257 } FTSENT;
 258
 259 #ifndef __GNUC_PREREQ
 260 # if defined __GNUC__ && defined __GNUC_MINOR__
 261 #  define __GNUC_PREREQ(maj, min) \
 262          ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
 263 # else
 264 #  define __GNUC_PREREQ(maj, min) 0
 265 # endif
 266 #endif
 267
 268 #if __GNUC_PREREQ (3,4)
 269 # undef __attribute_warn_unused_result__
 270 # define __attribute_warn_unused_result__ \
 271    __attribute__ ((__warn_unused_result__))
 272 #else
 273 # define __attribute_warn_unused_result__ /* empty */
 274 #endif
 275
 276 __BEGIN_DECLS
 277 FTSENT  *fts_children (FTS *, int) __THROW __attribute_warn_unused_result__;
 278 int      fts_close (FTS *) __THROW __attribute_warn_unused_result__;
 279 FTS     *fts_open (char * const *, int,
 280                    int (*)(const FTSENT **, const FTSENT **))
 281   __THROW __attribute_warn_unused_result__;
 282 FTSENT  *fts_read (FTS *) __THROW __attribute_warn_unused_result__;
 283 int      fts_set (FTS *, FTSENT *, int) __THROW;
 284 __END_DECLS
 285
 286 #endif /* fts.h */