min_malloc.c

小型内存分配模块,用通用循环双向链表实现

/*
 * 使用一条链表(管理空闲内存块)实现可变长度的内存分配和回收，可任意申请和分配
 * Author: [e-mail]  2009-5-15
*/
#include <stdio.h>
#include <stdlib.h>
#include "slist.h"

#define MALLOC_MAX_SIZE 10000
#define BLOCK_SIZE sizeof(struct Block)

typedef unsigned long uint_32;

struct Block{
    int used;
    size_t size;
    struct Slist free_node;
    struct Slist total_node;
};

char *mem = NULL;
struct Slist free_head;
struct Slist total_head;

/*
 *  功能：返回一个指针指向size大小的内存
 *   如果没有足够的内存空间，则返回NULL
*/
void *min_malloc(size_t size)
{
    size_t tmp_size;
    struct Block *blk;
    struct Slist *free_node_link;
    struct Slist *total_node_link;
    void *addr = NULL;

    /* 第一次分配内存，对其初始化 */
    if (mem == NULL) {
        slist_init(&free_head);
        slist_init(&total_head);
        mem = (char *)malloc(BLOCK_SIZE);
        blk = (struct Block *)mem;
        blk->used = 0;
        blk->size = MALLOC_MAX_SIZE - BLOCK_SIZE;
        blk->free_node.pre = NULL;
        blk->free_node.next = NULL;
        blk->total_node.pre = NULL;
        blk->total_node.next = NULL;
        slist_add_node(&free_head, &blk->free_node);
        slist_add_node(&total_head, &blk->total_node);
    }

    free_node_link = slist_get_head(&free_head);
    total_node_link = slist_get_head(&total_head);
    blk = (struct Block *)container_of(struct Block, free_node, (size_t)free_node_link);

    /* 寻找足够分配内存空间的结点 */
    while (blk->size < size) {
        free_node_link = slist_next(&free_head, &blk->free_node);
        if (free_node_link == NULL) {
            printf("memory is not enough!\n");
            return NULL;
       }
        blk = (struct Block *)container_of(struct Block, free_node, (size_t)free_node_link);
    }

    /* 找到足够内存分配空间的结点后从空闲链表中删除该结点 */
    slist_del_node(&free_head, &blk->free_node);
    blk->used = 1;
    if (blk->size - size >= BLOCK_SIZE) {
        tmp_size = blk->size - size - BLOCK_SIZE;
        blk->size = size;
        addr = (void *)((uint_32)blk + BLOCK_SIZE);
        blk = (struct Block *)((uint_32)blk + BLOCK_SIZE + blk->size);
        blk->used = 0;
        blk->size = tmp_size;
        slist_add_node(&free_head, &blk->free_node);
        slist_add_node(&total_head, &blk->total_node);
    } else {
        blk->size = blk->size;
        addr = (void *)((uint_32)blk + BLOCK_SIZE);
    }

    return addr;
}

/*
 * 功能：回收由min_malloc分配的内存空间
 *  如果指针addr为空，则什么都不做，指针addr指向的地址必须是min_malloc分配的地址，否则异常
*/
void min_free(void *addr)
{
    struct Block *blk;
    struct Slist *total_node_link_next;
    struct Slist *total_node_link_pre;
    struct Block *p;
    struct Block *q;

    /* 如果传入指针为空, 则什么也不做 */
    if (addr == NULL) {
        return;
    }

    /* 如果传入的地址不是由min_malloc分配, 则异常处理 */
    if ((uint_32)addr < (size_t)mem || (uint_32)addr > (size_t)mem + MALLOC_MAX_SIZE) {
        printf("The address is not allocated by min_malloc!\n");
        return;
    }

    blk = (struct Block *)((uint_32)addr - BLOCK_SIZE);

    if (&blk->total_node == slist_get_head(&total_head)) {
        total_node_link_next = slist_next(&total_head, &blk->total_node);
        if (total_node_link_next == NULL) {
            blk->used = 0;
            return;
        }
        p = (struct Block *)container_of(struct Block, total_node, (size_t)total_node_link_next);
        if (p->used == 0) {
            blk->used = 0;
            blk->size += p->size;
            slist_del_node(&free_head, &p->free_node);
            slist_del_node(&blk->total_node, &p->total_node);
            slist_add_node(&free_head, &blk->free_node);
            return;
        } else {
            blk->used = 0;
            slist_add_node(&free_head, &blk->free_node);
            return;
        }
    } else if (&blk->total_node == slist_pre(&total_head, &total_head)) {
        total_node_link_pre = slist_pre(&total_head, &blk->total_node);
        if (total_node_link_pre == NULL) {
            blk->used = 0;
            return;
        }
        q = (struct Block *)container_of(struct Block, total_node, (size_t)total_node_link_pre);
        if (q->used == 0) {
            blk->used = 0;
            q->size += blk->size;
            slist_del_node(&q->total_node, &blk->total_node);
            return;
        } else {
            blk->used = 0;
            slist_add_node(&free_head, &blk->free_node);
            return;
        }

    } else {

        total_node_link_next = slist_next(&total_head, &blk->total_node);
    p = (struct Block *)container_of(struct Block, total_node, (size_t)total_node_link_next);

    total_node_link_pre = slist_pre(&total_head, &blk->total_node);
    q = (struct Block *)container_of(struct Block, total_node, (size_t)total_node_link_pre);

    /* 分四种情况回收并合并相邻内存空间 */
    if (q->used == 1 && p->used == 1) {
        blk->used = 0;
        slist_add_node(&free_head, &blk->free_node);
        return;
    }

    if (q->used == 0 && p->used == 1) {
        blk->used = 0;
        q->size += blk->size + BLOCK_SIZE;
        slist_del_node(&q->total_node, &blk->total_node);
        return;
    }

    if (q->used == 1 && p->used == 0) {
        blk->used = 0;
        blk->size += p->size + BLOCK_SIZE;
        slist_add_node(&free_head, &blk->free_node);
        return;
    }

    if (q->used == 0 && p->used == 0) {
        blk->used = 0;
        q->size += blk->size + p->size + 2 * BLOCK_SIZE;
        return;
    }

    }

    return;
}


void min_malloc_debug(void)
{
    struct Block *p;

    p = (struct Block *)mem;
    while ((uint_32)p < (size_t)mem + MALLOC_MAX_SIZE) {
        printf("addr: %x, used: %d, size: %d\n", p, p->used, p->size);
        p = (struct Block *)((uint_32)p + BLOCK_SIZE + p->size);
    }
    putchar(10);
}