#include <stdio.h>
#include <unistd.h>
#include <string.h>

/**
 * C程序设计语言  第8章  动态分配内存实例
 *
 */

// 默认每次分配最小内存 sizeof(HEADER)
#define N_ALLOCATE 1024


// 用来对齐
typedef long Align;


// 联合体  用来构建链表
union header {
    struct {
        // 指向下一个节点
        union header *ptr;
        // 节点大小
        unsigned size;
    } s;


    // 用来内存对齐
    Align x;
};


// 定义节点类型
typedef union header Header;

// 定位链表指针
static Header *freep = NULL;

// 链表初始节点
static Header base;


// 动态分配内存
void *my_malloc(unsigned);

// 向操作系统申请内存
void *my_morecore(int);

// 释放内存  重新加入链表
void my_free(void *);


// 示例
void main() {
    Header *p;
    char *t;

    // 分配30个字节
    p = (Header *)my_malloc(30);

    // 打印链表节点的size
    printf("%d\n", (p-1)->s.size);


    // t指向新分配的内存地址
    t = (char *)p;
    int i = 0;
    for (; i < 29; i++) {
        // 向新分配的地址写入数据
        t[i] = i + '0';
    }

    // 字符结尾
    t[i] = '\0';

    // 打印
    printf("%s\n", t);
    printf("%lu\n", strlen(t));


}


// 动态分配内存
void *my_malloc(unsigned nbytes) {

    Header *p, *prevp;

    unsigned nunits;

    // 字节转换为节点单位长度
    // + sizeof(Header) 额外加上了节点占用的内存
    // - 1 这里减1的目的是当长度刚好是sizeof(Header)整数倍时 最后面的 + 1 配合使用   / 这个运算会舍去小数部分
    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    // 前置节点指向链表
    if ((prevp = freep) == NULL) {

        // 初始化链表节点数据  下一个节点指向了自己
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }


    // 指针p遍历链表  找出空闲内存块并返回  初始时p指向了下一个节点
    for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {

            // 空闲内容大于所需内存时
            if (p->s.size > nunits) {

                // 当有节点截出所需大小
                p->s.size -= nunits;

                // 向前移动 形成要返回的节点
                p += p->s.size;
                // 初始化节点大小
                p->s.size = nunits;
            } else {

                // 刚好相等时  直接移除当前节点  将前置节点的下一个节点指向当前节点的下一个节点
                prevp->s.ptr = p->s.ptr;
            }

            // 链表重新定位到前置节点
            freep = prevp;

            // 返回分配节点的下一个地址   节点本身占用内存空间
            return (void *)(p + 1);
        }



        // 遍历链表 回到了初始位置  没有找到合适内存
        if ((p == freep)) {

            // 向系统申请内存
            if ((p = my_morecore(nunits)) == NULL) {
                return NULL;
            }
        }
    }
}


// 向系统申请内存
void *my_morecore(int nunits) {

    char *p;
    Header *t;

    // 每次申请最小单位
    if (nunits < N_ALLOCATE) {
        nunits = N_ALLOCATE;
    }

    p = sbrk(nunits * sizeof(Header));
    // 是否申请成功
    if (p == (char *)-1) {
        return NULL;
    }


    // 申请成功  初始化节点大小
    t = (Header *)p;
    t->s.size = nunits;


    // 节点数据加入空间内存链表
    my_free((void *)(t + 1));


    // 重新返回当前节点
    return freep;
}


// 节点加入空闲链表   并合并地址相邻的内存
void my_free(void *ap) {
    Header *bp, *p;

    // 重新指向节点最开始位置
    bp = (Header *)ap - 1;


    // 遍历链表  找到节点地址的前一个合适节点  主要根据内存地址的顺序

    // 如果在两个节点之前 则退出
    for (p = freep;!(bp > p && bp < p->s.ptr);p = p->s.ptr) {

        // 如果在链表的尾部
        if (p >= p->s.ptr && (bp < p->s.ptr || bp > p)) {
            break;
        }
    }

    // 合并前置节点
    if (bp == (p + p->s.size)) {
        p->s.size = bp->s.size;
    } else {
        p->s.ptr = bp;
    }


    // 合并后置节点
    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;
    }

    // 链表定位到新加入节点的前一个节点
    freep = p;
}