一、概述

        为了实现单片机使用动态内存管理我利用红黑树和双向链表的高效内存管理方案（最佳适配策略）。该方案实现了完整的内存分配与释放功能，在时间和空间效率上表现优异，尤其适合嵌入式系统或其他需要自主内存管理的应用场景。通过融合红黑树和双向链表的优势，本方案不仅能确保内存操作的高效性，还能显著提升内存利用率并减少碎片化现象。采用自定义内存池的设计思路，该方案有效规避了传统内存分配器的性能瓶颈。

二、内存对齐要求

        在现代单片机系统中，大多数程序对内存的使用都有严格的对齐要求。这种对齐要求不仅可以提高内存访问的效率，还能避免由于不当对齐导致的性能下降，甚至出现错误。因此，对于从内存管理器中返回的内存块，其首地址通常需要满足对齐字节的整数倍要求。例如，如果对齐数为8字节，那么返回的内存地址应当是8的整数倍。

1. 内存对齐的基本概念
        内存对齐是指将数据存储在内存中的地址按特定字节数的整数倍进行对齐。大多数硬件平台要求内存地址的对齐，以确保内存访问的效率。例如，如果一个32位的整数类型要求4字节对齐，则该整数的存储地址必须是4的整数倍。若地址没有按4字节对齐，系统可能会花费更多的时间来访问内存，导致性能下降。

2. 内存对齐在内存管理中的应用
        在内存管理系统中，通常使用内存池来管理一块大内存区域。在内存池中分配内存时，为了满足对齐要求，我们需要确保分配的内存块的起始地址是按指定对齐字节（例如8字节、16字节等）进行对齐的。

为了解决这一问题，可以采取以下措施：

  • 将整个内存池划分成以对齐字节数（如8字节）为单位的内存块。这样，不管何时分配内存，返回的内存块的起始地址都将符合对齐要求。例如，若对齐数为8字节，内存池中的每个内存块的起始地址都将是8字节的倍数，从而满足对齐要求。

3. 解决方案实现细节
       为了确保内存分配的地址符合对齐要求，可以采用以下方法来进行内存块的划分：

  • 划分内存块：在初始化内存池时，我们可以将内存池划分为多个小块，每个内存块的大小是对齐数的倍数。以8字节为例，所有内存块的起始地址将是8的整数倍。这样，在分配内存时，不管请求的内存大小是多少，返回的内存地址都能满足8字节对齐的要求。

  • 调整分配策略：在分配内存时，如果请求的内存大小没有恰好是对齐数的倍数，则会向上调整分配的内存大小。例如，若请求的内存块大小为12字节，而对齐数为8字节，那么内存管理器将实际分配16字节的内存，并返回一个起始地址为8字节倍数的内存块。

  • 内存块对齐：通过采用内存池中的“对齐块”策略，即每次分配一个对齐后的内存块，可以确保返回的内存地址始终符合硬件要求的对齐标准。通过这种方式，内存管理器能够提供高效且符合系统要求的内存分配服务。

4. 实际应用场景
这种内存对齐的策略广泛应用于嵌入式系统、操作系统内核以及高性能计算应用中。在这些场景下，内存的高效使用至关重要，且内存对齐不仅能够提高数据访问效率，还能减少由于对齐不当导致的性能瓶颈。

例如，在嵌入式设备中，硬件的访问速度和内存带宽通常较为有限，因此通过合理的内存对齐可以确保系统在最小硬件资源的支持下高效运行。操作系统内核在管理内存时，也需要处理对齐问题，以确保内存分配不会影响系统的稳定性和响应速度。

三、方案实现思路

内存分配过程中的合法性检查与分配策略

在现代内存管理系统中，内存分配不仅要考虑性能，还必须保证内存的安全性和有效性。因此，每次内存分配操作前，都需要进行一系列检查和计算，确保分配的内存符合要求，并能够有效利用系统资源。本文将详细介绍内存分配过程中的合法性检查、内存块计算、红黑树查找、链表节点管理以及内存裁剪的策略。

1. 内存分配前的合法性检查

每次进行内存分配时，首先需要检查传入的参数是否合法。包括但不限于以下几点：

  • 检查请求的内存大小是否为正值。

  • 检查请求的内存是否符合对齐要求（例如8字节、16字节对齐）。

  • 检查系统内存池中是否有足够的空间满足分配需求。

只有当所有参数都通过合法性验证后，才能继续进行下一步的内存计算和分配操作。

2. 内存块大小的计算

内存分配请求的处理不仅涉及内存块的大小计算，还需要考虑元数据部分的大小。每个内存块通常会附加一些元数据（例如内存块的大小、状态信息等），这些元数据占用一定的内存空间。因此，在计算实际分配的内存块大小时，需要将请求的内存大小与元数据的大小相加，从而确保内存块能够完整存储数据及其相关的元信息。

此处，ALIGN_SIZE 函数会确保分配的内存块大小满足内存对齐的要求：

#define Offset_Byte   8
#define ALIGN_SIZE(size) (((size) + ((Offset_Byte) - 1)) & ~((Offset_Byte) - 1))

3. 使用红黑树查找合适的内存块

内存管理器通常使用红黑树来存储空闲内存块的元数据。通过红黑树的高效查找特性，我们能够快速定位到合适的空闲内存块。接下来的步骤是：

  • 将计算出的内存块大小作为关键字，在红黑树中进行查找。

  • 如果红黑树中没有找到合适的内存块（即找不到与请求的内存大小匹配的节点），则说明系统无法满足当前的分配请求，返回 NULL，表示分配失败。

4. 判断链表节点的存在

如果红黑树中找到了一些可能适合的节点，我们接下来需要进一步判断：

  • 检查该节点是否包含其他已分配的链表节点。通常，空闲的内存块会形成一个链表，以便进行快速回收和重用。

  • 如果节点上存在其他链表节点（即该内存块已经部分被分配或使用），则直接返回链表节点，避免重复分配相同的内存区域。

  • 如果没有其他链表节点，则可以直接返回红黑树节点，表示该内存块可以被直接分配。

5. 内存块裁剪与红黑树更新

在实际分配内存时，如果找到的内存块大小大于请求的大小，我们可能会选择对内存块进行裁剪。内存裁剪的目的是将过大的内存块切分为适合请求的大小，同时将剩余的内存返回给红黑树，以便后续使用。裁剪的具体步骤如下：

  • 确认剩余部分的内存大小满足最小内存块要求。

  • 将剩余部分返回到红黑树中，并标记为一个新的空闲内存块，供后续分配使用。

四、数据结构说明

1、红黑树 + 链表结构（空闲块组织方式）

2、单个内存块结构（MeMory_Information）

五、方案对比

1、底层原理对比

项目 本方案实现 标准库 malloc
数据结构 红黑树管理空闲块（按大小排序）+ 链表管理同等大小块 ptmalloc 使用多级空闲链表（bins）+ 双向链表；部分区域采用 mmap（大块）
分配策略 最佳适配（Best Fit）

分级适配（First Fit / Best Fit 混合）+

分段策略
合并策略 相邻空闲块立即合并（内存回收时） 延迟合并（释放时合并或后台回收）
内存来源 固定区域（start_addr ~ start_addr+length） 从系统堆（brk/mmap）动态获取
线程安全 初始化传入自定义线程安全函数（嵌入式友好） 线程安全（有锁机制）
目标环境 嵌入式 / RTOS / 无操作系统环境 通用系统（Linux、Windows等）

2、理论复杂度对比

操作 本方案实现 标准库 malloc
分配（malloc） O(log n) （红黑树插入查找） O(1)~O(log n) （按块大小定位 bin）
释放（free） O(log n)（树插入 + 合并） O(1)~O(log n)
合并效率 高（立即合并） 中（延迟合并或后台）
碎片率 低（最佳适配） 中（分级适配 + 局部合并）

六、整体代码实现

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、支持C99标准。
* 14、支持多种数据类型。
* 15、支持静态内存池和动态内存池。
*/


//红黑树颜色定义
enum Node_Color
{
	BLACK = 0, RED = 1, Yellow = 2
};

//状态控制定义
enum Condition_Control_Options
{//状态控制定义,作用是在出错情况下可以知道是在哪个操作过程中出错的方便报错检查
	IDLE = 0x00, MALLOC_ING = 0x01, FREE_ING = 0x02, REALLOC_ING = 0x04
};

//内存对齐宏定义
#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;//节点数量
	UINT_L Condition_Control;//状态控制
	void* start_Memory;//起点开始节点
	void* Condition_Ptr;//状态指针
	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->Condition_Control = IDLE;//初始化状态控制
	Control_Block->Lock_State = Lock_State;//设置锁函数
	Control_Block->Unlock_State = Unlock_State;//设置解锁函数
	Control_Block->Condition_Ptr = NULL;//初始化状态指针

	//初始化节点
	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;
			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)
{
	if (addr == NULL || Control_Block == NULL || addr < Control_Block->start_Memory || addr > ((Control_Block->Block_size * Offset_Byte) + (Byte*)Control_Block->start_Memory)) return 0;//地址不合法
	Base_Information* addr_info = (Base_Information*)((Byte*)addr - ALIGN_SIZE(sizeof(Base_Information)));//获取块的控制信息地址
	if (((Byte*)addr_info + (addr_info->Block_len * Offset_Byte)) > ((Control_Block->Block_size * Offset_Byte) + (Byte*)Control_Block->start_Memory)) return 0;//结束地址不合法
	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;//返回检查结果：1正确    0错误
}
//线程安全的内存申请接口
extern void* My_malloc_Safe(UINT_L size)
{
	void* addr = NULL;
	if (Control_Block->Lock_State != NULL) Control_Block->Lock_State();//加锁
	Control_Block->Condition_Control = MALLOC_ING;//设置状态
	addr = My_malloc(size);//申请内存
	Control_Block->Condition_Control = IDLE;//设置状态为空闲
	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();//加锁
	Control_Block->Condition_Control = FREE_ING, Control_Block->Condition_Ptr = addr;//设置状态
	My_free(addr);//释放内存
	Control_Block->Condition_Control = IDLE, Control_Block->Condition_Ptr = NULL;//设置状态为空闲
	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();//加锁
	Control_Block->Condition_Control = REALLOC_ING, Control_Block->Condition_Ptr = ptr;//设置状态
	addr = My_realloc(ptr, Length);//重新分配内存
	Control_Block->Condition_Control = IDLE, Control_Block->Condition_Ptr = NULL;//设置状态为空闲
	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;
}

测试运行代码

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "RB_Tree_Memory.h"
 
// 自定义内存管理系统的测试
void test_custom_malloc()
{
    int** P = (int**)malloc(sizeof(int*) * 10000);
    if (P == NULL) return;
 
    // 进行1000 0000次申请操作
    printf("Test Custom Malloc 开始\n");
    clock_t t = clock();
 
    // 初始化指针数组
    for (int i = 0; i < 10000; i++)
        P[i] = NULL;
 
    for (int i = 0; i < 10000000; i++)
    {
        if (rand() % 3 == 0 && P[i % 10000] == NULL)
        {
            P[i % 10000] = (int*)My_malloc(rand());
        }
        else
        {
            My_free(P[i % 10000]);
            P[i % 10000] = NULL;
        }
    }
 
    printf("自制内存管理耗时 %lu ms\n", (clock() - t) * 1000 / CLOCKS_PER_SEC);
 
    // 指针数组归零
    for (int i = 0; i < 10000; i++)
    {
        My_free(P[i]);
        P[i] = NULL;
    }
 
    free(P);
    printf("Test Custom Malloc 完成\n\n");
}
 
// 标准库 malloc 的测试
void test_standard_malloc()
{
    int** P = (int**)malloc(sizeof(int*) * 10000);
    if (P == NULL) return;
 
    // 进行1000 0000次申请操作
    printf("Test Standard Malloc 开始\n");
    clock_t t = clock();
 
    // 初始化指针数组
    for (int i = 0; i < 10000; i++)
        P[i] = NULL;
 
    for (int i = 0; i < 10000000; i++)
    {
        if (rand() % 3 == 0 && P[i % 10000] == NULL)
        {
            P[i % 10000] = (int*)malloc(rand());
        }
        else
        {
            free(P[i % 10000]);
            P[i % 10000] = NULL;
        }
    }
 
    printf("标准库 malloc 耗时 %lu ms\n", (clock() - t) * 1000 / CLOCKS_PER_SEC);
 
    // 指针数组归零
    for (int i = 0; i < 10000; i++)
    {
        free(P[i]);
        P[i] = NULL;
    }
 
    free(P);
    printf("Test Standard Malloc 完成\n\n");
}
 
// 测试函数
int main(void)
{
    srand(time(NULL));
    Init_malloc(malloc(80000 * 10240), 80000 * 10240, NULL, NULL);
 
    printf("初始可用内存: %u Byte\n", Get_Current_Available());
 
    test_custom_malloc();
    printf("自定义内存管理系统测试后可用内存: %u Byte\n", Get_Current_Available());
 
    test_standard_malloc();
 
    system("pause");
    return 0;
}

# 算法 # c语言 # 链表 # stm32 # mcu # 单片机 # 数据结构
Logo
openvela

openvela 操作系统专为 AIoT 领域量身定制，以轻量化、标准兼容、安全性和高度可扩展性为核心特点。openvela 以其卓越的技术优势，已成为众多物联网设备和 AI 硬件的技术首选，涵盖了智能手表、运动手环、智能音箱、耳机、智能家居设备以及机器人等多个领域。

更多推荐

cover

Arm Ethos‑U65：YOLOv8n 模型准备与 Vela 编译

avatar openvela
cover

开源新纪元：深度解析小米 MiMo Code 的技术架构与实战应用

avatar openvela

UniAD_v2 模型NPU适配

参考github网址：https://github.com/OpenDriveLab/UniAD/tree/v2.0参考readme：https://gitcode.com/Ascend/DrivingSDK/blob/master/model_examples/UniAD/README.md。

avatar openvela