void*で柔軟な動的配列をつくってみよう．(´・ω・｀) のCで遊ぼう(1)．

背景

• C言語にもvectorみたいな便利なのが欲しい．
• mallocで確保した要素数を知る公式手法がない
  • つまり自分で保存しとかないといけない
  • まあmallocがvoid*返す時点で．．．
• vectorのemplace_backがほしい(push_backと同じだが速いらしい)
• vectorのpush_backみたいなものが欲しい(emplace_backとかいうものもある．)
• intやdoubleだけでなく，自分で定義した構造体の配列も自在に作りたい．

structure of array vs array of structure問題はあるものの，大は小を兼ねる!!!

(´・ω・) < ちっこい配列char a[3];とか，だと領域を無駄に食うが．．．

(´・ω・｀) < まっ，いいよね！

そこらに転がっているライブラリだと，マクロ使ってたりする．

(´・ω・｀) < マクロ怖い！

C言語でとあるアプリケーションを作ろうと思ってるんだよ．
でね，勉強も兼ねてできるだけ標準ライブラリだけで（ネットワーク系のライブラリを除く）連想配列とか一から作ろうと思ったんだけど，まあ大変だった．（現在進行中だが．．．）

連想配列を作るのにこういった柔軟な動的配列がほんと役に立ったの．

(´・ω・) < わんだふぉ〜にコードが短くなった．

注意点

• 今回のvoid*の使い方は褒められたものではありません．
• 他にもマクロを使った実装方法があります
• Cマクロによる似非template
• Simulation of templates in C (for a queue data type)
• 使えるのであればC++のvectorを使ってください．よほど安全なので．

特徴

• どんな型でもあつかえる．
• C++のvectorの劣化バージョン，emplace_backpush_backのようなことができる．
• C言語でかかれている
• マクロは使わない

アイディア

• 万能選手void*がいるじゃないか．
• sizeof( char ) = 1とsizeof( struct A ) == ?

解説

どんなポインタでも入るvoid*を使えば，どんな配列でも保持できる．
後は，要素を自由に取り出せたらいい．

でもvoid*代入した後にどうやって元の型にもどす？

int a[3] = {1,2,3};

void* ptr = (void*)a;

この時，a[1]にアクセスしたい．

当然ながら

ptr[1]

なんぞ正しく動くわけがない．

(´・ω・) < なんでっかわっかるっかな〜

解説

(´・ω・) < 次の事を知っているという前提で話を進めているよ．

i_ptr[1] == *(i_ptr+1);
&i_ptr[1] == i_ptr+1;

ポインタの変数にはアドレスが入る．
アドレスはPCだと64bitとか32bitとかが多いのかな？

でもね，型によって次どこにジャンプするかが変わる．

簡単のため，charが8bitでintが64bitとしよう．
だから，sizeof( char ) == 1でsizeof( int ) == 8だ．

int一つでchar八個分の容量を食う．

ここで

char* c_ptr;
int* i_ptr;

にそれぞれ+1したときのアドレスの値を考えよう．

まずアドレスはどんな単位で振られているのだろうか．
C言語の場合，一番小さな単位がcharだから，charの幅．つまり8bit単位でアドレスを振られていると考えるのが自然だ．
(C言語の定義でsizeof( char )は必ず1になる．って決まってるんだけどのはこんなところから来てるのかもしれないね．)

じゃあ，c_ptr == 1000としたときc_ptr + 1 == 1001ってなるはずだ．

次に，i_ptr == 1000としたときを考えよう．

intはchar８個分の容量をとっているから，
i_ptr + 1 == 1008ってなるはずだ．

つまり，こういうことだ

i_ptr+1 == (int*)( (char*)i_ptr + 8 )

じゃあvoid*はどうか．
何でもはいるから，&ptr[1] == ptr+1がptrからどれだけ離れたアドレスを返すのか，入れた型によって違ってくる．

C言語はそれを自動解決してくれるほどぬるい言語ではない．

(´・ω・) < '甘えんなっ！' by C言語

(´・ω・｀) < って言われた気がする．．．

でも，逆を言えばどれだけ動かせばよいかはsizeof演算子で分かる．
つまり，sizeof( char ) == 1だから，sizeofを使えばcharの何倍分のメモリを食うかがわかる．

(´・ω・｀) < char何個分かということが！

sizeofはsize_tだから少数はないし．．．

これを応用すると．．．

さて．．．次に，void*で正しい+1の値を計算しよう．

char*が一番細かくアドレスを取得できる上，mallocの引数は通常sizeof( )で決める．
だから，すべてをchar*で考え，後でキャストすれば話がすごく簡単になる．

つまり，一つの要素数の大きさ(char何個分か)が分かれば，正しいアドレスを計算できる．

ちょっと例を見てみよう．

struct A{
	...
};

struct A a[3] = {0};
void* ptr = (void*)a;

ptrからa[1]にアクセスしたい時は．

*(struct A*)( (char*)ptr + sizeof( struct A ) );

とすればよい．
アドレスだけ見るとこんな感じ．

&a[1] == a+1 == (struct A*)( (char*)ptr + sizeof( struct A ) );

a[i]の場合だと，sizeof()をi倍にしてやればいい．

*(struct A*)( (char*)ptr + sizeof( struct A )*i );
&a[1] == a+1 == (struct A*)( (char*)ptr + sizeof( struct A )*i );

(´・ω・) < 言いたいことが分かるかな．

アドレスをすべてchar何個分かで計算するようにする．
そうすれば，sizeof演算子の値がそのまま使える．（だって，sizeof( char )==1だからすべてのsizzeofの値はcharの個数と同義）

char*に直して，sizeofで得た型の大きさ分をchar*で動かして，元のポインタの型に戻す．

作ったライブラリ抜粋

他にもいろいろ用意したけど一番重要名とこだけ抜粋．

何はともあれ，見れば分かるということもあろう．

まずは構造体だ．

struct Array{
	size_t type;     /* sizeof() */
	size_t reserved; /* reserved memory size */
	size_t size;     /* number of elements */
	void*  ptr;      /* pointer to first elements */
};

vectorみたいに確保したメモリと使うメモリはことなる．

(´・ω・) < emplace_back(push_back)したいからね．

ここで重要なのがsize_t typeだ．

ここにsizeof( struct A )の値を入れるのだ．

イニシャライザはまあ予想どおりだよね．
この段階では，容量の確保は一切しない．
push_backメインに使いたいから．（ArrayReserve，ArrayResize関数も用意はした．）

struct Array* ArrayInit( size_t type ){
	struct Array* array = (struct Array*)malloc( sizeof( struct Array ) );
	if ( array == NULL ){
		return NULL;
	}
	array->type = type;
	array->size = 0;
	array->reserved = 1;
	array->ptr = NULL;

	return array;
}

(´・ω・) < さあ，お待ちかねの，要素へのアクセスだ．

void* ArrayIthPtr( struct Array* array, size_t i ){
	return i < array->size ? (char*)array->ptr + array->type*i : NULL ;
}

せっかくだし，オーバーフロー防止もつけておいた．

実際に使うときには，

*(int*)ArrayIthPtr( array, i );

っていう風にキャストしないといけないけどね．

あとはpushをするための関数

size_t ArrayPush( struct Array* array, void* data ){

	array->size++;
	if ( array->reserved <= array->size ){
		/* allocate twice the size of current size */
		array->reserved *= 2;
		void* allocate = (void*)realloc( array->ptr, array->type*array->reserved );
		if ( allocate == NULL ){
			return SIZE_MAX;
		}
		array->ptr = allocate;
	}

	size_t idx = array->size-1;

	if ( data != NULL ){
		memcpy(
			   (void*)( (char*)array->ptr + array->type * idx ),
			   data,
			   array->type
			  );
	}
	return idx;
}

ここでなんでsize_tっていう風にインデックスで返すのかというと．
ポインタを使ってpushとかやると，新しくメモリが確保され直した時点でそのポインタが無効になるから．

別にvoid*を返せば次みたいなおもしろいことが出きるんだけどね．

void* ArrayPush( struct Array* array );

struct A b = { ... };

*(struct A*)ArrayPush( array ) = b;

(´・ω・) < ただね，人間ポインタを直接返されると保存しちゃうんだよ．

(´・ω・｀) < reallocしたら，もうそのポインタは使えないんだよ．

基本このライブラリを使うときは，インデックスですべてを管理する．

反響があればライブラリごとどっかにあげるかな．

次回予告

次回はこれを使って連想配列を実装するよ．

(´・ω・) < 一番シンプルな実装なのに，鬼のようにバグ取りが難しかった．

(´・ω・) < Pushのポインタを保存したせいでね．．．

(´・ω・｀) < 自分の首を自分で絞めました

========================

• 同じ事を考える奴はたくさんいるもんだ(日々量産-[プログラミング]C言語でvectorさせろ-)