/**
 *  @file   mlc_smp2.c
 *  @brief  ヒープ領域固定の malloc,free 例.  K&R 2nd のモノを改造
 *  @author tenk@6809.net
 *  @note
 *      ヘッダサイズを#defineラベルで可変に.
 *      mlc_smp1.c にコメントを付加(というか、mlc_smp2.cから 1 を作った)
 */
#include <string.h>

/// アライメント対策の型. アドレス違反で落ちないように一番広い幅の型を使う
typedef double Align;

/// ヘッダ＆メモリ取得の基本単位. // sizeof(Align)の倍数かつ2のn乗のこと
#define UNIT_SZ         16

/// 管理ヘッダ. sizeof(Header) == UNIT_SZ を満たすこと
typedef union Header {
    struct {
        union Header *ptr;          // 次のブロックへのポインタ
        unsigned     size;          // サイズ(sizeof(Header)単位の個数)
    } s;
    Align x[UNIT_SZ/sizeof(Align)]; // アライメント/基本サイズの調整
} Header;

/// 空きブロックの管理用
static Header *base;
static Header *freep;

/// アドレスmemからmemSzバイトをmallocで使うヒープ・メモリとして初期化.
void MallocInit(void *mem, unsigned memSz)
{
    // デバッグ向けに適当な奇数の値で埋めとく。ただし0や0xffだと、それに
    memset(mem, 0x55, memSz);   // 依存したバグが出来易いので避ける:-)

    // 先頭アドレスをUNIT_SZ単位にアライメントしておく
    base          = (Header*)(((unsigned long)mem+UNIT_SZ-1) & ~(UNIT_SZ-1));
    base->s.ptr   = base + 1;
    base->s.size  = 0;
    freep         = base->s.ptr;
    freep->s.ptr  = base;
    // アドレス調整を考慮してサイズを求める. サイズは'Header'個数。
    freep->s.size = ((char*)mem + memSz - (char*)freep) / UNIT_SZ;
}

/// nbytesのメモリをヒープから確保
void *Malloc(unsigned nbytes)
{
    // ヘッダ部を含めた必要メモリのサイズ(Header単位)を求める
    unsigned nunits = (nbytes + UNIT_SZ-1) / UNIT_SZ + 1;
    Header   *prevp = freep;
    Header   *p;

    // 空きブロック一覧を順繰りにナめる。
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits)    // 要求サイズを満たすブロックがあった
            break;
        if (p == freep)             // 空き一覧の先頭に戻ったのなら
            return NULL;            // 空きが無かった
    }
    // 空きが見つかったときの処理
    if (p->s.size == nunits) {      // 見つかったブロックが調度のとき
        prevp->s.ptr = p->s.ptr;    // 空き一覧リンクはら外す
    } else {
        p->s.size -= nunits;        // そのブロックの後半から必要ブロック
        p         += p->s.size;     // を切り出す。
        p->s.size  = nunits;        //
    }
    freep = prevp;                  // 今回の結果を空き一覧の先頭に反映.
    return (void *)(p + 1);         // ヘッダ部を除いたアドレスを返す
}

/// malloc したメモリを開放
void Free(void *ap)
{
    Header *p;
    Header *bp = (Header *)ap - 1;

    // s.ptr は低いアドレスから高アドレスにむかって繋がっている
    // 返却されたメモリが、空きブロックリストのどのへんに入るか、探す
    for (p = freep; !(p < bp && bp < p->s.ptr); p = p->s.ptr) {
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;
    }
    // 以下、挿入場所が見つかったものとして処理
    if (bp + bp->s.size == p->s.ptr) {  // 直後の要素と合体できる場合
        bp->s.size += p->s.ptr->s.size; //   サイズ更新
        bp->s.ptr  =  p->s.ptr->s.ptr;  //   繋ぎ替え
    } else {                            // 合体できない場合
        bp->s.ptr  =  p->s.ptr;         //   繋ぎ替え
    }
    if (p + p->s.size == bp) {          // 直前の要素と合体できる場合
        p->s.size += bp->s.size;        //   サイズ更新
        p->s.ptr  =  bp->s.ptr;         //   繋ぎ替え
    } else {                            // 合体できない場合
        p->s.ptr  =  bp;                //   繋ぎ替え
    }
    freep = p;                          // 空きブロックの先頭を更新
}