* Copyright (c) 1989 The Regents of the University of California.
* Redistribution and use in source and binary forms are permitted
* provided that the above copyright notice and this paragraph are
* duplicated in all such forms and that any documentation,
* advertising materials, and other materials related to such
* distribution and use acknowledge that the software was developed
* by the University of California, Berkeley. The name of the
* University may not be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)fts.c 5.1 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
FTSENT
*fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root();
char *malloc(), *realloc();
* Special case a root of "/" so that slashes aren't appended causing
* paths to be written as "//foo".
(p->level == ROOTLEVEL && p->pathlen == 1 && \
p->path[0] == '/' ? 0 : p->pathlen)
#define CHDIR(sp, path) (!(sp->options & FTS_NOCHDIR) && chdir(path))
#define ROOTPARENTLEVEL -1
static FTS
*stream
; /* current stream pointer */
ftsopen(argv
, options
, compar
)
register FTSENT
*p
, *root
;
register int nitems
, maxlen
;
char wd
[MAXPATHLEN
], *getwd(), *strdup();
/* allocate/initialize the stream */
if (!(stream
= sp
= (FTS
*)malloc((u_int
)sizeof(FTS
))))
/* allocate/initialize root's parent */
if (!(parent
= fts_alloc("", 0)))
parent
->level
= ROOTPARENTLEVEL
;
/* allocate/initialize root(s) */
if (options
& FTS_MULTIPLE
) {
for (root
= NULL
, nitems
= 0; *argv
; ++argv
, ++nitems
) {
if (!(p
= fts_root(*argv
)))
* if comparison routine supplied, traverse in sorted
* order; otherwise traverse in the order specified.
p
->info
= fts_stat(p
, 0);
if (compar
&& nitems
> 1)
root
= fts_sort(root
, nitems
);
if (!(root
= fts_root((char *)argv
)))
/* start out with at least 1K+ of path space */
if (!fts_path(MAX(maxlen
, MAXPATHLEN
)))
* some minor trickiness. Set the pointers so that ftsread thinks
* we've just finished the node before the root(s); set p->info to
* FTS_NS so that everything about the "current" node is ignored.
* Rather than allocate a dummy node use the root's parent's link
* pointer. This is handled specially in ftsclose() as well.
* if using chdir(2), do a getwd() to insure that we can get back
* here; this could be avoided for some paths, but probably not
* worth the effort. Slashes, symbolic links, and ".." are all
* fairly nasty problems. Note, if we can't get the current
* working directory we run anyway, just more slowly.
if (!(options
& FTS_NOCHDIR
) && (!getwd(wd
) || !(sp
->wd
= strdup(wd
))))
sp
->options
|= FTS_NOCHDIR
;
(void)free((char *)parent
);
mem1
: (void)free((char *)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
->pathlen
= p
->namelen
;
bcopy(p
->name
, stream
->path
, len
+ 1);
if ((cp
= rindex(p
->name
, '/')) && (cp
!= p
->name
|| cp
[1])) {
bcopy(cp
, p
->name
, len
+ 1);
p
->accpath
= p
->path
= stream
->path
;
register FTSENT
*freep
, *p
;
/* check for never having read anything */
if (sp
->cur
->level
== ROOTPARENTLEVEL
)
for (p
= sp
->cur
; p
->level
> ROOTPARENTLEVEL
;) {
p
= p
->link
? p
->link
: p
->parent
;
(void)free((char *)freep
);
/* free up child linked list, sort array, path buffer */
(void)free((char *)sp
->array
);
(void)free((char *)sp
->path
);
* return to original directory, save errno if necessary;
* free up the directory buffer
if (!(sp
->options
& FTS_NOCHDIR
)) {
saved_errno
= chdir(sp
->wd
) ? errno
: 0;
/* free up the stream pointer */
/* set errno and return */
if (!(sp
->options
& FTS_NOCHDIR
) && saved_errno
) {
/* if finished or unrecoverable error, return NULL */
if (!sp
->cur
|| sp
->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 */
/* any type of file may be re-visited; re-stat and return */
if (instr
== FTS_AGAIN
) {
p
->info
= fts_stat(p
, 0);
/* cd into child directory */
if (CHDIR(sp
, p
->accpath
)) {
sp
->options
|= FTS__STOP
;
} else if (!(sp
->child
= fts_build(sp
, 1)))
cp
= sp
->path
+ NAPPEND(p
->parent
);
bcopy(p
->name
, cp
, p
->namelen
+ 1);
else if (p
->info
== FTS_SL
&& instr
== FTS_FOLLOW
) {
p
->info
= fts_stat(p
, 1);
* user may have called ftsset on pointer returned by
* ftschildren; handle it here.
if (instr
== FTS_FOLLOW
) {
p
->info
= fts_stat(p
, 1);
/* go 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
* to wherever we started from.
if (p
->level
== ROOTLEVEL
) {
(void)free((char *)sp
->cur
);
if (p
->path
[0] != '/' && CHDIR(sp
, sp
->wd
)) {
/* return target path for error msg */
sp
->options
|= FTS__STOP
;
p
->info
= fts_stat(p
, 0);
(void)free((char *)sp
->cur
);
cp
= sp
->path
+ NAPPEND(p
->parent
);
bcopy(p
->name
, cp
, p
->namelen
+ 1);
if (p
->info
== FTS_D
&& (tmp
= fts_cycle(p
))) {
(void)free((char *)sp
->cur
);
if (p
->level
== ROOTPARENTLEVEL
) {
* done; free everything up and set errno to 0 so the user
* can distinguish between error and EOF.
sp
->path
[p
->pathlen
] = '\0';
sp
->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 (sp
->cur
->info
!= FTS_D
|| sp
->options
& FTS__STOP
)
if (sp
->child
= fts_build(sp
, 0)) {
* have to cd up so that the fields of the current node
* as returned from readfts will be correct.
sp
->options
|= FTS__STOP
;
#define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
fts_build(sp
, set_node_errors
)
register struct dirent
*dp
;
register FTSENT
*p
, *head
;
int len
, level
, maxlen
, nlinks
, saved_errno
;
if (!(dirp
= opendir(p
->accpath
))) {
if (CHDIR(sp
, p
->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
nlinks
= sp
->options
& FTS_NOSTAT
&& sp
->options
& FTS_PHYSICAL
?
p
->statb
.st_nlink
- (sp
->options
& FTS_SEEDOT
? 0 : 2) : -1;
/* get max file name length that can be stored in current path */
maxlen
= sp
->pathlen
- p
->pathlen
- 1;
cp
= sp
->path
+ (len
= NAPPEND(p
));
/* 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
->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
->options
|= FTS__STOP
;
sp
->options
|= FTS__STOP
;
maxlen
= sp
->pathlen
- sp
->cur
->pathlen
- 1;
p
->pathlen
= len
+ dp
->d_namlen
+ 1;
p
->accpath
= sp
->options
& FTS_NOCHDIR
? p
->path
: p
->name
;
/* make sure fts_stat has a filename to stat */
if (sp
->options
& FTS_NOCHDIR
)
bcopy(p
->name
, cp
, p
->namelen
+ 1);
p
->info
= fts_stat(p
, 0);
if (nlinks
> 0 && (p
->info
== FTS_D
||
p
->info
== FTS_DNR
|| p
->info
== FTS_DNX
))
sp
->options
|= FTS__STOP
;
} else if (set_node_errors
)
if (sp
->compar
&& nitems
> 1)
head
= fts_sort(head
, nitems
);
bcopy(head
->name
, cp
, head
->namelen
+ 1);
register int ngroups
, *gp
;
* detection of symbolic links w/o targets. If FTS_FOLLOW is set,
* the symlink structure is overwritten with the stat structure of
if (stream
->options
& FTS_LOGICAL
|| symflag
) {
if (stat(p
->accpath
, &p
->statb
))
return(symflag
|| !lstat(p
->accpath
, &p
->statb
) ?
} else if (lstat(p
->accpath
, &p
->statb
))
switch(p
->statb
.st_mode
&S_IFMT
) {
/* get new uid/groups each time, they may have changed */
if (getuid() == p
->statb
.st_uid
) {
if (!(p
->statb
.st_mode
&S_IRUSR
))
if (!(p
->statb
.st_mode
&S_IXUSR
))
if ((ngroups
= getgroups(NGROUPS
, gidset
)) == -1)
for (gp
= gidset
; ngroups
--;)
if (*gp
++ == p
->statb
.st_gid
) {
if (!(p
->statb
.st_mode
&S_IRGRP
))
if (!(p
->statb
.st_mode
&S_IXGRP
))
if (!(p
->statb
.st_mode
&S_IROTH
))
if (!(p
->statb
.st_mode
&S_IXOTH
))
* 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.
for (p
= p
->parent
; p
->level
> ROOTLEVEL
; p
= p
->parent
)
if (ino
== p
->statb
.st_ino
&& dev
== p
->statb
.st_dev
)
#define R(type, nelem, ptr) \
(type *)realloc((char *)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
->nitems
) {
stream
->nitems
= nitems
+ 40;
R(FTSENT
*, stream
->nitems
, stream
->array
))) {
for (ap
= stream
->array
, p
= head
; p
; p
= p
->link
)
qsort((char *)stream
->array
, nitems
, sizeof(FTSENT
*), stream
->compar
);
for (head
= *(ap
= stream
->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((u_int
)(sizeof(FTSENT
) + len
))))
bcopy(name
, p
->name
, len
+ 1);
* 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
->pathlen
+= size
+ 128;
return((int)(stream
->path
= R(char, stream
->pathlen
, stream
->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
));