我們都知道 c 語言申請內存釋放內存是 alloc / free 由蘑。直接調用函數就行甜无，但是某些特定的場景無法調用 c 的標準庫，比如單片機津辩，資源有限砚尽，并沒有帶 c 的標準庫施无，則需要自己實現 alloc / free，基本上就是先事先在單片機里申請一塊連續(xù)的內存必孤，然后基于這一塊內存實現內存管理猾骡。這里通過3種方式實現，以供參考：
因為在單片機上敷搪，內存非常有限兴想，大概不到100k，所以能用來額外申請的內存很小赡勘，另外不考慮多線程嫂便，所以實現內存管理比較簡單。多線程的可以參考微軟的 minialloc
我們先討論最簡單的一種闸与，定長的方式毙替，單片機很多情況自身的RAM也是這樣設計的岸售，也就是不管是 char 、int 都是4個字節(jié)厂画，這樣會帶來內存的一部分浪費凸丸。
1. 區(qū)塊設計
如上圖，需要先申請2塊區(qū)域：
- 數據區(qū)：以4個字節(jié)為一塊,申請的時候都是返回以塊為單位
- 標識區(qū)：用來標識數據區(qū)那一塊是可用的木羹，是可用被申請的甲雅，為了節(jié)省內存解孙，標識區(qū)用一個字節(jié)中的一位來標識數據區(qū)的一塊（4個字節(jié)）的可用性坑填。這樣，假如申請64塊也就是256個字節(jié)的數據區(qū)弛姜，需要8個字節(jié)的標識區(qū)脐瑰。
2. 申請和釋放
這里實現的是 realloc 方法，而不是 alloc 廷臼，區(qū)別就是 alloc 每次執(zhí)行都是申請一塊新的內存區(qū)域苍在，而 realloc 執(zhí)行的時候需要傳遞舊的指針，如果舊的不為空荠商，則相當于給舊的指針擴大或縮小申請的內存寂恬。申請基本流程是：
從頭遍歷標記區(qū)，一位一位的查找莱没，這里注意在常規(guī)的內存管理一般不會從頭遍歷初肉，會從上一次申請的地方往下遍歷，但是我們這里內存很小饰躲，從頭遍歷也不會影響速度牙咏。
找到第一個空閑位（為0），再查找后續(xù)的連續(xù)空的位數量是否滿足申請內存的塊數嘹裂，如果滿足妄壶，則返回指針，并把申請的所有標識位都改成 1 寄狼。比如要申請34個字節(jié)丁寄，則計算需要9個塊（4k一塊），則遍歷找到第一組連續(xù)超過9個塊都為空閑的區(qū)域返回回去泊愧。
如果要釋放伊磺，也很簡單，釋放的時候除了把指針傳遞過來拼卵，還需要把釋放的大小也傳遞過來奢浑，這樣釋放的時候只需要把標識區(qū)連續(xù)的區(qū)域標記為0即可∫溉看代碼很少雀彼，100來行：
////////////////////////////////////////////////////////////////////////
// 固定大小格式壤蚜，每塊占用4個字節(jié)（特定的單片機只支持這種方式
// 版本 20220913
//申請的內存區(qū)塊個數
#define dxheap_block_count 64
//總共占用的字節(jié)數需要*4
static unsigned char dxheap[dxheap_block_count * 4];
//需要用count/8個字節(jié)來標識每個區(qū)塊占用還是空閑，1個bit來表示一個區(qū)塊的情況徊哑，0表示空閑袜刷，1表示占用
static unsigned char dxheap_empty_flags[dxheap_block_count / 8];
/**
* @brief 內存塊標識占用還是空閑,把一段連續(xù)的塊標記成占用還是空閑
*
* @param tag 0表示空閑，1表示占用
* @param start_block_index 開始的塊序號莺丑，從0開始
* @param count 連續(xù)塊的個數
*/
void dxheap_flag_write(int tag, int start_block_index, int count)
{
int index;
for (index = start_block_index; index < start_block_index + count; index++)
{
if (tag)
{
dxheap_empty_flags[index / 8] = dxheap_empty_flags[index / 8] | (1 << (index % 8));
}
else
{
dxheap_empty_flags[index / 8] = dxheap_empty_flags[index / 8] &= ~(1 << (index % 8));
}
}
}
//判斷第index個塊是否被占用 0表示空閑著蟹，1表示占用
int dxheap_flag_read(int index)
{
char c = dxheap_empty_flags[index / 8];
int pos = index % 8;
return (c & (1 << pos)) >> pos;
}
//判斷從第index個塊開始，連續(xù)count個塊都為空則返回0梢莽，否則1
int dxheap_has_count_empty(int index, int count)
{
int notfound = 0;
int i = index;
while (notfound == 0 && i < dxheap_block_count && i <= (index + count))
{
notfound = notfound + dxheap_flag_read(i);
i++;
}
return notfound == 0;
}
void *dxheap_alloc(int size)
{
//先計算需要的塊數量
int count;
if (size % 4 == 0)
{
count = size / 4;
}
else
{
//內存可能浪費
count = (size / 4) + 1;
}
if (count > dxheap_block_count)
{
printf("not enough memory found\n");
return -1;
}
void *result;
int i = 0;
while (i < dxheap_block_count)
{
int flag = dxheap_flag_read(i);
if (flag)
{
//假如不為空,則跳過到下一塊
i++;
continue;
}
//判斷是否能找到count個空閑塊
int isfound = dxheap_has_count_empty(i, count);
if (isfound)
{
dxheap_flag_write(1, i, count);
return dxheap + i * 4;
}
else
{
i++;
continue;
}
}
printf("not enough memory found\n");
return -1;
}
void dxheap_free(void *ptr, int osize)
{
//先判斷ptr是否是整個數組區(qū)域內的指針
int min = &dxheap[0];
int max = &dxheap[dxheap_block_count * 4 - 1];
if (ptr < min || ptr > max)
{
return;
}
//先算出ptr對應的指針指向第幾塊,這里index必然是可以整除4的萧豆，是塊的首地址。除非亂傳一個地址過來
int index = ptr - min;
index = index / 4;
//后面osize個字節(jié)對應的塊也需要置空
int count = osize / 4;
if (osize % 4 != 0)
{
count++;
}
dxheap_flag_write(0, index, count);
memset(ptr, 0x00, count * 4);
}
void dxheap_init()
{
//初始化昏名，把整個數組標記為可用涮雷，
memset(dxheap, 0x00, dxheap_block_count * 4);
}
void *dxheap_realloc(void *ptr, int osize, int size)
{
if (!ptr)
{
// ptr為空表示直接alloc一塊內存
void *block = dxheap_alloc(size);
return block;
}
//先判斷ptr是否是整個數組區(qū)域內的指針,不是的話直接alloc
int min = &dxheap[0];
int max = &dxheap[dxheap_block_count * 4 - 1];
if (ptr < min || ptr > max)
{
void *block = dxheap_alloc(size);
return block;
}
//申請一塊足夠大的新快，把內容復制過去
int index = ptr - min;
//有可能osize比size大,這里不用math.min
int minLength = osize;
if (osize > size)
{
minLength = size;
}
void *newBlock = dxheap_alloc(size);
if (newBlock == -1)
{
return newBlock;
}
memcpy(newBlock, ptr, minLength);
//最后釋放舊的區(qū)域
dxheap_free(ptr, osize);
return newBlock;
}
// //////////////////////////////////////////////////////////////////////////////////////
對外暴露的函數主要是 dxheap_realloc,dxheap_free轻局。其中 dxheap_alloc是申請一塊新區(qū)域洪鸭，而 dxheap_realloc也是簡化了過程，也就是想要擴大或縮小現有指針指向的區(qū)塊仑扑，是先申請一塊額外的新塊區(qū)览爵，然后釋放舊塊區(qū)，而不是在原有區(qū)域上操作镇饮。
完整的源碼包括測試用例蜓竹，參考 git
參考下一部分
