memorymanage.cpp

内存管理, 减少碎片, 使用vc6编译通过.

    for(i=0;i<nbytes;i++)
    {
        mask = 1;

        for(j=0;j<8;j++)
        {
            if(bit>=index)
            {
                if(bit==index+nbits){ return;}
                if(val){ map[i]=map[i]|mask; }
                else{ map[i]=map[i]&(~mask); }
            }
            bit++;
            mask = mask*2;
        }
    }
    return;

}/*setBits---------------------------------------------------------------*/

/*
returns that value of the specified bit (0-nbits-1)
or -1 if index is out of bounds
*/

int BitMap::getBit(unsigned long index)
{
    unsigned long bit;
    unsigned long i,j;
    unsigned char mask;

    bit=0;

    for(i=0;i<nbytes;i++)
    {
        mask = 1;

        for(j=0;j<8;j++)
        {
            if(bit==index)
            {
                if(map[i]&mask){ return(1); }
                else{ return(0); }
            }
            bit++;
            mask = mask*2;
        }
    }
return(-1);

}/*getBit----------------------------------------------------*/

/*
returns the index that marks the start of 'size' bits set to 1
or returns -1 if such a run was not found
*/

long BitMap::getBitRun(unsigned long size)
{
    unsigned long current_size;
    unsigned long bit;
    unsigned long i,j;
    unsigned char mask;

    current_size=0;
    bit=0;

    for(i=0;i<nbytes;i++)
    {
        mask = 1;

        for(j=0;j<8;j++)
        {
            if(map[i]&mask)
            {
                current_size++;
                if(current_size==size){ return(bit-size+1); }
            }
            else
            {
                 current_size=0;
            }
            bit++;
            mask = mask*2;
        }
    }

    return(-1);

}/*getBitRun-----------------------------------------------------------------------*/

void BitMap::printMap()
{
    unsigned long bit;
    unsigned long i,j;
    unsigned char mask;

    bit=0;

    for(i=0;i<nbytes;i++)
    {
        mask = 1;
        printf("byte[%u]=%x\n",i,map[i]);

        for(j=0;j<8;j++)
        {
            if(map[i]&mask){ printf("1"); }
            else{ printf("0"); }
            bit++;
            mask = mask*2;
        }
        printf("\n\n");
    }
    return;

}/*end printMap------------------------------------------*/

memmgr.cpp
This source file brings the two previous data structures together to form an actual memory manager, known fittingly as the Memory-Manager class.

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ declarations
+
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

class MemoryManager
{
    private:
    BinarySearchTree bst;
    BitMap *bmap;
    HANDLE handle;            //handle to heap
    unsigned char *mem;       //actual memory to manage
    unsigned long memLength;  //size in bytes of memory

    public:
    MemoryManager(unsigned long totalbytes);
    ~MemoryManager();
    void* allocate(unsigned long nbytes);
    void release(void *ptr);
    void printState();
};


/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ definitions
+
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*
sets the total amount of memory, no re-sizing in this case each
byte in the BitMap represents BYTES_BITMAP_BYTE bytes of memory
*/
MemoryManager::MemoryManager(unsigned long totalbytes)
{
    //init 3 dynamic objects: bmap, bst, mem[]

    bmap = new BitMap((totalbytes/BYTES_PER_BITMAP_BYTE)+1);

    bst.root_ptr=NULL;

    memLength = (*bmap).getByteSize()*BYTES_PER_BITMAP_BYTE;

    handle = GetProcessHeap();
    if(handle==NULL)
    {
        printf("MemoryManager::MemoryManager(): invalid
                handle\n");
        return;
    }

    mem = (unsigned char*)HeapAlloc(handle,HEAP_ZERO_MEMORY,
           memLength);

    //for portability, you could use:
    //mem = (unsigned char*)malloc(memLength);

    if(mem==NULL)
    {
        printf("MemoryManager::MemoryManager():");
        printf("could not alloc memory\n");
        exit(1);
    }
    printf("MemoryManager::MemoryManager():");
    printf("mallloc() mem[%lu]\n",memLength);

    return;

}/*end constructor--------------------------------------------------------------------*/

MemoryManager::~MemoryManager()
{
    //release resources for objects: bmap, bst, mem[]

    delete(bmap);

    bst.deleteAll(&(bst.root_ptr));

    if(HeapFree(handle,HEAP_NO_SERIALIZE,mem)==0)
    {
        printf("MemoryManager::~MemoryManager(): HeapFree()
                failed\n");
        return;
    }

    //for portability, you could use:
    //free(mem);

    printf("MemoryManager::~MemoryManager():");
    printf("free() mem[%lu]\n",memLength);

    return;

}/*end destructor--------------------------------------------------------*/

void* MemoryManager::allocate(unsigned long nbytes)
{
    unsigned long run_bits;
    long index;
    struct BiNode node;

    PRINT("MemoryManager::allocate(): request %lu bytes\n",
           nbytes);

    //translate nbytes into # of bits in BitMap

    run_bits = (nbytes/BYTES_PER_BITMAP_BIT)+1;

    PRINT("MemoryManager::allocate(): run_bits=%lu\n",run_bits);

    //look for # of free bits in BitMap

    index = ((*bmap).getBitRun(run_bits));

    PRINT("MemoryManager::allocate(): found run of %lu bits
          ",run_bits);
    PRINT("at %lu\n",index);

    if(index==-1){ return(NULL); }

    //reserved bits in BitMap

    (*bmap).setBits(0,run_bits,index);

    node.value = (unsigned long)(&mem[index*16]);
    node.index = index;
    node.nreserved = run_bits;

    bst.insertNode(&(bst.root_ptr),&node);

    //return memory represented by BitMap bits

    PRINT("MemoryManager::allocate(): address=%lu\n",&mem
          [index*16]);

    return((void*)&mem[index*16]);

}/*end allocate------------------------------------------------------------------------------*/

void MemoryManager::release(void *addr)
{
    struct BiNode *ptr;

    ptr = bst.findNode(bst.root_ptr,(unsigned long)addr);
    if(ptr!=NULL)
    {
        PRINT("MemoryManager::release(): addr=%lu\n",(unsigned
               long)addr);
        (*bmap).setBits(1,(*ptr).nreserved,(*ptr).index);
        bst.deleteNode(&(bst.root_ptr),(unsigned long)addr);
    }
    return;

}/*end release--------------------------------------------------*/

void MemoryManager::printState()
{
    printf("-------------------------------------------------\n");
    (*bmap).printMap();
    printf ("------------------------------------------------\n");
    bst.printTree(bst.root_ptr,0);
    printf ("------------------------------------------------\n");
    return;

}/*end printState----------------------------------------------*/

mallocV1.cpp
This file supplies wrappers that allow the MemoryManager class to be used under the guise of the newMalloc() and newFree() functions so that existing applications will only have to be slightly modified.

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

// these DEBUG_XXX macros insert printf() statements in the
   final executable
//#define DEBUG_TREE
//#define DEBUG_BITMAP
//#define DEBUG_MEM_MGR
//#define DEBUG_MALLOCV1

#include<tree.cpp>
#include<bitmap.cpp>
#include<memmgr.cpp>

/*
wrapper functions
*/

MemoryManager *mmptr;

void initMemMgr(unsigned long totalbytes)
{
    mmptr = new MemoryManager(totalbytes);
}

void closeMemMgr()
{
    delete(mmptr);
}

void *newMalloc(unsigned long size)
{
    void *ptr = (*mmptr).allocate(size);

#ifdef DEBUG_MALLOCV1
    (*mmptr).printState();
#endif

    return(ptr);
}

void newFree(void *ptr)
{
    (*mmptr).release(ptr);

#ifdef DEBUG_MALLOCV1
    (*mmptr).printState();
#endif

    return;
}