lsっぽいコマンドを作る

表示するディレクトリリスト

まずは、表示するディレクトリのリストを保持しておくデータ構造を作成する。 任意個のデータを保持できるように可変長であり、 また、途中で見つけたディレクトリはリストの途中への挿入が必要となるため、 このような用途にふさわしいデータ構造としてリンクリストを採用することにする。

struct subdir {
  char path[PATH_MAX + 1];
  int depth;
  struct subdir *next;
};

なんのへんてつもないリンクリストである。 depth は再帰呼び出しの深さを記録できるように追加している。 ひとまず使用しない予定ではあるが この構造体をそのまま操作してもよいが、 メモリ確保とパラメータの初期化ができるコンストラクタのような関数を用意しておく。

static struct dir_path *new_dir_path(const char *path, int depth, struct dir_path *next) {
  struct dir_path *s = xmalloc(sizeof(struct dir_path));
  if (path != NULL) {
    strncpy(s->path, path, sizeof(s->path));
  }
  s->depth = depth;
  s->next = next;
  return s;
}

使い方は、以下のようにする。

a->next = new_subdir(path, a->next);

こうすると、aの次に新しい要素が挿入される。

ここで使用している xmalloc は以下のように定義している。

static void *xmalloc(size_t size) {
  void *p = malloc(size);
  if (p == NULL) {
    perror("");
    exit(EXIT_FAILURE);
  }
  return p;
}

見ての通り、メモリの確保に失敗した場合、実行プログラムを終了させるというものだ。 当然動き続けることが必要なプログラム内では使えないが、 結果を表示すれば終了するだけのプログラムであればこれで十分である。 流用する場合、組み込むプログラムの性質によって適宜変更してほしい。

再帰的走査手順の確認

さて、パス情報の格納手段が用意できた。 次に、データ構造の読み出しを所望の順序で行うためにはどのように処理をすればよいか一度整理しておこう。

a というディレクトリ以下のサブディレクトリ構成が以下のようになっていたとする。

a
├b
├c
│├e
│└f
└d

a 直下には b c d の3つのサブディレクトリがあり、更に、c は e f の２つのサブディレクトリを持つという構造である。 通常上記に示したように、ツリー表示したような順序で表示するのが一般的だろう。 すなわち、 a -> a/b -> a/c -> a/c/e -> a/c/f -> a/d という順序だ。

これを深さ優先探索というが、処理の順序として整理すると、 a ディレクトリを走査し、ディレクトリ内容を表示すると同時に、 見つけた順に a/b a/c a/d というサブディレクトリをデータ構造に追加する。 このループが終わったあとは、データ構造の戦闘の情報を読み出し、a/b のディレクトリを走査する。 a/b にはサブディレクトリが存在しないため、次のループでは a/c の読み出しが行われる。 a/c にはサブディレクトリが存在するため、それを表示するためのデータ構造に追加する。 a/c のサブディレクトリは a/d を表示する前に表示するために、 a/b の後、 a/d の前に挿入していくようにする。 こうすることで、ツリー構造で表示した順序で再帰的な表示を行うことができる。

まとめると、データ構造の先頭に書かれたディレクトリを読み出す。 途中で見つけたサブディレクトリは、読み出したデータ構造の次に追加していく。 先頭に追加するのではなく、そのディレクトリ途中で見つけたサブディレクトリは見つけた順に、先頭の次から読み出していく。 という順序で処理を行うようにすればよい。

呼び出し処理の変更

前回までの構成では、ファイル情報を表示する処理に、表示するディレクトリ名を文字列で渡して処理をする形にしていた。 そこを、作成したリンクリストを渡す方式に変更する。 また、表示処理をリンクリストが殻になるまで繰り返す形にした。

int main(int argc, char**argv) {
  struct dir_path *head;
  char *path = parse_cmd_args(argc, argv);
  if (path == NULL) {
    return EXIT_FAILURE;
  }
  head = new_dir_path(path, 0, NULL);
  while(head != NULL) {
    if (head->depth != 0) {
      printf("\n%s:\n", head->path);
    }
    list_dir(head);
    struct dir_path *tmp = head;
    head = head->next;
    free(tmp);
  }
  return EXIT_SUCCESS;
}

リンクリストが空になるまで list_dir() をコールする構成となっているが、 リンクリストは list_dir() の中でも更新されうるということで、 制御構造としてはより複雑になっているため注意したいところである。

サブディレクトリの再帰的表示

さて、実際の再帰的表示を行う処理であるが、前回再帰呼び出しを行っていた処理を削除し、以下の処理を追加する。 ディレクトリの走査中にディレクトリを見つけた場合、リンクリストに追加する。

while ((dent = readdir(dir)) != NULL) {
...
  strncpy(&path[path_len], dent->d_name, PATH_MAX - path_len);
  if (lstat(path, &dent_stat) != 0) {
    perror(path);
    continue;
  }
  if (recursive && S_ISDIR(dent_stat.st_mode)) {
    if (!(name[0] == '.' && name[1 + (name[1] == '.')] == '\0')) {
      subque->next = new_dir_path(path, base->depth + 1, subque->next);
      subque = subque->next;
    }
  }

単純にリンクリストの先頭に追加するのではなく、先頭から後ろ方向に追加していくようにしている。 単純に先頭に追加していくと、次に表示するサブディレクトリが最後に表示したサブディレクトリとなってしまい、 表示した順と逆になってしまうからだ。

対応としては以上で完了だ。