---

堆的概念

所谓的堆就是一块空间的内存，可以来管理这块内存。从这块内存中取出一部分然后再释放回去。

---

使用C语言实现 堆

char heap_buf[1024];            // 定义一个堆空间
int pos=0;                      // 当前位置

void *my_malloc(int size)
{
    int old_pos = pos;           // 记录旧位置
    pos += size;                 // 更新位置点
    return &heap_buf[old_pos];   // 返回旧位置地址
}

根据堆的概念写出上面的代码。定义出一块堆的空间heap_buf，可以在这块堆空间上任意申请，使用和释放空间。
使用Keil单步调试，对堆heap_buf申请和使用情况

根据单步调试情况可以看出：buf分配的起始地址就是heap_buf 堆空间起始地址，并且完成对堆空间的写入。

---

堆空间解析

使用上面的代码可以实现简单堆空间的申请和使用，但是这种简单的malloc函数没有办法释放空间。如下图所示

假如第一次使用my_malloc分配100字节空间buf1，第二次使用my_malloc分配100字节空间buf2
此时去释放空间buf1的空间my_free(buf1)，只知道buf1的起始地址，却不知道应该释放多大的内存空间。 因此使用简单的malloc无法实现释放空间。

在操作系统中对堆空间的管理，在分配实际内存前有一段头部空间，其中存放分配这段内存的相关信息包括分配的空间大小。
因此使用malloc函数申请堆空间时， 实际在堆空间中分配两部分：头部信息+实际可操作的堆空间。malloc返回值是实际可操作的堆空间的起始地址。
使用free函数释放空间时， 会根据传入的地址（实际可操作的堆空间的起始地址）减去固定的头部大小，找到头部中这块申请的堆空间大小。从而释放空间。

假如将buf2释放掉后，整个堆空间的空闲区域有buf2头部信息+50字节+其他空闲区域。这时要申请100空间的内存，应该如何分配呢？
为了解决这个问题，引入链表来解决。链表基本形式如下：

// 定义全局链表
struct head
{
    int size;
    struct head *next_free;
}

struct head g_heap;
g_heap.size = 0;
g_heap.next_free = NULL;

初始状态， 在堆内存空闲区域会构建一个头部，表明当前堆空闲大小以及下一个堆空闲的位置。

分配100字节空间。 会先判断g_heap.next_free所指向的头部中size的大小，若大于申请的空间就会划分出两块，一块为分配的空间，另一块为空闲空间。

以此类推，继续分配出50字节和100字节的空间

当执行free(buf2)函数，释放50字节的空间时，流程如下：
1、先将buf2的地址减去8，查找头部信息中的size为50
2、释放50+8字节的空间。
3、g_heap.next_free所指向空闲空间头部中next_free就会指向buf2已经释放的起始地址（上图中绿色的开头）。

这样，当下一个malloc的时候，会先看g_heap.next_free所指向空闲空间头部中size。
若大于申请的大小就划分空间；
若小于申请的大小就继续判断next_free所指向的size大小。