14.7. Walking File System Trees There are two functions available that make it easy for applications to look at all of the files in a directory, including files in subdirectories. Recursing through all entries in a tree (such as a file system) is often called walking the structure, and is the reason these two functions are called ftw() and nftw(), which stand for file tree walk and new file tree walk. As the names suggest, nftw() is an enhanced version of ftw. 14.7.1. Using ftw() #include <ftw.h> int ftw(const char *dir, ftwFunctionPointer callback, int depth);
The ftw() function starts in the directory dir and calls the function pointed to by callback for every file it finds in that directory and any subdirectories. The function is called for all file types, including symbolic links and directories. The implementation of ftw() opens every directory it finds (using up a file descriptor), and, to improve performance, it does not close them until it is finished reading all of the entries in that directory. This means that it uses as many file descriptors as there are levels of subdirectories. To prevent the application from running out of file descriptors, the depth parameter limits how many file descriptors ftw() will leave open at one time. If this limit is hit, performance slows down, because directories need to be opened and closed repeatedly. The callback points to a function defined as follows: int ftwCallbackFunction(const char *file, const struct stat * sb, int flag);
This function is called once for every file in the directory tree, and the first parameter, file, gives the name of the file beginning with the dir passed to ftw(). For example, if the dir was ".", one file name might be "./.bashrc". If "/etc" was used instead, a file name would be /etc/hosts. The second argument to the callback, sb, points to a struct stat that resulted from a stat() on the file.[4] The flag argument provides information on the file, and takes one of the following values: [4] ftw() has to stat every file it finds to determine whether or not it is a directory, and passing this information to the callback prevents the callback from having to stat the files again in many cases.
FTW_F | The file is not a symbolic link or a directory. | FTW_D | The file is a directory or a symbolic link pointing to a directory. | FTW_DNR | The file is a directory that the application does not have permission to read (so it cannot be traversed). | FTW_SL | The file is a symbolic link. | FTW_NS | The file is an object on which stat() failed. An example of this would be a file in a directory that the application has read permission for (allowing the application to get a list of the files in that directory) but not execute permission for (preventing the stat() call from succeeding on the files in that directory). |
When a file is a symbolic link, ftw() attempts to follow that link and return information on the file it points to (ftw() TRaverses the same directory multiple times if there are multiple symbolic links to that directory, although it is smart enough to avoid loops). If it is a broken link, however, it is not defined whether FTW_SL or FTW_NS is returned. This is a good reason to use nftw() instead. If the callback function returns zero, the directory traversal continues. If a nonzero value is returned, the file tree walk ends and that value is returned by ftw(). If the traversal completes normally, ftw() returns zero, and it returns -1 if an error occurs as part of ftw(). 14.7.2. File Tree Walks with nftw() The new version of ftw(), nftw() addresses the symbolic link ambiguities inherent in ftw() and includes some additional features. To have nftw() properly defined by the header files, the application needs to define _XOPEN_SOURCE to be 500 or greater. Here is the prototype for nftw(): #define _XOPEN_SOURCE 600 #include <ftw.h> int nftw(const char *dir, ftwFunctionPointer callback, int depth, int flags); int nftwCallbackFunction(const char *file, const struct stat * sb, int flag, struct FTW * ftwInfo);
Comparing nftw() to ftw() shows a single new parameter, flags. It can be one or more of the following flags logically OR'ed together: FTW_CHDIR | nftw() does not normally change the current directory of the program. When FTW_CHDIR is specified, nftw() changes the current directory to whatever directory is being currently read. In other words, when the callback is invoked, the file name it is passed is always in the current directory. | FTW_DEPTH | By default, nftw() reports a directory name before the files in the directory. This flag causes that order to be reversed, with the contents of a directory being reported before the directory itself.[5] | FTW_MOUNT | This flag prevents nftw() from crossing a file system boundary during the traversal. If you are not sure what a file system is, refer to [Sobell, 2002]. | FTW_PHYS | Rather than follow symbolic links, nftw() will report the links but not follow them. A side effect of this is that the callback gets the result of an lstat() call rather than a stat() call. |
[5] This flag causes nftw() to provide a depth first search. There is no similar flag for a breadth first search.
The flag argument to the callback can take on two new values for nftw(), in addition to the values we have already mentioned for ftw(). FTW_DP | The item is a directory whose contents have already been reported (this can occur only if FTW_DEPTH was specified). | FTW_SLN | The item is a symbolic link that points to a nonexistent file (it is a broken link). This can occur only if FTW_PHYS was not specified; if it was, FTW_SL would be passed. |
These extra flag values make the behavior nftw() for symbolic links well specified. If FTW_PHYS is used, all symbolic links return FTW_SL. Without nftw(), broken links yield FTW_NS and other symbolic links give the same result as the target of the link. The callback for nftw() takes one more argument, ftwInfo. It is a pointer to a struct FTW, which is defined as: #define _XOPEN_SOURCE 600 #include <ftw.h> struct FTW { int base; int level; };
The base is the offset of the file name within the full path passed to the callback. For example, if the full path passed was /usr/bin/ls, the base would be 9, and file + ftwInfo->base would give the file name ls. The level is the number of directories below the original directory this file is. If ls was found in an nftw() that began in /usr, the level would be 1. If the search began in /usr/bin, the level would instead be 0. 14.7.3. Implementing find The find command searches one or more directory trees for files that match certain characteristics. Here is a simple implementation of find that is built around nftw(). It uses fnmatch()[6] to implement the -name switch, and illustrates many of the flags nftw() understands. [6] The fnmatch() function is described on pages 555-556.
1: /* find.c */ 2: 3: #define _XOPEN_SOURCE 600 4: 5: #include <fnmatch.h> 6: #include <ftw.h> 7: #include <limits.h> 8: #include <stdio.h> 9: #include <stdlib.h> 10: #include <string.h> 11: 12: const char * name = NULL; 13: int minDepth = 0, maxDepth = INT_MAX; 14: 15: int find(const char * file, const struct stat * sb, int flags, 16: struct FTW * f) { 17: if (f->level < minDepth) return 0; 18: if (f->level > maxDepth) return 0; 19: if (name && fnmatch(name, file + f->base, FNM_PERIOD)) return 0; 20: 21: if (flags == FTW_DNR) { 22: fprintf(stderr, "find: %s: permission denied\n", file); 23: } else { 24: printf("%s\n", file); 25: } 26: 27: return 0; 28: } 29: 30: int main(int argc, const char ** argv) { 31: int flags = FTW_PHYS; 32: int i; 33: int problem = 0; 34: int tmp; 35: int rc; 36: char * chptr; 37: 38: /* look for first command line parameter (which must occur after 39: the list of paths */ 40: i = 1; 41: while (i < argc && *argv[i] != '-') i++; 42: 43: /* handle the command line options */ 44: while (i < argc && !problem) { 45: if (!strcmp(argv[i], "-name")) { 46: i++; 47: if (i == argc) 48: problem = 1; 49: else 50: name = argv[i++]; 51: } else if (!strcmp(argv[i], "-depth")) { 52: i++; 53: flags |= FTW_DEPTH; 54: } else if (!strcmp(argv[i], "-mount") || 55: !strcmp(argv[i], "-xdev")) { 56: i++; 57: flags |= FTW_MOUNT; 58: } else if (!strcmp(argv[i], "-mindepth") || 59: !strcmp(argv[i], "-maxdepth")) { 60: i++; 61: if (i == argc) 62: problem = 1; 63: else { 64: tmp = strtoul(argv[i++], &chptr, 10); 65: if (*chptr) 66: problem = 1; 67: else if (!strcmp(argv[i - 2], "-mindepth")) 68: minDepth = tmp; 69: else 70: maxDepth = tmp; 71: } 72: } 73: } 74: 75: if (problem) { 76: fprintf(stderr, "usage: find <paths> [-name <str>] " 77: "[-mindepth <int>] [-maxdepth <int>]\n"); 78: fprintf(stderr, " [-xdev] [-depth]\n"); 79: return 1; 80: } 81: 82: if (argc == 1 || *argv[1] == '-') { 83: argv[1] = "."; 84: argc = 2; 85: } 86: 87: rc = 0; 88: i = 1; 89: flags =0; 90: while (i < argc && *argv[i] != '-') 91: rc |= nftw(argv[i++], find, 100, flags); 92: 93: return rc; 94: }
|
