/** 
 *  @file   mlc_smp4.c
 *  @brief  ヒープ領域固定の malloc,free 例.  K&R 2nd のモノを改造
 *  @author tenk@6809.net
 *  @note
 *      mlc_smp2.c に対し、mallocポインタの範囲やヘッダにidを付加して
 *      mallocポインタの正当性チェックを追加。
 */ 
#include <string.h>
#include <assert.h> 

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

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

/// デバッグチェック用のヘッダid    // ★
#define ID_MLC          0xfdb9      // ★
#define ID_FRE          0x7531      // ★

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

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

// メモリの管理チェック用
static char *heap_top;
static char *heap_end;

/// pが ヘッダとして矛盾しないかチェック
static inline void CHECK_HDR_PTR(Header *p, int chkId) {
    char    *mp = (char *)(p + 1);
    assert(heap_top <= (char *)p && (char *)mp <= heap_end);
    assert(((int)mp & (UNIT_SZ-1)) == 0);
    assert((p == base || p->s.size > 0) && (char*)(p + p->s.size) <= heap_end);
    assert(p >= p->s.ptr || p+p->s.size <= p->s.ptr);
    assert(p->s.id == chkId);   // ★
}

/// アドレスmemからmemSzバイトをmallocで使うヒープ・メモリとして初期化.
void MallocInit(void *mem, unsigned memSz)
{
    assert(mem != NULL && memSz >= 4*UNIT_SZ);
    // デバッグ向けに適当な奇数の値で埋めとく。ただし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;
    base->s.id    = ID_FRE;     // チェック用のidを設定 ★
    freep         = base->s.ptr;
    freep->s.ptr  = base;
    // アドレス調整を考慮してサイズを求める. サイズは UNIT_SZ 単位の個数。
    freep->s.size = ((char*)mem + memSz - (char*)freep) / UNIT_SZ;
    freep->s.id   = ID_FRE;     // チェック用のidを設定 ★

    heap_top      = (char *)base;
    heap_end      = (char *)freep + freep->s.size * UNIT_SZ;
}

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

    assert(freep);
    // 空きブロック一覧を順繰りにナめる。
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
        CHECK_HDR_PTR(p, ID_FRE);
        if (p->s.size >= nunits)    // 要求サイズを満たすブロックがあった
            break;
        if (p == freep)             // 空き一覧の先頭に戻ったのなら
            return NULL;            // 空きが無かった
    }
    // CHECK_HDR_PTR(p, ID_FRE);
    // 空きが見つかったときの処理
    if (p->s.size == nunits) {      // 見つかったブロックが調度のとき
        if (prevp == p)             // 最後のブロックなら根元自体なくす
            prevp = NULL;
        else                        // まだ空きがあるなら
            prevp->s.ptr = p->s.ptr; // 空き一覧リンクはら外す
    } else {
        p->s.size -= nunits;        // そのブロックの後半から必要ブロック
        p         += p->s.size;     // を切り出す。
        p->s.size  = nunits;        //
    }
    p->s.id  = ID_MLC;              // チェック用のidを設定 ★
    p->s.ptr = NULL;                // 取得しちゃったらリンクされてない状態
    freep    = prevp;               // 今回の結果を空き一覧の先頭に反映.
    CHECK_HDR_PTR(p, ID_MLC);
    return (void *)(p + 1);         // ヘッダ部を除いたアドレスを返す
}

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

    if (ap == NULL)
        return;
    CHECK_HDR_PTR(bp, ID_MLC);
    bp->s.id = ID_FRE;              // ★ 

    // s.ptr は低いアドレスから高アドレスにむかって繋がっている
    // 返却されたメモリが、空きブロックリストのどのへんに入るか、探す
    for (p = freep; !(p < bp && bp < p->s.ptr); p = p->s.ptr) {
        CHECK_HDR_PTR(p, ID_FRE);
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;
    }
    // CHECK_HDR_PTR(p, ID_FRE);
    // 以下、挿入場所が見つかったものとして処理
    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;                          // 空きブロックの先頭を更新
    CHECK_HDR_PTR(p, ID_FRE);
}