つづき、文字単位コピーからブロック単位コピーにする
fgetcで書ければ、freadで書ける - ラシウラでは、fgetcからfreadを使うように変えました。これは機械的に変換しただけでしたが、ここからつぎは1文字づつコピーしている部分を、memcpyを使用して、ブロック単位でコピーするように変えてみましょう。
まずリファクタリング
まず、readlines中のバッファ確保の部分を関数として外に出し、readlinesをすっきりさせます。
char ** readlines(FILE * file) { enum {LINES_SIZE = 128}; enum {BUF_SIZE = 1024}; enum {CR = '\r'}; enum {LF = '\n'}; char ** lines = NULL; int lineindex = 0; int lines_size = LINES_SIZE; int index = 0; int line_size = 0; int is_prev_cr = 0; char buf[BUF_SIZE]; assert(file != NULL); lines = malloc(lines_size * sizeof(char *)); if (lines == NULL) goto error; lines[0] = NULL; for (;;) { int i = 0; int count = fread(buf, sizeof(char), BUF_SIZE, file); for (i = 0; i < count; i++) { char ch = buf[i]; if (is_prev_cr) { is_prev_cr = 0; if (ch == LF) continue; } if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!alloc_line(lines, lineindex, &line_size)) goto error; if (!expand_line(&lines[lineindex], index, &line_size)) goto error; if (ch == CR) is_prev_cr = 1; if (ch == CR || ch == LF) { realloc(lines[lineindex], (index + 1) * sizeof(char)); lineindex++; index = 0; } else { lines[lineindex][index] = (char) ch; index++; lines[lineindex][index] = '\0'; } } if (feof(file)) break; } realloc(lines, (lineindex + 2) * sizeof(char *)); return lines; error: freelines(lines); return NULL; }
expand_lines、alloc_line、expand_lineとして切り分けました。これらは以下のように実装です。更新する変数はそのポインタが渡るようにするくらいであり、をこれも機械的に行っています。
static int expand_lines(char *** plines, int lineindex, int * plines_size) { if (lineindex + 1 == *plines_size) { char ** expanded; *plines_size *= 2; expanded = realloc(*plines, *plines_size * sizeof(char *)); if (expanded == NULL) return 0; *plines = expanded; } return 1; }
static int alloc_line(char ** lines, int lineindex, int* pline_size) { enum {LINE_SIZE = 128}; if (lines[lineindex] == NULL) { *pline_size = LINE_SIZE; lines[lineindex] = malloc(*pline_size * sizeof(char)); if (lines[lineindex] == NULL) return 0; lines[lineindex + 1] = NULL; lines[lineindex][0] = '\0'; } return 1; }
static int expand_line(char ** pline, int index, int * pline_size) { if (index + 1 == *pline_size) { char * expanded; *pline_size *= 2; expanded = realloc(*pline, *pline_size * sizeof(char)); if (expanded == NULL) return 0; *pline = expanded; } return 1; }
ブロック単位コピー化する
バッファbufをブロック単位でコピーするためには、そのコピー範囲が必要です。
そこでループ中の処理は、コピー範囲(つまり、始点と終点)を探すものに変わります。
そして、いつコピーするか、を考える必要がでてきます。これは、改行が出たとき、そして、バッファの終端に届いたとき、の二箇所で行うことになります。
擬似コードでは、以下のようになるでしょう.
for (;;) { int 始点 = 0, 終点 = 0; count = fread(buf, sizeof(char), BUF_SIZE, file); for (i = 0; i < count; i++) { char ch = buf[i]; if (前がCR && ch == LF) { 始点、終点ともに1進む; continue; } if (ch == CR || ch == LF) { 現在行バッファを確保、拡張; 現在行バッファにbuf[始点...終点]をコピー; 次の行にいく; 終点が1進む; 始点 = 終点; } else { 終点が1進む; } } if (未コピー分がある場合) { 現在行バッファを確保、拡張; 現在行バッファにbuf[始点...終点]をコピー; } if (feof(file)) break; }
reallocでは、第一引数がNULLの場合、mallocと同じ動作になります。
前出のコードでは、行バッファは初期サイズから倍倍にしていくため、行バッファの確保と拡張を別々にしていました。
今回確保でも拡張でもコピーする分だけ確保できれば良く、確保すべき長さがわかっているため、確保も拡張もreallocで行うよう統一した、realloc_line関数で行うことにします。
readlines関数は以下のようになります。
char ** readlines(FILE * file) { enum {LINES_SIZE = 25}; enum {BUF_SIZE = 1024}; enum {CR = '\r'}; enum {LF = '\n'}; char ** lines = NULL; int lineindex = 0; int lines_size = LINES_SIZE; int index = 0; int is_prev_cr = 0; char buf[BUF_SIZE]; assert(file != NULL); lines = malloc(lines_size * sizeof(char *)); if (lines == NULL) goto error; lines[0] = NULL; for (;;) { int i = 0; int start = 0, end = 0; int count = fread(buf, sizeof(char), BUF_SIZE, file); for (i = 0; i < count; i++) { char ch = buf[i]; if (is_prev_cr) { is_prev_cr = 0; if (ch == LF) { end++; start++; continue; } } if (ch == CR) is_prev_cr = 1; if (ch == CR || ch == LF) { int len = end - start; if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!realloc_line(lines, lineindex, index + len + 1)) goto error; memcpy(&lines[lineindex][index], &buf[start], len); lines[lineindex][index + len] = '\0'; lineindex++; index = 0; end++; start = end; } else { end++; } } if (start != end) { int len = end - start; if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!realloc_line(lines, lineindex, index + len + 1)) goto error; memcpy(&lines[lineindex][index], &buf[start], len); lines[lineindex][index + len] = '\0'; index += len; } if (feof(file)) break; } realloc(lines, (lineindex + 2) * sizeof(char *)); return lines; error: freelines(lines); return NULL; }
static int realloc_line(char ** lines, int lineindex, int line_size) { char * buf = realloc(lines[lineindex], line_size * sizeof(char)); if (buf == NULL) return 0; lines[lineindex] = buf; lines[lineindex + 1] = NULL; return 1; }
バッファ拡張の部分は2箇所とも同じなので、同様に(copy_to_lineなどと名づけた関数にでも)一つにまとめれば、意外とすっきりしたコードになるでしょう。
いきなりこの関数実装をみてブロック処理がわからなくても、fgetcで一文字づつ処理する実装から変化させていくのを段階的に見ていけば、ブロック単位処理も難しいものではないことがわかるでしょう。
java.nioのBufferを使う処理も、このような処理方法で行うことになるでしょう。
put it together
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> char ** readlines(FILE *); void putlines(char **); void freelines(char **); int main(int argc, char ** argv) { FILE * file = NULL; char ** lines = NULL; char * filename = NULL; if (argc != 2) return EXIT_FAILURE; filename = argv[1]; file = fopen(filename, "r"); lines = readlines(file); fclose(file); putlines(lines); freelines(lines); return EXIT_SUCCESS; } static int realloc_line(char ** lines, int linecount, int line_size); static int expand_lines(char *** plines, int lineindex, int * plines_size); static int copy_line( char ** lines, int lineindex, int index, char * buf, int start, int end); char ** readlines(FILE * file) { enum {LINES_SIZE = 25}; enum {BUF_SIZE = 1024}; enum {CR = '\r'}; enum {LF = '\n'}; char ** lines = NULL; int lineindex = 0; int lines_size = LINES_SIZE; int index = 0; int is_prev_cr = 0; char buf[BUF_SIZE]; assert(file != NULL); lines = malloc(lines_size * sizeof(char *)); if (lines == NULL) goto error; lines[0] = NULL; for (;;) { int i = 0; int start = 0, end = 0; int count = fread(buf, sizeof(char), BUF_SIZE, file); for (i = 0; i < count; i++) { char ch = buf[i]; if (is_prev_cr) { is_prev_cr = 0; if (ch == LF) { end++; start++; continue; } } if (ch == CR) is_prev_cr = 1; if (ch == CR || ch == LF) { if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!copy_line(lines, lineindex, index, buf, start, end)) goto error; lineindex++; index = 0; end++; start = end; } else { end++; } } if (start != end) { if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!copy_line(lines, lineindex, index, buf, start, end)) goto error; index += end - start; } if (feof(file)) break; } realloc(lines, (lineindex + 2) * sizeof(char *)); return lines; error: freelines(lines); return NULL; } void freelines(char ** lines) { char ** cursor; if (lines == NULL) return; for (cursor = lines; *cursor; ++cursor) free(*cursor); free(lines); } void putlines(char ** lines) { char ** cursor; if (lines == NULL) return; for (cursor = lines; *cursor; ++cursor) puts(*cursor); } static int copy_line( char ** lines, int lineindex, int index, char * buf, int start, int end) { int len = end - start; if (!realloc_line(lines, lineindex, index + len + 1)) return 0; memcpy(&lines[lineindex][index], &buf[start], len); lines[lineindex][index + len] = '\0'; return 1; } static int realloc_line(char ** lines, int lineindex, int line_size) { char * buf = realloc(lines[lineindex], line_size * sizeof(char)); if (buf == NULL) return 0; lines[lineindex] = buf; lines[lineindex + 1] = NULL; return 1; } static int expand_lines(char *** plines, int lineindex, int * plines_size) { if (lineindex + 1 == *plines_size) { char ** expanded; *plines_size *= 2; expanded = realloc(*plines, *plines_size * sizeof(char *)); if (expanded == NULL) return 0; *plines = expanded; } return 1; }
余談: fread用バッファを用意せず、行バッファで読み込むようにする、と
freadから取り込むバッファを削ることも可能です。コピー回数とスタックサイズは減りますが、コードは若干複雑化し、おそらくバッファ確保回数も増えるので、パフォーマンスは落ちるでしょう。
char ** readlines(FILE * file) { enum {LINES_SIZE = 25}; enum {BUF_SIZE = 1024}; enum {CR = '\r'}; enum {LF = '\n'}; char ** lines = NULL; int lineindex = 0; int lines_size = LINES_SIZE; int index = 0; int is_prev_cr = 0; char * buf = NULL; assert(file != NULL); lines = malloc(lines_size * sizeof(char *)); if (lines == NULL) goto error; lines[0] = NULL; for (;;) { int i = 0; int start = 0, end = 0; int count; int buf_line_index; int buf_line_size; if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!realloc_line(lines, lineindex, index + BUF_SIZE)) goto error; buf_line_index = lineindex; buf_line_size = index; buf = &lines[lineindex][index]; count = fread(buf, sizeof(char), BUF_SIZE, file); for (i = 0; i < count; i++) { char ch = buf[i]; if (is_prev_cr) { is_prev_cr = 0; if (ch == LF) { end++; start++; continue; } } if (ch == CR) is_prev_cr = 1; if (ch == CR || ch == LF) { int len = end - start; if (buf_line_index != lineindex) { if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!realloc_line(lines, lineindex, index + len + 1)) goto error; memcpy(&lines[lineindex][index], &buf[start], len); } else { buf_line_size += len; } lines[lineindex][index + len] = '\0'; lineindex++; index = 0; end++; start = end; } else { end++; } } if (start != end) { int len = end - start; if (!expand_lines(&lines, lineindex, &lines_size)) goto error; if (!realloc_line(lines, lineindex, index + len + 1)) goto error; memmove(&lines[lineindex][index], &buf[start], len); lines[lineindex][index + len] = '\0'; index += len; } if (buf_line_index != lineindex) { realloc(lines[buf_line_index], buf_line_size * sizeof(char)); } if (feof(file)) break; } realloc(lines, (lineindex + 2) * sizeof(char *)); return lines; error: freelines(lines); return NULL; }
これはやりすぎの例でしょう。