C语言如何分离空闲块

Question

翻译：my_malloc()函数查找大于或等于size + HEADER_SIZE的最小空闲块。如果空闲块小于size + HEADER_SIZE + MIN_CHUNK_SPLIT，分配整个块。否则，将其分割为两个块，将较低的块分配给请求，而将较高的块作为一个新的空闲块。如果有多个大小相同的块，则必须选择最接近堆开头的块来分配。
该函数返回一个指向数据块中第一个可用字节的指针，如下图所示
（问题描述：前边差不多都会，但是这个中间要求要分割空闲块，将空闲块分离成两块，前一块分配给请求，后一块作为一个新空闲块；这部分不知道怎么操作……不知道是直接移动要开辟的大小然后设置alloc还是说有什么可以直接用的代ma或者函数？感谢！）
我这个函数开头是截图最上边那个void开头
还请帮帮忙，感谢

Answer 1

根据你的上一个初始化heap的题目，代码有一些修改，初始化heap的那个题目的代码也贴在这里了，完整代码如下：

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

#define ALLOC (int)1
#define FREE (int)2

//这里的这个宏定义改成你自己的
#define MIN_CHUNK_SPLIT (uint32_t)100

#define uint32_t unsigned int
typedef unsigned char byte;

typedef struct header {
    uint32_t status; // the chunk's status --should be either ALLOC or FREE
    uint32_t size; // number of bytes,including header
    byte data[]; //这个变量是无法改变的，这么些会有问题，图片中说这个变量不关心，所以先不管他了
}header_type;

typedef struct heap_infomation {
    byte* heap_mem;
    uint32_t heap_size;  //number of bytes in heap_mem
    byte** free_list; //array of pointers to free chunks
    uint32_t free_capacity; //maximum number of chunks
    uint32_t n_free; //current number of free chunks
}heap_information_type;


static struct heap_infomation my_heap;

#define HEADER_SIZE (sizeof(struct header))


int init_heap(uint32_t size)
{
    if (size < 4096)
        size = 4096;
    else if (size % 4 != 0)
    {
        size = (size / 4 + 1) * 4;
    }
    my_heap.heap_mem = (byte*)malloc(size); //申请空间
    if (my_heap.heap_mem == 0)
        return -1;
    my_heap.heap_size = size;

    int k = size / HEADER_SIZE;
    my_heap.free_capacity = k;
    my_heap.n_free = k;

    my_heap.free_list = (byte**)malloc(k * sizeof(byte*)); //申请数组空间
    if (my_heap.free_list == 0)
        return -1;


    //初始时，只有1个空间，其余都是0
    for (int i = 1; i < k; i++)
    {
        my_heap.free_list[i] = 0;
    }
    //初始化第1块空间
    my_heap.free_list[0] = my_heap.heap_mem;
    header_type* tt = (header_type*)my_heap.free_list[0];
    tt->status = FREE;
    //tt->data = free_list[i]; //这个先不管了，结构体中使用的数组，无法给它赋值
    tt->size = size;

    return 1;
}


//my_malloc()函数查找大于或等于size + HEADER_SIZE的最小空闲块。如果空闲块小于size + HEADER_SIZE + MIN_CHUNK_SPLIT
void* my_malloc(uint32_t size)
{
    //已无可用空间
    if (my_heap.n_free <= 0)
        return 0;
    for (int i = 0; i < my_heap.free_capacity; i++)
    {
        if (my_heap.free_list[i] == 0) //这里是continue是因为，之前分配的空间可能会被释放，所以for循环需要遍历所有空闲块，不能直接return 0
            continue;
        header_type* tt = (header_type*)my_heap.free_list[i];
        if (tt->status == ALLOC)
            continue;
        //查找符合条件的空闲空间
        if (tt->size < size + HEADER_SIZE) //这里是continue是因为，之前分配的空间可能会被释放，所以for循环需要遍历所有空闲块，不能直接return 0
            continue;
        else if (tt->size < size + HEADER_SIZE + MIN_CHUNK_SPLIT)
        {
            tt->status = ALLOC;
            my_heap.n_free = 0; //增加这一句
            return (void*)my_heap.free_list[i];
        }
        else
        {
            if (i + 1 >= my_heap.free_capacity)
                return 0;
            //更新下一个空闲块的信息
            my_heap.free_list[i + 1] = my_heap.free_list[i] + size + HEADER_SIZE; //重置空闲块的首地址
            header_type* pp = (header_type*)my_heap.free_list[i + 1];
            pp->status = FREE; //设置空闲块的状态
            pp->size = tt->size - size - HEADER_SIZE; //设置空闲块的大小

            my_heap.n_free--; //空闲块的数量减1
            return (void*)my_heap.free_list[i]; //返回可分配的空间地址
        }
    }
    return 0; //找不到可用空间，返回0
}