* Copyright (c) 1990 The Regents of the University of California.
* %sccs.include.redist.c%
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)fts.c 5.10 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
FTSENT
*fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root();
* Special case a root of "/" so that slashes aren't appended causing
* paths to be written as "//foo".
(p->fts_level == ROOTLEVEL && p->fts_pathlen == 1 && \
p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
#define CHDIR(sp, path) (!(sp->fts_options & FTS_NOCHDIR) && chdir(path))
#define FCHDIR(sp, fd) (!(sp->fts_options & FTS_NOCHDIR) && fchdir(fd))
#define ROOTPARENTLEVEL -1
#define BCHILD 1 /* from ftschildren */
#define BREAD 2 /* from ftsread */
static FTS
*stream
; /* current stream pointer */
ftsopen(argv
, options
, compar
)
register FTSENT
*p
, *root
;
register int nitems
, maxlen
;
/* allocate/initialize the stream */
if (!(stream
= sp
= (FTS
*)malloc((u_int
)sizeof(FTS
))))
* logical walks turn on NOCHDIR; symbolic links are just too
sp
->fts_options
= options
;
if (options
& FTS_LOGICAL
)
sp
->fts_options
|= FTS_NOCHDIR
;
/* allocate/initialize root's parent */
if (!(parent
= fts_alloc("", 0)))
parent
->fts_level
= ROOTPARENTLEVEL
;
/* allocate/initialize root(s) */
for (root
= NULL
, nitems
= 0; *argv
; ++argv
, ++nitems
) {
if (!(p
= fts_root(*argv
)))
if (maxlen
< p
->fts_namelen
)
* if comparison routine supplied, traverse in sorted
* order; otherwise traverse in the order specified.
p
->fts_accpath
= p
->fts_name
;
if (!(options
& FTS_NOSTAT
))
p
->fts_info
= fts_stat(p
, 0);
p
->fts_level
= ROOTLEVEL
;
if (compar
&& nitems
> 1)
root
= fts_sort(root
, nitems
);
* allocate a dummy pointer and make ftsread think that we've just
* finished the node before the root(s); set p->fts_info to FTS_NS
* so that everything about the "current" node is ignored.
if (!(sp
->fts_cur
= fts_alloc("", 0)))
sp
->fts_cur
->fts_link
= root
;
sp
->fts_cur
->fts_info
= FTS_NS
;
/* start out with at least 1K+ of path space */
if (!fts_path(MAX(maxlen
, MAXPATHLEN
)))
* if using chdir(2), grab a file descriptor pointing to dot to insure
* that we can get back here; this could be avoided for some paths,
* but almost certainly not worth the effort. Slashes, symbolic links,
* and ".." are all fairly nasty problems. Note, if we can't get the
* descriptor we run anyway, just more slowly.
if (!(options
& FTS_NOCHDIR
) &&
(sp
->fts_sd
= open(".", O_RDONLY
, 0)) < 0)
sp
->fts_options
|= FTS_NOCHDIR
;
mem3
: (void)free((void *)sp
->fts_cur
);
(void)free((void *)parent
);
mem1
: (void)free((void *)sp
);
* load the stream structure for the next traversal; set the
* accpath field specially so the chdir gets done to the right
* place and the user can access the first node.
len
= p
->fts_pathlen
= p
->fts_namelen
;
bcopy(p
->fts_name
, stream
->fts_path
, len
+ 1);
if ((cp
= rindex(p
->fts_name
, '/')) && (cp
!= p
->fts_name
|| cp
[1])) {
bcopy(cp
, p
->fts_name
, len
+ 1);
p
->fts_accpath
= p
->fts_path
= stream
->fts_path
;
register FTSENT
*freep
, *p
;
* this still works if we haven't read anything -- the dummy
* structure points to the root list, so we step through to
* the end of the root list which has a valid parent pointer.
for (p
= sp
->fts_cur
; p
->fts_level
> ROOTPARENTLEVEL
;) {
p
= p
->fts_link
? p
->fts_link
: p
->fts_parent
;
(void)free((void *)freep
);
/* free up child linked list, sort array, path buffer */
fts_lfree(sp
->fts_child
);
(void)free((void *)sp
->fts_array
);
(void)free((char *)sp
->fts_path
);
* return to original directory, save errno if necessary;
* free up the directory buffer
if (!(sp
->fts_options
& FTS_NOCHDIR
)) {
saved_errno
= fchdir(sp
->fts_sd
) ? errno
: 0;
/* free up the stream pointer */
/* set errno and return */
if (!(sp
->fts_options
& FTS_NOCHDIR
) && saved_errno
) {
register FTSENT
*p
, *tmp
;
/* if finished or unrecoverable error, return NULL */
if (!sp
->fts_cur
|| sp
->fts_options
& FTS__STOP
)
/* set global stream pointer, and current node pointer */
/* save and zero out user instructions */
/* if used link pointer for cycle detection, restore it */
p
->fts_link
= sp
->fts_savelink
;
/* any type of file may be re-visited; re-stat and return */
if (instr
== FTS_AGAIN
) {
p
->fts_info
= fts_stat(p
, 0);
/* following a symbolic link */
if (p
->fts_info
== FTS_SL
&& instr
== FTS_FOLLOW
) {
p
->fts_info
= fts_stat(p
, 1);
/* directory in pre-order */
if (p
->fts_info
== FTS_D
) {
/* if skipped or crossed mount point, do post-order visit */
if (instr
== FTS_SKIP
|| sp
->fts_options
& FTS_XDEV
&&
p
->fts_statb
.st_dev
!= sp
->sdev
) {
fts_lfree(sp
->fts_child
);
/* read the directory if necessary, and return first entry */
if (CHDIR(sp
, p
->fts_accpath
)) {
fts_lfree(sp
->fts_child
);
cp
= sp
->fts_path
+ NAPPEND(p
->fts_parent
);
bcopy(p
->fts_name
, cp
, p
->fts_namelen
+ 1);
if (!(sp
->fts_child
= fts_build(sp
, BREAD
)))
/* move to next node on this level */
* if root level node, set up paths and return. If not the
* first time, and it's not an absolute pathname, get back
if (p
->fts_level
== ROOTLEVEL
) {
p
->fts_path
[0] != '/' && FCHDIR(sp
, sp
->fts_sd
)) {
/* should never happen... */
p
->fts_path
= "starting directory";
sp
->fts_options
|= FTS__STOP
;
p
->fts_info
= fts_stat(p
, 0);
sp
->sdev
= p
->fts_statb
.st_dev
;
/* user may have called ftsset on node */
if (p
->fts_instr
== FTS_SKIP
)
if (p
->fts_instr
== FTS_FOLLOW
) {
p
->fts_info
= fts_stat(p
, 1);
cp
= sp
->fts_path
+ NAPPEND(p
->fts_parent
);
bcopy(p
->fts_name
, cp
, p
->fts_namelen
+ 1);
/* check for directory cycles */
if (p
->fts_info
== FTS_D
&& (tmp
= fts_cycle(p
))) {
sp
->fts_savelink
= p
->fts_link
;
if (p
->fts_level
== ROOTPARENTLEVEL
) {
* done; free everything up and set errno to 0 so the user
* can distinguish between error and EOF.
return(sp
->fts_cur
= NULL
);
sp
->fts_path
[p
->fts_pathlen
] = '\0';
sp
->fts_options
|= FTS__STOP
;
* ftsset takes the stream as an argument although it's not used in this
* implementation; it would be necessary if anyone wanted to add global
* semantics to fts using ftsset. A possible error return is allowed for
* set errno to 0 so that user can tell the difference between an
* error and a directory without entries.
if (p
->fts_info
!= FTS_D
|| sp
->fts_options
& FTS__STOP
)
fts_lfree(sp
->fts_child
);
* if using chdir on a relative path and called BEFORE ftsread on the
* root of a traversal, we can lose because we need to chdir into the
* subdirectory, and we don't know where the current directory is to
* get back so that the upcoming chdir by ftsread will work.
if (p
->fts_level
!= ROOTLEVEL
|| p
->fts_accpath
[0] == '/' ||
sp
->fts_options
& FTS_NOCHDIR
)
return(sp
->fts_child
= fts_build(sp
, BCHILD
));
if ((fd
= open(".", O_RDONLY
, 0)) < 0)
sp
->fts_child
= fts_build(sp
, BCHILD
);
#define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
register struct dirent
*dp
;
register FTSENT
*p
, *head
;
int descend
, len
, level
, maxlen
, nlinks
, saved_errno
;
if (!(dirp
= opendir(p
->fts_accpath
))) {
* the real slowdown in walking the tree is the stat calls. If
* FTS_NOSTAT is set and it's a physical walk (so that symbolic
* links can't be directories), fts assumes that the number of
* subdirectories in a node is equal to the number of links to
* the parent. This allows stat calls to be skipped in any leaf
* directories and for any nodes after the directories in the
* parent node have been found. This empirically cuts the stat
sp
->fts_options
& FTS_NOSTAT
&& sp
->fts_options
& FTS_PHYSICAL
?
p
->fts_statb
.st_nlink
- (sp
->fts_options
& FTS_SEEDOT
? 0 : 2) : -1;
/* if told to descend or found links and not told not to descend. */
if (nlinks
|| type
== BREAD
) {
if (FCHDIR(sp
, dirfd(dirp
))) {
/* get max file name length that can be stored in current path */
maxlen
= sp
->fts_pathlen
- p
->fts_pathlen
- 1;
cp
= sp
->fts_path
+ (len
= NAPPEND(p
));
level
= p
->fts_level
+ 1;
/* read the directory, attching each new entry to the `link' pointer */
for (head
= NULL
, nitems
= 0; dp
= readdir(dirp
);) {
if (ISDOT(dp
->d_name
) && !(sp
->fts_options
& FTS_SEEDOT
))
if (!(p
= fts_alloc(dp
->d_name
, dp
->d_namlen
))) {
if (dp
->d_namlen
> maxlen
) {
if (!fts_path((int)dp
->d_namlen
)) {
/* quit: this stream no longer has a path */
sp
->fts_options
|= FTS__STOP
;
if (descend
&& CHDIR(sp
, "..")) {
sp
->fts_options
|= FTS__STOP
;
maxlen
= sp
->fts_pathlen
- sp
->fts_cur
->fts_pathlen
- 1;
p
->fts_pathlen
= len
+ dp
->d_namlen
+ 1;
sp
->fts_options
& FTS_NOCHDIR
? p
->fts_path
: p
->fts_name
;
p
->fts_parent
= sp
->fts_cur
;
/* make sure fts_stat has a filename to stat */
if (sp
->fts_options
& FTS_NOCHDIR
)
bcopy(p
->fts_name
, cp
, p
->fts_namelen
+ 1);
p
->fts_info
= fts_stat(p
, 0);
if (nlinks
> 0 && (p
->fts_info
== FTS_D
||
p
->fts_info
== FTS_DNR
|| p
->fts_info
== FTS_DNX
))
if (cp
- 1 > sp
->fts_path
)
* if descended: if were called from ftsread and didn't find anything,
* or were called from ftschildren, get back.
if (descend
&& (!nitems
|| type
== BCHILD
) && CHDIR(sp
, "..")) {
sp
->fts_options
|= FTS__STOP
;
if (sp
->fts_compar
&& nitems
> 1)
head
= fts_sort(head
, nitems
);
bcopy(head
->fts_name
, cp
+ 1, head
->fts_namelen
+ 1);
* detection of symbolic links w/o targets. If FTS_FOLLOW is set,
* the symlink structure is overwritten with the stat structure of
if (stream
->fts_options
& FTS_LOGICAL
|| symflag
) {
if (stat(p
->fts_accpath
, &p
->fts_statb
))
return(symflag
|| !lstat(p
->fts_accpath
,
&p
->fts_statb
) ? FTS_SLNONE
: FTS_ERR
);
} else if (lstat(p
->fts_accpath
, &p
->fts_statb
))
switch(p
->fts_statb
.st_mode
&S_IFMT
) {
* cycle detection is brute force; if the tree gets deep enough or
* the number of symbolic links to directories is really high
* something faster might be worthwhile.
dev
= p
->fts_statb
.st_dev
;
ino
= p
->fts_statb
.st_ino
;
for (p
= p
->fts_parent
; p
->fts_level
> ROOTLEVEL
; p
= p
->fts_parent
)
if (ino
== p
->fts_statb
.st_ino
&& dev
== p
->fts_statb
.st_dev
)
#define R(type, nelem, ptr) \
(type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
register FTSENT
**ap
, *p
;
* construct an array of pointers to the structures and call qsort(3).
* Reassemble the array in the order returned by qsort. If unable to
* sort for memory reasons, return the directory entries in their
* current order. Allocate enough space for the current needs plus
* 40 so we don't realloc one entry at a time.
if (nitems
> stream
->fts_nitems
) {
stream
->fts_nitems
= nitems
+ 40;
if (!(stream
->fts_array
=
R(FTSENT
*, stream
->fts_nitems
, stream
->fts_array
))) {
for (ap
= stream
->fts_array
, p
= head
; p
; p
= p
->fts_link
)
qsort((void *)stream
->fts_array
, nitems
, sizeof(FTSENT
*),
for (head
= *(ap
= stream
->fts_array
); --nitems
; ++ap
)
* variable sized structures; the name is the last element so
* allocate enough extra space after the structure to hold it.
if (!(p
= (FTSENT
*)malloc((size_t)(sizeof(FTSENT
) + len
))))
bcopy(name
, p
->fts_name
, len
+ 1);
p
->fts_path
= stream
->fts_path
;
p
->fts_local
.pointer
= NULL
;
* allow essentially unlimited paths; certain programs (find, remove, ls)
* need to work on any tree. Most systems will allow creation of paths
* much longer than MAXPATHLEN, even though the kernel won't resolve them.
* Add an extra 128 bytes to the requested size so that we don't realloc
* the path 2 bytes at a time.
stream
->fts_pathlen
+= size
+ 128;
return(stream
->fts_path
=
R(char, stream
->fts_pathlen
, stream
->fts_path
));
* rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what
* /a/b/ really is, they don't talk about what a null path component
* resolves to. This hopefully does what the user intended. Don't
for (cp
= name
; *cp
; ++cp
);
while (--cp
> name
&& *cp
== '/');
return(fts_alloc(name
, cp
- name
));