kuno@gssm.otsuka.tsukuba.ac.jp writes:

> P.S. もしかしてセルは全部2のべきサイズでそのサイズ種類数だけリス
>      トを作るってやつかな。無駄が最大50%だけどそれなら定数かも。
>      前田さんどうしますか。

河野さんは、ポインタをずらすだけで割り付けて、解放する時は全体を一括解
放する(ポインタを初期値に戻す)ようなアロケータを考えてるのでは。

memory_pool *make_memory_pool(size_t bytes);
void *pool_allocate(memory_pool *, size_t bytes);
void pool_reset(memory_pool *);

typedef struct memory_pool_impl {
  size_t size;
  void *base;
  size_t used;
} memory_pool;

みたいな感じ。

もちろん、malloc/freeほどgeneralではないですが、これで済むような応用な
ら(割り付けた部分を初期化しないとすれば)pool_allocateもpool_resetも確
かにバイト数によらずO(1)でしょう。

しかし、割り付けた部分を必ず初期化するとか、実際のデータを書き込むとか
すると仮定するなら、他の記事に書いた通りGCを使う場合とオーダーは同じで
す。

                                前田敦司