lib/fts_.h

   1 /* Traverse a file hierarchy.
   2
   3    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /*
  20  * Copyright (c) 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         size_t fts_pathlen;             /* sizeof(path) */
  77         size_t fts_nitems;                      /* elements in the sort array */
  78         int (*fts_compar) (struct _ftsent const **, struct _ftsent const **);
  79                                         /* compare fn */
  80
  81 # define FTS_COMFOLLOW  0x0001          /* follow command line symlinks */
  82 # define FTS_LOGICAL    0x0002          /* logical walk */
  83 # define FTS_NOCHDIR    0x0004          /* don't change directories */
  84 # define FTS_NOSTAT     0x0008          /* don't get stat info */
  85 # define FTS_PHYSICAL   0x0010          /* physical walk */
  86 # define FTS_SEEDOT     0x0020          /* return dot and dot-dot */
  87 # define FTS_XDEV       0x0040          /* don't cross devices */
  88 # define FTS_WHITEOUT   0x0080          /* return whiteout information */
  89
  90   /* There are two ways to detect cycles.
  91      The lazy way (which works only with FTS_PHYSICAL),
  92      with which one may process a directory that is a
  93      part of the cycle several times before detecting the cycle.
  94      The `tight' way, whereby fts uses more memory (proportional
  95      to number of `active' directories, aka distance from root
  96      of current tree to current directory -- see active_dir_ht)
  97      to detect any cycle right away.  For example, du must use
  98      this option to avoid counting disk space in a cycle multiple
  99      times, but chown -R need not.
 100      The default is to use the constant-memory lazy way, when possible
 101      (see below).
 102
 103      However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
 104      using lazy cycle detection is inadequate.  For example, traversing
 105      a directory containing a symbolic link to a peer directory, it is
 106      possible to encounter the same directory twice even though there
 107      is no cycle:
 108      dir
 109      ...
 110      slink -> dir
 111      So, when FTS_LOGICAL is selected, we have to use a different
 112      mode of cycle detection: FTS_TIGHT_CYCLE_CHECK.  */
 113 # define FTS_TIGHT_CYCLE_CHECK  0x0100
 114
 115 # define FTS_OPTIONMASK 0x01ff          /* valid user option mask */
 116
 117 # define FTS_NAMEONLY   0x1000          /* (private) child names only */
 118 # define FTS_STOP       0x2000          /* (private) unrecoverable error */
 119         int fts_options;                /* fts_open options, global flags */
 120
 121 # if !_LGPL_PACKAGE
 122         union {
 123                 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
 124                    specified.  It records the directories between a starting
 125                    point and the current directory.  I.e., a directory is
 126                    recorded here IFF we have visited it once, but we have not
 127                    yet completed processing of all its entries.  Every time we
 128                    visit a new directory, we add that directory to this set.
 129                    When we finish with a directory (usually by visiting it a
 130                    second time), we remove it from this set.  Each entry in
 131                    this data structure is a device/inode pair.  This data
 132                    structure is used to detect directory cycles efficiently and
 133                    promptly even when the depth of a hierarchy is in the tens
 134                    of thousands.  */
 135                 struct hash_table *ht;
 136
 137                 /* This data structure uses lazy checking, as done by rm via
 138                    cycle-check.c.  It's the default, but it's not appropriate
 139                    for programs like du.  */
 140                 struct cycle_check_state *state;
 141         } fts_cycle;
 142 # endif
 143 } FTS;
 144
 145 typedef struct _ftsent {
 146         struct _ftsent *fts_cycle;      /* cycle node */
 147         struct _ftsent *fts_parent;     /* parent directory */
 148         struct _ftsent *fts_link;       /* next file in directory */
 149         long fts_number;                /* local numeric value */
 150         void *fts_pointer;              /* local address value */
 151         char *fts_accpath;              /* access file name */
 152         char *fts_path;                 /* root name; == fts_fts->fts_path */
 153         int fts_errno;                  /* errno for this node */
 154         int fts_symfd;                  /* fd for symlink */
 155         size_t fts_pathlen;             /* strlen(fts_path) */
 156
 157         FTS *fts_fts;                   /* the file hierarchy itself */
 158
 159 # define FTS_ROOTPARENTLEVEL    (-1)
 160 # define FTS_ROOTLEVEL           0
 161         ptrdiff_t fts_level;            /* depth (-1 to N) */
 162
 163         size_t fts_namelen;             /* strlen(fts_name) */
 164
 165 # define FTS_D           1              /* preorder directory */
 166 # define FTS_DC          2              /* directory that causes cycles */
 167 # define FTS_DEFAULT     3              /* none of the above */
 168 # define FTS_DNR         4              /* unreadable directory */
 169 # define FTS_DOT         5              /* dot or dot-dot */
 170 # define FTS_DP          6              /* postorder directory */
 171 # define FTS_ERR         7              /* error; errno is set */
 172 # define FTS_F           8              /* regular file */
 173 # define FTS_INIT        9              /* initialized only */
 174 # define FTS_NS         10              /* stat(2) failed */
 175 # define FTS_NSOK       11              /* no stat(2) requested */
 176 # define FTS_SL         12              /* symbolic link */
 177 # define FTS_SLNONE     13              /* symbolic link without target */
 178 # define FTS_W          14              /* whiteout object */
 179         unsigned short int fts_info;    /* user flags for FTSENT structure */
 180
 181 # define FTS_DONTCHDIR   0x01           /* don't chdir .. to the parent */
 182 # define FTS_SYMFOLLOW   0x02           /* followed a symlink to get here */
 183         unsigned short int fts_flags;   /* private flags for FTSENT structure */
 184
 185 # define FTS_AGAIN       1              /* read node again */
 186 # define FTS_FOLLOW      2              /* follow symbolic link */
 187 # define FTS_NOINSTR     3              /* no instructions */
 188 # define FTS_SKIP        4              /* discard node */
 189         unsigned short int fts_instr;   /* fts_set() instructions */
 190
 191         struct stat fts_statp[1];       /* stat(2) information */
 192         char fts_name[1];               /* file name */
 193 } FTSENT;
 194
 195 __BEGIN_DECLS
 196 FTSENT  *fts_children (FTS *, int) __THROW;
 197 int      fts_close (FTS *) __THROW;
 198 FTS     *fts_open (char * const *, int,
 199                    int (*)(const FTSENT **, const FTSENT **)) __THROW;
 200 FTSENT  *fts_read (FTS *) __THROW;
 201 int      fts_set (FTS *, FTSENT *, int) __THROW;
 202 __END_DECLS
 203
 204 #endif /* fts.h */