Re[3]: [avr-libc-dev] malloc implementation

[Bertolt Mildner]

Hi Joerg,

And again found something. Sorry!
So here is a full revised version:

void *
malloc(size_t len)
{
        struct __freelist *current          = __flp;
        struct __freelist *before_current   = NULL;
        struct __freelist *candidate        = NULL;
        struct __freelist *before_candidate = NULL;

        size_t size = 0;
        char *cp;
        
        /*
         * Our minimum chunk size is the size of a pointer (plus the
         * size of the "sz" field, but we don't need to account for
         * this), otherwise we could not possibly fit a freelist entry
         * into the chunk later.
         */
        if (len < sizeof(struct __freelist) - sizeof(current->sz))
                len = sizeof(struct __freelist) - sizeof(current->sz);


        /*
         * Step 1: Walk the free list and try finding the smallest
         * chunk that is >= len.
         * While walking, note down the candidate (incl. its previous
         * entry). Stop walking if we found an exact match or if we
         * hit the end of the free list.
         * If we have a candidate we use it and probably split it.
         * If no candidate was found we continue in step 2.
         *
         */
        while ((current != NULL) && (size != len))
        {
          if ((current->sz >= len) &&
              ((current->sz == len) ||
               (size == 0) ||
               (size > current->sz)))
          {
            candidate = current;
            before_candidate = before_current;
            size = current->sz;
          }

          before_current = current;
          current = current->nx;
        }

        if (candadate != NULL) /* found one with sz >= len */
        {
          if ((size == len) || /* full match or too small to split */
              (size - len < sizeof(struct __freelist)))
          {
            if (before_candidate == NULL) /* match is first in list */
            {
              __flp = candidate->nx;
            }
            else
            {
              before_candidate->nx = candidate->nx;
            }

            return &(candidate->nx);
          }
          else /* split candidate */
          {
            /* resize remaining entry */
            candidate->sz -= len + sizeof(current->sz);
            
            /* create chunk to be returnd */
            cp = ((char*) (&candidate->nx)) + candidate->sz;
            current = (struct __freelist*) cp;
              
            current->sz = len;

            return &(current->nx);
          }
        }

        /*
         * Step 2: If the request could not be satisfied from a
         * freelist entry, just prepare a new chunk.  This means we
         * need to obtain more memory first.  The largest address just
         * not allocated so far is remembered in the brkval variable.
         * Under Unix, the "break value" was the end of the data
         * segment as dynamically requested from the operating system.
         * Since we don't have an operating system, just make sure
         * that we don't collide with the stack.
         */
        if (__brkval == 0)
                __brkval = __malloc_heap_start;
        cp = __malloc_heap_end;
        if (cp == 0)
                cp = STACK_POINTER() - __malloc_margin;
        size = cp - __brkval;
        /*
         * Both tests below are needed to catch the case len >= 0xfffe.
         */
        if (size >= len && size >= len + sizeof(current->sz)) {
                current = (struct freelist *)__brkval;
                __brkval += len + sizeof(current->sz);
                current->sz = len;
                return &(current->nx);
        }
        /*
         * Step 3: There's no help, just fail. :-/
         */
        return 0;
}


Bertolt

-- 
Best regards,
 Bertolt                            mailto:address@hidden