lsっぽいコマンドを作る

作成:

UNIX 環境のコマンドラインを触ったことがある人ならどんな人でも使ったことがあるコマンドの一つ、 lsっぽいコマンドラインプログラムを作りながら、そのために必要な要素について解説していく。 あくまで「っぽい」であり、本物と全く同じものを作るわけではないので注意。

説明に使用するプログラムコードについては GitHub で公開している。 ソースコードの全文をよく見たい、ダウンロードしたいなどの場合はこちらを参照してほしい。

今回は ls11.c を利用した説明になる。

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

前回関数の再帰呼び出しを利用してディレクトリツリーを再帰的に探索した表示ができるようになった、 しかし、再帰呼び出しは慎重に行わないと不必要にリソースを消費するし、 再帰呼び出しが深くなりすぎるとスタックオーバーフローを起こしてしまう。

ケースバイケースではあるが、今回のケースでは再帰呼び出しを使用するより、 状態を独自にスタックしてループするようにしたほうが、コードレベルでも簡潔に記述でき、消費リソースを削減することができる。 また、スタックよりもヒープの方が大きなメモリを扱えるため、スタックオーバーフローを回避する意味でも有益だ。 今回は、再帰表示の改善として、関数の再帰的な呼び出しを利用しない方法について説明する。

ディレクトリの再帰的な表示には、あるディレクトリの走査、表示を行い、 その中にあったディレクトリについて再度同じ処理を実行することで実現する。 再帰呼び出しでは様々な状態をスタックに保持して呼び出しを行うことになるのだが、 本当に必要な情報は何かを整理して考えると、追加して必要となるのは、どのディレクトリを表示するかという情報だけである。

つまり、表示するディレクトリのリストを何処かに保持しておき、 ディレクトリの表示のための走査時にディレクトリを見つけた場合はそのディレクトリをリストに追加するようにし、 リストが空になるまでこれを繰り返せば良い。

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

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


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 の2つのサブディレクトリを持つという構造である。 通常上記に示したように、ツリー表示したような順序で表示するのが一般的だろう。 すなわち、 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;
    }
  }

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

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

リンクリストに処理内容をスタックすることで、 再帰呼び出しを使用しないでディレクトリの再帰的表示が実現できるようになった。