📝

1時間で書くGet Next Line(GNL)

2024/04/21に公開

C言語

42 Tokyo

tech

by 課題のハードルを下げようの会

課題

static変数を使用してバッファリングしながら、ファイルから1行読み込んで文字列として返す関数を作る。

方針

scrapboxでよく紹介されている方法は複雑な分岐が発生して辛いです。
色々な実装方法が考えられますが、課題要件としてlibft利用不可ということは、別に42が意地悪のためにそう決めているわけではなく、42の意図として『libftを利用しなくても実装できる』ということを意味していると考えられます。
自作getcから作ると、簡単に実装できるのでオススメです。

他の実装でもgetcを使って実装してるよ

get_next_lineの元ネタとなるgetlineという関数があり、GNUやBSD, muslなど様々な実装があります。
下記はgetcを使用してgetlineを実装してる例になります。

まずgetc(3)を実装しよう

僕のオススメはまずはgetc(3)を実装することです。
K&R(カニハン)の209ページにgetchar（単一バッファ版）^[1]のとてもきれいな実装があるのでそれを参考にします。(getcharというのは標準入力から1文字読み取って、1文字返す関数です。)

getchar

/* getchar: 単一バッファ版　*/
int getchar(void)
{
  static char buf[BUFSIZ];
  static char *bufp;
  static int n = 0;

  if(n == 0) { /* バッファはカラ */
    n = read(0, buf, sizeof buf);
    bufp = buf;
  }
  return (--n >= 0) ? (unsignd char) *bufp++ : EOF;
}

もしstatic変数に慣れていないと、プログラムの意味がよく意味が分からないかもしれませんが、最初はNormも無視して、一旦写経して動かしてみて下さい。（写経とコピペは違うよ。面倒くさくても意味を考えながら書き写すとコピペでは気づかなかったことが色々見えてきます。)
最後の行の"?"、":"の意味が分からない人は三項演算子で検索して下さい。

関数に引数からファイル記述子を受け取って、read(0,・・・のところをfdに変更すれば、ファイル記述子版getcの完成です。
わーい

readに失敗した場合、返り値が負の値になるのでエラー処理が必要です。詳しくはman 2 readを読んで下さい。
上のコードではreadエラーや最後までファイルを読み込むとnが負になり、そのまま次のファイルを読み込むとnが負からスタートして動作がおかしくなるので注意しましょう。
噂ではread(fd, buf, sizeof(buf))だと機械採点で『Read with a size different than BUFFER_SIZE』というエラーになるらしいです。read(fd, buf, BUFFER_SIZE)だとOK。配列の場合、同じ値になるはずなのですが、機械採点があまり厳密に見ていないのかもしれません。
ボーナスをする場合は、3つのstatic変数を構造体にして1つにまとめればよいです。
static変数はC言語の仕様として０やNULLに自動で初期化されます^[2]。

自作getcを動かしてみよう

写経できたでしょうか。（コピペしてないよね？）
ではちゃんと写経できたかテストしてみましょう。

main.c

#include "get_next_line.h"
#include <fcntl.h>
#include <stdio.h>

int main(void) {
    int fd;
    int c;

    fd = open("test.txt", O_RDONLY);
    while (1) {
        c = ft_getc(fd);
        if (c == EOF)
            break ;
        printf("%c", c);
    }
    close(fd);
    return (0);
}

test.txtの中身がそのまま出力されていれば成功です。

後は、1行づつ文字列にして返す関数を書けば、get_next_lineの完成です。
簡単ですね。

ここから先はネタバレ

putc(3)を作ろう

バッファリングしながら1文字づつ読み込む関数ft_getcができたので、今度は1文字つづメモリに書き込むft_putc関数を作ろう。1文字づつ書き込むといっても、その度にmallocして、コピーしいては遅くなってしまうし、エラー処理が面倒くさかったりするので、可能であれば呼び出す回数を減らしたいです。
getcでバッファリングして、read回数を減らしたように、putcでもある程度まとめてmallocしたいです。ただし、1行の長さを事前に知ることはできないので、足りなくなったらある程度まとめて容量を再確保する形にします。

typedef struct s_string {
    char *str;　// 文字列
    size_t len; //　文字列の長さ
    size_t capa;　//　確保した領域の大きさ
} t_string;

int ft_putc(t_string *str, char c) {
    if(str->len + 1 > str->capa) {
        // 領域が足りなくなったら新たに確保して、コピー
    }
    str->str[str->len] = c;　// 一文字詰め込む
    str->len++;
    return 0;
}

capaの増やし方は色々あると思いますが、capaを2倍にして再確保することが多いかな。理由は最終的な文字列の長さが $N$ とした時、 $log_2(N)$ 回の再確保で済むので(コピーも含めると計算量は $Nlog_2(N)$ )

あとは文字列を改行まで読み取るだけ

バッファリングしつつ、1文字づつ読み取る関数できたので、後は改行またはEOFが来るまで文字列に1文字づつ詰めて、返してあげればget_next_lineの完成です。

char *get_next_line(int fd) {
    // 今回の場合はt_string　 *retではなく、 t_string retとしておけば、
    // 構造体をmalloc & freeする必要がないので実装が楽になります。
    t_string ret; 
    char c;

    // 初期化
    ret.str = NULL;
    ret.len = 0;
    ret.capa = 0;

    while(1) {　// 無限ループ
        c = ft_getc(fd); // 1文字読み込む

        if(c == EOF) {
            break;　// ファイルの最後ならループから抜ける
        }
        ft_putc(&ret, c);　// 1文字詰める
        if(c == '\n') {
            break;　// 改行だったらループから抜ける
        }
    }
    if(ret.len > 0) {
        ft_putc(&ret, '\0');　// 最後にNULL文字を詰める
    }
    return ret.str;
}

大まかな流れはこんな感じになると思いますが、ft_getcやft_putcはエラーを返す可能性があるので、エラー処理をちゃんとしましょう（エラー処理の時にret.strのfreeも忘れずにネ）。

バッファについて

get_next_lineはバッファについて学ぶ課題ですが、さて結局readのバッファはどのぐらいの大きさにすれば良いのでしょうか？大き過ぎるバッファはリソース（メモリ）を多く使用してしまいますが、大きければ大きいほど速度は早くなるのでしょうか？バッファサイズはどれぐらいに設定するのが最適なのでしょうか？
TLPIではread時のバッファリングは4096バイト以上に上げてもあまり意味はないようです^[3]。
逆に巨大過ぎるバッファサイズはCPUキャッシュが効かなくなり速度が遅くなってしまうようです^[4]。

設計思想について

get_next_lineはとても小さなコードですが、人によって様々な考え方ができます。

バッファをどこに持たせるか？（スタック領域? or ヒープ領域?)
バッファをどこに確保するか。スタック領域つまりサンプルの通りbuf[BUFFER_SIZE]のように、配列で保持するか、それともヒープ領域つまり、mallocするか。バッファをどこに確保しますか？
メモリの最適化？ or 速度の最適化？
上記サンプルコードでは最悪1行の長さの2倍のメモリを確保してしまいますが、本当にそれで良いのでしょうか？それともget_next_lineから返す前に1行の長さにメモリを再確保した方が良いのでしょうか？再確保した場合、メモリの再確保とコピーに余分に時間がかかってしまいます。メモリの利用を最適化しますか？それとも速度を優先しますか？あるいは折衷案として行がある程度長い場合は、再確保してメモリ最適化しますか？

1も2もそれぞれ、どちらの選択をしても間違いではないと思います。両方の案を検討し、なぜその選択をしたのか、自分の設計思想を説明できると、より良いと思います。

脚注

B.W.カーニハン/D.M.リッチー, プログラミング言語C　第2版, 共立出版(1989), 　p.209-210 ↩︎
ISO/IEC 9899, 6.7.8 Initialization, https://port70.net/~nsz/c/c99/n1256.html#6.7.8p10 ↩︎
Michael Kerrisk, Linuxプログラミングインターフェース,　オライリー(2012), 表13-1 ↩︎
プログラムにおける究極のバッファサイズ, https://note.com/yunyun_ja/n/n5373501bbe78 ↩︎