/** 
 *  @file   mlc_smp7.c
 *  @brief  ヒープ領域固定の malloc,free 例.
 *  @author tenk@6809.net
 *  @note
 *      mlc_smp6.c に対して、アドレスの取得を高いアドレスになるようにする
 */ 
#include <string.h>
#include <assert.h>

/// ヘッダ＆メモリ取得の基本単位. // sizeof(double)の倍数かつ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
    } s;
} Header;

/// 空きブロックの管理用
static Header *base;            // 最下位アドレスの空きブロックを指す

// メモリの管理チェック用
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->s.ptr == 0 || p <= p->s.ptr || HP_ADD_SZ(p->s.ptr, p->s.ptr->s.size) <= p);
    assert(p->s.id == chkId);
}

/// アドレスmemからmemSzバイトをmallocで使うヒープ・メモリとして初期化.
void MallocInit(void *mem, unsigned memSz)
{
    Header *freep;

    assert(mem != NULL && memSz >= 4*UNIT_SZ);
    // デバッグ向けに適当な奇数の値で埋めとく。ただし0や0xffだと、それに
    memset(mem, 0x55, memSz);   // 依存したバグが出来易いので避ける:-)

    // UNIT_SZ単位にアライメントしたアドレスから 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 = base;
    Header   *p;

    assert(base);
    // 空きブロック一覧を順繰りにナめる。
    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 == base)                  // 空き一覧の先頭に戻ったのなら
            return NULL;                // 空きが無かった
    }
    //CHECK_HDR_PTR(p, ID_FRE);
    // 空きが見つかったときの処理
    if (p->s.size < nunits+HDR_UNITS) { // 見つかったブロックが調度のとき
        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;                    // 使わないリンクはとりあえずNULL化
                                        // base = prevp; は削除
    CHECK_HDR_PTR(p, ID_MLC);
    return  HDRP2MP(p);                 // ヘッダ部を除いたアドレスを返す
}

/// malloc したメモリを開放
void Free(void *ap)
{
    // s.ptr は高いアドレスの空きブロックから低いアドレスにむかって繋がっている/繋げる
    Header *bp = MP2HDRP(ap);
    Header *r  = NULL;
    Header *q  = base;                  // 最下位アドレス       
    Header *p  = base->s.ptr;           // 最上位アドレス       

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

    if (bp < base->s.ptr) {                 // highの空きブロックより低い
        // ブロックp(要素n)とq(要素n+1)の間に今回の領域が存在しない間ループ
        while ((p < bp && bp < q) == 0) {
            CHECK_HDR_PTR(p, ID_FRE);
            r = q;
            q = p;
            p = p->s.ptr;
            if (q == base)
                break;
        }
    }
    //CHECK_HDR_PTR(p, ID_FRE);

    if (HP_ADD_SZ(p,p->s.size) == bp) { // 直前の要素と合体できる場合
        p->s.size += bp->s.size;        //   サイズ更新
        //q->s.ptr = p;
        bp = p;
    } else {                            // 合体できない場合
        bp->s.ptr = p;                  //   繋ぎ替え
    }
    if (HP_ADD_SZ(bp,bp->s.size) == q) {// 直後の要素と合体できる場合
        // ※ bp>base->s.ptrの場合は条件が成立しないのでここに来ない(r=NULLでは来ない)
        bp->s.size += q->s.size;        // サイズ更新
        r->s.ptr = bp;                  // 繋ぎ替え
    } else {                            // 合体できない場合
        q->s.ptr   = bp;                // qとpの間に連結
    }
    CHECK_HDR_PTR(bp, ID_FRE);
    CHECK_HDR_PTR(p, ID_FRE);
}