+ GLibメモ

データ操作ライブラリとしてGLibで遊んでみたメモ。

realloc の検討

realloc はシャローコピー

reallocはシャローコピー。
シャローコピーとは単なるコピーのことで、
直値かポインタ値を区別せず単にコピーすること。

反対語はディープコピーで、これはポインタの指すデータも
コピーすることを指す。

reallocは別領域

reallocは、既存の領域を拡張してくれるわけではなく、新たに別領域を確保して、以前の内容を先頭にコピーしてくれるだけ。

組み込み機器で realloc は不要では？

仕様上の最大能力が出ないと困る。だから
アロケート失敗はテストのときに全部検出して対処するってこと。
なので、そもそもreallocする機能は要らなくて
最初からドカンとアロケートすればいいのではないか。

リンクリストのヘッダ領域

リンクリストは、前後のエントリへのポインタ（ヘッダ領域）と、
データ本体を持つ。実装で、下記の２通りが考えられる。

 (1) １エントリのヘッダ領域とデータ本体を一続きのメモリ領域に置く。
 (2) ヘッダ領域は、前後エントリへのリンクと、データ本体へのポインタだけを持つ。
     データ本体は、ライブラリユーザの責任で確保・解放する。

 （図を入れる）

GLibのやりかたは(2)。これの不利点は

 ・インダイレクトアドレッシング（ポインタアクセスのこと）が１回増える
 ・データ本体をユーザが確保・解放するのが面倒

ということ。利点は

 ・データ本体の構造やサイズに依存しない部分のソースを共通化できる
 ・ヘッダを置く領域をreallocできる。reallocしても、データ本体のアドレスは
   変わらないので、問題ない

ということ。

データ本体のアロケート

で、本体は一個ずつmallocしたら効率悪いけどどうするの？という話。

本体用の領域はこうしてる。

最初に1回mallocして「チャンク領域」を確保。
（例えばチャンク領域を256バイトずつ確保するとして)

   チャンクを指す変数
             --> チャンク { 次に振り出すアドレス = mallocした先頭(以降AAAAとします),
                            残りバイト数 = 256,
                            次のチャンク = NULL } 

で、例えば16バイトの領域が欲しいときは、「チャンクからのアロケート」関数で

   利用側に AAAA を振り出して

   チャンクを指す変数
             --> チャンク { 次に振り出すアドレス = AAAA+16,
                            残りバイト数 = 256-16,
                            次のチャンク = NULL } 
とする。
こうやって小出しにしていって...

新たに4バイトを振り出したいが...あと3バイトしか残っていない＝もういっぱいだ！
と、いつかは足りなくなる。

   チャンクを指す変数
             --> チャンク { 次に振り出すアドレス = AAAA+253,
                            残りバイト数 = 3,
                            次のチャンク = NULL } 
のように。

そうしたら、"チャンク領域全部をreallocする" のではなく、このように

   チャンクを指す変数
             --> 新しいチャンク { 新たにmallocした先頭(以降BBBBとします),
                                  残りバイト数 = 256,
                                  次のチャンク = 古いチャンク } 
             --> 古いチャンク { 次に振り出すアドレス = AAAA+253,
                                残りバイト数 = 3,
                                次のチャンク = NULL } 

する(＝古いチャンクの手前に、新しいチャンクを挿入する)、らしい。

下記ではない。

   チャンクを指す変数
             --> 古いチャンク { 次に振り出すアドレス = AAAA+253,
                                残りバイト数 = 3,
                                次のチャンク = 新しいチャンク} 
             --> 新しいチャンク { 新たにmallocした先頭(以降BBBBとします),
                                  残りバイト数 = 256,
                                  次のチャンク = NULL } 

このやりかたの賢いところは：

 (1) 領域を使い果たして、新しいチャンクを追加確保する場合でも、
   過去に小出しアロケートしたアドレスは変わらない。
   (チャンクを、reallocでより大きなサイズで確保しなおす方式だと、そうはいかない)
 (2) 新たに小出しアロケートする場所は新しいチャンクから探し始めるので
   チャンクのリンクが長くなっても速度上不利になりにくい

 （エントリの確保で毎回
   chunk = g_chunk_xxx( );
       ↑
 などと代入する必要があるのはこのためらしい。）

不要になった場合にどうするかによっていくつか選択できる。

 |__ 全部まとめて解放する機能のみ。
 |__ １個ずつ解放できる
        |__ エントリのサイズは固定 ... これだと再利用が簡単
        |__ エントリのサイズは可変 ... 再利用はコストかかるけど仕方ない

こういう、よくできたライブラリを使えばGC言語なんか要らないんじゃないかとおもうことです。


このページにて、「チャンク」という語を、チャンク管理ヘッダ と、あとで小出しにすべくドカンとallocした領域そのもの の両方の意味で混同してつかっていますが、明確に分けたら余計分かりにくかったのであえてあいまいに書いています。あしからず。