source: trunk/src/gmake/kmkbuiltin/fts.c@ 631

Last change on this file since 631 was 621, checked in by bird, 19 years ago

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