malloc和free实现代码

今天中午快速的实现了一个malloc和free的另一个版本代码，用位图的形式实现，速度暂时没优化，记录一下：

/*
 * file: main.c
 * author: [e-mail]
 * date: 2013-06-09
 * brief: main
 */

#include "stdafx.h"

#include "string.h"
#include "stdlib.h"
#include "stdio.h"
#include <time.h>

void xmfree(void *hd, void *pmblk);
void *xmalloc(void *hd, size_t size);
void dump_map(void *hd);
void* xmcreate(char *buf, size_t size);

void ConPrint(char *CharBuffer, int len);
void ConPrintAt(int x, int y, char *CharBuffer, int len);
void gotoXY(int x, int y);
void ClearConsole(void);
void ClearConsoleToColors(int ForgC, int BackC);
void SetColorAndBackground(int ForgC, int BackC);
void SetColor(int ForgC);
void HideTheCursor(void);
void ShowTheCursor(void);

struct stat_info{
    int success;
    int failed;
    int total;
    int time_val;
};

int main(int argc, char* argv[])
{
    char *arr_pnew[10];
    char buf[10000];
    void *handle=0;
    int rd_idx=0;

    unsigned int success=0;
    unsigned int failed=0;
    unsigned int total=0;
    unsigned int time_val=0;

    clock_t start, finish;

    srand(time(0));
    memset(arr_pnew, 0, sizeof(arr_pnew));
    handle = xmcreate(buf, sizeof(buf));

    start = clock();

    while (1) {

        rd_idx = rand()%(sizeof(arr_pnew)/sizeof(arr_pnew[0]));
        if(arr_pnew[rd_idx]==0){
            arr_pnew[rd_idx] = (char*)xmalloc(handle, rand()%sizeof(buf));
            if (arr_pnew[rd_idx])
                success++;
            else
                failed++;

            total++;
            if(total) {
                finish = clock();
                gotoXY(0, 0);
                SetColor(15);
                printf("total:%-8d success=%-8d failed=%-8drntime(ms)=%-8d precent=%d%% ",
                    total, success, failed, finish-start, (success*100)/total);
            }
        }else {
            xmfree(handle, arr_pnew[rd_idx]);
            arr_pnew[rd_idx]=0;
        }
    }

    //ClearConsole();
    return 0;
}

/*
 * file: xmalloc.c
 * author: [e-mail]
 * date: 2013-06-09
 * brief: xmalloc and xmfree
 */

#include "string.h"
#include "stdio.h"

void ConPrint(char *CharBuffer, int len);
void ConPrintAt(int x, int y, char *CharBuffer, int len);
void gotoXY(int x, int y);
void ClearConsole(void);
void ClearConsoleToColors(int ForgC, int BackC);
void SetColorAndBackground(int ForgC, int BackC);
void SetColor(int ForgC);
void HideTheCursor(void);
void ShowTheCursor(void);

void xmfree(void *hd, void *pmblk);
void *xmalloc(void *hd, size_t size);
void dump_map(void *hd);
void* xmcreate(char *buf, size_t size);


#define DIV_SYS        1
#define ALIGN_SIZE    8 /* 8 Byte */
#define XM_MAGIC    0x12345678
#define XM_BLOCK    S_ALIGN(32)    /* memory block size 32 Byte */

#if DIV_SYS
    #define INTDIV(dend,div) ((dend)/(div))
#else
    #define INTDIV(dend,div) int_div(dend,div)
#endif

#define S_ALIGN(sz)            (((unsigned int)(sz)+(ALIGN_SIZE-1))&~(ALIGN_SIZE-1))
#define F_ALIGN(addr)        ((unsigned int)((unsigned int)(addr)+(ALIGN_SIZE-1))&~(ALIGN_SIZE-1))
#define B_ALIGN(addr)        ((unsigned int)(addr)&~(ALIGN_SIZE-1))
#define MEM_ADDR_END(p,s)    (B_ALIGN((unsigned int)(p)+(s)))
#define MAP_ADDR(p)            (F_ALIGN(F_ALIGN(p)+sizeof(struct xmem_head)))
#define MAP_SIZE(p,s)        (INTDIV(((INTDIV((MEM_ADDR_END(p,s)-MAP_ADDR(p)+(XM_BLOCK-1)),XM_BLOCK))+(8-1)),8))
#define BLK_ADDR(p,s)        (F_ALIGN((unsigned int)MAP_ADDR(p)+MAP_SIZE(p,s)))
#define BLK_NUM(p,s)        (INTDIV((MEM_ADDR_END(p,s)-BLK_ADDR(p,s)),XM_BLOCK))

#define RBIT(v,n)        ((v)&(1<<(n)))
#define WBIT(v,n)        ((v)^=(1<<(n)))
#define CBIT(v,n)        ((v)&=~(1<<(n)))
#define MAP_RBIT(p,c)    RBIT(*((char*)p+(c)/8),(c)%8)
#define MAP_WBIT(p,c)    WBIT(*((char*)p+(c)/8),(c)%8)
#define MAP_CBIT(p,c)    CBIT(*((char*)p+(c)/8),(c)%8)

#define dump printf

#ifndef size_t
#define size_t unsigned int
#endif


#define assert(x) do {
    if (!(x)) {
        printf("ERROR: ASSERT ON LINE(%d)!!!rn", __LINE__);
        while(1);
    }
}while(0);

struct xmem_head {
    unsigned int magic;
    char *map_addr;
    char *blk_addr;
    unsigned int blk_nums;
};

static int int_div(unsigned int dividend, unsigned int divisor)
{
    unsigned int k, c, res=0;

    if(divisor == 0) {
        assert(divisor!=0);
        while(1);
    }
    if (dividend < divisor) return 0;
    if (dividend == divisor) return 1;
    while (dividend > divisor) {
        for (k = 0,c = divisor; dividend >= c; c <<= 1, k++) {
            if (dividend - c < divisor){
                res += 1<<k;
                break;
            }
        }
        if (dividend-c < divisor) break;
        res += 1<<(k - 1);
        dividend -= c>>1;
    }
    return res;
}

void* xmcreate(char *buf, size_t size)
{
    struct xmem_head *pxmh=0;
    if (!buf || size<sizeof(struct xmem_head)+ALIGN_SIZE+XM_BLOCK*2)
        return (void*)0;

    pxmh = (struct xmem_head*)(F_ALIGN(buf));
    pxmh->magic = XM_MAGIC;
    pxmh->map_addr=(char*)MAP_ADDR(buf);
    pxmh->blk_addr=(char*)BLK_ADDR(buf,size);
    pxmh->blk_nums=BLK_NUM(buf,size);

    memset(pxmh->map_addr, 0, MAP_SIZE(buf,size));

    if (pxmh->blk_addr<=pxmh->map_addr || pxmh->blk_nums<2) {
        pxmh->magic = 0;
        return (void*)0;
    }
    return pxmh;
}

void xmdestroy(void *hd)
{
    if (!hd || ((struct xmem_head*)hd)->magic!=XM_MAGIC)
        return ;
    ((struct xmem_head*)hd)->magic=0x11223344;
}

void dump_map(void *hd)
{
    int i=0, of, cnt;
    char* pmap;
    struct xmem_head *pxmh=(struct xmem_head *)hd;
    if (!hd || ((struct xmem_head*)hd)->magic!=XM_MAGIC)
        return;
    pmap = pxmh->map_addr;
    of=i=0;
    gotoXY(0,1);
    cnt=0;
    SetColor(10);
    printf("rn---------------------------------------------------------------rn");
    do {
        for(i=0; i<8; i++){
            if (of*8+i >= pxmh->blk_nums) {
                SetColor(10);
                printf("rn---------------------------------------------------------------rn");
                assert(cnt%2==0);
                return;
            }
            if (!!MAP_RBIT(pmap,of*8+i)) {
                SetColor(14);
                cnt++;
                printf("%d ", !!MAP_RBIT(pmap,of*8+i));
            }
            else
            {
                if ((cnt%2)==0)
                    SetColor(4);
                else
                    SetColor(14);
                printf("%d ", !!MAP_RBIT(pmap,of*8+i));
            }
        }
        if ((of+1)%4==0) printf("rn");
        of++;
    } while(1);
}


void *xmalloc(void *hd, size_t size)
{
    char *pmap=0;
    struct xmem_head *pxmh=0;
    int of, i, f, c;
    if (!hd || ((struct xmem_head*)hd)->magic!=XM_MAGIC)
        return (void*)0;
    //search of the free part for memory size
    pxmh = (struct xmem_head*)hd;
    pmap = pxmh->map_addr;
    f=c=i=0;
    of=0;
    //printf("INFO: xmalloc size=%drn", size);
    do {
        for (i=0; i<8; i++){
            if (of*8+i >= pxmh->blk_nums)
                goto MATCH_FAIL;

            if(MAP_RBIT(pmap, of*8+i)){
                f++;
                if (!(f&0x01)) {
                    c=0;
                    continue;
                }
            }
            c++;
            if(!(f&0x01) && c*XM_BLOCK>=size){
                if (c==1) continue; //must bigger than 2 blocks every malloc
                //printf("INFO: xmalloc index:%d-%drn", of*8+i-c+1, of*8+i);
                assert(MAP_RBIT(pmap,of*8+i-c+1)==0);
                MAP_WBIT(pmap,of*8+i-c+1); //set begin offset of free block
                assert(MAP_RBIT(pmap,of*8+i)==0);
                MAP_WBIT(pmap,of*8+i); //set end offset of free block
                dump_map(hd);
                return pxmh->blk_addr+(of*8+i-c+1)*XM_BLOCK;
            }
        }
        of++;
    } while (1);

MATCH_FAIL:
    //printf("ERROR: NO FREE SPACE FOR XMALLOC!!!rn");
    return (void*)0;
}

void xmfree(void *hd, void *pmblk)
{
    struct xmem_head *pxmh=0;
    char *pmb=(char*)pmblk;
    char *pmap, *pblk;
    int of=0, i=0;
    if (!hd || ((struct xmem_head*)hd)->magic!=XM_MAGIC)
        return ;
    pxmh = (struct xmem_head*)hd;
    pblk = pxmh->blk_addr;
    pmap = pxmh->map_addr;
    assert(pblk&&pmap);
    if (pmb>=pblk && pmb<pblk+pxmh->blk_nums*XM_BLOCK) {
        assert((pmb-pblk)%XM_BLOCK==0);
        of = (pmb-pblk)/XM_BLOCK;
        assert(of<pxmh->blk_nums);
        MAP_CBIT(pmap,of);
        //printf("INFO: xmfree index:%d-", of);
        while (1) {
            of++;
            if(MAP_RBIT(pmap,of)) {
                MAP_CBIT(pmap,of);
                //printf("%drn", of);
                dump_map(hd);
                break;
            }
        }
    }
}

/*
 * file: screen.c
 * brief: drawing
 */

#include <windows.h>
#include <stdio.h>

void ConPrint(char *CharBuffer, int len);
void ConPrintAt(int x, int y, char *CharBuffer, int len);
void gotoXY(int x, int y);
void ClearConsole(void);
void ClearConsoleToColors(int ForgC, int BackC);
void SetColorAndBackground(int ForgC, int BackC);
void SetColor(int ForgC);
void HideTheCursor(void);
void ShowTheCursor(void);

int test_main(int argc, char* argv[])
{
   HideTheCursor();
   ClearConsoleToColors(15, 1);
   ClearConsole();
   gotoXY(1, 1);
   SetColor(14);
   printf("This is a test...n");
   Sleep(5000);
   ShowTheCursor();
   SetColorAndBackground(15, 12);
   ConPrint("This is also a test...n", 23);
   SetColorAndBackground(1, 7);
   ConPrintAt(22, 15, "This is also a test...n", 23);
   gotoXY(0, 24);
   SetColorAndBackground(7, 1);
   return 0;
}

//This will clear the console while setting the forground and
//background colors.
void ClearConsoleToColors(int ForgC, int BackC)
{
   WORD wColor = ((BackC & 0x0F) << 4) + (ForgC & 0x0F);
   //Get the handle to the current output buffer...
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   //This is used to reset the carat/cursor to the top left.
   COORD coord = {0, 0};
   //A return value... indicating how many chars were written
   //not used but we need to capture this since it will be
   //written anyway (passing NULL causes an access violation).
   DWORD count;

   //This is a structure containing all of the console info
   // it is used here to find the size of the console.
   CONSOLE_SCREEN_BUFFER_INFO csbi;
   //Here we will set the current color
   SetConsoleTextAttribute(hStdOut, wColor);
   if(GetConsoleScreenBufferInfo(hStdOut, &csbi))
   {
      //This fills the buffer with a given character (in this case 32=space).
      FillConsoleOutputCharacter(hStdOut, (TCHAR) 32, csbi.dwSize.X * csbi.dwSize.Y, coord, &count);

      FillConsoleOutputAttribute(hStdOut, csbi.wAttributes, csbi.dwSize.X * csbi.dwSize.Y, coord, &count);
      //This will set our cursor position for the next print statement.
      SetConsoleCursorPosition(hStdOut, coord);
   }
}

//This will clear the console.
void ClearConsole()
{
   //Get the handle to the current output buffer...
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   //This is used to reset the carat/cursor to the top left.
   COORD coord = {0, 0};
   //A return value... indicating how many chars were written
   // not used but we need to capture this since it will be
   // written anyway (passing NULL causes an access violation).
   DWORD count;
   //This is a structure containing all of the console info
   // it is used here to find the size of the console.
   CONSOLE_SCREEN_BUFFER_INFO csbi;
   //Here we will set the current color
   if(GetConsoleScreenBufferInfo(hStdOut, &csbi))
   {
      //This fills the buffer with a given character (in this case 32=space).
      FillConsoleOutputCharacter(hStdOut, (TCHAR) 32, csbi.dwSize.X * csbi.dwSize.Y, coord, &count);
      FillConsoleOutputAttribute(hStdOut, csbi.wAttributes, csbi.dwSize.X * csbi.dwSize.Y, coord, &count);
      //This will set our cursor position for the next print statement.
      SetConsoleCursorPosition(hStdOut, coord);
   }
}

//This will set the position of the cursor
void gotoXY(int x, int y)
{
   //Initialize the coordinates
   COORD coord = {x, y};
   //Set the position
   SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}

//This will set the forground color for printing in a console window.
void SetColor(int ForgC)
{
   WORD wColor;
   //We will need this handle to get the current background attribute
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   CONSOLE_SCREEN_BUFFER_INFO csbi;

   //We use csbi for the wAttributes word.
   if(GetConsoleScreenBufferInfo(hStdOut, &csbi))
   {
      //Mask out all but the background attribute, and add in the forgournd color
      wColor = (csbi.wAttributes & 0xF0) + (ForgC & 0x0F);
      SetConsoleTextAttribute(hStdOut, wColor);
   }
}

//This will set the forground and background color for printing in a console window.
void SetColorAndBackground(int ForgC, int BackC)
{
   WORD wColor = ((BackC & 0x0F) << 4) + (ForgC & 0x0F);;
   SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), wColor);
}

//Direct console output
void ConPrint(char *CharBuffer, int len)
{
   DWORD count;
   WriteConsole(GetStdHandle(STD_OUTPUT_HANDLE), CharBuffer, len, &count, NULL);
}

//Direct Console output at a particular coordinate.
void ConPrintAt(int x, int y, char *CharBuffer, int len)
{
   DWORD count;
   COORD coord = {x, y};
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
   SetConsoleCursorPosition(hStdOut, coord);
   WriteConsole(hStdOut, CharBuffer, len, &count, NULL);
}

//Hides the console cursor
void HideTheCursor()
{
   CONSOLE_CURSOR_INFO cciCursor;
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);

   if(GetConsoleCursorInfo(hStdOut, &cciCursor))
   {
      cciCursor.bVisible = FALSE;
      SetConsoleCursorInfo(hStdOut, &cciCursor);
   }
}

//Shows the console cursor
void ShowTheCursor()
{
   CONSOLE_CURSOR_INFO cciCursor;
   HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);

   if(GetConsoleCursorInfo(hStdOut, &cciCursor))
   {
      cciCursor.bVisible = TRUE;
      SetConsoleCursorInfo(hStdOut, &cciCursor);
   }
}

附件：

xmalloc.rar