接上文
上一种方式的数据头占用字节太多，第三种方式改造一下，把固定数据头改成可变数据头。用1-3个字节来做数据头，其他结构不变。
1. 区块设计
image.png
最多3个字节，最少1个字节。如果是一个字节，去掉第一个字节的2个特殊位，只有6位，最多表示到数字63；如果是2个字节，去掉第二个字节的1个特殊位，只剩下13位，能表达的最大数字是2的13次方也就是8191；3个字节最多能表达的最大数字是2的21次方也就是 2097151，在笔者的单片机里够用了，如果你那边不够用，可以再按同样的方式扩展到4个字节。
相对上一次方式，很多小内存申请都只需要用1个字节的头，大大的节省了不少内存。
2. 申请和释放
类似上一种方式。申请基本流程是：
从头遍历数据块块，一块一块的查找，先解析数据头，判断第一个字节的最后一位是否是0，表示是空闲，再根据规则算出1字节或2字节或3字节的头对应的数据长度是多次，看看长度是否满足申请要求，如果满足则把剩下的数据域拆分成二部分，一部分是申请的长度并返回指针。剩下的空闲部分再生成一个新的数据块，包括数据头和数据域。
这个时候要注意的是数据域的长度变化的时候，数据头的长度可能发生变化，比如一开始数据域的长度用了3个字节，然后数据域的长度变成1个字节后，数据域的长度就会变成以前的长度加2，这会导致代码的复杂度增大。
如果要释放，也很简单，释放的时候除了把指针传递过来，还需要传长度，根据长度推算出数据头的字节数，然后往上移动指针找到数据头，把数据头的表示从 1 改成 0 , 另外为了减少碎片化的空闲内存，释放后还需要判断下一块内存是否也是空闲的，如果是则合并二块数据块为一块。
这里为了确保内存够用，会在遍历所有空闲区块都不够用的时候触发一次 GC，GC后再尝试申请一次，如果还不行会报错。
GC的流程就是从头到尾遍历空闲区块，然后和下一个空闲合并。
代码相对前2种就要复杂不少，大概300多行了：
完整的源码包括测试用例，参考 git
网友评论