lsっぽいコマンドを作る

作成：2017/1/4

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

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

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

ソート機能の追加

ls っぽいコマンドということで徐々に機能を拡張しながら作成してきたが、実際に使用する上でほぼ必須と思しき機能が未実装だった。それはソート機能だ。これまでは、ディレクトリストリームが返す順序でそのまま表示していた。これはシステム内部の管理の都合の順序であり、人間に取って使いやすい順序ではない。今回は、これをソートして表示する機能を実装する。

必要なことは、ディレクトリストリームから読み出し、その情報をその場で表示するのではなく、一度どこかにその情報を保存しておき、すべての情報がまとまってからソートをおこなう、それだけだ。少し考えなければならないのは、読み出した情報の何を保存するか、と、どのように保持するかだろう。

読み出しデータの保持方法

読み出したデータについて、名前の辞書順でのソートのみを行う場合は、struct dirent の名前だけあればよい。後の属性情報は表示するときに lstat などを利用して読み出すことができる。しかし、属性情報に基づいたソートも行うことを考慮すると、ソートする情報としても属性情報は予め読み出している方が良い。そこで以下の構造体を定義する。


struct info {
  char name[NAME_MAX + 1];
  char link[PATH_MAX + 1];
  struct stat stat;
  mode_t link_mode;
  bool link_ok;
};

構成要素は順に、ファイル名、（シンボリックリンクの場合のみ使用）リンク先のパス名、 lstat の結果を格納する stat 構造体、（シンボリックリンクの場合のみ使用）リンク先のモード情報、（シンボリックリンクの場合のみ使用）リンク先が存在するか否かのbool値、という内容になっている。シンボリックリンクの場合のみに使用する情報が5つのうち3つと通常使用されないフィールドが多いが、別途読み出すなどとすると処理が複雑になるため、まとめて読み出すことにする。

この構造体の確保と各情報の読み出し、格納をまとめて行う以下の関数を作成する。


static struct info *new_info(const char *path, const char *name) {
  struct info *info = xmalloc(sizeof(struct info));
  strncpy(info->name, name, NAME_MAX + 1);
  if (lstat(path, &info->stat) != 0) {
    perror(path);
    free(info);
    return NULL;
  }
  info->link_ok = false;
  info->link[0] = 0;
  info->link_mode = 0;
  if (S_ISLNK(info->stat.st_mode)) {
    struct stat link_stat;
    int link_len = readlink(path, info->link, PATH_MAX);
    if (link_len > 0) {
      info->link[link_len] = 0;
    }
    if (stat(path, &link_stat) == 0) {
      info->link_ok = true;
      info->link_mode = link_stat.st_mode;
    }
  } else {
    info->link_ok = true;
  }
  return info;
}

xmalloc でメモリを確保し、ファイル名を格納。 lstat でファイルの属性を読み出し、シンボリックリンクならリンクの情報も読み出し格納している。

可変長配列の作成

次に前述のファイル情報をどのように保存しておくか？が課題となる。ディレクトリ以下のエントリーすべてを格納する必要があるのだが、その数を予め想定することは難しい。また、ソートを行うことを考えると配列に格納しておいたほうがやりやすい。

これら要件を満たすために、今回は可変長配列を作成してそこに格納することとする。

可変長配列を表現する構造体として以下のように定義する。


struct info_list {
  struct info **array;
  int size;
  int used;
};

配列そのものは struct info のポインタを格納する配列になるので、ポインタのポインタとなる。配列の長さは可変なので、その配列がどれだけの長さを持っているのかを別途保持する必要がある。また、データを順次追加していくような使い方をするため、どこまで使用済みかの値も保持させる。

この構造体は以下の関数で初期化する。

static void init_info_list(struct info_list *list, int size) {
  list->array = xmalloc(sizeof(struct info*) * size);
  list->size = size;
  list->used = 0;
}

要素の追加を行うための関数として以下を用意する。


static void add_info(struct info_list *list, struct info *info) {
  if (list->size == list->used) {
    list->size = list->size * 2;
    list->array = xrealloc(list->array, sizeof(struct info*) * list->size);
  }
  list->array[list->used] = info;
  list->used++;
}

使用している領域の後ろに追加を行う。その際、容量が不足していれば、２倍の容量を確保する。という処理になる。

確保したメモリ領域の拡大は、ヒープから連続領域として確保できる場合はそのまま延長されるが、そうでない場合は別途領域を確保し、そこへ今までの内容をコピーし、元の領域を開放するという処理になる。このように領域の拡大はコストの大きな処理であるため、拡大する回数は最小限にしたいところであるが、一度に大きくしすぎるとメモリ容量が無駄になる。そのトレードオフとして、不足するたびに2倍にするという方式はよく用いられる。

realloc は malloc と同様に、確保に失敗するとプログラム自体を終了させるように、以下のような形でラップした関数を用意して使用している。


static void *xrealloc(void *ptr, size_t size) {
  void *p = realloc(ptr, size);
  if (p == NULL) {
    perror("");
    exit(EXIT_FAILURE);
  }
  return p;
}

最後に、可変長配列で確保したメモリを開放する関数も以下のように用意しておく。


static void free_info_list(struct info_list *list) {
  int i;
  for (i = 0; i < list->used; i++) {
    free(list->array[i]);
  }
  free(list->array);
}

ファイル情報に基づくソート

ファイル情報を配列に保持するようにしたため、ソート自体はC言語の標準関数である、 qsort をそのまま利用する。


static void sort_list(struct info_list *list) {
  qsort(list->array, list->used, sizeof(struct info*), compare_name);
}

問題は比較関数だが、単純にファイル名の順序としてもよいが、ディレクトリは先に表示するようにしたいので、以下のようにしてみた。

static int compare_name(const void *a, const void *b) {
  struct info *ai = *(struct info**)a;
  struct info *bi = *(struct info**)b;
  if (S_ISDIR(ai->stat.st_mode) && !S_ISDIR(bi->stat.st_mode)) {
    return -1;
  }
  if (!S_ISDIR(ai->stat.st_mode) && S_ISDIR(bi->stat.st_mode)) {
    return 1;
  }
  return strcmp(ai->name, bi->name);
}

比較関数の作りようによって任意のソートができるので、複数用意しておいてオプションで選択できるようにしても良いだろう。

ファイル情報の表示

これまでは表示する際に書く情報を取得していたところ、先に情報はまとめて取ってしまっているので、 struct info の情報をもとに表示できるように以下のような関数として定義し直す。


static void print_info(struct info *info) {
  if (long_format) {
    char buf[12];
    get_mode_string(info->stat.st_mode, buf);
    printf("%s ", buf);
    printf("%3d ", (int)info->stat.st_nlink);
    print_user(info->stat.st_uid);
    print_group(info->stat.st_gid);
    if (S_ISCHR(info->stat.st_mode) || S_ISBLK(info->stat.st_mode)) {
      printf("%4d,%4d ", major(info->stat.st_rdev),
             minor(info->stat.st_rdev));
    } else {
      printf("%9ld ", info->stat.st_size);
    }
    get_time_string(buf, info->stat.st_mtim.tv_sec);
    printf("%s ", buf);
  }
  if (color) {
    print_name_with_color(info->name, info->stat.st_mode, info->link_ok);
  } else {
    printf("%s", info->name);
  }
  if (classify) {
    print_type_indicator(info->stat.st_mode);
  }
  if (long_format) {
    if (info->link[0] != 0) {
      printf(" -> ");
      if (color) {
        print_name_with_color(info->link, info->link_mode, info->link_ok);
      } else {
        printf("%s", info->link);
      }
    }
  }
  putchar('\n');
}

ソートして表示する

これまで作成してきた関数群を使って、ソートして表示するようにした list_dir 関数は以下となる。


static void list_dir(struct dir_path *base) {
  const char *base_path = base->path;
  int i;
  DIR *dir;
  struct dirent *dent;
  char path[PATH_MAX + 1];
  size_t path_len;
  struct info_list list;
  struct dir_path *subque = base;
  dir = opendir(base_path);
  if (dir == NULL) {
    perror(base_path);
    return;
  }
  path_len = strlen(base_path);
  if (path_len >= PATH_MAX - 1) {
    fprintf(stderr, "too long path\n");
    return;
  }
  strncpy(path, base_path, PATH_MAX);
  if (path[path_len - 1] != '/') {
    path[path_len] = '/';
    path_len++;
    path[path_len] = '\0';
  }
  init_info_list(&list, 100);
  while ((dent = readdir(dir)) != NULL) {
    struct info *info;
    const char *name = dent->d_name;
    if (filter != FILTER_ALL
        && name[0] == '.'
        && (filter == FILTER_DEFAULT
            || name[1 + (name[1] == '.')] == '\0')) {
      continue;
    }
    strncpy(&path[path_len], dent->d_name, PATH_MAX - path_len);
    info = new_info(path, name);
    if (info == NULL) {
      continue;
    }
    add_info(&list, info);
  }
  closedir(dir);
  sort_list(&list);
  for (i = 0; i < list.used; i++) {
    struct info *info = list.array[i];
    if (recursive && S_ISDIR(info->stat.st_mode)) {
      const char *name = info->name;
      if (!(name[0] == '.'
          && name[1 + (name[1] == '.')] == '\0')) {
        strncpy(&path[path_len], name, PATH_MAX - path_len);
        subque->next = new_dir_path(path, base->depth + 1, subque->next);
        subque = subque->next;
      }
    }
    print_info(info);
  }
  free_info_list(&list);
}

以上で、ファイル情報に基づくソート機能を作ることができた。やることは単純だが、処理の構成を変更したり、データ構造とその操作関数を作成したりと、差分が大きくなってしまった。また、ソートを行うということは一度全部のデータをキャッシュする必要があるため、どうしても必要となるリソースが増えてしまっている。一方でこれから機能を追加するという観点で見ても柔軟に対応できる構成になったのではないだろうか。