解答7.1

小型の装置では入力はボタン、出力はLCDパネルなどが多いが、 エレベータでは出力としてモータや(過積載)ブザーを備えるなど 多種多様である.　通常は装置ごとに入出力の方式(プロトコル)を 定めて、専用の関数を作成する. printf/scanfのように多機能な関数を必要とすることはほとんどなく、 大抵は(モータなら回転on/off、 ブザーなら特定の単音の出力など)単純な機能の関数の集まりである.

異常状態の警告も同様であるが、回復処理は装置によって異なる. 共通するのはユーザが対応できる余地はほとんどなく、再起動などが 必要になる場合が多い点である.

解答7.2

定数として使用するメンバはconst宣言されることもある. 例えば解答4.5のbigintで、 要素数cntが一度決定したら 変更されない場合はconst宣言してもよい.
#defineとの違いは構造体変数ごとに初期化の際に別々の値を 設定できることである.

typedef struct bigint {
    const int cnt; 
    int *vec; 
    int size;
} Bigint;

Bigint x = { 10, 0, 0 }; // xは10個(最大80桁)固定
Bigint y = { 20, 0, 0 }; // yは20個(最大160桁)固定

x.cnt,y.cntへの書き込みはコンパイルエラーになる.
またx.vec,y.vecは使用前に領域割り当てが必要なので忘れないこと.

解答7.3

通常の関数は入力に基づいて出力が計算されるので、 出力が固定されるconst宣言は意味がない. ただしC言語では移植性を考慮して、定数を値ではなく (定数を返す)関数として記述する場合がある. 例えばバージョン番号を返す関数は以下のようになる.

static const char str[] = "Version 1.0";
const char* getversion() { return str; }

変数をextern宣言すると名前の衝突の原因となりやすいので、この技法はよく用いられる.

解答7.4

fgetsは改行までを読んで、改行を含めてbufに格納する. もし上限を超える入力が行われた場合にはbufには改行が入らないので strchrなどで判定し、入力を改行まで読んで捨て、最後に改行を出力すればよい.

void foo() {
    char buf[20];
    int c;
    fgets(buf,20,stdin);
    printf("%.20s", buf);
    // 入力バッファの破棄
    if (strchr(buf,'\n')==0) {
        while ((c=getchar()) != '\n')
               /* 破棄 */ ;
        putchar(c);
    }
}

fgetsによる入力とバッファの破棄を一緒に行う関数 getlineを定義するのが望ましい.

解答7.5

解答6.4に追加したものを示す.

new_list,copyはinput_listと同じ構造をしている. 相違点はnewp->valの与え方で、input_listはscanfを用いて標準入力から、 new_listは常に0、copyはコピー元リストから取得する. 要素を走査する部分はduplicatedとほぼ同様である.
なお最初にダミー要素を確保したときに、識別しやすいように 値に-1を代入している. concatはコピーを2回繰り返せばよい. 他はソースを参照. outfileは実行結果である.

List *new_list(int n) {
    List *r = (List*)malloc(sizeof(List));
    List *p = r;
    p->val = -1;

    for (int i=0;i<n;i++) {
        List *newp = (List*)malloc(sizeof(List));
        newp->val = 0;
        p->next = newp;
        p = p->next;
    }
    return r;
}

List *copy(const List *l) {
    List *r = (List*)malloc(sizeof(List));
    List *p = r;
    p->val = -1;

    List *q = l->next;
    for (;q;q=q->next) {
        List *newp = (List*)malloc(sizeof(List));
        newp->val = q->val;
        p->next = newp;
        p = p->next;
    }
    return r;
}

注意: 解放した領域がいつ再利用されるかは環境に依存する. この環境では直後のmallocで再利用されている(アドレスが同じ)ので、 *x1に書き込むと*x4まで変化してしまう. 領域を解放後は値を絶対に使用しないこと. 直後にx1に0を代入すれば誤書き換えを防止できる.

テストプログラム:
// 略
    delete_list(x1);
print_list(x1);
    List *x4 = copy(x3);
print_list(x4);
// 略

実行結果(抜粋):
(0,0x21080)(0,0x21090)(0,0x0)
(1,0x21080)(2,0x21090)(3,0x21150)(0,0x21160)(0,0x21170)(0,0x0)

解答7.6

前問の実行結果を見ると、 List構造体は8バイトであるが、領域は16バイト使用している (アドレスが16ずつ増加). 実は残りの8バイトに使用中かどうかのフラグが格納されている.
(この環境では左から3つめ、9が使用中,8が未使用)

領域とフラグをまとめて表すような構造体を作成し、 malloc/freeをこの構造体を単位として行うようにすれば (OSが管理する)作業領域を圧縮でき、メモリ利用効率がよくなる. 特に組込みシステムではメモリ制約が厳しいので、 このような工夫が必要になる場合が多い.

解答の概略を示す. 最初はプールの確保と解放である. プール全体も線形リストになっている点に注意.

#define POOL_SIZE 100

typedef struct pool {
    struct list vec[POOL_SIZE];       // 領域
    uint32_t    used[POOL_SIZE/32+1]; // 使用中フラグ
    int size;                         // 全体の大きさ
    struct pool *next;                // 次のプール
} Pool;

typedef struct poollist {
    Pool *pool;
    struct poollist *next;  // プール先頭要素の線形リスト
} PoolList;

PoolList root; // 使用しているプール一覧

// プールを1つ確保する
Pool *new_pool_sub() {
    Pool *p = (Pool*)malloc(sizeof(Pool));
    p->vecを0でクリア
    p->usedをすべて未使用にする
    p->next=0;
    return p;
}

// n個の要素を確保する
// 必要数が確保されるまでプールを確保し
// 線形リスト(ただしダミー要素なし)にして返す
Pool new_pool(int n) {
    Pool *r = new_pool_sub();
    r->size = n;
    n -= POOL_SIZE;
    Pool *p = r;
    while (n>0) {
       Pool *newp = new_pool_sub();
       p->next = newp;
       n -= POOL_SIZE;
       p = newp;
    }
    r を rootから始まるリストに繋ぐ
    return r;
}

// プールを開放する
void delete_pool(Pool *p) {
    Pool *q = p; // pを保存
    for (;q;q=q->next)
       if (q->usedに使用中の領域がある) return;

    // 解放
    q = p;
    while (q) {
       Pool *newq = q->next;
       free(q);
       q = newq;
    }
    p を rootから始まるリストより削除
}

フラグに関しては、セットとクリアにはビット演算を用いる. x番目の要素を使用(セット)/解放(クリア)する以下の操作は 組込みシステムのプログラムでよく使用される慣用句である.

static uint32_t mask[] = {
 1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80, ... , 0x80000000
};

#define SET(p,x) { p->used[x/32] |=  mask[x%32]; }
#define CLR(p,x) { p->used[x/32] &= ~mask[x%32]; }

あとはプールから必要な数の要素(連続する未使用領域)を 確保してフラグを使用中にする関数と、 プールに要素を返す(フラグを未使用にする)関数を作成すればよい.

// pからn個の領域を割り当てる
// pが0、または領域が不足する場合には新規プールを割り当てる
List *my_alloc(int n, Pool *p) {
    Pool *q=p; // pを保存
    for (;q;q=q->next) {
        List *l = q->vec;

        lを最初の未使用領域まで進める
        if (lから先 n個が連続して未使用) {
            n個を使用中にする(SET使用)
            p->size 調整
            return l;
        }
    }

    // 新しい領域の割り当て
    Pool *newp = new_pool(n);
    l = newp->vec;
    n個を使用中にする

    newp を pの最後に接続
    p->size 調整
    return l;
}

// pからn個の領域を開放する
// pが0の場合はrootから領域を探して解放する
bool my_free(int n, List *l, Pool *p) {
    PoolList *pl = root.next;
    if (p==0)
        for (; pl; pl=pl->next) {
            p = pl->pool;
            for (; p; p=p->next) {
                if (lがp内の領域) break;
            }
        }

    if (pl && lがp内の領域) {
        lから先のn個を未使用にする(CLR使用)
        return true;
    }
    return false; // 該当領域なし
}

確保と解放を繰り返すうちにやはり未使用領域は細切れになるが、 これを集める処理は行っていない. 一般にゴミ集め(ガベージコレクション)は実装が難しく、 また実行に時間がかかるので、特にタイミングに 厳しい組込みシステムではなるべくゴミ集めを行わないで済むように アルゴリズムを工夫する必要がある. またプログラムをモジュールに分けておき、 確保と解放を頻繁に繰り返すモジュールは一定の周期で再起動する、などの方法もある.