33. 简易内存池

1、题目描述
● 请实现一个简易内存池,根据请求命令完成内存分配和释放。
● 内存池支持两种操作命令，REQUEST和RELEASE，其格式为：
● REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。
● RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。
注意：

内存池总大小为100字节。
内存池地址分配必须是连续内存，并优先从低地址分配。
内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放。
不会释放已申请的内存块的中间地址。
释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块。
2、输入描述
首行为整数 N , 表示操作命令的个数，取值范围：0 < N <= 100。
接下来的N行, 每行将给出一个操作命令，操作命令和参数之间用 “=”分割。

3、输出描述
请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error
释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。
用例：

输入
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10

输出
0
10
30
0

ps：
第一条，申请地址0~9的10个字节内存，返回首地址0
第二条，申请地址10~29的20字节内存，返回首地址10
第三条，释放首地址为0的内存申请，0~9地址内存被释放，变为空闲，释放成功，无需输出
第四条，申请20字节内存，09地址内存连续空间不足20字节，往后查找到3049地址，返回首地址30
第五条，申请10字节，0~9地址内存空间足够，返回首地址0
————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
                        
原文链接：https://blog.csdn.net/weixin_52914380/article/details/138459806

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.请实现一个简易内存池，根据请求命令完成内存分配和释放

2.内存池支持两种操作命令，REQUEST和RELEASE，其格式为：

REQUEST=请求的内存大小，表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error。

RELEASE=释放的内存首地址，表示释放掉之前分配的内存，释放成功无需输出，如果释放不存在的首地址则输出error。

3.注意：（1）内存池总大小为100字节。

（2）内存池地址分配必须是连续内存，并优先从低地址分配

（3）内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放

（4）不会释放已申请的内存块的中间地址

（5）释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其他内存块。

4.输入描述：首行为整数N，表示操作命令的个数，取值范围：N大于0小于等于100.

接下来的N行，每行将给出一个操作命令，操作命令和参数之间用“=”分割。

5.输出描述：请求分配指定大小内存时，如果分配成功，返回分配到的内存首地址；如果内存不足，或指定的大小为0，则输出error

释放掉之前分配的内存时，释放成功无需输出，如果释放不存在的首地址则输出error。

二、解题思路

1.内存池一共有两种命令，一种是REQUEST，后面跟请求分配的内存大小

一种是RELEASE后面跟要释放内存的首地址

2.首先我们引入标准输入输出库、标准库、字符串处理库定义内存池总大小为100字节

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MEMORY_POOL_SIZE 100

3.然后定义MemoryBlock结构体用来表示内存池中的内存块信息。其中startAddress记录内存块的起始地址，size表示内存块的大小（字节数），isAllocated用于标记该内存块是否已经被分配出去（1表示已分配，0表示空闲），next指针用于链接下一个内存块，形成一个链表结构，方便管理内存池中多个内存块的情况。

typede struct MemoryBlock {

int startAddress; // 内存块起始地址

int size; // 内存块大小

int isAllocated; // 内存块是否已分配

struct MemoryBlock *next; // 指向下一个内存块的指针

} MemoryBlock;

4.然后声明一个函数用于创建并初始化内存池，通过动态分配内存创建一个MemoryBlock结构体来表示整个内存池，将其起始地址设为0，大小设为定义好的MEMORY_POOL_SIZE（也就是100字节），标记为未分配状态（isAllocated设为0），并将next指针设为NULL，表示初始时只有这一个代表整个内存池的空闲内存块，最后返回这个表示内存池的结构体指针。

MemoryBlock* initMemoryPool() {

MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));

if(pool == NULL) {

perror("内存分配失败");

return NULL;

}

pool->startAddress = 0;

pool->size = MEMORY_POOL_SIZE;

pool->isAllocated = 0;

pool->next = NULL;

return pool;

}

5.声明一个函数用来查找空闲内存块，该函数接收内存池的头指针pool和请求分配的内存大小requestSize作为参数，通过遍历内存池链表（从内存池的头指针开始，沿着next指针逐个访问内存块），查找是否存在未分配（isAllocated为0）且大小足够（size大于等于requestSize）的空闲内存块，找到则返回该内存块的指针，若遍历完整个链表都没有找到符合条件的空闲内存块，就返回NULL。

MemoryBlock* findFreeBlock(MemoryBlock *pool, int requestSize) {

MemoryBlock *current = pool;

while(current != NULL) {

if(current->isAllocated == 0 && current->size >= requestSize) {

return current;

}

current = current->next;

}

return NULL;

}

6.声明一个内存分配函数用于实际分配内存，首先判断请求分配的内存大小是否为0，若是则输出error并返回-1表示分配失败。然后调用findFreeBlock函数在内存池中查找合适的空闲内存块，如果没找到（返回NULL），同样输出error并返回-1.若找到了空闲内存块，分两种情况处理：

如果找到的空闲内存块大小正好等于请求的大小，直接将该内存块的isAllocated标记为1，表示已分配，然后返回该内存块的起始地址。

如果空闲内存块大小大于请求的大小，需要将其拆分成两个内存块，一个用于分配（大小设为requestSize，标记为已分配），另一个保持空闲（大小为原空闲内存块大小减去请求的大小，标记为未分配），并通过调整链表指针将新的空闲内存块插入到链表中合适的位置，最后返回分配的内存块的起始地址。

int allocateMemory(MemoryBlock **pool, int requestSize) {

if(requestSize == 0) {

printf("error\n");

return -1;

}

MemoryBlock *freeBlock = findFreeBlock(*pool, requestSize);

if(freeBlock == NULL) {

printf("error\n");

return -1;

}

if(freeBlock->size == requestSize) {

freeBlock->isAllocated = 1;

} else {

MemoryBlock *newBlock = (MemoryBlock *)malloc(sizeof(MemoryBlock));

if(newBlock == NULL) {

perror("内存分配失败");

return -1;

}

newBlock->startAddress = freeBlock->startAddress + requestSize;

newBlock->size = freeBlock->size - requestSize;

newBlock->isAllocated = 0;

newBlock->next = freeBlock->next;

freeBlock->size = requestSize;

freeBlock->isAllocated = 1;

freeBlock->next = newBlock;

}

return freeBlock->startAddress;

}

7.然后是释放内存函数，用于释放指定首地址对应的内存块，通过遍历内存池链表来查找要释放的内存块（根据起始地址匹配），如果找到了对应的内存块且该内存块是已分配状态，则将其标记为未分配，并且和前后有可能存在的空闲内存块合并，

void releaseMemory(MemoryBlock **pool, int relaseAddress) {

MemoryBlock *prev = NULL;

MemoryBlock *current = *pool;

while(current != NULL) {

if(current->startAddress == releaseAddress) {

if(current->isAllocated == 0) {

printf("error\n");

return;

}

current->isAllocated = 0;

// 如果前面有空闲内存块我们尝试合并

if(prev != NULL && prev->isAllocated == 0) {

prev->size += current->size;

prev->next = current->next;

free(current);

current = prev;

}

// 如果后面有空闲内存块，我们尝试合并

if(current->next != NULL && current->next->isAllocated == 0) {

current->size += current->next->size;

current->next = current->next->next;

}

return;

}

prev = current;

current = current->next;

}

printf("error\n");

}

8.主函数首先定义一个整数int N;用于读取命令的个数

int main() {

int N;

scanf("%d", &N);

MemoryBlock *memoryPool = initMemoryPool();

for(int i = 0;i < N; i++) {

char command[20];

scanf("%s",command);

if(strncmp(command,"REQUEST", 7) == 0) {

int requestSize;

sscanf(command + 7, "=%d", &requestSize);

int address = allocateMemory(&memoryPool, requestSize);

if(address != -1) {

printf("%d\n", address);

}

}

else if(strncmp(command,"RELEASE", 7) == 0) {

int relaseAddress;

sscanf(command + 7, "=%d", &releaseAddress);

releaseMemory(&memoryPool, releaseAddress);

}

}

return 0;

}

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MEMORY_POOL_SIZE 100// 内存块结构体
typedef struct MemoryBlock {int startAddress;int size;bool isAllocated;struct MemoryBlock *next;
} MemoryBlock;// 初始化内存池
MemoryBlock* initMemoryBlock() {MemoryBlock *pool = (MemoryBlock *)malloc(sizeof(MemoryBlock));if(pool == NULL) {perror("内存分配失败");return NULL;}pool->startAddress = 0;pool->size = MEMORY_POOL_SIZE;pool->isAllocated = false;pool->next = NULL;return pool;
}// 寻找空闲内存池
MemoryBlock* findFreeBlock(MemoryBlock* pool, int requestSize) {MemoryBlock *current = pool;while(current != NULL) {if(current->isAllocated == false && current->size >= requestSize) {return current;}current = current->next;}return NULL;
}// 为空闲地址池分配内存
int allocateMemory(MemoryBlock** pool, int requestSize) {if(requestSize == 0) {printf("error\n");return -1;}MemoryBlock *freeBlock = findFreeBlock(*pool, requestSize);if(freeBlock == NULL) {printf("error\n");return -1;}if(freeBlock->size == requestSize) {freeBlock->isAllocated = true;} else {MemoryBlock *newBlock = (MemoryBlock*)malloc(sizeof(MemoryBlock));if(newBlock == NULL) {perror("内存分配失败");return -1;}newBlock->size = freeBlock->size - requestSize;newBlock->isAllocated = false;newBlock->startAddress = freeBlock->startAddress + requestSize;newBlock->next = freeBlock->next;freeBlock->isAllocated = true;freeBlock->size = requestSize;freeBlock->next = newBlock;}return freeBlock->startAddress;
}void releaseMemory(MemoryBlock** pool, int relaseAddress) {MemoryBlock* prev = NULL, *current = *pool;while(current != NULL) {if(current->startAddress == relaseAddress) {if(current->isAllocated == false) {printf("error\n");return;}current->isAllocated = false;if(prev!= NULL && prev->isAllocated == false) {prev->size += current->size;prev->next = current->next;free(current);current = prev;}if(current->next != NULL && current->next->isAllocated == 0) {current->size += current->next->size;current->next = current->next->next;}return;}prev = current;current = current->next;}printf("error\n");
}int main() {int N;scanf("%d", &N);MemoryBlock *memoryPool = initMemoryBlock();for(int i = 0; i < N; i++) {char command[20];int num;scanf("%s", command);char *temp;temp = strtok(command, "=");num = atoi(strtok(NULL, "="));//printf("%s=%d\n", temp, num);if(strcmp(temp,"REQUEST") == 0) {int address = allocateMemory(&memoryPool, num);if(address != -1) {printf("%d\n", address);}} else if(strcmp(temp, "RELEASE") == 0) {releaseMemory(&memoryPool, num);}}return 0;
}