c - 显式空闲列表(动态内存分配)

我的作业需要一些帮助。我的工作是使用“只在空闲块中显式使用空闲列表”技术在C中创建/实现malloc/free函数。我已经研究了很多材料，但我仍然停留在某一点上，我不明白一些细节。所以我的工作是创建4个函数：initialize（）、allocate（）、free（）和check（）。我只能使用一个全局变量void *memory–这是我可以使用alloc（）分配内存的块。
所以我想用双链表来实现它，我创建了一个结构：

typedef struct memoryBlock{
    struct memoryBlock *prev,*next;
}memoryBlock;

以及标题的结构：

typedef struct header{
int size;
}header;

我在班上被建议为一个空闲内存块创建一个单独的结构，为一个分配的块创建另一个单独的结构。我的第一个想法是使用头中块大小的一位来区分空闲/分配的块-如果块被分配，则将其设置为1，如果块是空闲的，则将其设置为0。（我在隐式列表中看到了这种技术）。所以我的问题是：我需要为显式列表创建一个freeBlock和allocatedBlock结构，还是只使用其中的一个大小？
第二个问题是：块的页眉/页脚是否需要单独的结构？或者我可以在页眉/页脚中将块的大小写为*(int *)ptr = size;？我试图在initialize（）函数中使用此函数：

void initialize(void *ptr, int size){
memory = ptr;
*(int *)memory = size; //header
*((int *)memory + size) = size; //footer
}

请问这是对的吗？
非常感谢你的帮助。

最佳答案

我需要为显式列表[…]创建一个freeBlock和allocatedBlock结构吗？
我觉得这是个好主意。不要误解这个建议：你不需要两个不同的结构定义，只需要两个不同的列表。您可以通过两个指针来实现这一点，一个用于空闲块，另一个用于已分配块。
[…]我能用一下这个尺寸吗？
如果未使用，则只能使用一位大小。如果选择位0，则仅当分配偶数个内存字时才起作用。
是否需要为块的页眉/页脚使用单独的结构？
这取决于你的设计和算法。是否要创建页眉和页脚？
或者我可以在页眉/页脚中将块的大小写为*(int *)ptr = size;？
你可以这么做。但我会将给定的指针赋给指向正确结构的（临时）指针，然后将值赋给正确的位置。

void initialize(void *ptr, int size) {
    memory = ptr;
    header* h = memory;
    h->size = size;
}

附加观察：代替

typedef struct memoryBlock{
    struct memoryBlock *prev,*next;
}memoryBlock;

最好习惯这一点，它会帮你省下很多拔出来的头发：

typedef struct memoryBlock {
    struct memoryBlock *prev;
    struct memoryBlock *next;
} memoryBlock;

注意：由于指针的复杂性，请将编译器的警告级别提高到最大。阅读所有警告并消除其原因。

关于c - 显式空闲列表(动态内存分配)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58240162/