/*	$Id: fts.c,v 1.5 2000/11/25 16:33:36 arnd Exp $	*/

//

// © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

//

/*-

 * Copyright (c) 1990, 1993, 1994

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

 *

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

 * modification, are permitted provided that the following conditions

 * are met:

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

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

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

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

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

 * 3. All advertising materials mentioning features or use of this software

 *    must display the following acknowledgement:

 *	This product includes software developed by the University of

 *	California, Berkeley and its contributors.

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

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

 *    without specific prior written permission.

 *

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

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

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

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

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

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

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

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

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

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

 * SUCH DAMAGE.

 */

#define __NO_FCHDIR /* Fix me! fchdir fn not yet implemented (AH) */

#define _BSD_SOURCE

#include <sys/param.h>

#include <sys/stat.h>

#include <dirent.h>

#ifndef __SYMBIAN32__

#include <sys/direntx.h>

#endif

#include <errno.h>

#include <fcntl.h>

#include "fts.h"

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

static FTSENT	*fts_alloc(FTS *, char *, size_t);

static FTSENT	*fts_build(FTS *, int);

static void	 fts_lfree(FTSENT *);

static void	 fts_load(FTS *, FTSENT *);

static size_t	 fts_maxarglen(char * const *);

static void	 fts_padjust(FTS *, FTSENT *);

static int	 fts_palloc(FTS *, size_t);

static FTSENT	*fts_sort(FTS *, FTSENT *, size_t);

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

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

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

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

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

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

#ifndef __NO_FCHDIR

#define	CHDIR(sp, path)	(!ISSET(FTS_NOCHDIR) && chdir(path))

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

#else

#define	CHDIR(sp, path)	(0)

#define	FCHDIR(sp, fd)	(0)

#endif

#ifdef __SYMBIAN32__

#ifdef __WINSCW__

#pragma warn_unusedarg off

#endif//__WINSCW__

#ifdef __ARMCC__

// Turn off the 'extended constant initialiser used' warning

#pragma diag_remark 1294

#endif

#endif//__SYMBIAN32__

/* fts_build flags */

#define	BCHILD		1		/* fts_children */

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

#define	BREAD		3		/* fts_read */

static void

fts_load(sp, p)

	FTS *sp;

	register FTSENT *p;

{

	register size_t len;

	register char *cp;

	/*

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

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

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

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

	 * known that the path will fit.

	 */

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

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

	if (!(cp = strrchr(p->fts_name, '\\')))

		cp = strrchr(p->fts_name, '\\');

	if (cp && (cp != p->fts_name || cp[1])) {

		len = strlen(++cp);

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

		p->fts_namelen = len;

	}

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

	sp->fts_dev = p->fts_dev;

}

/*

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

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

 */

#define	NAPPEND(p)							\

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

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

/*

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

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

 * and fts_read.  There are lots of special cases.

 *

 * 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),

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

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

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

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

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

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

 */

static FTSENT *

fts_build(sp, type)

	register FTS *sp;

	int type;

{

	register struct dirent *dp;

	register FTSENT *p, *head;

	register size_t nitems;

	FTSENT *cur, *tail;

	DIR *dirp;

	void *oldaddr;

	int cderrno, descend, level, nlinks, /* oflag, */ saved_errno,

	    nostat = 0, doadjust;

	size_t len, maxlen;

	char *cp = NULL;

	/* Set current node pointer. */

	cur = sp->fts_cur;

	/*

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

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

	 */

#ifdef FTS_WHITEOUT

	if (ISSET(FTS_WHITEOUT))

		oflag = DTF_NODUP|DTF_REWIND;

	else

		oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;

#else

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

#endif

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

		if (type == BREAD) {

			cur->fts_info = FTS_DNR;

			cur->fts_errno = errno;

		}

		return (NULL);

	}

	/*

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

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

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

	 */

	if (type == BNAMES)

		nlinks = 0;

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

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

		nostat = 1;

	} else {

		nlinks = -1;

		nostat = 0;

	}

#ifdef notdef

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

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

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

#endif

	/*

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

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

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

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

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

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

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

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

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

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

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

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

	 * checking FTS_NS on the returned nodes.

	 */

	cderrno = 0;

	if (nlinks || type == BREAD) {

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

			if (nlinks && type == BREAD)

				cur->fts_errno = errno;

			cur->fts_flags |= FTS_DONTCHDIR;

			descend = 0;

			cderrno = errno;

			(void)closedir(dirp);

			dirp = NULL;

		} else

			descend = 1;

	} else

		descend = 0;

	/*

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

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

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

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

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

	 *

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

	 * each new name into the path.

	 */

	len = NAPPEND(cur);

	if (ISSET(FTS_NOCHDIR)) {

		cp = sp->fts_path + len;

		*cp++ = '\\';

	}

	len++;

	maxlen = sp->fts_pathlen - len;

	level = cur->fts_level + 1;

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

	doadjust = 0;

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

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

			continue;

		if ((p = fts_alloc(sp, dp->d_name, dp->d_namlen)) == NULL)

			goto mem1;

		if (dp->d_namlen >= maxlen) {	/* include space for NUL */

			oldaddr = sp->fts_path;

			if (fts_palloc(sp, dp->d_namlen +len + 1)) {

				/*

				 * No more memory for path or structures.  Save

				 * errno, free up the current structure and the

				 * structures already allocated.

				 */

mem1:				saved_errno = errno;

				if (p)

					free(p);

				fts_lfree(head);

				(void)closedir(dirp);

				cur->fts_info = FTS_ERR;

				SET(FTS_STOP);

				errno = saved_errno;

				return (NULL);

			}

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

			if (oldaddr != sp->fts_path) {

				doadjust = 1;

				if (ISSET(FTS_NOCHDIR))

					cp = sp->fts_path + len;

			}

			maxlen = sp->fts_pathlen - len;

		}

		if (len + dp->d_namlen >= USHRT_MAX) {

			/*

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

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

			 * the current structure and the structures already

			 * allocated, then error out with ENAMETOOLONG.

			 */

			free(p);

			fts_lfree(head);

			(void)closedir(dirp);

			cur->fts_info = FTS_ERR;

			SET(FTS_STOP);

			errno = ENAMETOOLONG;

			return (NULL);

		}

		p->fts_level = level;

		p->fts_parent = sp->fts_cur;

		p->fts_pathlen = len + dp->d_namlen;

#ifdef FTS_WHITEOUT

		if (dp->d_type == DT_WHT)

			p->fts_flags |= FTS_ISW;

#endif

		if (nlinks == 0 || (nostat &&

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

		    ) {

			p->fts_accpath =

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

			p->fts_info = FTS_NSOK;

		} else {

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

			if (ISSET(FTS_NOCHDIR)) {

				p->fts_accpath = p->fts_path;

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

			} else

				p->fts_accpath = p->fts_name;

			/* Stat it. */

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

			/* Decrement link count if applicable. */

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

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

				--nlinks;

		}

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

		p->fts_link = NULL;

		if (head == NULL)

			head = tail = p;

		else {

			tail->fts_link = p;

			tail = p;

		}

		++nitems;

	}

	if (dirp)

		(void)closedir(dirp);

	/*

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

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

	 */

	if (doadjust)

		fts_padjust(sp, head);

	/*

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

	 * state.

	 */

	if (ISSET(FTS_NOCHDIR)) {

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

			--cp;

		*cp = '\0';

	}

	/*

	 * If descended after called from fts_children or after called from

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

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

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

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

	 */

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

	    (cur->fts_level == FTS_ROOTLEVEL ?

	    FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {

		cur->fts_info = FTS_ERR;

		SET(FTS_STOP);

		return (NULL);

	}

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

	if (!nitems && (head == NULL)) {

		if (type == BREAD)

			cur->fts_info = FTS_DP;

		return (NULL);

	}

	/* Sort the entries. */

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

		head = fts_sort(sp, head, nitems);

	return (head);

}

static u_short

fts_stat(sp, p, follow)

	FTS *sp;

	register FTSENT *p;

	int follow;

{

	register dev_t dev;

	register ino_t ino;

	struct stat *sbp, sb;

	int saved_errno;

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

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

#ifdef FTS_WHITEOUT

	/* check for whiteout */

	if (p->fts_flags & FTS_ISW) {

		if (sbp != &sb) {

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

			sbp->st_mode = S_IFWHT;

		}

		return (FTS_W);

	}

#endif

	/*

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

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

	 * fail, set the errno from the stat call.

	 */

	if (ISSET(FTS_LOGICAL) || follow) {

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

			saved_errno = errno;

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

				errno = 0;

				return (FTS_SLNONE);

			}

			p->fts_errno = saved_errno;

			goto err;

		}

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

		p->fts_errno = errno;

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

		return (FTS_NS);

	}

	if (S_ISDIR(sbp->st_mode)) {

		/*

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

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

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

		 * understood that these fields are only referenced if fts_info

		 * is set to FTS_D.

		 */

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

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

		p->fts_nlink = sbp->st_nlink;

		if (ISDOT(p->fts_name))

			return (FTS_DOT);

		/*

		 * Cycle detection is done by brute force when the directory

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

		 * number of symbolic links to directories is high enough,

		 * something faster might be worthwhile.

		 */

#ifndef __SYMBIAN32__		 

		//fts_ino is set

		for (t = p->fts_parent;

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

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

				p->fts_cycle = t;

				return (FTS_DC);

			}

#endif

		return (FTS_D);

	}

	if (S_ISLNK(sbp->st_mode))

		return (FTS_SL);

	if (S_ISREG(sbp->st_mode))

		return (FTS_F);

	return (FTS_DEFAULT);

}

typedef int (*qsType)(const void *, const void *);

static FTSENT *

fts_sort(sp, head, nitems)

	FTS *sp;

	FTSENT *head;

	register size_t nitems;

{

	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 don't realloc one entry at a time.

	 */

	if (nitems > sp->fts_nitems) {

		struct _ftsent **a;

		sp->fts_nitems = nitems + 40;

		if ((a = realloc(sp->fts_array,

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

			if (sp->fts_array)

				free(sp->fts_array);

			sp->fts_array = NULL;

			sp->fts_nitems = 0;

			return (head);

		}

		sp->fts_array = a;

	}

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

		*ap++ = p;

	qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), 

		(qsType)sp->fts_compar);

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

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

	ap[0]->fts_link = NULL;

	return (head);

}

static FTSENT *

fts_alloc(sp, name, namelen)

	FTS *sp;

	char *name;

	register size_t namelen;

{

	register FTSENT *p;

	size_t len;