1 /* File tree walker functions.
2 Copyright (C) 1996-2004, 2006-2008, 2010 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26 # define alloca __builtin_alloca
32 #define NAMLEN(dirent) strlen ((dirent)->d_name)
43 # include <sys/param.h>
46 #include <atalk/ftw.h>
49 #define mempcpy(D, S, N) ((void *) ((char *) memcpy (D, S, N) + (N)))
57 # define __chdir chdir
59 # define __closedir closedir
61 # define __fchdir fchdir
63 # define __getcwd(P, N) xgetcwd ()
65 # define __mempcpy mempcpy
67 # define __opendir opendir
69 # define __readdir64 readdir
71 # define __tdestroy tdestroy
73 # define __tfind tfind
75 # define __tsearch tsearch
76 # undef internal_function
77 # define internal_function /* empty */
79 # define dirent64 dirent
81 # define MAX(a, b) ((a) > (b) ? (a) : (b))
85 # define __set_errno(Val) errno = (Val)
88 /* Support for the LFS API version. */
91 # define NFTW_NAME nftw
92 # define NFTW_OLD_NAME __old_nftw
93 # define NFTW_NEW_NAME __new_nftw
96 # define LXSTAT(V,f,sb) lstat (f,sb)
97 # define XSTAT(V,f,sb) stat (f,sb)
98 # define FXSTATAT(V,d,f,sb,m) fstatat (d, f, sb, m)
102 /* We define PATH_MAX if the system does not provide a definition.
103 This does not artificially limit any operation. PATH_MAX is simply
104 used as a guesstimate for the expected maximal path length.
105 Buffers will be enlarged if necessary. */
107 # define PATH_MAX 1024
125 /* Array with pointers to open directory streams. */
126 struct dir_data **dirstreams;
130 /* Buffer containing name of currently processed object. */
134 /* Passed as fourth argument to `nftw' callback. The `base' member
135 tracks the content of the `dirbuf'. */
138 /* Flags passed to `nftw' function. 0 for `ftw'. */
141 /* Conversion array for flag values. It is the identity mapping for
142 `nftw' calls, otherwise it maps the values to those known by
146 /* Callback function. We always use the `nftw' form. */
149 /* Device of starting point. Needed for FTW_MOUNT. */
152 /* Data structure for keeping fingerprints of already processed
153 object. This is needed when not using FTW_PHYS. */
158 /* Internally we use the FTW_* constants used for `nftw'. When invoked
159 as `ftw', map each flag to the subset of values used by `ftw'. */
160 static const int nftw_arr[] =
162 FTW_F, FTW_D, FTW_DNR, FTW_NS, FTW_SL, FTW_DP, FTW_SLN
165 static const int ftw_arr[] =
167 FTW_F, FTW_D, FTW_DNR, FTW_NS, FTW_F, FTW_D, FTW_NS
171 static dir_notification_func_t upfunc;
173 /* Forward declarations of local functions. */
174 static int ftw_dir (struct ftw_data *data, struct STAT *st,
175 struct dir_data *old_dir) internal_function;
177 typedef void (*__free_fn_t) (void *__nodep);
178 typedef struct node_t {
181 struct node_t *right;
185 static void tdestroy_recurse (node root, __free_fn_t freefct)
187 if (root->left != NULL)
188 tdestroy_recurse (root->left, freefct);
189 if (root->right != NULL)
190 tdestroy_recurse (root->right, freefct);
191 (*freefct) ((void *) root->key);
192 /* Free the node itself. */
196 static void mytdestroy (void *vroot, __free_fn_t freefct)
198 node root = (node) vroot;
201 tdestroy_recurse (root, freefct);
204 static char *mystpcpy(char *a, const char *b)
207 return (a + strlen(a));
210 static char *xgetcwd(void)
217 path_max = (unsigned) PATH_MAX;
218 path_max += 2; /* The getcwd docs say to do this. */
220 cwd = malloc (path_max);
222 while ((ret = getcwd (cwd, path_max)) == NULL && errno == ERANGE) {
224 cwd = realloc (cwd, path_max);
229 int save_errno = errno;
238 object_compare (const void *p1, const void *p2)
240 /* We don't need a sophisticated and useful comparison. We are only
241 interested in equality. However, we must be careful not to
242 accidentally compare `holes' in the structure. */
243 const struct known_object *kp1 = p1, *kp2 = p2;
245 cmp1 = (kp1->ino > kp2->ino) - (kp1->ino < kp2->ino);
248 return (kp1->dev > kp2->dev) - (kp1->dev < kp2->dev);
253 add_object (struct ftw_data *data, struct STAT *st)
255 struct known_object *newp = malloc (sizeof (struct known_object));
258 newp->dev = st->st_dev;
259 newp->ino = st->st_ino;
260 return __tsearch (newp, &data->known_objects, object_compare) ? 0 : -1;
265 find_object (struct ftw_data *data, struct STAT *st)
267 struct known_object obj;
268 obj.dev = st->st_dev;
269 obj.ino = st->st_ino;
270 return __tfind (&obj, &data->known_objects, object_compare) != NULL;
275 open_dir_stream (int *dfdp, struct ftw_data *data, struct dir_data *dirp)
279 if (data->dirstreams[data->actdir] != NULL)
281 /* Oh, oh. We must close this stream. Get all remaining
282 entries and store them as a list in the `content' member of
283 the `struct dir_data' variable. */
284 size_t bufsize = 1024;
285 char *buf = malloc (bufsize);
291 DIR *st = data->dirstreams[data->actdir]->stream;
295 while ((d = __readdir64 (st)) != NULL)
297 size_t this_len = NAMLEN (d);
298 if (actsize + this_len + 2 >= bufsize)
301 bufsize += MAX (1024, 2 * this_len);
302 newp = (char *) realloc (buf, bufsize);
305 /* No more memory. */
306 int save_err = errno;
308 __set_errno (save_err);
314 *((char *) __mempcpy (buf + actsize, d->d_name, this_len))
316 actsize += this_len + 1;
319 /* Terminate the list with an additional NUL byte. */
320 buf[actsize++] = '\0';
322 /* Shrink the buffer to what we actually need. */
323 data->dirstreams[data->actdir]->content = realloc (buf, actsize);
324 if (data->dirstreams[data->actdir]->content == NULL)
326 int save_err = errno;
328 __set_errno (save_err);
334 data->dirstreams[data->actdir]->stream = NULL;
335 data->dirstreams[data->actdir]->streamfd = -1;
336 data->dirstreams[data->actdir] = NULL;
341 /* Open the new stream. */
344 assert (data->dirstreams[data->actdir] == NULL);
346 if (dfdp != NULL && *dfdp != -1)
348 int fd = openat(*dfdp, data->dirbuf + data->ftw.base, O_RDONLY);
350 if (fd != -1 && (dirp->stream = fdopendir (fd)) == NULL)
357 if (data->flags & FTW_CHDIR)
359 name = data->dirbuf + data->ftw.base;
366 dirp->stream = __opendir (name);
369 if (dirp->stream == NULL)
373 dirp->streamfd = dirfd (dirp->stream);
374 dirp->content = NULL;
375 data->dirstreams[data->actdir] = dirp;
377 if (++data->actdir == data->maxdir)
387 process_entry (struct ftw_data *data, struct dir_data *dir, const char *name, size_t namlen)
394 if (name[0] == '.' && (name[1] == '\0'
395 || (name[1] == '.' && name[2] == '\0')))
396 /* Don't process the "." and ".." entries. */
399 new_buflen = data->ftw.base + namlen + 2;
400 if (data->dirbufsize < new_buflen)
402 /* Enlarge the buffer. */
405 data->dirbufsize = 2 * new_buflen;
406 newp = (char *) realloc (data->dirbuf, data->dirbufsize);
412 *((char *) __mempcpy (data->dirbuf + data->ftw.base, name, namlen)) = '\0';
415 if (dir->streamfd != -1)
416 statres = FXSTATAT (_STAT_VER, dir->streamfd, name, &st,
417 (data->flags & FTW_PHYS) ? AT_SYMLINK_NOFOLLOW : 0);
420 if ((data->flags & FTW_CHDIR) == 0)
423 statres = ((data->flags & FTW_PHYS)
424 ? LXSTAT (_STAT_VER, name, &st)
425 : XSTAT (_STAT_VER, name, &st));
430 if (errno != EACCES && errno != ENOENT)
432 else if (data->flags & FTW_PHYS)
436 if (dir->streamfd != -1)
437 statres = FXSTATAT (_STAT_VER, dir->streamfd, name, &st,
438 AT_SYMLINK_NOFOLLOW);
440 statres = LXSTAT (_STAT_VER, name, &st);
441 if (statres == 0 && S_ISLNK (st.st_mode))
449 if (S_ISDIR (st.st_mode))
451 else if (S_ISLNK (st.st_mode))
459 || !(data->flags & FTW_MOUNT) || st.st_dev == data->dev))
463 if ((data->flags & FTW_PHYS)
464 || (!find_object (data, &st)
465 /* Remember the object. */
466 && (result = add_object (data, &st)) == 0))
467 result = ftw_dir (data, &st, dir);
470 result = (*data->func) (data->dirbuf, &st, data->cvt_arr[flag],
474 if ((data->flags & FTW_ACTIONRETVAL) && result == FTW_SKIP_SUBTREE)
482 ftw_dir (struct ftw_data *data, struct STAT *st, struct dir_data *old_dir)
486 int previous_base = data->ftw.base;
490 /* Open the stream for this directory. This might require that
491 another stream has to be closed. */
492 result = open_dir_stream (old_dir == NULL ? NULL : &old_dir->streamfd,
497 /* We cannot read the directory. Signal this with a special flag. */
498 result = (*data->func) (data->dirbuf, st, FTW_DNR, &data->ftw);
503 /* First, report the directory (if not depth-first). */
504 if (!(data->flags & FTW_DEPTH))
506 result = (*data->func) (data->dirbuf, st, FTW_D, &data->ftw);
512 __closedir (dir.stream);
514 __set_errno (save_err);
516 if (data->actdir-- == 0)
517 data->actdir = data->maxdir - 1;
518 data->dirstreams[data->actdir] = NULL;
523 /* If necessary, change to this directory. */
524 if (data->flags & FTW_CHDIR)
526 if (__fchdir (dirfd (dir.stream)) < 0)
533 /* Next, update the `struct FTW' information. */
535 startp = data->dirbuf + strlen(data->dirbuf);
536 /* There always must be a directory name. */
537 assert (startp != data->dirbuf);
538 if (startp[-1] != '/')
540 data->ftw.base = startp - data->dirbuf;
542 while (dir.stream != NULL && (d = __readdir64 (dir.stream)) != NULL)
544 result = process_entry (data, &dir, d->d_name, NAMLEN (d));
549 if (dir.stream != NULL)
551 /* The stream is still open. I.e., we did not need more
552 descriptors. Simply close the stream now. */
553 int save_err = errno;
555 assert (dir.content == NULL);
557 __closedir (dir.stream);
559 __set_errno (save_err);
561 if (data->actdir-- == 0)
562 data->actdir = data->maxdir - 1;
563 data->dirstreams[data->actdir] = NULL;
568 char *runp = dir.content;
570 while (result == 0 && *runp != '\0')
572 char *endp = strchr (runp, '\0');
574 // XXX Should store the d_type values as well?!
575 result = process_entry (data, &dir, runp, endp - runp);
582 __set_errno (save_err);
585 if ((data->flags & FTW_ACTIONRETVAL) && result == FTW_SKIP_SIBLINGS)
588 /* Prepare the return, revert the `struct FTW' information. */
589 data->dirbuf[data->ftw.base - 1] = '\0';
593 data->ftw.base = previous_base;
595 /* Finally, if we process depth-first report the directory. */
596 if (result == 0 && (data->flags & FTW_DEPTH))
597 result = (*data->func) (data->dirbuf, st, FTW_DP, &data->ftw);
600 && (data->flags & FTW_CHDIR)
602 || ((data->flags & FTW_ACTIONRETVAL)
603 && (result != -1 && result != FTW_STOP))))
605 /* Change back to the parent directory. */
607 if (old_dir->stream != NULL)
608 if (__fchdir (dirfd (old_dir->stream)) == 0)
613 if (data->ftw.base == 1)
615 if (__chdir ("/") < 0)
619 if (__chdir ("..") < 0)
628 static int ftw_startup (const char *dir,
631 dir_notification_func_t up,
635 struct ftw_data data;
645 /* First make sure the parameters are reasonable. */
648 __set_errno (ENOENT);
652 data.maxdir = descriptors < 1 ? 1 : descriptors;
654 data.dirstreams = (struct dir_data **) alloca (data.maxdir
655 * sizeof (struct dir_data *));
656 memset (data.dirstreams, '\0', data.maxdir * sizeof (struct dir_data *));
658 /* PATH_MAX is always defined when we get here. */
659 data.dirbufsize = MAX (2 * strlen (dir), PATH_MAX);
660 data.dirbuf = (char *) malloc (data.dirbufsize);
661 if (data.dirbuf == NULL)
663 cp = mystpcpy (data.dirbuf, dir);
664 /* Strip trailing slashes. */
665 while (cp > data.dirbuf + 1 && cp[-1] == '/')
672 while (cp > data.dirbuf && cp[-1] != '/')
674 data.ftw.base = cp - data.dirbuf;
678 /* This assignment might seem to be strange but it is what we want.
679 The trick is that the first three arguments to the `ftw' and
680 `nftw' callback functions are equal. Therefore we can call in
681 every case the callback using the format of the `nftw' version
682 and get the correct result since the stack layout for a function
683 call in C allows this. */
684 data.func = (NFTW_FUNC_T) func;
686 /* Since we internally use the complete set of FTW_* values we need
687 to reduce the value range before calling a `ftw' callback. */
688 data.cvt_arr = is_nftw ? nftw_arr : ftw_arr;
690 /* No object known so far. */
691 data.known_objects = NULL;
693 /* Now go to the directory containing the initial file/directory. */
694 if (flags & FTW_CHDIR)
696 /* We have to be able to go back to the current working
697 directory. The best way to do this is to use a file
699 cwdfd = open (".", O_RDONLY);
702 /* Try getting the directory name. This can be needed if
703 the current directory is executable but not readable. */
705 /* GNU extension ahead. */
706 cwd = __getcwd(NULL, 0);
711 else if (data.maxdir > 1)
712 /* Account for the file descriptor we use here. */
715 if (data.ftw.base > 0)
717 /* Change to the directory the file is in. In data.dirbuf
718 we have a writable copy of the file name. Just NUL
719 terminate it for now and change the directory. */
720 if (data.ftw.base == 1)
721 /* I.e., the file is in the root directory. */
722 result = __chdir ("/");
725 char ch = data.dirbuf[data.ftw.base - 1];
726 data.dirbuf[data.ftw.base - 1] = '\0';
727 result = __chdir (data.dirbuf);
728 data.dirbuf[data.ftw.base - 1] = ch;
733 /* Get stat info for start directory. */
738 if (data.flags & FTW_CHDIR)
740 name = data.dirbuf + data.ftw.base;
747 if (((flags & FTW_PHYS)
748 ? LXSTAT (_STAT_VER, name, &st)
749 : XSTAT (_STAT_VER, name, &st)) < 0)
751 if (!(flags & FTW_PHYS)
753 && LXSTAT (_STAT_VER, name, &st) == 0
754 && S_ISLNK (st.st_mode))
755 result = (*data.func) (data.dirbuf, &st, data.cvt_arr[FTW_SLN],
758 /* No need to call the callback since we cannot say anything
764 if (S_ISDIR (st.st_mode))
766 /* Remember the device of the initial directory in case
767 FTW_MOUNT is given. */
768 data.dev = st.st_dev;
770 /* We know this directory now. */
771 if (!(flags & FTW_PHYS))
772 result = add_object (&data, &st);
775 result = ftw_dir (&data, &st, NULL);
779 int flag = S_ISLNK (st.st_mode) ? FTW_SL : FTW_F;
781 result = (*data.func) (data.dirbuf, &st, data.cvt_arr[flag],
786 if ((flags & FTW_ACTIONRETVAL)
787 && (result == FTW_SKIP_SUBTREE || result == FTW_SKIP_SIBLINGS))
791 /* Return to the start directory (if necessary). */
794 int save_err = errno;
797 __set_errno (save_err);
799 else if (cwd != NULL)
801 int save_err = errno;
804 __set_errno (save_err);
807 /* Free all memory. */
810 mytdestroy (data.known_objects, free);
812 __set_errno (save_err);
820 int NFTW_NAME(const char *path,
822 dir_notification_func_t up,
826 return ftw_startup (path, 1, func, up, descriptors, flags);