c - malloc指针识别

Question

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

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

这是我现在的 memory_free(void *ptr) 函数，类型是 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指向user block的第一个字节，也就是说，如果我要读header，就得往回走4个字节。检查指针有效性的一种解决方案是从头开始遍历堆，看看我是否得到了有问题的 header ，但这不是时间效率。谁能告诉我更好的方法？

Answer 1

一个 O(1) 的解决方案是将 header 设为 8 个字节而不是 4 个字节；使用额外的四个字节来指示有效性。例如，它可以是您存储在其他四个字节中的内容的补码。因此，您查看 header ，如果这些额外字节包含 header 第一部分的补码以外的任何内容，您就知道它不是有效 block 。