c++ - 自定义malloc实现

最近，有人问我一个问题，要实现一个具有以下限制和初始条件的非常简单的malloc。

#define HEAP_SIZE 2048
int main()
{
    privateHeap = malloc(HEAP_SIZE + 256); //extra 256 bytes for heap metadata

    void* ptr = mymalloc( size_t(750) );

    myfree( ptr );
    return 0;

}

我需要使用提供的确切空间在此处实现mymalloc和myfree。 256个字节很好地映射到2048个位，如果分配了一个字节还是空闲的话，我可以存储一个位数组。但是，当我使用myfree进行ptr调用时，我无法知道开始分配了多少大小。我不能使用任何多余的位。

我似乎没有办法解决这个问题，但是我已经重申可以做到。有什么建议么 ？

编辑1:

对齐限制不存在。我以为我不会对齐任何东西。

有一个演示程序，它执行了一系列malloc并可以对其进行自由测试，并且它没有任何小的内存块。但这并不能保证任何事情。

编辑2:

文档中的准则:
有关代码的某些准则:

管理私有(private)堆中的堆元数据；不要在提供的私有(private)堆之外创建额外的链接列表；

设计mymalloc，myrealloc和myFree以适用于所有可能的输入。

myrealloc应该像C++库中的realloc一样执行以下操作:void* myrealloc( void* C, size_t newSize ):

如果newSize大于reallocThis中的块大小:

它应该首先尝试分配一个大小为newSize的块，以便新块的基本指针也为reallocThis；

如果没有可用空间来进行位置分配，则应在不同区域中分配请求大小的块；
然后应该复制上一个块中的内容。

如果函数未能分配请求的内存块，则返回NULL指针，并指向该内存块
通过参数reallocThis保持不变。

如果newSize较小，则realloc应缩小块的大小，并且应始终成功。

如果newSize为0，则应该像free一样工作。

如果reallocThis为NULL，则应像malloc一样工作。

如果reallocThis是已经释放的指针，则应该通过返回NULL

正常地失败
传递给已释放的指针时，

myFree不应崩溃。

最佳答案

您似乎将256字节的元数据视为一个位图，用于逐字节地跟踪空闲/正在使用中。

我认为以下只是一种可能的选择:

我首先将2048字节的堆视为每个2字节的1024个“块”。这为每个块提供2位信息。您可以将第一个视为表示该块是否正在使用，第二个视为表示后面的块是否与当前块属于同一逻辑块。

调用free函数时，可以使用传递的地址在位图中找到正确的起点。然后，您遍历将每个块都标记为空闲的位，直到到达第二个位设置为0的位，表示当前逻辑块的末尾(即，下一个2个字节的块不是当前逻辑块的一部分)。

[糟糕:刚刚注意到Ross Ridge在评论中已经提出了几乎相同的基本想法。]

关于c++ - 自定义malloc实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25414839/