📝

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

2024/04/21に公開

C言語

42 Tokyo

tech

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

課題

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

方針

scrapboxでよく紹介されている方法は複雑な分岐が発生して辛いです。
色々な実装方法が考えられますが、Examにも出るので、ササッと1時間ぐらいで書けるような実装方法を考える必要があります。
自作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の完成です。
わーい

ボーナスをする場合は、3つのstatic変数を構造体にして1つにまとめればよいです。
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。配列の場合、同じ値になるはずなのですが、機械採点があまり厳密に見ていないのかもしれません。
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も忘れずにネ）。

(補足)配列派？malloc派？

BUFFER_SIZEの領域を配列で持つか？mallocするか？
以下は僕の思想強めの独り言です。各自で判断してください。

正直どっちでもいいと思いますが、個人的には配列派です。
コンパイル時に配列のサイズが分かっているものは静的配列が原則であり、わざわざmallocで動的確保する必要はないと考えるためです。

あえてmalloc派のメリットを挙げるとすれば、主に以下2つがあります。

BUFFER_SIZEのエラー処理ができる
巨大なバッファサイズを指定できる

BUFFER_SIZEが変数であれば、エラー処理は必要ですが、マクロ定数であるBUFFER_SIZEの不正な値のエラー処理のためにmallocを使用するのは、本末転倒な気がします。レビューのためにBUFFER_SIZEを変更することはあっても、マクロであるBUFFER_SIZEのエラー処理まで実装するのは明らかにやり過ぎです。
また、バッファサイズはread呼び出し時のオーバーヘッドを減らし、高速化するために使用しますが、read時のバッファリングは4096バイト以上に上げてもあまり意味はないようです^[3]。INT_MAXのような巨大なバッファサイズを指定できることによるメリットがあるとは考えにくいです^[4]。
他にもstatic変数にmallocした物を放置するとValgrindでStill Reachableとなります。通常それが大きな問題になることはありませんが、mallocを使う理由として挙げられる配列に収まりきらない数GBもあるような巨大なバッファがStill Reachableのまま放置され、開放する手段がないのはやはり問題があると思います。（EOFが来たらfreeする方法がありますが、問題文に標準入力にも対応するように明確に書かれているため、必ずEOFが来ると限りません。）
結局のところ「get_next_lineで巨大なバッファを実装すべき」という前提がそもそも間違っていると考えられます。

ピアレビューの時に突っ込まれたら？
ピアレビューは別にレビュアーが偉くて、レビュイーが弱い立場である訳ではありません。”ピア”である以上対等な立場です。それぞれの実装のメリット・デメリットを把握し、検討した上で、どちらの実装を選んだのか、ちゃんと説明できればよいと思います。少なくとも『絶対にどちらであるべき』とまで強く主張できる理由はないでしょう。

とはいえ、巨大な配列を宣言した時、スタックオーバーフローが発生するという現象自体は知っておく必要があるし、説明できた方がいいと思います。また、自分は配列派だと言いましたが、それはマンダトリパートの話で、ボーナスパートでBUFFER_SIZE×OPEN＿MAXを全部静的配列でやってしまうのはちょっと厳しいと思います（そもそもOPEN_MAXで良いのかという問題もある。僕は線形リストで実装しました）。

もし、mallocしたい場合は、

    static char buf[BUFFER_SIZE];

の所を下記のように変更します。static変数は仕様として初期化されることになっているため、初回呼び出し時bufは必ずNULLであると仮定して問題ありません。FILE構造体も中でmallocしているし、この実装も良いと思います。

  static char *buf;
  if(!buf)　{
    buf = (char *)malloc(BUFFER_SIZE * sizeof(char));
    // bufのエラー処理
  }

いずれにしても「静的配列にするか動的確保するか適切に判断しましょう。安易にmallocするのは反対」ということが言いたいのでした。

脚注

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 ↩︎