接上文
这种方式考虑的数据区不是固定分块大小的，是可变的，那么就需要一个数据头来标识数据的大小和占用情况。
1. 区块设计
image.png
每个数据块由固定长度数据头加上可变长度数据域来组成。TLV格式，1个字节的标识tag+4个字节的长度+长度个字节的数据区,这种设计和第一种比，只需要事先申请一块大的内存区域就可以，另外数据区是可变的，节省了一点内存，但是数据头太浪费内存了，即使数据区只有一个字节，数据头也需要5个字节
2. 申请和释放
类似第一种方式。申请基本流程是：
从头遍历数据块块，一块一块的查找，先解析数据头，判断第一个字节是否是'0'，表示是空闲，再看长度是否满足申请要求，如果满足则把剩下的数据域拆分成二部分，一部分是申请的长度并返回指针。剩下的空闲部分再生成一个新的数据块，包括数据头和数据域。
如果要释放，也很简单，释放的时候除了把指针传递过来就可以，然后往上移动指针找到数据头，把数据头的表示从'1' 改成 '0', 另外为了减少碎片化的空闲内存，释放后还需要判断下一块内存是否也是空闲的，如果是则合并二块数据块为一块。
为了简单，只是合并了一次。也就是下下块或者上一块也是空闲的时候并不会合并。
看代码也很少，100来行：
////////////////////////////////////////////////////////////////////////
// TLV格式，1个字节的标识tag+4个字节的长度+长度个字节的数据区
#define dxheap_all_size 102400
static unsigned char dxheap_all[dxheap_all_size];
int dxheap_char2int(int i)
{
return (dxheap_all[i + 1] << 24) | (dxheap_all[i + 2] << 16) | (dxheap_all[i + 3] << 8) | dxheap_all[i + 4];
}
void dxheap_int2char(int length, int index)
{
dxheap_all[index + 1] = (length >> 24) & 0xFF;
dxheap_all[index + 2] = (length >> 16) & 0xFF;
dxheap_all[index + 3] = (length >> 8) & 0xFF;
dxheap_all[index + 4] = length & 0xFF;
}
void* dxheap_alloc(int size)
{
void* result;
int i;
for (i = 0; i < dxheap_all_size - 5; i++)
{
//先从前5个字节获取header的tag和length
char tag = dxheap_all[i];
int length = dxheap_char2int(i);
if (tag != '0' || size > length - 5)
{
//假如tag不为0表示不为空，或者这一块不够大，则跳过到下一块
i = i + 5 + length;
// for循环会自动加1，所以提前减1
i = i - 1;
continue;
}
dxheap_all[i] = '1';
//长度调整为size
dxheap_int2char(size, i);
//返回的地址需要跳过header
result = dxheap_all + i + 5;
//把剩余的空间标记为空
i = i + size + 5;
dxheap_all[i] = '0';
dxheap_int2char(length - size - 5, i);
//再利用free去合并空闲的区块
dxheap_free(&dxheap_all[i + 5]);
return result;
}
}
void dxheap_free(void* ptr)
{
//先判断ptr是否是整个数组区域内的指针
int min = &dxheap_all[0];
int max = &dxheap_all[dxheap_all_size];
if (ptr < min || ptr > max)
{
return;
}
int index = ptr - min;
//往前5个是header的tag
dxheap_all[index - 5] = '0';
//往前4个是header的length
int length = dxheap_char2int(index - 5);
memset(ptr, '\0', length);
//往后length个是下一个块头
int nexindex = index + length;
if (ptr > max)
{
return;
}
if (dxheap_all[nexindex] == '0')
{
//如果下一个快也为空，则合并到上一个快
int nextlength = dxheap_char2int(nexindex);
length = length + nextlength + 5;
dxheap_int2char(length, index - 5);
memset(ptr, '\0', length);
}
}
void dxheap_init()
{
//初始化，把整个数组标记为可用，长度需要减少5（header的长度）
int n = dxheap_all_size - 5;
dxheap_all[0] = '0';
dxheap_int2char(n, 0);
memset(dxheap_all + 5, '\0', n);
}
void* dxheap_realloc(void* ptr, int size)
{
if (!ptr)
{
// ptr为空表示直接alloc一块内存
return dxheap_alloc(size);
}
//先判断ptr是否是整个数组区域内的指针,不是的话直接alloc
int min = &dxheap_all[0];
int max = &dxheap_all[dxheap_all_size];
if (ptr < min || ptr > max)
{
return dxheap_alloc(size);
}
//申请一块足够大的新快，把内容复制过去
int index = ptr - min;
int length = dxheap_char2int(index - 5);
//有可能length比size大,这里不用math.min
int minLength = length;
if (length > size)
{
minLength = size;
}
void* newBlock = dxheap_alloc(size);
memcpy(newBlock, ptr, minLength);
//最后释放旧的区域
dxheap_free(ptr);
return newBlock;
}
//////////////////////////////////////////////////////////////////////////////////////
完整的源码包括测试用例，参考 git
参考下一部分
网友评论