How to recursively list directories in C on Linux?
I need to recursively list all directories and files in C programming. I have looked into FTW but that is not included with the 2 operating systems that I am using (Fedora and Minix). I am starting to get a big headache from all the different things that I have read over the past few hours.
If somebody knows of a code snippet I could look at that would be amazing, or if anyone can give me good direction on this I would be very grateful.
Why does everyone insist on reinventing the wheel again and again?
POSIX.1-2008 standardized the nftw() function, also defined in the Single Unix Specification v4 (SuSv4), and available in Linux (glibc, man 3 nftw), OS X, and most current BSD variants. It is not new at all.
Naïve opendir()/readdir()/closedir() -based implementations almost never handle the cases where directories or files are moved, renamed, or deleted during the tree traversal, whereas nftw() should handle them gracefully.
As an example, consider the following C program that lists the directory tree starting at the current working directory, or at each of the directories named on the command line, or just the files named at the command line:
/* 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;
}
Most of the code above is in print_entry(). Its task is to print out each directory entry. In print_directory_tree(), we tell nftw() to call it for each directory entry it sees.
The only hand-wavy detail above is the decision on how many file descriptors one should let nftw() use. If your program uses at most two extra file descriptors (in addition to the standard streams) during the file tree walk, 15 is known to be safe (on all systems having nftw() and being mostly POSIX-compliant).
In Linux, you could use sysconf(_SC_OPEN_MAX) to find the maximum number of open files, and subtract the number you use concurrently with the nftw() call, but I wouldn't bother (unless I knew the utility would be used mostly with pathologically deep directory structures). Fifteen descriptors does not limit the tree depth; nftw() just gets slower (and might not detect changes in a directory if walking a directory deeper than 13 directories from that one, although the tradeoffs and general ability to detect changes vary between systems and C library implementations). Just using a compile-time constant like that keeps the code portable -- it should work not just on Linux, but on Mac OS X and all current BSD variants, and most other not-too-old Unix variants, too.
In a comment, Ruslan mentioned that they had to switch to nftw64() because they had filesystem entries that required 64-bit sizes/offsets, and the "normal" version of nftw() failed with errno == EOVERFLOW. The correct solution is to not switch to GLIBC-specific 64-bit functions, but to define _LARGEFILE64_SOURCE and _FILE_OFFSET_BITS 64. These tell the C library to switch to 64-bit file sizes and offsets if possible, while using the standard functions (nftw(), fstat(), et cetera) and type names (off_t etc.).
Here is a recursive version:
#include <unistd.h>
#include <sys/types.h>
#include <dirent.h>
#include <stdio.h>
#include <string.h>
void listdir(const char *name, int indent)
{
DIR *dir;
struct dirent *entry;
if (!(dir = opendir(name)))
return;
while ((entry = readdir(dir)) != NULL) {
if (entry->d_type == DT_DIR) {
char path[1024];
if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0)
continue;
snprintf(path, sizeof(path), "%s/%s", name, entry->d_name);
printf("%*s[%s]\n", indent, "", entry->d_name);
listdir(path, indent + 2);
} else {
printf("%*s- %s\n", indent, "", entry->d_name);
}
}
closedir(dir);
}
int main(void) {
listdir(".", 0);
return 0;
}
int is_directory_we_want_to_list(const char *parent, char *name) {
struct stat st_buf;
if (!strcmp(".", name) || !strcmp("..", name))
return 0;
char *path = alloca(strlen(name) + strlen(parent) + 2);
sprintf(path, "%s/%s", parent, name);
stat(path, &st_buf);
return S_ISDIR(st_buf.st_mode);
}
int list(const char *name) {
DIR *dir = opendir(name);
struct dirent *ent;
while (ent = readdir(dir)) {
char *entry_name = ent->d_name;
printf("%s\n", entry_name);
if (is_directory_we_want_to_list(name, entry_name)) {
// You can consider using alloca instead.
char *next = malloc(strlen(name) + strlen(entry_name) + 2);
sprintf(next, "%s/%s", name, entry_name);
list(next);
free(next);
}
}
closedir(dir);
}
Header files worth being skimmed in this context: stat.h, dirent.h. Bear in mind that the code above isn't checking for any errors which might occur.
A completely different approach is offered by ftw defined in ftw.h.
As I mentioned in my comment, I believe a recursive approach to have two inherent flaws to this task.
The first flaw is the limit on open files. This limit imposes a limit on deep traversal. If there are enough sub-folders, the recursive approach will break. (See edit regarding stack overflow)
The second flaw is a bit more subtle. The recursive approach makes it very hard to test for hard links. If a folder tree is cyclic (due to hard links), the recursive approach will break (hopefully without a stack overflow). (See edit regarding hard links)
However, it is quite simple to avoid these issues by replacing recursion with a single file descriptor and linked lists.
I assume this isn't a school project and that recursion is optional.
Here's an example application.
Use a.out ./ to view folder tree.
I apologize for the macros and stuff... I usually use inline functions, but I thought it would be easier to follow the code if it was all in a single function.
#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;
}
EDIT
@Stargateur mentioned in the comments that the recursive code will probably overflow the stack before reaching the open file limit.
Although I don't see how a stack-overflow is any better, this assessment is probably correct as long as the process isn't close to the file limit when invoked.
Another point mentioned by @Stargateur in the comments was that the depth of the recursive code is limited by the maximum amount of sub-directories (64000 on the ext4 filesystem) and that hard links are extremely unlikely (since hard links to folders aren't allowed on Linux/Unix).
This is good news if the code is running on Linux (which it is, according to the question), so this issue isn't a real concern (unless running the code on macOS or, maybe, Windows)... although 64K subfolders in recursion might blow the stack wide open.
Having said that, the none recursive option still has advantages, such as being able to easily add a limit to the amount of items processed as well as being able to cache the result.
P.S.
According to the comments, here's a non-recursive version of the code that doesn't check for cyclic hierarchies. It's faster and should be safe enough to use on a Linux machine where hard links to folders aren't allowed.
#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;
}