memorymanage.cpp

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

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

struct BiNode
{
    unsigned long value;        //linear address
    unsigned long index;        //index into bitmap [0,nbits-1]
    unsigned long nreserved;    //number of bits reserved

    struct BiNode *left;
    struct BiNode *right;
};

class BinarySearchTree
{
    public:
    struct BiNode *root_ptr;

    void insertNode(struct BiNode **link, unsigned long val);
    void insertNode(struct BiNode **link, struct BiNode *ptr);

    struct BiNode* findNode(struct BiNode *link, unsigned
                            long val);

    struct BiNode* deleteSmallestNode(struct BiNode **link);
    void deleteNode(struct BiNode **link, unsigned long val);
    void deleteAll(struct BiNode **link);

    void printTree(struct BiNode *link, int level);
    unsigned long getHeight(struct BiNode *link);
};

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ definitions
+
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*
     given struct Binode **link
     link   = address of a variable which holds the address
              of the node
     *link = address of the node
     **link = node
*/

void BinarySearchTree::insertNode(struct BiNode **link,
                                  unsigned long val)
{
   if( *link==NULL )
   {
       (*link) = (struct BiNode*)malloc(sizeof(struct BiNode));
       (*(*link)).value = val;
       (*(*link)).left = NULL;
       (*(*link)).right = NULL;
       PRINT("insertNode(): inserting %d\n",val);
   }
   else if( val < (*(*link)).value)
   {
       PRINT("insertNode(): moving left\n",val);
       insertNode(&((*(*link)).left),val);
   }
   else
   {
       PRINT("insertNode(): moving right\n",val);
       insertNode(&((*(*link)).right),val);
   }
   return;

}/*end insertNode---------------------------------------------*/

void BinarySearchTree::insertNode(struct BiNode **link, struct
                                  BiNode *ptr)
{
    if( *link==NULL )
    {
        (*link) = (struct BiNode*)malloc(sizeof(struct BiNode));

        (*(*link)).value = (*ptr).value;
        (*(*link)).index = (*ptr).index;
        (*(*link)).nreserved = (*ptr).nreserved;

        (*(*link)).left = NULL;
        (*(*link)).right = NULL;
        PRINT("insertNode(): inserting %d\n",(*ptr).value);
    }
    else if( (*ptr).value < (*(*link)).value)
    {
        PRINT("insertNode(): moving left\n",(*ptr).value);
        insertNode(&((*(*link)).left),ptr);
    }
    else
    {
        PRINT("insertNode(): moving right\n", (*ptr).value);
        insertNode(&((*(*link)).right),ptr);
    }
    return;

}/*end insertNode---------------------------------------------*/

struct BiNode* BinarySearchTree::findNode
(
    struct BiNode *link,
    unsigned long val )
}
{
    if(link==NULL)
    {
        return(NULL);
    }
    else if((*link).value == val)
    {
        return(link);
    }
    else if(val >= (*link).value)
    {
        return(findNode((*link).right,val));
    }
    else
    {
        return(findNode((*link).left,val));
    }

}/*end findNode---------------------------------------------*/

struct BiNode* BinarySearchTree::deleteSmallestNode(struct
               BiNode **link)
{
    if((*(*link)).left != NULL)
    {
         return(deleteSmallestNode(&((*(*link)).left)));
    }
    else
    {
         struct BiNode *temp;
         temp = *link;
         (*link) = (*(*link)).right;
         return(temp);
     }

}/*end deleteSmallestNode------------------------------------*/
void BinarySearchTree::deleteNode
(
    struct BiNode **link,
    unsigned long val )
}
{
    if( (*link)==NULL )
    {
        PRINT("deleteNode(): %d does not exist\n",val);
        return;
    }

    if(val < (*(*link)).value)
    {
        deleteNode(&((*(*link)).left),val);
    }
    else if(val > (*(*link)).value)
    {
        deleteNode(&((*(*link)).right),val);
    }
    else
    {
        /*
        have equality
        3 cases
            i)  node has no children (just delete it)
            ii) node has one child
            (set parent of current node
              to child of current node, delete current node)
            iii) node has two children/subtrees

            In the third case, get smallest/leftmost node in
            right subtree of current node. Then delete the
            leftmost node and place its value in the current
            node (retain binary tree properties)
        */

        struct BiNode *temp;
        temp = *link;

        if((*(*link)).right==NULL)
        {
            (*link) = (*(*link)).left;
        }
        else if((*(*link)).left==NULL)
        {
            (*link) = (*(*link)).right;
        }
        else
        {
            temp = deleteSmallestNode(&((*(*link)).right));
             (*(*link)).value = (*temp).value;
        }
        PRINT("deleteNode(): freeing %d\n",val);
        free(temp);


    }
    return;

}/*end deleteNode ---------------------------------------------------*/

void BinarySearchTree::deleteAll(struct BiNode **link)
{
    if((*link)==NULL)
    {
        return;
    }
    deleteAll(&((*(*link)).left));
    deleteAll(&((*(*link)).right));

    PRINT("deleteAll(): freeing %d\n",(*(*link)).value);
    free((*link));
    *link=NULL;
    return;

}/*end deleteAll-------------------------------------------*/

void BinarySearchTree::printTree(struct BiNode *link, int level)
{
    int i;
    if(link==NULL)
    {
        return;
    }

    printTree((*link).right,level+1);

    for(i=0;i<level;i++){ printf ("-");}
    printf("(%d)\n",(*link).value);

    printTree((*link).left,level+1);
    return;

}/*end printTree-----------------------------------------------------------------*/

unsigned long BinarySearchTree::getHeight(struct BiNode *link)
{
    unsigned long u;
    unsigned long v;

    if(link==NULL) { return(-1); }
    u = getHeight((*link).left);
    v = getHeight((*link).right);

    if(u > v){ return(u+1); }
    else{ return(v+1); }

}/*end getHeight----------------------------------------------------------*/

bitmap.cpp
The BitMap class is also fairly straightforward in its implementation and could be reused for something else:

/*
1 bitmap bit = 16-byte block of memory
1 bitmap byte (i.e., block) = 128-byte block of memory
*/

#define BYTES_PER_BITMAP_BIT    16
#define BYTES_PER_BITMAP_BYTE    128

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

class BitMap
{
   private:
   unsigned char *map;
   unsigned long nbytes;
   unsigned long nbits;

   public:
   BitMap(unsigned long nblocks);
   ~BitMap();
   unsigned long getByteSize();
   void setBits(int val,unsigned long nbits,unsigned long
                index);
   int getBit(unsigned long index);
   long getBitRun(unsigned long size);
   void printMap();
};


/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ definitions
+
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

BitMap::BitMap(unsigned long nblocks)
{
    unsigned long i;

    map = (unsigned char*)calloc(nblocks,1);
    if(map==NULL)
    {
        printf("BitMap::BitMap():");
        printf("could not allocate bitmap\n");
        exit(1);
    }
    nbytes = nblocks;
    nbits = nbytes*8;

    for(i=0;i<nbytes;i++){ map[i]=0xFF; }

    printf("BitMap::BitMap(): nbytes=%lu",nbytes);
    printf(", nbits=%lu\n",nbits);

    return;

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

BitMap::~BitMap()
{
    printf("BitMap::~BitMap(): freeing map[%ld]\n",nbytes);
    free(map);
    return;

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

unsigned long BitMap::getByteSize()
{
    return(nbytes);

}/*end getByteSize)---------------------------------------------------------*/

/*
set nbits to val(i.e., 0,1) starting at bit specified by index
*/
void BitMap::setBits
(
    int val,
    unsigned long nbits,
    unsigned long index )
}
{
    unsigned long bit;
    unsigned long i,j;
    unsigned char mask;
    bit=0;