C言語で書き溜めたコード片を再利用のためにcplaygroundというリポジトリにまとめているよ、というはなし。
概要
最近、C言語でコードを書く機会が増えており(カーネルランドのものを書くときや、VMを最適化するためには、やはりCがやりやすいなどの理由により)、よくつかうデータ構造やアルゴリズムを再利用のために一つのリポジトリにまとめておくと
そこから切り貼りすればいつでも簡単に使えるのでは、と考え、そういうリポジトリを創ることにした。
以下で公開している。
この記事では、cplaygroundに現時点で含まれているデータ構造とアルゴリズムについて解説する。
また、Cを書く上でのちょっとしたテクニックについてもかけたら良いかもなあと思っている。そのため、C言語の初学者から中級者には参考になる内容が含まれているかもしれない。
それでは、続きからどうぞ。
含まれているデータ構造とアルゴリズム一覧
現時点で含まれているコンポーネントは以下のとおりになる。
- AVL Tree : AVL木
- Binary Search Tree : 2分探索木
- Queue : キュー
- Stack : スタック
- Vector : 動的配列
- Functional pipe : 関数をパイプライン的に処理するためのマクロとランタイム
- S-Expression Parser : S式パーサ
- Binary Heap : 2分ヒープ
- Priority Queue : 優先度付きキュー
- Dijkstra : ダイクストラ法
- minilisp Compiler & Virtual Machine : 小さなLisp処理系(パーサは上にあるS式パーサを用い、コンパイラとVMからなる) これについては独立して記事を書く
- ArrayList : JavaのArrayListみたいなやつ
- RingBuffer : リングバッファ
これらをMITライセンスのもとで、提供している。
また、他にもutil.cの中でちょっと便利な関数も提供している。(例えば検査付きmallocなど)
テストについて
ほとんどすべてのコンポーネントについて(テストがめんどくさそうじゃないやつ。ホントは全部書いたほうが良いんだけど)、テストが書かれてる。(RingBufferについてはテストを書いてない(さっきこの記事のために急遽公開したため))
make build_testでテストをビルドし、make run_testでテストが走る。
cplaygroundのtester(テストをちょっとだけ管理しやすくするためのものを適当にそう読んでいる)については、後ほど書こうと思う。
特徴
基本的に、コンテナは特定の型に依存しないような作りになっている。C++やDなどのtemplteのある言語では、コンテナが保持する値の型をTと具体的に指定できるが、Cにテンプレートはない。そのため、コンテナはすべて、void *を内部で取るようにしている。
これにより、スカラ型(intやdouble, charなど)は基本的に全部64bit格納可能なvoid *に入るし、ポインタもすべてvoid *に入るので、何を入れておいたかを覚えておけばこれで問題ない。(型安全性はなくなるが、こうするしか無い)
また、もしもCでテンプレートみたいなものが欲しくなった場合(何らかの理由によってvoid *を使いたくなくて特定の型を指定して、その型について特化した関数を生成したい場合など)は、次のようにすることで、一応目的は達成できる。
#define GenGenericAdd(T) \ T add_##T(T a, T b) {\ return a + b; \ } // add for int GenGenericAdd(int) // add for double GenGenericAdd(double)
のようにすると、add_intとadd_doubleが生成される。
また、このライブラリでは、文字列は基本的にsdsというライブラリを用いている。
各コンポーネントについて簡単な説明
AVLTree と Binary Search Tree
AVLTree: avl.c
Binary Search Tree: binarytree.c
AVLTreeは平衡2分探索木、Binary Search Tree(BST)は単純な2分探索木である。AVLTreeがあるのでBSTをつかう必要はない。
また、内部構造と、公開している関数は以下で示すとおり(headerから抜粋)
typedef struct AVLNode_t { void *key; void *value; int height; int size; struct AVLNode_t *left; struct AVLNode_t *right; } AVLNode; AVLNode *new_AVLNode(void *key, void *value); typedef struct { AVLNode *root; ELEM_COMPARE compare; } AVLTree; AVLTree *new_AVLTree(ELEM_COMPARE compare); typedef void (*ELEM_FREE)(void *); void free_AVLNode(AVLNode **n_ptr, ELEM_FREE free_key, ELEM_FREE free_val); void free_AVLTree(AVLTree **t_ptr, ELEM_FREE free_key, ELEM_FREE free_val); typedef int (*ELEM_COMPARE)(void *, void *); bool avl_exists(AVLTree *tree, void *key); void *avl_find(AVLTree *tree, void *key); void avl_insert(AVLTree *tree, void *key, void *value); void avl_delete(AVLTree *tree, void *key); void avl_print_node(AVLNode *node, size_t depth, ELEM_PRINTER key_printer, ELEM_PRINTER value_printer); void avl_print_tree(AVLTree *tree, ELEM_PRINTER key_printer, ELEM_PRINTER value_printer); Vector *avl_values(AVLTree *tree); Vector *avl_keys(AVLTree *tree);
比較関数をAVLTreeのインスタンスを作る時に関数ポインタとして渡すことで、任意の型の値を格納することができる。
また、keyとvalueの組から各Nodeは構成される。(AVL木上の探索はkeyの値によって行われる)
Queue と Stack
これは普通のQueueとStackなので、特に説明することはない。
Vector
Cで動的配列を実現するためのライブラリ。実装としては、値をvoid **で保持している。
以下にAPIと内部構造を以下に示す。
typedef struct { void **data; size_t capacity; size_t len; } Vector; #define VECTOR_DEFAULT_CAPACITY 16 #define VecForeachWithType(vec, T, loop_val, loop_body) \ for (size_t fe_loop_counter_ ## vec = 0; fe_loop_counter_ ## vec < vec->len; fe_loop_counter_ ## vec ++) { \ T loop_val = vec->data[fe_loop_counter_ ## vec]; \ loop_body; \ } #define VecForeach(vec, loop_val, loop_body) VecForeachWithType(vec, void*, loop_val, loop_body) Vector *new_vec_with(size_t capacity); Vector *new_vec(void); void vec_push(Vector *v, void *elem); void vec_pushi(Vector *v, int val); void vec_pushlli(Vector *v, long long int val); void *vec_get(Vector *v, size_t idx); void *vec_pop(Vector *v); void *vec_last(Vector *v); bool vec_contains(Vector *v, void *elem); bool vec_containss(Vector *v, sds elem); bool vec_union1(Vector *v, void *elem); Vector *vec_dup(Vector *v); void vec_append(Vector *v1, Vector *v2);
Functional pipe
Functional pipe: functional.c
関数をパイプライン的に処理するためのマクロとランタイム。
#define PIPE(val, ...) pipegen(val, PIPE_ARG_MAKE(__VA_ARGS__)) #define PIPE_ARG_MAKE(...) PIPE_ARG_MAKE2(((void *[]){__VA_ARGS__})) #define PIPE_ARG_MAKE2(ARRAY) ARRAY, sizeof(ARRAY) / sizeof((ARRAY)[0]) typedef void *(*ANY_FUNCTION)(void *); void *pipegen(void *val, void **funcs, size_t len); void *pipegen(void *val, void **funcs, size_t len) { for (size_t i = 0; i < len; i++) { val = ((ANY_FUNCTION)funcs[i])(val); } return val; }
これを用いると次のようなコードがかける。
void *square(void *vi) { long v = (intptr_t)vi; return (void *)(intptr_t)(v * v); } #define INT_TO_VoPTR(i) ((void *)(intptr_t)i) #define VoPTR_TO_INT(ptr) ((int)(intptr_t)ptr) TEST_CASE(basic_test, { void *ret = PIPE(INT_TO_VoPTR(4), square, square); assert(VoPTR_TO_INT(ret) == 256); })
これは、squareに4を適用し、その結果をsquareに適用することになる。
S-Expression Parser
S-Expression Parser: sexp.c
再帰降下式のS式パーサ。
はじめに、内部表現とAPIを示し、以下にパーサの実装について簡単に説明を行う。
enum { float_ty, bool_ty, string_ty, symbol_ty, list_ty, object_ty, quote_ty, }; typedef struct SexpObject { int ty; union { double float_val; bool bool_val; sds string_val; sds symbol_val; Vector *list_val; struct SexpObject *object_val; struct SexpObject *quote_val; }; } SexpObject; #define GenSexpObjectConstructorProtWithName(T, Name) \ SexpObject *new_SexpObject_##Name(T val); SexpObject *new_SexpObject(void); SexpObject *dup_SexpObject(SexpObject *obj); void free_SexpObject(SexpObject **obj_ptr); GenSexpObjectConstructorProtWithName(double, float); GenSexpObjectConstructorProtWithName(bool, bool); GenSexpObjectConstructorProtWithName(sds, string); GenSexpObjectConstructorProtWithName(sds, symbol); GenSexpObjectConstructorProtWithName(Vector *, list); GenSexpObjectConstructorProtWithName(SexpObject *, object); GenSexpObjectConstructorProtWithName(SexpObject *, quote); #define GenGetterOfSexpObjectProtWithName(T, Name) \ T get_##Name##_val(SexpObject *obj); GenGetterOfSexpObjectProtWithName(double, float); GenGetterOfSexpObjectProtWithName(bool, bool); GenGetterOfSexpObjectProtWithName(sds, string); GenGetterOfSexpObjectProtWithName(sds, symbol); GenGetterOfSexpObjectProtWithName(Vector *, list); GenGetterOfSexpObjectProtWithName(SexpObject *, object); GenGetterOfSexpObjectProtWithName(SexpObject *, quote); bool equal_SexpObjects(SexpObject *lhs, SexpObject *rhs); typedef struct { SexpObject *parse_result; size_t read_len; } ParseResult; ParseResult sexp_parseExpr(sds code); Vector *sexp_parse(sds code); sds show_sexp_object(SexpObject *obj); sds show_sexp_object_impl(SexpObject *obj, bool display_string_dq);
このようなAPIになっている。
パーサーの一番肝となっている関数は以下の関数である。
ParseResult sexp_parseExpr(sds code) {
size_t code_len = strlen(code);
ParseResult result = new_ParseResult();
size_t i = 0;
for (; i < code_len;) {
char c = code[i];
// 空白やデリミタをスキップする
if (c == ' ' || c == '\n' || c == '\r' || c == '\t') {
i++;
continue;
}
// コメントをスキップ
if (c == ';') {
i += skip_line(&code[i]).read_len;
continue;
}
// 数字をパース
if (isdigit(c)) {
result = parse_number(&code[i]);
result.read_len += i;
return result;
}
// もし、'-'がきて、その後に文字列が存在し、かつ、それが数値である場合負の数としてパースを行う。
if (c == '-' && i + 1 < code_len && isdigit(code[i + 1])) {
result = parse_number(&code[i]);
result.read_len += i;
return result;
}
// シンボルをパース
if (isalpha(c) || strchr(symbol_chars, c)) {
result = parse_symbol(&code[i]);
result.read_len += i;
return result;
}
// 文字列リテラルをパース
if (c == '\"') {
result = parse_string(&code[i]);
result.read_len += i;
return result;
}
// リストをパース
if (c == '(') {
result = parse_list(&code[i]);
result.read_len += i;
return result;
}
// クオートをパース
if (c == '\'') {
result = parse_quote(&code[i]);
result.read_len += i;
return result;
}
}
result.read_len = i;
return result;
}
1文字ずつ文字列を見ていき、あるトークンの開始を検知したら適切なハンドラを再帰的に読んでいくことでパースが進む。
なお、これを呼ぶだけだと一つのS式、つまり(hoge fuga bar)しかパースすることが出来ない。
そのため、複数のS式をパースするために、以下の関数で与えられた文字列全体をパースする。
Vector *sexp_parse(sds code) {
Vector *ret = new_vec();
for (size_t i = 0; i < strlen(code);) {
ParseResult result = sexp_parseExpr(&code[i]);
if (result.parse_result != NULL) {
vec_push(ret, result.parse_result);
}
i += result.read_len;
}
return ret;
}
Binary Heap
Binary Heap: binaryheap.c
これも普通に2分ヒープ。
APIは以下に示すようになっており、最初に与えた比較関数によって最大ヒープか最小ヒープかを切り替えることができる。
typedef struct { Vector *vec; ELEM_COMPARE compare; } BinaryHeap; BinaryHeap *new_BinaryHeap(ELEM_COMPARE compare); void heap_insert(BinaryHeap *heap, void *val); void *heap_pop(BinaryHeap *heap); void print_heap(BinaryHeap *heap, ELEM_PRINTER show); bool heap_empty(BinaryHeap *heap);
Priority Queue
Priority Queue: priorityqueue.c
Dijkstraを実装するために実装した。中身は2分ヒープ。
Dijkstra
最短路探索をなんとなくやりたいときがあるので、Dijkstraを実装した。
minilisp Compiler & Virtual Machine
minilisp: minilisp.c
小さなLisp処理系(パーサは上にあるS式パーサを用い、コンパイラとVMからなる) これについては独立して記事を書く予定である。
これを作った動機としては、主に2つあり、1つはS式パーサを実装したら当然Lisp処理系を書きたくなるからという自然なものであり、2つめはVMをこれまでいくつか作ってきたがそれらの設計には不満があったので、新しい設計のVMの模索を目的としていた。
これについては後日詳細な記事を書く予定である。(実装についてと、行った最適化などについて)
なお、この処理系(コンパイラとVM)は当初1000行程度であったが最適化を進めるに連れてコードが増えていった。
ArrayList
事情により(Memory Poolを作りたかった)ArrayListが必要になって実装した。
特徴としてはLinux kernelで使われてる型に関係なくつかえるLinked listのテクニックを用いていることである。(offset_ofとかcontainer_ofをつかうやつ)
RingBuffer
RingBuffer: ringbuffer.c
これもArrayList同様の事情(詳しいことは書かないけど軽くネタバレすると、上述したVMをカーネルランドにもってく際に必要だったという事情)により必要となって作ったRingBuffer。
まとめ
minilispのVMを実装した話の記事を書こうと思ったけど、先にcplaygroundについての記事を書こうということで急遽書くことにした記事なため、書いている途中で力尽きてきて説明が少々雑になってしまった。(Cのテクニックもあんまりかけなかった。。。)
取り敢えず、今後更新するか別の記事でCのテクニックはぼちぼち書いていけたらなあと思う。(と言ってもテクニック自体はcplaygroundのソースコードにコードとして書かれていて、それを日本語で説明するという感じなので、すべてを知りた人はコードを読むといいです。)
次回の記事では、minilispの実装と最適化について記述する予定であり、その次の記事ではそれをLinuxのカーネランドに移植し、miscデバイスとして動作させたことについて書く予定である。
積極的なアウトプットを行っていきたいと考えているため、近日中に記事をあげるつもりである。
それでは、このへんで。
