🆕 malloc 怎么是个函数啊

题目

不允许使用内置的 malloc 和 free，用 C 语言实现 mymalloc 和 myfree。

题解

Windows 实现

没错。你没说不能用 Windows 吧！

#include <windows.h>

void* mymalloc(size_t size) {
    return HeapAlloc(GetProcessHeap(), 0, size);
}

void myfree(void* ptr) {
    HeapFree(GetProcessHeap(), 0, ptr);
}

打我时下手轻点

Linux 实现

咳咳，不开玩笑了。

#include <unistd.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdlib.h>

int brk(void *addr);
void *sbrk(intptr_t increment);


typedef struct block block, *pblock;
struct block {
    pblock next;
    pblock prev;
    size_t size;
    size_t isFree;
    char* ptr;
    char data[];
};

pblock head = NULL, tail = NULL;

int fit(pblock b, size_t size) {
    return b->isFree && b->size >= size;
}

pblock find(size_t size) {
    pblock b = head;
    while (b && !fit(b, size)) {
        b = b->next;
    }
    return b;
}

pblock append(size_t size) {
    pblock b = sbrk(0);
    if (sbrk(sizeof(block) + size) == (void*)-1)
        return NULL;
    b->size = size;
    b->next = NULL;
    if (tail) {
        tail->next = b;
    } else {
        head = b;
    }
    b->prev = tail;
    b->isFree = false;
    b->ptr = b->data;
    return tail = b;
}

size_t align8(size_t size) {
    return ((size + 7) >> 3) << 3;
}

void* mymalloc(size_t size) {
    size = align8(size);
    pblock b = find(size);
    if (b == NULL) {
        b = append(size);
        if (b == NULL) return NULL;
    } else {
        b->isFree = false;
    }
    return b->ptr;
}

bool inRange(void* ptr) {
    return head < ptr && ptr < sbrk(0);
}

pblock blockOf(void* ptr) {
    return (pblock)((char*)ptr - sizeof(block));
}

bool isValid(void* ptr) {
    return head && inRange(ptr) && blockOf(ptr)->ptr == ptr;
}

void myfree(void* ptr) {
    if (isValid(ptr)) {
        pblock b = blockOf(ptr);
        b->isFree = true;
        if (b->next == NULL) {
            tail = b->prev;
            if (tail) {
                tail->next = NULL;
            } else {
                head = NULL;
            }
            brk(b);
        }
    }
}