lib0042.html

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

<span style="background-color:d9d9d9">class RefCountMemoryManager</span>
<span style="background-color:d9d9d9">{</span>
    <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">int checkAddress(void *addr);</span>
    <span style="background-color:d9d9d9">int checkIndex(U4 free);</span>
    <span style="background-color:d9d9d9">void release(U4 free);</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">RefCountMemoryManager(U4 nbytes);</span>
    <span style="background-color:d9d9d9">~RefCountMemoryManager();</span>

    <span style="background-color:d9d9d9">void*allocate(U4 nbytes);</span>
    <span style="background-color:d9d9d9">void inc(void *addr);</span>
    <span style="background-color:d9d9d9">void dec(void *addr);</span>
    <span style="background-color:d9d9d9">void printState();</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">RefCountMemoryManager::RefCountMemoryManager(U4 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("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("RefCountMemoryManager():");</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("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("RefCountMemoryManager():");</span>
        <span style="background-color:d9d9d9">printf("not enough memory fed to constructor\n");</span><a name="554"></a><a name="IDX-292"></a>
        <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">COUNT(START)=0;</span>
    <span style="background-color:d9d9d9">SIZE(START)=size-SZ_HEADER;</span>

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

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

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

<span style="background-color:d9d9d9">RefCountMemoryManager::~RefCountMemoryManager()</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("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">printf("~RefCountMemoryManager():");</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("RefCountMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG0("~RefCountMemoryManager()");</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* RefCountMemoryManager::allocate(U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">U4 current;</span>

    <span style="background-color:d9d9d9">MSG0("RefCountMemoryManager::");</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("RefCountMemoryManager::");</span><a name="555"></a><a name="IDX-293"></a>
        <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;(COUNT(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;(COUNT(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">return(NULL);</span>

<span style="background-color:d9d9d9">}/*end allocation----&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--&mdash;--------------*/</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 RefCountMemoryManager::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 16 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("RefCountMemoryManager::");</span><a name="556"></a><a name="IDX-294"></a>
        <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">COUNT(addr)=1;</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">COUNT(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>
        <span style="background-color:d9d9d9">MSG0("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0 "split () : split=NO\n");</span>
        <span style="background-color:d9d9d9">COUNT(addr)=1;</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">int RefCountMemoryManager::checkAddress(void *addr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">if(addr==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("checkAddress(): cannot release NULL pointer\n");</span>
        <span style="background-color:d9d9d9">return(FALSE);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">MSG0("RefCountMemoryManager::");</span>
    <span style="background-color:d9d9d9">MSG1("checkAddress(%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("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("checkAddress(): address out of bounds\n");</span>
        <span style="background-color:d9d9d9">return(FALSE);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">return(TRUE);</span><a name="557"></a><a name="IDX-295"></a>

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

<span style="background-color:d9d9d9">int RefCountMemoryManager::checkIndex(U4 free)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//a header always occupies first SZ_HEADER bytes of storage</span>

    <span style="background-color:d9d9d9">if(free&lt;SZ_HEADER)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">MSG0("RefCountMemoryManager::");</span>
        <span style="background-color:d9d9d9">MSG0("checkIndex(): address in first 16 bytes\n");</span>
        <span style="background-color:d9d9d9">return(FALSE);</span>
    <span style="background-color:d9d9d9">}</span>