source: trunk/src/kmk/kmkbuiltin/fts.c@ 2114

Last change on this file since 2114 was 2113, checked in by bird, 17 years ago

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