C言語

C言語(GCC)の&&のもう一つの使い方

"&&"と言えば論理演算子ですが、gccの拡張文法では以下のようにして、gotoのラベルを配列に入れることができます。 include<stdio.h> int main(int argc, char* argv[]) { static void* LABELS[] = {&&LABEL0, &&LABEL1, &&LABEL2}; goto *LABELS[(int)(argv[1][0] - </stdio.h>…

&&と||は何をやってるか調べてみた

C言語の"&&"と"||"は短絡評価をする演算子と知られています。実際には、どんな感じで評価しているか調べてみました。 // and_or.c #include<stdio.h> int and(int a, int b) { return a && b; } int or(int a, int b) { return a || b; } int main(void) { printf("1&</stdio.h>…

GNU indentを使ってみた

わざとらしく次のようなファイル(hello.c)を用意します。 #include<stdio.h> int main( void ) { printf("hello, world\n"); return 0 ; } $ indent -st hello.c すると #include<stdio.h> int main (void) { printf ("hello, world\n"); return 0; } が標準出力されます(-stが</stdio.h></stdio.h>…

sqlite_masterの中身を読み込む(1)

うまくいくときと、いかないときがあるのですが、sqlite_masterに書かれた内容を標準出力するプログラムを書きました(また直ったら更新すると思います)。現在のところは,リーフページのみ読み込めるのみです。まず読み込むためのsqlite3を使って読み込むファ…

64ビット整数を8ビット配列に格納

(uint64_t)64ビット整数を(uint8_t)8ビット配列に格納する際、8成分必要です。番兵を入れれば9成分でしょうか。同じ最大9成分でも、それぞれの成分の1ビット分を次があるかどうかを示すフラグにする方法も考えられます。メリットとしては、成分が少ないとき…

変数 = (式, 値); assert(値 == 変数);

C言語の文法にこんなのあったかなぁ.. #include <assert.h> #include <string.h> #define getVarint(p, v) (*(p+1) & 0xff)? (*v = *p, 1): get_varint(p, v) unsigned get_varint(unsigned char* p, unsigned int* v) { unsigned int a[4]; int i; assert(*p & 0xff); a[0] = *p</string.h></assert.h>…

Insertion Sort

SQLiteのソースコードリーディングしているのですが、ぼくはソート・アルゴリズムについてあまり勉強したことがないので、アルゴリズムのところでいちいち躓いています。SQLiteで使われているアルゴリズムは本にも載っているような古典アルゴリズムがほとん…

エンディアンについてのメモ

ビッグエンディアンで記録されている数値を読み出す処理が、逆なんじゃないかと思ったら、実はx86はリトルエンディアンで記録しているということでした。本当にそうなっているのかC言語で確認しました。 #include <assert.h> #include <stdint.h> #include <string.h> int main(void) { uin</string.h></stdint.h></assert.h>…

定義のない構造体

SQLiteを読んでるとsqlite3_stmtという構造体が名前だけ出てきます。ところが定義がどこを探してもありません。どうやらsqlite3_stmt*のような構造体はvoid*のように使えるようです。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef struct Str Str; int </assert.h></string.h></stdlib.h></stdio.h>…

ファイル操作の練習とStringIO(1)

ファイルにアクセスして、色々と細かい操作をしないといけないことはあるかと思いますが、ぼくは正直ファイル操作処理がOS任せになってブラックボックスなところもあって馴染めません。さらにファイル操作した後、ファイルの内容が変更してしまっては、くり…

Python2.6のC拡張モジュールを使ってオブジェクトをCで書いてみた(3)

前回までにオブジェクトにメソッドを追加する以外のことはやったので、ここではメソッドを追加してあげましょう。テストはtestStringに書いてありました。コメントアウトされてる部分を元に戻します。 def testString(self): s = String.new('abc') self.ass…

Python2.6のC拡張モジュールを使ってオブジェクトをCで書いてみた(2)

前回はコンストラクタを定義しました。次はgetattrを定義して、フィールドにアクセスするところまで進めます。テストの方は、testStringを復活させます。 def testString(self): s = String.new('abc') self.assertEqual(3, s.length) # self.assertEqual('a…

Python2.6のC拡張モジュールを使ってオブジェクトをCで書いてみた(1)

C拡張モジュールの例として、helloworldをstringオブジェクトとして返すような簡単な例は見ますが、ユーザー定義オブジェクトをC言語で実装するような例は見つかりませんでした。Makefileはhelloworldモジュールを作るときと変わらないので省略します。最低…

正規表現エンジン(RE1)への道(2)

re1を読むために作ったプロジェクトregexp_vm(d58ae...)に(RE1の)pikevmを追加しました。ビルドは次のようにすると、reという実行ファイルができあがります。 git git@github.com:nnabeyang/regexp_vm.git regexp_vm cd regexp_vm make 使い方もvmを指定する…

RE1(正規表現エンジン)への道(1)

Google RE2の前の実験的実装としてRE1があります。VMを使った正規表現エンジンの勉強に最適だと思います。ここではRE1実装ができるまでの実装を細かく追っていくことを目的に再開発します。blogで解説したいと思っているのですが、どうかけば良いか考え中で…

minigcのgc_mark_stack(void):void はいつ動くの?

ガベージコレクションのアルゴリズムと実装を読む準備としてminigc(tree:ff305e...)を読んでいるのですが、どうにもよく分からないところがでてきました。それはgc_mark_stack()を通していつオブジェクトがマークされるのかということです。少なくともぼくの…

mallocとfreeの実装

ガベージコレクションのアルゴリズムと実装の参考資料でもあるminigcのmalloc/free部分の実装を抜き出して、自分でも書いてみました。sbrk(2)は呼び出すたびに、ヒープ領域を伸ばします。my_freeは、ヒープ領域を解放するわけではなく、my_freeしたヒープ領…

windowsでmmap

windows.hをはじめて使ってみました。CreateFileWでファイル名を指定するために、mbtowcという関数を使わないといけないようです。windowsでコンパイルするときは"gcc file.c -DOS_WINDOWS"とします。linuxなどの場合は"gcc file.c"だけでokです。 使い方 コ…

ピアノ問題の一般解(数学ガール: 乱択アルゴリズム)

本の中では(a=8, b=4)の場合だけ検算していますが、それ以外の場合についても確かめるためのプログラムです。"./a.out a b"で実行すると場合の数を返します(a,bは書籍上で定義されているものと同じです)。 ソースコード #include <stdio.h> #include <stdlib.h> #include <string.h> #incl</string.h></stdlib.h></stdio.h>…

甘いもの詰め合わせ(ダイナミック・プログラミング)

プログラマのための論理パズルの解答例です。 "./a.out 1 160"で問題1の解答が、"./a.out 5 160"で問題2の解答が得られます。低性能と言って良いようなPC(netbook)で計算してますが、1問あたり5分以内で計算が終わりました。 ソースコード #include <stdio.h> #includ</stdio.h>…

数独(推論のいる場合)

数独の拘束条件だけでは答えが1つに絞れない場合に対応しているプログラムです。 例 例えば、こんな問題(0は空欄を意味します)は前回のプログラムでは解くことはできませんでしたが、今回のプログラムでは解くことができます。 000 104 870 000 007 400 300 …

数独(推論のいらない場合)

数独を解くプログラムです。少しでも問題が難しいと、解けなくなります。 コード #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> struct State { char c; struct State* right; struct State* down; }; struct State* state(char c) { struct State* s = malloc(s</string.h></assert.h></stdlib.h></stdio.h>…

年齢並べ

プログラマのための論理パズルに掲載されているパズル「年齢並べ」をC言語に解かせてみました。順列の生成のところで、つまってしまって少し凹みました。 コード #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> struct Person { const char* name; int age; struc</assert.h></string.h></stdlib.h></stdio.h>…

共用体で作るポインタリスト

共用体を使ってポインタのコレクションが作れます。ポインタのサイズ(sizeof(struct Struct*)とsizeof(union PtrList*))が同じだからサイズ的にはok。(struct Struct**)の変数を(union PtrList*)にキャストできるのが新鮮でした。フィールド名を通して元の型…

正規表現エンジンの実装(1)

これから数回をかけて正規表現エンジンをC言語で実装します。この回では、メタ記号('(',')', '|','?','+'..)無しの正規表現を作ります。すると結局、文字列の比較をするプログラムを作るということになります。例えば"./a.out hello hello"としたら"match\n"…

GNU Bisonの使い方(C言語)

GNU Bisonは人が読んで理解しやすい文法ファイル(*.y)から、C,C++そしてJavaのparserを生成してくれるツールです。それぞれに多少APIが異なると思いますが、ここではC言語で使う場合に定義しないといけない関数、アクセスできるグローバル変数について説明し…

C言語から機械語を直接実行する方法

v8(JavaScript Engine)を読んでいると、機械語を直接生成してから、それを関数型に流し込んで実行していることが分かってきました。面白いと思ったのでC言語で簡単に再現してみました。 コード #include <stdio.h> #include <sys/mman.h> #include <string.h> #include <assert.h> int sum(int a, int </assert.h></string.h></sys/mman.h></stdio.h>…