「Unix/Linuxプログラミング 理論と実践」読み進めています。
引き続き3章課題について進んでいきます。
3つ目。lsを拡張して、ディレクトリを再帰的に読み込んでいくような機能（ls -R）を実装せよ。
一つ前の記事で拡張したlsを更に拡張して、下記のように実装しました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <sys/types.h>
#include <sys/dirent.h>
#include <unistd.h>
#include <pwd.h>
#include <grp.h>
#include <uuid/uuid.h>
#include <time.h>
#define BUFF_SIZE 4096
//
// 3.18
// implement recursive ls
//
struct sline {
char *mode;
int link;
char *user;
char *group;
int size;
char *datetime;
char *file;
};
struct queue {
char *dir;
struct queue *next;
};
int create_stat_info(struct dirent *entry, struct sline *lentry, const char *root);
int get_digit(int num);
int enqueue(const char *dir, const char *root);
struct queue dequeue(struct queue qp);
static int luser=0, llink=0, lgroup=0, lsize=0;
static struct queue *qp;
int main(int argc, char* argv[])
{
DIR *dp;
struct dirent *dent;
struct sline *lines;
struct queue *tmp;
int i=0, csize=1, cline=0;
char *root;
if (1 < argc) {
root = argv[1];
} else {
root = malloc(sizeof(char) * 2);
strcpy(root, ".");
}
qp = malloc(sizeof(struct queue));
qp->dir = root;
qp->next = NULL;
while(qp != NULL) {
luser=0; llink=0; lgroup=0; lsize=0;
i=0; csize=1; cline=0;
if ((dp=opendir(qp->dir)) == NULL) {
printf("failed to opendir.");
exit(-1);
}
// initialize malloc.
lines = malloc(sizeof(struct sline) * csize);
while ((dent=readdir(dp)) != NULL) {
if (cline+1 > csize) {
csize *= 2;
lines = realloc(lines, sizeof(struct sline) * csize);
}
if (create_stat_info(dent, &lines[cline], qp->dir) != -1) {
cline++;
}
}
// print out
printf("--- stat info of dir '%s' ---\n", qp->dir);
for(i=0; i<cline; i++) {
printf("%s ", lines[i].mode);
printf("%*d ", llink+1, lines[i].link);
printf("%*s ", luser+1, lines[i].user);
printf("%*s ", lgroup+1, lines[i].group);
printf("%*d ", lsize+1, lines[i].size);
printf("%s ", lines[i].datetime);
printf("%s \n", lines[i].file);
}
printf("\n");
tmp = qp;
qp = qp->next;
free(tmp);
free(lines);
closedir(dp);
}
return 1;
}
int create_stat_info(struct dirent *entry, struct sline *lentry, char const *root)
{
// init
struct stat info;
int len;
char *smode, *suser, *sgroup, *sfile, *stime;
struct sline line;
char *filepath;
filepath = malloc(sizeof(char) * (strlen(entry->d_name) + strlen(root) + 1));
strcpy(filepath, root);
len = strlen(root);
filepath[len] = '/';
strcpy(&filepath[len+1], entry->d_name);
// validation.
if (stat(filepath, &info) == -1) {
return -1;
}
if (S_ISDIR(info.st_mode)) {
if (strcmp(".", entry->d_name) != 0 && strcmp("..", entry->d_name) != 0) {
// enqueue
// printf("%s\n", entry->d_name);
if (enqueue(entry->d_name, root) == -1) {
printf("failed to enqueu.");
exit(-1);
}
}
}
// create mode.
smode = malloc(sizeof(char) * 11);
strcpy(smode, "----------");
// inode type.
if (S_ISDIR(info.st_mode)) { smode[0] = 'd'; }
if (S_ISCHR(info.st_mode)) { smode[0] = 'c'; }
if (S_ISBLK(info.st_mode)) { smode[0] = 'b'; }
// permission.
if (info.st_mode & S_IRUSR) { smode[1] = 'r'; }
if (info.st_mode & S_ISUID) { smode[1] = 's'; }
if (info.st_mode & S_IWUSR) { smode[2] = 'w'; }
if (info.st_mode & S_IXUSR) { smode[3] = 'x'; }
if (info.st_mode & S_IRGRP) { smode[4] = 'r'; }
if (info.st_mode & S_ISGID) { smode[4] = 's'; }
if (info.st_mode & S_IWGRP) { smode[5] = 'w'; }
if (info.st_mode & S_IXGRP) { smode[6] = 'x'; }
if (info.st_mode & S_IROTH) { smode[7] = 'r'; }
if (info.st_mode & S_IWOTH) { smode[8] = 'w'; }
if (info.st_mode & S_IXOTH) { smode[9] = 'x'; }
if (info.st_mode & S_ISVTX) { smode[9] = 't'; }
// user
struct passwd* user = getpwuid(info.st_uid);
len = strlen(user->pw_name);
suser = malloc(sizeof(char) * len);
strcpy(suser, user->pw_name);
if (len > luser) {
luser = len;
}
// group
struct group* group = getgrgid(info.st_gid);
len = strlen(group->gr_name);
sgroup = malloc(sizeof(char) * len);
strcpy(sgroup, group->gr_name);
if (len > lgroup) {
lgroup = len;
}
// file
len = strlen(entry->d_name);
sfile = malloc(sizeof(char) * len);
strcpy(sfile, entry->d_name);
// time
struct tm* stm = localtime(&info.st_atimespec.tv_sec);
stime = malloc(sizeof(char) * 17);
strcpy(stime, " ");
sprintf(stime, "%d %2d %2d %02d:%02d", stm->tm_year+1900, stm->tm_mon+1, stm->tm_mday, stm->tm_hour, stm->tm_min);
// link
len = get_digit(info.st_nlink);
if (len > llink) {
llink = len;
}
// size
len = get_digit(info.st_size);
if (len > lsize) {
lsize = len;
}
line.mode = smode;
line.user = suser;
line.group = sgroup;
line.file = sfile;
line.link = info.st_nlink;
line.size = info.st_size;
line.datetime = stime;
*lentry = line;
return 1;
}
int get_digit(int num)
{
int count = 0;
while(1) {
count++;
if (num < 10) {
return count;
}
num = (int)(num / 10);
}
return count;
}
int enqueue(const char *dir, const char *root)
{
char *dirname;
char buff[BUFF_SIZE];
int idx, len;
struct queue *q, *p;
q = malloc(sizeof(struct queue));
strcpy(buff, root);
idx = strlen(root);
buff[idx] = '/';
strcpy(&buff[idx+1], dir);
len = strlen(buff);
dirname = malloc(sizeof(char) * len);
strcpy(dirname, buff);
q->dir = dirname;
q->next = NULL;
p = qp;
while (p->next != NULL) {
p = p->next;
}
p->next = q;
return 1;
}
実行すると下記のように表示される。
一応機能は満たされている。
$ ./a.out --- stat info of dir '.' --- drwxr-xr-x 16 user staff 544 2015 8 12 00:40 . drwxr-xr-x 13 user staff 442 2015 8 12 00:40 .. -rwxr-xr-x 1 user staff 13812 2015 8 12 00:40 a.out drwxr-xr-x 3 user staff 102 2015 8 12 00:39 a.out.dSYM -rw-r--r-- 1 user staff 1748 2015 8 11 09:41 cp03.c -rw-r--r-- 1 user staff 3040 2015 8 11 09:41 cp04.c drwxr-xr-x 4 user staff 136 2015 8 12 00:39 dir drwxr-xr-x 4 user staff 136 2015 8 12 00:39 dir2 -rw-r--r-- 1 user staff 295 2015 8 11 09:21 hoge -rw-r--r-- 1 user staff 490 2015 8 11 09:21 ls01.c -rw-r--r-- 1 user staff 2059 2015 8 11 21:28 ls02.c -rw-r--r-- 1 user staff 3941 2015 8 11 23:03 ls03.c -rw-r--r-- 1 user staff 5419 2015 8 12 00:40 ls04.c -rw-r--r-- 1 user staff 839 2015 8 11 09:31 readtest.c -rw-r--r-- 1 user staff 647 2015 8 11 09:21 statinfo.c -rw-r--r-- 1 user staff 295 2015 8 11 09:32 test.c --- stat info of dir './a.out.dSYM' --- drwxr-xr-x 3 user staff 102 2015 8 12 00:40 . drwxr-xr-x 16 user staff 544 2015 8 12 00:40 .. drwxr-xr-x 4 user staff 136 2015 8 12 00:11 Contents --- stat info of dir './dir' --- drwxr-xr-x 4 user staff 136 2015 8 12 00:40 . drwxr-xr-x 16 user staff 544 2015 8 12 00:40 .. -rw-r--r-- 1 user staff 295 2015 8 10 23:44 fuga -rw-r--r-- 1 user staff 295 2015 8 10 23:44 test.c --- stat info of dir './dir2' --- drwxr-xr-x 4 user staff 136 2015 8 12 00:40 . drwxr-xr-x 16 user staff 544 2015 8 12 00:40 .. -rw-r--r-- 1 user staff 295 2015 8 10 23:46 fuga -rw-r--r-- 1 user staff 295 2015 8 12 00:32 test.c --- stat info of dir './a.out.dSYM/Contents' --- drwxr-xr-x 4 user staff 136 2015 8 12 00:40 . drwxr-xr-x 3 user staff 102 2015 8 12 00:40 .. -rw-r--r-- 1 user staff 634 2015 8 11 23:57 Info.plist drwxr-xr-x 3 user staff 102 2015 8 12 00:11 Resources --- stat info of dir './a.out.dSYM/Contents/Resources' --- drwxr-xr-x 3 user staff 102 2015 8 12 00:40 . drwxr-xr-x 4 user staff 136 2015 8 12 00:40 .. drwxr-xr-x 3 user staff 102 2015 8 12 00:39 DWARF --- stat info of dir './a.out.dSYM/Contents/Resources/DWARF' --- drwxr-xr-x 3 user staff 102 2015 8 12 00:40 . drwxr-xr-x 3 user staff 102 2015 8 12 00:40 .. -rw-r--r-- 1 user staff 15830 2015 8 12 00:39 a.out
今回の実装のポイントとしてはディレクトリをどのように再帰的に読み込むか。です。
アプローチとしては2つ考えられました。深さ優先探索と、幅優先探索です。
上記の実装は幅優先探索になります。
深さ優先の場合はディレクトリを発見した瞬間に再帰的にどんどん掘り下げていきます。
直感的でわかりやすい。実際できることならばこちらを選びたかったところがなくは無いです。
なんですがいくつかの問題点があったのですぐに辞めました。
一つ目に先に実装したアライメントについて、これはある一定のグループ（例えばディレクトリ単位）でその表示幅を最大長のものに合わせるような仕組みとして実装しました。
深さ優先にするとこの値が決定するまでにすごく時間がかかる。更に非常にバラける可能性がある。
と言うかそもそも、探索したディレクトリも含めて表示する必要があるので、表示ファイル名が長くなってしまうので全然実用的ではないです。
というわけでシンプルに幅優先で実装しました。
ディレクトリを再帰的に発見した場合は、いったんそのパス情報をキューに入れるようにしました。
それによって非常に効率的に処理できます。
いったん見つけたディレクトリはキューに入れてしまえば現在のプロセスでは考慮しなくてよいです。
プロセスはキューがからになるまで再帰的に処理を続けますので、それらは独立して動いているようになります。
コメントを残す