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

`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](https://qiita.com/nothingcosmos/items/3932b159d225d49d9067)
 - [Simulation of templates in C (for a queue data type)](https://stackoverflow.com/questions/10950828/simulation-of-templates-in-c-for-a-queue-data-type)
- 使えるのであればC++のvectorを使ってください．よほど安全なので．


特徴
=======

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


アイディア
=======

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


解説
========

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

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

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

void* ptr = (void*)a;
```

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

当然ながら

```c
ptr[1]
```

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

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

解説
----------

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

```c
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`八個分の容量を食う．

ここで

```c
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`ってなるはずだ．

つまり，こういうことだ

```c
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`何個分か)が分かれば，正しいアドレスを計算できる．

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

```c
struct A{
	...
};

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

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


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

```

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

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

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

```c
*(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*`で動かして，元のポインタの型に戻す．

作ったライブラリ抜粋
====================

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

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

まずは構造体だ．

```c
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関数も用意はした．）

```c
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;
}
```


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

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

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

実際に使うときには，
```c
*(int*)ArrayIthPtr( array, i );
```

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

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

```c
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*`を返せば次みたいなおもしろいことが出きるんだけどね．

```c
void* ArrayPush( struct Array* array );

struct A b = { ... };

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

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

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

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


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

次回予告
=====================

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

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

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

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



========================
- 同じ事を考える奴はたくさんいるもんだ([日々量産-[プログラミング]C言語でvectorさせろ-](http://d.hatena.ne.jp/ryousanngata/20100920/1284911587))