/* compact.c - Compaction routine triggered when the wasted space in an image
 *             gets above 10%
 */

#include "chunks.h"
#include "debug.h"
#include <stdlib.h>
#include "swis.h"

#define BATCHSIZE  100

#define _max(x, y) ((x) > (y) ? (x) : (y))
#define _min(x, y) ((x) < (y) ? (x) : (y))

typedef struct
{
   unsigned cnkNum;
   xFiles_chunk chunk;

} xFiles__chunkRef;

/* Yet another dodgy implementation of my standard shifting heap
 * compactor. Each pass finds the chunk numbers of the next N items
 * in the file, then relocates them down towards the header. Simple
 * as that.
 */

_kernel_oserror *xFiles_Compact(xFiles_info *pInfo)
{
   _kernel_oserror *err;
   xFiles__chunkRef *workSpace = NULL;
   unsigned tableSize, bitSize, nChunks, fileSize;
   unsigned thisChunk;
   unsigned highWaterMark = xFiles_roundUp(pInfo, sizeof(xFiles_header));
   unsigned tablePos;
   xFiles_chunk *pChunk;
   int workUsed = 0;
   int i;
   _kernel_swi_regs regs;

   if (pInfo->compacting)
      return NULL;

   pInfo->compacting = TRUE;
   (void) _kernel_swi(Hourglass_On, &regs, &regs);

   if (err = xFiles_getLength(pInfo, &fileSize), err) goto fail;

   /*TRACE("Compacting file (size = %08x)\n", fileSize);*/

   if (workSpace = malloc(BATCHSIZE * sizeof(xFiles__chunkRef)), !workSpace)
   {
      err = &xFiles_NoMemory;
      goto fail;
   }

   do
   {
      /* Collect the next 100 candidates */

      tableSize = pInfo->fileHeader.chunkTable.size;
      tablePos = 0;
      workUsed = 0;
      thisChunk = 0;

      if (err = xFiles_claimBuffer(tableSize), err)
         goto fail;

      while (tableSize > 0)
      {
         bitSize = _min(tableSize, xFiles_windowBufferSize);
         nChunks = bitSize / sizeof(xFiles_chunk);
         bitSize = nChunks * sizeof(xFiles_chunk);

         if (err = xFiles_readChunk(pInfo, xFiles_windowBuffer, 0, tablePos, bitSize), err)
            goto fail2;

         for (pChunk = xFiles_windowBuffer; nChunks > 0; nChunks--, pChunk++, thisChunk++)
         {
            if (pChunk->usage != 0x45455246 && pChunk->offset >= highWaterMark)
            {
               xFiles__chunkRef ref, tmp;

               ref.cnkNum  = thisChunk;
               ref.chunk   = *pChunk;

               for (i = 0; i < workUsed; i++)
               {
                  if (ref.chunk.offset < workSpace[i].chunk.offset)
                  {
                     tmp = workSpace[i];
                     workSpace[i] = ref;
                     ref = tmp;
                  }
               }

               if (workUsed < BATCHSIZE)
                  workSpace[workUsed++] = ref;
            }
         }

         tableSize -= bitSize;
         tablePos  += bitSize;
      }

      if (err = xFiles_releaseBuffer(), err)
         goto fail;

      /*TRACE("Identified %d chunks\n", workUsed);

      for (i = 0; i < workUsed; i++)
      {
         TRACE("chunk %5d at %08x, size %08x, allocSize %08x\n",
                  workSpace[i].cnkNum, workSpace[i].chunk.offset,
                  workSpace[i].chunk.size, workSpace[i].chunk.allocSize);
      }*/

      /* Processed the whole table and got a few candidates for relocating, so let's
       * shift them.
       */

      for (i = 0; i < workUsed; i++)
      {
         if (workSpace[i].chunk.allocSize != xFiles_roundDown(pInfo, workSpace[i].chunk.allocSize))
            TRACE("How strange: allocSize = %08x\n", workSpace[i].chunk.allocSize);

         if (workSpace[i].chunk.allocSize < xFiles_roundUp(pInfo, workSpace[i].chunk.size))
            TRACE("How odd: allocSize = %08x, size = %08x\n",
                    workSpace[i].chunk.allocSize, workSpace[i].chunk.size);

         if (workSpace[i].chunk.offset != xFiles_roundDown(pInfo, workSpace[i].chunk.offset))
            TRACE("How weird: offset = %08x\n", workSpace[i].chunk.offset);

         ASSERT(workSpace[i].chunk.allocSize >= workSpace[i].chunk.size);
         ASSERT(workSpace[i].chunk.offset    >= sizeof(xFiles_header));

         workSpace[i].chunk.allocSize = xFiles_roundUp(pInfo, workSpace[i].chunk.size);

         /*TRACE("Moving %08x bytes from %08x to %08x\n",
                       workSpace[i].chunk.allocSize, workSpace[i].chunk.offset, highWaterMark);*/

         if (workSpace[i].chunk.offset < highWaterMark && workSpace[i].chunk.allocSize != 0)
         {
            TRACE("*** can't move block from %08x to %08x\n",
                       workSpace[i].chunk.offset, highWaterMark);
            goto skip;           
         }

         regs.r[0] = 100 * (workSpace[i].chunk.offset >> 8) / (fileSize >> 8);
         (void) _kernel_swi(Hourglass_Percentage, &regs, &regs);

         if (err = xFiles_moveBlock(pInfo, highWaterMark, workSpace[i].chunk.offset, workSpace[i].chunk.allocSize), err)
            goto fail;

         workSpace[i].chunk.offset = highWaterMark;

         if (err = xFiles_setChunkInfo(pInfo, workSpace[i].cnkNum, &workSpace[i].chunk), err)
            goto fail;

skip:
         highWaterMark += workSpace[i].chunk.allocSize;

         if (xFiles_roundDown(pInfo, highWaterMark) != highWaterMark)
         {
            TRACE("Huh? HWM = %08x\n", highWaterMark);
         }
      }

   } while (workUsed == BATCHSIZE);

   free(workSpace);

   /*TRACE("Compacted file (size = %08x)\n", highWaterMark);*/

   if (err = xFiles_setLength(pInfo, highWaterMark), err)
      goto fail;

   pInfo->fileHeader.waste = 0;
   if (err = xFiles_updateHeader(pInfo), err)
      goto fail;

   pInfo->flags |= xFiles_fNeedTruncate;

   (void) _kernel_swi(Hourglass_Off, &regs, &regs);
   pInfo->compacting = FALSE;
   return err;

fail2:
   (void) xFiles_releaseBuffer();

fail:
   if (workSpace) free(workSpace);
   pInfo->compacting = FALSE;
   (void) _kernel_swi(Hourglass_Off, &regs, &regs);
   return err;
}
