/*
    ####             #    #     # #
    #   #            #    #       #          The FreeWare C library for 
    #   #  ##   ###  #  # #     # ###             RISC OS machines
    #   # #  # #     # #  #     # #  #   ___________________________________
    #   # ####  ###  ##   #     # #  #                                      
    #   # #        # # #  #     # #  #    Please refer to the accompanying
    ####   ### ####  #  # ##### # ###    documentation for conditions of use
    ________________________________________________________________________

    File:    Mem.MidExtend.c
    Author:  Copyright  1993, 1995 Jason Williams and Jason Howat
    Version: 2.00 (18 Jun 1995)
    Purpose: Dynamic memory manager - reallocation
*/

#include "Desk.Error.h"
#include "MemDefs.h"

#include <string.h> 

#ifdef Desk_MEM__DEBUG
#include <stdio.h>
#endif


static Desk_bool Desk_Mem__MidExtendNoCompact(Desk_mem_anchor *anchor, Desk_mem_header *chunk, int at, int by)
{
  int         available = chunk->realsize,
              olddatasize,
              newdatasize;
  Desk_mem_header *nextchunk = (Desk_mem_header *)((int)chunk + chunk->realsize),
             *prevchunk = (Desk_mem_header *)((int)chunk - chunk->prevrealsize),
             *newchunk = chunk;
  Desk_bool        Desk_now_last = (chunk == Desk_mem__lastchunk) ? Desk_bool_TRUE : Desk_bool_FALSE;
  char       *source,
             *destination;

  /* check space in adjoining blocks and use if available */
  if((chunk != Desk_mem__lastchunk) && (ISFREE(nextchunk)))
  {
    available += nextchunk->realsize;
    Desk_now_last = (nextchunk == Desk_mem__lastchunk) ? Desk_bool_TRUE : Desk_bool_FALSE;
  }

  if(((int)chunk != Desk_mem__heap) && (ISFREE(prevchunk)))
  {
    available += prevchunk->realsize;
    newchunk = prevchunk;
  }

  newdatasize = chunk->datasize + by;
  source = (char *)chunk + sizeof(Desk_mem_header);
  olddatasize = chunk->datasize;

  if(available >= CHUNKSIZE(chunk->datasize + by))
  {
    destination = (char *)((int)newchunk + sizeof(Desk_mem_header));
    *chunk->handle = destination;
    newchunk->handle = chunk->handle;
    newchunk->realsize = available;
    newchunk->datasize = newdatasize;
    Desk_mem__free -= WORDALIGN(newdatasize) - WORDALIGN(olddatasize);

    if(!Desk_now_last)
    {
      Desk_mem_header *nn = (Desk_mem_header *)((int)newchunk + available);
      nn->prevrealsize = available;
    }

    memmove(destination, source, at);
    memmove(destination + at + by, source + at, olddatasize - at);

    Desk_Mem__SplitOffFreeChunk(newchunk);
  }
  else /* try to alloc block of new size and copy old one over */
  {
    if(!Desk_Mem_Alloc((Desk_mem_anchor *)&destination, newdatasize))
      return Desk_bool_FALSE;

    memmove(destination, source, at);
    memmove(destination + at + by, source + at, olddatasize - at);

    Desk_Mem_Free(anchor);
    *anchor = destination;
    Desk_Mem__FindChunk((Desk_mem_anchor *)&destination, &chunk);
    chunk->handle = anchor;
  }

  return Desk_bool_TRUE;
}

extern Desk_bool Desk_Mem_MidExtend(Desk_mem_anchor *anchor, int at, int by)
/*  Enlarges or reduces a Mem chunk by moving all data beyond 'at' by
 *  'by' bytes up or down in memory. 'at' is an offset within the chunk.
 *
 *  Goes to rather a lot of effort to avoid moving the base address of
 *  this chunk and others, but if Desk_mem_autocompact allows, it will compact
 *  if it is absolutely necessary in order to manage the extension.
 *
 *  Returns Desk_bool_TRUE if it succeeds
 */
{
  Desk_mem_header *chunk,
             *bestfit = NULL,
             *start, *end,
             *Desk_best_start = NULL, *Desk_best_end=0,
             *Desk_scan_start, *Desk_scan_end,
             *Desk_end_of_heap;
  int         Desk_bestfit_size=0,
              Desk_best_move=0, Desk_best_free,
              Desk_move_count, Desk_free_count,
              needed,
              newdatasize, extchunksize;
  char       *source,
             *destination;


  if(by == 0)         /* Zero bytes? Certainly sir! Anything else? */
    return(Desk_bool_TRUE);

  if(at < 0 || !Desk_Mem__FindChunk(anchor, &chunk))
    return(Desk_bool_FALSE);

  if(at > chunk->datasize)
    return(Desk_bool_FALSE);

  source = (char *)chunk + sizeof(Desk_mem_header);

  /* ------ Reduce chunk ------ */
  if (by < 0)                            /* Reducing the size of the chunk   */
  {
    if (-by > at) by = -at;              /* Can't delete past start of chunk */

    Desk_mem__free += WORDALIGN(chunk->datasize) - WORDALIGN(chunk->datasize + by);

    memmove(source + at + by, source + at, chunk->datasize - at);
    chunk->datasize += by;               /* Shrink data area of this block   */

    Desk_Mem__SplitOffFreeChunk(chunk);       /* Return any free space for use    */
    /* The anchor has not changed */
    return(Desk_bool_TRUE);
  }


  /* ------ Extend chunk ------ */
  if(Desk_mem_autocompact == Desk_mem_NOCOMPACT)
    return Desk_Mem__MidExtendNoCompact(anchor, chunk, at, by);
  else /*  allowed to relocate other blocks in the search for the cheapest way
        *  of creating enough space for the extension
        */
  {
    newdatasize = chunk->datasize + by;
    extchunksize = CHUNKSIZE(newdatasize);
    /* needed: is the number of free bytes required to perform the extension
               (will be a multiple of 4) */
    needed = WORDALIGN(newdatasize) - WORDALIGN(chunk->datasize);

    /* ensure there is enough space _before_ we go searching for the cheapest
     * way of using it
     */
    if(Desk_mem__free < needed)
    {
      /* extend the heap by at least (needed - Desk_mem__free) bytes */
      int extra = needed - Desk_mem__free,
          prevsize = Desk_mem__heapsize;

      Desk_mem__heapsize = Desk_Mem__HeapSize(Desk_mem__heapsize + extra + 16);
      Desk_mem__free += Desk_mem__heapsize - prevsize;
#ifdef Desk_MEM__DEBUG
fprintf(stderr, "grow heap: %8x\n", Desk_mem__heapsize - prevsize);
fflush(stderr);
#endif
      Desk_mem__lastchunk->realsize = Desk_mem__heap + Desk_mem__heapsize - (int)Desk_mem__lastchunk;

      if(Desk_mem__free < needed)
      {
        Desk_Mem__SplitOffFreeChunk(Desk_mem__lastchunk);
        Desk_Mem__ReduceSlot();
        return Desk_bool_FALSE;     /* unable to get enough freespace to do extension */
      }
    }

    start = chunk;
    end = (Desk_mem_header *)((int)chunk + chunk->realsize);
    Desk_end_of_heap = (Desk_mem_header *)(Desk_mem__heap + Desk_mem__heapsize);

    if(start->realsize >= extchunksize)
    {
      bestfit = start;
      Desk_bestfit_size = start->realsize;
    }

    Desk_move_count = start->datasize;
    Desk_free_count = start->realsize - CHUNKSIZE(start->datasize);
  
    /* Scan backwards from chunk to find start of possible run of blocks */
    while((Desk_free_count < needed) && ((int)start != Desk_mem__heap))
    {
      int used;
  
      start = (Desk_mem_header *)((int)start - start->prevrealsize);
  
      if(ISFREE(start))
      {
        used = 0;

        if(((bestfit == NULL) || (Desk_bestfit_size > start->realsize)) &&
           (start->realsize >= extchunksize))
        {
          bestfit = start;
          Desk_bestfit_size = Desk_bestfit_size;
        }
      }
      else
      {
        used = CHUNKSIZE(start->datasize);
        Desk_move_count += used;
      }

      Desk_free_count += start->realsize - used;
    }

    Desk_scan_start = start;

    /* Alternately advance end/start forwards keeping track of count of bytes
       to be moved, remembering start/end points for run of blocks with
       minimum.  At the same time scan for a single free block which is big
       enough to hold the entire extended block. Check for when start == chunk
       and adjust *_count variables accordingly */
    while(1)
    {
      /* advance end and adjust *_count stats until Desk_free_count >= needed */
      while((Desk_free_count < needed) && (end < Desk_end_of_heap))
      {
        int used;

        if(ISFREE(end))
        {
          used = 0;

          if(((bestfit == NULL) || (Desk_bestfit_size > end->realsize)) &&
             (end->realsize >= extchunksize))
          {
            bestfit = end;
            Desk_bestfit_size = Desk_bestfit_size;
          }
        }
        else
        {
          used = CHUNKSIZE(end->datasize);
          Desk_move_count += used;
        }

        Desk_free_count += end->realsize - used;

        end = (Desk_mem_header *)((int)end + end->realsize);
      }

      /* check stats and copy to Desk_best_* if needed */
      if((Desk_free_count >= needed) &&
         ((Desk_best_start == NULL) || (Desk_best_move > Desk_move_count)))
      {
        Desk_best_start = start;
        Desk_best_end = end;
        Desk_best_move = Desk_move_count;
        Desk_best_free = Desk_free_count;
      }
  
      if(start == chunk)
        break;

      {
        int used;

        /* adjust *_count stats and advance start one block */
        if(!ISFREE(start))
        {
          used = CHUNKSIZE(start->datasize);
          Desk_move_count -= used;
        }
        else
          used = 0;
        Desk_free_count -= start->realsize - used;
      }

      start = (Desk_mem_header *)((int)start + start->realsize);

      if(start == chunk)
        Desk_move_count -= sizeof(Desk_mem_header) + at;
    }

    Desk_scan_end = end;

    /* Consider cost of moving whole block to larger free block and choose
     * cheapest option for the extension of the block.
     * NB: as we have already ensured that (Desk_mem__free >= needed), Desk_best_start
     *     must be non-NULL, as a run of blocks has to exist.
     */
    if(Desk_best_move > chunk->datasize)
    {
      /* check chunks before Desk_scan_start and after Desk_scan_end for single free
       * block that is large enough for the extended block, as it is cheaper
       * to relocate target block.
       */
      Desk_mem_header *check;

      check = (Desk_mem_header *)Desk_mem__heap;
      while(check < Desk_scan_start)
      {
        if(ISFREE(check))
        {
          if(((bestfit == NULL) || (Desk_bestfit_size > check->realsize)) &&
             (check->realsize >= extchunksize))
          {
            bestfit = check;
            Desk_bestfit_size = check->realsize;
          }
        }

        check = (Desk_mem_header *)((int)check + check->realsize);
      }

      check = Desk_scan_end;
      while(check < Desk_end_of_heap)
      {
        if(ISFREE(check))
        {
          if(((bestfit == NULL) || (Desk_bestfit_size > check->realsize)) &&
             (check->realsize >= extchunksize))
          {
            bestfit = check;
            Desk_bestfit_size = check->realsize;
          }
        }

        check = (Desk_mem_header *)((int)check + check->realsize);
      }
    }

    if((bestfit != NULL) && (Desk_best_move > chunk->datasize))
    {
      /* it is cheaper to relocate entire chunk */
#ifdef Desk_MEM__DEBUG
fprintf(stderr, "relocate: bestfit %p\n", bestfit);
fflush(stderr);
#endif

      /* copy data */
      destination = (char *)bestfit + sizeof(Desk_mem_header);
      memmove(destination, source, at);
      memmove(destination + at + by, source + at, chunk->datasize - at);
      
      /* update heap control structures */
      bestfit->handle = chunk->handle;
      bestfit->datasize = newdatasize;
      Desk_Mem_Free(anchor);
      *bestfit->handle = destination;
      Desk_mem__free -= extchunksize;

      Desk_Mem__SplitOffFreeChunk(bestfit);

      return(Desk_bool_TRUE);
    }
    else
    {
      /* perform extension by:
       *   compacting region defined by Desk_best_start/Desk_best_end
       *   move data to new locations
       *   update headers of surrounding and target chunks
       */
      Desk_mem_header *newchunk;
      int         newchunksize,
                  oldchunksize;

      if(Desk_best_start < chunk)  /* must be free space available before chunk */
      {
        Desk_Mem__ShuffleDown(Desk_best_start, chunk);
        newchunk = (Desk_mem_header *)((int)chunk - chunk->prevrealsize);
      }
      else
        newchunk = chunk;
      destination = (char *)((int)newchunk + sizeof(Desk_mem_header));

      if(Desk_best_end > (Desk_mem_header *)((int)chunk + chunk->realsize))
        Desk_Mem__ShuffleUp(chunk, Desk_best_end);

      newchunksize = chunk->realsize;
      if(Desk_best_start < chunk)
        newchunksize += newchunk->realsize;

      if(extchunksize > newchunksize)  /* sanity check */
        Desk_Error_ReportFatalInternal(0, "Unexpected failure in Desk_Mem_MidExtend");

      /* update anchors/links */
      oldchunksize = chunk->datasize;
      newchunk->handle = chunk->handle;
      newchunk->datasize = newdatasize;
      newchunk->realsize = newchunksize;
      *(newchunk->handle) = destination;

      /* move data */
      memmove(destination, source, at);
      memmove(destination + at + by, source + at, oldchunksize - at);

      if(chunk != Desk_mem__lastchunk)
      {
        Desk_mem_header *next = (Desk_mem_header *)((int)newchunk + newchunksize);
        next->prevrealsize = newchunksize;
      }
      else
        Desk_mem__lastchunk = newchunk;      /* update Desk_mem__lastchunk */

      Desk_Mem__SplitOffFreeChunk(newchunk);
    }
  }

  Desk_mem__free -= needed;   /* successful allocation - update stats */

  return(Desk_bool_TRUE);
}
