lib0038.html

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

    <span style="background-color:d9d9d9">private:</span>
    <span style="background-color:d9d9d9">HANDLE handle;</span>
    <span style="background-color:d9d9d9">U1  *ram;    /*memory storage*/</span>
    <span style="background-color:d9d9d9">U4  size;</span>

    <span style="background-color:d9d9d9">void split(U4 addr,U4 nbytes);</span>
    <span style="background-color:d9d9d9">void merge(U4 prev,U4 current,U4 next);</span>

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

    <span style="background-color:d9d9d9">SequentialFitMemoryManager(U4 nbytes);</span>
    <span style="background-color:d9d9d9">~SequentialFitMemoryManager();</span><a name="494"></a><a name="IDX-253"></a>
    <span style="background-color:d9d9d9">void*allocate(U4 nbytes);</span>
    <span style="background-color:d9d9d9">void release(void* addr);</span>
    <span style="background-color:d9d9d9">void printState();</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">SequentialFitMemoryManager::SequentialFitMemoryManager(U4</span>
          <span style="background-color:d9d9d9">nbytes)</span>
<span style="background-color:d9d9d9">{</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("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("SequentialFitMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("invalid handle\n");</span>
        <span style="background-color:d9d9d9">exit(1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">ram = (U1*)HeapAlloc(handle,HEAP_ZERO_MEMORY,nbytes);</span>

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


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

    <span style="background-color:d9d9d9">if(size&lt;=SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("SequentialFitMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("not enough memory fed to constructor\n");</span>
        <span style="background-color:d9d9d9">exit(1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">PREV(START)=0;</span>
    <span style="background-color:d9d9d9">NEXT(START)=0;</span>
    <span style="background-color:d9d9d9">STATE(START)=FREE;</span>
    <span style="background-color:d9d9d9">SIZE(START)=size-SZ_HEADER;</span>

    <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("SequentialFitMemoryManager(%lu)\n", nbytes);</span>

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

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

<span style="background-color:d9d9d9">SequentialFitMemoryManager::~SequentialFitMemoryManager()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if(HeapFree(handle,HEAP_NO_SERIALIZE,ram)==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("SequentialFitMemoryManager::");</span><a name="495"></a><a name="IDX-254"></a>
        <span style="background-color:d9d9d9">printf("~SequentialFitMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("could not free heap storage\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(ram);</span>

    <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("~SequentialFitMemoryManager()");</span>
    <span style="background-color:d9d9d9">MSG1("free ram[%lu]\n",size);</span>
    <span style="background-color:d9d9d9">return;</span>

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

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">U4 nbytes    -    number of bytes required</span>
<span style="background-color:d9d9d9">returns address of first byte of memory region allocated</span>
<span style="background-color:d9d9d9">( or NULL if cannot allocate a large enough block )</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">void* SequentialFitMemoryManager::allocate(U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 current;</span>

    <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("allocate(%lu)\n",nbytes);</span>

    <span style="background-color:d9d9d9">if(nbytes==0)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("allocate(): zero bytes requested\n");</span>
        <span style="background-color:d9d9d9">return(NULL);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//traverse the linked list, starting with first element</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">if((SIZE(current)&gt;=nbytes)&amp;&amp;(STATE(current)==FREE))</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">split(current,nbytes);</span>
            <span style="background-color:d9d9d9">return((void*)&amp;ram[current]);</span>
        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">current = NEXT(current);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//handle the last block ( which has NEXT(current)=0 )</span>

    <span style="background-color:d9d9d9">if((SIZE(current)&gt;=nbytes)&amp;&amp;(STATE(current)==FREE))</span><a name="496"></a><a name="IDX-255"></a>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">split(current,nbytes);</span>
        <span style="background-color:d9d9d9">return((void*)&amp;ram[current]);</span>
    <span style="background-color:d9d9d9">}</span>

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

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

<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">breaks [free] region into [alloc] [free] pair, if possible</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">void SequentialFitMemoryManager::split(U4 addr, U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">want payload to have enough room for</span>
    <span style="background-color:d9d9d9">nbytes = size of request</span>
    <span style="background-color:d9d9d9">SZ_HEADER = header for new region</span>
    <span style="background-color:d9d9d9">SZ_HEADER = payload for new region (arbitrary 13 bytes)</span>
    <span style="background-color:d9d9d9">*/</span>

    <span style="background-color:d9d9d9">if(SIZE(addr)&gt;= nbytes+SZ_HEADER+SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">U4 oldnext;</span>
        <span style="background-color:d9d9d9">U4 oldprev;</span>
        <span style="background-color:d9d9d9">U4 oldsize;</span>

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

        <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("split():split=YES\n");</span>

        <span style="background-color:d9d9d9">oldnext=NEXT(addr);</span>
        <span style="background-color:d9d9d9">oldprev=PREV(addr);</span>
        <span style="background-color:d9d9d9">oldsize=SIZE(addr);</span>

        <span style="background-color:d9d9d9">newaddr = addr + nbytes + SZ_HEADER;</span>

        <span style="background-color:d9d9d9">NEXT(addr)=newaddr;</span>
        <span style="background-color:d9d9d9">PREV(addr)=oldprev;</span>
        <span style="background-color:d9d9d9">STATE(addr)=OCCUPIED;</span>
        <span style="background-color:d9d9d9">SIZE(addr)=nbytes;</span>

        <span style="background-color:d9d9d9">NEXT(newaddr)=oldnext;</span>
        <span style="background-color:d9d9d9">PREV(newaddr)=addr;</span>
        <span style="background-color:d9d9d9">STATE(newaddr)=FREE;</span>
        <span style="background-color:d9d9d9">SIZE(newaddr)=oldsize-nbytes-SZ_HEADER;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">else</span>
    <span style="background-color:d9d9d9">{</span><a name="497"></a><a name="IDX-256"></a>
        <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("split(): split=NO\n");</span>
        <span style="background-color:d9d9d9">STATE(addr)=OCCUPIED;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

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

<span style="background-color:d9d9d9">void SequentialFitMemoryManager::release(void *addr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 free;    //index into ram[]</span>

    <span style="background-color:d9d9d9">if(addr==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("release(): cannot release NULL pointer\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("release(%lu)\n",addr);</span>

    <span style="background-color:d9d9d9">//perform sanity check to make sure address is kosher</span>

    <span style="background-color:d9d9d9">if( (addr&gt;= (void*)&amp;ram[size]) || (addr&lt; (void*)&amp;ram[0]) )</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("release(): address out of bounds\n");</span>
        <span style="background-color:d9d9d9">return;</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">//translate void* addr to index in ram[]</span>

    <span style="background-color:d9d9d9">free = (U4)( ((U1*)addr) - &amp;ram[0]);</span>

    <span style="background-color:d9d9d9">MSG0("SequentialFitMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("address resolves to index %lu\n",free);</span>