用边界标识法实现内存回收的代码

内存回收是一个非常重要的话题，可以通过边界标识法来实现内存回收。

边界标识法的基本思想是，在分配内存时，为每个块添加前缀和后缀标记。前缀标记包含块大小和其他元数据，后缀标记包含块大小以及其他元数据。当程序需要释放内存时，它可以使用这些标记来找到相邻的内存块并将它们合并为一个更大的块。

下面是一个使用边界标识法进行内存回收的示例代码：

#include <stdlib.h>
#include <stdio.h>

typedef struct block_header {
    size_t size; // 块大小
    int free; // 空闲标志
    struct block_header* next; // 指向下一个块
} block_header;

#define BLOCK_SIZE sizeof(block_header) // 块头大小
#define MIN_BLOCK_SIZE 128 // 最小块大小
#define ALIGNMENT 8 // 对齐大小

void* heap_start; // 堆起始地址
block_header* free_list; // 空闲块链表

void* allocate_block(size_t size) {
    // 将请求的大小调整为对齐的大小
    size = (size + ALIGNMENT - 1) & ~(ALIGNMENT - 1);
    // 请求的大小必须大于等于最小块大小
    size = size < MIN_BLOCK_SIZE ? MIN_BLOCK_SIZE : size;
    block_header* block = free_list;
    while (block) {
        // 找到第一个足够大的空闲块
        if (block->free && block->size >= size) {
            // 将块分裂成两个块，一个用于分配，另一个用于剩余空间
            size_t remaining_size = block->size - size;
            if (remaining_size >= BLOCK_SIZE + MIN_BLOCK_SIZE) {
                block_header* remaining_block = (block_header*)((char*)block + BLOCK_SIZE + size);
                remaining_block->size = remaining_size - BLOCK_SIZE;
                remaining_block->free = 1;
                remaining_block->next = block->next;
                block->size = size;
                block->free = 0;
                block->next = remaining_block;
            } else {
                // 剩余空间不足以存储另一个块
                block->free = 0;
            }
            free_list = block->next;
            return (void*)(block + 1);
        }
        block = block->next;
    }
    // 没有足够大的空闲块，需要分配新块
    size_t block_size = size + BLOCK_SIZE;
    block = (block_header*)sbrk(block_size);
    if (block == (void*)-1) {
        // 内存分配失败
        return NULL;
    }
    block->size = size;
    block->free = 0;
    block->next = NULL;
    return (void*)(block + 1);
}

void free_block(void* ptr) {
    if (!ptr) {
        // 空指针
        return;
    }
    block_header* block = (block_header*)ptr - 1;
    block->free = 1;
    // 将相邻的空闲块合并为一个更大的块
    block_header* prev = NULL;
    block_header* next = free_list;
    while (next) {
        if (next > block) {
            break;
        }
        prev = next;
        next = next->next;
    }
    if (prev && (char*)prev + prev->size + BLOCK_SIZE == block) {
        // 合并前面的空闲块
        prev->size += BLOCK_SIZE + block->size;
        block = prev;
    } else {
        // 前面没有空闲块
        block->next = next;
        prev->next = block;
    }
    if (next && (char*)block + block->size + BLOCK_SIZE == next) {
        // 合并后面的空闲块
        block->size += BLOCK_SIZE + next->size;
        block->next = next->next;
    }
    free_list = block;
}

int main() {
    // 初始化堆起始地址
    heap_start = sbrk(0);
    free_list = (block_header*)heap_start;
    free_list->size = 0;
    free_list->free = 0;
    free_list->next = NULL;

    // 分配一些内存块
    void* ptr1 = allocate_block(64);
    void* ptr2 = allocate_block(128);
    void* ptr3 = allocate_block(256);
    void* ptr4 = allocate_block(512);

    // 释放一些内存块
    free_block(ptr2);
    free_block(ptr4);

    // 再次分配内存块
    void* ptr5 = allocate_block(64);
    void* ptr6 = allocate_block(512);

    // 输出分配的内存块地址
    printf("ptr1 = %p\n", ptr1);
    printf("ptr3 = %p\n", ptr3);
    printf("ptr5 = %p\n", ptr5);
    printf("ptr6 = %p\n", ptr6);

    return 0;
}

在上面的代码中，我们定义了一个结构体 `block_header`，用于表示内存块的头部信息。该结构体包含块大小、空闲标志以及指向下一个块的指针。我们还定义了一些常量，例如块头大小、最小块大小和对齐大小等。最后，我们定义了两个函数 `allocate_block` 和 `free_block`，用于分配和释放内存块。

在 `allocate_block` 函数中，我们首先将请求的大小调整为对齐的大小，并确保请求的大小至少为最小块大小。然后，我们遍历空闲块链表，找到第一个足够大的空闲块，并将其分裂成两个块，一个用于分配，另一个用于剩余空间。如果剩余空间不足以存储另一个块，则将其标记为空闲。如果没有足够大的空闲块，则需要分配新块。最后，我们将分配的块标记为非空闲，并返回块的地址。

在 `free_block` 函数中，我们首先将指针转换为块头指针，并将该块标记为空闲。然后，我们遍历空闲块链表，找到相邻的空闲块，并将它们合并为一个更大的块。如果前面或后面没有空闲块，则将该块插入到空闲块链表中。最后，我们将新的空闲块链表头部指针设置为合并后的块。

在主函数中，我们首先初始化堆起始地址和空闲块链表。然后，我们分配一些内存块，释放一些内存块，并再次分配内存块。最后，我们输出分配的内存块地址。

使用边界标识法实现内存回收是一个比较高效和常用的方法。但是需要注意的是，这种方法需要额外的内存空间来存储块头信息，因此会造成一定的内存浪费。此外，边界标识法也可能会出现内存碎片问题，需要定期进行碎片整理。