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

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

/* Try to expand a block in place.  MEM points to the start of the
   block, SIZE is the new size.  Shrinking the size of a block always
   succeeds.  Return MEM on success.  Return NULL on failure (the
   block has been made as big as possible). */

void *_expand (void *mem, size_t size)
{
  void *p;

  HEAP_LOCK;
  p = _expand2 (mem, size, TRUE, FALSE);
  HEAP_UNLOCK;
  return (p);
}


/* Try to expand a block in place.  The heap must be locked before
   calling this function.  If EXPAND_HEAP is zero, expanding the heap
   is not allowed.  Shrinking the size of a block always succeeds.
   Return MEM on success.  Return NULL on failure (the block has been
   made as big as possible). */

void *_expand2 (void *mem, size_t size, int expand_heap, int tile)
{
  size_t in_use, len, xlen, a;
  size_t *base, *block;
  void *p;

  /* Sanity-check the SIZE argument. */

  if (size > MAX_SIZE)
    return (NULL);

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

  size = (size+3) & ~3;

  /* When tiling, check whether the block can be expanded in place
     without crossing a 64K boundary. */

  if (tile)
    {
      a = (size_t)mem;
      if ((a & 0xffff) != 0 && (a & 0xffff) + size > 0x10000)
        return (NULL);
    }

  /* Let base point to the block header and read the block header.  We
     need only the in-use bit of the block header */

  base = mem;
  --base;
  in_use = *base;

  /* Jump here after expanding the heap.  Collaps free blocks starting
     at MEM (which is included). */

restart:
  *base &= ~3;                  /* Mark block temporarily in-use */
  len = *base;                  /* Get the length of the block */

  /* Collaps free blocks following block MEM.  len will be set to the
     size of block MEM plus the combined size of all the free blocks
     following block MEM. */

  for (;;)
    {
      block = (size_t *)((char *)base + sizeof (size_t) + len);
      if (block == rover)
        rover = base;           /* avoid invalid rover */
      xlen = *block;
      if (!(xlen & 1))          /* block in use? */
        break;                  /* yes -> end of contiguous area */
      len += sizeof (size_t) + (xlen & ~3);
    }

  /* If the size of the block (plus the combined size of the free
     blocks) is big enough, we won. */

  if (len >= size)
    goto success;

  /* Set the length of block MEM to the combined size of MEM and the
     following free blocks.  That's how big we can make the block
     without relocating it.  Restore the in-use bit. */

  *base = (len & ~3) | (in_use & 1);

  /* If the block isn't the last block of the heap or if we aren't
     allowed to expand the heap, fail. */

  if (*block != END_OF_HEAP || !expand_heap)
    return (NULL);

  /* Expand the heap as much as required to accomodate for the
     requested block size, but round the size of the heap up to the
     next multiple of the page size. */

  xlen = (size-len + sizeof (size_t) + 0xfff) & ~0xfff;
  p = sbrk (xlen);

  /* Fail if expanding the heap failed. */

  if (p == (void *)(-1))
    return (NULL);

  /* Fail if someone has used brk() or sbrk() to change the size of
     the data segment.  This heap implementation requires a contiguous
     heap. */

  if (p != top+1)
    return (NULL);

  /* Turn the new heap space into a free block and adjust the pointer
     to the end of the heap.  Then restart.  As the free blocks have
     been collapsed, the second pass will be quick. */

  *top = (xlen - sizeof (size_t)) | 1;
  top = (size_t *)((char *)top + xlen);
  *top = END_OF_HEAP;
  goto restart;

  /* The size of block MEM plus the combined size of the free blocks
     following MEM is big enough to serve the request.  Split the
     combined block into two blocks: block MEM of size SIZE and
     optionally a free block following MEM. */

success:

  /* Create a free block if there's enough space left.  Otherwise
     assign the bytes left over to block MEM. */

  if (len - size > sizeof (size_t))
    {
      block = (size_t *)((char *)base + sizeof (size_t) + size);
      *block = (len - size - sizeof (size_t)) | 1;
      len = size;
    }

  /* Set the size of block MEM and restore the in-use bit. */

  *base = (len & ~3) | (in_use & 1);

  /* Return MEM. */

  ++base;
  return (base);
}