/*--------------------------------------------------------------------------
MALLOC.C is part of the CARM Compiler package from Keil Software.
Copyright (c) 1995 - 2005 Keil Software.  All rights reserved.
--------------------------------------------------------------------------*/

#include "ican_STDLIB.H"


struct __mp__  {                   /* memory pool */
  struct __mp__   *next;           /* single-linked list */
  unsigned int      len;           /* length of following block */
};

extern struct __mp__ *__mp__;      /* Memory Pool Header */
#define	HLEN	(sizeof(struct __mp__))

/*  Memory pool header:  __mp__ points to the first available.
 *
 *  Note that the list is maintained in address order.  __mp__ points to the
 *  block with the lowest address.  That block points to the block with the
 *  next higher address and so on.
 *
 *  Memory is laid out as follows:
 *
 *  {[NEXT | LEN] [BLOCK (LEN bytes)]} {[NEXT | LEN][BLOCK] } ...
 *
 *  Note that the size of a node is:
 *          mp.len + sizeof (struct mp_b)
 */


#define MIN_BLOCK	(HLEN * 2)


void *reg_malloc (unsigned int size)   {
  struct __mp__  *q;      /* ptr to free block */
  struct __mp__  *p;      /* q->next */
  unsigned int k;         /* space remaining in the allocated block */
 
/*  Make sure that block is word aligned                                    */
  size = (size + 3) & ~3L;

/*  Initialization:  Q is the pointer to the next available block.          */
  q = (struct __mp__ *) &__mp__;

/*  End-Of-List:  P points to the next block.  If that block DNE (P==NULL),
 *  we are at the end of the list.                                          */

  while (1)  {
    p = q->next;
    if (!p)  return (NULL); /* FAILURE */

/*  Found Space:  If block is large enough, reserve if.  Otherwise, copy P
 *  to Q and try the next free block.                                       */
    if (p->len >= size) break;
    q = p;
  }

/*  Reserve P:  Use at least part of the P block to satisfy the allocation
 *  request.  At this time, the following pointers are setup:
 *  P points to the block from which we allocate Q->next points to P        */

  k = p->len - size;		/* calc. remaining bytes in block */

  if (k < MIN_BLOCK)  {		/* rem. bytes too small for new block */
    q->next = p->next;
    return (&p[1]);		    /* SUCCESS */
  }

/*  Split P Block:  If P is larger than we need, we split P into two blocks:
 *  the leftover space and the allocated space.  That means, we need to 
 *  create a header in the allocated space.                                 */

  k -= HLEN;
  p->len = k;

  q = (struct __mp__*) (((char *) (&p[1])) + k);
  q->len = size;
  return (&q[1]);           /* SUCCESS */
}