1 /*-

     2  * Copyright (c) 1990, 1993, 1994

     3  *	The Regents of the University of California.  All rights reserved.

     4  *

     5  * Redistribution and use in source and binary forms, with or without

     6  * modification, are permitted provided that the following conditions

     7  * are met:

     8  * 1. Redistributions of source code must retain the above copyright

     9  *    notice, this list of conditions and the following disclaimer.

    10  * 2. Redistributions in binary form must reproduce the above copyright

    11  *    notice, this list of conditions and the following disclaimer in the

    12  *    documentation and/or other materials provided with the distribution.

    13  * 4. Neither the name of the University nor the names of its contributors

    14  *    may be used to endorse or promote products derived from this software

    15  *    without specific prior written permission.

    16  *

    17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

    18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

    21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

    22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

    23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

    24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

    25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

    26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

    27  * SUCH DAMAGE.

    28  *

    29  * * Portions Copyright (c) 2007 Nokia Corporation and/or its subsidiary(-ies).. All rights reserved.

    30  * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $

    31  */

    32 

    33 #if 0

    34 #if defined(LIBC_SCCS) && !defined(lint)

    35 static char sccsid[] = "@(#)fts.c	8.6 (Berkeley) 8/14/94";

    36 #endif /* LIBC_SCCS and not lint */

    37 #endif

    38 

    39 #include <sys/cdefs.h>

    40 __FBSDID("$FreeBSD: src/lib/libc/gen/fts.c,v 1.27 2004/06/08 06:23:23 das Exp $");

    41 

    42 #ifdef __cplusplus

    43 extern "C"	{

    44 #endif

    45 

    46 #ifndef __SYMBIAN32__

    47 #include "namespace.h"

    48 #endif

    49 #include <sys/param.h>

    50 #ifndef __SYMBIAN32__

    51 #include <sys/mount.h>

    52 #endif

    53 #include <sys/stat.h>

    54 

    55 #include <dirent.h>

    56 #include <errno.h>

    57 #include <fcntl.h>

    58 #include <stdlib.h>

    59 #include <string.h>

    60 #include <unistd.h>

    61 #ifndef __SYMBIAN32__

    62 #include "un-namespace.h"

    63 #endif

    64 #include "fts.h"

    65 

    66 #ifdef __SYMBIAN32__

    67 #ifdef __WINSCW__

    68 #pragma warn_unusedarg off

    69 #pragma warn_possunwant off

    70 #endif//__WINSCW__

    71 #endif//__SYMBIAN32__

    72 

    73 static FTSENT	*fts_alloc(FTS *, char *, int);

    74 static FTSENT	*fts_build(FTS *, int);

    75 static void	 fts_lfree(FTSENT *);

    76 static void	 fts_load(FTS *, FTSENT *);

    77 static size_t	 fts_maxarglen(char * const *);

    78 static void	 fts_padjust(FTS *, FTSENT *);

    79 static int	 fts_palloc(FTS *, size_t);

    80 static FTSENT	*fts_sort(FTS *, FTSENT *, int);

    81 static u_short	 fts_stat(FTS *, FTSENT *, int);

    82 static int	 fts_safe_changedir(FTS *, FTSENT *, int, char *);

    83 #ifndef __SYMBIAN32__

    84 static int	 fts_ufslinks(FTS *, const FTSENT *);

    85 #endif

    86 #define	ISDOT(a)	(a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))

    87 

    88 #define	CLR(opt)	(sp->fts_options &= ~(opt))

    89 #define	ISSET(opt)	(sp->fts_options & (opt))

    90 #define	SET(opt)	(sp->fts_options |= (opt))

    91 

    92 #define	FCHDIR(sp, fd)	(!ISSET(FTS_NOCHDIR) && fchdir(fd))

    93 

    94 /* fts_build flags */

    95 #define	BCHILD		1		/* fts_children */

    96 #define	BNAMES		2		/* fts_children, names only */

    97 #define	BREAD		3		/* fts_read */

    98 

    99 #ifndef __SYMBIAN32__

   100 /*

   101  * Internal representation of an FTS, including extra implementation

   102  * details.  The FTS returned from fts_open points to this structure's

   103  * ftsp_fts member (and can be cast to an _fts_private as required)

   104  */

   105 struct _fts_private {

   106 	FTS		ftsp_fts;

   107 	struct statfs	ftsp_statfs;

   108 	dev_t		ftsp_dev;

   109 	int		ftsp_linksreliable;

   110 };

   111 #endif

   112 /*

   113  * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it

   114  * knows that a directory could not possibly have subdirectories.  This

   115  * is decided by looking at the link count: a subdirectory would

   116  * increment its parent's link count by virtue of its own ".." entry.

   117  * This assumption only holds for UFS-like filesystems that implement

   118  * links and directories this way, so we must punt for others.

   119  */

   120 

   121 static const char *ufslike_filesystems[] = {

   122 	"ufs",

   123 	"nfs",

   124 	"nfs4",

   125 	"ext2fs",

   126 	0

   127 };

   128 

   129 FTS *

   130 fts_open(argv, options, compar)

   131 	char * const *argv;

   132 	int options;

   133 	int (*compar)(const FTSENT * const *, const FTSENT * const *);

   134 {

   135 #ifndef __SYMBIAN32__

   136 	struct _fts_private *priv;

   137 #endif	

   138 	FTS *sp;

   139 	FTSENT *p, *root;

   140 	int nitems;

   141 	FTSENT *parent, *tmp;

   142 	int len;

   143 

   144 	/* Options check. */

   145 	if (options & ~FTS_OPTIONMASK) {

   146 		errno = EINVAL;

   147 		return (NULL);

   148 	}

   149 #ifndef __SYMBIAN32__

   150 	/* Allocate/initialize the stream. */

   151 	if ((priv = malloc(sizeof(*priv))) == NULL)

   152 		return (NULL);

   153 	memset(priv, 0, sizeof(*priv));

   154 	sp = &priv->ftsp_fts;

   155 #else

   156 	/* Allocate/initialize the stream */

   157 	if ((sp = malloc((u_int)sizeof(FTS))) == NULL)

   158 		return (NULL);

   159 	memset(sp, 0, sizeof(FTS));

   160 #endif	

   161 	sp->fts_compar = compar;

   162 	sp->fts_options = options;

   163 

   164 	/* Shush, GCC. */

   165 	tmp = NULL;

   166 

   167 	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */

   168 	if (ISSET(FTS_LOGICAL))

   169 		SET(FTS_NOCHDIR);

   170 

   171 	/*

   172 	 * Start out with 1K of path space, and enough, in any case,

   173 	 * to hold the user's paths.

   174 	 */

   175 	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))

   176 		goto mem1;

   177 

   178 	/* Allocate/initialize root's parent. */

   179 	if ((parent = fts_alloc(sp, "", 0)) == NULL)

   180 		goto mem2;

   181 	parent->fts_level = FTS_ROOTPARENTLEVEL;

   182 

   183 	/* Allocate/initialize root(s). */

   184 	for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {

   185 		/* Don't allow zero-length paths. */

   186 		if ((len = strlen(*argv)) == 0) {

   187 			errno = ENOENT;

   188 			goto mem3;

   189 		}

   190 

   191 		p = fts_alloc(sp, *argv, len);

   192 		p->fts_level = FTS_ROOTLEVEL;

   193 		p->fts_parent = parent;

   194 		p->fts_accpath = p->fts_name;

   195 		p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));

   196 

   197 		/* Command-line "." and ".." are real directories. */

   198 		if (p->fts_info == FTS_DOT)

   199 			p->fts_info = FTS_D;

   200 

   201 		/*

   202 		 * If comparison routine supplied, traverse in sorted

   203 		 * order; otherwise traverse in the order specified.

   204 		 */

   205 		if (compar) {

   206 			p->fts_link = root;

   207 			root = p;

   208 		} else {

   209 			p->fts_link = NULL;

   210 			if (root == NULL)

   211 				tmp = root = p;

   212 			else {

   213 				tmp->fts_link = p;

   214 				tmp = p;

   215 			}

   216 		}

   217 	}

   218 	if (compar && nitems > 1)

   219 		root = fts_sort(sp, root, nitems);

   220 

   221 	/*

   222 	 * Allocate a dummy pointer and make fts_read think that we've just

   223 	 * finished the node before the root(s); set p->fts_info to FTS_INIT

   224 	 * so that everything about the "current" node is ignored.

   225 	 */

   226 	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)

   227 		goto mem3;

   228 	sp->fts_cur->fts_link = root;

   229 	sp->fts_cur->fts_info = FTS_INIT;

   230 

   231 	/*

   232 	 * If using chdir(2), grab a file descriptor pointing to dot to ensure

   233 	 * that we can get back here; this could be avoided for some paths,

   234 	 * but almost certainly not worth the effort.  Slashes, symbolic links,

   235 	 * and ".." are all fairly nasty problems.  Note, if we can't get the

   236 	 * descriptor we run anyway, just more slowly.

   237 	 */

   238 	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)

   239 		SET(FTS_NOCHDIR);

   240 

   241 	return (sp);

   242 

   243 mem3:	fts_lfree(root);

   244 	free(parent);

   245 mem2:	free(sp->fts_path);

   246 mem1:	free(sp);

   247 	return (NULL);

   248 }

   249 

   250 static void

   251 fts_load(sp, p)

   252 	FTS *sp;

   253 	FTSENT *p;

   254 {

   255 	int len;

   256 	char *cp;

   257 

   258 	/*

   259 	 * Load the stream structure for the next traversal.  Since we don't

   260 	 * actually enter the directory until after the preorder visit, set

   261 	 * the fts_accpath field specially so the chdir gets done to the right

   262 	 * place and the user can access the first node.  From fts_open it's

   263 	 * known that the path will fit.

   264 	 */

   265 	len = p->fts_pathlen = p->fts_namelen;

   266 	memmove(sp->fts_path, p->fts_name, len + 1);

   267 	if ((cp = strrchr(p->fts_name, '\\')) && (cp != p->fts_name || cp[1])) {

   268 		len = strlen(++cp);

   269 		memmove(p->fts_name, cp, len + 1);

   270 		p->fts_namelen = len;

   271 	}

   272 	p->fts_accpath = p->fts_path = sp->fts_path;

   273 	sp->fts_dev = p->fts_dev;

   274 }

   275 

   276 int

   277 fts_close(sp)

   278 	FTS *sp;

   279 {

   280 	FTSENT *freep, *p;

   281 	int saved_errno;

   282 

   283 	/*

   284 	 * This still works if we haven't read anything -- the dummy structure

   285 	 * points to the root list, so we step through to the end of the root

   286 	 * list which has a valid parent pointer.

   287 	 */

   288 	if (sp->fts_cur) {

   289 		for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {

   290 			freep = p;

   291 			p = p->fts_link != NULL ? p->fts_link : p->fts_parent;

   292 			free(freep);

   293 		}

   294 		free(p);

   295 	}

   296 

   297 	/* Free up child linked list, sort array, path buffer. */

   298 	if (sp->fts_child)

   299 		fts_lfree(sp->fts_child);

   300 	if (sp->fts_array)

   301 		free(sp->fts_array);

   302 	free(sp->fts_path);

   303 

   304 	/* Return to original directory, save errno if necessary. */

   305 	if (!ISSET(FTS_NOCHDIR)) {

   306 		saved_errno = fchdir(sp->fts_rfd) ? errno : 0;

   307 		(void)close(sp->fts_rfd);

   308 

   309 		/* Set errno and return. */

   310 		if (saved_errno != 0) {

   311 			/* Free up the stream pointer. */

   312 			free(sp);

   313 			errno = saved_errno;

   314 			return (-1);

   315 		}

   316 	}

   317 

   318 	/* Free up the stream pointer. */

   319 	free(sp);

   320 	return (0);

   321 }

   322 

   323 /*

   324  * Special case of "/" at the end of the path so that slashes aren't

   325  * appended which would cause paths to be written as "....//foo".

   326  */

   327 #define	NAPPEND(p)							\

   328 	(p->fts_path[p->fts_pathlen - 1] == '\\'				\

   329 	    ? p->fts_pathlen - 1 : p->fts_pathlen)

   330 

   331 FTSENT *

   332 fts_read(sp)

   333 	FTS *sp;

   334 {

   335 	FTSENT *p, *tmp;

   336 	int instr;

   337 	char *t;

   338 	int saved_errno;

   339 

   340 	/* If finished or unrecoverable error, return NULL. */

   341 	if (sp->fts_cur == NULL || ISSET(FTS_STOP))

   342 		return (NULL);

   343 

   344 	/* Set current node pointer. */

   345 	p = sp->fts_cur;

   346 

   347 	/* Save and zero out user instructions. */

   348 	instr = p->fts_instr;

   349 	p->fts_instr = FTS_NOINSTR;

   350 

   351 	/* Any type of file may be re-visited; re-stat and re-turn. */

   352 	if (instr == FTS_AGAIN) {

   353 		p->fts_info = fts_stat(sp, p, 0);

   354 		return (p);

   355 	}

   356 

   357 	/*

   358 	 * Following a symlink -- SLNONE test allows application to see

   359 	 * SLNONE and recover.  If indirecting through a symlink, have

   360 	 * keep a pointer to current location.  If unable to get that

   361 	 * pointer, follow fails.

   362 	 */

   363 	if (instr == FTS_FOLLOW &&

   364 	    (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {

   365 		p->fts_info = fts_stat(sp, p, 1);

   366 		if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

   367 			if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {

   368 				p->fts_errno = errno;

   369 				p->fts_info = FTS_ERR;

   370 			} else

   371 				p->fts_flags |= FTS_SYMFOLLOW;

   372 		}

   373 		return (p);

   374 	}

   375 

   376 	/* Directory in pre-order. */

   377 	if (p->fts_info == FTS_D) {

   378 		/* If skipped or crossed mount point, do post-order visit. */

   379 		if (instr == FTS_SKIP ||

   380 		    (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {

   381 			if (p->fts_flags & FTS_SYMFOLLOW)

   382 				(void)close(p->fts_symfd);

   383 			if (sp->fts_child) {

   384 				fts_lfree(sp->fts_child);

   385 				sp->fts_child = NULL;

   386 			}

   387 			p->fts_info = FTS_DP;

   388 			return (p);

   389 		}

   390 

   391 		/* Rebuild if only read the names and now traversing. */

   392 		if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {

   393 			CLR(FTS_NAMEONLY);

   394 			fts_lfree(sp->fts_child);

   395 			sp->fts_child = NULL;

   396 		}

   397 

   398 		/*

   399 		 * Cd to the subdirectory.

   400 		 *

   401 		 * If have already read and now fail to chdir, whack the list

   402 		 * to make the names come out right, and set the parent errno

   403 		 * so the application will eventually get an error condition.

   404 		 * Set the FTS_DONTCHDIR flag so that when we logically change

   405 		 * directories back to the parent we don't do a chdir.

   406 		 *

   407 		 * If haven't read do so.  If the read fails, fts_build sets

   408 		 * FTS_STOP or the fts_info field of the node.

   409 		 */

   410 		if (sp->fts_child != NULL) {

   411 			if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {

   412 				p->fts_errno = errno;

   413 				p->fts_flags |= FTS_DONTCHDIR;

   414 				for (p = sp->fts_child; p != NULL;

   415 				    p = p->fts_link)

   416 					p->fts_accpath =

   417 					    p->fts_parent->fts_accpath;

   418 			}

   419 		} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {

   420 			if (ISSET(FTS_STOP))

   421 				return (NULL);

   422 			return (p);

   423 		}

   424 		p = sp->fts_child;

   425 		sp->fts_child = NULL;

   426 		goto name;

   427 	}

   428 

   429 	/* Move to the next node on this level. */

   430 next:	tmp = p;

   431 	if ((p = p->fts_link) != NULL) {

   432 		free(tmp);

   433 

   434 		/*

   435 		 * If reached the top, return to the original directory (or

   436 		 * the root of the tree), and load the paths for the next root.

   437 		 */

   438 		if (p->fts_level == FTS_ROOTLEVEL) {

   439 			if (FCHDIR(sp, sp->fts_rfd)) {

   440 				SET(FTS_STOP);

   441 				return (NULL);

   442 			}

   443 			fts_load(sp, p);

   444 			return (sp->fts_cur = p);

   445 		}

   446 

   447 		/*

   448 		 * User may have called fts_set on the node.  If skipped,

   449 		 * ignore.  If followed, get a file descriptor so we can

   450 		 * get back if necessary.

   451 		 */

   452 		if (p->fts_instr == FTS_SKIP)

   453 			goto next;

   454 		if (p->fts_instr == FTS_FOLLOW) {

   455 			p->fts_info = fts_stat(sp, p, 1);

   456 			if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

   457 				if ((p->fts_symfd =

   458 				    open(".", O_RDONLY, 0)) < 0) {

   459 					p->fts_errno = errno;

   460 					p->fts_info = FTS_ERR;

   461 				} else

   462 					p->fts_flags |= FTS_SYMFOLLOW;

   463 			}

   464 			p->fts_instr = FTS_NOINSTR;

   465 		}

   466 

   467 name:		t = sp->fts_path + NAPPEND(p->fts_parent);

   468 		*t++ = '\\';

   469 		memmove(t, p->fts_name, p->fts_namelen + 1);

   470 		return (sp->fts_cur = p);

   471 	}

   472 

   473 	/* Move up to the parent node. */

   474 	p = tmp->fts_parent;

   475 	free(tmp);

   476 

   477 	if (p->fts_level == FTS_ROOTPARENTLEVEL) {

   478 		/*

   479 		 * Done; free everything up and set errno to 0 so the user

   480 		 * can distinguish between error and EOF.

   481 		 */

   482 		free(p);

   483 		errno = 0;

   484 		return (sp->fts_cur = NULL);

   485 	}

   486 

   487 	/* NUL terminate the pathname. */

   488 	sp->fts_path[p->fts_pathlen] = '\0';

   489 

   490 	/*

   491 	 * Return to the parent directory.  If at a root node or came through

   492 	 * a symlink, go back through the file descriptor.  Otherwise, cd up

   493 	 * one directory.

   494 	 */

   495 	if (p->fts_level == FTS_ROOTLEVEL) {

   496 		if (FCHDIR(sp, sp->fts_rfd)) {

   497 			SET(FTS_STOP);

   498 			return (NULL);

   499 		}

   500 	} else if (p->fts_flags & FTS_SYMFOLLOW) {

   501 		if (FCHDIR(sp, p->fts_symfd)) {

   502 			saved_errno = errno;

   503 			(void)close(p->fts_symfd);

   504 			errno = saved_errno;

   505 			SET(FTS_STOP);

   506 			return (NULL);

   507 		}

   508 		(void)close(p->fts_symfd);

   509 	} else if (!(p->fts_flags & FTS_DONTCHDIR) &&

   510 	    fts_safe_changedir(sp, p->fts_parent, -1, "..")) {

   511 		SET(FTS_STOP);

   512 		return (NULL);

   513 	}

   514 	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;

   515 	return (sp->fts_cur = p);

   516 }

   517 

   518 /*

   519  * Fts_set takes the stream as an argument although it's not used in this

   520  * implementation; it would be necessary if anyone wanted to add global

   521  * semantics to fts using fts_set.  An error return is allowed for similar

   522  * reasons.

   523  */

   524 /* ARGSUSED */

   525 #ifndef __SYMBIAN32__

   526 int

   527 fts_set(sp, p, instr)

   528 	FTS *sp;

   529 	FTSENT *p;

   530 	int instr;

   531 {

   532 	if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&

   533 	    instr != FTS_NOINSTR && instr != FTS_SKIP) {

   534 		errno = EINVAL;

   535 		return (1);

   536 	}

   537 	p->fts_instr = instr;

   538 	return (0);

   539 }

   540 

   541 

   542 FTSENT *

   543 fts_children(sp, instr)

   544 	FTS *sp;

   545 	int instr;

   546 {

   547 	FTSENT *p;

   548 	int fd;

   549 

   550 	if (instr != 0 && instr != FTS_NAMEONLY) {

   551 		errno = EINVAL;

   552 		return (NULL);

   553 	}

   554 

   555 	/* Set current node pointer. */

   556 	p = sp->fts_cur;

   557 

   558 	/*

   559 	 * Errno set to 0 so user can distinguish empty directory from

   560 	 * an error.

   561 	 */

   562 	errno = 0;

   563 

   564 	/* Fatal errors stop here. */

   565 	if (ISSET(FTS_STOP))

   566 		return (NULL);

   567 

   568 	/* Return logical hierarchy of user's arguments. */

   569 	if (p->fts_info == FTS_INIT)

   570 		return (p->fts_link);

   571 

   572 	/*

   573 	 * If not a directory being visited in pre-order, stop here.  Could

   574 	 * allow FTS_DNR, assuming the user has fixed the problem, but the

   575 	 * same effect is available with FTS_AGAIN.

   576 	 */

   577 	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)

   578 		return (NULL);

   579 

   580 	/* Free up any previous child list. */

   581 	if (sp->fts_child != NULL)

   582 		fts_lfree(sp->fts_child);

   583 

   584 	if (instr == FTS_NAMEONLY) {

   585 		SET(FTS_NAMEONLY);

   586 		instr = BNAMES;

   587 	} else

   588 		instr = BCHILD;

   589 

   590 	/*

   591 	 * If using chdir on a relative path and called BEFORE fts_read does

   592 	 * its chdir to the root of a traversal, we can lose -- we need to

   593 	 * chdir into the subdirectory, and we don't know where the current

   594 	 * directory is, so we can't get back so that the upcoming chdir by

   595 	 * fts_read will work.

   596 	 */

   597 	if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '\\' ||

   598 	    ISSET(FTS_NOCHDIR))

   599 		return (sp->fts_child = fts_build(sp, instr));

   600 

   601 	if ((fd = open(".", O_RDONLY, 0)) < 0)

   602 		return (NULL);

   603 	sp->fts_child = fts_build(sp, instr);

   604 	if (fchdir(fd))

   605 		return (NULL);

   606 	(void)close(fd);

   607 	return (sp->fts_child);

   608 }

   609 

   610 #ifndef fts_get_clientptr

   611 #error "fts_get_clientptr not defined"

   612 #endif

   613 

   614 void *

   615 (fts_get_clientptr)(FTS *sp)

   616 {

   617 

   618 	return (fts_get_clientptr(sp));

   619 }

   620 

   621 #ifndef fts_get_stream

   622 #error "fts_get_stream not defined"

   623 #endif

   624 

   625 FTS *

   626 (fts_get_stream)(FTSENT *p)

   627 {

   628 	return (fts_get_stream(p));

   629 }

   630 

   631 void

   632 fts_set_clientptr(FTS *sp, void *clientptr)

   633 {

   634 

   635 	sp->fts_clientptr = clientptr;

   636 }

   637 #endif // __SYMBIAN32__

   638 

   639 /*

   640  * This is the tricky part -- do not casually change *anything* in here.  The

   641  * idea is to build the linked list of entries that are used by fts_children

   642  * and fts_read.  There are lots of special cases.

   643  *

   644  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is

   645  * set and it's a physical walk (so that symbolic links can't be directories),

   646  * we can do things quickly.  First, if it's a 4.4BSD file system, the type

   647  * of the file is in the directory entry.  Otherwise, we assume that the number

   648  * of subdirectories in a node is equal to the number of links to the parent.

   649  * The former skips all stat calls.  The latter skips stat calls in any leaf

   650  * directories and for any files after the subdirectories in the directory have

   651  * been found, cutting the stat calls by about 2/3.

   652  */

   653 static FTSENT *

   654 fts_build(sp, type)

   655 	FTS *sp;

   656 	int type;

   657 {

   658 	struct dirent *dp;

   659 	FTSENT *p, *head;

   660 	int nitems;

   661 	FTSENT *cur, *tail;

   662 	DIR *dirp;

   663 	void *oldaddr;

   664 	size_t dnamlen;

   665 	int cderrno, descend, len, level, maxlen, nlinks, saved_errno,

   666 	    nostat, doadjust;

   667 	char *cp;

   668 

   669 	/* Set current node pointer. */

   670 	cur = sp->fts_cur;

   671 

   672 	/*

   673 	 * Open the directory for reading.  If this fails, we're done.

   674 	 * If being called from fts_read, set the fts_info field.

   675 	 */

   676 #ifdef FTS_WHITEOUT

   677 	if (ISSET(FTS_WHITEOUT))

   678 		oflag = DTF_NODUP | DTF_REWIND;

   679 	else

   680 		oflag = DTF_HIDEW | DTF_NODUP | DTF_REWIND;

   681 #else

   682 #define __opendir2(path, flag) opendir(path)

   683 #endif

   684 	if ((dirp = (DIR*)__opendir2(cur->fts_accpath, oflag)) == NULL) {

   685 		if (type == BREAD) {

   686 			cur->fts_info = FTS_DNR;

   687 			cur->fts_errno = errno;

   688 		}

   689 		return (NULL);

   690 	}

   691 

   692 	/*

   693 	 * Nlinks is the number of possible entries of type directory in the

   694 	 * directory if we're cheating on stat calls, 0 if we're not doing

   695 	 * any stat calls at all, -1 if we're doing stats on everything.

   696 	 */

   697 #ifndef __SYMBIAN32__	 

   698 	if (type == BNAMES) {

   699 		nlinks = 0;

   700 		/* Be quiet about nostat, GCC. */

   701 		nostat = 0;

   702 	} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {

   703 		if (fts_ufslinks(sp, cur))

   704 			nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);

   705 		else

   706 			nlinks = -1;

   707 		nostat = 1;

   708 	} else {

   709 		nlinks = -1;

   710 		nostat = 0;

   711 	}

   712 #else

   713 	if (type == BNAMES)

   714 		nlinks = 0;

   715 	else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {

   716 		nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);

   717 		nostat = 1;

   718 	} else {

   719 		nlinks = -1;

   720 		nostat = 0;

   721 	}	

   722 #endif //__SYMBIAN32__

   723 

   724 #ifdef notdef

   725 	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);

   726 	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",

   727 	    ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));

   728 #endif

   729 	/*

   730 	 * If we're going to need to stat anything or we want to descend

   731 	 * and stay in the directory, chdir.  If this fails we keep going,

   732 	 * but set a flag so we don't chdir after the post-order visit.

   733 	 * We won't be able to stat anything, but we can still return the

   734 	 * names themselves.  Note, that since fts_read won't be able to

   735 	 * chdir into the directory, it will have to return different path

   736 	 * names than before, i.e. "a/b" instead of "b".  Since the node

   737 	 * has already been visited in pre-order, have to wait until the

   738 	 * post-order visit to return the error.  There is a special case

   739 	 * here, if there was nothing to stat then it's not an error to

   740 	 * not be able to stat.  This is all fairly nasty.  If a program

   741 	 * needed sorted entries or stat information, they had better be

   742 	 * checking FTS_NS on the returned nodes.

   743 	 */

   744 	cderrno = 0;

   745 	if (nlinks || type == BREAD) {

   746 		if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {

   747 			if (nlinks && type == BREAD)

   748 				cur->fts_errno = errno;

   749 			cur->fts_flags |= FTS_DONTCHDIR;

   750 			descend = 0;

   751 			cderrno = errno;

   752 		} else

   753 			descend = 1;

   754 	} else

   755 		descend = 0;

   756 

   757 	/*

   758 	 * Figure out the max file name length that can be stored in the

   759 	 * current path -- the inner loop allocates more path as necessary.

   760 	 * We really wouldn't have to do the maxlen calculations here, we

   761 	 * could do them in fts_read before returning the path, but it's a

   762 	 * lot easier here since the length is part of the dirent structure.

   763 	 *

   764 	 * If not changing directories set a pointer so that can just append

   765 	 * each new name into the path.

   766 	 */

   767 	len = NAPPEND(cur);

   768 	if (ISSET(FTS_NOCHDIR)) {

   769 		cp = sp->fts_path + len;

   770 		*cp++ = '\\';

   771 	} else {

   772 		/* GCC, you're too verbose. */

   773 		cp = NULL;

   774 	}

   775 	len++;

   776 	maxlen = sp->fts_pathlen - len;

   777 

   778 	level = cur->fts_level + 1;

   779 

   780 	/* Read the directory, attaching each entry to the `link' pointer. */

   781 	doadjust = 0;

   782 	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {

   783 		dnamlen = dp->d_namlen;

   784 		if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))

   785 			continue;

   786 

   787 		if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL)

   788 			goto mem1;

   789 		if (dnamlen >= maxlen) {	/* include space for NUL */

   790 			oldaddr = sp->fts_path;

   791 			if (fts_palloc(sp, dnamlen + len + 1)) {

   792 				/*

   793 				 * No more memory for path or structures.  Save

   794 				 * errno, free up the current structure and the

   795 				 * structures already allocated.

   796 				 */

   797 mem1:				saved_errno = errno;

   798 				if (p)

   799 					free(p);

   800 				fts_lfree(head);

   801 				(void)closedir(dirp);

   802 				cur->fts_info = FTS_ERR;

   803 				SET(FTS_STOP);

   804 				errno = saved_errno;

   805 				return (NULL);

   806 			}

   807 			/* Did realloc() change the pointer? */

   808 			if (oldaddr != sp->fts_path) {

   809 				doadjust = 1;

   810 				if (ISSET(FTS_NOCHDIR))

   811 					cp = sp->fts_path + len;

   812 			}

   813 			maxlen = sp->fts_pathlen - len;

   814 		}

   815 

   816 		if (len + dnamlen >= USHRT_MAX) {

   817 			/*

   818 			 * In an FTSENT, fts_pathlen is a u_short so it is

   819 			 * possible to wraparound here.  If we do, free up

   820 			 * the current structure and the structures already

   821 			 * allocated, then error out with ENAMETOOLONG.

   822 			 */

   823 			free(p);

   824 			fts_lfree(head);

   825 			(void)closedir(dirp);

   826 			cur->fts_info = FTS_ERR;

   827 			SET(FTS_STOP);

   828 			errno = ENAMETOOLONG;

   829 			return (NULL);

   830 		}

   831 		p->fts_level = level;

   832 		p->fts_parent = sp->fts_cur;

   833 		p->fts_pathlen = len + dnamlen;

   834 

   835 #ifdef FTS_WHITEOUT

   836 		if (dp->d_type == DT_WHT)

   837 			p->fts_flags |= FTS_ISW;

   838 #endif

   839 

   840 		if (cderrno) {

   841 			if (nlinks) {

   842 				p->fts_info = FTS_NS;

   843 				p->fts_errno = cderrno;

   844 			} else

   845 				p->fts_info = FTS_NSOK;

   846 			p->fts_accpath = cur->fts_accpath;

   847 		} else if (nlinks == 0

   848 #ifdef DT_DIR

   849 		    || (nostat &&

   850 		    dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)

   851 #endif

   852 		    ) {

   853 			p->fts_accpath =

   854 			    ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;

   855 			p->fts_info = FTS_NSOK;

   856 		} else {

   857 			/* Build a file name for fts_stat to stat. */

   858 			if (ISSET(FTS_NOCHDIR)) {

   859 				p->fts_accpath = p->fts_path;

   860 				memmove(cp, p->fts_name, p->fts_namelen + 1);

   861 			} else

   862 				p->fts_accpath = p->fts_name;

   863 			/* Stat it. */

   864 			p->fts_info = fts_stat(sp, p, 0);

   865 

   866 			/* Decrement link count if applicable. */

   867 			if (nlinks > 0 && (p->fts_info == FTS_D ||

   868 			    p->fts_info == FTS_DC || p->fts_info == FTS_DOT))

   869 				--nlinks;

   870 		}

   871 

   872 		/* We walk in directory order so "ls -f" doesn't get upset. */

   873 		p->fts_link = NULL;

   874 		if (head == NULL)

   875 			head = tail = p;

   876 		else {

   877 			tail->fts_link = p;

   878 			tail = p;

   879 		}

   880 		++nitems;

   881 	}

   882 	if (dirp)

   883 		(void)closedir(dirp);

   884 

   885 	/*

   886 	 * If realloc() changed the address of the path, adjust the

   887 	 * addresses for the rest of the tree and the dir list.

   888 	 */

   889 	if (doadjust)

   890 		fts_padjust(sp, head);

   891 

   892 	/*

   893 	 * If not changing directories, reset the path back to original

   894 	 * state.

   895 	 */

   896 	if (ISSET(FTS_NOCHDIR)) {

   897 		if (len == sp->fts_pathlen || nitems == 0)

   898 			--cp;

   899 		*cp = '\0';

   900 	}

   901 

   902 	/*

   903 	 * If descended after called from fts_children or after called from

   904 	 * fts_read and nothing found, get back.  At the root level we use

   905 	 * the saved fd; if one of fts_open()'s arguments is a relative path

   906 	 * to an empty directory, we wind up here with no other way back.  If

   907 	 * can't get back, we're done.

   908 	 */

   909 	if (descend && (type == BCHILD || !nitems) &&

   910 	    (cur->fts_level == FTS_ROOTLEVEL ?

   911 	    FCHDIR(sp, sp->fts_rfd) :

   912 	    fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {

   913 		cur->fts_info = FTS_ERR;

   914 		SET(FTS_STOP);

   915 		return (NULL);

   916 	}

   917 

   918 	/* If didn't find anything, return NULL. */

   919 	if (!nitems) {

   920 		if (type == BREAD)

   921 			cur->fts_info = FTS_DP;

   922 		return (NULL);

   923 	}

   924 

   925 	/* Sort the entries. */

   926 	if (sp->fts_compar && nitems > 1)

   927 		head = fts_sort(sp, head, nitems);

   928 	return (head);

   929 }

   930 

   931 static u_short

   932 fts_stat(sp, p, follow)

   933 	FTS *sp;

   934 	FTSENT *p;

   935 	int follow;

   936 {

   937 #ifndef __SYMBIAN32__

   938 	FTSENT *t;

   939 #endif	

   940 	dev_t dev;

   941 	ino_t ino;

   942 	struct stat *sbp, sb;

   943 	int saved_errno;

   944 

   945 	/* If user needs stat info, stat buffer already allocated. */

   946 	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;

   947 

   948 #ifdef FTS_WHITEOUT

   949 	/* Check for whiteout. */

   950 	if (p->fts_flags & FTS_ISW) {

   951 		if (sbp != &sb) {

   952 			memset(sbp, '\0', sizeof(*sbp));

   953 			sbp->st_mode = S_IFWHT;

   954 		}

   955 		return (FTS_W);

   956 	}

   957 #endif

   958 

   959 	/*

   960 	 * If doing a logical walk, or application requested FTS_FOLLOW, do

   961 	 * a stat(2).  If that fails, check for a non-existent symlink.  If

   962 	 * fail, set the errno from the stat call.

   963 	 */

   964 	if (ISSET(FTS_LOGICAL) || follow) {

   965 		if (stat(p->fts_accpath, sbp)) {

   966 			saved_errno = errno;

   967 			if (!lstat(p->fts_accpath, sbp)) {

   968 				errno = 0;

   969 				return (FTS_SLNONE);

   970 			}

   971 			p->fts_errno = saved_errno;

   972 			goto err;

   973 		}

   974 	} else if (lstat(p->fts_accpath, sbp)) {

   975 		p->fts_errno = errno;

   976 err:		memset(sbp, 0, sizeof(struct stat));

   977 		return (FTS_NS);

   978 	}

   979 

   980 	if (S_ISDIR(sbp->st_mode)) {

   981 		/*

   982 		 * Set the device/inode.  Used to find cycles and check for

   983 		 * crossing mount points.  Also remember the link count, used

   984 		 * in fts_build to limit the number of stat calls.  It is

   985 		 * understood that these fields are only referenced if fts_info

   986 		 * is set to FTS_D.

   987 		 */

   988 		dev = p->fts_dev = sbp->st_dev;

   989 		ino = p->fts_ino = sbp->st_ino;

   990 		p->fts_nlink = sbp->st_nlink;

   991 

   992 		if (ISDOT(p->fts_name))

   993 			return (FTS_DOT);

   994 

   995 		/*

   996 		 * Cycle detection is done by brute force when the directory

   997 		 * is first encountered.  If the tree gets deep enough or the

   998 		 * number of symbolic links to directories is high enough,

   999 		 * something faster might be worthwhile.

  1000 		 */

  1001 #ifndef __SYMBIAN32__		 

  1002 		for (t = p->fts_parent;

  1003 		    t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)

  1004 			if (ino == t->fts_ino && dev == t->fts_dev) {

  1005 				p->fts_cycle = t;

  1006 				return (FTS_DC);

  1007 			}

  1008 #endif

  1009 		return (FTS_D);

  1010 	}

  1011 	if (S_ISLNK(sbp->st_mode))

  1012 		return (FTS_SL);

  1013 	if (S_ISREG(sbp->st_mode))

  1014 		return (FTS_F);

  1015 	return (FTS_DEFAULT);

  1016 }

  1017 

  1018 /*

  1019  * The comparison function takes pointers to pointers to FTSENT structures.

  1020  * Qsort wants a comparison function that takes pointers to void.

  1021  * (Both with appropriate levels of const-poisoning, of course!)

  1022  * Use a trampoline function to deal with the difference.

  1023  */

  1024 static int

  1025 fts_compar(const void *a, const void *b)

  1026 {

  1027 	FTS *parent;

  1028 

  1029 	parent = (*(const FTSENT * const *)a)->fts_fts;

  1030 	return (*parent->fts_compar)(a, b);

  1031 }

  1032 

  1033 static FTSENT *

  1034 fts_sort(sp, head, nitems)

  1035 	FTS *sp;

  1036 	FTSENT *head;

  1037 	int nitems;

  1038 {

  1039 	FTSENT **ap, *p;

  1040 

  1041 	/*

  1042 	 * Construct an array of pointers to the structures and call qsort(3).

  1043 	 * Reassemble the array in the order returned by qsort.  If unable to

  1044 	 * sort for memory reasons, return the directory entries in their

  1045 	 * current order.  Allocate enough space for the current needs plus

  1046 	 * 40 so don't realloc one entry at a time.

  1047 	 */

  1048 	if (nitems > sp->fts_nitems) {

  1049 		sp->fts_nitems = nitems + 40;

  1050 		if ((sp->fts_array = reallocf(sp->fts_array,

  1051 		    sp->fts_nitems * sizeof(FTSENT *))) == NULL) {

  1052 			sp->fts_nitems = 0;

  1053 			return (head);

  1054 		}

  1055 	}

  1056 	for (ap = sp->fts_array, p = head; p; p = p->fts_link)

  1057 		*ap++ = p;

  1058 	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);

  1059 	for (head = *(ap = sp->fts_array); --nitems; ++ap)

  1060 		ap[0]->fts_link = ap[1];

  1061 	ap[0]->fts_link = NULL;

  1062 	return (head);

  1063 }

  1064 

  1065 static FTSENT *

  1066 fts_alloc(sp, name, namelen)

  1067 	FTS *sp;

  1068 	char *name;

  1069 	int namelen;

  1070 {

  1071 	FTSENT *p;

  1072 	size_t len;

  1073 

  1074 	struct ftsent_withstat {

  1075 		FTSENT	ent;

  1076 		struct	stat statbuf;

  1077 	};

  1078 

  1079 	/*

  1080 	 * The file name is a variable length array and no stat structure is

  1081 	 * necessary if the user has set the nostat bit.  Allocate the FTSENT

  1082 	 * structure, the file name and the stat structure in one chunk, but

  1083 	 * be careful that the stat structure is reasonably aligned.

  1084 	 */

  1085 	if (ISSET(FTS_NOSTAT))

  1086 		len = sizeof(FTSENT) + namelen + 1;

  1087 	else

  1088 		len = sizeof(struct ftsent_withstat) + namelen + 1;

  1089 

  1090 	if ((p = malloc(len)) == NULL)

  1091 		return (NULL);

  1092 

  1093 	if (ISSET(FTS_NOSTAT)) {

  1094 		p->fts_name = (char *)(p + 1);

  1095 		p->fts_statp = NULL;

  1096 	} else {

  1097 		p->fts_name = (char *)((struct ftsent_withstat *)p + 1);

  1098 		p->fts_statp = &((struct ftsent_withstat *)p)->statbuf;

  1099 	}

  1100 

  1101 	/* Copy the name and guarantee NUL termination. */

  1102 	memcpy(p->fts_name, name, namelen);

  1103 	p->fts_name[namelen] = '\0';

  1104 	p->fts_namelen = namelen;

  1105 	p->fts_path = sp->fts_path;

  1106 	p->fts_errno = 0;

  1107 	p->fts_flags = 0;

  1108 	p->fts_instr = FTS_NOINSTR;

  1109 	p->fts_number = 0;

  1110 	p->fts_pointer = NULL;

  1111 	p->fts_fts = sp;

  1112 	return (p);

  1113 }

  1114 

  1115 static void

  1116 fts_lfree(head)

  1117 	FTSENT *head;

  1118 {

  1119 	FTSENT *p;

  1120 

  1121 	/* Free a linked list of structures. */

  1122 	while ((p = head)) {

  1123 		head = head->fts_link;

  1124 		free(p);

  1125 	}

  1126 }

  1127 

  1128 /*

  1129  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.

  1130  * Most systems will allow creation of paths much longer than MAXPATHLEN, even

  1131  * though the kernel won't resolve them.  Add the size (not just what's needed)

  1132  * plus 256 bytes so don't realloc the path 2 bytes at a time.

  1133  */

  1134 static int

  1135 fts_palloc(sp, more)