Namaran

Code daily. Without assist.

2026-09-28

mark_seen.c

#define _XOPEN_SOURCE 700
#include <stddef.h>
#include <sys/stat.h>

enum { SEEN_MAX = 64 };

struct file_id {
    dev_t dev;
    ino_t ino;
};

struct seen {
    struct file_id ids[SEEN_MAX];
    size_t n;
};

bool mark_seen(struct seen *s, const struct stat *st) {
}

ディレクトリを走査するときに、同じディレクトリへ2度入らないよう記録する mark_seen を書いてください。st は stat で得たディレクトリの情報で、そのディレクトリを初めて見たなら s に記録して true を、記録済みなら何もせずに false を返します。s->n が SEEN_MAX より小さいことは呼び出し側が保証します。st_dev が 1、st_ino が 42 の a と、st_dev が 2、st_ino が 42 の b について、空の s から順に呼ぶと mark_seen(&s, &a) → true、mark_seen(&s, &a) → false、mark_seen(&s, &b) → true

Reference
bool mark_seen(struct seen *s, const struct stat *st) {
    for (size_t i = 0; i < s->n; i++) {
        if (s->ids[i].dev == st->st_dev && s->ids[i].ino == st->st_ino) {
            return false;
        }
    }
    s->ids[s->n++] = (struct file_id){st->st_dev, st->st_ino};
    return true;
}

ファイルが同じかどうかは、st_dev と st_ino の組で決まります。st_dev はそのファイルがあるファイルシステム(デバイス)の番号で、st_ino はその中でファイルに振られた番号です。シンボリックリンクやハードリンクを通って別のパスから来ても、stat が返すこの組は変わりません。

st_ino だけで比べると、例の a と b を同じものと判定してしまいます。inode 番号はファイルシステムごとに振られるので、マウントポイントをまたいで走査すると、別のディレクトリが同じ番号を持つことがあるからです。struct stat 全体を memcmp で比べるのも誤りで、アクセス時刻のように同じファイルでも呼ぶたびに変わりうるメンバや、中身の定まらないパディングまで比べることになります。

見たディレクトリをすべて記録するこの方法なら、ループだけでなく、別の経路から同じディレクトリに着いたときも2度目は入りません。代わりに記録は走査の間ずっと増え続けます。掲載したのは参考実装で、唯一の正解ではありません。数が多いなら、線形探索の代わりにハッシュ表や tsearch の二分探索木で引きます。