/**
 *  @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);
}

/// 配列を想定した引数で、かつ、0クリアされるメモリ確保
void *Calloc(unsigned asz, unsigned num)
{
    unsigned sz = asz * num;
    void     *m = Malloc(sz);
    if (m)
        memset(m, 0, sz);
    return m;
}

/// Header::s.size の値を実際のバイト数に変換 (usz=0は未対応)
#define UNITSZ2BYT(usz)     ((usz) * UNIT_SZ - HDR_SZ)

/// mallocされたメモリの領域サイズを返す
unsigned Msize(void *mp)
{
    unsigned sz;
    Header   *p = MP2HDRP(mp);
    CHECK_HDR_PTR(p, ID_MLC);
    sz = UNITSZ2BYT(p->s.size);
    return sz;
}

/// mallocしたメモリのサイズ変更(手抜き版)
void *Realloc(void *s, unsigned dsz)
{
    unsigned ssz = Msize(s);
    void     *d  = Malloc(dsz);
    if (ssz > dsz)
        ssz = dsz;
    if (d)
        memcpy(d, s, ssz);
    Free(s);
    return d;
}

/// p が ヘッダとして正常(1)か否(0)か
static inline int IS_HDR_PTR(Header *p, int chkId) {
    void *mp = HDRP2MP(p);
    if ((char *)p  <  heap_top) return 0;
    if ((char *)mp >  heap_end) return 0;
    if (p != base) {
        if ((int)mp & (UNIT_SZ-1))  return 0;
        if (p->s.size == 0 || (char*)HP_ADD_SZ((p), (p)->s.size) > heap_end) return 0;
    }
    if (p < p->s.ptr && HP_ADD_SZ(p, p->s.size) > p->s.ptr) return 0;
    if (p->s.id != chkId) return 0;
    return 1;
}

/// mpが malloc されたポインタか(1) 否か(0) をチェック
int IsMallocPtr(void *mp)
{
    return IS_HDR_PTR(MP2HDRP(mp), ID_MLC);
}

/// mallocできる最大サイズを求める
unsigned MaxSize(void)
{
    unsigned sz = 0;
    Header *p;
    assert(base);
    for (p = base->s.ptr; ;p = p->s.ptr) {
        CHECK_HDR_PTR(p, ID_FRE);
        if (sz < p->s.size)
            sz = p->s.size;
        if (p == base)
            break;
    }
    return (sz > 0) ? UNITSZ2BYT(sz) : 0;
}

/// 空き領域のサイズを求める
/// @param *maxSize mallocできる最大サイズを返す
/// @param *total   空き領域の合計サイズを返す
/// @param *split   空き領域の分割数を返す
/// @return         空きリストが壊れてる(0)か正常(1)かを返す
int GetEmptySize(int *maxSize, int *total, int *split)
{
    unsigned maxSz= 0;
    int      n    = 0;
    int      sum  = 0;
    Header *p;
    assert(base);
    for (p = base->s.ptr; ;p = p->s.ptr) {
        if (IS_HDR_PTR(p, ID_FRE) == 0) {
          #if 0
            #define ERR_PRINTF(x)   printf x
            Header *q;
            int    i = 0;
            ERR_PRINTF(("Mallocの空管理リストが不正\t"));
            for (q = base->s.ptr; IS_HDR_PTR(q, ID_FRE); q = q->s.ptr, i++) {
                ERR_PRINTF(("%d:%#x->", i,q));
            }
            ERR_PRINTF(("%d:%#x\n", n,p));
          #endif
            return 0;
        }
        if (maxSz < p->s.size)
            maxSz = p->s.size;
        sum += UNITSZ2BYT(p->s.size);
        n++;
        if (p == base)
            break;
    }
    if (maxSize) *maxSize = (maxSz > 0) ? UNITSZ2BYT(maxSz) : 0;
    if (total)   *total   = sum;
    if (split)   *split   = n;
    return 1;
}