lib0043.html

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

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

    <span style="background-color:d9d9d9">//yet more sanity checks</span><a name="596"></a><a name="IDX-322"></a>
    <span style="background-color:d9d9d9">if((STATE(index)==FREE)   || //region if free</span>
       <span style="background-color:d9d9d9">(PREV(index)&gt;=index)   || //previous element not previous</span>
       <span style="background-color:d9d9d9">(NEXT(index)&gt;=size)    || //next is beyond the end</span>
       <span style="background-color:d9d9d9">(SIZE(index)&gt;=size)    || //size region greater than whole</span>
       <span style="background-color:d9d9d9">(SIZE(index)==0))         //no size at all</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("release(): referencing invalid region\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">merge(PREV(index),index,NEXT(index));</span>

<span style="background-color:d9d9d9">#ifdef  DEBUG_MS_MEM_MGR</span>
    <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("release(): post merge layout\n");</span>
    <span style="background-color:d9d9d9">printState();</span>
<span style="background-color:d9d9d9">#endif</span>

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

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

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::merge(U4 prev,U4 current,U4 next)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">first handle special cases of region at end(s)</span>
    <span style="background-color:d9d9d9">prev=0                    low end</span>
    <span style="background-color:d9d9d9">next=0                    high end</span>
    <span style="background-color:d9d9d9">prev=0 and next=0         only 1 list element</span>
    <span style="background-color:d9d9d9">*/</span>

    <span style="background-color:d9d9d9">if(prev==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">if(next==0)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">else if((STATE(next)==OCCUPIED)||(STATE(next)==TESTING))</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">else if(STATE(next)==FREE)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">U4 temp;</span>

            <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
            <span style="background-color:d9d9d9">MSG0("merging to NEXT\n");</span>

            <span style="background-color:d9d9d9">STATE(current)=FREE;</span><a name="597"></a><a name="IDX-323"></a>
            <span style="background-color:d9d9d9">SIZE(current)=SIZE(current)+SIZE(next)+SZ_HEADER;</span>
            <span style="background-color:d9d9d9">NEXT(current)=NEXT(next);</span>

            <span style="background-color:d9d9d9">temp = NEXT(next);</span>
            <span style="background-color:d9d9d9">if(temp!=0){ PREV(temp)=current; }</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if(next==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">if((STATE(prev)==OCCUPIED)||(STATE(prev)==TESTING))</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">else if(STATE(prev)==FREE)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
            <span style="background-color:d9d9d9">MSG0("merging to PREV\n");</span>
            <span style="background-color:d9d9d9">SIZE(prev)=SIZE(prev)+SIZE(current)+SZ_HEADER;</span>
            <span style="background-color:d9d9d9">NEXT(prev)=NEXT(current);</span>
        <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">/*</span>
        <span style="background-color:d9d9d9">cases:</span>
                <span style="background-color:d9d9d9">OTO      -&gt;    OFO</span>
                <span style="background-color:d9d9d9">TTT            TFT</span>
                <span style="background-color:d9d9d9">TTO            TFO</span>
                <span style="background-color:d9d9d9">OTT            OFT</span>

                <span style="background-color:d9d9d9">OTF            O[F]</span>
                <span style="background-color:d9d9d9">TTF            T[F]</span>
                <span style="background-color:d9d9d9">FTO            [F]O</span>
                <span style="background-color:d9d9d9">FTT            [F]T</span>
                <span style="background-color:d9d9d9">FTF            [F]</span>
    <span style="background-color:d9d9d9">*/</span>

    <span style="background-color:d9d9d9">else if((STATE(prev)==OCCUPIED)&amp;&amp;(STATE(next)==OCCUPIED))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==TESTING)&amp;&amp;(STATE(next)==TESTING))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==TESTING)&amp;&amp;(STATE(next)==OCCUPIED))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==OCCUPIED)&amp;&amp;(STATE(next)==TESTING))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span><a name="598"></a><a name="IDX-324"></a>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==OCCUPIED)&amp;&amp;(STATE(next)==FREE))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">U4 temp;</span>

        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
        <span style="background-color:d9d9d9">MSG0("merging to NEXT\n");</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
        <span style="background-color:d9d9d9">SIZE(current)=SIZE(current)+SIZE(next)+SZ_HEADER;</span>
        <span style="background-color:d9d9d9">NEXT(current)=NEXT(next);</span>

        <span style="background-color:d9d9d9">temp = NEXT(next);</span>
        <span style="background-color:d9d9d9">if(temp!=0){ PREV(temp)=current; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==TESTING)&amp;&amp;(STATE(next)==FREE))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">U4 temp;</span>

        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
        <span style="background-color:d9d9d9">MSG0("merging to NEXT\n");</span>
        <span style="background-color:d9d9d9">STATE(current)=FREE;</span>
        <span style="background-color:d9d9d9">SIZE(current)=SIZE(current)+SIZE(next)+SZ_HEADER;</span>
        <span style="background-color:d9d9d9">NEXT(current)=NEXT(next);</span>

        <span style="background-color:d9d9d9">temp = NEXT(next);</span>
        <span style="background-color:d9d9d9">if(temp!=0){ PREV(temp)=current; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==FREE)&amp;&amp;(STATE(next)==OCCUPIED))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
        <span style="background-color:d9d9d9">MSG0("merging to PREV\n");</span>
        <span style="background-color:d9d9d9">SIZE(prev)=SIZE(prev)+SIZE(current)+SZ_HEADER;</span>
        <span style="background-color:d9d9d9">NEXT(prev)=NEXT(current);</span>
        <span style="background-color:d9d9d9">PREV(next)=prev;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==FREE)&amp;&amp;(STATE(next)==TESTING))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
        <span style="background-color:d9d9d9">MSG0("merging to PREV\n");</span>
        <span style="background-color:d9d9d9">SIZE(prev)=SIZE(prev)+SIZE(current)+SZ_HEADER;</span>
        <span style="background-color:d9d9d9">NEXT(prev)=NEXT(current);</span>
        <span style="background-color:d9d9d9">PREV(next)=prev;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else if((STATE(prev)==FREE)&amp;&amp;(STATE(next)==FREE))</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">U4 temp;</span>

        <span style="background-color:d9d9d9">MSG0("MarkSweepMemoryManager::merge():");</span>
        <span style="background-color:d9d9d9">MSG0("merging with both sides\n");</span>
        <span style="background-color:d9d9d9">SIZE(prev)=SIZE(prev) +</span><a name="599"></a><a name="IDX-325"></a>
                   <span style="background-color:d9d9d9">SIZE(current)+SZ_HEADER+</span>
                   <span style="background-color:d9d9d9">SIZE(next)+SZ_HEADER;</span>
        <span style="background-color:d9d9d9">NEXT(prev)=NEXT(next);</span>

        <span style="background-color:d9d9d9">temp = NEXT(next);</span>
        <span style="background-color:d9d9d9">if(temp!=0){ PREV(temp)=prev; }</span>
    <span style="background-color:d9d9d9">}</span>

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

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

<span style="background-color:d9d9d9">void MarkSweepMemoryManager::printState()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 i;</span>
    <span style="background-color:d9d9d9">U4 current;</span>

    <span style="background-color:d9d9d9">i=0;</span>
    <span style="background-color:d9d9d9">current=START;</span>

    <span style="background-color:d9d9d9">while(NEXT(current)!=0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("%lu) [P=%lu]",i,PREV(current));</span>
        <span style="background-color:d9d9d9">printf("[addr=%lu]",current);</span>
        <span style="background-color:d9d9d9">printf("[St=%s]",stateStr[STATE(current)]);</span>
        <span style="background-color:d9d9d9">printf("[Sz=%lu]",SIZE(current));</span>
        <span style="background-color:d9d9d9">printf("[N=%lu]\n",NEXT(current));</span>
        <span style="background-color:d9d9d9">current = NEXT(current);</span>
        <span style="background-color:d9d9d9">i++;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//print the last list element</span>

    <span style="background-color:d9d9d9">printf("%lu) [P=%lu]",i,PREV(current));</span>
    <span style="background-color:d9d9d9">printf("[addr=%lu]",current);</span>
    <span style="background-color:d9d9d9">printf("[St=%s]",stateStr[STATE(current)]);</span>
    <span style="background-color:d9d9d9">printf("[Sz=%lu]",SIZE(current));</span>
    <span style="background-color:d9d9d9">printf("[N=%lu]\n",NEXT(current));</span>

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

<span style="background-color:d9d9d9">}/*end printState---------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="600"></a><a name="ch05lev2sec7"></a>Tests</h3>
<p class="first-para">I performed two