/** 
 *  @file   mlc_smp6.c
 *  @brief  ヒープ領域固定の malloc,free 例.  K&R 2nd のモノを改造
 *  @author tenk@6809.net
 *  @note
 *      mlc_smp5.c に対して、管理単位サイズを64バイトにし、ヘッダ
 *      サイズを 12 バイトとして、ヘッダの無駄領域を減らす。
 */ 
#include <string.h>
#include <assert.h>

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

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

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

/// 管理ヘッダ.  HDR_SZ = sizeof(Header) のこと
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;

/// mallocポインタから(Header*)を取得
#define MP2HDRP(mp)         ((Header*)((char *)mp - HDR_SZ))

/// ヘッダアドレスからmallocポインタを算出
#define HDRP2MP(hp)         ((void*)((char *)hp + HDR_SZ))

/// Header* を UNIT_SZ単位の sz で更新。
#define HP_ADD_SZ(p, sz)    ((Header*)((char*)(p) + (sz) * UNIT_SZ))

/// pが ヘッダとして矛盾しないかチェック
static inline void CHECK_HDR_PTR(Header *p, int chkId) {
    void *mp = HDRP2MP(p);
    assert(heap_top <= (char *)p && (char *)mp <= heap_end);
    if (p != base) {
        assert(((int)mp & (UNIT_SZ-1)) == 0);
        assert(p->s.size > 0 && (char*)HP_ADD_SZ(p, p->s.size) <= heap_end);
    }
    assert(p >= p->s.ptr || HP_ADD_SZ(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単位にアライメントしたアドレスから HDR_SZ をひいたアドレスをfreepとする
    // さらにbaseはヘッダサイズだけでいいのでfreepの手前にHDR_SZだけ確保しておく
    base = (Header*)((((unsigned long)mem + 2*HDR_SZ + UNIT_SZ-1) & ~(UNIT_SZ-1)) - 2*HDR_SZ);
    base->s.ptr   = (Header*)((char*)base + HDR_SZ);
    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 *)HP_ADD_SZ(freep, freep->s.size);
}

/// nbytesのメモリをヒープから確保
void *Malloc(unsigned nbytes)
{
    // ヘッダ部を含めた必要メモリのサイズ(UNIT_SZ単位)を求める
    unsigned nunits = (nbytes + HDR_SZ + UNIT_SZ-1) / UNIT_SZ;
    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+HDR_UNITS) { // 見つかったブロックが調度のとき
        if (prevp == p)                 // 最後のブロックなら根元自体なくす
            prevp = NULL;
        else                            // まだ空きがあるなら
            prevp->s.ptr = p->s.ptr;    // 空き一覧リンクはら外す
    } else {
        p->s.size -= nunits;            // そのブロックの後半から必要ブロック
        p = HP_ADD_SZ(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  HDRP2MP(p);                 // ヘッダ部を除いたアドレスを返す
}

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

    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 (HP_ADD_SZ(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 (HP_ADD_SZ(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);
}