【C言語】メモリアロケータ書けますか？
突然ですが、メモリアロケータ書けますか？
プログラマーならメモリアロケータはご存じですよね？
実際に中の処理はどのように行われているか考えたことはありますか？
考えたことがある人はもっといろいろと興味を持ってスクラッチプログラミングを楽しみましょう。マジ面白いです。
ここで扱うアロケーションモデルは 固定サイズブロック・アロケーション という単純な方法です。
主に組み込み系では今でも使われている手法だと思われます。
固定サイズブロック・アロケーションを理解していく上で得られる知識は結構多いですので、ぜひ理解をしてください。
・アロケートの概念
・物理アドレス空間
・アライメントの重要性
・ポインタの使い方
・双方向連結リスト（接続・切断）
・空き探索
・ヘッダ、データブロックの概念
・メモリ破壊（意図的な）
・アドレスウォッチ（中身を見る）
最低でもこれくらいは知識として得ることができるはずです。理解することでビットマップファイルの構造が理解できたり libzipを使ってみたり pngに変換したりとかいろいろできるようになると思います。
さて、実際には解説はしません。ソースを見て理解していってください。いろいろ機能をはしょって簡単にしてあります。
読むことでより深く理解ができるはずです。
プログラム自体は僕がすっごい単純なもの（回すだけ）からコツコツと発展させていったものです。
どうやったら効率的に高速に行えるかを考えながらやっているうちに一般的に使用されているようなモデルにたどり着いたときは正しかったんだと思いました。
人ってすごいですね。
教え方としては獅子の子落としですが、そのほうが次につながる力が身につくので頑張ってみてください。
理解できないとか、そんなのを見に来たんじゃないという方は、
こちらでものすんごく丁寧に書いてありますので参照ください。ほんと頭が下がります。
こちらにも図解がありソースもあるので理解がしやすいと思います。
Microsoftも最近メモリアロケータを公開しているようです。
Googleも独自のアロケータを公開しています。
TCMallocの実装は malloc/freeの置き換えを行うため、組み込みも超簡単なので使ってみるのもいいかもしれませんね（あまり実感はできませんでしたが・・・）。
では、頑張ってください！（鬼）
#define RoundUp(size, alignment) \
(((size) + (alignment)-1) & ~((alignment)-1)) // アライメント補正
#define BLOCK_SIZE (size_t)sizeof(BLOCK) #define INFO_SIZE (size_t)sizeof(INFO)
/*!
* メモリブロック管理構造体
/**/
typedef struct tagBLOCK {
struct tagBLOCK *prev; //!< 前の要素
struct tagBLOCK *next; //!< 次の要素
size_t size; //!< サイズ 空き領域リスト ：空きサイズ
// アロケートリスト：使用サイズ
long reserve1;
} BLOCK;
/*!
* メモリ管理構造体
/**/
typedef struct tagINFO {
BLOCK *freeTop; //!< 空き領域リスト 先頭
BLOCK *freeBottom; //!< 空き領域リスト 終端
BLOCK *allocTop; //!< アロケートリスト
long allocCount; //!< アロケートカウンタ）
} INFO;
//----------------------------------
// メモリアドレス先頭
void *g_address = nullptr;
// メモリサイズ
size_t g_size = 0;
//----------------------------------
/*!
* 空きメモリブロックの検索（前方）
* @param block 検索開始ブロック
* @param size 取得サイズ
* @return 0:失敗, BLOCK*:取得可能なメモリブロック
/**/
static BLOCK *getFrontBlock(BLOCK *block, size_t size)
{
for (/* None */; block; block = block->next)
{
// リストの中に納まるサイズの要素があった
if (size <= block->size)
{
break;
}
}
return block;
}
/*!
* 空き領域リストのリンク
* @param info 管理ポインタ
* @param block 接続対象ブロック
/**/
static void linkFreeList(INFO *info, BLOCK *block)
{
BLOCK *pos;
// block に一番近い要素を探す
for (pos = info->freeTop; pos; pos = pos->next)
{
if (block < pos)
{
break;
}
}
// block が先頭
if (pos == 0)
{
pos = info->freeTop; // 現在地を freeTop にする
// 空きリストは block だけになる
if (pos == 0)
{
// 空き領域リスト作成
block->prev = 0;
block->next = 0;
// リスト設定
info->freeTop = block;
info->freeBottom = block;
}
else
{
// block と pos は隣り合わせ
if ((char *)block + block->size == (char *)pos)
{
// block と pos を結合
BLOCK *next = pos->next;
block->prev = 0;
block->next = next;
if (next)
{
next->prev = block;
}
else /*if (next == 0)*/
{
// リスト設定
info->freeBottom = block;
}
}
else // block と pos は隣り合っていない
{
// block と pos をつなぐ
block->prev = 0;
block->next = pos;
pos->prev = block;
// リスト設定
info->freeTop = block;
}
}
}
else // pos <-> block <-> pos->next でつなぐ
{
if (pos->next)
{
// pos と block は隣り合わせ
if ((char *)pos + pos->size == (char *)block)
{
// pos と block と pos->next は隣り合わせ。
if ((char *)block + block->size == (char *)pos->next)
{
// pos と block と pos->next を結合
BLOCK *next = pos->next->next;
pos->size = pos->size + block->size + pos->next->size;
pos->next = next;
if (next)
{
next->prev = pos;
}
else /*if (next == 0)*/
{
// リスト設定
info->freeBottom = pos;
}
}
else // pos と block だけ隣り合わせ
{
// pos と block を結合
pos->size = pos->size + block->size;
}
}
else if ((char *)block + block->size == // block と pos->next は隣り合わせ
(char *)pos->next)
{
// block と pos->next を結合
BLOCK *next = pos->next->next;
block->size = block->size + pos->next->size;
block->next = next;
if (next)
{
next->prev = block;
}
else /*if (next == 0)*/
{
// リスト設定
info->freeBottom = block;
}
}
}
else /*if (pos->next == 0)*/
{
// pos と block は隣り合わせ
if ((char *)pos + pos->size == (char *)block)
{
// pos と block を結合
pos->size = pos->size + block->size;
}
else // pos と block は隣り合っていない
{
// pos と block とつなげる
pos->next = block;
block->prev = pos;
block->next = 0;
// リスト設定
info->freeBottom = block;
}
}
}
}
/*!
* 空き領域リストのアンリンク
* @param info 管理ポインタ
* @param block 切断対象ブロック
/**/
static void unlinkFreeList(INFO *info, BLOCK *block)
{
BLOCK *prev = block->prev;
BLOCK *next = block->next;
if (prev)
{
// ○ prev ○ next
if (next)
{
prev->next = next;
next->prev = prev;
}
else /*if (next == 0)*/ // ○ prev × next
{
prev->next = 0;
info->freeBottom = prev;
}
}
else /*if (prev == 0)*/
{
// × prev ○ next
if (next)
{
next->prev = 0;
info->freeTop = next;
}
else /*if (next == 0)*/ // × prev × next
{
// ここにくるとしたら
// 空きがちょうどなくなったとき
info->freeTop = 0;
info->freeBottom = 0;
}
}
}
/*!
* アロケートリストの接続（先頭に追加していく）
* @param info 管理ポインタ
* @param block 接続対象ブロック
/**/
static void linkAllocList(INFO *info, BLOCK *block)
{
// アロケートリスト追加
block->prev = 0;
block->next = info->allocTop;
// allocTop があれば設定
if (info->allocTop)
{
info->allocTop->prev = block;
}
info->allocTop = block;
// アロケートカウンタを増やす
info->allocCount++;
}
/*!
* アロケートリストの切断
* @param info 管理ポインタ
* @param block 切断対象ブロック
/**/
static void unlinkAllocList(INFO *info, BLOCK *block)
{
BLOCK *prev = block->prev;
BLOCK *next = block->next;
if (prev)
{
if (next)
{
prev->next = next;
next->prev = prev;
}
else /*if (next == 0)*/
{
prev->next = 0;
}
}
else /*if (prev == 0)*/
{
if (next)
{
next->prev = 0;
info->allocTop = next;
}
else
{
info->allocTop = 0;
}
}
// アロケートカウンタを減らす
info->allocCount--;
}
/*!
* 使用するメモリ空間の初期化
* @param addr 先頭アドレス
* @param size 空間サイズ
/**/
void meminit(void *addr, size_t size)
{
INFO *info = (INFO *)addr;
BLOCK *block;
// 空き領域リスト作成（空きとして最初に１つ作成しておく）
block = (BLOCK *)((char *)addr + INFO_SIZE);
block->prev = 0;
block->next = 0;
block->size = size - INFO_SIZE;
// バッファの設定
info->freeTop = block;
info->freeBottom = block;
info->allocTop = 0;
info->allocCount = 0; // アロケートカウンタ
// 配置
g_address = addr;
g_size = size;
}
/*!
* 指定バイト分、メモリ領域を確保する
* @paaram size 確保したいメモリサイズ
/**/
void *malloc(size_t size)
{
INFO *info;
BLOCK *block; // 現在の要素
BLOCK *add;
// サイズが不正
if (size < 0)
{
// サイズの指定が不正です
return (void *)0;
}
info = (INFO *)g_address;
// 取得サイズの設定
size = RoundUp(size + BLOCK_SIZE, sizeof(size_t));
// メモリブロックの取得
{
block = getFrontBlock(info->freeTop, size);
// 取得失敗
if (block == 0)
{
// FRONT:有効なメモリブロックが見つかりません(%d), size
return (void *)0;
}
// 追加ブロック設定
add = block;
if (block->size == size)
{
/*
* 取得した空きリストがサイズ0になったため，空き領域として使えない
* そのため，空き領域リストから切断する必要がある
*/
// 空き領域リストから切断（サイズが０になったらもう使えない）
unlinkFreeList(info, block);
}
else
{
/*
* 前方からの取得に伴い，先頭アドレスが変化してしまうため
* 取得した空きリストの残りサイズ分のブロックを再構築し
* 再度，空き領域リストに接続しなおす
*/
int rem_size = block->size - size; // 残りサイズ
// 空き領域リストから切断
unlinkFreeList(info, block);
// ブロック再設定
block = (BLOCK *)((char *)block + size);
block->size = rem_size; // 残りサイズ更新
// 空き領域リストに接続
linkFreeList(info, block);
}
}
// アロケートリスト更新
linkAllocList(info, add);
// ブロックサイズ設定
add->size = size;
// 返すポインタに情報は含まず
return (char *)add + BLOCK_SIZE;
}
/*!
* メモリ領域を解放する
* @param p 解放するメモリブロックのポインタ
/**/
void free(void *p)
{
INFO *info;
BLOCK *block;
// null 解放の保証
if (p == 0)
{
return;
}
info = (INFO *)g_address;
// ブロック設定
block = (BLOCK *)((char *)p - BLOCK_SIZE);
// アロケートリスト更新
unlinkAllocList(info, block);
// 空き領域リスト更新
linkFreeList(info, block);
}侑
悉く書を信ずれば則ち書無きに如かず