/*****************************************************************************/

/*      */

/*  MALLOC - Allocate a packet of a given size, and return pointer to it.    */

/*      */

/*****************************************************************************/

void *malloc(size_t size)

{

    memsz_t allocsize;

    PACKET *current, *next, *prev;

 

    if (check_alloc_size(size) == 0) return 0;

 

    allocsize = (memsz_t)size;

 

    if (allocsize == 0) return 0;

 

    /*-----------------------------------------------------------------------*/

    /* We may need to adjust the size of the allocation request to ensure    */

    /* that the address of the field "next_free" remains strictly aligned    */

    /* in all packets on the free list.      */

    /*-----------------------------------------------------------------------*/

    if ((allocsize ^ OVERHEAD) & 1) ++allocsize;

 

    _lock();

 

    if (first_call) minit();

 

    current = sys_free;

    prev = 0;

 

    /*-----------------------------------------------------------------------*/

    /* Find the first block large enough to hold the requested allocation    */

    /*-----------------------------------------------------------------------*/

    while (current != LIMIT && -current->packet_size < allocsize)

    {

prev = current;

current = current->next_free;

    }

 

    if (current == LIMIT)

    {

        /*-------------------------------------------------------------------*/

        /* No block large enough was found, so return NULL.      */

        /*-------------------------------------------------------------------*/

_unlock();

return 0;

    }

 

    if (-current->packet_size > (allocsize + OVERHEAD + MINSIZE))

    {

        /*-------------------------------------------------------------------*/

        /* The packet is larger than needed; split the block and mark the    */

        /* smaller-addressed block as used.  The smaller-addressed block     */

        /* was chosen as a way to ensure that freed blocks get recycled      */

        /* before allocations are made from the large original free block.   */

        /* However, this may tend to increase the length of the free list    */

        /* search for a large enough block.      */

        /*-------------------------------------------------------------------*/

        /* Knuth's algorithm 2.5a instead allocates the larger-addressed     */

        /* block to the user.  This tends to leave the largest free blocks   */

        /* at the beginning of the free list.  Knuth's 2.5a' uses a "rover"  */

        /* pointer to prevent small free blocks from being concentrated in   */

        /* any part of the list.      */

        /*-------------------------------------------------------------------*/

next = (PACKET *)((char *)current + allocsize + OVERHEAD);

next->packet_size=current->packet_size+allocsize+OVERHEAD;/*NEG==FREE*/

#ifdef DEBUG

next->guard = GUARDWORD;

#endif

current->packet_size = allocsize; /* POSITIVE==IN USE */

 

if (prev) prev->next_free = next;

else      sys_free        = next;

 

next->next_free = current->next_free;

    }

    else

    {

        /*-------------------------------------------------------------------*/

        /* Allocate the whole block and remove it from the free list.      */

        /*-------------------------------------------------------------------*/

if (prev) prev->next_free = current->next_free;

else      sys_free        = current->next_free;

 

current->packet_size = -current->packet_size; /* POSITIVE==IN USE */

    }

 

    _unlock();

    return &(current->next_free);

}

 

/*****************************************************************************/

/*      */

/*  FREE - Return a packet allocated by malloc to free memory pool.      */

/*      */

/*****************************************************************************/

void free(void *userptr)

{

    PACKET *sysblock, *next, *prev;

 

    if (userptr == 0) return; /* HANDLE NULL POINTER */

 

    _lock();

 

    next = sys_free;

    prev = 0;

    sysblock = (PACKET *)((char *)userptr - OVERHEAD);

 

    /*-----------------------------------------------------------------------*/

    /* Search the free list for the *free* packets physically closest to     */

    /* the packet to be freed.  PREV is the closest free packet with a      */

    /* smaller address, and NEXT is the closest free packet with a larger    */

    /* address.      */

    /*-----------------------------------------------------------------------*/

    while (next < sysblock)

    {

prev = next;

next = next->next_free;

    }

 

    /*-----------------------------------------------------------------------*/

    /* Coallesce with next block if possible.      */

    /*-----------------------------------------------------------------------*/

    if ((char *)sysblock + sysblock->packet_size + OVERHEAD == (char *)next)

    {

sysblock->next_free = next->next_free;

sysblock->packet_size += -next->packet_size + OVERHEAD; /* POS==USED */

#ifdef DEBUG

next->guard = 0;

#endif

    }

    else sysblock->next_free = next; /* START TO PUT INTO LIST */

 

    if (prev) /* ARE WE THE NEW HEAD OF THE LIST */

    {

        /*-------------------------------------------------------------------*/

        /* sysblock is not the head of the free list; try to coallesce with  */

        /* prev      */

        /*-------------------------------------------------------------------*/

if ((char *)prev - prev->packet_size + OVERHEAD == (char *)sysblock)

{

    prev->next_free = sysblock->next_free;

    prev->packet_size += -sysblock->packet_size - OVERHEAD;/*NEG==FREE*/

#ifdef DEBUG

    sysblock->guard = 0;

#endif

}

else

{

    prev->next_free = sysblock;

    sysblock->packet_size = -sysblock->packet_size; /* NEGATIVE==FREE */

}

    }

    else

    {

sys_free = sysblock;

sysblock->packet_size = -sysblock->packet_size; /* NEGATIVE==FREE */

    }

    _unlock();

}