第2回メモリ管理、アルゴリズム2

本日の講義内容

メモリ管理
基本的なデータ構造: 線形リスト

メモリ管理

これまで作ってきたプログラムにおいて、各変数は計算機のメモリに保存されているのでした。配列やポインタの学習にあわせてそうしたイメージを学んだことと思います。今回は、メモリやその管理についてもう少し深堀りしていきます。

メモリ領域

まず、C言語のプログラムで使われるメモリ領域について理解しましょう。C言語のプログラムで宣言された変数は以下に示すいずれかのメモリ領域に確保されます。

静的領域（スタティック領域）

プログラム開始時に確保され、終了まで保持される固定的な領域
グローバル変数や、後述するstatic変数がこの領域に配置される

スタック領域

関数呼び出し時に自動的に確保・解放される一時的な領域
ローカル変数や、関数の引数がこの領域に配置される

ヒープ領域

プログラム実行中に、必要に応じて明示的に確保・解放を行う領域
後述するmallocやcalloc、freeといったメモリ管理関数を使用することで操作する

メモリ領域

これまでのプログラムでは主に静的領域とスタック領域を用いてきました。以下は一般的なプログラムの構成ですが、関数外で定義されたグローバル変数が静的領域に、関数内で宣言、定義された変数はスタック領域に確保されます。配列も同様になります。

example0.c
#include <stdio.h>

// グローバル変数。これは静的領域に確保される
int global_variable = 10; 

void func(int val);

int main(int argc, char **argv) {
    // 以下のval, i , array は mainが呼び出された時にスタック領域に確保される
    int val;
    int array[100];
    for (int i = 0 ; i < 100 ; i++){
        val += i * i;
    }
    printf("gval: %p\n",&global_variable);  // グローバル変数のアドレスを表示
    printf("val: %p\n",&val);  // val のアドレスを表示

    func(val);  // func を呼び出す
    return 0;
}

void func(int val) {
    // 以下のval, i は func が呼び出された時にスタック領域に確保される
    for (int i = 1 ; i < 100 ; i++){
        val %= i;
    }
    printf("val: %p\n",&val);  // val のアドレスを表示
    return;
}

上記のメモリ配置の仕様と、今までに学んだC言語の変数のスコープの仕様について考えてみると、それぞれのうまく対応していることがわかると思います。

グローバル変数は静的領域に配置され、関数の終了とは無関係にプログラム実行中ずっと確保されているので、どの関数からでもアクセス可能。
ローカル変数はスタック領域に配置され、各関数ごとに実行時にスタック領域に確保され、関数の終了と共にその領域が解放されるので、他の関数からはアクセスできない。

今回は上記の領域に加えて、ヒープ領域にメモリを確保することを考えます。

コラム: メモリ領域の実際の配置

上では、メモリ領域のイメージ図を掲載しています、「メモリ上ではこのように並んでいる」という概念図なわけですが、実際のところこれらはどのようなアドレスにどのようにして配置されるのでしょうか。実際のアドレスは、計算機環境によって大きく異なります。たとえば、マイコンなど、ベアメタルと呼ばれるようなOSの無い環境では、どのメモリ領域をどの物理アドレスに配置するかをリンカスクリプト（linker script）といったリンカの設定ファイルで明示的に指定します。一方、LinuxなどのOSが動く環境では事情がすっかり異なり、プログラムが見ているアドレスは仮想的なアドレスになります。これは実際の物理アドレスとは一致しません。OSはプロセス毎に独立した仮想的なアドレス空間を提供し、それが実際にどこに配置されるかはOSによって動的に決定されます。このあたりの詳細に興味のある方は、ローダーや、ページング、MMUといったキーワードで調べてみると面白いと思います。

malloc

mallocはヒープ領域からメモリを確保する関数です。なぜヒープ領域という3種類目のメモリ領域を使うのかは後述するとして、まずは使用例を見てみましょう。mallocはstdlib.hに宣言されている関数です。

#include <stdlib.h>

// malloc 関数: ヒープ領域から指定されたバイト数のメモリを確保しその先頭アドレスを返す
// 以下では100バイトを確保してその先頭アドレスをint型変数のポインタで受け取っている
int *p = malloc(100);

ポインタはメモリ上のアドレスを保持できるため、任意の型のデータが格納される領域を参照するための汎用的な仕組みとして利用できます。これをmallocのような動的メモリ確保関数と組み合わせることで、実行時に配列のサイズを決定してメモリを確保することが可能になります。なおもしメモリを使いすぎてヒープ領域に空きがないような場合には（滅多におきませんが）、NULLが返ります。

まずはスタック領域に配列を確保する場合との違いを以下のコードで見てみましょう。

example1.c
// このコードは関数func()のスタック領域に確保したメモリ領域のアドレスを返すため、
// 関数を抜けた後にアクセスできない領域ということでNG

#include <stdio.h>
#include <stdlib.h>

int *func(int n) {
    // 可変長配列: この関数内だけ有効
    int a[n];

    for (int i = 0 ; i < n ; i++){
    a[i] = i+1;
    }

    return a;
 }

int main() {
    int *b = func(3);

    printf("%d\n",b[0]);
    printf("%d\n",b[1]);
    printf("%d\n",b[2]);

    return 0;
}

example2.c
// このコードは関数func()内でmallocを使い
// ヒープ領域に確保したメモリ領域のアドレスを返すため、
// 関数を抜けた後でもにアクセス可能: OK

#include <stdio.h>
#include <stdlib.h>

int *func(int n) {
    int *a = (int*)malloc(n * sizeof(int));

    // 実際は a に正しく領域が確保されたか確認する必要があるが
    // ここでは一旦省略

    for (int i = 0 ; i < n ; i++){
        a[i] = i+1;
    }

    return a;
}

int main(){
    int *b = func(3);

    printf("%d\n",b[0]);
    printf("%d\n",b[1]);
    printf("%d\n",b[2]);

    return 0;
}

演習

上記のソースコードexample1.cとexample2.cのそれぞれについてコンパイルし、実行して、どのような結果になるか見てみましょう。

最近のコンパイラは賢いのでおそらく上の方のコードでは警告が出てきたかと思います。ただしコンパイル自体は通ってしまうと思います。解放済みのメモリ領域にアクセスしようとすると、今回見られたようなことが起きます。

free

使い終わったメモリ領域を解放し再使用可能にする関数、すなわち、mallocを使って割り当てたメモリ領域を「もう使わないよ」と解放するのがfree関数です。プログラム全体を通してmallocとfreeは対になっています。動的メモリ確保を使った典型的な例は以下のようになります。

// 確保したい型のサイズをsizeof演算子で取得し、個数をかけて確保
// 型のキャストは必須ではないがこのようにすることが多い
int *ptr = (int *)malloc(10 * sizeof(int));

// 確保に失敗していないかチェックする
if (ptr == NULL){
    exit(1);  // return EXIT_FAILURE; の別の書き方: exit関数で返り値1 でプログラム終了
}

// 確保した領域は配列同様に使用できる
ptr[0] = 123;
ptr[1] = 551;
ptr[2] = 334;
ptr[3] = 114514;

// do something; ...
//（中略）

// 使い終わったら解放する
free(ptr);

スタック領域とヒープ領域の比較

確保や解放の方法と、容量の観点でスタック領域とヒープ領域を比較すると以下のようになります。

	スタック	ヒープ
確保と解放	変数宣言/関数終了で自動的に確保・解放	malloc/freeを使う
容量変更	事後的に変更できない	確保時に動的に指定可能
容量	（相対的に）小さい	（相対的に）大きい

スタック領域は関数の終了とともに解放されるため、複数の関数を跨いで共通のデータをやり取りする場合には不向きです。一方で関数内で一時的な処理をする場合には、関数終了時に解放されるので意識せずに利用できます。スタック領域の容量はヒープに比べると小さいため（だいたい数MBぐらいのことが多い）、多くのメモリをスタック領域に確保するようなケースは不向きです。

ヒープ領域は、確保や解放はmalloc/freeを用いてプログラマが行う必要があり、面倒ですが、サイズを動的に決定でき、容量もスタック領域より大きいです。また複数の関数を跨ぐデータのやりとりはmallocした領域のアドレスをポインタでやりとりすることで実現します。例えばスタック領域に大規模な配列を確保した以下のようなプログラムは他に何もしていませんが、セグメンテーションフォルトで落ちます。これはスタック領域へのメモリ確保に失敗した例です。

example3.c
#include <stdio.h>
int main() {
    char a[100000000];  // 100MB 確保!
    printf("Do something\n");
    return 0;
}

一方ヒープ領域への確保は問題なく動くと思います。

example4.c
// ヒープ領域に大規模なメモリを確保しようとした場合
#include <stdio.h>
#include <stdlib.h>
int main() {
    char *a = malloc(sizeof(char)*100000000);
    if (a != NULL){
        printf("確保成功\n");
    }
    return 0;
}

演習

上記のソースコードexample3.cとexample4.cのそれぞれについてコンパイルし、実行して、どのような結果になるか見てみましょう。

エラーの捕捉

先ほどmallocを実行後のエラーチェックとして、簡易的にNULLとの一致を確認していました。最近のマシンはメモリも多く、メモリ不足によるエラーは再現しにくいのですが、以下のコードで、malloc失敗ケースを再現してみましょう。エラーを捕捉する場合、mallocの返り値を検査するのが第一ですが、errno.hという標準ライブラリヘッダを読みこむことで追加の情報を取得できます。

example5.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>  // エラー情報を取得するための標準ライブラリ
#include <string.h>  // strerror を使う
#include <stdint.h>  // **SIZE_MAX のために追記**

int main() {
    // errno.h で定義されるグローバル変数
    // エラーが起きた場合、エラーの種類に対応する値がセットされる
    errno = 0;
    // まずは -1 を size_t にキャストすると何がみえるでしょう
    printf("OUTPUT (-1): %zu\n",(size_t)-1);

    // SIZE_MAX という値も出力してみましょう
    printf("OUTPUT (SIZE_MAX): %zu\n",SIZE_MAX);

    // malloc は size_t を引数にとります。それ以外は型変換されます
    int *a = (int*)malloc(-1);

    if (a == NULL){
        // stdio.h に定義されたperrorを用いる場合
        perror("PERROR OUTPUT: ");

        // string.h に定義されたstrerrorを用いる場合
        fprintf(stderr,"ERROR at %s : %s\n", __func__, strerror(errno));

        exit (EXIT_FAILURE);
    }

    free(a);
    return 0;
}

まず-1をsize_tにキャストするという特殊な処理をしています。実はこれによりSIZE_MAXという、size_tがとりうる最大値を取得できます。この値は十分巨大であるので、今回mallocに無理をさせるのに使います。

perrorは現在のerrnoの値から（グローバル変数であるため引数なしで取得可能）、エラーの情報を標準エラー出力に出力します。このとき引数に、その前に追加する文字列を設定できます。strerrorはerrnoを引数にとり、エラー情報の文字列へのポインタを返します。なおerrnoは、その後何かの関数が正常終了しても値がリセットされないため、複数回使う場合は適宜0を代入しなおします（今回はexitするつもりなので特に関係なしです）。

__func__はC99で追加されたマクロの一つで、現在の関数の名前に置き換わります。デバッグに有用な情報を出力できます。

実際にエラー処理まで考慮すると初期化部分が複雑になることがあります。実際にアプリケーションで用いる場合は、生のmallocとエラー検査を含んだ初期化関数を作ると見通しよく記述できます。ただし今日の講義のサンプルコードでは、簡単のためエラー検査を省略していることがあります。

演習

上記のソースコードexample5.cをコンパイルし、実行して、どのような結果になるか見てみましょう。

構造体と動的メモリ確保

mallocは構造体にも使用可能です。特に構造体を新たに確保して様々な関数で利用する場合によく利用されます。たとえば、以下のようなコードでは、Point構造体を新たに確保してそのアドレスを返しています。

example6.c
#include <stdio.h>
#include <stdlib.h>

// 構造体の確保と初期化を malloc で行う例

typedef struct point {
    int x;
    int y;
} Point;

// Point構造体の初期化関数: 関数内で malloc し、そのアドレスを返している
Point *init_point(int x, int y){
    Point *ptr = (Point*) malloc(sizeof(Point));

    ptr->x = x;
    ptr->y = y;

    return ptr;   
}

int main() {
    Point *p = init_point(10, 20);

    printf("(%d %d)\n", p->x, p->y);

    free(p);

    return 0;
}

こうした記述に初期化指示子と複合リテラルを組み合わせると以下のようになります。ここでmallocで確保したアドレスが指す領域を*ptrで指定し、ここに複合リテラルで構成された構造体をそのまま代入していることに気をつけてください。講義冒頭の例と同様、スタック領域に構造体を確保してそのアドレスを返すのではNGです。

// Point構造体の初期化関数: 関数内でmalloc し、そのアドレスを返している
// 初期化指示子と複合リテラルを利用
Point *init_point(int x, int y){
    Point *ptr = (Point*) malloc(sizeof(Point));
    // 最初の *を忘れないこと
    *ptr = (Point){ .x = x, .y = y};

    return ptr;
}

以下は具体的なNGコードです。

// Point構造体の初期化関数の失敗例
// 関数内で構造体を宣言し、複合リテラルで初期化した上で、そのアドレスを返す
// この場合はスタック領域に確保されるため、関数終了時に自動解放されてしまう
Point *init_point(int x, int y) {
    Point pt = (Point){ .x = x, .y = y};
    return &pt;
}

配列と動的メモリ確保

上で示した例のようにmallocによりメモリ領域を確保し、ポインタでアドレスを受け取ることで、配列と同じように使うことができます。ただし何度もでてきたsizeof を使った要素数取得のテクニックは使えません。たとえば、以下のコードの結果はどのようになるでしょうか?

example7.c
#include <stdio.h>
#include <stdlib.h>

int main() {
    int *ptr = (int *)malloc(10 * sizeof(int));

    if (ptr == NULL) exit(1);

    printf("%lu\n", sizeof(ptr) / sizeof(ptr[0]));

    return 0;
}

演習

上記のソースコードexample7.cをコンパイルし、実行して、どのような結果になるか見てみましょう。

sizeof演算子を配列に適用して配列全体のメモリ領域のサイズを返す構文は同一関数内で宣言された配列（スタック領域の変数）か静的領域での配列についてのみ有効です。関数で配列を渡す場合はポインタになるという原則から、他の関数に対して配列サイズも一緒に渡していたのを思い出しましょう。

calloc

mallocはヒープ領域から使えるメモリ領域を確保してきてその先頭ポインタを返します。使える領域だとしてもそこにどのような値が入っているかは決まっていません。前回使用した状態で散らかっていることも十分考えられます。以下のプログラムで確保した領域がどのような状態か確認してみましょう

example8.c
// この例は一度ヒープを確保して値を代入、free後に、もう一度malloc しています
// どの領域が確保されるかは状況に依存しますが、
// 同じアドレスの場合は前の値が残っていることがわかります。
#include <stdio.h>
#include <stdlib.h>

int main() {
    // 一旦確保して散らかす
    int *ptr = (int*)malloc(10 * sizeof(int));
    if (ptr == NULL) exit(1);

    printf("%p\n", ptr);

    for(int i = 0 ; i < 10 ; i++){
        ptr[i] = i*i;
    }
    free(ptr);

    // ここからが本番
    ptr = (int*)malloc(10 * sizeof(int));
    if (ptr == NULL) exit(1);

    printf("%p\n", ptr);

    // 初期化せずに表示すると
    for(int i = 0 ; i < 10 ; i++){
        printf("%d: %d\n", i, ptr[i]);
    }
}

ヒープに確保した領域をとりあえず全てのビットを0で埋めたい場合は、mallocの親戚であるcallocを使います。

ptr = calloc(size_t count, size_t size);

演習

上記のソースコードexample8.cをコンパイルし、実行して、どのような結果になるか見てみましょう。
後半部分のメモリ確保をcallocで置き換えて、どのような結果になるか改めて見てみましょう。

メモリ管理の注意点

mallocで割り当てられたヒープ領域をfreeで解放する際、以下の点に注意しましょう。

スタック領域や代入前のポインタは絶対にfreeしない
二重解放（同じアドレスを2回free）は危険
- これを防ぐために解放後にNULLを代入をするのは有効、free(NULL)であれば何も起こらない

以下にOK/NG の例を示します。

int *a = (int *)malloc(10 * sizeof(int));
int *b;
int c[10];

free(a);  // OK
a = NULL;  // ok
free(b);  // NG
free(c);  // NG

また、確保されたアドレスをfree前に忘れると、そのメモリ領域へのアクセス手段がなくなります。複数回のmallocを繰り返すようなプログラムでこのような状態になると、場合によってはメモリが枯渇してしまうことがあります。たとえば以下のコードはmallocされた領域へのアクセス手段を失っており、メモリリークの原因となります。

int number = 10;
int *a = (int *)malloc(number * sizeof(int));
a = &number;  // ここで先ほど確保したアドレス情報を失う
// 以後最初にmallocされた領域へのアクセスはできない

コラム: プログラミング言語ごとのメモリ管理の違い

これまで見てきたように、C言語ではメモリの管理はmallocやfreeといった関数を用いて行いました。一方、他のプログラミング言語ではどのような仕組みでメモリを管理しているのでしょうか。たとえば、Pythonでは、基本的にメモリ管理はランタイムで自動的に行われます。ガベージコレクションと呼ばれるような仕組みを通して、オブジェクトが参照されなくなると、そのオブジェクトは自動的に解放されます。これには、プログラマがメモリ管理についてそれほど考えなくてよいというメリットがあります。一方、C言語のような管理方法には前述したような注意点も存在するものの、メモリ配置の細かい制御や、オーバーヘッドの少ない動作を実現できるというメリットがあります。Rustではまた別の仕組みでメモリ管理がおこなわれます。プログラミング言語の設計思想をよく反映しており、評価の観点も多様なので奥が深いです。

記憶クラス指定子

今回、変数を格納するメモリ領域について詳細に学びました。一方、前回の講義では分割コンパイルについて学んだのでした。ここで、改めて、分割コンパイルを行う際にグローバル変数などがどのように扱われるのかについて詳しく見てみましょう。記憶クラス指定子は、その際重要になる概念です。

グローバル変数

グローバル変数は関数外で宣言して、それぞれの関数から参照するものでした。以前のようにファイルが1つなら扱いはシンプルでしたが、分割コンパイルする場合にはどのようになるでしょうか。

まず単純にヘッダファイルがない場合を考えてみましょう。以下のような2つのファイルに分割するとどうでしょうか？

main.c
#include <stdio.h>

void foo(void);

int main(){
    foo();
    printf("%d\n", x);  // グローバル変数xはきっとどこかにある......
    return 0;
}

foo.c
int x = 0;  // とりあえず、ここにグローバル変数xを書いてみる

void foo(){
    x += 1024;
}

これを以下の手順でコンパイルしてみます。

演習

上記のソースコードfoo.cとmain.cについて、

$ gcc -c foo.c
$ gcc -c main.c

と分割コンパイルし、どのような結果になるか見てみましょう。

続いて、下のように修正して再度トライしてみましょう。

main2.c
#include <stdio.h>

void foo(void);
int x = 0;  // ここにグローバルで書いておこう

int main(){
    foo();
    printf("%d\n", x);
    return 0;
}

演習

上記のソースコードmain2.cについて、

$ gcc -c main2.c

とコンパイルし、foo.cをコンパイルして生成されたオブジェクトファイルとリンクし、どのような結果になるか見てみましょう。

以上の結果から、分割コンパイルでグローバル変数を扱う場合は、このファイル上に定義はないけれど、グローバル変数はどこかにちゃんとありますということを伝えてやるための記述が必要になります。変数を使える状態にするには宣言と定義がありました。これは関数におけるプロトタイプ宣言と実際の定義の関係と同じです。

宣言

どのような変数があるかを示す。すなわち、名前と型を知らせる。

定義

宣言された変数にメモリ領域を割り当てる。

分割コンパイルの考え方では変数の宣言はヘッダファイルに、変数の定義は実装するCファイルに書くようにします。この宣言時に、この変数の定義はどこか別のところにある、と示すのがextern指定子です。

extern指定子

extern指定子は、変数の宣言時に用いて、別の場所に定義が存在することを明示する指定子です。ヘッダファイルがない場合でも、宣言と定義を分けてその役割を明示します。externに関わるポイントは以下です。

externは宣言のみに用いるため、extern指定子と初期化は同時には行わない。
externで宣言された変数が、リンク時にどの場所でも定義されていない場合はエラー。

まずはヘッダファイルを用いずに先ほどまでのコードにextern指定子をつけてみましょう。

main3.c
#include <stdio.h>

void foo(void);
extern int x; // ここではないどこかに定義があります

int main(){
    foo();
    printf("%d\n", x);
    return 0;
}

foo2.c
int x = 0;  // ここでグローバル変数を定義

void foo(){
    x += 1024;
}

演習

上記のソースコードmain3.cについて、

$ gcc -c main3.c
$ gcc -c foo2.c

とコンパイルし、それぞれのオブジェクトファイルをリンクし、どのような結果になるか見てみましょう。

さらに、ヘッダファイルを分割した場合についても見てみましょう。

foo.h
#pragma once

void foo(void);
extern int x;

foo.c
#include "foo.h"

void foo(void) {
    x += 1024;
}

main.c
#include <stdio.h>
#include <stdlib.h>
#include "foo.h"

int main(void) {
    foo();

    printf("%d\n",x);

    return 0;
}

この例では、ヘッダファイルで、extern指定子のついた変数宣言が行われ、これが各Cファイルにincludeされています。

演習

上記のソースコードについて、まずそのままコンパイルしてみましょう
続いて、foo.cにグローバル変数の定義を追加してコンパイルしてみましょう。

最初の結果から、externによって、使うべき変数の未定義を正しく検出することができたかと思います。これを経て修正することで正しくコードが動きます。このように未定義を適切に捉えられること、変数の参照関係を正しく記述できることから、ヘッダファイルでexternをつけて宣言し、最も関連するソースコードで定義を行うという書き方をしておくとよいでしょう。

コラム: 仮定義

extern指定子も初期化子もないグローバル変数の宣言は仮定義 (tentative definition)となります。仮定義とは、

他に定義がない場合は0初期化の定義扱い
他に定義がある場合には宣言となる

というようなものです。たとえば、同一ファイル内に、

int x = 1024;
int x = 0;

という記述があった場合、これをコンパイルすると多重定義のエラーになると思います。これは当たり前と思うかもしれません。一方、

int x = 1024;
int x;

とすると、2行目の記述は仮定義となり、なんと、多重定義のエラーにならない (!) と思います。さらに、xの値を確かめてみると1024になると思います。一昔前の処理系では、このような言語仕様と、複数ファイルへの分割が絡んだ場合、かなりトリッキーな事象が発生していたのですが、現在の処理系ではそのようなことはなくなっていると思います。興味のある方は仮定義や、GCC/Clangの-fcommon/-fno-commonオプションなどについて調べてみるとよいでしょう。

static指定子

static指定子は分割コンパイルにおいては特に重要な指定子です。以下で説明するように、関数の中で使う場合と関数の外で使う場合で異なる意味になることに注意しておきましょう。

関数の中でのstatic指定子

関数内でstatic指定子を用いる場合は、変数のメモリ領域として、通常のスタック領域ではなく静的領域を用いることを示しています。スタック領域の変数は関数の実行のたびに確保・解放がされるのでした。一方、静的領域に置かれると、プログラムの開始から終了まで保持されます。なお、static変数の定義は、関数が最初に呼び出されたときにのみ実行されます。

count.c
#include <stdio.h>

int count(){
    static int c = 0;

    c++;
    return c;
}

int main(){
    for (int i = 0 ; i < 10 ; i++){
        printf("%d\n", count());
    }
    return 0;
}

演習

上記のcount.cを写経して、まずそのままコンパイル・実行してみましょう。
続いて、count()内の変数cのstatic宣言をstatic int c; c = 0;と2行にわたってかくとどのような結果になるか確かめてみましょう。

関数の外でのstatic指定子

関数の外で使うstatic指定子は、関数内で使う場合とは異なる意味を持ちます。関数の外でstatic指定子をつけた変数や関数は、そのファイル内でのみ有効になります。これを内部リンケージを持つといいます。逆に言えば、static宣言がついていれば、同じ名前の変数や関数が複数のファイルに存在しても問題ありません。このようにstatic指定子を使うことで、特定のファイル内だけで使うローカルな定義を作成でき、機能を適切に隠蔽できます。なお、static指定子のついた関数は外部に公開しない前提なので、ヘッダファイルには記述しないようにしましょう。

線形リスト

今日は基本的なデータ構造の一つである線形リストについて学びましょう。線形リストは「データ」と「参照」をセットにした要素によって構成されるデータ構造です。各要素はデータを持っており、それに加えて次にどの要素にアクセスすべきかのアドレスをセットで持っておくことで、順々にデータにアクセスすることができます。もう後ろにデータがないという状態は、NULLなどの特殊なアドレスを参照することで実現できます。

連結リスト

線形リストには参照が一方向のみの片方向リストと二方向を参照する双方向リストがありますが、ここでは片方向リストを扱います。なお、これまで使ってきた配列も立派なデータ構造です。線形リストと配列の特徴を比較すると以下のようになります。

	線形リスト	配列
要素の挿入・削除	コストが小さい（ポインタをつなぎかえるだけ）	コストが高い
要素数の制限	なし（ヒープ領域に追加確保するだけ）	あり（C言語では一般に固定）
ランダムアクセス	コストが高い	簡単（インデックスを指定するだけ）

実装方法

C言語には言語仕様自体には線形リストは実装されていません。今回も自己参照構造体を用いて実装していきます。自己参照構造体とは、自分自身と同じ型を指すポインタをメンバとして持つ構造体のことでした。例えば山手線の駅をつなぐ片方向リストを作成する場合、以下のような構造体を定義します。

struct station{
    char name[20];
    int birthyear;
    struct station *next;
};

ここで重要となるのは最後のメンバであるポインタです。このポインタに次にさすstruct stationのアドレスを格納することで、要素を順々につなぐことができます。

操作例: 先頭への挿入

線形リストに新たにデータを加えるための基本操作は

加えるデータを確保する領域をヒープに確保
ポインタのアドレスを適切に張り替える

の2つです。まずは先頭にデータを挿入する場合は以下の図のようになります。

先頭に挿入01 先頭に挿入02

操作例: 途中への挿入

途中挿入の場合も基本的な操作は同じです。

途中に挿入01 途中に挿入02

操作例: 要素の削除

要素を削除する場合は、

先に新しい接続関係を確保しておく
その上で削除する要素を解放する

という手順を踏みます。

削除01 削除02

実装例

線形リストのサンプルプログラムlist.cを使って線形リストの実装に触れてみましょう。

list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

const int maxlen = 1000;

typedef struct node Node;

struct node {
    char *str;
    Node *next;
};


Node *push_front(Node *begin, const char *str) {

    Node *p = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *p = (Node){.str = s , .next = begin};

    return p; 
}


Node *pop_front(Node *begin) {
    assert(begin != NULL);
    Node *p = begin->next;

    free(begin->str);
    free(begin);

    return p;
}

Node *push_back(Node *begin, const char *str) {
    if (begin == NULL) { 
        return push_front(begin, str);
    }

    Node *p = begin;
    while (p->next != NULL) {
        p = p->next;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *q = (Node){.str = s, .next = NULL};
    p->next = q;

    return begin;
}

// pop_back の実装
Node *pop_back(Node *begin) {
    // 以下に実装する

    return begin;
}


Node *remove_all(Node *begin) {
    while ((begin = pop_front(begin))) ;  // リストが空になるまで pop_front() を繰り返し
    return begin;
}

int main() {
    Node *begin = NULL; 


    char buf[maxlen];
    while (fgets(buf, maxlen, stdin)) {
        begin = push_front(begin, buf);
        //begin = push_back(begin, buf);  // push_front() の代わりにこれを実行してみる
    }

    //begin = pop_front(begin);  // 何が起こるでしょう?
    //begin = pop_back(begin);   // 何が起こるでしょう? 

    //begin = remove_all(begin); // 何が起こるでしょう?

    for (const Node *p = begin; p != NULL; p = p->next) {
        printf("%s", p->str);
    }

    return EXIT_SUCCESS;
}

この処理内容は

標準入力から１行ずつ読み込み、文字列を線形リストに保存
線形リストを先頭から順にたどり、文字列を標準出力に書きだす

となっています。実行する際にはファイルからリダイレクトします。以下のような山手線の駅名が一行一駅書かれたファイルyamanote.txtを用意しておきましょう。

yamanote.txt

Tamachi
Hamamatsucho
Shimbashi
Yurakucho
Tokyo
Kanda
Akihabara
Okachimachi
Ueno
Uguisudani
Nippori
Nishinippori
Tabata
Komagome
Otsuka
Ikebukuro
Mejiro
Takadanobaba
Shinokubo
Shinjuku
Yoyogi
Harajuku
Shibuya
Ebisu
Meguro
Gotanda
Osaki
Shinagawa

演習

上記のソースコードlist.cを以下のように、コンパイルして実行してみましょう。

$ gcc list.c -o linearlist
$ ./linearlist < yamanote.txt

線形リストを操作する際に使う変数および関数は以下のようになっています。線形リストは先頭ノードさえわかれば順に辿れることができるので、この操作時にはこのアドレスだけ考慮します。

Node *begin;  // 先頭ノードへのポインタ
Node *push_front();  // 先頭に要素を追加する関数
Node *push_back();  // 末尾に要素を追加する関数
Node *pop_front();  // 先頭の要素を削除

コラム: pop/push

popやpushはデータ構造へのデータの出し入れを表すのによく使われる単語です。CPUの命令や高級言語においても広く用いられています。たとえば今回の関数名は、後に学習するRustのstd::collections::LinkedListのメソッドと同様の名前になっています。

以降では、list.cを詳細に解説していきます。コードの冒頭では、自己参照構造体を定義しています。

typedef struct node Node;
struct node {
    char *str;
    Node *next;
};

ここでのポイントは

データは文字列（charポインタ）のみ
文字列そのものは保持しない: Node生成時はmallocとstrcpyを使う
typedefによる型名宣言を最初に独立して行い、その後structの定義に入ることで、structの定義中にNodeという型名を使うことを可能にしています。自己参照構造体の場合、typedefと構造体定義を同時にすることはできません（struct node *nextのように書き下すのはOKです）。

push_front() は先頭に要素を挿入する関数です。

Node *push_front(Node *begin, const char *str) {   
    Node *p = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *p = (Node){.str = s , .next = begin};

    return p; 
}

この関数は

入力：リストの先頭へのポインタ、格納する文字列
出力：（挿入後の）リストの先頭へのポインタ

となっており、malloc で、ノードおよび文字列のメモリを確保し、データ（文字列）を保存した後、ポインタを張り替えています。文字列確保時に+1があるのは文字列終端の\0のためです。

pop_front()は先頭の要素を削除する関数です。

Node *pop_front(Node *begin) {
    assert(begin != NULL);
    Node *p = begin->next;

    free(begin->str);
    free(begin);

    return p;
}

この関数は

入力：リストの先頭へのポインタ
出力：（削除後の）リストの先頭へのポインタ

となっており、freeを使って文字列およびノードのメモリを解放しています。先頭のassertはNULLが引数の場合はbegin->nextのアクセスができないためについています。構造体へのポインタがNULLを指していないかの確認は重要なので、プログラムの挙動がおかしい時のチェックポイントの一つと思ってください。

push_back()は末尾に要素を追加する関数です。

Node *push_back(Node *begin, const char *str) {
    if (begin == NULL) { 
        return push_front(begin, str);
    }

    Node *p = begin;
    while (p->next != NULL) {
        p = p->next;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *q = (Node){.str = s, .next = NULL};
    p->next = q;

    return begin;
}

この関数では、末尾の要素に行きつくまでリストを先頭からたどり、その後ろに新たな要素を追加しています。ただしリストが空の場合のみ特別扱いとしています。

演習

list.cに末尾の要素を削除するpop_back()関数を追加してください。
- 特に新たに末尾となる要素の処理に注意しましょう。
main関数内でいろいろなpop/pushの関数を変えてどのような結果になるか確認してください。
- 例えば高輪ゲートウェイをpush_backしてください。
先頭のNode構造体へのポインタをメンバにもつ新たな構造体Listを定義し、前述の関数群をこれを操作するように書き換えてみましょう。
- 関数内でlist->beginを直接更新でき、返り値を他の用途に使えるようになります。
```
typedef struct list{
    Node *begin;
} List;
```
  のようなものを考えます。

こたえ

pop_back()

Node *pop_back(Node *begin){
    // NULLだった場合はすでに要素がない
    // そのまま return してもよいが
    // pop_front() 同様ここでは assert で終了
    assert(begin != NULL);

    Node *p = begin;
    Node *q = NULL;  // pがp->nextに進む前に直前を保存するポインタ

    while (p->next != NULL){
        // nextにいく前に今いるポインタを記憶する
        q = p;
        p = p->next;
    }

    // whileを抜けた時点でpは終端ノード、qは一つ前のノード
    if (q == NULL){
        // qがNULLの場合は1つだけの要素だったものが削除されるケース
        // この時に線形リストに要素がなくなったことを示すためにNULLをreturnする
        free(p->str);
        free(p);
        return NULL;
    }
    // 上のケース以外は q->next が触れる
    // pを削除した時にqは最後のノードになるので、
    // q->next にNULLをセットする
    q->next = NULL;

    // pの削除
    free(p->str);
    free(p);

    return begin;
}

list.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

const int maxlen = 1000;

typedef struct node Node;

struct node {
    char *str;
    Node *next;
};

// List構造体を導入する利点：
// - 関数にList*を渡せば、関数内でlist->beginを直接更新できる
// - 返り値を「新しい先頭ノード」に使う必要がなくなり、他の用途に使える
//   例: pop()で取り出したノードを返り値にできる

typedef struct list {
    Node *begin;  // 線形リストの先頭ノードへのポインタ
} List;
// 以下では挿入したノードへのポインタとしている
// list->begin = p; として先頭ノードを書き換えている
Node *push_front(List *list, const char *str){
    Node *p = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *p = (Node){.str = s, .next = list->begin};
    list->begin = p;

    return p;
}

// 返り値はpopしたデータを指すように変更
// 削除の場合はこれまでと同様freeする
// これまでは新たな先頭を返していたが、今回は値を取り出しつつ先頭の変更が可能
Node *pop_front(List *list){
    Node *p = list->begin;

    if (p != NULL){
        // 次の要素を線形リストの先頭に設定
        list->begin = p->next;

        // 今回はこれまで先頭だったデータが欲しい
        p->next = NULL;

        // 削除の場合は以下を行う
        // free(p->str)
        // free(p);
    }

    return p;
}

// こちらも新たに生成したノードをreturn するように変更
Node *push_back(List *list, const char *str){
    Node *p = list->begin;

    if (p == NULL) return push_front(list,str);

    while (p->next != NULL) {
        p = p->next;
    }

    Node *q = (Node *)malloc(sizeof(Node));
    char *s = (char *)malloc(strlen(str) + 1);
    strcpy(s, str);

    *q = (Node){.str = s, .next = NULL};
    p->next = q;

    return q;
}

// pop_back の実装
Node *pop_back(List *list) {
    Node *p = list->begin;
    Node *q = NULL;

    if (p == NULL) return NULL;

    while (p->next != NULL){
        // nextにいく前に今いるポインタを記憶する
        q = p;
        p = p->next;
    }

    if ( q == NULL ) return pop_front(list);
    // 新たな末尾の設定
    if ( q != NULL) q->next = NULL;

    return p;
    // 削除の場合は以下の処理
    //free(p->str);
    //free(p);
}


void remove_all(List *list){
    Node *p;
    while ((p = pop_front(list))) ;
    return;
}

int main() {
    // 構造体自体はmainのスタック領域に定義
    // push/pop関数にはアドレスで渡す
    List list = (List){ .begin = NULL};

    char buf[maxlen];
    while (fgets(buf, maxlen, stdin)) {
        push_front(&list, buf);
        //push_back(&list, buf);
    }

    Node *p;
    p = pop_front(&list);
    printf("%s", p->str);
    printf("==\n");

    p = pop_back(&list);
    printf("%s", p->str);
    printf("==\n");

    for (const Node *p = list.begin; p != NULL; p = p->next){
        printf("%s", p->str);
    }
    return EXIT_SUCCESS;
}

アプリケーション: ペイントソフト

今日扱った動的メモリ確保や線形リストを扱うアプリケーションとして、コマンド入力によるペイントソフトを扱います。通常のペイントソフトはGUIによる入力ですが、コマンドラインで端末上に描画するアプリケーションを考えます。特にコマンド履歴を取り扱う際に線形リストを使用してみます。

サンプルプログラム

サンプルプログラムはchar**の変数をメンバに持つ構造体をHistory構造体として、コマンドに相当する文字列を順次保存していく形で履歴を管理するペイントプログラムになっています。

ペイント用に現状実装されているコマンドは以下になります。

line: 4つの整数を引数にとり2点間に線をひくコマンド。
save: 現状のコマンド履歴を保存するコマンド。引数に保存するファイル名を入れることもできる。省略するとhistory.txtとなる。
undo: 直前の描画コマンド（現状lineのみ）を取り消すコマンド。
quit: 描画プログラムを終了する。

なお履歴は5つまで保存され、それを超えるとプログラムが終了します。またCtrl-DなどでEOFが投げ込まれた場合も一応ちゃんと終了します。早速コンパイルして実行してみましょう。

paint_arrayhistory.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h> // for error catch

// Structure for canvas
typedef struct {
    int width;
    int height;
    char **canvas;
    char pen;
} Canvas;

// Structure for history (2-D array)
typedef struct {
    size_t max_history;
    size_t bufsize;
    size_t hsize;
    char **commands;
} History;

// functions for Canvas type
Canvas *init_canvas(int width, int height, char pen);
void reset_canvas(Canvas *c);
void print_canvas(Canvas *c);
void free_canvas(Canvas *c);

// display functions
void rewind_screen(unsigned int line);
void clear_command(void);
void clear_screen(void);

// enum for interpret_command results
// interpret_command の結果をより詳細に分割
typedef enum res{ EXIT, LINE, UNDO, SAVE, UNKNOWN, ERRNONINT, ERRLACKARGS} Result;
// Result 型に応じて出力するメッセージを返す
char *strresult(Result res);

int max(const int a, const int b);
void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1);
Result interpret_command(const char *command, History *his, Canvas *c);
void save_history(const char *filename, History *his);


int main(int argc, char **argv) {
    //for history recording
    const int max_history = 5;
    const int bufsize = 1000;
    History his = (History){.max_history = max_history, .bufsize = bufsize, .hsize = 0};

    his.commands = (char**)malloc(his.max_history * sizeof(char*));
    char* tmp = (char*) malloc(his.max_history * his.bufsize * sizeof(char));
    for (int i = 0 ; i < his.max_history ; i++)
    his.commands[i] = tmp + (i * his.bufsize);

    int width;
    int height;
    if (argc != 3){
        fprintf(stderr,"usage: %s <width> <height>\n",argv[0]);
        return EXIT_FAILURE;
    }
    else {
        char *e;
        long w = strtol(argv[1],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[1],e);
            return EXIT_FAILURE;
        }
        long h = strtol(argv[2],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[2],e);
            return EXIT_FAILURE;
        }
        width = (int)w;
        height = (int)h;    
    }
    char pen = '*';

    char buf[his.bufsize];

    Canvas *c = init_canvas(width,height, pen);

    printf("\n"); // required especially for windows env

    while (his.hsize < his.max_history) {
        size_t hsize = his.hsize;
        size_t bufsize = his.bufsize;
        print_canvas(c);
        printf("%zu > ", hsize);
        if(fgets(buf, bufsize, stdin) == NULL) break;

        const Result r = interpret_command(buf, &his,c);

        if (r == EXIT) break;

        // 返ってきた結果に応じてコマンド結果を表示
        clear_command();
        printf("%s\n",strresult(r));
        // LINEの場合はHistory構造体に入れる
        if (r == LINE) {
            strcpy(his.commands[his.hsize], buf);
            his.hsize++;        
        }
        rewind_screen(2); // command results
        clear_command(); // command itself
        rewind_screen(height+2); // rewind the screen to command input

    }

    clear_screen();
    free_canvas(c);

    return 0;
}

Canvas *init_canvas(int width,int height, char pen) {
    Canvas *new = (Canvas *)malloc(sizeof(Canvas));
    new->width = width;
    new->height = height;
    new->canvas = (char **)malloc(width * sizeof(char *));

    char *tmp = (char *)malloc(width*height*sizeof(char));
    memset(tmp, ' ', width*height*sizeof(char));
    for (int i = 0 ; i < width ; i++) {
        new->canvas[i] = tmp + i * height;
    }

    new->pen = pen;
    return new;
}

void reset_canvas(Canvas *c) {
    const int width = c->width;
    const int height = c->height;
    memset(c->canvas[0], ' ', width*height*sizeof(char));
}

void print_canvas(Canvas *c) {
    const int height = c->height;
    const int width = c->width;
    char **canvas = c->canvas;

    // 上の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");

    // 外壁と内側
    for (int y = 0 ; y < height ; y++) {
        printf("|");
        for (int x = 0 ; x < width; x++){
            const char c = canvas[x][y];
            putchar(c);
        }
        printf("|\n");
    }

    // 下の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");
    fflush(stdout);
}

void free_canvas(Canvas *c) {
    free(c->canvas[0]); //  for 2-D array free
    free(c->canvas);
    free(c);
}

void rewind_screen(unsigned int line) {
    printf("\e[%dA",line);
}

void clear_command(void) {
    printf("\e[2K");
}

void clear_screen(void) {
    printf("\e[2J");
}

int max(const int a, const int b) {
    return (a > b) ? a : b;
}

void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1) {
    const int width = c->width;
    const int height = c->height;
    char pen = c->pen;

    const int n = max(abs(x1 - x0), abs(y1 - y0));
    if ( (x0 >= 0) && (x0 < width) && (y0 >= 0) && (y0 < height)) c->canvas[x0][y0] = pen;
    for (int i = 1; i <= n; i++) {
        const int x = x0 + i * (x1 - x0) / n;
        const int y = y0 + i * (y1 - y0) / n;
        if ( (x >= 0) && (x< width) && (y >= 0) && (y < height)) c->canvas[x][y] = pen;
    }
}

void save_history(const char *filename, History *his) {
    const char *default_history_file = "history.txt";
    if (filename == NULL) filename = default_history_file;

    FILE *fp;
    if ((fp = fopen(filename, "w")) == NULL) {
        fprintf(stderr, "error: cannot open %s.\n", filename);
        return;
    }

    for (int i = 0; i < his->hsize; i++) {
        fprintf(fp, "%s", his->commands[i]);
    }

    fclose(fp);
}

Result interpret_command(const char *command, History *his, Canvas *c) {
    char buf[his->bufsize];
    strcpy(buf, command);
    buf[strlen(buf) - 1] = 0;  // remove the newline character at the end

    const char *s = strtok(buf, " ");
    if (s == NULL) {  // 改行だけ入力された場合
        return UNKNOWN;
    }
    // The first token corresponds to command
    if (strcmp(s, "line") == 0) {
        int p[4] = {0};  // p[0]: x0, p[1]: y0, p[2]: x1, p[3]: x1 
        char *b[4];
        for (int i = 0 ; i < 4; i++){
            b[i] = strtok(NULL, " ");
            if (b[i] == NULL){
            return ERRLACKARGS;
            }
        }
        for (int i = 0 ; i < 4 ; i++){
            char *e;
            long v = strtol(b[i],&e, 10);
            if (*e != '\0'){
                return ERRNONINT;
            }
            p[i] = (int)v;
        }

        draw_line(c,p[0],p[1],p[2],p[3]);
        return LINE;
    }

    if (strcmp(s, "save") == 0) {
        s = strtok(NULL, " ");
        save_history(s, his);
        return SAVE;
    }

    if (strcmp(s, "undo") == 0) {
        reset_canvas(c);
        if (his->hsize != 0){
            for (int i = 0; i < his->hsize - 1; i++) {
                interpret_command(his->commands[i], his, c);
            }
            his->hsize--;
        }
        return UNDO;
    }

    if (strcmp(s, "quit") == 0) {
        return EXIT;
    }

    return UNKNOWN;
}

char *strresult(Result res) {
    switch(res) {
        case EXIT:
            break;
        case SAVE:
            return "history saved";
        case LINE:
            return "1 line drawn";
        case UNDO:
            return "undo!";
        case UNKNOWN:
            return "error: unknown command";
        case ERRNONINT:
            return "Non-int value is included";
        case ERRLACKARGS:
            return "Too few arguments";
    }
    return NULL;
}

演習

$ gcc -o paint paint_arrayhistory.c
# w = 80, h = 40 で実行。引数なしで実行すると引数指定の方法が表示される
$ ./paint 80 40 
# 描画領域に合わせてターミナルを調整し、一度quitで終了
0> quit

というように、サンプルプログラムを実行してみましょう。また、

$ ./paint 80 40
0> line 10 10 20 10
1> line 10 10 20 20
2> line 10 10 10 20
3> undo
2> save
2> quit

として、history.txtが生成され、最初の2つのコマンドがテキスト形式で保存されていることを確認しつつ、テキトーに遊んでみましょう。

以降では特に今日の講義に関連する部分や難しそうな部分について解説します。

全体構造は

ヘッダファイルのinclude
構造体定義
- 盤面を表す2次元配列にサイズ情報と描画用の文字種を保存する変数がセットになったCanvas構造体
- 履歴を保存するための文字列の配列に最大配列サイズと現在の配列位置の情報がついたHistory構造体
今回実装する関数のプロトタイプ宣言
- Canvas構造体に関連するもの（主に描画関係）
- ANSIエスケープシーケンスによる巻き戻しや描画クリアに関するもの
- ペイントソフトとしての関数
main関数および各関数の実際の実装

のようになっています。

main関数

main関数内の流れは

History構造体を初期化
ユーザの入力サイズに応じてCanvas構造体をヒープ領域に確保
while文で履歴が一定数になるまで繰り返す
ユーザから1行うけとる。EOFならbreakする。
入力を解釈する
解釈結果が標準コマンドの場合は履歴に追加
描画領域を調整する
whileを抜けたら片付けをしてプログラムを終了する

のようになっています。ユーザの入力サイズを受け取る際に今回はatoiではなくstrtolという関数を用いています。これはatoiがユーザの想定外の入力に対応するのが難しいためです。

コラム: atoiとstrtol

atoiとstrtolはどちらも文字列を整数に変換する関数です。atoiは文字列の先頭から整数に変換します。strtolは文字列の先頭から整数に変換し、変換できない場合は0を返します。atoiはユーザの想定外の入力に対応するのが難しく、たとえば整数以外の文字列が入力された時にエラーを検知できません。そこでここではstrtolを用いています。

#include <stdlib.h>
long strtol(const char *s, char **endptr, int base);

strtolの第1引数は変換対象となる文字列です。第2引数のポインタには、変換出来なかった場合にその箇所のアドレスが格納されます。これによって読み込みできなかった部分を正確に見付けることができます。また、strtolは第3引数として基数を指定することができ、10進数の場合は10を指定します。

Canvas構造体

Canvas構造体の定義は以下です。

typedef struct {
    int width;
    int height;
    char **canvas;
    char pen;
} Canvas;

今回のプログラムではキャンバスを動的に確保しているので、構造体自体にはポインタポインタをメンバとし、構造体を確保する際に必要な領域をmallocします。この実装がinit_canvasです。

Canvas *init_canvas(int width,int height, char pen) {
    Canvas *new = (Canvas *)malloc(sizeof(Canvas));
    new->width = width;
    new->height = height;
    new->canvas = (char **)malloc(width * sizeof(char *));

    char *tmp = (char *)malloc(width*height*sizeof(char));
    memset(tmp, ' ', width*height*sizeof(char));
    for (int i = 0 ; i < width ; i++){
    new->canvas[i] = tmp + i * height;
    }

    new->pen = pen;
    return new;
}

init_canvasで使われているmallocと対になる形でfree_canvasも実装されています。

History構造体

こちらの実装ではchar **で複数のコマンド文字列を保存していき、次の空きインデックスがどこかをhsizeで記録するような実装になっています。

typedef struct {
    size_t max_history;
    size_t bufsize;
    size_t hsize;
    char **commands;
} History;

History構造体については、main関数内で宣言されているのでスタック領域に保存されていますが、その内部のcommandsについてはmallocで必要なサイズを確保しています。

draw_line()

線を引く関数については、離散化した端末上で線を引くために、長い方の軸方向にn等分して点を打つ実装になっています。

void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1) {
    const int width = c->width;
    const int height = c->height;
    char pen = c->pen;

    const int n = max(abs(x1 - x0), abs(y1 - y0));
    if ( (x0 >= 0) && (x0 < width) && (y0 >= 0) && (y0 < height))
        c->canvas[x0][y0] = pen;
   for (int i = 1; i <= n; i++) {
    const int x = x0 + i * (x1 - x0) / n;
    const int y = y0 + i * (y1 - y0) / n;
    if ( (x >= 0) && (x< width) && (y >= 0) && (y < height))
        c->canvas[x][y] = pen;
    }
}

interpret_command()

interpret_command()によって、ユーザから入力されたコマンドを解釈します。冒頭部分を見てみます。

Result interpret_command(const char *command, History *his, Canvas *c) {
    char buf[his->bufsize];
    strcpy(buf, command);
    buf[strlen(buf) - 1] = 0; // remove the newline character at the end

    const char *s = strtok(buf, " ");

    // .... 中略
}

冒頭部分では引数で受け取ったユーザ入力の文字列を関数内で用意したバッファにコピーしたのち、strtokという関数を用いて空白区切りで最初の単語を取り出しています。strtok()は区切り文字（デリミタ）を指定して、そのデリミタで順番に区切って文字列を取り出していく関数です。少し特殊な使い方をする関数で、ポイントとしては、以下のようになります。

第1引数の文字列は書き換えられる。具体的には見つけた区切り文字が\0に置換されていく
最終的に返しているのは置換した\0を末尾とする文字列の先頭へのポインタ
2回目以降はNULLを引数に呼び出す。これはstrtok()の関数内でどこまで切りだしたかが記憶されていることによる（static変数として記録されている）

これにより先頭の単語が取り出せるので、interpret_command()の後半ではその単語（例えばsave, quitなど）に応じて実行を変化させています。

Undo

今回直前のコマンドを取り消すundoが実装されていますが、実装方針は以下です。

キャンバスを初期化し、最初のコマンドから直前のコマンドまでを実行しなおす
コマンドの履歴の長さを1減らす

列挙型について

今回利用している列挙型について説明します。列挙型は「定数のリスト」を作ることのできる特殊な変数です。例えば何パターンかの情報を区別したいが、その値そのものはなんでもいい場合に用います。使い方は

enum tag { name01, name02, name03, name04 } variable;

のように使います。変数variableは、name01,name02,name03,name04 のいずれかの値をとるものとします。これらの定数は実際には整数ですが、整数の値そのものには意味はありません。

今回のプログラムではinterpret_command関数が読み取ったコマンドがどのような種類のものだったかを表す5つの定数を返すようにしています。列挙型も構造体と同様にtypedef と組み合わせて別名をつけることができます。今回はResult型という名前になっています。

typedef enum res{ EXIT, LINE, UNDO, SAVE, UNKNOWN, ERRNONINT, ERRLACKARGS} Result;

これからやること

現在の履歴管理はあらかじめ配列を確保しておき、どのインデックスまで書き込んだかを別変数で保存する形式をとっています。この後の実習ではこれを線形リストによる管理に置き換えます。巨大なプログラムですが、実際に書き換える方針を以下に示します。

構造体名Historyは変更しない
メンバは変更する
線形リストの各要素はコマンド文字列をデータに持ち、次のコマンドへのポインタを持つ
リストの終端が最新のコマンドに対応する

つまり以下のような構造体設計に置き換えます

// 最大履歴と現在位置の情報は持たない
typedef struct command Command;
struct command{
    char *str;
    size_t bufsize;
    Command *next;
};

// コマンドリストの先頭へのポインタをメンバに持つ構造体としてHistoryを考える。
// 履歴がない時点ではbegin = NULL となる。
typedef struct{
    Command *begin;
    size_t bufsize;
} History;

これにより書き換える必要があるのは

main関数冒頭のHistory構造体部分: 初期化方法が変わる
while文: 履歴の上限はなし
現在、History構造体へのポインタを引数に持つ以下の関数（同じプロトタイプで実装可能）
- save_history()
- interpret_command()
hsize相当のものは実装しなくてよいが、もし再現したければ、線形リストを先頭からスキャンしてリストの長さを測る関数を作る。

となります。

なお、実装例はこたえから見ることができます。"[*]" という文字列を検索すると変更点を確認できます。いきなり書くのはなかなか難しいかもしれませんが、読んでみて理解を深めてみてください。

演習

paint_arrayhistory.cをもとに履歴の管理を線形リストで再実装しましょう（ファイル名はpaint.cとします）
- 履歴の追加は末尾追加 (push_back) になります。適宜list.cを参考にしましょう

こたえ

paint.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h> // for error catch

// Structure for canvas
typedef struct {
    int width;
    int height;
    char **canvas;
    char pen;
} Canvas;

// Command 構造体と History構造体
// [*]
typedef struct command Command;
struct command{
    char *str;
    size_t bufsize;
    Command *next;
};

typedef struct {
    Command *begin;
    size_t bufsize; 
} History;

// functions for Canvas type
Canvas *init_canvas(int width, int height, char pen);
void reset_canvas(Canvas *c);
void print_canvas(Canvas *c);
void free_canvas(Canvas *c);

// display functions
void rewind_screen(unsigned int line); 
void clear_command(void);
void clear_screen(void);

// enum for interpret_command results
// interpret_command の結果をより詳細に分割
typedef enum res{ EXIT, LINE, UNDO, SAVE, UNKNOWN, ERRNONINT, ERRLACKARGS, NOCOMMAND} Result;
// Result 型に応じて出力するメッセージを返す
char *strresult(Result res);

int max(const int a, const int b);
void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1);
Result interpret_command(const char *command, History *his, Canvas *c);
void save_history(const char *filename, History *his);

// [*] list.c のpush_backと同じ
Command *push_command(History *his, const char *str);

int main(int argc, char **argv) {
    //for history recording

    const int bufsize = 1000;

    // [*]
    History his = (History){ .begin = NULL, .bufsize = bufsize};

    int width;
    int height;
    if (argc != 3){
        fprintf(stderr,"usage: %s <width> <height>\n",argv[0]);
        return EXIT_FAILURE;
    }
    else {
        char *e;
        long w = strtol(argv[1],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[1],e);
            return EXIT_FAILURE;
        }
        long h = strtol(argv[2],&e,10);
        if (*e != '\0'){
            fprintf(stderr, "%s: irregular character found %s\n", argv[2],e);
            return EXIT_FAILURE;
        }
        width = (int)w;
        height = (int)h;    
    }
    char pen = '*';


    char buf[bufsize];

    Canvas *c = init_canvas(width,height, pen);

    printf("\n"); // required especially for windows env

    while(1){
        // [*]
        // hsize はひとまずなし
        // 作る場合はリスト長を調べる関数を作っておく
        print_canvas(c);
        printf("* > ");
        if(fgets(buf, bufsize, stdin) == NULL) break;

        const Result r = interpret_command(buf, &his, c);

        if (r == EXIT) break;

        // 返ってきた結果に応じてコマンド結果を表示
        clear_command();
        printf("%s\n",strresult(r));
        // LINEの場合はHistory構造体に入れる
        if (r == LINE) {
            // [*]
            push_command(&his,buf);
        }

        rewind_screen(2); // command results
        clear_command(); // command itself
        rewind_screen(height+2); // rewind the screen to command input

    }

    clear_screen();
    free_canvas(c);

    return 0;
}

Canvas *init_canvas(int width,int height, char pen) {
    Canvas *new = (Canvas *)malloc(sizeof(Canvas));
    new->width = width;
    new->height = height;
    new->canvas = (char **)malloc(width * sizeof(char *));

    char *tmp = (char *)malloc(width*height*sizeof(char));
    memset(tmp, ' ', width*height*sizeof(char));
    for (int i = 0 ; i < width ; i++){
        new->canvas[i] = tmp + i * height;
    }

    new->pen = pen;
    return new;
}

void reset_canvas(Canvas *c) {
    const int width = c->width;
    const int height = c->height;
    memset(c->canvas[0], ' ', width*height*sizeof(char));
}


void print_canvas(Canvas *c) {
    const int height = c->height;
    const int width = c->width;
    char **canvas = c->canvas;

    // 上の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");

    // 外壁と内側
    for (int y = 0 ; y < height ; y++) {
        printf("|");
        for (int x = 0 ; x < width; x++){
            const char c = canvas[x][y];
            putchar(c);
        }
        printf("|\n");
    }

    // 下の壁
    printf("+");
    for (int x = 0 ; x < width ; x++) printf("-");
    printf("+\n");
    fflush(stdout);
}

void free_canvas(Canvas *c) {
    free(c->canvas[0]); //  for 2-D array free
    free(c->canvas);
    free(c);
}

void rewind_screen(unsigned int line) {
    printf("\e[%dA",line);
}

void clear_command(void) {
    printf("\e[2K");
}

void clear_screen(void) {
    printf("\e[2J");
}

int max(const int a, const int b) {
    return (a > b) ? a : b;
}

void draw_line(Canvas *c, const int x0, const int y0, const int x1, const int y1) {
    const int width = c->width;
    const int height = c->height;
    char pen = c->pen;

    const int n = max(abs(x1 - x0), abs(y1 - y0));
    if ( (x0 >= 0) && (x0 < width) && (y0 >= 0) && (y0 < height)) c->canvas[x0][y0] = pen;
    for (int i = 1; i <= n; i++) {
        const int x = x0 + i * (x1 - x0) / n;
        const int y = y0 + i * (y1 - y0) / n;
        if ( (x >= 0) && (x< width) && (y >= 0) && (y < height)) c->canvas[x][y] = pen;
    }
}

void save_history(const char *filename, History *his) {
    const char *default_history_file = "history.txt";
    if (filename == NULL) filename = default_history_file;

    FILE *fp;
    if ((fp = fopen(filename, "w")) == NULL) {
        fprintf(stderr, "error: cannot open %s.\n", filename);
        return;
    }
    // [*] 線形リスト版
    for (Command *p = his->begin ; p != NULL ; p = p->next){
        fprintf(fp, "%s", p->str);
    }

    fclose(fp);
}

Result interpret_command(const char *command, History *his, Canvas *c) {
    char buf[his->bufsize];
    strcpy(buf, command);
    buf[strlen(buf) - 1] = 0; // remove the newline character at the end

    const char *s = strtok(buf, " ");
    if (s == NULL){ // 改行だけ入力された場合
        return UNKNOWN;
    }
    // The first token corresponds to command
    if (strcmp(s, "line") == 0) {
        int p[4] = {0}; // p[0]: x0, p[1]: y0, p[2]: x1, p[3]: x1 
        char *b[4];
        for (int i = 0 ; i < 4; i++){
            b[i] = strtok(NULL, " ");
            if (b[i] == NULL){
                return ERRLACKARGS;
            }
        }
        for (int i = 0 ; i < 4 ; i++){
            char *e;
            long v = strtol(b[i],&e, 10);
            if (*e != '\0'){
                return ERRNONINT;
            }
            p[i] = (int)v;
        }

        draw_line(c,p[0],p[1],p[2],p[3]);
        return LINE;
    }

    if (strcmp(s, "save") == 0) {
        s = strtok(NULL, " ");
        save_history(s, his);
        return SAVE;
    }

    if (strcmp(s, "undo") == 0) {
        reset_canvas(c);
        //[*] 線形リストの先頭からスキャンして逐次実行
        // pop_back のスキャン中にinterpret_command を絡めた感じ
        Command *p = his->begin;
        if (p == NULL){
            return NOCOMMAND;
        }
        else{
            Command *q = NULL; // 新たな終端を決める時に使う
            while (p->next != NULL){ // 終端でないコマンドは実行して良い
                interpret_command(p->str, his, c);
                q = p;
                p = p->next;
            }
            // 1つしかないコマンドのundoではリストの先頭を変更する
            if (q == NULL) {
                his->begin = NULL;
            }
            else{
                q->next = NULL;
            }
            free(p->str);
            free(p);    
            return UNDO;
        }  
    }

    if (strcmp(s, "quit") == 0) {
        return EXIT;
    }
    return UNKNOWN;
}

// [*] 線形リストの末尾にpush する
Command *push_command(History *his, const char *str) {
    Command *c = (Command*)malloc(sizeof(Command));
    char *s = (char*)malloc(his->bufsize);
    strcpy(s, str);

    *c = (Command){ .str = s, .bufsize = his->bufsize, .next = NULL};

    Command *p = his->begin;

    if ( p == NULL) {
        his->begin = c;
    }
    else{
        while (p->next != NULL){
            p = p->next;
        }
        p->next = c;
    }
    return c;
}

char *strresult(Result res) {
    switch(res) {
        case EXIT:
            break;
        case SAVE:
            return "history saved";
        case LINE:
            return "1 line drawn";
        case UNDO:
            return "undo!";
        case UNKNOWN:
            return "error: unknown command";
        case ERRNONINT:
            return "Non-int value is included";
        case ERRLACKARGS:
            return "Too few arguments";
        case NOCOMMAND:
            return "No command in history";
        default:
            return NULL;
    }
    return NULL;
}

レポート

本日はここまでです。宿題として以下をお願いします。

Slackで配付した宿題リンクから、レポートを提出してください。
- リンクは公開しないでください
- 締切は次の授業の前日の夜23:59までです（今回の場合、2025/12/17, 23:59）
- リポジトリを更新するかたちで提出してください
  - リポジトリのトップ階層、またはsrcディレクトリ以下など、わかりやすい場所に作成したコードを配置してください
  - 自動採点的な機能はありません
- レポートの内容は以下になります

week2_1

最後の演習のpaint.cに長方形を描くコマンドrectと円を描くコマンドcircleを追加してみましょう。

rectは4つの引数を取り、rect x0 y0 width heightのように、左上の座標と横幅、高さを指定するものとします。塗りつぶさず線で描画します。辺は軸と平行としてよいです。
circleは3つの引数を取り、circle x0 y0 rで中心座標と半径を指定するものとします。塗りつぶさず線で描画します。描画領域の性質上、見た目は正円に見えないですが、その点は無視してください。

第2回 メモリ管理、アルゴリズム2

メモリ管理

メモリ領域

malloc

free

スタック領域とヒープ領域の比較

エラーの捕捉

構造体と動的メモリ確保

配列と動的メモリ確保

calloc

メモリ管理の注意点

記憶クラス指定子

グローバル変数

extern指定子

static指定子

関数の中でのstatic指定子

関数の外でのstatic指定子

線形リスト

実装方法

操作例: 先頭への挿入

操作例: 途中への挿入

操作例: 要素の削除

実装例

アプリケーション: ペイントソフト

サンプルプログラム

レポート

第2回メモリ管理、アルゴリズム2