lib/fts_.h

   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) 1989, 1993
  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  *      @(#)fts.h       8.3 (Berkeley) 8/14/94
  48  */
  49
  50 #ifndef _FTS_H
  51 # define _FTS_H 1
  52
  53 # ifdef _LIBC
  54 #  include <features.h>
  55 #  define _LGPL_PACKAGE 1
  56 # else
  57 #  undef __THROW
  58 #  define __THROW
  59 #  undef __BEGIN_DECLS
  60 #  define __BEGIN_DECLS
  61 #  undef __END_DECLS
  62 #  define __END_DECLS
  63 # endif
  64
  65 # include <stddef.h>
  66 # include <sys/types.h>
  67 # include <sys/stat.h>
  68
  69 typedef struct {
  70         struct _ftsent *fts_cur;        /* current node */
  71         struct _ftsent *fts_child;      /* linked list of children */
  72         struct _ftsent **fts_array;     /* sort array */
  73         dev_t fts_dev;                  /* starting device # */
  74         char *fts_path;                 /* file name for this descent */
  75         int fts_rfd;                    /* fd for root */
  76         int fts_cwd_fd;                 /* the file descriptor on which the
  77                                            virtual cwd is open, or AT_FDCWD */
  78         size_t fts_pathlen;             /* sizeof(path) */
  79         size_t fts_nitems;              /* elements in the sort array */
  80         int (*fts_compar) (struct _ftsent const **, struct _ftsent const **);
  81                                         /* compare fn */
  82
  83 # define FTS_COMFOLLOW  0x0001          /* follow command line symlinks */
  84 # define FTS_LOGICAL    0x0002          /* logical walk */
  85 # define FTS_NOCHDIR    0x0004          /* don't change directories */
  86 # define FTS_NOSTAT     0x0008          /* don't get stat info */
  87 # define FTS_PHYSICAL   0x0010          /* physical walk */
  88 # define FTS_SEEDOT     0x0020          /* return dot and dot-dot */
  89 # define FTS_XDEV       0x0040          /* don't cross devices */
  90 # define FTS_WHITEOUT   0x0080          /* return whiteout information */
  91
  92   /* There are two ways to detect cycles.
  93      The lazy way (which works only with FTS_PHYSICAL),
  94      with which one may process a directory that is a
  95      part of the cycle several times before detecting the cycle.
  96      The `tight' way, whereby fts uses more memory (proportional
  97      to number of `active' directories, aka distance from root
  98      of current tree to current directory -- see active_dir_ht)
  99      to detect any cycle right away.  For example, du must use
 100      this option to avoid counting disk space in a cycle multiple
 101      times, but chown -R need not.
 102      The default is to use the constant-memory lazy way, when possible
 103      (see below).
 104
 105      However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
 106      using lazy cycle detection is inadequate.  For example, traversing
 107      a directory containing a symbolic link to a peer directory, it is
 108      possible to encounter the same directory twice even though there
 109      is no cycle:
 110      dir
 111      ...
 112      slink -> dir
 113      So, when FTS_LOGICAL is selected, we have to use a different
 114      mode of cycle detection: FTS_TIGHT_CYCLE_CHECK.  */
 115 # define FTS_TIGHT_CYCLE_CHECK  0x0100
 116
 117   /* Use this flag to enable semantics with which the parent
 118      application may be made both more efficient and more robust.
 119      Whereas the default is to visit each directory in a recursive
 120      traversal (via chdir), using this flag makes it so the initial
 121      working directory is never changed.  Instead, these functions
 122      perform the traversal via a virtual working directory, maintained
 123      through the file descriptor member, fts_cwd_fd.  */
 124 # define FTS_CWDFD              0x0200
 125
 126 # define FTS_OPTIONMASK 0x03ff          /* valid user option mask */
 127
 128 # define FTS_NAMEONLY   0x1000          /* (private) child names only */
 129 # define FTS_STOP       0x2000          /* (private) unrecoverable error */
 130         int fts_options;                /* fts_open options, global flags */
 131
 132 # if !_LGPL_PACKAGE
 133         union {
 134                 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
 135                    specified.  It records the directories between a starting
 136                    point and the current directory.  I.e., a directory is
 137                    recorded here IFF we have visited it once, but we have not
 138                    yet completed processing of all its entries.  Every time we
 139                    visit a new directory, we add that directory to this set.
 140                    When we finish with a directory (usually by visiting it a
 141                    second time), we remove it from this set.  Each entry in
 142                    this data structure is a device/inode pair.  This data
 143                    structure is used to detect directory cycles efficiently and
 144                    promptly even when the depth of a hierarchy is in the tens
 145                    of thousands.  */
 146                 struct hash_table *ht;
 147
 148                 /* FIXME: rename these two members to have the fts_ prefix */
 149                 /* This data structure uses a lazy cycle-detection algorithm,
 150                    as done by rm via cycle-check.c.  It's the default,
 151                    but it's not appropriate for programs like du.  */
 152                 struct cycle_check_state *state;
 153         } fts_cycle;
 154 # endif
 155 } FTS;
 156
 157 typedef struct _ftsent {
 158         struct _ftsent *fts_cycle;      /* cycle node */
 159         struct _ftsent *fts_parent;     /* parent directory */
 160         struct _ftsent *fts_link;       /* next file in directory */
 161         long fts_number;                /* local numeric value */
 162         void *fts_pointer;              /* local address value */
 163         char *fts_accpath;              /* access file name */
 164         char *fts_path;                 /* root name; == fts_fts->fts_path */
 165         int fts_errno;                  /* errno for this node */
 166         int fts_symfd;                  /* fd for symlink */
 167         size_t fts_pathlen;             /* strlen(fts_path) */
 168
 169         FTS *fts_fts;                   /* the file hierarchy itself */
 170
 171 # define FTS_ROOTPARENTLEVEL    (-1)
 172 # define FTS_ROOTLEVEL           0
 173         ptrdiff_t fts_level;            /* depth (-1 to N) */
 174
 175         size_t fts_namelen;             /* strlen(fts_name) */
 176
 177 # define FTS_D           1              /* preorder directory */
 178 # define FTS_DC          2              /* directory that causes cycles */
 179 # define FTS_DEFAULT     3              /* none of the above */
 180 # define FTS_DNR         4              /* unreadable directory */
 181 # define FTS_DOT         5              /* dot or dot-dot */
 182 # define FTS_DP          6              /* postorder directory */
 183 # define FTS_ERR         7              /* error; errno is set */
 184 # define FTS_F           8              /* regular file */
 185 # define FTS_INIT        9              /* initialized only */
 186 # define FTS_NS         10              /* stat(2) failed */
 187 # define FTS_NSOK       11              /* no stat(2) requested */
 188 # define FTS_SL         12              /* symbolic link */
 189 # define FTS_SLNONE     13              /* symbolic link without target */
 190 # define FTS_W          14              /* whiteout object */
 191         unsigned short int fts_info;    /* user flags for FTSENT structure */
 192
 193 # define FTS_DONTCHDIR   0x01           /* don't chdir .. to the parent */
 194 # define FTS_SYMFOLLOW   0x02           /* followed a symlink to get here */
 195         unsigned short int fts_flags;   /* private flags for FTSENT structure */
 196
 197 # define FTS_AGAIN       1              /* read node again */
 198 # define FTS_FOLLOW      2              /* follow symbolic link */
 199 # define FTS_NOINSTR     3              /* no instructions */
 200 # define FTS_SKIP        4              /* discard node */
 201         unsigned short int fts_instr;   /* fts_set() instructions */
 202
 203         struct stat fts_statp[1];       /* stat(2) information */
 204         char fts_name[1];               /* file name */
 205 } FTSENT;
 206
 207 __BEGIN_DECLS
 208 FTSENT  *fts_children (FTS *, int) __THROW;
 209 int      fts_close (FTS *) __THROW;
 210 FTS     *fts_open (char * const *, int,
 211                    int (*)(const FTSENT **, const FTSENT **)) __THROW;
 212 FTSENT  *fts_read (FTS *) __THROW;
 213 int      fts_set (FTS *, FTSENT *, int) __THROW;
 214 __END_DECLS
 215
 216 #endif /* fts.h */