概要

本記事では，C言語においてVector<T>のような型ジェネリクスもどきを用いることのできるライブラリを作成したので紹介する．

作成したライブラリの特徴

1. void *型を引数に取らない

マクロの引数に渡した型を用いて展開されるため，charのvecにintをpushするというミスを防ぐことが可能

1. 安全なメモリアクセス

領域外を参照しようとするとout of range Errorが発生

3. filterやforeach，reduceといった高階関数が提供される

面倒なforやwhileを書く手間を削減

4. それ以外の便利な関数

配列int[]からの変換や，vec_len，比較関数を渡すことのできるソート(現状連結リストのみ)などで定型的なコードを書く必要を削減

vecの使い方

ここでは今回作成したvecに関する基本的な関数について示す．

1. 型と関数の定義

vec_def(Type)

まず，使用したい型ごとにvec_def(Type)マクロを呼び出し，vec_type型とそれに関する関数を定義する． 各種関数の利用前に呼び出す必要がある．

vec_def(int); /* int型の動的配列`vec_int`を定義し，関連する関数を定義 */
vec_def(MyStruct); /* 構造体でも同様の操作が可能 `vec_MyStruct`が定義される */

2. vecの生成と破棄

vec_Type *vec_Type_new(size_t len)
vec_Type *vec_Type_from(Type *data, size_t len)
void vec_free(void *vec)

次に，vec_Type_new()やvec_Type_from()を使ってvecの構造体を生成する．

vec_int *vec = vec_int_from((int[]){1, 2, 3}, 3);

lenを指定する必要があるが，大きさが不足すると自動で拡張するので深く考える必要はない． しかし，実際の要素数よりあまりに小さいと，内部でrealloc()を呼ぶ回数が増えるためパフォーマンスが悪化するため，適度に大きな値を設定することを勧める．

また，vec_free()は，唯一のvoid *を引数に持つ関数である．これはfreeするのにわざわざ型を指定するメリットが薄いためである．

3. 要素へのアクセスと変更

Type vec_Type_get(const vec_Type *vec, size_t idx)
Type *vec_int_get_mut(vec_Type *vec, size_t idx)

vecの要素には，vec_Type_get()とvec_Type_get_mut()を用いて安全にアクセスできる．

/* 安全な vec[i] */
printf("vec[0]: %d\n", vec_int_get(vec, 0));
printf("vec[1]: %d\n", vec_int_get(vec, 1));
printf("vec[2]: %d\n", vec_int_get(vec, 2));

/* 実行時に out of range Error */
// printf("vec: %d\n", vec_int_get(vec, 3));

/* 変更できるポインタの取得 */
*vec_int_get_mut(vec, 1) = 10;

これらの関数は実行時に，範囲外のアクセスでないかを判定する．

また，vec_Type_get()は実体を返すため，変更が不要な場合に便利である．

4. 高階関数

Type vec_Type_reduce(vec_Type *vec, Type (*func)(const Type *, const Type *), Type first)

高階関数の一例としてreduceを紹介する．

int sum_int(const int *a, const int *b) { return *a + *b; }
/* 省略 */
printf("sum: %d\n", vec_int_reduce(vec, sum_int, 0)); /* 14 */

C言語には無名関数が存在しないため，利用するのは若干面倒である．

使用例

それ以外の関数を含むサンプルコードを次に示す．

インクルードのパス等は適宜環境に合わせてください．

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "datastructure/base/hinc_vec.h"

void print_int(int *n) {
    printf("%d ", *n);
    return;
}

void duble_int(int *n) {
    *n = *n * 2;
    return;
}

int sum_int(const int *a, const int *b) { return *a + *b; }

bool is_up15(const int *n) { return *n > 15; }

/* 新しいvecの定義 */
vec_def(int);

int main(void) {
    /* 新しいvecの宣言と初期化 */
    vec_int *vec = vec_int_from((int[]){1, 2, 3}, 3);
    printf("data_size: %zu\n", vec->data_size);     /* 4 */
    printf("len: %zu\n", vec->len);                 /* 3 */
    printf("size: %zu\n", vec->size);               /* 128 */
    printf("\n");

    /* 安全な vec[i] */
    printf("vec[0]: %d\n", vec_int_get(vec, 0));    /* 1 */
    printf("vec[1]: %d\n", vec_int_get(vec, 1));    /* 2 */
    printf("vec[2]: %d\n", vec_int_get(vec, 2));    /* 3 */
    printf("\n");

    /* 実行時に out of range Error */
    // printf("vec: %d\n", vec_int_get(vec, 3));

    /* 変更できるポインタの取得 */
    *vec_int_get_mut(vec, 1) = 10;

    /* pushとpop */
    printf("pop: %d\n", vec_int_pop(vec));          /* 3 */
    vec_int_push(vec, 100);
    printf("\n");

    /* foreachの利用 */
    vec_int_foreach(vec, duble_int);
    vec_int_foreach(vec, print_int);                /* 2 20 200 */
    printf("\n");

    /* 条件を満たす要素だけの新しいvecを作成 */
    vec_int *new_vec = vec_int_filter(vec, is_up15);    /* 20 200 */
    vec_int_foreach(new_vec, print_int);
    printf("\n");

    /* 累積的な計算 */
    printf("sum: %d\n", vec_int_reduce(new_vec, sum_int, 0));   /* 220 */
    printf("\n");

    vec_free(vec);
    vec_free(new_vec);
}

ぜひコンパイルして実行してみましょう．

双方向連結リストもあります

実は双方向連結リストlistがライブラリに実装されている． 双方向連結リストにはvecに追加してソートやイテレータといった追加の機能が先行して実装されている．

vecと同様にlist_def(Type)によって定義を行うことができる．

内部ではパフォーマンスの向上を目的とした，空きノードリストとブロック割り当てを行っているなど，vec以上に実験的なコンテナである．

イテレータ

より発展的な機能としてイテレータが実装されている． イテレータも同様にiter_def(Type)によって定義が行われるが，これによって定義されるのはiter_Typeとnext()等の操作であり，イテレータの作成関数は提供されない．

イテレータを作成するにはiter_def_for_list(Type)を呼び出し，イテレータをリストから作成する関数iter_Type_list_begin()等を定義する必要がある． これはイテレータをvecやlistといった特定のコンテナ型に依存しないようにするためである．

今後はvecにもiter_def_for_vec(Type)を実装する予定である．

これによって次のようなfor文の記述が可能になる．

for (iter_int iter = iter_int_list_begin(list); iter.has_next;
         iter_next(iter)) {
        printf("iter: %d\n", *iter.ref);
    }

内部の実装

ここからは内部の実装について簡単に説明する． まずvec_def等のマクロの内部ではトークン結合演算子である##が用いられており， これによって，同じ処理を異なる型に対して展開している．

#define vec_def(Type)                                                  \
    typedef struct {                                                   \
        Type *data;                                                    \
        size_t data_size;                                              \
        size_t len;                                                    \
        size_t size;                                                   \
    } vec_##Type;                                                      \
                                                                       \
    vec_##Type *vec_##Type##_new(size_t len) {                         \
        return (vec_##Type *)_vec_new(sizeof(Type), len);              \
    }                                                                  \
    /* 省略 */

これはvec_def(int)を記述することで，

typedef struct {                                                   
        int *data;                                                    
        size_t data_size;                                              
        size_t len;                                                    
        size_t size;                                                   
    } vec_int;                                                      
                                                                       
    vec_int *vec_int_new(size_t len) {                         
        return (vec_int *)_vec_new(sizeof(int), len);              
    }                                                                  
    /* 省略 */

のように展開される．

その内部では，アンダーバー_から始まる構造体と関数によって共通の処理を行っている．

typedef struct {
    void *data;
    size_t data_size;
    size_t len;   /// 要素数
    size_t size;  /// 割り当て済み要素数
} _Vec;

_Vec *_vec_new(size_t data_size, size_t len);

_Vecはvec_Typeとメモリレイアウトが一致するため，受け取ったポインタを展開された関数内部でキャストすることで，型付けされた関数を実現している．

また，listの_Nodeでは_Node自身とdataの領域をまとめて確保するため，フレキシブル配列メンバが用いている．

struct _Node {
    _Node *next;
    _Node *prev;
    char data[];
};

おわりに

GitHubで公開しています．

MITライセンスなのでご自由にご利用ください．

https://github.com/hinshiba/hinclib

蛇足

このプロジェクトは学部2年のプログラミング演習において，謎の構造体や連結リストを作成するのに飽きたため作成した．

実際の提出においてもこのライブラリを使用しており，提出の要件で1ファイルにまとめる必要があったためMITライセンスの文言から始まるソースコードを提出する羽目になった．

また，その他無駄機能として独自言語の実行環境が実装されており，含めるとソースコードが2900行あり，レポートの22ページ目から97ページ目までソースコードが貼られることとなった．

次回記事はその独自言語について書くのでお楽しみに．