KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

template in C

この記事はKMC Advent Calendar 2015 - Adventar 9日目の記事です。 8日目の記事は、sio_puyoさんの超!エキサイティン!(副題:12月8日は何の日?) - KMC活動ブログでした。

はじめに

KMC 4回生のhatsusatoです。

今日はC言語の話です。

最近Cをたくさん書いている*1のですが、Cを書いているとC++が恋しくなってきます。どうしてでしょうか。

その理由の一つに、C言語にはSTLがないことが挙げられると思います*2

C言語には標準的なコンテナがないので、必要になるたびに自分で用意する必要があります。しかも、要素の型が異なるたびにコンテナの型が変わるので、いちいち作らないといけないです。

面倒くさいです。

C言語にはテンプレートがないので、(型安全な)ジェネリックプログラミングができないから面倒くさいのです。

そこで今日は、なんとかいい感じのジェネリックなコンテナをC言語の範囲でできないか、ということを考えます。

void*を用いたCでのジェネリック

C言語には汎用ポインタとも呼ばれるvoid*があります。汎用ですよ、ジェネリックですよ。なんだかできそうです。

実際void*を使ってジェネリックプログラミング*3ができます。て言うかしてます。

<stdlib.h>に次のシグネチャをもつqsortという関数があります。

void qsort(void *ptr, size_t count, size_t size,
           int (*comp)(const void *, const void *));

このqsortは配列上の要素をソート*4してくれる関数です。詳しくはqsortリファレンス*5をご覧ください。

このとき、要素の型に特に制限はありません。型ごとの違いを第3引数のsizeと第4引数のcompにこめてやることで、任意の型に対する操作を一つの関数で表現しています。

まさにジェネリックです。やればできるんですね。

ただこの手法では、データに対してvoid*を介してアクセスするしか方法がないので、元のデータが持っていた型情報が失われてしまいます。qsortの場合は、並び替えるだけでいいのでなんとか間に合っていますが、コンテナでこれをやると、ユーザがそのコンテナに入っているオブジェクトの型を把握して、誤ったアクセスをしないように注意する必要があります。

もうちょっとなんとかしたいですね。

マクロを用いたCでのジェネリック

ここからが本題です。マクロを用いてジェネリックなコンテナを実装します。

まずはユーティリティとしてトークン連結マクロを準備します。

#define CONCATENATE(x, y) x ## y
#define CONCAT(x, y) CONCATENATE(x, y)

CONCATの引数に渡したマクロが展開された後にトークン連結されてほしいので、CONCATENATEマクロを一段階挟んでいます*6

そしてデータ構造を定義します。

#define VECTOR_TYPE(T) \
  CONCAT(Vector, T)
#define VECTOR_REF(T) \
  CONCAT(VectorRef, T)

#define DEFINE_VECTOR(T) \
  struct VECTOR_TYPE(T) { \
    T* data; \
    size_t capacity; \
    size_t size; \
  }; \
  typedef struct VECTOR_TYPE(T)* VECTOR_REF(T);

T型の要素を保持するコンテナを定義しました。マクロ引数のTの部分に要素の型を入れてDEFINE_VECTORマクロを展開すると、対応するstruct VECTOR_TYPE(T)の定義とその参照型VECTOR_REF(T)の宣言が展開されます。

CONCATマクロのおかげで、マクロ引数に渡した型の識別子ごとに異なる識別子の構造体が定義されるので、各コンテナの型が区別できて型安全性が少し向上します。

しかし、マクロは低級でトークンレベルの連結しかしてくれないので、例えばポインタ型(int*)や構造体型(struct S)など、複数のトークンからなる型のコンテナを定義したいときは、typedefで単一のトークンからなる識別子に置き換えてから利用する必要があります。

typedef int* int_ptr;
typedef struct S struct_S;

/* DEFINE_VECTOR(int*)  /* よくない */
DEFINE_VECTOR(int_ptr)  /* よい */
/* DEFINE_VECTOR(struct S)  /* よくない */
DEFINE_VECTOR(sturct_S)  /* よい */

データ構造が定義できたら、それにアクセスするメンバ関数もほしいですね。せっかくなのでオブジェクト指向っぽく書いてみます。

まずは基本的なメンバ関数から。

#define VECTOR_METHOD(T, f) \
  CONCAT(VECTOR_TYPE(T), f)

#define DEFINE_VECTOR_CONSTRUCTOR(T) \
  void VECTOR_METHOD(T, constructor)(VECTOR_REF(T) self, size_t size) { \
    self->data = size == 0 ? NULL : malloc(sizeof(T) * size); \
    self->capacity = size; \
    self->size = 0; \
  }
#define DEFINE_VECTOR_DESTRUCTOR(T) \
  void VECTOR_METHOD(T, destructor)(VECTOR_REF(T) self) { \
    free(self->data); \
    self->data = NULL; \
    self->capacity = self->size = 0; \
  }

これで構築して破棄できるようになりました。

メンバ関数Tに依存するので、関数名にも型の識別子を埋め込む必要があります。VECTOR_METHOD(T)マクロを用意しておくことで、T型に依存した関数名を書きやすくなりました。マクロの性質上、かっこが2つ続いて不格好になってしまいますが、しかたありません。

続いて要素を出し入れします。

#define DEFINE_VECTOR_PUSH_BACK(T) \
  void VECTOR_METHOD(T, push_back)(VECTOR_REF(T) self, T value) { \
    if (self->capacity == self->size) { \
      self->capacity = self->capacity == 0 ? 1 : self->capacity * 2; \
      self->data = realloc(self->data, sizeof(T) * self->capacity); \
    } \
    self->data[self->size] = value; \
    ++self->size; \
  }
#define DEFINE_VECTOR_POP_BACK(T) \
  void VECTOR_METHOD(T, pop_back)(VECTOR_REF(T) self) { \
    --self->size; \
  }

これで最低限使えるようになったのではないでしょうか。最後に少し使ってみます。

#define DEFINE_VECTOR_METHODS(T) \
  DEFINE_VECTOR_CONSTRUCTOR(T) \
  DEFINE_VECTOR_DESTRUCTOR(T) \
  DEFINE_VECTOR_PUSH_BACK(T) \
  DEFINE_VECTOR_POP_BACK(T)

DEFINE_VECTOR(int)
DEFINE_VECTOR(double)
DEFINE_VECTOR_METHODS(int)
DEFINE_VECTOR_METHODS(double)

int main(void) {
  struct VECTOR_TYPE(int) v_int;
  struct VECTOR_TYPE(double) v_double;
  const VECTOR_REF(int) vr_int = &v_int;
  const VECTOR_REF(double) vr_double = &v_double;
  VECTOR_METHOD(int, constructor)(vr_int, 10);
  VECTOR_METHOD(double, constructor)(vr_double, 10);
  int i = 0;
  for (; i < 100; ++i) {
    VECTOR_METHOD(int, push_back)(vr_int, i);
    VECTOR_METHOD(double, push_back)(vr_double, (double)i);
  }
  VECTOR_METHOD(double, destructor)(vr_double);
  VECTOR_METHOD(int, destructor)(vr_int);
}

intdoubleのコンテナを型レベルで区別して扱えるようになりました。適宜足りないメンバ関数を実装すれば、遜色なく使えると思います。

実は、これはC++のテンプレートの実装と似たようなことをしています。つまり、

  • C++では、データ構造や関数の「テンプレート」を作って、必要になるところで具体的な型を指定してインスタンス化しているところを、
  • C言語では、データ構造や関数の定義の「マクロ」を作って、必要になるところで具体的な型を指定してマクロ展開しています。

C++C言語との違いは、その過程をコンパイラが内部で行ってくれるか、自分で実装しないといけないかということです。

C言語には様々な制約があるとはいえ、これだけ模倣できれば十分ではないでしょうか。

まとめ

これで我々は、ジェネリックなコンテナをC言語でいい感じに扱えるようになりました。

C言語はなんだかんだ言って面倒くさいし、リソースは簡単に漏れるし、扱いづらい言語ですが、丁寧にしっかりライブラリを整備しておけば、規模が大きくなってもそれなりに書けると思います。

皆さんもジェネリックコンテナを活用して、楽しいC言語ライフをお過ごしください。

次回予告

明日のKMC Advent Calendar 2015 - Adventar 10日目の記事は、wass君による「slackのshellチャンネルを安全にしたい」を予定しています。

お楽しみに。

宣伝

実は、KMCは来るコミックマーケット89(通称C89)に向けてC89コンパイラ*7を作成しています*8。それも、C言語で実装して最終的にはセルフホスティングしたいと考えています。

コンパイラはまだまだ鋭意作成中ですが、コミケ当日にはある程度の形にしたいと考えております。

ぜひこのC89というまたとない機会を逃さず、コミケ3日目、31日(木) 東モ-42bのKMCブースへお越しください。お待ちしています。

*1:最後まで読むと理由がわかります。

*2:一番大きい理由はコンストラクタやデストラクタがないことだと思います。自分でリソース管理するのつらすぎ。RAIIしたい。

*3:一般に言われるジェネリックはもっと型安全なものを指すと思いますが、型に依存しないアルゴリズムを記述できるので、ジェネリックと呼んでいいと思います。

*4:名前に反して実は規格上クイックソートしてくれるとは限らない。

*5:cppreferenceは僕の行きつけのサイトです。おすすめ。

*6:マクロの細かい仕様についてはこの記事では深追いしません。適宜ググってください。

*7:どうして今、C89コンパイラなのか、お分かりかと思います。

*8:実は今回紹介した技術はこのコンパイラで使うために考えました。