C语言实现单片机上的malloc函数功能
声明： 本人的实力是废铁级别，这也是我在博客园第一次发表文章，如果内容存在错误请各位大佬能否在评论区指正一下本人万分感谢🙇。
一、概述
在常规单片机设备开发中一般很少用到动态内存管理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;
}
浙公网安备 33010602011771号