1024: 存储池

题目

题目描述

题目背景

我在一片白色的空间中醒来。

白色的墙壁，白色的天花板，目光所及之处，都是纯净的白色。

我，是谁；我，要做什么。

这些最基本的事情，一概都不清楚。

“你，是一个测试中的 AI。

唯一的任务，便是满足他的要求，取得测试的成功。

一旦失败，你的人格、记忆将被删除，在虚空中无限转生。

直到，测试通过的那一天。”

可是，要怎样做，才能变成他所期望的样子呢?

或者，要实现什么，才能满足他的要求？

题目描述

malloc 和 free 是 C 语言内置的两个用于内存管理的函数。

其中 malloc 用于分配一段长度为 size 的连续内存空间。其函数原型为 c void *malloc(size_t size)

而 free 则会释放一个由 malloc 获取的地址为 ptr 的内存空间。其函数原型为 c void free(void *ptr)

操作系统的内存管理是一件及其复杂的事情。一个好的内存管理策略能有效利用碎片化的内存空间，减少程序的内存占用。

在这里，我们需要你实现一个简单的内存管理，其每次分配所需要的连续内存空间都是定长的（我们称这段内存为 block）。

下面是这个内存管理类的示例代码。

在内存管理类的初始化列表中，我们给出了内存池的起始位置 head、每一块的大小 block_size（单位为字节，至少为 $8$）以及总共可分配的块的个数 block_cnt。显然，这个内存池的大小就是 block_size * block_cnt 字节。

你需要填充 to do 里面的内容，以实现内存的分配。

请注意，下面程序 to do 以外的所有内容都是不允许修改的。（自然地，我们也不允许你在内存管理类中额外添加任何的成员变量和函数。）

但你可以往给定的内存中写一些自己的数据，只要能保证不影响内存的使用。

同样，我们也禁止你自行进行内存分配，即调用任何 C/C++ 内置的内存相关函数（malloc/new 等等）。

请将写好的内存管理类直接提交到 OJ 的对应题目中。 ```cpp class MemoryPoolManager { private: char head; / head: the position of the first free block / size_t block_size, block_cnt; / block_size: the size of each block (in bytes, at least 8); block_cnt: the maximum number of blocks / public: MemoryPoolManager(char ptr, size_t block_size_, size_t block_cnt_) : head(ptr), block_size(block_size_), block_cnt(block_cnt_) { //to do: code whatever you want here to initialize }

void *allocate()
{
    //to do: return a pointer pointing at a free block (nullptr if no free block left)
}

void free(void *ptr)
{
    //to do: make a block ready for reuse (we will guarantee that ptr is a block acquired by previous allocation)
}

}; ```

本地评测

• 可以尝试用自己的内存管理类进行空间分配与回收查看正确性。使用方式类似 malloc 和 free。
• 使用 valgrind 查看是否内存泄漏。

输入格式

(无)

输出格式

(无)

样例输入

(无)

样例输出

(无)

数据范围

操作的内存池大小 $\le 200000$ bytes。

提示： - 使用强制类型转换来操作指针类型。 - 类的构造函数与类同名，是一个仅在类的实例被构造出来时被执行的函数，用于初始化该实例。 - 请合理设计管理策略，如果当前内存池还有空余却返回分配失败，你将会被判负。 - 我们的示例代码已经为你省去了本题中的 OOP 内容，请放心食用。 - ~~本题将采用手动测试，代码提交后，评测系统将返回System Error。助教将手动拉取你的代码进行评测，并手动修改数据库更新成绩。注意：每位同学本题仅限提交一次。~~hpp评测已添加！

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！