/*****************************************************************************/
/* */
/* 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();
}
