fts.c@ 371

Last change on this file since 371 was 370, checked in by bird, 19 years ago
o Ported all kmk builtins to win32. o Fixed serveral bugs in kmk builtins. o Probably broke both linux, bsd and OS/2. :-)
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 33.7 KB

Line
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	* 3. All advertising materials mentioning features or use of this software
14	* must display the following acknowledgement:
15	* This product includes software developed by the University of
16	* California, Berkeley and its contributors.
17	* 4. Neither the name of the University nor the names of its contributors
18	* may be used to endorse or promote products derived from this software
19	* without specific prior written permission.
20	*
21	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31	* SUCH DAMAGE.
32	*
33	* $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
34	*/
35
36	#if 0
37	#if defined(LIBC_SCCS) && !defined(lint)
38	static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
39	#endif /* LIBC_SCCS and not lint */
40
41	#include <sys/cdefs.h>
42	__FBSDID("$FreeBSD: src/lib/libc/gen/fts.c,v 1.27 2004/06/08 06:23:23 das Exp $");
43	#endif
44
45	//#include "namespace.h"
46	#ifndef _MSC_VER
47	#include <sys/param.h>
48	#include <sys/mount.h>
49	#endif
50	#include <sys/stat.h>
51
52	#include <dirent.h>
53	#include <errno.h>
54	#include <fcntl.h>
55	#include <stdlib.h>
56	#include <string.h>
57	#ifndef _MSC_VER
58	#include <unistd.h>
59	#else
60	#include "mscfakes.h"
61	#define dirfd(dir) -1
62	#endif
63	#include "ftsfake.h"
64	//#include "un-namespace.h"
65
66	static FTSENT fts_alloc(FTS , char *, int);
67	static FTSENT fts_build(FTS , int);
68	static void fts_lfree(FTSENT *);
69	static void fts_load(FTS , FTSENT );
70	static size_t fts_maxarglen(char * const *);
71	static void fts_padjust(FTS , FTSENT );
72	static int fts_palloc(FTS *, size_t);
73	static FTSENT fts_sort(FTS , FTSENT *, int);
74	static u_short fts_stat(FTS , FTSENT , int);
75	static int fts_safe_changedir(FTS , FTSENT , int, char *);
76	static int fts_ufslinks(FTS , const FTSENT );
77
78	#if defined(__EMX__) \|\| defined(_MSC_VER)
79	# define NEED_STRRSLASH
80	# define IS_SLASH(ch) ( (ch) == '/' \|\| (ch) == '\\' )
81	#else
82	# define HAVE_FCHDIR
83	# define IS_SLASH(ch) ( (ch) == '/' )
84	#endif
85
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	#ifdef HAVE_FCHDIR
93	#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
94	#else
95	#define FCHDIR(sp, rdir) (!ISSET(FTS_NOCHDIR) && chdir(rdir))
96	#endif
97
98	/* fts_build flags */
99	#define BCHILD 1 /* fts_children */
100	#define BNAMES 2 /* fts_children, names only */
101	#define BREAD 3 /* fts_read */
102
103	/*
104	* Internal representation of an FTS, including extra implementation
105	* details. The FTS returned from fts_open points to this structure's
106	* ftsp_fts member (and can be cast to an _fts_private as required)
107	*/
108	struct _fts_private {
109	FTS ftsp_fts;
110	#ifndef _MSC_VER
111	struct statfs ftsp_statfs;
112	#endif
113	dev_t ftsp_dev;
114	int ftsp_linksreliable;
115	};
116
117	#if !defined(__EMX__) && !defined(_MSC_VER)
118	/*
119	* The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it
120	* knows that a directory could not possibly have subdirectories. This
121	* is decided by looking at the link count: a subdirectory would
122	* increment its parent's link count by virtue of its own ".." entry.
123	* This assumption only holds for UFS-like filesystems that implement
124	* links and directories this way, so we must punt for others.
125	*/
126
127	static const char *ufslike_filesystems[] = {
128	"ufs",
129	"nfs",
130	"nfs4",
131	"ext2fs",
132	0
133	};
134	#endif /* !__EMX__ && !_MSC_VER */
135
136	FTS *
137	fts_open(argv, options, compar)
138	char * const *argv;
139	int options;
140	int (compar)(const FTSENT const , const FTSENT const *);
141	{
142	struct _fts_private *priv;
143	FTS *sp;
144	FTSENT p, root;
145	int nitems;
146	FTSENT parent, tmp;
147	int len;
148
149	/* Options check. */
150	if (options & ~FTS_OPTIONMASK) {
151	errno = EINVAL;
152	return (NULL);
153	}
154
155	/* Allocate/initialize the stream. */
156	if ((priv = malloc(sizeof(*priv))) == NULL)
157	return (NULL);
158	memset(priv, 0, sizeof(*priv));
159	sp = &priv->ftsp_fts;
160	sp->fts_compar = compar;
161	sp->fts_options = options;
162
163	/* Shush, GCC. */
164	tmp = NULL;
165
166	/* Logical walks turn on NOCHDIR; symbolic links are too hard. */
167	if (ISSET(FTS_LOGICAL))
168	SET(FTS_NOCHDIR);
169
170	/*
171	* Start out with 1K of path space, and enough, in any case,
172	* to hold the user's paths.
173	*/
174	if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
175	goto mem1;
176
177	/* Allocate/initialize root's parent. */
178	if ((parent = fts_alloc(sp, "", 0)) == NULL)
179	goto mem2;
180	parent->fts_level = FTS_ROOTPARENTLEVEL;
181
182	/* Allocate/initialize root(s). */
183	for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
184	/* Don't allow zero-length paths. */
185	if ((len = strlen(*argv)) == 0) {
186	errno = ENOENT;
187	goto mem3;
188	}
189
190	p = fts_alloc(sp, *argv, len);
191	p->fts_level = FTS_ROOTLEVEL;
192	p->fts_parent = parent;
193	p->fts_accpath = p->fts_name;
194	p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
195
196	/* Command-line "." and ".." are real directories. */
197	if (p->fts_info == FTS_DOT)
198	p->fts_info = FTS_D;
199
200	/*
201	* If comparison routine supplied, traverse in sorted
202	* order; otherwise traverse in the order specified.
203	*/
204	if (compar) {
205	p->fts_link = root;
206	root = p;
207	} else {
208	p->fts_link = NULL;
209	if (root == NULL)
210	tmp = root = p;
211	else {
212	tmp->fts_link = p;
213	tmp = p;
214	}
215	}
216	}
217	if (compar && nitems > 1)
218	root = fts_sort(sp, root, nitems);
219
220	/*
221	* Allocate a dummy pointer and make fts_read think that we've just
222	* finished the node before the root(s); set p->fts_info to FTS_INIT
223	* so that everything about the "current" node is ignored.
224	*/
225	if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
226	goto mem3;
227	sp->fts_cur->fts_link = root;
228	sp->fts_cur->fts_info = FTS_INIT;
229
230	/*
231	* If using chdir(2), grab a file descriptor pointing to dot to ensure
232	* that we can get back here; this could be avoided for some paths,
233	* but almost certainly not worth the effort. Slashes, symbolic links,
234	* and ".." are all fairly nasty problems. Note, if we can't get the
235	* descriptor we run anyway, just more slowly.
236	*/
237	#ifdef HAVE_FCHDIR
238	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = _open(".", O_RDONLY, 0)) < 0)
239	#else
240	if (!ISSET(FTS_NOCHDIR) && (sp->fts_rdir = getcwd(NULL, 0)) != NULL)
241	#endif
242	SET(FTS_NOCHDIR);
243
244	return (sp);
245
246	mem3: fts_lfree(root);
247	free(parent);
248	mem2: free(sp->fts_path);
249	mem1: free(sp);
250	return (NULL);
251	}
252
253	#ifdef NEED_STRRSLASH
254	static char strrslash(register char psz)
255	{
256	register char ch;
257	char *pszLast = NULL;
258	for (; (ch = *psz); psz++)
259	switch (ch)
260	{
261	case '/':
262	case '\\':
263	case ':':
264	pszLast = psz;
265	break;
266	}
267	return pszLast;
268	}
269	#endif
270
271	static void
272	fts_load(sp, p)
273	FTS *sp;
274	FTSENT *p;
275	{
276	int len;
277	char *cp;
278
279	/*
280	* Load the stream structure for the next traversal. Since we don't
281	* actually enter the directory until after the preorder visit, set
282	* the fts_accpath field specially so the chdir gets done to the right
283	* place and the user can access the first node. From fts_open it's
284	* known that the path will fit.
285	*/
286	len = p->fts_pathlen = p->fts_namelen;
287	memmove(sp->fts_path, p->fts_name, len + 1);
288	#ifdef NEED_STRRSLASH
289	if ((cp = strrslash(p->fts_name)) && (cp != p->fts_name \|\| cp[1])) {
290	#else
291	if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name \|\| cp[1])) {
292	#endif
293	len = strlen(++cp);
294	memmove(p->fts_name, cp, len + 1);
295	p->fts_namelen = len;
296	}
297	p->fts_accpath = p->fts_path = sp->fts_path;
298	sp->fts_dev = p->fts_dev;
299	}
300
301	int
302	fts_close(sp)
303	FTS *sp;
304	{
305	FTSENT freep, p;
306	int saved_errno;
307
308	/*
309	* This still works if we haven't read anything -- the dummy structure
310	* points to the root list, so we step through to the end of the root
311	* list which has a valid parent pointer.
312	*/
313	if (sp->fts_cur) {
314	for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
315	freep = p;
316	p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
317	free(freep);
318	}
319	free(p);
320	}
321
322	/* Free up child linked list, sort array, path buffer. */
323	if (sp->fts_child)
324	fts_lfree(sp->fts_child);
325	if (sp->fts_array)
326	free(sp->fts_array);
327	free(sp->fts_path);
328
329	/* Return to original directory, save errno if necessary. */
330	if (!ISSET(FTS_NOCHDIR)) {
331	#ifdef HAVE_FCHDIR
332	saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
333	(void)_close(sp->fts_rfd);
334	#else
335	saved_errno = chdir(sp->fts_rdir) ? errno : 0;
336	free(sp->fts_rdir); sp->fts_rdir = NULL;
337	#endif
338
339	/* Set errno and return. */
340	if (saved_errno != 0) {
341	/* Free up the stream pointer. */
342	free(sp);
343	errno = saved_errno;
344	return (-1);
345	}
346	}
347
348	/* Free up the stream pointer. */
349	free(sp);
350	return (0);
351	}
352
353
354	/*
355	* Special case of "/" at the end of the path so that slashes aren't
356	* appended which would cause paths to be written as "....//foo".
357	*/
358	#define NAPPEND(p) \
359	(IS_SLASH(p->fts_path[p->fts_pathlen - 1]) \
360	? p->fts_pathlen - 1 : p->fts_pathlen)
361
362	FTSENT *
363	fts_read(sp)
364	FTS *sp;
365	{
366	FTSENT p, tmp;
367	int instr;
368	char *t;
369	int saved_errno;
370
371	/* If finished or unrecoverable error, return NULL. */
372	if (sp->fts_cur == NULL \|\| ISSET(FTS_STOP))
373	return (NULL);
374
375	/* Set current node pointer. */
376	p = sp->fts_cur;
377
378	/* Save and zero out user instructions. */
379	instr = p->fts_instr;
380	p->fts_instr = FTS_NOINSTR;
381
382	/* Any type of file may be re-visited; re-stat and re-turn. */
383	if (instr == FTS_AGAIN) {
384	p->fts_info = fts_stat(sp, p, 0);
385	return (p);
386	}
387
388	/*
389	* Following a symlink -- SLNONE test allows application to see
390	* SLNONE and recover. If indirecting through a symlink, have
391	* keep a pointer to current location. If unable to get that
392	* pointer, follow fails.
393	*/
394	if (instr == FTS_FOLLOW &&
395	(p->fts_info == FTS_SL \|\| p->fts_info == FTS_SLNONE)) {
396	p->fts_info = fts_stat(sp, p, 1);
397	if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
398	#ifdef HAVE_FCHDIR
399	if ((p->fts_symfd = _open(".", O_RDONLY, 0)) < 0) {
400	p->fts_errno = errno;
401	p->fts_info = FTS_ERR;
402	} else
403	p->fts_flags \|= FTS_SYMFOLLOW;
404	#endif
405	}
406	return (p);
407	}
408
409	/* Directory in pre-order. */
410	if (p->fts_info == FTS_D) {
411	/* If skipped or crossed mount point, do post-order visit. */
412	if (instr == FTS_SKIP \|\|
413	(ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
414	#ifdef HAVE_FCHDIR
415	if (p->fts_flags & FTS_SYMFOLLOW)
416	(void)_close(p->fts_symfd);
417	#endif
418	if (sp->fts_child) {
419	fts_lfree(sp->fts_child);
420	sp->fts_child = NULL;
421	}
422	p->fts_info = FTS_DP;
423	return (p);
424	}
425
426	/* Rebuild if only read the names and now traversing. */
427	if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
428	CLR(FTS_NAMEONLY);
429	fts_lfree(sp->fts_child);
430	sp->fts_child = NULL;
431	}
432
433	/*
434	* Cd to the subdirectory.
435	*
436	* If have already read and now fail to chdir, whack the list
437	* to make the names come out right, and set the parent errno
438	* so the application will eventually get an error condition.
439	* Set the FTS_DONTCHDIR flag so that when we logically change
440	* directories back to the parent we don't do a chdir.
441	*
442	* If haven't read do so. If the read fails, fts_build sets
443	* FTS_STOP or the fts_info field of the node.
444	*/
445	if (sp->fts_child != NULL) {
446	if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
447	p->fts_errno = errno;
448	p->fts_flags \|= FTS_DONTCHDIR;
449	for (p = sp->fts_child; p != NULL;
450	p = p->fts_link)
451	p->fts_accpath =
452	p->fts_parent->fts_accpath;
453	}
454	} else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
455	if (ISSET(FTS_STOP))
456	return (NULL);
457	return (p);
458	}
459	p = sp->fts_child;
460	sp->fts_child = NULL;
461	goto name;
462	}
463
464	/* Move to the next node on this level. */
465	next: tmp = p;
466	if ((p = p->fts_link) != NULL) {
467	free(tmp);
468
469	/*
470	* If reached the top, return to the original directory (or
471	* the root of the tree), and load the paths for the next root.
472	*/
473	if (p->fts_level == FTS_ROOTLEVEL) {
474	#ifdef HAVE_FCHDIR
475	if (FCHDIR(sp, sp->fts_rfd)) {
476	#else
477	if (FCHDIR(sp, sp->fts_rdir)) {
478	#endif
479	SET(FTS_STOP);
480	return (NULL);
481	}
482	fts_load(sp, p);
483	return (sp->fts_cur = p);
484	}
485
486	/*
487	* User may have called fts_set on the node. If skipped,
488	* ignore. If followed, get a file descriptor so we can
489	* get back if necessary.
490	*/
491	if (p->fts_instr == FTS_SKIP)
492	goto next;
493	if (p->fts_instr == FTS_FOLLOW) {
494	p->fts_info = fts_stat(sp, p, 1);
495	if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
496	#ifdef HAVE_FCHDIR
497	if ((p->fts_symfd =
498	_open(".", O_RDONLY, 0)) < 0) {
499	p->fts_errno = errno;
500	p->fts_info = FTS_ERR;
501	} else
502	p->fts_flags \|= FTS_SYMFOLLOW;
503	#endif
504	}
505	p->fts_instr = FTS_NOINSTR;
506	}
507
508	name: t = sp->fts_path + NAPPEND(p->fts_parent);
509	*t++ = '/';
510	memmove(t, p->fts_name, p->fts_namelen + 1);
511	return (sp->fts_cur = p);
512	}
513
514	/* Move up to the parent node. */
515	p = tmp->fts_parent;
516	free(tmp);
517
518	if (p->fts_level == FTS_ROOTPARENTLEVEL) {
519	/*
520	* Done; free everything up and set errno to 0 so the user
521	* can distinguish between error and EOF.
522	*/
523	free(p);
524	errno = 0;
525	return (sp->fts_cur = NULL);
526	}
527
528	/* NUL terminate the pathname. */
529	sp->fts_path[p->fts_pathlen] = '\0';
530
531	/*
532	* Return to the parent directory. If at a root node or came through
533	* a symlink, go back through the file descriptor. Otherwise, cd up
534	* one directory.
535	*/
536	if (p->fts_level == FTS_ROOTLEVEL) {
537	#ifdef HAVE_FCHDIR
538	if (FCHDIR(sp, sp->fts_rfd)) {
539	#else
540	if (FCHDIR(sp, sp->fts_rdir)) {
541	#endif
542	SET(FTS_STOP);
543	return (NULL);
544	}
545	#ifdef HAVE_FCHDIR
546	} else if (p->fts_flags & FTS_SYMFOLLOW) {
547	if (FCHDIR(sp, p->fts_symfd)) {
548	saved_errno = errno;
549	(void)_close(p->fts_symfd);
550	errno = saved_errno;
551	SET(FTS_STOP);
552	return (NULL);
553	}
554	(void)_close(p->fts_symfd);
555	#else
556	(void)saved_errno;
557	#endif
558	} else if (!(p->fts_flags & FTS_DONTCHDIR) &&
559	fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
560	SET(FTS_STOP);
561	return (NULL);
562	}
563	p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
564	return (sp->fts_cur = p);
565	}
566
567	/*
568	* Fts_set takes the stream as an argument although it's not used in this
569	* implementation; it would be necessary if anyone wanted to add global
570	* semantics to fts using fts_set. An error return is allowed for similar
571	* reasons.
572	*/
573	/* ARGSUSED */
574	int
575	fts_set(sp, p, instr)
576	FTS *sp;
577	FTSENT *p;
578	int instr;
579	{
580	if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
581	instr != FTS_NOINSTR && instr != FTS_SKIP) {
582	errno = EINVAL;
583	return (1);
584	}
585	p->fts_instr = instr;
586	return (0);
587	}
588
589	FTSENT *
590	fts_children(sp, instr)
591	FTS *sp;
592	int instr;
593	{
594	FTSENT *p;
595	#ifdef HAVE_FCHDIR
596	int fd;
597	#else
598	char *pszRoot;
599	int rc;
600	#endif
601	if (instr != 0 && instr != FTS_NAMEONLY) {
602	errno = EINVAL;
603	return (NULL);
604	}
605
606	/* Set current node pointer. */
607	p = sp->fts_cur;
608
609	/*
610	* Errno set to 0 so user can distinguish empty directory from
611	* an error.
612	*/
613	errno = 0;
614
615	/* Fatal errors stop here. */
616	if (ISSET(FTS_STOP))
617	return (NULL);
618
619	/* Return logical hierarchy of user's arguments. */
620	if (p->fts_info == FTS_INIT)
621	return (p->fts_link);
622
623	/*
624	* If not a directory being visited in pre-order, stop here. Could
625	* allow FTS_DNR, assuming the user has fixed the problem, but the
626	* same effect is available with FTS_AGAIN.
627	*/
628	if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
629	return (NULL);
630
631	/* Free up any previous child list. */
632	if (sp->fts_child != NULL)
633	fts_lfree(sp->fts_child);
634
635	if (instr == FTS_NAMEONLY) {
636	SET(FTS_NAMEONLY);
637	instr = BNAMES;
638	} else
639	instr = BCHILD;
640
641	/*
642	* If using chdir on a relative path and called BEFORE fts_read does
643	* its chdir to the root of a traversal, we can lose -- we need to
644	* chdir into the subdirectory, and we don't know where the current
645	* directory is, so we can't get back so that the upcoming chdir by
646	* fts_read will work.
647	*/
648	if (p->fts_level != FTS_ROOTLEVEL \|\| IS_SLASH(p->fts_accpath[0]) \|\|
649	ISSET(FTS_NOCHDIR))
650	return (sp->fts_child = fts_build(sp, instr));
651
652	#ifdef HAVE_FCHDIR
653	if ((fd = _open(".", O_RDONLY, 0)) < 0)
654	#else
655	if ((pszRoot = getcwd(NULL, 0)) == NULL)
656	#endif
657	return (NULL);
658	sp->fts_child = fts_build(sp, instr);
659	#ifdef HAVE_FCHDIR
660	if (fchdir(fd))
661	return (NULL);
662	(void)_close(fd);
663	#else
664	rc = chdir(pszRoot);
665	free(pszRoot);
666	if (rc)
667	return NULL;
668	#endif
669	return (sp->fts_child);
670	}
671
672	#ifndef fts_get_clientptr
673	#error "fts_get_clientptr not defined"
674	#endif
675
676	void *
677	(fts_get_clientptr)(FTS *sp)
678	{
679
680	return (fts_get_clientptr(sp));
681	}
682
683	#ifndef fts_get_stream
684	#error "fts_get_stream not defined"
685	#endif
686
687	FTS *
688	(fts_get_stream)(FTSENT *p)
689	{
690	return (fts_get_stream(p));
691	}
692
693	void
694	fts_set_clientptr(FTS sp, void clientptr)
695	{
696
697	sp->fts_clientptr = clientptr;
698	}
699
700	/*
701	* This is the tricky part -- do not casually change anything in here. The
702	* idea is to build the linked list of entries that are used by fts_children
703	* and fts_read. There are lots of special cases.
704	*
705	* The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
706	* set and it's a physical walk (so that symbolic links can't be directories),
707	* we can do things quickly. First, if it's a 4.4BSD file system, the type
708	* of the file is in the directory entry. Otherwise, we assume that the number
709	* of subdirectories in a node is equal to the number of links to the parent.
710	* The former skips all stat calls. The latter skips stat calls in any leaf
711	* directories and for any files after the subdirectories in the directory have
712	* been found, cutting the stat calls by about 2/3.
713	*/
714	static FTSENT *
715	fts_build(sp, type)
716	FTS *sp;
717	int type;
718	{
719	struct dirent *dp;
720	FTSENT p, head;
721	int nitems;
722	FTSENT cur, tail;
723	DIR *dirp;
724	void *oldaddr;
725	int dnamlen;
726	int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno,
727	nostat, doadjust;
728	char *cp;
729
730	/* Set current node pointer. */
731	cur = sp->fts_cur;
732
733	/*
734	* Open the directory for reading. If this fails, we're done.
735	* If being called from fts_read, set the fts_info field.
736	*/
737	#ifdef FTS_WHITEOUT
738	if (ISSET(FTS_WHITEOUT))
739	oflag = DTF_NODUP \| DTF_REWIND;
740	else
741	oflag = DTF_HIDEW \| DTF_NODUP \| DTF_REWIND;
742	#else
743	(void)(oflag);
744	#define __opendir2(path, flag) opendir(path)
745	#endif
746	if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
747	if (type == BREAD) {
748	cur->fts_info = FTS_DNR;
749	cur->fts_errno = errno;
750	}
751	return (NULL);
752	}
753
754	/*
755	* Nlinks is the number of possible entries of type directory in the
756	* directory if we're cheating on stat calls, 0 if we're not doing
757	* any stat calls at all, -1 if we're doing stats on everything.
758	*/
759	if (type == BNAMES) {
760	nlinks = 0;
761	/* Be quiet about nostat, GCC. */
762	nostat = 0;
763	} else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
764	if (fts_ufslinks(sp, cur))
765	nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
766	else
767	nlinks = -1;
768	nostat = 1;
769	} else {
770	nlinks = -1;
771	nostat = 0;
772	}
773
774	#ifdef notdef
775	(void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
776	(void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
777	ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
778	#endif
779	/*
780	* If we're going to need to stat anything or we want to descend
781	* and stay in the directory, chdir. If this fails we keep going,
782	* but set a flag so we don't chdir after the post-order visit.
783	* We won't be able to stat anything, but we can still return the
784	* names themselves. Note, that since fts_read won't be able to
785	* chdir into the directory, it will have to return different path
786	* names than before, i.e. "a/b" instead of "b". Since the node
787	* has already been visited in pre-order, have to wait until the
788	* post-order visit to return the error. There is a special case
789	* here, if there was nothing to stat then it's not an error to
790	* not be able to stat. This is all fairly nasty. If a program
791	* needed sorted entries or stat information, they had better be
792	* checking FTS_NS on the returned nodes.
793	*/
794	cderrno = 0;
795	if (nlinks \|\| type == BREAD) {
796	#ifdef HAVE_FCHDIR
797	if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
798	#else
799	if (fts_safe_changedir(sp, cur, dirfd(dirp), cur->fts_accpath)) {
800	#endif
801	if (nlinks && type == BREAD)
802	cur->fts_errno = errno;
803	cur->fts_flags \|= FTS_DONTCHDIR;
804	descend = 0;
805	cderrno = errno;
806	} else
807	descend = 1;
808	} else
809	descend = 0;
810
811	/*
812	* Figure out the max file name length that can be stored in the
813	* current path -- the inner loop allocates more path as necessary.
814	* We really wouldn't have to do the maxlen calculations here, we
815	* could do them in fts_read before returning the path, but it's a
816	* lot easier here since the length is part of the dirent structure.
817	*
818	* If not changing directories set a pointer so that can just append
819	* each new name into the path.
820	*/
821	len = NAPPEND(cur);
822	if (ISSET(FTS_NOCHDIR)) {
823	cp = sp->fts_path + len;
824	*cp++ = '/';
825	} else {
826	/* GCC, you're too verbose. */
827	cp = NULL;
828	}
829	len++;
830	maxlen = sp->fts_pathlen - len;
831
832	level = cur->fts_level + 1;
833
834	/* Read the directory, attaching each entry to the `link' pointer. */
835	doadjust = 0;
836	for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
837	#ifdef _MSC_VER
838	dnamlen = strlen(dp->d_name);
839	#else
840	dnamlen = dp->d_namlen;
841	#endif
842	if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
843	continue;
844
845	if ((p = fts_alloc(sp, dp->d_name, (int)dnamlen)) == NULL)
846	goto mem1;
847	if (dnamlen >= maxlen) { /* include space for NUL */
848	oldaddr = sp->fts_path;
849	if (fts_palloc(sp, dnamlen + len + 1)) {
850	/*
851	* No more memory for path or structures. Save
852	* errno, free up the current structure and the
853	* structures already allocated.
854	*/
855	mem1: saved_errno = errno;
856	if (p)
857	free(p);
858	fts_lfree(head);
859	(void)closedir(dirp);
860	cur->fts_info = FTS_ERR;
861	SET(FTS_STOP);
862	errno = saved_errno;
863	return (NULL);
864	}
865	/* Did realloc() change the pointer? */
866	if (oldaddr != sp->fts_path) {
867	doadjust = 1;
868	if (ISSET(FTS_NOCHDIR))
869	cp = sp->fts_path + len;
870	}
871	maxlen = sp->fts_pathlen - len;
872	}
873
874	if (len + dnamlen >= USHRT_MAX) {
875	/*
876	* In an FTSENT, fts_pathlen is a u_short so it is
877	* possible to wraparound here. If we do, free up
878	* the current structure and the structures already
879	* allocated, then error out with ENAMETOOLONG.
880	*/
881	free(p);
882	fts_lfree(head);
883	(void)closedir(dirp);
884	cur->fts_info = FTS_ERR;
885	SET(FTS_STOP);
886	errno = ENAMETOOLONG;
887	return (NULL);
888	}
889	p->fts_level = level;
890	p->fts_parent = sp->fts_cur;
891	p->fts_pathlen = len + dnamlen;
892
893	#ifdef FTS_WHITEOUT
894	if (dp->d_type == DT_WHT)
895	p->fts_flags \|= FTS_ISW;
896	#endif
897
898	if (cderrno) {
899	if (nlinks) {
900	p->fts_info = FTS_NS;
901	p->fts_errno = cderrno;
902	} else
903	p->fts_info = FTS_NSOK;
904	p->fts_accpath = cur->fts_accpath;
905	} else if (nlinks == 0
906	#ifdef DT_DIR
907	\|\| (nostat &&
908	dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
909	#endif
910	) {
911	p->fts_accpath =
912	ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
913	p->fts_info = FTS_NSOK;
914	} else {
915	/* Build a file name for fts_stat to stat. */
916	if (ISSET(FTS_NOCHDIR)) {
917	p->fts_accpath = p->fts_path;
918	memmove(cp, p->fts_name, p->fts_namelen + 1);
919	} else
920	p->fts_accpath = p->fts_name;
921	/* Stat it. */
922	p->fts_info = fts_stat(sp, p, 0);
923
924	/* Decrement link count if applicable. */
925	if (nlinks > 0 && (p->fts_info == FTS_D \|\|
926	p->fts_info == FTS_DC \|\| p->fts_info == FTS_DOT))
927	--nlinks;
928	}
929
930	/* We walk in directory order so "ls -f" doesn't get upset. */
931	p->fts_link = NULL;
932	if (head == NULL)
933	head = tail = p;
934	else {
935	tail->fts_link = p;
936	tail = p;
937	}
938	++nitems;
939	}
940	if (dirp)
941	(void)closedir(dirp);
942
943	/*
944	* If realloc() changed the address of the path, adjust the
945	* addresses for the rest of the tree and the dir list.
946	*/
947	if (doadjust)
948	fts_padjust(sp, head);
949
950	/*
951	* If not changing directories, reset the path back to original
952	* state.
953	*/
954	if (ISSET(FTS_NOCHDIR)) {
955	if (len == sp->fts_pathlen \|\| nitems == 0)
956	--cp;
957	*cp = '\0';
958	}
959
960	/*
961	* If descended after called from fts_children or after called from
962	* fts_read and nothing found, get back. At the root level we use
963	* the saved fd; if one of fts_open()'s arguments is a relative path
964	* to an empty directory, we wind up here with no other way back. If
965	* can't get back, we're done.
966	*/
967	if (descend && (type == BCHILD \|\| !nitems) &&
968	(cur->fts_level == FTS_ROOTLEVEL ?
969	#ifdef HAVE_FCHDIR
970	FCHDIR(sp, sp->fts_rfd) :
971	#else
972	FCHDIR(sp, sp->fts_rdir) :
973	#endif
974	fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
975	cur->fts_info = FTS_ERR;
976	SET(FTS_STOP);
977	return (NULL);
978	}
979
980	/* If didn't find anything, return NULL. */
981	if (!nitems) {
982	if (type == BREAD)
983	cur->fts_info = FTS_DP;
984	return (NULL);
985	}
986
987	/* Sort the entries. */
988	if (sp->fts_compar && nitems > 1)
989	head = fts_sort(sp, head, nitems);
990	return (head);
991	}
992
993	static u_short
994	fts_stat(sp, p, follow)
995	FTS *sp;
996	FTSENT *p;
997	int follow;
998	{
999	FTSENT *t;
1000	dev_t dev;
1001	ino_t ino;
1002	struct stat *sbp, sb;
1003	int saved_errno;
1004
1005	/* If user needs stat info, stat buffer already allocated. */
1006	sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
1007
1008	#ifdef FTS_WHITEOUT
1009	/* Check for whiteout. */
1010	if (p->fts_flags & FTS_ISW) {
1011	if (sbp != &sb) {
1012	memset(sbp, '\0', sizeof(*sbp));
1013	sbp->st_mode = S_IFWHT;
1014	}
1015	return (FTS_W);
1016	}
1017	#endif
1018
1019	/*
1020	* If doing a logical walk, or application requested FTS_FOLLOW, do
1021	* a stat(2). If that fails, check for a non-existent symlink. If
1022	* fail, set the errno from the stat call.
1023	*/
1024	if (ISSET(FTS_LOGICAL) \|\| follow) {
1025	if (stat(p->fts_accpath, sbp)) {
1026	saved_errno = errno;
1027	if (!lstat(p->fts_accpath, sbp)) {
1028	errno = 0;
1029	return (FTS_SLNONE);
1030	}
1031	p->fts_errno = saved_errno;
1032	goto err;
1033	}
1034	} else if (lstat(p->fts_accpath, sbp)) {
1035	p->fts_errno = errno;
1036	err: memset(sbp, 0, sizeof(struct stat));
1037	return (FTS_NS);
1038	}
1039
1040	if (S_ISDIR(sbp->st_mode)) {
1041	/*
1042	* Set the device/inode. Used to find cycles and check for
1043	* crossing mount points. Also remember the link count, used
1044	* in fts_build to limit the number of stat calls. It is
1045	* understood that these fields are only referenced if fts_info
1046	* is set to FTS_D.
1047	*/
1048	dev = p->fts_dev = sbp->st_dev;
1049	ino = p->fts_ino = sbp->st_ino;
1050	p->fts_nlink = sbp->st_nlink;
1051
1052	if (ISDOT(p->fts_name))
1053	return (FTS_DOT);
1054
1055	/*
1056	* Cycle detection is done by brute force when the directory
1057	* is first encountered. If the tree gets deep enough or the
1058	* number of symbolic links to directories is high enough,
1059	* something faster might be worthwhile.
1060	*/
1061	for (t = p->fts_parent;
1062	t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1063	if (ino == t->fts_ino && dev == t->fts_dev) {
1064	p->fts_cycle = t;
1065	return (FTS_DC);
1066	}
1067	return (FTS_D);
1068	}
1069	if (S_ISLNK(sbp->st_mode))
1070	return (FTS_SL);
1071	if (S_ISREG(sbp->st_mode))
1072	return (FTS_F);
1073	return (FTS_DEFAULT);
1074	}
1075
1076	/*
1077	* The comparison function takes pointers to pointers to FTSENT structures.
1078	* Qsort wants a comparison function that takes pointers to void.
1079	* (Both with appropriate levels of const-poisoning, of course!)
1080	* Use a trampoline function to deal with the difference.
1081	*/
1082	static int
1083	fts_compar(const void a, const void b)
1084	{
1085	FTS *parent;
1086
1087	parent = ((const FTSENT const *)a)->fts_fts;
1088	return (*parent->fts_compar)(a, b);
1089	}
1090
1091	static FTSENT *
1092	fts_sort(sp, head, nitems)
1093	FTS *sp;
1094	FTSENT *head;
1095	int nitems;
1096	{
1097	FTSENT *ap, p;
1098
1099	/*
1100	* Construct an array of pointers to the structures and call qsort(3).
1101	* Reassemble the array in the order returned by qsort. If unable to
1102	* sort for memory reasons, return the directory entries in their
1103	* current order. Allocate enough space for the current needs plus
1104	* 40 so don't realloc one entry at a time.
1105	*/
1106	if (nitems > sp->fts_nitems) {
1107	sp->fts_nitems = nitems + 40;
1108	if ((sp->fts_array = reallocf(sp->fts_array,
1109	sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
1110	sp->fts_nitems = 0;
1111	return (head);
1112	}
1113	}
1114	for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1115	*ap++ = p;
1116	qsort(sp->fts_array, nitems, sizeof(FTSENT *), fts_compar);
1117	for (head = *(ap = sp->fts_array); --nitems; ++ap)
1118	ap[0]->fts_link = ap[1];
1119	ap[0]->fts_link = NULL;
1120	return (head);
1121	}
1122
1123	static FTSENT *
1124	fts_alloc(sp, name, namelen)
1125	FTS *sp;
1126	char *name;
1127	int namelen;
1128	{
1129	FTSENT *p;
1130	size_t len;
1131
1132	struct ftsent_withstat {
1133	FTSENT ent;
1134	struct stat statbuf;
1135	};
1136
1137	/*
1138	* The file name is a variable length array and no stat structure is
1139	* necessary if the user has set the nostat bit. Allocate the FTSENT
1140	* structure, the file name and the stat structure in one chunk, but
1141	* be careful that the stat structure is reasonably aligned.
1142	*/
1143	if (ISSET(FTS_NOSTAT))
1144	len = sizeof(FTSENT) + namelen + 1;
1145	else
1146	len = sizeof(struct ftsent_withstat) + namelen + 1;
1147
1148	if ((p = malloc(len)) == NULL)
1149	return (NULL);
1150
1151	if (ISSET(FTS_NOSTAT)) {
1152	p->fts_name = (char *)(p + 1);
1153	p->fts_statp = NULL;
1154	} else {
1155	p->fts_name = (char )((struct ftsent_withstat )p + 1);
1156	p->fts_statp = &((struct ftsent_withstat *)p)->statbuf;
1157	}
1158
1159	/* Copy the name and guarantee NUL termination. */
1160	memcpy(p->fts_name, name, namelen);
1161	p->fts_name[namelen] = '\0';
1162	p->fts_namelen = namelen;
1163	p->fts_path = sp->fts_path;
1164	p->fts_errno = 0;
1165	p->fts_flags = 0;
1166	p->fts_instr = FTS_NOINSTR;
1167	p->fts_number = 0;
1168	p->fts_pointer = NULL;
1169	p->fts_fts = sp;
1170	return (p);
1171	}
1172
1173	static void
1174	fts_lfree(head)
1175	FTSENT *head;
1176	{
1177	FTSENT *p;
1178
1179	/* Free a linked list of structures. */
1180	while ((p = head)) {
1181	head = head->fts_link;
1182	free(p);
1183	}
1184	}
1185
1186	/*
1187	* Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1188	* Most systems will allow creation of paths much longer than MAXPATHLEN, even
1189	* though the kernel won't resolve them. Add the size (not just what's needed)
1190	* plus 256 bytes so don't realloc the path 2 bytes at a time.
1191	*/
1192	static int
1193	fts_palloc(sp, more)
1194	FTS *sp;
1195	size_t more;
1196	{
1197
1198	sp->fts_pathlen += more + 256;
1199	/*
1200	* Check for possible wraparound. In an FTS, fts_pathlen is
1201	* a signed int but in an FTSENT it is an unsigned short.
1202	* We limit fts_pathlen to USHRT_MAX to be safe in both cases.
1203	*/
1204	if (sp->fts_pathlen < 0 \|\| sp->fts_pathlen >= USHRT_MAX) {
1205	if (sp->fts_path)
1206	free(sp->fts_path);
1207	sp->fts_path = NULL;
1208	errno = ENAMETOOLONG;
1209	return (1);
1210	}
1211	sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
1212	return (sp->fts_path == NULL);
1213	}
1214
1215	/*
1216	* When the path is realloc'd, have to fix all of the pointers in structures
1217	* already returned.
1218	*/
1219	static void
1220	fts_padjust(sp, head)
1221	FTS *sp;
1222	FTSENT *head;
1223	{
1224	FTSENT *p;
1225	char *addr = sp->fts_path;
1226
1227	#define ADJUST(p) do { \
1228	if ((p)->fts_accpath != (p)->fts_name) { \
1229	(p)->fts_accpath = \
1230	(char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1231	} \
1232	(p)->fts_path = addr; \
1233	} while (0)
1234	/* Adjust the current set of children. */
1235	for (p = sp->fts_child; p; p = p->fts_link)
1236	ADJUST(p);
1237
1238	/* Adjust the rest of the tree, including the current level. */
1239	for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1240	ADJUST(p);
1241	p = p->fts_link ? p->fts_link : p->fts_parent;
1242	}
1243	}
1244
1245	static size_t
1246	fts_maxarglen(argv)
1247	char * const *argv;
1248	{
1249	size_t len, max;
1250
1251	for (max = 0; *argv; ++argv)
1252	if ((len = strlen(*argv)) > max)
1253	max = len;
1254	return (max + 1);
1255	}
1256
1257	/*
1258	* Change to dir specified by fd or p->fts_accpath without getting
1259	* tricked by someone changing the world out from underneath us.
1260	* Assumes p->fts_dev and p->fts_ino are filled in.
1261	*/
1262	static int
1263	fts_safe_changedir(sp, p, fd, path)
1264	FTS *sp;
1265	FTSENT *p;
1266	int fd;
1267	char *path;
1268	{
1269	int ret, oerrno, newfd;
1270	struct stat sb;
1271
1272	newfd = fd;
1273	if (ISSET(FTS_NOCHDIR))
1274	return (0);
1275	#ifdef HAVE_FCHDIR
1276	if (fd < 0 && (newfd = _open(path, O_RDONLY, 0)) < 0)
1277	return (-1);
1278	if (_fstat(newfd, &sb)) {
1279	#else
1280	(void)newfd;
1281	if (stat(path, &sb)) {
1282	#endif
1283	ret = -1;
1284	goto bail;
1285	}
1286	if (p->fts_dev != sb.st_dev \|\| p->fts_ino != sb.st_ino) {
1287	errno = ENOENT; /* disinformation */
1288	ret = -1;
1289	goto bail;
1290	}
1291	#ifdef HAVE_FCHDIR
1292	ret = fchdir(newfd);
1293	#else
1294	ret = chdir(path);
1295	#endif
1296	bail:
1297	#ifdef HAVE_FCHDIR
1298	oerrno = errno;
1299	if (fd < 0)
1300	(void)_close(newfd);
1301	errno = oerrno;
1302	#else
1303	(void)oerrno;
1304	#endif
1305	return (ret);
1306	}
1307
1308	/*
1309	* Check if the filesystem for "ent" has UFS-style links.
1310	*/
1311	static int
1312	fts_ufslinks(FTS sp, const FTSENT ent)
1313	{
1314	struct _fts_private *priv;
1315	const char **cpp;
1316
1317	priv = (struct _fts_private *)sp;
1318	#if defined(__EMX__) \|\| defined(_MSC_VER)
1319	/* we don't have reliable links */
1320	priv->ftsp_linksreliable = 0;
1321	(void)cpp;
1322	#else
1323	/*
1324	* If this node's device is different from the previous, grab
1325	* the filesystem information, and decide on the reliability
1326	* of the link information from this filesystem for stat(2)
1327	* avoidance.
1328	*/
1329	if (priv->ftsp_dev != ent->fts_dev) {
1330	if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) {
1331	priv->ftsp_dev = ent->fts_dev;
1332	priv->ftsp_linksreliable = 0;
1333	for (cpp = ufslike_filesystems; *cpp; cpp++) {
1334	if (strcmp(priv->ftsp_statfs.f_fstypename,
1335	*cpp) == 0) {
1336	priv->ftsp_linksreliable = 1;
1337	break;
1338	}
1339	}
1340	} else {
1341	priv->ftsp_linksreliable = 0;
1342	}
1343	}
1344	#endif
1345	return (priv->ftsp_linksreliable);
1346	}
1347

Note: See TracBrowser for help on using the repository browser.

source: kBuild/trunk/src/gmake/kmkbuiltin/fts.c@ 371

Download in other formats: