A fairly simple malloc implementation for the ZCPU

memory.txt

// memory.txt - a HL-ZASM malloc implementation
// by Rikki "R2ZER0" Guy 2012-13
// Released into the public domain.

// Usage:
// first call heap_format(ptr, size);
// where ptr in the pointer to a block of memory to be used as a heap
// and size is the size of the heap (in bytes)
// A simple way is to use __PROGRAMSIZE__ as a heap pointer
//
// Then just standard malloc/free/realloc


char* heap_ptr = 0;     // pointer to the heap (DO NOT CHANGE MANUALLY)
float heap_parts = 0;   // number of parts
float heap_size = 0;    // size of the heap
float heap_used = 0;    // nuber of bytes used

// heap_used is the raw number of bytes in use, including overhead
// the overhead can be calculated as heap_parts * 2
// So the actual number of bytes you have allocated is:
// num used = heap_used - heap_parts * 2
// obv. subtract heap_used from heap_size to get available memory


struct heap_part
{
    float used;
    float size; //size includes header (2)
};

void heap_format(char* hptr, hsize)
{
    if(hptr <= 0) return;
    heap_part* tpart = hptr;
    heap_ptr = hptr;
    heap_size = hsize;
    heap_parts = 2; //root part and end part
    heap_used = 4; //sizeof heap_part header * 2
    tpart.used = 0;
    tpart.size = (hsize - heap_used);
    
    tpart += tpart.size;
    
    tpart.used = 1;//end part alwyas has size as -1
    tpart.size = -1;
}

void heap_merge_sweep()
{
    heap_part* tpart = heap_ptr;
    heap_part* npart = tpart + tpart.size;
    while(npart.size > 0)
    { 
        if((tpart.used == 0) && (npart.used == 0))
        {
            heap_merge_part(tpart);
            npart = tpart + tpart.size;
        }
        else
        {
            tpart = npart;
            npart += npart.size;
        }
    }
}

void heap_merge_part(heap_part* parta)
{
    heap_part* partb = parta + parta.size;
    if(partb.used == 1) return -1;
    parta.size += partb.size;
    partb.size = 0;
    --heap_parts;
    return 1;
}

void heap_split_part(heap_part* tprt, float partasize) //split a part into two smaller parts
{
    float partbsize = tprt.size - partasize;
    tprt.size = partasize;
    tprt += partasize;
    
    tprt.used = 0;
    tprt.size = partbsize;
    ++heap_parts;
}

void heap_memcpy(char* dest, char* src, float n)
{
    float i = n;
    while(i > 0)
    {
        *(dest++) = *(src++);
        --i;
    }
}

char* malloc(float memsize)
{
    if(memsize <= 0) return 0;
    memsize += 2; //plus room for header
    heap_part* tpart = heap_ptr;
    while((tpart.size < memsize) || (tpart.used == 1))
    {
        if(tpart.size < 0) return 0; //NULL (reached end of heap)
        tpart += tpart.size;
    }
    
    if((tpart.size) > (memsize + 3))
    {
        heap_split_part(tpart, memsize);
    }
    
    tpart.used = 1;
    return tpart + 2;
}

void free(char* mem)
{
    if(mem <= 0) return;
    heap_part* tpart = mem - 2;
    tpart.used = 0;
    
    heap_part* npart = tpart + tpart.size;
    while(npart.used == 0)
    {
        heap_merge_part(tpart);
        npart = tpart + tpart.size;
    }
}

char* realloc(char* mem, float memsize)
{
    if(mem <= 0) return;
    heap_part* tpart = mem - 2;
    float osize = tpart.size - 2;
    
    if((memsize + 5) < tpart.size) // shrinking
    {
        heap_split_part(tpart, memsize + 2); //split the part to avoid wasting space
        //possibly merge the new part with the next part
        heap_part* ttpart = tpart + tpart.size;
        heap_part* tttpart = ttpart + ttpart.size;
        if(tttpart.used == 0) heap_merge_part(ttpart);
        return mem;
    }
    else //expanding
    {
        if(memsize <= osize)
        {
            //nothing to do, already fits
            return mem;
        }
        else
        {
            //attempt to expand in place
            float reqmemsize = memsize + 2;
            heap_part* npart = tpart + tpart.size;
            while(npart.used == 0)
            {
                heap_merge_part(tpart);
                if(tpart.size >= reqmemsize) return mem; //expanding successful
            }
            
            //if we get here, expanding was not successful - malloc and copy :(
            char* newmem = malloc(memsize);
            if(newmem <= 0) return 0; // just can't do it D:
            heap_memcpy(newmem, mem, osize);
            free(mem);
            return newmem;
        }
    }
}