/* malloc2.c (emx+gcc) -- Copyright (c) 1990-1993 by Eberhard Mattes */

#include <sys/emx.h>
#include <stdlib.h>
#include "malloc2.h"

#define CHUNK_SIZE 65536

/* To do: take size of last free block into account, if no used block
          follows and if sbrk() must be called. */

/* Bug: sbrk/brk must not be called by user program to change data
        segment size (very complicated to fix). malloc returns NULL if it
        thinks the data segment size has been changed. */

size_t *rover = NULL;
size_t *bottom = NULL;
size_t *top = NULL;

int _malloc_init (void)
{
  size_t n;
  void *p;

  HEAP_LOCK;
  n = (size_t)sbrk (0);
  if ((n & 3) != 0)
    sbrk (4 - (n & 3));
  p = sbrk (2 * sizeof (size_t));
  if (p == (void *)(-1) || ((size_t)p & 3) != 0)
    {
      HEAP_UNLOCK;
      return (FALSE);
    }
  bottom = rover = p;
  top = bottom+1;
  *bottom = 1;                  /* length = 0, free */
  *top = END_OF_HEAP;           /* End of heap      */
  HEAP_UNLOCK;
  return (TRUE);
}


/* Pass 1: search from rover to end of heap
   Pass 2: search from start of heap to rover
   Pass 3: search from rover to end of heap (after growing heap)

   If EXPAND_HEAP is non-zero, we are allowed to expand the heap. */

void *_malloc2 (size_t size, int expand_heap, int tile)
{
  size_t *block, *base;
  void *p;
  size_t len, n, a;
  int pass;

  /* Sanity-check SIZE.  Don't call sbrk() with negative argument */

  if (size > MAX_SIZE)
    return (NULL);

  /* Round up SIZE to a multiple of 4. */

  size = (size+3) & ~3;

  pass = 1;

  /* Start new pass at rover. */

restart:
  block = base = rover;

  /* Skip blocks which are in use.  Jump to free_start if we found a
     free block. */

in_use:
  if (*block & 1)
    goto free_start;

  /* Same as in_use, but we already know that the current block is in
     use (speed hack). */

not_free:

  /* The second pass stops at rover. */

  if (pass == 2 && (size_t)block > (size_t)rover)
    {
      block = top;
      goto not_found;
    }

  /* Start next pass when reaching the end of the heap. */

  if (*block == END_OF_HEAP)
    {
      if (block != top)
        return (NULL);
      if (pass >= 2)
        goto not_found;
      ++pass; block = bottom;
      goto in_use;
    }

  /* Move to the next block and repeat loop. */

  block = (size_t *)((char *)block + sizeof (size_t) + *block);
  goto in_use;

  /* We found a free block.  Now collapse successive free blocks until
     the block is big enough or there is not another adjacent free
     block. */

free_start:

  /* base points to the start of the free block we're examining.  len
     is used to accumulate the length of successive free blocks. */

  base = block;
  len = *base & ~3;

  /* If tiling is in effect, the block must not cross a 64K boundary.
     Compute n, the number of extra bytes required at the beginning of
     the block, based on the address of the current block, to align
     the data properly. */

  n = 0;
  if (tile)
    {

      /* If the requested size is 64K or more or if the data crosses a
         64K boundary, align the block to a 64K boundary. */

      a = (size_t)base + sizeof (size_t);
      if (((a + size) & 0xffff) < size)
        {
          n = a & 0xffff;
          if (n != 0)
            n = 0x10000 - n;
        }
    }

free_loop:

  /* If the block is big enough, quit the loop and use the block. */

  if (len >= size + n)
    goto found;

  /* Move to the next block. */

  block = (size_t *)((char *)base + sizeof (size_t) + len);

  /* If that block is in use, quit the loop and skip used blocks until
     another free block is found. */

  if (!(*block & 1))
    goto not_free;

  /* Update len and collaps the current block and the new block into
     one free block.  Then repeat the loop. */

  len += sizeof (size_t) + (*block & ~3);
  *base = len | 1;
  goto free_loop;

  /* A big enough block was found.  Split it into up to three blocks,
     one of which will be marked used and returned to the caller. */

found:

  /* If alignment is required, create a free block of size n
     (including the header), then advance the pointer.  This may
     create a block of size 0 (excluding the header). */

  if (n != 0)
    {
      if ((n & 3) != 0)
        abort ();
      *base = n - sizeof (size_t); /* Even, ie, in use */
      base = (size_t *)((char *)base + n); len -= n;
    }

  /* If there are more than 4 bytes left, create a free block after
     the block to be used.  If there are 4 bytes left, we simply make
     the block 4 bytes too big. */

  if (len - size > sizeof (size_t))
    {
      *base = size;             /* Even, ie, in use */
      block = (size_t *)((char *)base + sizeof (size_t) + size);
      *block = (len - size - sizeof (size_t)) | 1;
    }
  else
    *base &= ~3;                /* in use! */
  rover = base;
  return ((void *)((char *)base + sizeof (size_t)));

not_found:
  if (!expand_heap)
    return (NULL);
  if (tile)
    n = (size + 0x10000 + 0xfff) & ~0xfff;
  else
    {
      n = (size + sizeof (size_t) + 0xfff) & ~0xfff;
      if (n < CHUNK_SIZE)
        n = CHUNK_SIZE;         /* Memory is cheap, searching expensive */
    }
  p = sbrk (n);
  if (p == (void *)(-1))
    return (NULL);
  if (p != top+1)
    return (NULL);
  *top = (n - sizeof (size_t)) | 1;
  top = (size_t *)((char *)top + n);
  *top = END_OF_HEAP;
  pass = 3; rover = base;
  goto restart;
}