fts-compat.c revision 103726
11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * Redistribution and use in source and binary forms, with or without 61573Srgrimes * modification, are permitted provided that the following conditions 71573Srgrimes * are met: 81573Srgrimes * 1. Redistributions of source code must retain the above copyright 91573Srgrimes * notice, this list of conditions and the following disclaimer. 101573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111573Srgrimes * notice, this list of conditions and the following disclaimer in the 121573Srgrimes * documentation and/or other materials provided with the distribution. 131573Srgrimes * 3. All advertising materials mentioning features or use of this software 141573Srgrimes * must display the following acknowledgement: 151573Srgrimes * This product includes software developed by the University of 161573Srgrimes * California, Berkeley and its contributors. 171573Srgrimes * 4. Neither the name of the University nor the names of its contributors 181573Srgrimes * may be used to endorse or promote products derived from this software 191573Srgrimes * without specific prior written permission. 201573Srgrimes * 211573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311573Srgrimes * SUCH DAMAGE. 3254770Sgreen * 3354770Sgreen * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $ 341573Srgrimes */ 351573Srgrimes 361573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3723668Speterstatic char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; 381573Srgrimes#endif /* LIBC_SCCS and not lint */ 3990045Sobrien#include <sys/cdefs.h> 4090045Sobrien__FBSDID("$FreeBSD: head/lib/libc/gen/fts-compat.c 103726 2002-09-21 01:28:41Z wollman $"); 411573Srgrimes 4271579Sdeischen#include "namespace.h" 4377497Skris#include <sys/types.h> 441573Srgrimes#include <sys/param.h> 451573Srgrimes#include <sys/stat.h> 461573Srgrimes 471573Srgrimes#include <dirent.h> 481573Srgrimes#include <errno.h> 491573Srgrimes#include <fcntl.h> 501573Srgrimes#include <fts.h> 511573Srgrimes#include <stdlib.h> 521573Srgrimes#include <string.h> 531573Srgrimes#include <unistd.h> 5471579Sdeischen#include "un-namespace.h" 551573Srgrimes 5690045Sobrienstatic FTSENT *fts_alloc(FTS *, char *, int); 5790045Sobrienstatic FTSENT *fts_build(FTS *, int); 5890045Sobrienstatic void fts_lfree(FTSENT *); 5990045Sobrienstatic void fts_load(FTS *, FTSENT *); 6090045Sobrienstatic size_t fts_maxarglen(char * const *); 6190045Sobrienstatic void fts_padjust(FTS *, FTSENT *); 6290045Sobrienstatic int fts_palloc(FTS *, size_t); 6390045Sobrienstatic FTSENT *fts_sort(FTS *, FTSENT *, int); 6490045Sobrienstatic u_short fts_stat(FTS *, FTSENT *, int); 6590045Sobrienstatic int fts_safe_changedir(FTS *, FTSENT *, int, char *); 661573Srgrimes 6728913Simp#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 681573Srgrimes 6928913Simp#define CLR(opt) (sp->fts_options &= ~(opt)) 7028913Simp#define ISSET(opt) (sp->fts_options & (opt)) 7128913Simp#define SET(opt) (sp->fts_options |= (opt)) 721573Srgrimes 731573Srgrimes#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 741573Srgrimes 751573Srgrimes/* fts_build flags */ 761573Srgrimes#define BCHILD 1 /* fts_children */ 771573Srgrimes#define BNAMES 2 /* fts_children, names only */ 781573Srgrimes#define BREAD 3 /* fts_read */ 791573Srgrimes 801573SrgrimesFTS * 811573Srgrimesfts_open(argv, options, compar) 821573Srgrimes char * const *argv; 8390045Sobrien int options; 84103726Swollman int (*compar)(const FTSENT * const *, const FTSENT * const *); 851573Srgrimes{ 8690045Sobrien FTS *sp; 8790045Sobrien FTSENT *p, *root; 8890045Sobrien int nitems; 891573Srgrimes FTSENT *parent, *tmp; 901573Srgrimes int len; 911573Srgrimes 921573Srgrimes /* Options check. */ 931573Srgrimes if (options & ~FTS_OPTIONMASK) { 941573Srgrimes errno = EINVAL; 951573Srgrimes return (NULL); 961573Srgrimes } 971573Srgrimes 981573Srgrimes /* Allocate/initialize the stream */ 99103726Swollman if ((sp = malloc(sizeof(FTS))) == NULL) 1001573Srgrimes return (NULL); 1011573Srgrimes memset(sp, 0, sizeof(FTS)); 1021573Srgrimes sp->fts_compar = compar; 1031573Srgrimes sp->fts_options = options; 1041573Srgrimes 10554770Sgreen /* Shush, GCC. */ 10654770Sgreen tmp = NULL; 10754770Sgreen 1081573Srgrimes /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 1091573Srgrimes if (ISSET(FTS_LOGICAL)) 1101573Srgrimes SET(FTS_NOCHDIR); 1111573Srgrimes 1121573Srgrimes /* 1131573Srgrimes * Start out with 1K of path space, and enough, in any case, 1141573Srgrimes * to hold the user's paths. 1151573Srgrimes */ 1161573Srgrimes if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 1171573Srgrimes goto mem1; 1181573Srgrimes 1191573Srgrimes /* Allocate/initialize root's parent. */ 1201573Srgrimes if ((parent = fts_alloc(sp, "", 0)) == NULL) 1211573Srgrimes goto mem2; 1221573Srgrimes parent->fts_level = FTS_ROOTPARENTLEVEL; 1231573Srgrimes 1241573Srgrimes /* Allocate/initialize root(s). */ 12564740Sgreen for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { 1261573Srgrimes /* Don't allow zero-length paths. */ 1271573Srgrimes if ((len = strlen(*argv)) == 0) { 1281573Srgrimes errno = ENOENT; 1291573Srgrimes goto mem3; 1301573Srgrimes } 1311573Srgrimes 1321573Srgrimes p = fts_alloc(sp, *argv, len); 1331573Srgrimes p->fts_level = FTS_ROOTLEVEL; 1341573Srgrimes p->fts_parent = parent; 1351573Srgrimes p->fts_accpath = p->fts_name; 1361573Srgrimes p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 1371573Srgrimes 1381573Srgrimes /* Command-line "." and ".." are real directories. */ 1391573Srgrimes if (p->fts_info == FTS_DOT) 1401573Srgrimes p->fts_info = FTS_D; 1411573Srgrimes 1421573Srgrimes /* 1431573Srgrimes * If comparison routine supplied, traverse in sorted 1441573Srgrimes * order; otherwise traverse in the order specified. 1451573Srgrimes */ 1461573Srgrimes if (compar) { 1471573Srgrimes p->fts_link = root; 1481573Srgrimes root = p; 1491573Srgrimes } else { 1501573Srgrimes p->fts_link = NULL; 1511573Srgrimes if (root == NULL) 1521573Srgrimes tmp = root = p; 1531573Srgrimes else { 1541573Srgrimes tmp->fts_link = p; 1551573Srgrimes tmp = p; 1561573Srgrimes } 1571573Srgrimes } 1581573Srgrimes } 1591573Srgrimes if (compar && nitems > 1) 1601573Srgrimes root = fts_sort(sp, root, nitems); 1611573Srgrimes 1621573Srgrimes /* 1631573Srgrimes * Allocate a dummy pointer and make fts_read think that we've just 1641573Srgrimes * finished the node before the root(s); set p->fts_info to FTS_INIT 1651573Srgrimes * so that everything about the "current" node is ignored. 1661573Srgrimes */ 1671573Srgrimes if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 1681573Srgrimes goto mem3; 1691573Srgrimes sp->fts_cur->fts_link = root; 1701573Srgrimes sp->fts_cur->fts_info = FTS_INIT; 1711573Srgrimes 1721573Srgrimes /* 17354770Sgreen * If using chdir(2), grab a file descriptor pointing to dot to ensure 1741573Srgrimes * that we can get back here; this could be avoided for some paths, 1751573Srgrimes * but almost certainly not worth the effort. Slashes, symbolic links, 1761573Srgrimes * and ".." are all fairly nasty problems. Note, if we can't get the 1771573Srgrimes * descriptor we run anyway, just more slowly. 1781573Srgrimes */ 17956698Sjasone if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = _open(".", O_RDONLY, 0)) < 0) 1801573Srgrimes SET(FTS_NOCHDIR); 1811573Srgrimes 1821573Srgrimes return (sp); 1831573Srgrimes 1841573Srgrimesmem3: fts_lfree(root); 1851573Srgrimes free(parent); 1861573Srgrimesmem2: free(sp->fts_path); 1871573Srgrimesmem1: free(sp); 1881573Srgrimes return (NULL); 1891573Srgrimes} 1901573Srgrimes 1911573Srgrimesstatic void 1921573Srgrimesfts_load(sp, p) 1931573Srgrimes FTS *sp; 19490045Sobrien FTSENT *p; 1951573Srgrimes{ 19690045Sobrien int len; 19790045Sobrien char *cp; 1981573Srgrimes 1991573Srgrimes /* 2001573Srgrimes * Load the stream structure for the next traversal. Since we don't 2011573Srgrimes * actually enter the directory until after the preorder visit, set 2021573Srgrimes * the fts_accpath field specially so the chdir gets done to the right 2031573Srgrimes * place and the user can access the first node. From fts_open it's 2041573Srgrimes * known that the path will fit. 2051573Srgrimes */ 2061573Srgrimes len = p->fts_pathlen = p->fts_namelen; 2071573Srgrimes memmove(sp->fts_path, p->fts_name, len + 1); 2081573Srgrimes if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 2091573Srgrimes len = strlen(++cp); 2101573Srgrimes memmove(p->fts_name, cp, len + 1); 2111573Srgrimes p->fts_namelen = len; 2121573Srgrimes } 2131573Srgrimes p->fts_accpath = p->fts_path = sp->fts_path; 2141573Srgrimes sp->fts_dev = p->fts_dev; 2151573Srgrimes} 2161573Srgrimes 2171573Srgrimesint 2181573Srgrimesfts_close(sp) 2191573Srgrimes FTS *sp; 2201573Srgrimes{ 22190045Sobrien FTSENT *freep, *p; 2221573Srgrimes int saved_errno; 2231573Srgrimes 2241573Srgrimes /* 2251573Srgrimes * This still works if we haven't read anything -- the dummy structure 2261573Srgrimes * points to the root list, so we step through to the end of the root 2271573Srgrimes * list which has a valid parent pointer. 2281573Srgrimes */ 2291573Srgrimes if (sp->fts_cur) { 2301573Srgrimes for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 2311573Srgrimes freep = p; 23264740Sgreen p = p->fts_link != NULL ? p->fts_link : p->fts_parent; 2331573Srgrimes free(freep); 2341573Srgrimes } 2351573Srgrimes free(p); 2361573Srgrimes } 2371573Srgrimes 2381573Srgrimes /* Free up child linked list, sort array, path buffer. */ 2391573Srgrimes if (sp->fts_child) 2401573Srgrimes fts_lfree(sp->fts_child); 2411573Srgrimes if (sp->fts_array) 2421573Srgrimes free(sp->fts_array); 2431573Srgrimes free(sp->fts_path); 2441573Srgrimes 2451573Srgrimes /* Return to original directory, save errno if necessary. */ 2461573Srgrimes if (!ISSET(FTS_NOCHDIR)) { 2471573Srgrimes saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 24856698Sjasone (void)_close(sp->fts_rfd); 24954770Sgreen 25054770Sgreen /* Set errno and return. */ 25154770Sgreen if (saved_errno != 0) { 25254770Sgreen /* Free up the stream pointer. */ 25354770Sgreen free(sp); 25454770Sgreen errno = saved_errno; 25554770Sgreen return (-1); 25654770Sgreen } 2571573Srgrimes } 2581573Srgrimes 25937349Sphk /* Free up the stream pointer. */ 26037349Sphk free(sp); 2611573Srgrimes return (0); 2621573Srgrimes} 2631573Srgrimes 2641573Srgrimes/* 26528913Simp * Special case of "/" at the end of the path so that slashes aren't 26628913Simp * appended which would cause paths to be written as "....//foo". 2671573Srgrimes */ 2681573Srgrimes#define NAPPEND(p) \ 26928913Simp (p->fts_path[p->fts_pathlen - 1] == '/' \ 27028913Simp ? p->fts_pathlen - 1 : p->fts_pathlen) 2711573Srgrimes 2721573SrgrimesFTSENT * 2731573Srgrimesfts_read(sp) 27490045Sobrien FTS *sp; 2751573Srgrimes{ 27677599Skris struct stat sb; 27790045Sobrien FTSENT *p, *tmp; 27890045Sobrien int instr; 27990045Sobrien char *t; 2801573Srgrimes int saved_errno; 2811573Srgrimes 2821573Srgrimes /* If finished or unrecoverable error, return NULL. */ 2831573Srgrimes if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 2841573Srgrimes return (NULL); 2851573Srgrimes 2861573Srgrimes /* Set current node pointer. */ 2871573Srgrimes p = sp->fts_cur; 2881573Srgrimes 2891573Srgrimes /* Save and zero out user instructions. */ 2901573Srgrimes instr = p->fts_instr; 2911573Srgrimes p->fts_instr = FTS_NOINSTR; 2921573Srgrimes 2931573Srgrimes /* Any type of file may be re-visited; re-stat and re-turn. */ 2941573Srgrimes if (instr == FTS_AGAIN) { 2951573Srgrimes p->fts_info = fts_stat(sp, p, 0); 2961573Srgrimes return (p); 2971573Srgrimes } 2981573Srgrimes 2991573Srgrimes /* 3001573Srgrimes * Following a symlink -- SLNONE test allows application to see 3011573Srgrimes * SLNONE and recover. If indirecting through a symlink, have 3021573Srgrimes * keep a pointer to current location. If unable to get that 3031573Srgrimes * pointer, follow fails. 3041573Srgrimes */ 3051573Srgrimes if (instr == FTS_FOLLOW && 3061573Srgrimes (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 3071573Srgrimes p->fts_info = fts_stat(sp, p, 1); 30854770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 30956698Sjasone if ((p->fts_symfd = _open(".", O_RDONLY, 0)) < 0) { 3101573Srgrimes p->fts_errno = errno; 3111573Srgrimes p->fts_info = FTS_ERR; 3121573Srgrimes } else 3131573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 31454770Sgreen } 3151573Srgrimes return (p); 3161573Srgrimes } 3171573Srgrimes 3181573Srgrimes /* Directory in pre-order. */ 3191573Srgrimes if (p->fts_info == FTS_D) { 3201573Srgrimes /* If skipped or crossed mount point, do post-order visit. */ 3211573Srgrimes if (instr == FTS_SKIP || 32228913Simp (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 3231573Srgrimes if (p->fts_flags & FTS_SYMFOLLOW) 32456698Sjasone (void)_close(p->fts_symfd); 3251573Srgrimes if (sp->fts_child) { 3261573Srgrimes fts_lfree(sp->fts_child); 3271573Srgrimes sp->fts_child = NULL; 3281573Srgrimes } 3291573Srgrimes p->fts_info = FTS_DP; 3301573Srgrimes return (p); 3318870Srgrimes } 3321573Srgrimes 3331573Srgrimes /* Rebuild if only read the names and now traversing. */ 33464740Sgreen if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) { 33528913Simp CLR(FTS_NAMEONLY); 3361573Srgrimes fts_lfree(sp->fts_child); 3371573Srgrimes sp->fts_child = NULL; 3381573Srgrimes } 3391573Srgrimes 3401573Srgrimes /* 3411573Srgrimes * Cd to the subdirectory. 3421573Srgrimes * 3431573Srgrimes * If have already read and now fail to chdir, whack the list 3441573Srgrimes * to make the names come out right, and set the parent errno 3451573Srgrimes * so the application will eventually get an error condition. 3461573Srgrimes * Set the FTS_DONTCHDIR flag so that when we logically change 3471573Srgrimes * directories back to the parent we don't do a chdir. 3481573Srgrimes * 3491573Srgrimes * If haven't read do so. If the read fails, fts_build sets 3501573Srgrimes * FTS_STOP or the fts_info field of the node. 3511573Srgrimes */ 35264740Sgreen if (sp->fts_child != NULL) { 35377599Skris if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) { 3541573Srgrimes p->fts_errno = errno; 3551573Srgrimes p->fts_flags |= FTS_DONTCHDIR; 35664740Sgreen for (p = sp->fts_child; p != NULL; 35764740Sgreen p = p->fts_link) 3581573Srgrimes p->fts_accpath = 3591573Srgrimes p->fts_parent->fts_accpath; 3601573Srgrimes } 3611573Srgrimes } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 3621573Srgrimes if (ISSET(FTS_STOP)) 3631573Srgrimes return (NULL); 3641573Srgrimes return (p); 3651573Srgrimes } 3661573Srgrimes p = sp->fts_child; 3671573Srgrimes sp->fts_child = NULL; 3681573Srgrimes goto name; 3691573Srgrimes } 3701573Srgrimes 3711573Srgrimes /* Move to the next node on this level. */ 3721573Srgrimesnext: tmp = p; 37364740Sgreen if ((p = p->fts_link) != NULL) { 3741573Srgrimes free(tmp); 3751573Srgrimes 3761573Srgrimes /* 37754770Sgreen * If reached the top, return to the original directory (or 37854770Sgreen * the root of the tree), and load the paths for the next root. 3791573Srgrimes */ 3801573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 38128913Simp if (FCHDIR(sp, sp->fts_rfd)) { 3821573Srgrimes SET(FTS_STOP); 3831573Srgrimes return (NULL); 3841573Srgrimes } 3851573Srgrimes fts_load(sp, p); 3861573Srgrimes return (sp->fts_cur = p); 3871573Srgrimes } 3881573Srgrimes 3891573Srgrimes /* 3901573Srgrimes * User may have called fts_set on the node. If skipped, 3911573Srgrimes * ignore. If followed, get a file descriptor so we can 3921573Srgrimes * get back if necessary. 3931573Srgrimes */ 3941573Srgrimes if (p->fts_instr == FTS_SKIP) 3951573Srgrimes goto next; 3961573Srgrimes if (p->fts_instr == FTS_FOLLOW) { 3971573Srgrimes p->fts_info = fts_stat(sp, p, 1); 39854770Sgreen if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) { 3991573Srgrimes if ((p->fts_symfd = 40056698Sjasone _open(".", O_RDONLY, 0)) < 0) { 4011573Srgrimes p->fts_errno = errno; 4021573Srgrimes p->fts_info = FTS_ERR; 4031573Srgrimes } else 4041573Srgrimes p->fts_flags |= FTS_SYMFOLLOW; 40554770Sgreen } 4061573Srgrimes p->fts_instr = FTS_NOINSTR; 4071573Srgrimes } 4081573Srgrimes 4091573Srgrimesname: t = sp->fts_path + NAPPEND(p->fts_parent); 4101573Srgrimes *t++ = '/'; 4111573Srgrimes memmove(t, p->fts_name, p->fts_namelen + 1); 4121573Srgrimes return (sp->fts_cur = p); 4131573Srgrimes } 4141573Srgrimes 4151573Srgrimes /* Move up to the parent node. */ 4161573Srgrimes p = tmp->fts_parent; 4171573Srgrimes free(tmp); 4181573Srgrimes 4191573Srgrimes if (p->fts_level == FTS_ROOTPARENTLEVEL) { 4201573Srgrimes /* 4211573Srgrimes * Done; free everything up and set errno to 0 so the user 4221573Srgrimes * can distinguish between error and EOF. 4231573Srgrimes */ 4241573Srgrimes free(p); 4251573Srgrimes errno = 0; 4261573Srgrimes return (sp->fts_cur = NULL); 4271573Srgrimes } 4281573Srgrimes 42954770Sgreen /* NUL terminate the pathname. */ 4301573Srgrimes sp->fts_path[p->fts_pathlen] = '\0'; 4311573Srgrimes 4321573Srgrimes /* 4331573Srgrimes * Return to the parent directory. If at a root node or came through 4341573Srgrimes * a symlink, go back through the file descriptor. Otherwise, cd up 4351573Srgrimes * one directory. 4361573Srgrimes */ 4371573Srgrimes if (p->fts_level == FTS_ROOTLEVEL) { 43828913Simp if (FCHDIR(sp, sp->fts_rfd)) { 4391573Srgrimes SET(FTS_STOP); 4401573Srgrimes return (NULL); 4411573Srgrimes } 4421573Srgrimes } else if (p->fts_flags & FTS_SYMFOLLOW) { 4431573Srgrimes if (FCHDIR(sp, p->fts_symfd)) { 4441573Srgrimes saved_errno = errno; 44556698Sjasone (void)_close(p->fts_symfd); 4461573Srgrimes errno = saved_errno; 4471573Srgrimes SET(FTS_STOP); 4481573Srgrimes return (NULL); 4491573Srgrimes } 45056698Sjasone (void)_close(p->fts_symfd); 45177497Skris } else if (!(p->fts_flags & FTS_DONTCHDIR) && 45277599Skris fts_safe_changedir(sp, p->fts_parent, -1, "..")) { 45377599Skris SET(FTS_STOP); 45477599Skris return (NULL); 4551573Srgrimes } 4561573Srgrimes p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 4571573Srgrimes return (sp->fts_cur = p); 4581573Srgrimes} 4591573Srgrimes 4601573Srgrimes/* 4611573Srgrimes * Fts_set takes the stream as an argument although it's not used in this 4621573Srgrimes * implementation; it would be necessary if anyone wanted to add global 4631573Srgrimes * semantics to fts using fts_set. An error return is allowed for similar 4641573Srgrimes * reasons. 4651573Srgrimes */ 4661573Srgrimes/* ARGSUSED */ 4671573Srgrimesint 4681573Srgrimesfts_set(sp, p, instr) 4691573Srgrimes FTS *sp; 4701573Srgrimes FTSENT *p; 4711573Srgrimes int instr; 4721573Srgrimes{ 47364740Sgreen if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW && 4741573Srgrimes instr != FTS_NOINSTR && instr != FTS_SKIP) { 4751573Srgrimes errno = EINVAL; 4761573Srgrimes return (1); 4771573Srgrimes } 4781573Srgrimes p->fts_instr = instr; 4791573Srgrimes return (0); 4801573Srgrimes} 4811573Srgrimes 4821573SrgrimesFTSENT * 4831573Srgrimesfts_children(sp, instr) 48490045Sobrien FTS *sp; 4851573Srgrimes int instr; 4861573Srgrimes{ 48790045Sobrien FTSENT *p; 4881573Srgrimes int fd; 4891573Srgrimes 49064740Sgreen if (instr != 0 && instr != FTS_NAMEONLY) { 4911573Srgrimes errno = EINVAL; 4921573Srgrimes return (NULL); 4931573Srgrimes } 4941573Srgrimes 4951573Srgrimes /* Set current node pointer. */ 4961573Srgrimes p = sp->fts_cur; 4971573Srgrimes 4981573Srgrimes /* 4991573Srgrimes * Errno set to 0 so user can distinguish empty directory from 5001573Srgrimes * an error. 5011573Srgrimes */ 5021573Srgrimes errno = 0; 5031573Srgrimes 5041573Srgrimes /* Fatal errors stop here. */ 5051573Srgrimes if (ISSET(FTS_STOP)) 5061573Srgrimes return (NULL); 5071573Srgrimes 5081573Srgrimes /* Return logical hierarchy of user's arguments. */ 5091573Srgrimes if (p->fts_info == FTS_INIT) 5101573Srgrimes return (p->fts_link); 5111573Srgrimes 5121573Srgrimes /* 5131573Srgrimes * If not a directory being visited in pre-order, stop here. Could 5141573Srgrimes * allow FTS_DNR, assuming the user has fixed the problem, but the 5151573Srgrimes * same effect is available with FTS_AGAIN. 5161573Srgrimes */ 5171573Srgrimes if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 5181573Srgrimes return (NULL); 5191573Srgrimes 5201573Srgrimes /* Free up any previous child list. */ 52164740Sgreen if (sp->fts_child != NULL) 5221573Srgrimes fts_lfree(sp->fts_child); 5231573Srgrimes 5241573Srgrimes if (instr == FTS_NAMEONLY) { 52528913Simp SET(FTS_NAMEONLY); 5261573Srgrimes instr = BNAMES; 5278870Srgrimes } else 5281573Srgrimes instr = BCHILD; 5291573Srgrimes 5301573Srgrimes /* 5311573Srgrimes * If using chdir on a relative path and called BEFORE fts_read does 5321573Srgrimes * its chdir to the root of a traversal, we can lose -- we need to 5331573Srgrimes * chdir into the subdirectory, and we don't know where the current 5341573Srgrimes * directory is, so we can't get back so that the upcoming chdir by 5351573Srgrimes * fts_read will work. 5361573Srgrimes */ 5371573Srgrimes if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 5381573Srgrimes ISSET(FTS_NOCHDIR)) 5391573Srgrimes return (sp->fts_child = fts_build(sp, instr)); 5401573Srgrimes 54156698Sjasone if ((fd = _open(".", O_RDONLY, 0)) < 0) 5421573Srgrimes return (NULL); 5431573Srgrimes sp->fts_child = fts_build(sp, instr); 5441573Srgrimes if (fchdir(fd)) 5451573Srgrimes return (NULL); 54656698Sjasone (void)_close(fd); 5471573Srgrimes return (sp->fts_child); 5481573Srgrimes} 5491573Srgrimes 550103726Swollman#ifndef fts_get_clientptr 551103726Swollman#error "fts_get_clientptr not defined" 552103726Swollman#endif 553103726Swollman 554103726Swollmanvoid * 555103726Swollman(fts_get_clientptr)(FTS *sp) 556103726Swollman{ 557103726Swollman 558103726Swollman return (fts_get_clientptr(sp)); 559103726Swollman} 560103726Swollman 561103726Swollman#ifndef fts_get_stream 562103726Swollman#error "fts_get_stream not defined" 563103726Swollman#endif 564103726Swollman 565103726SwollmanFTS * 566103726Swollman(fts_get_stream)(FTSENT *p) 567103726Swollman{ 568103726Swollman return (fts_get_stream(p)); 569103726Swollman} 570103726Swollman 571103726Swollmanvoid 572103726Swollmanfts_set_clientptr(FTS *sp, void *clientptr) 573103726Swollman{ 574103726Swollman 575103726Swollman sp->fts_clientptr = clientptr; 576103726Swollman} 577103726Swollman 5781573Srgrimes/* 5791573Srgrimes * This is the tricky part -- do not casually change *anything* in here. The 5801573Srgrimes * idea is to build the linked list of entries that are used by fts_children 5811573Srgrimes * and fts_read. There are lots of special cases. 5821573Srgrimes * 5831573Srgrimes * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 5841573Srgrimes * set and it's a physical walk (so that symbolic links can't be directories), 5851573Srgrimes * we can do things quickly. First, if it's a 4.4BSD file system, the type 5861573Srgrimes * of the file is in the directory entry. Otherwise, we assume that the number 5871573Srgrimes * of subdirectories in a node is equal to the number of links to the parent. 5881573Srgrimes * The former skips all stat calls. The latter skips stat calls in any leaf 5891573Srgrimes * directories and for any files after the subdirectories in the directory have 5901573Srgrimes * been found, cutting the stat calls by about 2/3. 5911573Srgrimes */ 5921573Srgrimesstatic FTSENT * 5931573Srgrimesfts_build(sp, type) 59490045Sobrien FTS *sp; 5951573Srgrimes int type; 5961573Srgrimes{ 59790045Sobrien struct dirent *dp; 59890045Sobrien FTSENT *p, *head; 59990045Sobrien int nitems; 6001573Srgrimes FTSENT *cur, *tail; 6011573Srgrimes DIR *dirp; 60254770Sgreen void *oldaddr; 60354770Sgreen int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno, 60454770Sgreen nostat, doadjust; 6051573Srgrimes char *cp; 6061573Srgrimes 6071573Srgrimes /* Set current node pointer. */ 6081573Srgrimes cur = sp->fts_cur; 6091573Srgrimes 6101573Srgrimes /* 6111573Srgrimes * Open the directory for reading. If this fails, we're done. 6121573Srgrimes * If being called from fts_read, set the fts_info field. 6131573Srgrimes */ 61423668Speter#ifdef FTS_WHITEOUT 61523668Speter if (ISSET(FTS_WHITEOUT)) 61623668Speter oflag = DTF_NODUP|DTF_REWIND; 61723668Speter else 61823668Speter oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND; 61923668Speter#else 62023668Speter#define __opendir2(path, flag) opendir(path) 62123668Speter#endif 62223668Speter if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 6231573Srgrimes if (type == BREAD) { 6241573Srgrimes cur->fts_info = FTS_DNR; 6251573Srgrimes cur->fts_errno = errno; 6261573Srgrimes } 6271573Srgrimes return (NULL); 6281573Srgrimes } 6291573Srgrimes 6301573Srgrimes /* 6311573Srgrimes * Nlinks is the number of possible entries of type directory in the 6321573Srgrimes * directory if we're cheating on stat calls, 0 if we're not doing 6331573Srgrimes * any stat calls at all, -1 if we're doing stats on everything. 6341573Srgrimes */ 63554770Sgreen if (type == BNAMES) { 6361573Srgrimes nlinks = 0; 63754770Sgreen /* Be quiet about nostat, GCC. */ 63854770Sgreen nostat = 0; 63954770Sgreen } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 6401573Srgrimes nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 64154770Sgreen nostat = 1; 64254770Sgreen } else { 6431573Srgrimes nlinks = -1; 64454770Sgreen nostat = 0; 64554770Sgreen } 6461573Srgrimes 6471573Srgrimes#ifdef notdef 6481573Srgrimes (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 6491573Srgrimes (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 6501573Srgrimes ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 6511573Srgrimes#endif 6521573Srgrimes /* 6531573Srgrimes * If we're going to need to stat anything or we want to descend 6541573Srgrimes * and stay in the directory, chdir. If this fails we keep going, 6551573Srgrimes * but set a flag so we don't chdir after the post-order visit. 6561573Srgrimes * We won't be able to stat anything, but we can still return the 6571573Srgrimes * names themselves. Note, that since fts_read won't be able to 6581573Srgrimes * chdir into the directory, it will have to return different path 6591573Srgrimes * names than before, i.e. "a/b" instead of "b". Since the node 6601573Srgrimes * has already been visited in pre-order, have to wait until the 6611573Srgrimes * post-order visit to return the error. There is a special case 6621573Srgrimes * here, if there was nothing to stat then it's not an error to 6631573Srgrimes * not be able to stat. This is all fairly nasty. If a program 6641573Srgrimes * needed sorted entries or stat information, they had better be 6651573Srgrimes * checking FTS_NS on the returned nodes. 6661573Srgrimes */ 6671573Srgrimes cderrno = 0; 66854770Sgreen if (nlinks || type == BREAD) { 66977599Skris if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) { 6701573Srgrimes if (nlinks && type == BREAD) 6711573Srgrimes cur->fts_errno = errno; 6721573Srgrimes cur->fts_flags |= FTS_DONTCHDIR; 6731573Srgrimes descend = 0; 6741573Srgrimes cderrno = errno; 67528913Simp (void)closedir(dirp); 67628913Simp dirp = NULL; 6771573Srgrimes } else 6781573Srgrimes descend = 1; 67954770Sgreen } else 6801573Srgrimes descend = 0; 6811573Srgrimes 6821573Srgrimes /* 6831573Srgrimes * Figure out the max file name length that can be stored in the 6841573Srgrimes * current path -- the inner loop allocates more path as necessary. 6851573Srgrimes * We really wouldn't have to do the maxlen calculations here, we 6861573Srgrimes * could do them in fts_read before returning the path, but it's a 6871573Srgrimes * lot easier here since the length is part of the dirent structure. 6881573Srgrimes * 6891573Srgrimes * If not changing directories set a pointer so that can just append 6901573Srgrimes * each new name into the path. 6911573Srgrimes */ 6921573Srgrimes len = NAPPEND(cur); 6931573Srgrimes if (ISSET(FTS_NOCHDIR)) { 6941573Srgrimes cp = sp->fts_path + len; 6951573Srgrimes *cp++ = '/'; 69654770Sgreen } else { 69754770Sgreen /* GCC, you're too verbose. */ 69854770Sgreen cp = NULL; 6991573Srgrimes } 70054770Sgreen len++; 70154770Sgreen maxlen = sp->fts_pathlen - len; 7021573Srgrimes 7031573Srgrimes level = cur->fts_level + 1; 7041573Srgrimes 7051573Srgrimes /* Read the directory, attaching each entry to the `link' pointer. */ 70654770Sgreen doadjust = 0; 70728913Simp for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) { 7081573Srgrimes if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 7091573Srgrimes continue; 7101573Srgrimes 7111573Srgrimes if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL) 7121573Srgrimes goto mem1; 71354770Sgreen if (dp->d_namlen >= maxlen) { /* include space for NUL */ 71454770Sgreen oldaddr = sp->fts_path; 71564740Sgreen if (fts_palloc(sp, dp->d_namlen + len + 1)) { 7161573Srgrimes /* 7171573Srgrimes * No more memory for path or structures. Save 7181573Srgrimes * errno, free up the current structure and the 7191573Srgrimes * structures already allocated. 7201573Srgrimes */ 7211573Srgrimesmem1: saved_errno = errno; 7221573Srgrimes if (p) 7231573Srgrimes free(p); 7241573Srgrimes fts_lfree(head); 7251573Srgrimes (void)closedir(dirp); 7261573Srgrimes cur->fts_info = FTS_ERR; 7271573Srgrimes SET(FTS_STOP); 72854770Sgreen errno = saved_errno; 7291573Srgrimes return (NULL); 7301573Srgrimes } 73154770Sgreen /* Did realloc() change the pointer? */ 73254770Sgreen if (oldaddr != sp->fts_path) { 73354770Sgreen doadjust = 1; 73454770Sgreen if (ISSET(FTS_NOCHDIR)) 73554770Sgreen cp = sp->fts_path + len; 73654770Sgreen } 73754770Sgreen maxlen = sp->fts_pathlen - len; 7381573Srgrimes } 7391573Srgrimes 74054770Sgreen if (len + dp->d_namlen >= USHRT_MAX) { 74154770Sgreen /* 74254770Sgreen * In an FTSENT, fts_pathlen is a u_short so it is 74354770Sgreen * possible to wraparound here. If we do, free up 74454770Sgreen * the current structure and the structures already 74554770Sgreen * allocated, then error out with ENAMETOOLONG. 74654770Sgreen */ 74754770Sgreen free(p); 74854770Sgreen fts_lfree(head); 74954770Sgreen (void)closedir(dirp); 75054770Sgreen cur->fts_info = FTS_ERR; 75154770Sgreen SET(FTS_STOP); 75254770Sgreen errno = ENAMETOOLONG; 75354770Sgreen return (NULL); 75454770Sgreen } 75554770Sgreen p->fts_level = level; 7561573Srgrimes p->fts_parent = sp->fts_cur; 75754770Sgreen p->fts_pathlen = len + dp->d_namlen; 7581573Srgrimes 75923668Speter#ifdef FTS_WHITEOUT 76023668Speter if (dp->d_type == DT_WHT) 76123668Speter p->fts_flags |= FTS_ISW; 76223668Speter#endif 76323668Speter 7641573Srgrimes if (cderrno) { 7651573Srgrimes if (nlinks) { 7661573Srgrimes p->fts_info = FTS_NS; 7671573Srgrimes p->fts_errno = cderrno; 7681573Srgrimes } else 7691573Srgrimes p->fts_info = FTS_NSOK; 7701573Srgrimes p->fts_accpath = cur->fts_accpath; 7711573Srgrimes } else if (nlinks == 0 7721573Srgrimes#ifdef DT_DIR 77354770Sgreen || (nostat && 77417141Sjkh dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 7751573Srgrimes#endif 7761573Srgrimes ) { 7771573Srgrimes p->fts_accpath = 7781573Srgrimes ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 7791573Srgrimes p->fts_info = FTS_NSOK; 7801573Srgrimes } else { 7811573Srgrimes /* Build a file name for fts_stat to stat. */ 7821573Srgrimes if (ISSET(FTS_NOCHDIR)) { 7831573Srgrimes p->fts_accpath = p->fts_path; 7841573Srgrimes memmove(cp, p->fts_name, p->fts_namelen + 1); 7851573Srgrimes } else 7861573Srgrimes p->fts_accpath = p->fts_name; 7871573Srgrimes /* Stat it. */ 7881573Srgrimes p->fts_info = fts_stat(sp, p, 0); 7891573Srgrimes 7901573Srgrimes /* Decrement link count if applicable. */ 7911573Srgrimes if (nlinks > 0 && (p->fts_info == FTS_D || 7921573Srgrimes p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 7931573Srgrimes --nlinks; 7941573Srgrimes } 7951573Srgrimes 7961573Srgrimes /* We walk in directory order so "ls -f" doesn't get upset. */ 7971573Srgrimes p->fts_link = NULL; 7981573Srgrimes if (head == NULL) 7991573Srgrimes head = tail = p; 8001573Srgrimes else { 8011573Srgrimes tail->fts_link = p; 8021573Srgrimes tail = p; 8031573Srgrimes } 8041573Srgrimes ++nitems; 8051573Srgrimes } 80628913Simp if (dirp) 80728913Simp (void)closedir(dirp); 8081573Srgrimes 8091573Srgrimes /* 81054770Sgreen * If realloc() changed the address of the path, adjust the 81154770Sgreen * addresses for the rest of the tree and the dir list. 8121573Srgrimes */ 81354770Sgreen if (doadjust) 81454770Sgreen fts_padjust(sp, head); 8151573Srgrimes 8161573Srgrimes /* 8171573Srgrimes * If not changing directories, reset the path back to original 8181573Srgrimes * state. 8191573Srgrimes */ 8201573Srgrimes if (ISSET(FTS_NOCHDIR)) { 82154770Sgreen if (len == sp->fts_pathlen || nitems == 0) 8221573Srgrimes --cp; 8231573Srgrimes *cp = '\0'; 8241573Srgrimes } 8251573Srgrimes 8261573Srgrimes /* 8271573Srgrimes * If descended after called from fts_children or after called from 8281573Srgrimes * fts_read and nothing found, get back. At the root level we use 8291573Srgrimes * the saved fd; if one of fts_open()'s arguments is a relative path 8301573Srgrimes * to an empty directory, we wind up here with no other way back. If 8311573Srgrimes * can't get back, we're done. 8321573Srgrimes */ 8331573Srgrimes if (descend && (type == BCHILD || !nitems) && 8341573Srgrimes (cur->fts_level == FTS_ROOTLEVEL ? 83577599Skris FCHDIR(sp, sp->fts_rfd) : 83677599Skris fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) { 8371573Srgrimes cur->fts_info = FTS_ERR; 8381573Srgrimes SET(FTS_STOP); 8391573Srgrimes return (NULL); 8401573Srgrimes } 8411573Srgrimes 8421573Srgrimes /* If didn't find anything, return NULL. */ 8431573Srgrimes if (!nitems) { 8441573Srgrimes if (type == BREAD) 8451573Srgrimes cur->fts_info = FTS_DP; 8461573Srgrimes return (NULL); 8471573Srgrimes } 8481573Srgrimes 8491573Srgrimes /* Sort the entries. */ 8501573Srgrimes if (sp->fts_compar && nitems > 1) 8511573Srgrimes head = fts_sort(sp, head, nitems); 8521573Srgrimes return (head); 8531573Srgrimes} 8541573Srgrimes 8551573Srgrimesstatic u_short 8561573Srgrimesfts_stat(sp, p, follow) 8571573Srgrimes FTS *sp; 85890045Sobrien FTSENT *p; 8591573Srgrimes int follow; 8601573Srgrimes{ 86190045Sobrien FTSENT *t; 86290045Sobrien dev_t dev; 86390045Sobrien ino_t ino; 8641573Srgrimes struct stat *sbp, sb; 8651573Srgrimes int saved_errno; 8661573Srgrimes 8671573Srgrimes /* If user needs stat info, stat buffer already allocated. */ 8681573Srgrimes sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 8698870Srgrimes 87023668Speter#ifdef FTS_WHITEOUT 87123668Speter /* check for whiteout */ 87223668Speter if (p->fts_flags & FTS_ISW) { 87323668Speter if (sbp != &sb) { 87423668Speter memset(sbp, '\0', sizeof (*sbp)); 87523668Speter sbp->st_mode = S_IFWHT; 87623668Speter } 87723668Speter return (FTS_W); 87823668Speter } 87923668Speter#endif 88023668Speter 8811573Srgrimes /* 8821573Srgrimes * If doing a logical walk, or application requested FTS_FOLLOW, do 8831573Srgrimes * a stat(2). If that fails, check for a non-existent symlink. If 8841573Srgrimes * fail, set the errno from the stat call. 8851573Srgrimes */ 8861573Srgrimes if (ISSET(FTS_LOGICAL) || follow) { 8871573Srgrimes if (stat(p->fts_accpath, sbp)) { 8881573Srgrimes saved_errno = errno; 8891573Srgrimes if (!lstat(p->fts_accpath, sbp)) { 8901573Srgrimes errno = 0; 8911573Srgrimes return (FTS_SLNONE); 8928870Srgrimes } 8931573Srgrimes p->fts_errno = saved_errno; 8941573Srgrimes goto err; 8951573Srgrimes } 8961573Srgrimes } else if (lstat(p->fts_accpath, sbp)) { 8971573Srgrimes p->fts_errno = errno; 8981573Srgrimeserr: memset(sbp, 0, sizeof(struct stat)); 8991573Srgrimes return (FTS_NS); 9001573Srgrimes } 9011573Srgrimes 9021573Srgrimes if (S_ISDIR(sbp->st_mode)) { 9031573Srgrimes /* 9041573Srgrimes * Set the device/inode. Used to find cycles and check for 9051573Srgrimes * crossing mount points. Also remember the link count, used 9061573Srgrimes * in fts_build to limit the number of stat calls. It is 9071573Srgrimes * understood that these fields are only referenced if fts_info 9081573Srgrimes * is set to FTS_D. 9091573Srgrimes */ 9101573Srgrimes dev = p->fts_dev = sbp->st_dev; 9111573Srgrimes ino = p->fts_ino = sbp->st_ino; 9121573Srgrimes p->fts_nlink = sbp->st_nlink; 9131573Srgrimes 9141573Srgrimes if (ISDOT(p->fts_name)) 9151573Srgrimes return (FTS_DOT); 9161573Srgrimes 9171573Srgrimes /* 9181573Srgrimes * Cycle detection is done by brute force when the directory 9191573Srgrimes * is first encountered. If the tree gets deep enough or the 9201573Srgrimes * number of symbolic links to directories is high enough, 9211573Srgrimes * something faster might be worthwhile. 9221573Srgrimes */ 9231573Srgrimes for (t = p->fts_parent; 9241573Srgrimes t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 9251573Srgrimes if (ino == t->fts_ino && dev == t->fts_dev) { 9261573Srgrimes p->fts_cycle = t; 9271573Srgrimes return (FTS_DC); 9281573Srgrimes } 9291573Srgrimes return (FTS_D); 9301573Srgrimes } 9311573Srgrimes if (S_ISLNK(sbp->st_mode)) 9321573Srgrimes return (FTS_SL); 9331573Srgrimes if (S_ISREG(sbp->st_mode)) 9341573Srgrimes return (FTS_F); 9351573Srgrimes return (FTS_DEFAULT); 9361573Srgrimes} 9371573Srgrimes 938103726Swollman/* 939103726Swollman * The comparison function takes pointers to pointers to FTSENT structures. 940103726Swollman * Qsort wants a comparison function that takes pointers to void. 941103726Swollman * (Both with appropriate levels of const-poisoning, of course!) 942103726Swollman * Use a trampoline function to deal with the difference. 943103726Swollman */ 944103726Swollmanstatic int 945103726Swollmanfts_compar(const void *a, const void *b) 946103726Swollman{ 947103726Swollman FTS *parent; 948103726Swollman 949103726Swollman parent = (*(const FTSENT * const *)a)->fts_fts; 950103726Swollman return (*parent->fts_compar)(a, b); 951103726Swollman} 952103726Swollman 9531573Srgrimesstatic FTSENT * 9541573Srgrimesfts_sort(sp, head, nitems) 9551573Srgrimes FTS *sp; 9561573Srgrimes FTSENT *head; 95790045Sobrien int nitems; 9581573Srgrimes{ 95990045Sobrien FTSENT **ap, *p; 9601573Srgrimes 9611573Srgrimes /* 9621573Srgrimes * Construct an array of pointers to the structures and call qsort(3). 9631573Srgrimes * Reassemble the array in the order returned by qsort. If unable to 9641573Srgrimes * sort for memory reasons, return the directory entries in their 9651573Srgrimes * current order. Allocate enough space for the current needs plus 9661573Srgrimes * 40 so don't realloc one entry at a time. 9671573Srgrimes */ 9681573Srgrimes if (nitems > sp->fts_nitems) { 9691573Srgrimes sp->fts_nitems = nitems + 40; 97064740Sgreen if ((sp->fts_array = reallocf(sp->fts_array, 97154770Sgreen sp->fts_nitems * sizeof(FTSENT *))) == NULL) { 9721573Srgrimes sp->fts_nitems = 0; 9731573Srgrimes return (head); 9741573Srgrimes } 9751573Srgrimes } 9761573Srgrimes for (ap = sp->fts_array, p = head; p; p = p->fts_link) 9771573Srgrimes *ap++ = p; 978103726Swollman qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar); 9791573Srgrimes for (head = *(ap = sp->fts_array); --nitems; ++ap) 9801573Srgrimes ap[0]->fts_link = ap[1]; 9811573Srgrimes ap[0]->fts_link = NULL; 9821573Srgrimes return (head); 9831573Srgrimes} 9841573Srgrimes 9851573Srgrimesstatic FTSENT * 9861573Srgrimesfts_alloc(sp, name, namelen) 9871573Srgrimes FTS *sp; 9881573Srgrimes char *name; 98990045Sobrien int namelen; 9901573Srgrimes{ 99190045Sobrien FTSENT *p; 9921573Srgrimes size_t len; 9931573Srgrimes 994103726Swollman struct ftsent_withstat { 995103726Swollman FTSENT ent; 996103726Swollman struct stat statbuf; 997103726Swollman }; 998103726Swollman 9991573Srgrimes /* 10001573Srgrimes * The file name is a variable length array and no stat structure is 10011573Srgrimes * necessary if the user has set the nostat bit. Allocate the FTSENT 10021573Srgrimes * structure, the file name and the stat structure in one chunk, but 1003103726Swollman * be careful that the stat structure is reasonably aligned. 10041573Srgrimes */ 1005103726Swollman if (ISSET(FTS_NOSTAT)) 1006103726Swollman len = sizeof(FTSENT) + namelen + 1; 1007103726Swollman else 1008103726Swollman len = sizeof(struct ftsent_withstat) + namelen + 1; 1009103726Swollman 10101573Srgrimes if ((p = malloc(len)) == NULL) 10111573Srgrimes return (NULL); 10121573Srgrimes 1013103726Swollman if (ISSET(FTS_NOSTAT)) { 1014103726Swollman p->fts_name = (char *)(p + 1); 1015103726Swollman p->fts_statp = NULL; 1016103726Swollman } else { 1017103726Swollman p->fts_name = (char *)((struct ftsent_withstat *)p + 1); 1018103726Swollman p->fts_statp = &((struct ftsent_withstat *)p)->statbuf; 1019103726Swollman } 1020103726Swollman 102154770Sgreen /* Copy the name and guarantee NUL termination. */ 1022103726Swollman memcpy(p->fts_name, name, namelen); 102354770Sgreen p->fts_name[namelen] = '\0'; 10241573Srgrimes p->fts_namelen = namelen; 10251573Srgrimes p->fts_path = sp->fts_path; 10261573Srgrimes p->fts_errno = 0; 10271573Srgrimes p->fts_flags = 0; 10281573Srgrimes p->fts_instr = FTS_NOINSTR; 10291573Srgrimes p->fts_number = 0; 10301573Srgrimes p->fts_pointer = NULL; 1031103726Swollman p->fts_fts = sp; 10321573Srgrimes return (p); 10331573Srgrimes} 10341573Srgrimes 10351573Srgrimesstatic void 10361573Srgrimesfts_lfree(head) 103790045Sobrien FTSENT *head; 10381573Srgrimes{ 103990045Sobrien FTSENT *p; 10401573Srgrimes 10411573Srgrimes /* Free a linked list of structures. */ 104228913Simp while ((p = head)) { 10431573Srgrimes head = head->fts_link; 10441573Srgrimes free(p); 10451573Srgrimes } 10461573Srgrimes} 10471573Srgrimes 10481573Srgrimes/* 10491573Srgrimes * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 10501573Srgrimes * Most systems will allow creation of paths much longer than MAXPATHLEN, even 10511573Srgrimes * though the kernel won't resolve them. Add the size (not just what's needed) 10528870Srgrimes * plus 256 bytes so don't realloc the path 2 bytes at a time. 10531573Srgrimes */ 10541573Srgrimesstatic int 10551573Srgrimesfts_palloc(sp, more) 10561573Srgrimes FTS *sp; 10571573Srgrimes size_t more; 10581573Srgrimes{ 105954770Sgreen 10601573Srgrimes sp->fts_pathlen += more + 256; 106154770Sgreen /* 106254770Sgreen * Check for possible wraparound. In an FTS, fts_pathlen is 106354770Sgreen * a signed int but in an FTSENT it is an unsigned short. 106454770Sgreen * We limit fts_pathlen to USHRT_MAX to be safe in both cases. 106554770Sgreen */ 106654770Sgreen if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) { 106754770Sgreen if (sp->fts_path) 106854770Sgreen free(sp->fts_path); 106954770Sgreen sp->fts_path = NULL; 107054770Sgreen errno = ENAMETOOLONG; 107154770Sgreen return (1); 107250790Simp } 107364740Sgreen sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen); 107464740Sgreen return (sp->fts_path == NULL); 107550790Simp} 107650790Simp 10771573Srgrimes/* 10781573Srgrimes * When the path is realloc'd, have to fix all of the pointers in structures 10791573Srgrimes * already returned. 10801573Srgrimes */ 10811573Srgrimesstatic void 108254770Sgreenfts_padjust(sp, head) 10831573Srgrimes FTS *sp; 108454770Sgreen FTSENT *head; 10851573Srgrimes{ 10861573Srgrimes FTSENT *p; 108754770Sgreen char *addr = sp->fts_path; 10881573Srgrimes 108964740Sgreen#define ADJUST(p) do { \ 109054770Sgreen if ((p)->fts_accpath != (p)->fts_name) { \ 109154770Sgreen (p)->fts_accpath = \ 109254770Sgreen (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 109354770Sgreen } \ 10941573Srgrimes (p)->fts_path = addr; \ 109564740Sgreen} while (0) 10961573Srgrimes /* Adjust the current set of children. */ 10971573Srgrimes for (p = sp->fts_child; p; p = p->fts_link) 109854770Sgreen ADJUST(p); 10991573Srgrimes 110054770Sgreen /* Adjust the rest of the tree, including the current level. */ 110154770Sgreen for (p = head; p->fts_level >= FTS_ROOTLEVEL;) { 110254770Sgreen ADJUST(p); 11031573Srgrimes p = p->fts_link ? p->fts_link : p->fts_parent; 11041573Srgrimes } 11051573Srgrimes} 11061573Srgrimes 11071573Srgrimesstatic size_t 11081573Srgrimesfts_maxarglen(argv) 11091573Srgrimes char * const *argv; 11101573Srgrimes{ 11111573Srgrimes size_t len, max; 11121573Srgrimes 11131573Srgrimes for (max = 0; *argv; ++argv) 11141573Srgrimes if ((len = strlen(*argv)) > max) 11151573Srgrimes max = len; 111654770Sgreen return (max + 1); 11171573Srgrimes} 111828913Simp 111928913Simp/* 112028913Simp * Change to dir specified by fd or p->fts_accpath without getting 112128913Simp * tricked by someone changing the world out from underneath us. 112228913Simp * Assumes p->fts_dev and p->fts_ino are filled in. 112328913Simp */ 112428913Simpstatic int 112577599Skrisfts_safe_changedir(sp, p, fd, path) 112628913Simp FTS *sp; 112728913Simp FTSENT *p; 112828913Simp int fd; 112977599Skris char *path; 113028913Simp{ 113128913Simp int ret, oerrno, newfd; 113228913Simp struct stat sb; 113328913Simp 113428913Simp newfd = fd; 113528913Simp if (ISSET(FTS_NOCHDIR)) 113628913Simp return (0); 113777599Skris if (fd < 0 && (newfd = _open(path, O_RDONLY, 0)) < 0) 113828913Simp return (-1); 113971579Sdeischen if (_fstat(newfd, &sb)) { 114028913Simp ret = -1; 114128913Simp goto bail; 114228913Simp } 114328913Simp if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) { 114428913Simp errno = ENOENT; /* disinformation */ 114528913Simp ret = -1; 114628913Simp goto bail; 114728913Simp } 114828913Simp ret = fchdir(newfd); 114928913Simpbail: 115028913Simp oerrno = errno; 115128913Simp if (fd < 0) 115256698Sjasone (void)_close(newfd); 115328913Simp errno = oerrno; 115428913Simp return (ret); 115528913Simp} 1156