min_malloc.cpp 第一版

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

#include "list.h"
#include "min_malloc.h"

typedef unsigned long uint_32;
#define offsetof(s,m) (size_t)&(((s *)0)->m)
#define container_of(TYPE, MEMBER, ADDR) \
    (size_t)((size_t)ADDR - offsetof(TYPE, MEMBER))

#define MALLOC_SIZE 10000000
#define MALLOC_HEADER sizeof(struct malloc_header)

FILE *fp = fopen("malloc.log", "w");

static char *malloc_mem = NULL;

static struct DListHeader malloc_list;
static struct DListHeader malloc_free_list;

struct malloc_header
{
    struct DListNode list; // manage the free block and used block

    struct DListNode free_list; // manage the free block

    uint_32 addr;
    int size;
};

int malloc_debug()
{
    int i = 0;
    int malloc_sum = 0;
    int malloc_free = 0;
    struct DListNode *p = NULL;
    struct malloc_header * malloc_point = NULL;

    if (1)
    {
        p = &malloc_list.head;
        i = 0;
        while (p)
        {
            ++i;
            malloc_point = (struct malloc_header *)container_of(struct malloc_header, list, p);
            if (p != &malloc_list.head)
                malloc_sum += malloc_point->size;
            fprintf(fp, "malloc_list :NO.%d %8x %8x %8x size:%d\n", i, (uint_32)p, (uint_32)p->pre, (uint_32)p->next, malloc_point->size);
            p = DList_get_next(&malloc_list, p);
        }

        p = &malloc_free_list.head;
        i = 0;
        while (p)
        {
            ++i;
            malloc_point = (struct malloc_header *)container_of(struct malloc_header, free_list, p);
            if (p != &malloc_free_list.head)
                malloc_free += malloc_point->size;
            fprintf(fp, "malloc_free_list:NO.%d %8x %8x %8x size:%d\n", i, (uint_32)p, (uint_32)p->pre, (uint_32)p->next, malloc_point->size);
            p = DList_get_next(&malloc_free_list, p);
        }
    }

    fprintf(fp, "The sum of malloc: %d The sum of free: %d\n", malloc_sum, malloc_free);
    fprintf(fp, "\n");

    return 0;
}

void * min_malloc(int size)
{
    struct malloc_header * malloc_point = NULL;
    struct malloc_header * malloc_free = NULL;
    struct DListNode *node = NULL;
    void *p = NULL;

    /* first call min_malloc, and apply a large block */
    if (malloc_mem == NULL)
    {
        malloc_mem = (char *)malloc(MALLOC_SIZE);
        malloc_point = (struct malloc_header *)malloc_mem;
        malloc_point->addr = (uint_32)malloc_mem;
        malloc_point->size = MALLOC_SIZE;
        malloc_point->free_list.next = malloc_point->free_list.pre = NULL;
        malloc_point->list.next = malloc_point->list.pre = NULL;

        initialize_Dlist_header(&malloc_list);
        initialize_Dlist_header(&malloc_free_list);
        DList_add_tail(&malloc_list, &malloc_point->list);
        DList_add_tail(&malloc_free_list, &malloc_point->free_list);
    }

    // search the first enough memory

    node = DList_get_head(&malloc_free_list);
    while (node != NULL)
    {
        malloc_point = (struct malloc_header *)container_of(struct malloc_header, free_list, node);
        if (malloc_point->size >= size + (int)MALLOC_HEADER)
            break;
        node = DList_get_next(&malloc_free_list, &malloc_point->free_list);
    }

    if (node == NULL)
        return NULL;

    if (malloc_point->size <= size + (int)MALLOC_HEADER * 2)
    {
        DList_delete_node(&malloc_free_list, &malloc_point->free_list);
        p = (void *)(malloc_point->addr + MALLOC_HEADER);
    }
    else
    {
        p = (void *)(malloc_point->addr + MALLOC_HEADER);

        malloc_free = (struct malloc_header *)(malloc_point->addr + MALLOC_HEADER + size);
        malloc_free->addr = malloc_point->addr + MALLOC_HEADER + size;
        malloc_free->size = malloc_point->size - MALLOC_HEADER - size;
        DList_add_after(&malloc_free_list, &malloc_point->free_list, &malloc_free->free_list);
        DList_add_after(&malloc_list, &malloc_point->list, &malloc_free->list);

        malloc_point->size = MALLOC_HEADER + size;
        DList_delete_node(&malloc_free_list, &malloc_point->free_list);
    }
    
    return p;
}

void * min_free(void *addr)
{
    int coalesce_case = 0;
    struct malloc_header * malloc_point = NULL;
    struct malloc_header * malloc_free_pre = NULL;
    struct malloc_header * malloc_free_next = NULL;

    if (addr == NULL)
        return NULL;

    /* find out the management structure */
    malloc_point = (struct malloc_header *)malloc_list.head.next;
    while ((malloc_point && (malloc_point->addr + MALLOC_HEADER != (uint_32)addr)) || (malloc_point->free_list.next != NULL && malloc_point->free_list.pre != NULL))
        malloc_point = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_point->list);

    if (malloc_point == NULL)
    {
        printf("The bad address!\n");
        return 0;
    }

    /* coalesce with adjoint block */
    malloc_free_pre = (struct malloc_header *)DList_get_pre(&malloc_list, &malloc_point->list);
    if (malloc_free_pre != NULL && malloc_free_pre->free_list.next != NULL && malloc_free_pre->free_list.pre != NULL)
        coalesce_case |= 1;

    malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_point->list);
    if (malloc_free_next != NULL && malloc_free_next->free_list.next != NULL && malloc_free_next->free_list.pre != NULL)
        coalesce_case |= 2;

    switch(coalesce_case)
    {
    case 0: /* coalesce with nothing */
        malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_point->list);
        while (malloc_free_next != NULL && malloc_free_next->free_list.next == NULL && malloc_free_next->free_list.pre == NULL)
            malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_free_next->list);
        if (malloc_free_next == NULL)
            DList_add_tail(&malloc_free_list, &malloc_point->free_list);
        else
            DList_add_before(&malloc_free_list, &malloc_free_next->free_list, &malloc_point->free_list);
        break;
    case 1: /* coalesce with pre */
        malloc_free_pre = (struct malloc_header *)DList_get_pre(&malloc_list, &malloc_point->list);
        malloc_free_pre->size += malloc_point->size;
        DList_delete_node(&malloc_list, &malloc_point->list);
        break;
    case 2: /* coalesce with next */
        malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_point->list);
        malloc_point->size += malloc_free_next->size;
        DList_add_before(&malloc_free_list, &malloc_free_next->free_list, &malloc_point->free_list);
        DList_delete_node(&malloc_list, &malloc_free_next->list);
        DList_delete_node(&malloc_free_list, &malloc_free_next->free_list);
        break;
    case 3: /* coalesce with both */
        malloc_free_pre = (struct malloc_header *)DList_get_pre(&malloc_list, &malloc_point->list);
        malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_point->list);
        malloc_free_pre->size = malloc_free_pre->size + malloc_free_next->size + malloc_point->size;
        DList_delete_node(&malloc_free_list, &malloc_free_next->free_list);
        DList_delete_node(&malloc_list, &malloc_free_next->list);
        DList_delete_node(&malloc_list, &malloc_point->list);
        break;
    }

    return NULL;
}