自制malloc

完善当中。。。。

sbrk()函数

sbrk 参数n是一个整数 n>0 当前位置向后移，相当于分配内存空间； n<0 当前位置向前移，相当于释放内存空间； n=0 当前位置移动0个字节(不动) 主要是为了返回当前位置 sbrk(0) :

当程序中第一次调用sbrk(0)时，系统并不会分配物理空间，只是返回一个未使用的虚拟内存地址，之后再分配空间时，系统会将分配的物理空间和此虚拟地址进行映射。 以后调用sbrk(0),仅仅是返回当前位置。

代码

• size_t 32位占4字节 64位占8字节

• (char *) 因为char是1字节，强转成char *方便计算找地址

typedef struct __metadata {
    size_t size; // 存储数据的大小
    size_t free; // 是否空闲
    struct __metadata *next; // 后继
    struct __metadata *prev; // 前驱
    void *begin; // 存储数据的起始地址
} MetaData, *pMetaData;

static pMetaData __memory_head = NULL;

void print_log(char *str) {
    printf("[%s:%d]: %s\n", __func__, __LINE__, str);
    fflush(stdout);
}

static void initMetaData(pMetaData p, size_t size, size_t free, pMetaData prev, pMetaData next) {
    p->size = size;
    p->free = free;
    p->prev = prev;
    p->next = next;
    p->begin = ((char *)p) + sizeof(MetaData);
}

// myrealloc 时拷贝数据
static void dataCopyTo(void *dest, void *src, size_t len) {
    size_t i;
    char *p1 = (char *)dest;
    char *p2 = (char *)src;
    for (i = 0; i < len; ++i) {
        p1[i] = p2[i];
    }
    return ;
}

void *mylloc(size_t sizes) {
    pMetaData p, q;
    size_t msize = sizes + sizeof(MetaData);
    if (__memory_head == NULL) {
        // 头为空 向内存申请空间
        p = sbrk(0);
        if (sbrk(msize) == (void *)-1) {
            return NULL;
        }
        initMetaData(p, sizes, 0, NULL, NULL);
        __memory_head = p;
    } else {
        // 搜索可以利用的空闲空间
        p = __memory_head;
        while (p) {
            if (p->free && p->size >= msize) {
                q = (pMetaData)(((char *)p->begin) + sizes);
                initMetaData(q, p->size - msize, 1, p, p->next);
                p->size = sizes;
                if (p->next != NULL) {
                    p->next->prev = q;
                }
                p->next = q;
                p->free = 0;
                break;
            } else if (p->free && p->size >= sizes) {
                p->free = 0;
                break;
            }
            if (p->next == NULL) break;
            p = p->next;
        }
        // 没搜索到重新申请
        if (p->next == NULL) {
            q = sbrk(0);
            if (sbrk(msize) == (void *)-1) {
                return NULL;
            }
            initMetaData(q, sizes, 0, p, NULL);
            p->next = q;
            p = q;
        }
    }
    return p->begin;
}

void myfree(void *p) {
    pMetaData q, k;
    q = (pMetaData)(((char *)p) - sizeof(MetaData));
    q->free = 1;
    // 向前合并
    if (q->prev && q->prev->free) {
        k = q->next;
        q = q->prev;
        q->size += q->next->size + sizeof(MetaData);
        q->next = k;
        if (k != NULL) {
            k->prev = q;
        }
    }
    // 向后合并
    if (q->next != NULL && q->next->free) {
        k = q->next->next;
        q->size += q->next->size + sizeof(MetaData);
        q->next = k;
        if (k != NULL) {
            k->prev = q;
        }
    }
    // 如果q指向的是最后一块则归还个系统
    size_t msize;
    if (q->next == NULL) {
        if (q->prev != NULL) {
            q->prev->next = NULL;
        } else {
            __memory_head = NULL;
        }
        msize = q->size + sizeof(MetaData);
        sbrk(-msize);
    }
}

void *mycalloc(size_t numitems, size_t size) {
    void *ret = mylloc(numitems * size);
    if (ret == NULL) return ret;
    char *p = (char *)ret;
    size_t i = numitems * size;
    while (i--) { // 初始化
        (*p) = 0;
        ++p;
    }
    return ret;
}

void *myrealloc(void *ptr, size_t size) {
    pMetaData p, q, k;
    p = (pMetaData)(((char *)ptr) - sizeof(MetaData));
    if (p->size >= size) return p->begin; // 需重开的size比之前小，直接返回
    // 如果是最后一块，直接向系统申请
    if (p->next == NULL) {
        if (sbrk(size - p->size) == (void *)-1) {
            return NULL;
        }
        p->size = size;
    }
    // 向后合并
    if (p->size < size && p->next && p->next->free) {
        if (p->size + p->next->size >= size) { 
            // 不需要记录必要节点信息的节点空间
            q = (pMetaData)(((char *)p->begin) + size);
            initMetaData(q, p->size + p->next->size - size, 1, p, p->next->next);
            if (p->next->next != NULL) {
                p->next->next->prev = q;
            }
            p->next = q;
            p->size = size;
        } else if (p->size + p->next->size + sizeof(MetaData) >= size) {
            // 需要记录必要节点信息的节点空间
            p->size = p->size + p->next->size + sizeof(MetaData);
            q = p->next->next;
            p->next = q;
            if (q != NULL) {
                q->prev = p;
            }
            //p->size = size;
        }
    }
    // 向前合并
    if (p->size < size && p->prev && p->prev->free) {
        if (p->size + p->prev->size >= size) {
            q = p->next;
            p = p->prev;
            size_t ksize = p->size + p->next->size - size;
            dataCopyTo(p->begin, p->next->begin, p->next->size);
            k = (pMetaData)(((char *)p->begin) + size);
            initMetaData(k, ksize, 1, p, q);
            p->next = k;
            if (q != NULL) {
                q->prev = k;
            }
            p->size = size;
            p->free = 0;
        } else if (p->size + p->prev->size + sizeof(MetaData) >= size) {
            q = p->next;
            p = p->prev;
            size_t totalsize = p->size + p->next->size + sizeof(MetaData);
            dataCopyTo(p->begin, p->next->begin, p->next->size);
            p->next = q;
            if (q != NULL) {
                q->prev = p;
            }
            p->size = totalsize;
            p->free = 0;
        }
    }
    // 没有合适的位置，重新向系统申请并释放之前的空间
    if (p->size < size) {
        void *ret = mylloc(size);
        if (ret == NULL) return NULL;
        dataCopyTo(ret, p->begin, p->size);
        myfree(p->begin);
        p = (pMetaData)(((char *)ret) - sizeof(MetaData));
    }
    return p->begin;
}