/* We want POSIX.1-2008 + XSI, i.e. SuSv4, features */
#define _XOPEN_SOURCE 700
/* Added on 2017-06-25:
If the C library can support 64-bit file sizes
and offsets, using the standard names,
these defines tell the C library to do so. */
#define _LARGEFILE64_SOURCE
#define _FILE_OFFSET_BITS 64
#include <stdlib.h>
#include <unistd.h>
#include <ftw.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
/* POSIX.1 says each process has at least 20 file descriptors.
* Three of those belong to the standard streams.
* Here, we use a conservative estimate of 15 available;
* assuming we use at most two for other uses in this program,
* we should never run into any problems.
* Most trees are shallower than that, so it is efficient.
* Deeper trees are traversed fine, just a bit slower.
* (Linux allows typically hundreds to thousands of open files,
* so you'll probably never see any issues even if you used
* a much higher value, say a couple of hundred, but
* 15 is a safe, reasonable value.)
*/
#ifndef USE_FDS
#define USE_FDS 15
#endif
int print_entry(const char *filepath, const struct stat *info,
const int typeflag, struct FTW *pathinfo)
{
/* const char *const filename = filepath + pathinfo->base; */
const double bytes = (double)info->st_size; /* Not exact if large! */
struct tm mtime;
localtime_r(&(info->st_mtime), &mtime);
printf("%04d-%02d-%02d %02d:%02d:%02d",
mtime.tm_year+1900, mtime.tm_mon+1, mtime.tm_mday,
mtime.tm_hour, mtime.tm_min, mtime.tm_sec);
if (bytes >= 1099511627776.0)
printf(" %9.3f TiB", bytes / 1099511627776.0);
else
if (bytes >= 1073741824.0)
printf(" %9.3f GiB", bytes / 1073741824.0);
else
if (bytes >= 1048576.0)
printf(" %9.3f MiB", bytes / 1048576.0);
else
if (bytes >= 1024.0)
printf(" %9.3f KiB", bytes / 1024.0);
else
printf(" %9.0f B ", bytes);
if (typeflag == FTW_SL) {
char *target;
size_t maxlen = 1023;
ssize_t len;
while (1) {
target = malloc(maxlen + 1);
if (target == NULL)
return ENOMEM;
len = readlink(filepath, target, maxlen);
if (len == (ssize_t)-1) {
const int saved_errno = errno;
free(target);
return saved_errno;
}
if (len >= (ssize_t)maxlen) {
free(target);
maxlen += 1024;
continue;
}
target[len] = '\0';
break;
}
printf(" %s -> %s\n", filepath, target);
free(target);
} else
if (typeflag == FTW_SLN)
printf(" %s (dangling symlink)\n", filepath);
else
if (typeflag == FTW_F)
printf(" %s\n", filepath);
else
if (typeflag == FTW_D || typeflag == FTW_DP)
printf(" %s/\n", filepath);
else
if (typeflag == FTW_DNR)
printf(" %s/ (unreadable)\n", filepath);
else
printf(" %s (unknown)\n", filepath);
return 0;
}
int print_directory_tree(const char *const dirpath)
{
int result;
/* Invalid directory path? */
if (dirpath == NULL || *dirpath == '\0')
return errno = EINVAL;
result = nftw(dirpath, print_entry, USE_FDS, FTW_PHYS);
if (result >= 0)
errno = result;
return errno;
}
int main(int argc, char *argv[])
{
int arg;
if (argc < 2) {
if (print_directory_tree(".")) {
fprintf(stderr, "%s.\n", strerror(errno));
return EXIT_FAILURE;
}
} else {
for (arg = 1; arg < argc; arg++) {
if (print_directory_tree(argv[arg])) {
fprintf(stderr, "%s.\n", strerror(errno));
return EXIT_FAILURE;
}
}
}
return EXIT_SUCCESS;
}
上面的大部分代码都在print_entry()中，它的任务是打印出每个目录条目，在print_directory_tree()中，我们告诉nftw()为它看到的每个目录条目调用它。 上面唯一的细节是nftw()应该使用多少文件描述符，如果你的程序在文件树遍历过程中最多使用两个额外的文件描述符（除了标准流），15是安全的（在所有有nftw()并且大多数是POSIX兼容的系统上）。 在Linux中，您可以使用sysconf(_SC_OPEN_MAX)来查找打开文件的最大数量，然后减去与nftw()调用同时使用的数量，但我不会为此费心（除非我知道该实用程序将主要用于病态深度的目录结构）。nftw()只会变得更慢（并且如果从一个目录开始遍历超过13个目录，可能无法检测到该目录中的更改，尽管在不同的系统和C库实现之间，检测更改的权衡和一般能力会有所不同）。仅使用这样的编译时常量就可以保持代码的可移植性--它不仅应该在Linux上工作，而且应该在Mac OS X和所有当前的BSD变体上工作，以及大多数其他不太老的Unix变体。 Ruslan在评论中提到，他们必须切换到nftw64()，因为他们的文件系统条目需要64位大小/偏移量，而nftw()的“普通”版本失败于errno == EOVERFLOW。正确的解决方案是不要切换到特定于GLIFC的64位函数，而是定义_LARGEFILE64_SOURCE和_FILE_OFFSET_BITS 64。这些命令告诉C库在使用标准函数（nftw()、fstat()等）和类型名（off_t等）时，如果可能，切换到64位文件大小和偏移量。
#include <dirent.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
int main(int argc, char const *argv[]) {
/* print use instruction unless a folder name was given */
if (argc < 2)
fprintf(stderr,
"\nuse:\n"
" %s <directory>\n"
"for example:\n"
" %s ./\n\n",
argv[0], argv[0]),
exit(0);
/*************** a small linked list macro implementation ***************/
typedef struct list_s {
struct list_s *next;
struct list_s *prev;
} list_s;
#define LIST_INIT(name) \
{ .next = &name, .prev = &name }
#define LIST_PUSH(dest, node) \
do { \
(node)->next = (dest)->next; \
(node)->prev = (dest); \
(node)->next->prev = (node); \
(dest)->next = (node); \
} while (0);
#define LIST_POP(list, var) \
if ((list)->next == (list)) { \
var = NULL; \
} else { \
var = (list)->next; \
(list)->next = var->next; \
var->next->prev = var->prev; \
}
/*************** a record (file / folder) item type ***************/
typedef struct record_s {
/* this is a flat processing queue. */
list_s queue;
/* this will list all queued and processed folders (cyclic protection) */
list_s folders;
/* this will list all the completed items (siblings and such) */
list_s list;
/* unique ID */
ino_t ino;
/* name length */
size_t len;
/* name string */
char name[];
} record_s;
/* take a list_s pointer and convert it to the record_s pointer */
#define NODE2RECORD(node, list_name) \
((record_s *)(((uintptr_t)(node)) - \
((uintptr_t) & ((record_s *)0)->list_name)))
/* initializes a new record */
#define RECORD_INIT(name) \
(record_s){.queue = LIST_INIT((name).queue), \
.folders = LIST_INIT((name).folders), \
.list = LIST_INIT((name).list)}
/*************** the actual code ***************/
record_s records = RECORD_INIT(records);
record_s *pos, *item;
list_s *tmp;
DIR *dir;
struct dirent *entry;
/* initialize the root folder record and add it to the queue */
pos = malloc(sizeof(*pos) + strlen(argv[1]) + 2);
*pos = RECORD_INIT(*pos);
pos->len = strlen(argv[1]);
memcpy(pos->name, argv[1], pos->len);
if (pos->name[pos->len - 1] != '/')
pos->name[pos->len++] = '/';
pos->name[pos->len] = 0;
/* push to queue, but also push to list (first item processed) */
LIST_PUSH(&records.queue, &pos->queue);
LIST_PUSH(&records.list, &pos->list);
/* as long as the queue has items to be processed, do so */
while (records.queue.next != &records.queue) {
/* pop queued item */
LIST_POP(&records.queue, tmp);
/* collect record to process */
pos = NODE2RECORD(tmp, queue);
/* add record to the processed folder list */
LIST_PUSH(&records.folders, &pos->folders);
/* process the folder and add all folder data to current list */
dir = opendir(pos->name);
if (!dir)
continue;
while ((entry = readdir(dir)) != NULL) {
/* create new item, copying it's path data and unique ID */
item = malloc(sizeof(*item) + pos->len + entry->d_namlen + 2);
*item = RECORD_INIT(*item);
item->len = pos->len + entry->d_namlen;
memcpy(item->name, pos->name, pos->len);
memcpy(item->name + pos->len, entry->d_name, entry->d_namlen);
item->name[item->len] = 0;
item->ino = entry->d_ino;
/* add item to the list, right after the `pos` item */
LIST_PUSH(&pos->list, &item->list);
/* unless it's a folder, we're done. */
if (entry->d_type != DT_DIR)
continue;
/* test for '.' and '..' */
if (entry->d_name[0] == '.' &&
(entry->d_name[1] == 0 ||
(entry->d_name[1] == '.' && entry->d_name[2] == 0)))
continue;
/* add folder marker */
item->name[item->len++] = '/';
item->name[item->len] = 0;
/* test for cyclic processing */
list_s *t = records.folders.next;
while (t != &records.folders) {
if (NODE2RECORD(t, folders)->ino == item->ino) {
/* we already processed this folder! */
break; /* this breaks from the small loop... */
}
t = t->next;
}
if (t != &records.folders)
continue; /* if we broke from the small loop, entry is done */
/* item is a new folder, add to queue */
LIST_PUSH(&records.queue, &item->queue);
}
closedir(dir);
}
/*************** Printing the results and cleaning up ***************/
while (records.list.next != &records.list) {
/* pop list item */
LIST_POP(&records.list, tmp);
/* collect and process record */
pos = NODE2RECORD(tmp, list);
fwrite(pos->name, pos->len, 1, stderr);
fwrite("\n", 1, 1, stderr);
/* free node */
free(pos);
}
return 0;
}
#include <dirent.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
int main(int argc, char const *argv[]) {
/* print use instruction unless a folder name was given */
if (argc < 2)
fprintf(stderr,
"\nuse:\n"
" %s <directory>\n"
"for example:\n"
" %s ./\n\n",
argv[0], argv[0]),
exit(0);
/*************** a small linked list macro implementation ***************/
typedef struct list_s {
struct list_s *next;
struct list_s *prev;
} list_s;
#define LIST_INIT(name) \
{ .next = &name, .prev = &name }
#define LIST_PUSH(dest, node) \
do { \
(node)->next = (dest)->next; \
(node)->prev = (dest); \
(node)->next->prev = (node); \
(dest)->next = (node); \
} while (0);
#define LIST_POP(list, var) \
if ((list)->next == (list)) { \
var = NULL; \
} else { \
var = (list)->next; \
(list)->next = var->next; \
var->next->prev = var->prev; \
}
/*************** a record (file / folder) item type ***************/
typedef struct record_s {
/* this is a flat processing queue. */
list_s queue;
/* this will list all the completed items (siblings and such) */
list_s list;
/* unique ID */
ino_t ino;
/* name length */
size_t len;
/* name string */
char name[];
} record_s;
/* take a list_s pointer and convert it to the record_s pointer */
#define NODE2RECORD(node, list_name) \
((record_s *)(((uintptr_t)(node)) - \
((uintptr_t) & ((record_s *)0)->list_name)))
/* initializes a new record */
#define RECORD_INIT(name) \
(record_s){.queue = LIST_INIT((name).queue), .list = LIST_INIT((name).list)}
/*************** the actual code ***************/
record_s records = RECORD_INIT(records);
record_s *pos, *item;
list_s *tmp;
DIR *dir;
struct dirent *entry;
/* initialize the root folder record and add it to the queue */
pos = malloc(sizeof(*pos) + strlen(argv[1]) + 2);
*pos = RECORD_INIT(*pos);
pos->len = strlen(argv[1]);
memcpy(pos->name, argv[1], pos->len);
if (pos->name[pos->len - 1] != '/')
pos->name[pos->len++] = '/';
pos->name[pos->len] = 0;
/* push to queue, but also push to list (first item processed) */
LIST_PUSH(&records.queue, &pos->queue);
LIST_PUSH(&records.list, &pos->list);
/* as long as the queue has items to be processed, do so */
while (records.queue.next != &records.queue) {
/* pop queued item */
LIST_POP(&records.queue, tmp);
/* collect record to process */
pos = NODE2RECORD(tmp, queue);
/* process the folder and add all folder data to current list */
dir = opendir(pos->name);
if (!dir)
continue;
while ((entry = readdir(dir)) != NULL) {
/* create new item, copying it's path data and unique ID */
item = malloc(sizeof(*item) + pos->len + entry->d_namlen + 2);
*item = RECORD_INIT(*item);
item->len = pos->len + entry->d_namlen;
memcpy(item->name, pos->name, pos->len);
memcpy(item->name + pos->len, entry->d_name, entry->d_namlen);
item->name[item->len] = 0;
item->ino = entry->d_ino;
/* add item to the list, right after the `pos` item */
LIST_PUSH(&pos->list, &item->list);
/* unless it's a folder, we're done. */
if (entry->d_type != DT_DIR)
continue;
/* test for '.' and '..' */
if (entry->d_name[0] == '.' &&
(entry->d_name[1] == 0 ||
(entry->d_name[1] == '.' && entry->d_name[2] == 0)))
continue;
/* add folder marker */
item->name[item->len++] = '/';
item->name[item->len] = 0;
/* item is a new folder, add to queue */
LIST_PUSH(&records.queue, &item->queue);
}
closedir(dir);
}
/*************** Printing the results and cleaning up ***************/
while (records.list.next != &records.list) {
/* pop list item */
LIST_POP(&records.list, tmp);
/* collect and process record */
pos = NODE2RECORD(tmp, list);
fwrite(pos->name, pos->len, 1, stderr);
fwrite("\n", 1, 1, stderr);
/* free node */
free(pos);
}
return 0;
}
6条答案
按热度按时间ohfgkhjo1#
为什么大家一次又一次坚持要另起炉灶？
POSIX.1-2008标准化了
nftw()函数，它也在单一Unix规范v4（SuSv 4）中定义，并在Linux（glibc，man 3 nftw）、OS X和大多数当前的BSD变体中可用。简单的基于
opendir()/readdir()/closedir()的实现几乎从来不处理目录或文件在树遍历过程中被移动、重命名或删除的情况，而nftw()应该能够很好地处理这些情况。例如，考虑下面的C程序，该程序列出了从当前工作目录开始的目录树，或从命令行中指定的每个目录开始的目录树，或仅从命令行中指定的文件开始的目录树：
上面的大部分代码都在
print_entry()中，它的任务是打印出每个目录条目，在print_directory_tree()中，我们告诉nftw()为它看到的每个目录条目调用它。上面唯一的细节是
nftw()应该使用多少文件描述符，如果你的程序在文件树遍历过程中最多使用两个额外的文件描述符（除了标准流），15是安全的（在所有有nftw()并且大多数是POSIX兼容的系统上）。在Linux中，您可以使用
sysconf(_SC_OPEN_MAX)来查找打开文件的最大数量，然后减去与nftw()调用同时使用的数量，但我不会为此费心（除非我知道该实用程序将主要用于病态深度的目录结构）。nftw()只会变得更慢（并且如果从一个目录开始遍历超过13个目录，可能无法检测到该目录中的更改，尽管在不同的系统和C库实现之间，检测更改的权衡和一般能力会有所不同）。仅使用这样的编译时常量就可以保持代码的可移植性--它不仅应该在Linux上工作，而且应该在Mac OS X和所有当前的BSD变体上工作，以及大多数其他不太老的Unix变体。Ruslan在评论中提到，他们必须切换到
nftw64()，因为他们的文件系统条目需要64位大小/偏移量，而nftw()的“普通”版本失败于errno == EOVERFLOW。正确的解决方案是不要切换到特定于GLIFC的64位函数，而是定义_LARGEFILE64_SOURCE和_FILE_OFFSET_BITS 64。这些命令告诉C库在使用标准函数（nftw()、fstat()等）和类型名（off_t等）时，如果可能，切换到64位文件大小和偏移量。sr4lhrrt2#
下面是一个递归版本：
6tdlim6h3#
在此上下文中值得略读的头文件：stat.h，dirent.h。请记住，上面的代码不会检查任何可能发生的错误。
ftw.h中定义的
ftw提供了一种完全不同的方法。ybzsozfc4#
正如我在评论中提到的，我认为递归方法对于此任务有两个固有的缺陷。
第一个缺陷是对打开文件的限制。这个限制对深度遍历施加了限制。如果有足够的子文件夹，递归方法将被破坏。（参见编辑关于堆栈溢出的内容）
第二个缺陷更微妙一些。递归方法使得测试硬链接变得非常困难。如果一个文件夹树是循环的（由于硬链接），递归方法将中断（希望没有堆栈溢出）。（参见关于硬链接的编辑）
然而，通过用单个文件描述符和链表代替递归来避免这些问题是相当简单的。
我假设这不是学校的作业，递归是可选的。
下面是一个示例应用程序。
使用
a.out ./查看文件夹树。我为宏和其他东西道歉...我通常使用内联函数，但我认为如果它都在一个函数中，那么遵循代码会更容易。
@Stargateur在注解中提到，递归代码很可能会在达到打开文件限制之前溢出堆栈。
尽管我看不出堆栈溢出有什么好处，但只要进程在调用时不接近文件限制，这种评估可能是正确的。
@Stargateur在评论中提到的另一点是递归代码的深度受到最大子目录数量的限制（ext4文件系统上为64000个），而且硬链接是极不可能的（因为Linux/Unix不允许硬链接到文件夹）。
如果代码在Linux上运行（根据问题，这是一个好消息），所以这个问题不是一个真正的问题（除非在macOS或Windows上运行代码）...尽管递归中的64K子文件夹可能会使堆栈大开。
话虽如此，无递归选项仍然有优势，例如能够轻松地添加对处理的项目数量的限制，以及能够缓存结果。
根据评论，这里是一个非递归版本的代码，它不检查循环层次结构，它更快，而且应该足够安全，可以在不允许硬链接到文件夹的Linux机器上使用。
nxagd54h5#
下面是一个递归的简化版本，但使用的堆栈空间要少得多：
在我的系统上，它的输出与
find .完全相同lawou6xi6#
遍历目录树而不构造路径名
这是一个使用文件描述符来引用目录的版本，使用
fdopendir()、fstatat()和openat()来遍历目录树，而不必构造任何路径名。这更易于实现，并且在具有深度嵌套目录树的系统上非常有用，其中完整路径名可能超过
PATH_MAX-请注意，PATH_MAX甚至可能不存在。张贴的代码被压缩，分解，并删除所有的错误检查，以消除垂直滚动条和提高可读性。一个完整的例子是在问题的最后。
标题
实际目录树遍历实现：
使用目录名的公共呼叫：
使用示例：
为了简洁起见，这里没有进行错误检查。真实的的代码应该检查所有调用的错误，并适当地处理它们。
带错误检查的完整代码：