最近,有人问我一个问题,要实现一个具有以下限制和初始条件的非常简单的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:
文档中的准则:
有关代码的某些准则:
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/