c-malloc指针标识

Question

所以我有这个任务来实现我自己的malloc和C中的free。这个问题是memory_free(void *ptr)函数的要求之一。如果指针无效，即memory_alloc(unsigned int size)尚未分配指针，则必须返回1，否则返回0。我只是想不出一种方法来做到这一点，否则绝对不会浪费时间。

所以我的内存结构是这样的：我有一个全局指针，指向数组的开头，我可以充当堆。每个内存块都有一个int头，用来告诉它的大小以及它是否空闲。

这是我现在的memory_free（void*ptr）函数，TYPE是typedef unsigned int:

int memory_free(void *ptr)
{
    void *head = ptr;
    if (head == NULL)
        return 1;
    head -= sizeof(TYPE);
    if (!((*(TYPE*) head) & 1 ))
        return 1;
    (*(TYPE*) head) &= ~0x1;
    return 0;
}

指针ptr指向用户块的第一个字节，这意味着如果我想读取头，我必须返回4个字节。检查指针有效性的一种解决方案是从一开始就遍历堆，看看我是否找到了有问题的头，但这并不节省时间。有人能告诉我更好的方法吗？

Answer 1

一个O（1）解决方案是使标头为8个字节，而不是4个字节；使用额外的四个字节来表示有效性。例如，它可以是您存储在其他四个字节中的内容的一个补码。所以你看一下标题，如果这些额外的字节包含的不是标题第一部分的补码，你就知道它不是一个有效的块。

Answer 2

我看到了两种可能的替代方案：

• 保留已分配的指针的链表：由memory_alloc填充，由memory_free消耗。通过这种方式，您可以仔细检查传递给memory_free的内容是否一致
• 链表可能很耗时：作为折衷方案，您可以只存储内存池的开始和结束地址，并确保传递给memory_free的指针处于正确的绑定中。它远没有那么精确和确定，但速度更快