2026-09-28
count_dirs.c
#define _XOPEN_SOURCE 700
#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
struct frame {
dev_t dev;
ino_t ino;
const struct frame *up;
};
static int walk(const char *path, const struct frame *up) {
struct stat st;
if (stat(path, &st) != 0 || !S_ISDIR(st.st_mode)) return 0;
for (const struct frame *f = up; f; f = f->up) {
if (f->dev == st.st_dev && f->ino == st.st_ino) return 0;
}
struct frame me = {st.st_dev, st.st_ino, up};
DIR *dir = opendir(path);
if (!dir) return 0;
int count = 1;
struct dirent *e;
while ((e = readdir(dir))) {
if (strcmp(e->d_name, ".") == 0 || strcmp(e->d_name, "..") == 0) continue;
char child[4096];
snprintf(child, sizeof child, "%s/%s", path, e->d_name);
count += walk(child, &me);
}
closedir(dir);
return count;
}
int main(void) {
char root[] = "/tmp/treeXXXXXX";
if (!mkdtemp(root) || chdir(root) != 0) return 1;
if (mkdir("a", 0700) || mkdir("a/b", 0700) || mkdir("c", 0700)) return 1;
if (symlink("../c", "a/c") || symlink("..", "a/b/up")) return 1;
printf("%d\n", walk(".", NULL));
return 0;
}
これは何を出力するでしょうか?
Answer
5 です。
main が一時ディレクトリの中に作るのは、ディレクトリ a、a/b、c と、2つのシンボリックリンクです。リンクの中身の相対パスは、リンクが置かれたディレクトリから解決されます。a/c の中身 ../c は a から見た c を指し、a/b/up の中身 .. は a/b の親の a を指します。
walk は stat で種類を調べます。stat はリンクをたどってリンク先の情報を返すので、この2つのリンクはどちらもディレクトリとして扱われ、中に入ります。そこで循環を止めるのが up の連なりで、いまのディレクトリに着くまでに通った祖先たちの st_dev と st_ino が積まれています。
. から始めると、.、a、a/b、a/c、c の5つが数えられます。a/b/up の先の a は a/b の祖先なので、そこで 0 が返ります。a/c と c は同じディレクトリですが、どちらも相手の祖先ではないので両方とも数えます。readdir が名前を返す順番は決まっていませんが、どの順で回っても祖先の並びは変わらないので、結果は 5 のままです。
祖先とだけ比べるのは、無限に深くなる原因が祖先へ戻るリンクに限られるからです。同じディレクトリに別の経路から着くことは循環ではないので、この関数は止めません1。比較にパスではなく st_dev と st_ino の組を使うのは、a/b/up と a のように文字列の違うパスでも、stat が返すこの組は同じになるからです。
- BSD と glibc の
ftsも同じ考え方で、祖先と同じディレクトリに入ろうとしたときだけFTS_DCを返します。同じディレクトリを2度数えたくないなら、見たディレクトリをすべて記録しておく必要があります。