lib0037.html

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

    <span style="background-color:d9d9d9">printf("mallloc() mem[%lu]\n",memLength);</span>

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

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

<span style="background-color:d9d9d9">MemoryManager::~MemoryManager()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//release resources for objects: bmap, bst, mem[]</span>

    <span style="background-color:d9d9d9">delete(bmap);</span>

    <span style="background-color:d9d9d9">bst.deleteAll(&amp;(bst.root_ptr));</span>

    <span style="background-color:d9d9d9">if(HeapFree(handle,HEAP_NO_SERIALIZE,mem)==0)</span>
    <span style="background-color:d9d9d9">{</span><a name="469"></a><a name="IDX-238"></a>
        <span style="background-color:d9d9d9">printf("MemoryManager::~MemoryManager(): HeapFree()</span>
                <span style="background-color:d9d9d9">failed\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//for portability, you could use:</span>
    <span style="background-color:d9d9d9">//free(mem);</span>

    <span style="background-color:d9d9d9">printf("MemoryManager::~MemoryManager():");</span>
    <span style="background-color:d9d9d9">printf("free() mem[%lu]\n",memLength);</span>

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

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

<span style="background-color:d9d9d9">void* MemoryManager::allocate(unsigned long nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long run_bits;</span>
    <span style="background-color:d9d9d9">long index;</span>
    <span style="background-color:d9d9d9">struct BiNode node;</span>

    <span style="background-color:d9d9d9">PRINT("MemoryManager::allocate(): request %lu bytes\n",</span>
           <span style="background-color:d9d9d9">nbytes);</span>

    <span style="background-color:d9d9d9">//translate nbytes into # of bits in BitMap</span>

    <span style="background-color:d9d9d9">run_bits = (nbytes/BYTES_PER_BITMAP_BIT)+1;</span>

    <span style="background-color:d9d9d9">PRINT("MemoryManager::allocate(): run_bits=%lu\n",run_bits);</span>

    <span style="background-color:d9d9d9">//look for # of free bits in BitMap</span>

    <span style="background-color:d9d9d9">index = ((*bmap).getBitRun(run_bits));</span>

    <span style="background-color:d9d9d9">PRINT("MemoryManager::allocate(): found run of %lu bits</span>
          <span style="background-color:d9d9d9">",run_bits);</span>
    <span style="background-color:d9d9d9">PRINT("at %lu\n",index);</span>

    <span style="background-color:d9d9d9">if(index==-1){ return(NULL); }</span>

    <span style="background-color:d9d9d9">//reserved bits in BitMap</span>

    <span style="background-color:d9d9d9">(*bmap).setBits(0,run_bits,index);</span>

    <span style="background-color:d9d9d9">node.value = (unsigned long)(&amp;mem[index*16]);</span>
    <span style="background-color:d9d9d9">node.index = index;</span>
    <span style="background-color:d9d9d9">node.nreserved = run_bits;</span>

    <span style="background-color:d9d9d9">bst.insertNode(&amp;(bst.root_ptr),&amp;node);</span>

    <span style="background-color:d9d9d9">//return memory represented by BitMap bits</span><a name="470"></a><a name="IDX-239"></a>

    <span style="background-color:d9d9d9">PRINT("MemoryManager::allocate(): address=%lu\n",&amp;mem</span>
          <span style="background-color:d9d9d9">[index*16]);</span>

    <span style="background-color:d9d9d9">return((void*)&amp;mem[index*16]);</span>

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

<span style="background-color:d9d9d9">void MemoryManager::release(void *addr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">struct BiNode *ptr;</span>

    <span style="background-color:d9d9d9">ptr = bst.findNode(bst.root_ptr,(unsigned long)addr);</span>
    <span style="background-color:d9d9d9">if(ptr!=NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">PRINT("MemoryManager::release(): addr=%lu\n",(unsigned</span>
               <span style="background-color:d9d9d9">long)addr);</span>
        <span style="background-color:d9d9d9">(*bmap).setBits(1,(*ptr).nreserved,(*ptr).index);</span>
        <span style="background-color:d9d9d9">bst.deleteNode(&amp;(bst.root_ptr),(unsigned long)addr);</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

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

<span style="background-color:d9d9d9">void MemoryManager::printState()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">printf("-------------------------------------------------\n");</span>
    <span style="background-color:d9d9d9">(*bmap).printMap();</span>
    <span style="background-color:d9d9d9">printf ("------------------------------------------------\n");</span>
    <span style="background-color:d9d9d9">bst.printTree(bst.root_ptr,0);</span>
    <span style="background-color:d9d9d9">printf ("------------------------------------------------\n");</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end printState----------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">mallocV1.cpp</h4>
<p class="first-para">This file supplies wrappers that allow the <span class="fixed">MemoryManager</span> class to be used under the guise of the <span class="fixed">newMalloc()</span> and <span class="fixed">newFree()</span> functions so that existing applications will only have to be slightly modified.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</span>

<span style="background-color:d9d9d9">// these DEBUG_XXX macros insert printf() statements in the</span>
   <span style="background-color:d9d9d9">final executable</span>
<span style="background-color:d9d9d9">//#define DEBUG_TREE</span>
<span style="background-color:d9d9d9">//#define DEBUG_BITMAP</span><a name="471"></a><a name="IDX-240"></a>
<span style="background-color:d9d9d9">//#define DEBUG_MEM_MGR</span>
<span style="background-color:d9d9d9">//#define DEBUG_MALLOCV1</span>

<span style="background-color:d9d9d9">#include&lt;tree.cpp&gt;</span>
<span style="background-color:d9d9d9">#include&lt;bitmap.cpp&gt;</span>
<span style="background-color:d9d9d9">#include&lt;memmgr.cpp&gt;</span>

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">wrapper functions</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">MemoryManager *mmptr;</span>

<span style="background-color:d9d9d9">void initMemMgr(unsigned long totalbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">mmptr = new MemoryManager(totalbytes);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void closeMemMgr()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">delete(mmptr);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void *newMalloc(unsigned long size)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr = (*mmptr).allocate(size);</span>

<span style="background-color:d9d9d9">#ifdef DEBUG_MALLOCV1</span>
    <span style="background-color:d9d9d9">(*mmptr).printState();</span>
<span style="background-color:d9d9d9">#endif</span>

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

<span style="background-color:d9d9d9">void newFree(void *ptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">(*mmptr).release(ptr);</span>

<span style="background-color:d9d9d9">#ifdef DEBUG_MALLOCV1</span>
    <span style="background-color:d9d9d9">(*mmptr).printState();</span>
<span style="background-color:d9d9d9">#endif</span>

    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">The <span class="fixed">DEBUG_XXX</span> macros, defined at the top of this file insert, activate a set of debugging <span class="fixed">printf()</span> statements in each file. For the performance test run, I commented these macros out so that none of the <span class="fixed">printf()</span> statements made it into the build.</p>
<a name="472"></a><a name="IDX-241"></a>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">perform.cpp</h4>
<p class="first-para">In addition to the <span class="fixed">PerformanceTest</span> class described earlier, this file also contains the definition of the <span class="fixed">PerformanceTestDriver()</span> function that will be called from <span class="fixed">main()</span>.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">void PerformanceTestDriver()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">double p[8] = {.15, .20, .35, .20, .02, .04, .02, .02};</span>
    <span style="background-color:d9d9d9">unsigned long x[8] = {16,32,64,128,256,512,1024,4096};</span>

    <span style="background-color:d9d9d9">struct TestData td;</span>
    <span style="background-color:d9d9d9">td.dptr = p;</span>
    <span style="background-color:d9d9d9">td.lptr = x;</span>
    <span style="background-color:d9d9d9">td.samplesize = 1024;</span>
    <span style="background-color:d9d9d9">td.length = 8;</span>

    <span style="background-color:d9d9d9">PerformanceTest pt = PerformanceTest(&amp;td);</span>
    <span style="background-color:d9d9d9">printf("msecs=%lu\n",pt.runTest());</span>

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

<span style="background-color:d9d9d9">}/*end PerformanceTestDriver--------------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">driver.cpp</h4>
<p class="first-para">This file is where everything comes together. The <span class="fixed">main()</span> function contains a call to <span class="fixed">debugTest()</span> and <span class="fixed">PerformanceTestDriver()</span>. For diagnostic builds, I activate the debug macros in <span class="fixed">mallocV1.cpp</span> and then comment out the <span class="fixed">PerformanceTestDriver()</span> function call. For the build that tests performance, I comment out the debug macros and the <span class="fixed">debugTest()</span> function invocation. The version of <span class="fixed">driver.cpp</span> below is set up to build an executable that runs a performance test.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;mallocV1.cpp&gt;</span>
<span style="background-color:d9d9d9">#include&lt;perform.cpp&gt;</span>

<span style="background-color:d9d9d9">void debugTest()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr[10];</span>
    <span style="background-color:d9d9d9">int i;</span>

    <span style="background-color:d9d9d9">initMemMgr(270);</span>

    <span style="background-color:d9d9d9">ptr[0] = newMalloc(8);</span>
    <span style="background-color:d9d9d9">ptr[1] = newMalloc(12);</span>
    <span style="background-color:d9d9d9">ptr[2] = newMalloc(33);</span>
    <span style="background-color:d9d9d9">ptr[3] = newMalloc(1);</span>
    <span style="background-color:d9d9d9">ptr[4] = newMalloc(122);</span><a name="473"></a><a name="IDX-242"></a>
    <span style="background-color:d9d9d9">ptr[5] = newMalloc(50);</span>

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

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

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

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
     <span style="background-color:d9d9d9">//for the debug test, should activate debug macros in</span>
     <span style="background-color:d9d9d9">//mallocVx.cpp</span>
     <span style="background-color:d9d9d9">//debugTest();</span>

     <span style="background-color:d9d9d9">//for the performance test, should comment out debug macros</span>
     <span style="background-color:d9d9d9">PerformanceTestDriver();</span>
     <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main--------------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">