/* from the TOS GCC library */
/* malloc, free, realloc: dynamic memory allocation */

#include <stddef.h>	/* for size_t */
#include <memory.h>
#include <string.h>
#include <assert.h>

extern long _stksize;
extern void *_sbrk();

/* minimum chunk to ask OS for */
static size_t MINHUNK =	4096L;	/* default */
static size_t MAXHUNK = 32*1024L; /* max. default */

	/* CAUTION: use _mallocChunkSize() to tailor to your environment,
		    do not make the default too large, as the compiler
		    gets screwed on a 1M machine otherwise (stack/heap clash)
	 */

struct mem_chunk 
	{
	long valid;
#define VAL_FREE  0xf4ee0abc
#define VAL_ALLOC 0xa11c0abc

	struct mem_chunk *next;
	long size;
	};

/* linked list of free blocks */

static struct mem_chunk _mchunk_free_list = { VAL_FREE, NULL, 0L };

/* flag to control zero'ing of malloc'ed chunks */
static int _ZeroMallocs = 0;


#if 0
asm(".text; .even; .globl _mlalloc; _mlalloc:"); /* dept of dirty tricks */
#endif

void * malloc(n)
size_t n; 
{
  struct mem_chunk *p, *q;
  long sz;
  extern void *_heapbase;

/* add a mem_chunk to required size and round up */
  n = n + sizeof(struct mem_chunk);
  n = (7 + n) & ~7;
/* look for first block big enough in free list */
  p = &_mchunk_free_list;
  q = _mchunk_free_list.next;

  while ((q != NULL) && (q->size < n))
	{
	p = q;
	q = q->next;
	}

/* if not enough memory, get more from the system */
  if (q == NULL) 
	{
	if ((_heapbase != NULL) || (n > MINHUNK))
		sz = n;
	else {
		sz = MINHUNK;
		if (MINHUNK < MAXHUNK)
			MINHUNK *= 2;
	}
	q = (struct mem_chunk * )_sbrk(sz);

	if (((long)q) == -1) 		/* can't alloc any more? */
		return(NULL);

	p->next = q;
	q->size = sz;
	q->next = NULL;
	q->valid = VAL_FREE;
	}
		
  if (q->size > n + sizeof(struct mem_chunk))
	{				/* split, leave part of free list */
	q->size -= n;
	q = (struct mem_chunk * )(((long) q) + q->size);
	q->size = n;
	q->valid = VAL_ALLOC;
	}
    else
	{				/* just unlink it */
	p->next = q->next;
	q->valid = VAL_ALLOC;
	}

  q->next = NULL;	
  q++;	/* hand back ptr to after chunk desc */
  if(_ZeroMallocs != 0)
      bzero((void *)q, (size_t)(n - sizeof(struct mem_chunk)));
  
  return((void * )q);
}

void free(param)
	void *param;
{
  struct mem_chunk *o, *p, *q, *s;
  struct mem_chunk *r = (struct mem_chunk *) param;
  extern void *_heapbase;

/* free(NULL) should do nothing */
  if (r == 0)
     return;

/* move back to uncover the mem_chunk */
  r--;			/* there it is! */

  if (r->valid != VAL_ALLOC)
	return;

  r->valid = VAL_FREE;

/* stick it into free list, preserving ascending address order */
  o = NULL;
  p = &_mchunk_free_list;
  q = _mchunk_free_list.next;
  while (q != NULL && q < r) 
	{
	o = p;
	p = q;
	q = q->next;
	}

/* merge after if possible */
  s = (struct mem_chunk * )(((long) r) + r->size);
  if (q != NULL && s >= q) 
	{
	assert(s == q);
	r->size += q->size;
	q = q->next;
	s->size = 0;
	s->next = NULL;
	}
  r->next = q;
	
/* merge before if possible, otherwise link it in */
  s = (struct mem_chunk * )(((long) p) + p->size);
  if (s >= r && p != &_mchunk_free_list)
    /* remember: r may be below &_mchunk_free_list in memory */
	{
	assert(s == r);
	p->size += r->size;
	p->next = r->next;
	r->size = 0;
	r->next = NULL;
	s = (struct mem_chunk * )(((long) p) + p->size);
	if (_heapbase != NULL && s >= (struct mem_chunk *) _heapbase) {
	  assert(s == _heapbase);
	  _heapbase = (char *) p;
	  _stksize += p->size;
	  o->next = NULL;	/* o is always != NULL here */
	}
	}
    else
        {
	  s = (struct mem_chunk * )(((long) r) + r->size);
	  if (_heapbase != NULL && s >= (struct mem_chunk *) _heapbase) {
	    assert(s == _heapbase);
	    _heapbase = (char *) r;
	    _stksize += r->size;
	    p->next = NULL;
	  } else p->next = r;
	}
}

#if 0
asm(".text; .even; .globl _relalloc,_realloc; _relalloc: jra _realloc");
#ifdef NDEBUG
static char *__dummy = ""; /* otherwise we get a bra with 0 offset above */
#endif
#endif

void * realloc(_r, n)
void *_r;
size_t n;
{
  struct mem_chunk *p, *q, *r = _r;
  long sz;

/* obscure features: realloc(NULL,n) is the same as malloc(n)
 *  		     realloc(p, 0) is the same as free(p)
 */
  if (!r)
	return malloc(n);
  if (n == 0) {
	free(_r);
	return NULL;
  }
  p = r - 1;
  sz = (n + sizeof(struct mem_chunk) + 7) & ~7;

  if (p->size > sz) 
	{			/* block too big, split in two */
	q = (struct mem_chunk * )(((long) p) + sz);
	q->size = p->size - sz;
        q->valid = VAL_ALLOC;
	free(q + 1);
	p->size = sz;
	}
    else 
  if (p->size < sz)
    {			/* block too small, get new one */
    struct mem_chunk *s, *t;
    q = &_mchunk_free_list;
    t = _mchunk_free_list.next;
    while (t != NULL && t < p)
      {
      q = t;
      t = t->next;
      }

    /* merge after if possible */
    s = (struct mem_chunk * )(((long) p) + p->size);
    if (t != NULL && s >= t && p->size + t->size >= sz)
      {
      assert(s == t);
      p->size += t->size;
      q->next = t->next;
      t->size = 0;
      t->next = NULL;
      }
    else
      {
      q = (struct mem_chunk * )malloc(n);
      if (q != NULL)
	{
	n = p->size - sizeof(struct mem_chunk);
	bcopy(r, q, n);
        free(r);	/* free r only if we got a new block */
        }
      r = q;
    }
  }
  /* else current block will do just fine */
  return((void * )r);
}

#if 0
asm(".text; .even; .globl _clalloc; _clalloc:");
#endif

void * calloc(n, sz)
size_t n, sz;
{
  char *r;
  size_t total;

  total = n * sz;
  if ((r = malloc(total)) != NULL) {
	bzero(r, total);
  }
  return(r);
}

/*
 * Set zero block after malloc flag
 */
void _malloczero(yes)
int yes;
{
    _ZeroMallocs = yes;
}

/*
 * tune chunk size
 */
void _mallocChunkSize (siz)
size_t siz;
{
    MAXHUNK = MINHUNK = siz;
}