lib0037.html

Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag

<span style="background-color:d9d9d9">BitMap::BitMap(unsigned long nblocks)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>

    <span style="background-color:d9d9d9">map = (unsigned char*)calloc(nblocks,1);</span>
    <span style="background-color:d9d9d9">if(map==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("BitMap::BitMap():");</span>
        <span style="background-color:d9d9d9">printf("could not allocate bitmap\n");</span>
        <span style="background-color:d9d9d9">exit(1);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">nbytes = nblocks;</span>
    <span style="background-color:d9d9d9">nbits = nbytes*8;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nbytes;i++){ map[i]=0xFF; }</span>

    <span style="background-color:d9d9d9">printf("BitMap::BitMap(): nbytes=%lu",nbytes);</span>
    <span style="background-color:d9d9d9">printf(", nbits=%lu\n",nbits);</span>

    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end constructor--------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">BitMap::~BitMap()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">printf("BitMap::~BitMap(): freeing map[%ld]\n",nbytes);</span>
    <span style="background-color:d9d9d9">free(map);</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end destructor----------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">unsigned long BitMap::getByteSize()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">return(nbytes);</span>

<span style="background-color:d9d9d9">}/*end getByteSize)---------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">set nbits to val(i.e., 0,1) starting at bit specified by index</span>
<span style="background-color:d9d9d9">*/</span>
<span style="background-color:d9d9d9">void BitMap::setBits</span>
<span style="background-color:d9d9d9">(</span>
    <span style="background-color:d9d9d9">int val,</span>
    <span style="background-color:d9d9d9">unsigned long nbits,</span>
    <span style="background-color:d9d9d9">unsigned long index )</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long bit;</span>
    <span style="background-color:d9d9d9">unsigned long i,j;</span>
    <span style="background-color:d9d9d9">unsigned char mask;</span><a name="465"></a><a name="IDX-234"></a>
    <span style="background-color:d9d9d9">bit=0;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nbytes;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">mask = 1;</span>

        <span style="background-color:d9d9d9">for(j=0;j&lt;8;j++)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">if(bit&gt;=index)</span>
            <span style="background-color:d9d9d9">{</span>
                <span style="background-color:d9d9d9">if(bit==index+nbits){ return;}</span>
                <span style="background-color:d9d9d9">if(val){ map[i]=map[i]|mask; }</span>
                <span style="background-color:d9d9d9">else{ map[i]=map[i]&amp;(~mask); }</span>
            <span style="background-color:d9d9d9">}</span>
            <span style="background-color:d9d9d9">bit++;</span>
            <span style="background-color:d9d9d9">mask = mask*2;</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*setBits---------------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">returns that value of the specified bit (0-nbits-1)</span>
<span style="background-color:d9d9d9">or -1 if index is out of bounds</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">int BitMap::getBit(unsigned long index)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long bit;</span>
    <span style="background-color:d9d9d9">unsigned long i,j;</span>
    <span style="background-color:d9d9d9">unsigned char mask;</span>

    <span style="background-color:d9d9d9">bit=0;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nbytes;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">mask = 1;</span>

        <span style="background-color:d9d9d9">for(j=0;j&lt;8;j++)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">if(bit==index)</span>
            <span style="background-color:d9d9d9">{</span>
                <span style="background-color:d9d9d9">if(map[i]&amp;mask){ return(1); }</span>
                <span style="background-color:d9d9d9">else{ return(0); }</span>
            <span style="background-color:d9d9d9">}</span>
            <span style="background-color:d9d9d9">bit++;</span>
            <span style="background-color:d9d9d9">mask = mask*2;</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">return(-1);</span><a name="466"></a><a name="IDX-235"></a>

<span style="background-color:d9d9d9">}/*getBit----------------------------------------------------*/</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">returns the index that marks the start of 'size' bits set to 1</span>
<span style="background-color:d9d9d9">or returns -1 if such a run was not found</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">long BitMap::getBitRun(unsigned long size)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long current_size;</span>
    <span style="background-color:d9d9d9">unsigned long bit;</span>
    <span style="background-color:d9d9d9">unsigned long i,j;</span>
    <span style="background-color:d9d9d9">unsigned char mask;</span>

    <span style="background-color:d9d9d9">current_size=0;</span>
    <span style="background-color:d9d9d9">bit=0;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nbytes;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">mask = 1;</span>

        <span style="background-color:d9d9d9">for(j=0;j&lt;8;j++)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">if(map[i]&amp;mask)</span>
            <span style="background-color:d9d9d9">{</span>
                <span style="background-color:d9d9d9">current_size++;</span>
                <span style="background-color:d9d9d9">if(current_size==size){ return(bit-size+1); }</span>
            <span style="background-color:d9d9d9">}</span>
            <span style="background-color:d9d9d9">else</span>
            <span style="background-color:d9d9d9">{</span>
                 <span style="background-color:d9d9d9">current_size=0;</span>
            <span style="background-color:d9d9d9">}</span>
            <span style="background-color:d9d9d9">bit++;</span>
            <span style="background-color:d9d9d9">mask = mask*2;</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">return(-1);</span>

<span style="background-color:d9d9d9">}/*getBitRun-----------------------------------------------------------------------*/</span>

<span style="background-color:d9d9d9">void BitMap::printMap()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long bit;</span>
    <span style="background-color:d9d9d9">unsigned long i,j;</span>
    <span style="background-color:d9d9d9">unsigned char mask;</span>

    <span style="background-color:d9d9d9">bit=0;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nbytes;i++)</span><a name="467"></a><a name="IDX-236"></a>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">mask = 1;</span>
        <span style="background-color:d9d9d9">printf("byte[%u]=%x\n",i,map[i]);</span>

        <span style="background-color:d9d9d9">for(j=0;j&lt;8;j++)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">if(map[i]&amp;mask){ printf("1"); }</span>
            <span style="background-color:d9d9d9">else{ printf("0"); }</span>
            <span style="background-color:d9d9d9">bit++;</span>
            <span style="background-color:d9d9d9">mask = mask*2;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">printf("\n\n");</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end printMap------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">memmgr.cpp</h4>
<p class="first-para">This source file brings the two previous data structures together to form an actual memory manager, known fittingly as the <span class="fixed">Memory-Manager</span> class.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ declarations</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span>

<span style="background-color:d9d9d9">class MemoryManager</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">private:</span>
    <span style="background-color:d9d9d9">BinarySearchTree bst;</span>
    <span style="background-color:d9d9d9">BitMap *bmap;</span>
    <span style="background-color:d9d9d9">HANDLE handle;            //handle to heap</span>
    <span style="background-color:d9d9d9">unsigned char *mem;       //actual memory to manage</span>
    <span style="background-color:d9d9d9">unsigned long memLength;  //size in bytes of memory</span>

    <span style="background-color:d9d9d9">public:</span>
    <span style="background-color:d9d9d9">MemoryManager(unsigned long totalbytes);</span>
    <span style="background-color:d9d9d9">~MemoryManager();</span>
    <span style="background-color:d9d9d9">void* allocate(unsigned long nbytes);</span>
    <span style="background-color:d9d9d9">void release(void *ptr);</span>
    <span style="background-color:d9d9d9">void printState();</span>
<span style="background-color:d9d9d9">};</span>


<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ definitions</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span><a name="468"></a><a name="IDX-237"></a>
<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">sets the total amount of memory, no re-sizing in this case each</span>
<span style="background-color:d9d9d9">byte in the BitMap represents BYTES_BITMAP_BYTE bytes of memory</span>
<span style="background-color:d9d9d9">*/</span>
<span style="background-color:d9d9d9">MemoryManager::MemoryManager(unsigned long totalbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//init 3 dynamic objects: bmap, bst, mem[]</span>

    <span style="background-color:d9d9d9">bmap = new BitMap((totalbytes/BYTES_PER_BITMAP_BYTE)+1);</span>

    <span style="background-color:d9d9d9">bst.root_ptr=NULL;</span>

    <span style="background-color:d9d9d9">memLength = (*bmap).getByteSize()*BYTES_PER_BITMAP_BYTE;</span>

    <span style="background-color:d9d9d9">handle = GetProcessHeap();</span>
    <span style="background-color:d9d9d9">if(handle==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("MemoryManager::MemoryManager(): invalid</span>
                <span style="background-color:d9d9d9">handle\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">mem = (unsigned char*)HeapAlloc(handle,HEAP_ZERO_MEMORY,</span>
           <span style="background-color:d9d9d9">memLength);</span>

    <span style="background-color:d9d9d9">//for portability, you could use:</span>
    <span style="background-color:d9d9d9">//mem = (unsigned char*)malloc(memLength);</span>

    <span style="background-color:d9d9d9">if(mem==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("MemoryManager::MemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("could not alloc memory\n");</span>
        <span style="background-color:d9d9d9">exit(1);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">printf("MemoryManager::MemoryManager():");</span>