Namaran

Code daily. Without assist.

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 が返すこの組は同じになるからです。

  1. BSD と glibc の fts も同じ考え方で、祖先と同じディレクトリに入ろうとしたときだけ FTS_DC を返します。同じディレクトリを2度数えたくないなら、見たディレクトリをすべて記録しておく必要があります。