C语言编程实现空闲表法

空闲表法是一种分配和回收内存的算法。其基本思想是维护一个空闲块链表，每次分配内存时从链表中取出一个空闲块，将其从链表中删除，并返回给程序使用；每次释放内存时将其插入到空闲块链表的表头。

下面是一个简单的C语言程序实现空闲表法：

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

#define MEM_SIZE 100

typedef struct node {
    int size;
    void *start;
    struct node *next;
} Node;

void *mem_start = NULL;  // 内存起始地址
Node *free_list = NULL;  // 空闲块链表

void init_mem() {
    mem_start = malloc(MEM_SIZE);  // 分配内存
    free_list = (Node *)mem_start;  // 空闲块链表头指针指向内存起始地址
    free_list->size = MEM_SIZE - sizeof(Node);  // 空闲块大小为可用内存大小
    free_list->start = mem_start + sizeof(Node);  // 空闲块起始地址为可用内存起始地址
    free_list->next = NULL;  // 空闲块链表只有一个节点
}

void *malloc_mem(int size) {
    Node *prev = NULL;
    Node *cur = free_list;
    while (cur != NULL) {  // 遍历空闲块链表
        if (cur->size >= size) {  // 找到合适大小的空闲块
            if (cur->size == size) {  // 空闲块大小刚好等于申请大小
                if (prev != NULL) {  // 不是第一个节点
                    prev->next = cur->next;
                } else {  // 是第一个节点
                    free_list = cur->next;
                }
            } else {  // 空闲块大小大于申请大小
                cur->size -= size;
                cur->start += size;
            }
            return cur->start;
        }
        prev = cur;
        cur = cur->next;
    }
    return NULL;  // 没有找到合适大小的空闲块
}

void free_mem(void *ptr, int size) {
    Node *cur = free_list;
    Node *prev = NULL;
    while (cur != NULL && cur->start < ptr) {  // 找到要释放的内存在空闲块链表中的位置
        prev = cur;
        cur = cur->next;
    }
    if (prev != NULL) {  // 不是第一个节点
        if (prev->start + prev->size == ptr) {  // 要释放的内存与前一个节点相邻
            prev->size += size;
            if (cur != NULL && ptr + size == cur->start) {  // 要释放的内存与后一个节点相邻
                prev->size += cur->size + sizeof(Node);
                prev->next = cur->next;
            }
        } else {  // 要释放的内存与前一个节点不相邻
            Node *new = (Node *)ptr;
            new->size = size;
            new->start = ptr;
            new->next = cur;
            prev->next = new;
            if (cur != NULL && ptr + size == cur->start) {  // 要释放的内存与后一个节点相邻
                new->size += cur->size + sizeof(Node);
                new->next = cur->next;
            }
        }
    } else {  // 是第一个节点
        if (cur != NULL && ptr + size == cur->start) {  // 要释放的内存与后一个节点相邻
            cur->start = ptr;
            cur->size += size;
        } else {  // 要释放的内存与后一个节点不相邻
            Node *new = (Node *)ptr;
            new->size = size;
            new->start = ptr;
            new->next = cur;
            free_list = new;
        }
    }
}

int main() {
    init_mem();  // 初始化内存
    void *p1 = malloc_mem(20);  // 分配内存
    printf("%p\n", p1);
    void *p2 = malloc_mem(30);
    printf("%p\n", p2);
    void *p3 = malloc_mem(50);
    printf("%p\n", p3);
    free_mem(p2, 30);  // 释放内存
    void *p4 = malloc_mem(40);  // 分配内存
    printf("%p\n", p4);
    free_mem(p1, 20);
    free_mem(p3, 50);
    free_mem(p4, 40);
    free(mem_start);  // 释放内存
    return 0;
}

在程序中，我们使用了一个结构体`Node`来表示空闲块链表中的每一个节点，其中`size`表示节点中可用内存的大小，`start`表示节点中可用内存的起始地址，`next`表示下一个节点的指针。

在`init_mem()`函数中，我们首先分配了一段大小为`MEM_SIZE`的内存，并将其起始地址赋给全局变量`mem_start`。然后我们将空闲块链表头指针`free_list`指向内存起始地址，并初始化空闲块链表中的唯一节点，即该节点的大小为可用内存大小，起始地址为可用内存起始地址，下一个节点为空。

在`malloc_mem(int size)`函数中，我们遍历空闲块链表，找到第一个大小大于等于申请大小的空闲块。如果找到了合适大小的空闲块，则根据申请大小和空闲块大小的关系分三种情况进行处理：空闲块大小刚好等于申请大小，则将该节点从链表中删除；空闲块大小大于申请大小，则将该节点的大小减去申请大小，起始地址向后移动申请大小，并返回该空闲块的起始地址。如果没有找到合适大小的空闲块，则返回`NULL`。

在`free_mem(void *ptr, int size)`函数中，我们首先找到要释放的内存在空闲块链表中的位置。然后根据要释放的内存与前一个节点和后一个节点的关系分三种情况进行处理：要释放的内存与前一个节点相邻，则将前一个节点的大小增加要释放的内存大小，并将要释放的内存插入到前一个节点中；要释放的内存与前一个节点不相邻，则将要释放的内存插入到空闲块链表中；要释放的内存与后一个节点相邻，则将要释放的内存与后一个节点合并成一个节点，并将该节点插入到空闲块链表中。

在`main()`函数中，我们首先调用`init_mem()`函数初始化内存。然后我们分别调用`malloc_mem(int size)`函数分配内存，并将分配得到的内存的起始地址打印出来。接着我们调用`free_mem(void *ptr, int size)`函数释放内存，并再次调用`malloc_mem(int size)`函数分配内存。最后我们依次释放所有内存，并调用`free()`函数释放分配的内存。