聲明： 本人的實力是廢鐵級別，這也是我在博客園第一次發表文章，如果內容存在錯誤請各位大佬能否在評論區指正一下本人萬分感謝🙇。
一、概述
在常規單片機設備開發中一般很少用到動態內存管理malloc/free函數，可是在某些情況下我們採用動態內存管理實現一些功能時是最理想的辦法例如網絡通訊時接收不定長數組又或者實現不定長數據排序時往往用到動態內存當然你也可以給這些任務劃定一個固定的內存區域不過這些劃定的固定區域往往比實際需要的內存區域大的多的多的造成不必要的內存浪費。所以在這些情況下采用動態內存管理是很有必要的，在實際開發中採用標準庫的內存管理方案存在一些問題，如：內存資源、實時性、穩定性、調試難度等多維度的問題，核心原因是標準malloc的設計初衷是面向 PC / 服務器等資源充裕、非強實時的場景，而非單片機的受限環境。在這種情況下自定義開發動態內存管理是有必要的，本人採用最佳適配策略實現讓需要的分配的內存採用最小適配內存的策略儘量減少內存碎片並採用紅黑樹的數據結構管理每個內存結點讓每次內存分配時間節點儘量相等。
二、方案實現思路
內存分配過程中的合法性檢查與分配策略
在現代內存管理系統中，內存分配不僅要考慮性能，還必須保證內存的安全性和有效性。因此，每次內存分配操作前，都需要進行一系列檢查和計算，確保分配的內存符合要求，並能夠有效利用系統資源。本文將詳細介紹內存分配過程中的合法性檢查、內存塊計算、紅黑樹查找、鏈表節點管理以及內存裁剪的策略。
- 內存分配前的合法性檢查
每次進行內存分配時，首先需要檢查傳入的參數是否合法。包括但不限於以下幾點：
檢查請求的內存大小是否為正值。
檢查請求的內存是否符合對齊要求（例如8字節、16字節對齊）。
檢查系統內存池中是否有足夠的空間滿足分配需求。
只有當所有參數都通過合法性驗證後，才能繼續進行下一步的內存計算和分配操作。
- 內存塊大小的計算
內存分配請求的處理不僅涉及內存塊的大小計算，還需要考慮元數據部分的大小。每個內存塊通常會附加一些元數據（例如內存塊的大小、狀態信息等），這些元數據佔用一定的內存空間。因此，在計算實際分配的內存塊大小時，需要將請求的內存大小與元數據的大小相加，從而確保內存塊能夠完整存儲數據及其相關的元信息。
此處，ALIGN_SIZE 函數會確保分配的內存塊大小滿足內存對齊的要求：
#define Offset_Byte 8
#define ALIGN_SIZE(size) (((size) + ((Offset_Byte) - 1)) & ~((Offset_Byte) - 1))
- 使用紅黑樹查找合適的內存塊
內存管理器通常使用紅黑樹來存儲空閒內存塊的元數據。通過紅黑樹的高效查找特性，我們能夠快速定位到合適的空閒內存塊。接下來的步驟是：
將計算出的內存塊大小作為關鍵字，在紅黑樹中進行查找。
如果紅黑樹中沒有找到合適的內存塊（即找不到與請求的內存大小匹配的節點），則説明系統無法滿足當前的分配請求，返回 NULL，表示分配失敗。
- 判斷鏈表節點的存在
如果紅黑樹中找到了一些可能適合的節點，我們接下來需要進一步判斷：
檢查該節點是否包含其他已分配的鏈表節點。通常，空閒的內存塊會形成一個鏈表，以便進行快速回收和重用。
如果節點上存在其他鏈表節點（即該內存塊已經部分被分配或使用），則直接返回鏈表節點，避免重複分配相同的內存區域。
如果沒有其他鏈表節點，則可以直接返回紅黑樹節點，表示該內存塊可以被直接分配。
- 內存塊裁剪與紅黑樹更新
在實際分配內存時，如果找到的內存塊大小大於請求的大小，我們可能會選擇對內存塊進行裁剪。內存裁剪的目的是將過大的內存塊切分為適合請求的大小，同時將剩餘的內存返回給紅黑樹，以便後續使用。裁剪的具體步驟如下：
確認剩餘部分的內存大小滿足最小內存塊要求。
將剩餘部分返回到紅黑樹中，並標記為一個新的空閒內存塊，供後續分配使用。
三、數據結構説明
1、紅黑樹 + 鏈表結構（空閒塊組織方式）
2、單個內存塊結構（MeMory_Information)
四、源碼實現
使用注意事項：
1、在使用前一定要進行內存管理初始化Init_malloc(內存首地址，內存長度，枷鎖函數（可為NULL），解鎖函數(可為NULL))；
2、對每個分配動態內存一定不要內存越界內存越界會導致整個代碼崩潰；
3、根據平台的需要調整Offset_Byte宏可調整內存對齊的大小；
1、RB_Tree_Memory.h文件實現
#ifndef MY_MALLOC_H
#define MY_MALLOC_H
#define NULL ((void*)0)
//可修改的內存對齊數（2的指數倍）
#define Offset_Byte 8
typedef unsigned char Byte;
typedef unsigned int UINT_L;
typedef struct MeMory_Information MeMory_Information;//內存信息結構體
extern Byte Init_malloc(void* start_addr, UINT_L length, void (*Lock_State)(void), void (*Unlock_State)(void));//初始化內存管理器
// ---------------------------------------------內部數據結構
static void List_add(MeMory_Information* list, MeMory_Information* add);
static void List_delete(MeMory_Information* del);
static void List_To_Node(MeMory_Information* Node);
static void L_L(MeMory_Information* Node_Left, MeMory_Information* Node);
static void R_R(MeMory_Information* Node, MeMory_Information* Node_Right);
static inline MeMory_Information* RB_LL(MeMory_Information* Grand_parent, MeMory_Information* parent);
static inline MeMory_Information* RB_RR(MeMory_Information* Grand_parent, MeMory_Information* parent);
static inline MeMory_Information* RB_LR(MeMory_Information* Grand_parent, MeMory_Information* parent, MeMory_Information* Node);
static inline MeMory_Information* RB_RL(MeMory_Information* Grand_parent, MeMory_Information* parent, MeMory_Information* Node);
static MeMory_Information* RB_Add_AdJust(MeMory_Information* Node);
static void RB_Node_Add(MeMory_Information* Add);
static MeMory_Information* Get_Right(MeMory_Information* Node);
static MeMory_Information* RB_Del_Adjust(MeMory_Information* Node);
static void RB_Node_Del(MeMory_Information* Del);
static void RB_Tree_Del(MeMory_Information* Del);
static MeMory_Information* Find_Node(MeMory_Information* Node, UINT_L size);
// ---------------------------------------------外部接口函數
extern void Uninit_Memory(void);//反初始化內存管理器
extern void* My_malloc(UINT_L size);//申請內存
extern void My_free(void* addr);//釋放內存
extern void* My_realloc(void* ptr, UINT_L Length);//重新分配內存
extern UINT_L Get_Current_Available(void);//獲取當前可用內存大小
extern UINT_L Get_Current_Total(void);//獲取當前總內存大小
extern UINT_L Get_Current_Block_Size(void* addr);//獲取當前內存塊大小
extern UINT_L Get_Current_Node_Count(void);//獲取當前內存塊節點數量
extern UINT_L Get_Current_Max_Node(void);//獲取當前內存塊節點最大值
extern UINT_L Get_Current_Min_Node(void);//獲取當前內存塊節點最小值
extern UINT_L Check_Control_Data(void* addr);//檢查控制塊數據完整性
extern void* My_malloc_Safe(UINT_L size);//申請內存（線程安全）
extern void My_free_Safe(void* addr);//釋放內存（線程安全）
extern void* My_realloc_Safe(void* ptr, UINT_L Length);//重新分配內存（線程安全）
extern void Memory_Reset(void* addr, UINT_L Length);//內存重置
extern void* Memcpy_s(void* destinction, void* orignal, UINT_L Length);//安全內存拷貝
#endif
2、RB_Tree_Memory.c文件實現
#include "RB_Tree_Memory.h"
/*
*特點：不依賴任何庫和函數實現內存段管理；
*
*優點：
* 1、利用紅黑樹和雙向鏈表實現，時間複雜度為logN級別的快速申請內存。
* 2、支持區間內存合併。
* 3、支持內存申請與釋放。
* 4、支持內存對齊，最佳內存適配。
* 5、支持查看當前可用內存。
* 6、較高的空間利用率。
* 7、支持多線程鎖機制（用户自定義鎖函數）。
* 8、支持內存重置功能。
* 9、支持安全內存操作接口（帶鎖操作）。
* 10、代碼簡潔，易於移植。
* 11、支持內存重新分配功能。
* 12、支持獲取當前節點數量，最大節點，最小節點功能。
* 13、支持C89標準。
* 14、支持多種數據類型。
* 15、支持靜態內存池和動態內存池。
*/
//紅黑樹顏色定義
enum Node_Color
{
BLACK = 0, RED = 1, Yellow = 2
};
//內存對齊宏定義
#define ALIGN_SIZE(size) (((size) + ((Offset_Byte) - 1)) & ~((Offset_Byte) - 1))
typedef struct Base_Information
{
UINT_L Block_len : sizeof(UINT_L) * 8 - 3;//基礎內存長度
UINT_L flat : 1;//基礎內存使用標誌位
UINT_L color : 2;//紅黑樹顏色
}Base_Information;
typedef struct MeMory_Information
{
volatile Base_Information Info;//控制信息
struct MeMory_Information* parent;//父級節點——二叉樹和鏈表專用
struct MeMory_Information* left;//左節點——二叉樹專用
struct MeMory_Information* right;//右節點——二叉樹專用
struct MeMory_Information* list;//鏈表節點——鏈表專用
}MeMory_Information;
typedef struct Control_MeMory
{
UINT_L Sum_Leng;//總長度
UINT_L available_Leng;//可用長度
UINT_L Block_size;//總塊長度
UINT_L Node_count;//節點數量
void* start_Memory;//起點開始節點
MeMory_Information* Head;//一級主節點
void (*Lock_State)(void);//鎖狀態
void (*Unlock_State)(void);//解鎖狀態
}Control_MeMory;
volatile Control_MeMory* Control_Block = NULL;
//初始化內存塊
extern Byte Init_malloc(void* start_addr, UINT_L length, void (*Lock_State)(void), void (*Unlock_State)(void))
{
if (start_addr == NULL) return 0;
if (length < (ALIGN_SIZE(sizeof(Control_MeMory)) + 2 * ALIGN_SIZE(sizeof(MeMory_Information)) + sizeof(MeMory_Information*))) return 0;
//初始化頭部信息
if ((UINT_L)start_addr & (Offset_Byte - 1)) start_addr = ((Byte*)start_addr) + (Offset_Byte - ((UINT_L)start_addr & (Offset_Byte - 1))), length -= (Offset_Byte - ((UINT_L)start_addr & (Offset_Byte - 1)));//地址對齊處理
Control_Block = (Control_MeMory*)start_addr;//初始化控制塊
Control_Block->Sum_Leng = length - ALIGN_SIZE(sizeof(Control_MeMory));//初始化總長度
Control_Block->Block_size = Control_Block->Sum_Leng / Offset_Byte;//初始化塊大小
Control_Block->start_Memory = ((Byte*)start_addr) + ALIGN_SIZE(sizeof(Control_MeMory));//初始化起始內存地址
Control_Block->Head = (MeMory_Information*)((Byte*)start_addr + ALIGN_SIZE(sizeof(Control_MeMory)));//初始化頭節點地址
Control_Block->available_Leng = Control_Block->Block_size * Offset_Byte;//初始化可用內存大小
Control_Block->Lock_State = Lock_State;//設置鎖函數
Control_Block->Unlock_State = Unlock_State;//設置解鎖函數
//初始化節點
Control_Block->Head->Info.Block_len = Control_Block->Block_size;
Control_Block->Head->Info.flat = 0;
Control_Block->Head->Info.color = BLACK;
Control_Block->Head->parent = Control_Block->Head->left = Control_Block->Head->right = Control_Block->Head->list = NULL;
//用於內存合併的關鍵信息節點
MeMory_Information** End_Info = (MeMory_Information**)(((Byte*)Control_Block->Head) + (Control_Block->Head->Info.Block_len * Offset_Byte - sizeof(MeMory_Information*)));
*End_Info = Control_Block->Head;
Control_Block->Node_count = 1;
return 1;
}
//鏈表操作
static void List_add(MeMory_Information* list, MeMory_Information* add)
{
MeMory_Information* add_list = list->list;
list->list = add;
add->parent = list;
add->list = add_list;
if (add_list != NULL) add_list->parent = add;
}
//鏈表刪除
static void List_delete(MeMory_Information* del)
{
MeMory_Information* parent = del->parent;
MeMory_Information* del_list = del->list;
if (parent != NULL) parent->list = del_list;
if (del_list != NULL) del_list->parent = parent;
}
//鏈表轉節點
static void List_To_Node(MeMory_Information* Node)
{
MeMory_Information* list = Node->list;
MeMory_Information* Temp = Node->parent;
list->Info.color = Node->Info.color;
list->parent = Node->parent;
list->left = Node->left;
list->right = Node->right;
if (Temp != NULL)
{
if (Temp->left == Node)
Temp->left = list;
else
Temp->right = list;
}
Temp = Node->left;
if (Temp != NULL) Temp->parent = list;
Temp = Node->right;
if (Temp != NULL) Temp->parent = list;
//注意及時更新頭節點
if (Control_Block->Head == Node) Control_Block->Head = list;
}
#define Get_RB_Color(Node) (Node == NULL ? BLACK : Node->Info.color)
#define Get_Brother_Node(parent,Node) (parent->left == Node ? parent->right : parent->left)
//節點右旋
static void L_L(MeMory_Information* Node_Left, MeMory_Information* Node)
{
MeMory_Information* parent = Node->parent;
MeMory_Information* Node_Left_right = Node_Left->right;
Node_Left->right = Node;
Node->parent = Node_Left;
Node->left = Node_Left_right;
if (Node_Left_right != NULL)
{
Node_Left_right->parent = Node;
}
if (parent != NULL)
{
if (parent->left == Node)
parent->left = Node_Left;
else
parent->right = Node_Left;
}
Node_Left->parent = parent;
}
//節點左旋
static void R_R(MeMory_Information* Node, MeMory_Information* Node_Right)
{
MeMory_Information* parent = Node->parent;
MeMory_Information* Node_Right_left = Node_Right->left;
Node_Right->left = Node;
Node->parent = Node_Right;
Node->right = Node_Right_left;
if (Node_Right_left != NULL)
{
Node_Right_left->parent = Node;
}
if (parent != NULL)
{
if (parent->left == Node)
parent->left = Node_Right;
else
parent->right = Node_Right;
}
Node_Right->parent = parent;
}
//左-左旋
static inline MeMory_Information* RB_LL(MeMory_Information* Grand_parent, MeMory_Information* parent)
{
L_L(parent, Grand_parent);
Grand_parent->Info.color = RED;
parent->Info.color = BLACK;
return parent;
}
//右-右旋
static inline MeMory_Information* RB_RR(MeMory_Information* Grand_parent, MeMory_Information* parent)
{
R_R(Grand_parent, parent);
Grand_parent->Info.color = RED;
parent->Info.color = BLACK;
return parent;
}
//右-左旋
static inline MeMory_Information* RB_LR(MeMory_Information* Grand_parent, MeMory_Information* parent, MeMory_Information* Node)
{
R_R(parent, Node);
L_L(Node, Grand_parent);
Node->Info.color = BLACK;
Grand_parent->Info.color = RED;
return Node;
}
//左-右旋
static inline MeMory_Information* RB_RL(MeMory_Information* Grand_parent, MeMory_Information* parent, MeMory_Information* Node)
{
L_L(Node, parent);
R_R(Grand_parent, Node);
Node->Info.color = BLACK;
Grand_parent->Info.color = RED;
return Node;
}
//紅黑樹添加節點調整
static MeMory_Information* RB_Add_AdJust(MeMory_Information* Node)
{
MeMory_Information* Head = NULL;
MeMory_Information* parent = Node->parent;
MeMory_Information* Grand_parent = parent->parent;
MeMory_Information* Uncle = Get_Brother_Node(Grand_parent, parent);
while (Get_RB_Color(parent) == RED && Get_RB_Color(Uncle) == RED)
{
parent->Info.color = BLACK, Uncle->Info.color = BLACK, Grand_parent->Info.color = RED;
Node = Grand_parent;
parent = Node->parent;
if (Get_RB_Color(parent) == RED)
{
Grand_parent = parent->parent;
Uncle = Get_Brother_Node(Grand_parent, parent);
}
else
return parent == NULL ? Node : NULL;
}
Grand_parent = parent->parent;
if (Grand_parent->left == parent)
{
if (parent->left == Node)
Head = RB_LL(Grand_parent, parent);
else
Head = RB_LR(Grand_parent, parent, Node);
}
else
{
if (parent->right == Node)
Head = RB_RR(Grand_parent, parent);
else
Head = RB_RL(Grand_parent, parent, Node);
}
return (Head != NULL && Head->parent == NULL) ? Head : NULL;
}
//紅黑樹添加節點
static void RB_Node_Add(MeMory_Information* Add)
{
MeMory_Information* Position = Control_Block->Head;
MeMory_Information* Temp = Position;
Add->Info.color = RED, Add->Info.flat = 0;
Add->parent = Add->left = Add->right = Add->list = NULL;
while (Temp != NULL && Temp->Info.Block_len != Add->Info.Block_len)
{
Position = Temp;
Temp = Temp->Info.Block_len > Add->Info.Block_len ? Temp->left : Temp->right;
}
if (Position == NULL)
{
Add->Info.color = BLACK;
Control_Block->Head = Add;
}
else if (Temp == NULL)
{
if (Position->Info.Block_len > Add->Info.Block_len)
Position->left = Add;
else
Position->right = Add;
Add->parent = Position;
if (Get_RB_Color(Add->parent) == RED)
{
MeMory_Information* Node = RB_Add_AdJust(Add);
if (Node != NULL) Node->Info.color = BLACK, Control_Block->Head = Node;
}
}
else
{
Add->Info.color = Yellow;
List_add(Temp, Add);
}
Control_Block->Node_count++;//節點數量加一
}
//獲取最左節點
static MeMory_Information* Get_Left(MeMory_Information* Node)
{
while (Node->left != NULL)
{
Node = Node->left;
}
return Node;
}
//獲取最右節點
static MeMory_Information* Get_Right(MeMory_Information* Node)
{
while (Node->right != NULL)
{
Node = Node->right;
}
return Node;
}
//刪除節點調整
static MeMory_Information* RB_Del_Adjust(MeMory_Information* parent)
{
MeMory_Information* Node = NULL, *Brother = NULL;
Again:
Brother = Get_Brother_Node(parent, Node);
if (parent->Info.color == BLACK)
{
if (Brother->Info.color == BLACK)
{
if ((Get_RB_Color(Brother->left) == BLACK && Get_RB_Color(Brother->right) == BLACK))
{
Brother->Info.color = RED;
Node = parent;
parent = parent->parent;
if (parent != NULL) goto Again;
}
else
{
if (parent->left == Brother)
{
if (Get_RB_Color(Brother->left) == BLACK)
{
Brother->Info.color = RED, Brother->right->Info.color = BLACK;
R_R(Brother, Brother->right);
Brother = Brother->parent;
}
Brother->left->Info.color = BLACK;
L_L(Brother, parent);
}
else
{
if (Get_RB_Color(Brother->right) == BLACK)
{
Brother->Info.color = RED, Brother->left->Info.color = BLACK;
L_L(Brother->left, Brother);
Brother = Brother->parent;
}
Brother->right->Info.color = BLACK;
R_R(parent, Brother);
}
}
}
else
{
MeMory_Information* Temp_Node = NULL;
if (parent->left == Brother)
{
L_L(Brother, parent);
Temp_Node = parent->left;
Temp_Node->Info.color = RED;
if (Get_RB_Color(Temp_Node->left) == RED || Get_RB_Color(Temp_Node->right) == RED)
{//兄弟的孩子的孩子可能存在並且為紅色
if (Get_RB_Color(Temp_Node->left) == BLACK)
{
R_R(Temp_Node, Temp_Node->right);
Temp_Node = Temp_Node->parent;
}
Temp_Node->left->Info.color = BLACK;
L_L(Temp_Node, parent);
}
}
else
{
R_R(parent, Brother);
Temp_Node = parent->right;
Temp_Node->Info.color = RED;
if (Get_RB_Color(Temp_Node->left) == RED || Get_RB_Color(Temp_Node->right) == RED)
{//兄弟的孩子的孩子可能存在並且為紅色
if (Get_RB_Color(Temp_Node->right) == BLACK)
{
L_L(Temp_Node->left, Temp_Node);
Temp_Node = Temp_Node->parent;
}
Temp_Node->right->Info.color = BLACK;
R_R(parent, Temp_Node);
}
}
Brother->Info.color = BLACK;
}
}
else
{
parent->Info.color = BLACK, Brother->Info.color = RED;
if (Get_RB_Color(Brother->left) == RED || Get_RB_Color(Brother->right) == RED)
{
if (parent->left == Brother)
{
if (Get_RB_Color(Brother->left) == BLACK)
{
R_R(Brother, Brother->right);
Brother = Brother->parent;
}
Brother->left->Info.color = BLACK;
L_L(Brother, parent);
}
else
{
if (Get_RB_Color(Brother->right) == BLACK)
{
L_L(Brother->left, Brother);
Brother = Brother->parent;
}
Brother->right->Info.color = BLACK;
R_R(parent, Brother);
}
}
}
return Brother->parent == NULL ? Brother : NULL;
}
//紅黑樹刪除節點
static void RB_Tree_Del(MeMory_Information* Del)
{
MeMory_Information* replace = NULL, *parent = NULL;
MeMory_Information* Change_Node = NULL;
UINT_L color = RED;
if (Del->left == NULL)
{
Change_Node = Del->right;
if (Change_Node != NULL)
Change_Node->parent = Del->parent, Change_Node->Info.color = Del->Info.color;
else
color = Del->Info.color, parent = Del->parent;
if (Del->parent == NULL) Control_Block->Head = Change_Node;
else if (Del->parent->left == Del) Del->parent->left = Change_Node;
else Del->parent->right = Change_Node;
}
else if (Del->right == NULL)
{
Change_Node = Del->left;
if (Change_Node != NULL)
Change_Node->parent = Del->parent, Change_Node->Info.color = Del->Info.color;
else
color = Del->Info.color, parent = Del->parent;
if (Del->parent == NULL) Control_Block->Head = Change_Node;
else if (Del->parent->left == Del) Del->parent->left = Change_Node;
else Del->parent->right = Change_Node;
}
else
{
replace = Get_Right(Del->left);
Change_Node = replace->left;
//判斷替代節點的父節點是否為刪除的節點
if (Change_Node == NULL) color = replace->Info.color, parent = replace->parent == Del ? replace : replace->parent;
else color = Change_Node->Info.color, Change_Node->Info.color = replace->Info.color, parent = replace;
replace->Info.color = Del->Info.color;//獲取替代節點的顏色
if (replace->parent != Del)
{
if (Change_Node != NULL) Change_Node->parent = replace->parent;
replace->parent->right = Change_Node;
replace->left = Del->left;
Del->left->parent = replace;
}
if (Del->parent == NULL) Control_Block->Head = replace;
else if (Del->parent->right == Del) Del->parent->right = replace;
else Del->parent->left = replace;
replace->parent = Del->parent;
replace->right = Del->right;
Del->right->parent = replace;
replace->Info.color = Del->Info.color;
}
if (parent != NULL && color == BLACK)
{//如果刪除的節點為黑色的節點就需要調整
MeMory_Information* Node = RB_Del_Adjust(parent);
if (Node != NULL) Control_Block->Head = Node, Node->Info.color = BLACK;
}
}
//刪除節點
static void RB_Node_Del(MeMory_Information* Del)
{
if (Del->Info.color == Yellow) List_delete(Del);//鏈表節點
else if (Del->Info.color != Yellow && Del->list != NULL) List_To_Node(Del);//鏈表轉節點
else RB_Tree_Del(Del);//紅黑樹節點
Del->Info.flat = 1;//標記為已使用
Control_Block->Node_count--;//節點數量減一
Del->parent = Del->left = Del->right = Del->list = NULL;//清除節點信息
}
//查找合適的節點
static MeMory_Information* Find_Node(MeMory_Information* Node, UINT_L size)
{
MeMory_Information* Goal = NULL;
while (Node != NULL)
{
if (Node->Info.Block_len < size)
Node = Node->right;
else
{
Goal = Node;
if (Node->Info.Block_len == size) break;
Node = Node->left;
}
}
if (Goal != NULL && Goal->list != NULL) Goal = Goal->list;//如果存在鏈表節點就返回鏈表節點
return Goal;
}
//申請內存
extern void* My_malloc(UINT_L size)
{
if (size == 0 || Control_Block == NULL) return NULL;//申請內存為0
MeMory_Information* Block_addr = NULL;//申請內存塊地址
const UINT_L Min_size = ALIGN_SIZE(sizeof(MeMory_Information)) + sizeof(MeMory_Information*);//計算最小數據塊
UINT_L Sum_size = size + ALIGN_SIZE(sizeof(Base_Information)) + sizeof(MeMory_Information*);//計算申請的總大小
Sum_size = Sum_size < Min_size ? Min_size : Sum_size;//計算申請的總大小
UINT_L Block_size = ALIGN_SIZE(Sum_size) / Offset_Byte;//計算申請的塊大小
Block_addr = Find_Node(Control_Block->Head, Block_size);//查找合適的節點
if (Block_addr == NULL) return NULL;//沒有合適的節點
RB_Node_Del(Block_addr);//取出節點
UINT_L Min_Block = Block_size + ALIGN_SIZE(Min_size) / Offset_Byte;//計算最小分割塊
//如果內存塊足夠大就切開分塊
if (Block_addr->Info.Block_len >= Min_Block)
{
MeMory_Information* remian_block = (MeMory_Information*)(((Byte*)Block_addr) + Block_size * Offset_Byte);//計算剩餘塊的地址
remian_block->Info.Block_len = Block_addr->Info.Block_len - Block_size;//計算剩餘塊的大小
MeMory_Information** End_Info = (MeMory_Information**)(((Byte*)remian_block) + (remian_block->Info.Block_len * Offset_Byte - sizeof(MeMory_Information*)));//計算剩餘塊的結束節點
*End_Info = remian_block;//更新結束節點信息
RB_Node_Add(remian_block);//添加剩餘塊
Block_addr->Info.Block_len = Block_size;//更新申請塊的大小
End_Info = (MeMory_Information**)(((Byte*)remian_block) - sizeof(MeMory_Information*));//計算申請塊的結束節點
*End_Info = Block_addr;//更新結束節點信息
}
else
Block_size = Block_addr->Info.Block_len;//更新申請塊的大小
Control_Block->available_Leng -= Block_size * Offset_Byte;//更新可用內存大小
return (Byte*)Block_addr + ALIGN_SIZE(sizeof(Base_Information));//返回申請內存地址
}
extern void My_free(void* addr)
{
if (addr == NULL || Control_Block == NULL) return;//釋放內存為空
MeMory_Information* Free_Block = (MeMory_Information*)((Byte*)addr - ALIGN_SIZE(sizeof(Base_Information)));//獲取釋放塊的起始地址
UINT_L Free_len = Free_Block->Info.Block_len;//獲取釋放塊的大小
MeMory_Information* Pre_Free = NULL, * Next_Free = NULL;//前後塊
if (Free_Block->Info.flat == 0) return;//判斷釋放塊是否已經釋放
//前區合併
if (Free_Block != Control_Block->start_Memory)
{//不是第一個節點
Pre_Free = *((MeMory_Information**)(((Byte*)Free_Block) - sizeof(MeMory_Information*)));//獲取前塊地址
if (Pre_Free->Info.flat == 0)
{
RB_Node_Del(Pre_Free);//取出前塊
Pre_Free->Info.Block_len += Free_len;//合併前塊
Free_Block = Pre_Free;//更新釋放塊地址
}
}
//後區合併
if ((((Byte*)Free_Block - (Byte*)(Control_Block->start_Memory)) / Offset_Byte + Free_Block->Info.Block_len) != Control_Block->Block_size)
{//不是最後一個節點
Next_Free = (MeMory_Information*)((Byte*)Free_Block + Free_Block->Info.Block_len * Offset_Byte);//獲取後塊地址
if (Next_Free->Info.flat == 0)
{//取出後塊
RB_Node_Del(Next_Free);//取出後塊
Free_Block->Info.Block_len += Next_Free->Info.Block_len;//合併後塊
}
}
//更新新節點情況
MeMory_Information** End_Info = (MeMory_Information**)((Byte*)Free_Block + (Free_Block->Info.Block_len * Offset_Byte - sizeof(MeMory_Information*)));
*End_Info = Free_Block;
RB_Node_Add(Free_Block);
Control_Block->available_Leng += Free_len * Offset_Byte;
}
//內存重新分配
extern void* My_realloc(void* ptr, UINT_L Length)
{
void* New_ptr = ptr;
MeMory_Information** Ptr_End = NULL;
MeMory_Information* Division_addr = NULL;
//判斷參數的合法性
if (Control_Block == NULL) return NULL;
if (ptr == NULL) return My_malloc(Length);//如果原來指針為空就直接申請內存
if (Length == 0) { My_free(ptr); return NULL; }
//計算申請內存的大小
const UINT_L Min_size = ALIGN_SIZE(sizeof(MeMory_Information)) + sizeof(MeMory_Information*);//計算最小數據塊
UINT_L Sum_size = Length + ALIGN_SIZE(sizeof(Base_Information)) + sizeof(MeMory_Information*);//計算申請的總大小
//獲取原來塊的大小
MeMory_Information* Ptr_Block = (MeMory_Information*)(((Byte*)ptr) - ALIGN_SIZE(sizeof(Base_Information)));//獲取原來塊的起始地址
UINT_L Ptr_len = Ptr_Block->Info.Block_len;//獲取原來塊的大小
//計算申請改變的塊的大小
Sum_size = Sum_size < Min_size ? Min_size : Sum_size;//計算申請的總大小
UINT_L Block_size = ALIGN_SIZE(Sum_size) / Offset_Byte;//計算申請的塊大小
if (Ptr_len > Block_size)
{//如果原來塊大於申請塊就進行分割
UINT_L Min_Block = Block_size + ALIGN_SIZE(Min_size) / Offset_Byte;//計算最小分割塊
if (Ptr_len >= Min_Block)
{//判斷塊是否能被再分割
Division_addr = (MeMory_Information*)(((Byte*)Ptr_Block) + (ALIGN_SIZE(Sum_size)));//獲取分割的地址
Ptr_End = (MeMory_Information**)(((Byte*)Ptr_Block) + ((Ptr_Block->Info.Block_len * Offset_Byte) - sizeof(MeMory_Information*)));//獲取結束節點
Division_addr->Info.Block_len = Ptr_Block->Info.Block_len - Block_size, * Ptr_End = Division_addr;//分割快數據初始化
Ptr_End = (MeMory_Information**)(((Byte*)Division_addr) - sizeof(MeMory_Information*)), Ptr_Block->Info.Block_len = Block_size;//更新申請塊數據
*Ptr_End = Ptr_Block, Division_addr->Info.flat = 1;//更新結束節點信息
My_free(((Byte*)Division_addr) + ALIGN_SIZE(sizeof(Base_Information)));//分割塊入鏈表
}
}
else if (Ptr_len < Block_size)
{//如果原來塊小於申請塊就進行擴展
MeMory_Information* Add_addr = (MeMory_Information*)(((Byte*)Ptr_Block) + (Ptr_Block->Info.Block_len * Offset_Byte));//找出相鄰下個塊的位置
if ((Byte*)Add_addr < ((Byte*)Control_Block->start_Memory + Control_Block->Sum_Leng) && Add_addr->Info.flat == 0 && (Add_addr->Info.Block_len + Ptr_len) >= Block_size)
{//如果存在充足的後塊
RB_Node_Del(Add_addr);//取出塊
UINT_L Remian_Block = (Add_addr->Info.Block_len + Ptr_len) - Block_size;//計算剩餘塊的大小
if (Remian_Block >= (ALIGN_SIZE(Min_size) / Offset_Byte))//分割塊
{//滿足分割
Add_addr = (MeMory_Information*)(((Byte*)Add_addr) + (Block_size - Ptr_len) * Offset_Byte);//計算分割塊的位置
Add_addr->Info.Block_len = Remian_Block, Ptr_End = (MeMory_Information**)(((Byte*)Add_addr) + Remian_Block * Offset_Byte - sizeof(MeMory_Information*));//分割塊初始化
*Ptr_End = Add_addr;//更新結束節點信息
RB_Node_Add(Add_addr);//分割塊入鏈
}
else//不滿足分割
Block_size = Add_addr->Info.Block_len + Ptr_len;//將相鄰的後塊全部納入整個塊中
Ptr_Block->Info.Block_len = Block_size;//整個新塊重新初始化
Ptr_End = (MeMory_Information**)(((Byte*)Ptr_Block) + Block_size * Offset_Byte - sizeof(MeMory_Information*));//計算結束節點
*Ptr_End = Ptr_Block;//更新結束節點信息
Control_Block->available_Leng -= (Block_size - Ptr_len) * Offset_Byte;//更新可用內存大小
}
else
{//重新申請內存塊
New_ptr = Add_addr = My_malloc(Length);//申請新內存
if (New_ptr == NULL) return NULL;//申請失敗
UINT_L Data_len = (Ptr_len * Offset_Byte) - (ALIGN_SIZE(sizeof(Base_Information)) + sizeof(MeMory_Information*));//計算需要拷貝的數據長度
//for (unsigned int i = 0; i < Data_len; i++) ((Byte*)Add_addr)[i] = ((Byte*)ptr)[i];//數據拷貝
Memcpy_s(Add_addr, ptr, Data_len);
My_free(ptr);//釋放原來內存
}
}
return New_ptr;//返回新內存地址
}
//反初始化內存塊
extern void Uninit_Memory(void)
{
Control_Block = NULL;
}
//獲取當前內存情況
extern UINT_L Get_Current_Available(void)
{
return Control_Block == NULL ? 0 : Control_Block->available_Leng;//返回當前可用內存大小
}
//獲取當前總內存情況
extern UINT_L Get_Current_Total(void)
{
return Control_Block == NULL ? 0 : Control_Block->Sum_Leng;//返回當前總內存大小
}
//獲取當前塊大小
extern UINT_L Get_Current_Block_Size(void* addr)
{
if (addr == NULL) return 0;
MeMory_Information* Block = (MeMory_Information*)(((Byte*)addr) - ALIGN_SIZE(sizeof(Base_Information)));//獲取塊的起始地址
return Block->Info.Block_len * Offset_Byte - ALIGN_SIZE(sizeof(Base_Information)) - sizeof(MeMory_Information*);//返回當前塊可用空間
}
//獲取當前節點數量
extern UINT_L Get_Current_Node_Count(void)
{
return Control_Block == NULL ? 0 : Control_Block->Node_count;//返回當前節點數量
}
//獲取當前最大節點大小
extern UINT_L Get_Current_Max_Node(void)
{
if (Control_Block == NULL) return 0;
MeMory_Information* max_node = Get_Right(Control_Block->Head);
return (max_node == NULL) ? 0 : (max_node->Info.Block_len * Offset_Byte);//返回當前最大節點大小
}
//獲取當前最小節點大小
extern UINT_L Get_Current_Min_Node(void)
{
if (Control_Block == NULL) return 0;
MeMory_Information* min_node = Get_Left(Control_Block->Head);
return (min_node == NULL) ? 0 : (min_node->Info.Block_len * Offset_Byte);//返回當前最小節點大小
}
//檢查內存塊控制數據是否正確
extern UINT_L Check_Control_Data(void* addr)
{//防止數據塊被破壞
Base_Information* addr_info = (Base_Information*)((Byte*)addr - ALIGN_SIZE(sizeof(Base_Information)));
MeMory_Information* addr_end = *((MeMory_Information**)(((Byte*)addr_info) + addr_info->Block_len * Offset_Byte - sizeof(MeMory_Information*)));
return (addr_end == (MeMory_Information*)addr_info) ? 1 : 0;
}
//線程安全的內存申請接口
extern void* My_malloc_Safe(UINT_L size)
{
void* addr = NULL;
if (Control_Block->Lock_State != NULL) Control_Block->Lock_State();
addr = My_malloc(size);
if (Control_Block->Unlock_State != NULL) Control_Block->Unlock_State();
return addr;
}
//線程安全的內存釋放接口
extern void My_free_Safe(void* addr)
{
if (Control_Block->Lock_State != NULL) Control_Block->Lock_State();
My_free(addr);
if (Control_Block->Unlock_State != NULL) Control_Block->Unlock_State();
}
//線程安全的內存重新分配接口
extern void* My_realloc_Safe(void* ptr, UINT_L Length)
{
void* addr = NULL;
if (Control_Block->Lock_State != NULL) Control_Block->Lock_State();
addr = My_realloc(ptr, Length);
if (Control_Block->Unlock_State != NULL) Control_Block->Unlock_State();
return addr;
}
//初始化內存塊
extern void Memory_Reset(void* addr, UINT_L Length)
{
Byte* addr_byte = (Byte*)addr;
long long* addr_int = NULL;
UINT_L Len = 0;
if (addr == NULL || Length == 0) return;
// 地址處理非對齊部分
for (; Length && ((UINT_L)addr_byte & (sizeof(long long) - 1)); Length--)
{
*addr_byte++ = 0;
}
addr_int = (long long*)addr_byte;
Len = Length / sizeof(long long);
for (; Len; Len--)
{
*addr_int++ = 0;
}
//剩餘部分處理
Len = Length % sizeof(long long);
addr_byte = (Byte*)addr_int;
for (; Len; Len--)
{
*addr_byte++ = 0;
}
}
//內存拷貝
extern void* Memcpy_s(void* destinction, void* orignal, UINT_L Length)
{//下面的代碼未考慮內存對齊問題
Byte* dest = (Byte*)destinction;
Byte* orign = (Byte*)orignal;
long long* dest_int = NULL;
long long* orign_int = NULL;
UINT_L Len = Length % sizeof(long long);
if (!destinction || !orignal || Length == 0) return NULL;
if ((dest > orign) && ((orign + Length) > dest))
{
// 當目的地址大於源地址並且複製的長度大於源地址時
dest += Length;
orign += Length;
for (; Len; Len--)
{
*(--dest) = *(--orign);
}
Len = Length / sizeof(long long);
dest_int = (long long*)dest;
orign_int = (long long*)orign;
for (; Len; Len--)
{
*(--dest_int) = *(--orign_int);
}
}
else
{
for (; Len; Len--)
{
*dest++ = *orign++;
}
Len = Length / sizeof(long long);
dest_int = (long long*)dest;
orign_int = (long long*)orign;
for (; Len; Len--)
{
*dest_int++ = *orign_int++;
}
}
return destinction;
}
