/* chunks.c */

/*#define NOCOMPACT*/
/*#define ERASE*/
/*#define NOCHUNKCACHE*/

#include "chunks.h"
#include "debug.h"
#include "swis.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

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

#define FREE 0x45455246

xFiles_list xFiles_openFiles;

static void xFiles_checkChunk(xFiles_info *pInfo, const xFiles_chunk *pChunk)
{
   unsigned maxChunk = pInfo->fileHeader.chunkTable.size / sizeof(xFiles_chunk);
   
   if (pChunk->usage == FREE)
   {
      ASSERT(pChunk->offset < maxChunk);
      ASSERT(pChunk->size == FREE);
      ASSERT(pChunk->allocSize == FREE);
   }
   else
   {
      if (pChunk->offset != xFiles_roundDown(pInfo, pChunk->offset))
      {
         TRACE("offset: %08x\n", pChunk->offset);
      }

      /*ASSERT(pChunk->offset == (pChunk->offset & ~(pInfo->fileHeader.allocationUnit-1)));*/
      ASSERT(pChunk->allocSize == (pChunk->allocSize & ~(pInfo->fileHeader.allocationUnit-1)));
      ASSERT(pChunk->size <= pChunk->allocSize);
   }
}

unsigned xFiles_chunkAddress(xFiles_info *pInfo, unsigned cnkNum)
{
   ASSERT(pInfo->fileHeader.chunkTable.offset >= sizeof(xFiles_header));
   ASSERT(cnkNum * sizeof(xFiles_chunk) < pInfo->fileHeader.chunkTable.size);

   return pInfo->fileHeader.chunkTable.offset + cnkNum * sizeof(xFiles_chunk);
}

unsigned xFiles_roundDown(xFiles_info *pInfo, unsigned pos)
{
   ASSERT(pInfo->fileHeader.allocationUnit == 1024);
   return pos & ~(pInfo->fileHeader.allocationUnit-1);
}

unsigned xFiles_roundUp(xFiles_info *pInfo, unsigned pos)
{
   return xFiles_roundDown(pInfo, pos + pInfo->fileHeader.allocationUnit - 1);
}

#ifndef NOCHUNKCACHE
static int xFiles__cacheLookup(xFiles_info *pInfo, unsigned cnkNum)
{
   int lo, mid, hi;

   for (lo = 0, hi = pInfo->cacheUsed-1; lo <= hi; )
   {
      mid = (lo + hi) / 2;
      if (pInfo->chunkCache[mid].cnkNum < cnkNum)
         lo = mid + 1;
      else if (pInfo->chunkCache[mid].cnkNum > cnkNum)
         hi = mid - 1;
      else  /* cache hit */
         return mid;
   }

   return -1;
}
#endif

_kernel_oserror *xFiles_getChunkInfo(xFiles_info *pInfo, unsigned cnkNum, xFiles_chunk *pChunk)
{
   _kernel_oserror *err;
#ifndef NOCHUNKCACHE
   int cacheIndex = xFiles__cacheLookup(pInfo, cnkNum);

   if (cacheIndex != -1)
   {
      *pChunk = pInfo->chunkCache[cacheIndex].chunk;
      xFiles_checkChunk(pInfo, pChunk);
      return NULL;
   }
#endif

   if (err = xFiles_read(pInfo, pChunk,
                         xFiles_chunkAddress(pInfo, cnkNum),
                         sizeof(xFiles_chunk)), err)
      return err;

#ifndef NOCHUNKCACHE
   if (pInfo->cacheUsed >= xFiles_CHUNKCACHE)
   {
      pInfo->cacheUsed--;
      cacheIndex = rand() % xFiles_CHUNKCACHE;
      memmove(&pInfo->chunkCache[cacheIndex], &pInfo->chunkCache[cacheIndex+1],
              sizeof(xFiles_chunkCacheItem) * (pInfo->cacheUsed - cacheIndex));
   }

   /* Got a space in the cache now */

   for (cacheIndex = 0;
        cacheIndex < pInfo->cacheUsed && cnkNum > pInfo->chunkCache[cacheIndex].cnkNum;
        cacheIndex++)
      ;

   memmove(&pInfo->chunkCache[cacheIndex+1], &pInfo->chunkCache[cacheIndex],
           sizeof(xFiles_chunkCacheItem) * (pInfo->cacheUsed - cacheIndex));
   pInfo->cacheUsed++;

   pInfo->chunkCache[cacheIndex].cnkNum = cnkNum;
   pInfo->chunkCache[cacheIndex].chunk  = *pChunk;
#endif

   return NULL;
}

_kernel_oserror *xFiles_setChunkInfo(xFiles_info *pInfo, unsigned cnkNum, const xFiles_chunk *pChunk)
{
   _kernel_oserror *err;
   int cacheIndex;

   xFiles_checkChunk(pInfo, pChunk);

   /* There has to be a special case for cnkNum == 0 which updates
    * the cached information in the header before the actual index
    * is written
    */

   if (cnkNum == 0)
   {
      if (pChunk->offset < sizeof(xFiles_header))
      {
         TRACE("Attempt to write chunk %d with illegal offset %08x\n", cnkNum, pChunk->offset);
      }

      ASSERT(pChunk->usage != FREE);
      ASSERT(pChunk->offset >= sizeof(xFiles_header));

      pInfo->fileHeader.chunkTable = *pChunk;
   }

   if (err = xFiles_write(pInfo, (void *) pChunk, xFiles_chunkAddress(pInfo, cnkNum), sizeof(xFiles_chunk)), err)
      return err;

   /* Write through cache */

#ifndef NOCHUNKCACHE
   if (cacheIndex = xFiles__cacheLookup(pInfo, cnkNum), cacheIndex != -1)
   {
      pInfo->chunkCache[cacheIndex].cnkNum = cnkNum;
      pInfo->chunkCache[cacheIndex].chunk  = *pChunk;
   }
#endif

   if (cnkNum == 0)
      return xFiles_updateHeader(pInfo);
   else
      return NULL;
}

_kernel_oserror *xFiles_readChunk(xFiles_info *pInfo, void *pBuffer,
                                  unsigned cnkNum, unsigned pos, unsigned size)
{
   _kernel_oserror *err;
   xFiles_chunk chunk;

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (pos + size > chunk.allocSize)
   {
      TRACE("readChunk: chunk = [%08x, %08x], cnkNum = %08x, pos = %08x, size = %08x\n",
             chunk.offset, chunk.size, cnkNum, pos, size);
      return &xFiles_Outside;
   }

   return xFiles_read(pInfo, pBuffer, chunk.offset + pos, size);
}

_kernel_oserror *xFiles_erase(xFiles_info *pInfo, unsigned pos, unsigned size)
{
#ifdef ERASE
   _kernel_oserror *err;
   unsigned chunk;

   if (err = xFiles_claimBuffer(size), err)
      return err;

   memset(xFiles_windowBuffer, 0xAA, _min(size, xFiles_windowBufferSize));

   while (size > 0)
   {
      chunk = _min(size, xFiles_windowBufferSize);
      if (err = xFiles_write(pInfo, xFiles_windowBuffer, pos, chunk), err)
         goto fail;
      pos += chunk;
      size -= chunk;
   }
   return xFiles_releaseBuffer();

fail:
   (void) xFiles_releaseBuffer();
   return err;
#else
   (void) pInfo;
   (void) pos;
   (void) size;
   return NULL;
#endif
}

_kernel_oserror *xFiles_writeChunk(xFiles_info *pInfo, void *pBuffer,
                                   unsigned cnkNum, unsigned pos, unsigned size)
{
   _kernel_oserror *err;
   xFiles_chunk chunk;

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (pos + size > chunk.allocSize)
   {
      TRACE("writeChunk: chunk = [%08x, %08x], pos = %08x, size = %08x\n",
             chunk.offset, chunk.size, pos, size);
      return &xFiles_Outside;
   }

   return xFiles_write(pInfo, pBuffer, chunk.offset + pos, size);
}

_kernel_oserror *xFiles_writeAndGrow(xFiles_info *pInfo, void *pBuffer,
                                     unsigned cnkNum, unsigned pos, unsigned size)
{
   _kernel_oserror *err;
   xFiles_chunk chunk;

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (pos + size > chunk.size)
   {
      if (err = xFiles_setChunkSize(pInfo, cnkNum, pos + size), err)
         return err;
   }

   return xFiles_write(pInfo, pBuffer, chunk.offset + pos, size);
}

_kernel_oserror *xFiles_squashFile(xFiles_info *pInfo, BOOL force)
{
   _kernel_oserror *err;
   _kernel_swi_regs regs;
   unsigned fileLength;
   int now, compactAge;

#ifndef NOCOMPACT
   if (err = xFiles_getLength(pInfo, &fileLength), err)
      return err;

   (void) _kernel_swi(OS_ReadMonotonicTime, &regs, &regs);
   now = regs.r[0];

   compactAge = now - pInfo->lastCompact;
   if (force || compactAge > 3000)
   {
      if (pInfo->fileHeader.waste > 1024 && fileLength / pInfo->fileHeader.waste < 5)
         return xFiles_Compact(pInfo);

      pInfo->lastCompact = now;
   }
#endif

   return NULL;
}

_kernel_oserror *xFiles_updateHeader(xFiles_info *pInfo)
{
   _kernel_oserror *err;

   if (err = xFiles_write(pInfo, &pInfo->fileHeader, 0, sizeof(pInfo->fileHeader)), err)
      return err;

   return NULL;
}

_kernel_oserror *xFiles_moveToEnd(xFiles_info *pInfo, unsigned cnkNum)
{
   xFiles_chunk chunk;
   _kernel_oserror *err;
   unsigned newOffset, copyFrom, copyTo, totalSize, bitSize;

   /*TRACE("Attempting to move chunk %d to the end of the file\n", cnkNum);*/

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (err = xFiles_getLength(pInfo, &newOffset), err)
      return err;

   if (err = xFiles_claimBuffer(chunk.allocSize), err)
      return err;

   copyFrom  = chunk.offset;
   copyTo    = newOffset;
   totalSize = chunk.allocSize;

   if (err = xFiles_setLength(pInfo, newOffset + totalSize), err)
      return err;

   while (totalSize > 0)
   {
      bitSize = _min(totalSize, xFiles_windowBufferSize);

      if (err = xFiles_read(pInfo, xFiles_windowBuffer, copyFrom, bitSize), err)
         goto truncate;
      if (err = xFiles_write(pInfo, xFiles_windowBuffer, copyTo, bitSize), err)
         goto truncate;

      copyFrom  += bitSize;
      copyTo    += bitSize;
      totalSize -= bitSize;
   }

   if (err = xFiles_releaseBuffer(), err)
      return err;

   /* Copied OK, so update the information */

   chunk.offset = newOffset;
   if (err = xFiles_setChunkInfo(pInfo, cnkNum, &chunk), err)
      goto truncate;

   return NULL;

   /* If copying fails (probably because the disc is full or something) then
    * attempt to truncate the image file back to the length it had before we
    * started messing about.
    */

truncate:
   (void) xFiles_releaseBuffer();
   (void) xFiles_setLength(pInfo, newOffset);
   return err;
}

/* Unhook a chunk by placing it's reference in the free list and counting
 * the space it used as wasted.
 */
_kernel_oserror *xFiles_freeChunk(xFiles_info *pInfo, unsigned cnkNum)
{
   _kernel_oserror *err;
   xFiles_chunk chunk;


   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (err = xFiles_erase(pInfo, chunk.offset, chunk.size), err)
      return err;

   pInfo->fileHeader.waste += chunk.size;

   chunk.offset    = pInfo->fileHeader.freeChunk;
   chunk.size      =
   chunk.usage     =
   chunk.allocSize = FREE;  /* 'FREE' */

   pInfo->fileHeader.freeChunk = cnkNum;

   if (err = xFiles_setChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   return xFiles_updateHeader(pInfo);
}

/* Main allocation routine. This sets the length of a chunk. At the moment it
 * simplistically always moves the chunk to the end of the file.
 */

_kernel_oserror *xFiles_setChunkSize(xFiles_info *pInfo, unsigned cnkNum, unsigned newSize)
{
   _kernel_oserror *err;
   unsigned fileSize;
   xFiles_chunk chunk;
   BOOL isAtEnd;
   unsigned newAllocSize;
   BOOL changedHeader = FALSE;

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (err = xFiles_getLength(pInfo, &fileSize), err)
      return err;

   if (1)
   {
      unsigned chunkEnd = chunk.offset + chunk.allocSize;
      if (chunkEnd > fileSize)
         TRACE("Hmm, chunkEnd = %08x, fileSize = %08x\n", chunkEnd, fileSize);
      else if (chunkEnd < fileSize && chunkEnd > fileSize - pInfo->fileHeader.allocationUnit + 1)
         TRACE("How queer, chunkEnd = %08x, fileSize = %08x\n", chunkEnd, fileSize);
      if (chunk.offset != xFiles_roundDown(pInfo, chunk.offset))
         TRACE("chunk.offset = %08x\n", chunk.offset);
      if (chunk.allocSize != xFiles_roundDown(pInfo, chunk.allocSize))
         TRACE("chunk.allocSize = %08x\n", chunk.allocSize);
      if (chunk.allocSize < xFiles_roundUp(pInfo, chunk.size))
         TRACE("chunk.size = %08x, chunk.allocSize = %08x\n", chunk.size, chunk.allocSize);
      if (fileSize != xFiles_roundDown(pInfo, fileSize))
         TRACE("fileSize = %08x\n", fileSize);   
   }

   isAtEnd = (chunk.offset + chunk.allocSize) == fileSize;

   newAllocSize = xFiles_roundUp(pInfo, newSize);

   /* Growing */

   if (newAllocSize > chunk.allocSize)
   {
      if (!isAtEnd)
      {
         if (err = xFiles_moveToEnd(pInfo, cnkNum), err)
            return err;

         if (err = xFiles_erase(pInfo, chunk.offset, chunk.allocSize), err)
            return err;

         chunk.offset = fileSize;
         fileSize += chunk.allocSize;
         isAtEnd = TRUE;

         pInfo->fileHeader.waste += chunk.allocSize;
         changedHeader = TRUE;
      }
   }

   /* Growing or shrinking */

   if (isAtEnd)
   {
      if (err = xFiles_setLength(pInfo, fileSize - chunk.allocSize + newAllocSize), err)
         return err;

      chunk.allocSize = newAllocSize;
   }
   else
   {
      int oldWaste = chunk.allocSize - xFiles_roundUp(pInfo, chunk.size);
      int newWaste = newAllocSize    - xFiles_roundUp(pInfo, newSize);

      pInfo->fileHeader.waste += (newWaste - oldWaste);
      if (newWaste != oldWaste)
         changedHeader = TRUE;
   }

   chunk.size = newSize;

   if (err = xFiles_setChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (changedHeader && (err = xFiles_updateHeader(pInfo), err))
      return err;

   return NULL;
}

/* Move a block in the file without trashing it */

_kernel_oserror *xFiles_moveBlock(xFiles_info *pInfo, unsigned to, unsigned from, int size)
{
   _kernel_oserror *err;

   if (size < 0)
      return &xFiles_OutOfRange;

   if (from == to || size == 0)
      return NULL;

   if (err = xFiles_claimBuffer(size), err)
      return err;

   if (to < from)
   {
      int fragSize;

      while (size > 0)
      {
         fragSize = _min(size, xFiles_windowBufferSize);

         if (err = xFiles_read(pInfo, xFiles_windowBuffer, from, fragSize), err)
            goto failed;
         if (err = xFiles_write(pInfo, xFiles_windowBuffer, to, fragSize), err)
            goto failed;

         from += fragSize;
         to   += fragSize;
         size -= fragSize;
      }
   }
   else if (to > from)
   {
      int fragSize;
      from += size;
      to   += size;

      while (size > 0)
      {
         fragSize = _min(size, xFiles_windowBufferSize);

         from -= fragSize;
         to   -= fragSize;

         if (err = xFiles_read(pInfo, xFiles_windowBuffer, from, fragSize), err)
            goto failed;
         if (err = xFiles_write(pInfo, xFiles_windowBuffer, to, fragSize), err)
            goto failed;

         size -= fragSize;
      }
   }

   return xFiles_releaseBuffer();

failed:
   (void) xFiles_releaseBuffer();
   return err;
}

/* Make a space in the middle of a chunk. If 'by' is positive everything from pos
 * upwards will be moved up by pos bytes. If 'by' is negative everything from pos
 * upwards will be moved down by pos bytes. In other words if 'by' is negative it
 * deletes backwards rather than deleting forwards.
 */

_kernel_oserror *xFiles_midExtend(xFiles_info *pInfo, unsigned cnkNum, int pos, int by)
{
   _kernel_oserror *err;
   xFiles_chunk chunk;
   int amountToMove;

   if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
      return err;

   if (pos > chunk.size || pos < 0 || pos + by < 0)
      return &xFiles_OutOfRange;

   amountToMove = chunk.size - pos;

   if (by > 0)
   {
      /* Extend it first */

      if (err = xFiles_setChunkSize(pInfo, cnkNum, chunk.size + by), err)
         return err;

      /* Chunk may have moved so we need to find out where it is again */

      if (err = xFiles_getChunkInfo(pInfo, cnkNum, &chunk), err)
         return err;

      if (err = xFiles_moveBlock(pInfo, chunk.offset + pos + by, chunk.offset + pos, amountToMove), err)
         return err;
   }
   else if (by < 0)
   {
      if (err = xFiles_moveBlock(pInfo, chunk.offset + pos + by, chunk.offset + pos, amountToMove), err)
         return err;

      if (err = xFiles_setChunkSize(pInfo, cnkNum, chunk.size + by), err)
         return err;
   }

   return NULL;
}

/* Make the free chunk list non-empty
 */

_kernel_oserror *xFiles_makeFreeChunks(xFiles_info *pInfo)
{
   _kernel_oserror *err;
   xFiles_chunk chunkTable;
   xFiles_chunk newChunk;
   int c;
   unsigned nChunks;

   if (pInfo->fileHeader.freeChunk != 0)
      return NULL;

   /* The free list is empty, so extend the chunk table and add a few
    * new entries to the free list.
    */

   if (err = xFiles_getChunkInfo(pInfo, 0, &chunkTable), err)
      return err;

   nChunks = chunkTable.size / sizeof(xFiles_chunk);  /* how many just now? */

   /* Grow the table */

   if (err = xFiles_setChunkSize(pInfo, 0, chunkTable.size + xFiles_NEWCHUNKS * sizeof(xFiles_chunk)), err)
      return err;

   newChunk.offset    = 0;
   newChunk.size      =
   newChunk.usage     =
   newChunk.allocSize = FREE;  /* 'FREE' */

   for (c = 0; c < xFiles_NEWCHUNKS; c++)
   {
      if (err = xFiles_setChunkInfo(pInfo, nChunks + c, &newChunk), err)
         return err;

      newChunk.offset = nChunks + c;  /* Ready for next one */
  }

  pInfo->fileHeader.freeChunk = newChunk.offset;

  return xFiles_updateHeader(pInfo);
}

/* Create a new chunk with zero length.
 */

_kernel_oserror *xFiles_newChunk(xFiles_info *pInfo, unsigned *pCnkNum)
{
   _kernel_oserror *err;
   xFiles_chunk freeChunk;
   unsigned newChunk;

   if (err = xFiles_makeFreeChunks(pInfo), err)
      return err;

   newChunk = pInfo->fileHeader.freeChunk;

   if (err = xFiles_getChunkInfo(pInfo, newChunk, &freeChunk), err)
      return err;

   pInfo->fileHeader.freeChunk = freeChunk.offset;    /* chain to next free chunk */

   if (err = xFiles_updateHeader(pInfo), err)
      return err;

   if (err = xFiles_getLength(pInfo, &freeChunk.offset), err)
      return err;

   freeChunk.size  = 0;
   freeChunk.usage = 1;      /* There must be one user, surely? */
   freeChunk.allocSize = xFiles_roundUp(pInfo, 1);  /* make it one block long */

   if (err = xFiles_setLength(pInfo, freeChunk.offset + freeChunk.allocSize), err)
      return err;

   if (err = xFiles_setChunkInfo(pInfo, newChunk, &freeChunk), err)
      return err;

   if (pCnkNum) *pCnkNum = newChunk;

   return NULL;
}

/* Build a new, empty filesystem in the specified file.
 */

_kernel_oserror *xFiles_buildNewFilesystem(xFiles_info *pInfo)
{
   _kernel_oserror *err;
   unsigned tablePos;

   if (err = xFiles_setLength(pInfo, 0), err)  /* truncate */
      return err;

   pInfo->fileHeader.allocationUnit    = xFiles_ALLOCATIONUNIT;

   tablePos = xFiles_roundUp(pInfo, sizeof(xFiles_header));

   pInfo->fileHeader.sig                  = xFiles_SIG;
   pInfo->fileHeader.hdrSize              = sizeof(xFiles_header);  /* surprise! */
   pInfo->fileHeader.structureVersion     = xFiles_STRUCTUREVERSION;
   pInfo->fileHeader.directoryVersion     = xFiles_DIRECTORYVERSION;
   pInfo->fileHeader.chunkTable.offset    = tablePos;
   pInfo->fileHeader.chunkTable.size      = sizeof(xFiles_chunk);
   pInfo->fileHeader.chunkTable.usage     = 1;
   pInfo->fileHeader.chunkTable.allocSize = xFiles_roundUp(pInfo, sizeof(xFiles_chunk));
   pInfo->fileHeader.rootChunk            = 0;
   pInfo->fileHeader.freeChunk            = 0;
   pInfo->fileHeader.waste                = 0;

   if (err = xFiles_write(pInfo, &pInfo->fileHeader, 0, sizeof(pInfo->fileHeader)), err)
      return err;

   /* Write a second copy of the chunkTable entry in the header. This is actually the
    * 1 entry long chunktable in this minimal filesystem.
    */

   if (err = xFiles_write(pInfo, &pInfo->fileHeader.chunkTable, tablePos, sizeof(xFiles_chunk)), err)
      return err;

   if (err = xFiles_setLength(pInfo, tablePos + pInfo->fileHeader.chunkTable.allocSize), err)
      return err;

   if (err = xFiles_cDir(pInfo, 0, &pInfo->fileHeader.rootChunk), err)
      return err;

   if (err = xFiles_updateHeader(pInfo), err)
      return err;

   return NULL;
}

/* The specified image file is open, so update our flags.
 */

_kernel_oserror *xFiles_OpenImage(xFiles_info *pInfo)
{
   _kernel_swi_regs regs;
   _kernel_oserror *err;
   unsigned imageSize;

   pInfo->compacting = FALSE;
   pInfo->cacheUsed = 0;

   (void) _kernel_swi(OS_ReadMonotonicTime, &regs, &regs);
   pInfo->lastCompact = regs.r[0];

   pInfo->readOnly = FALSE;          /* doesn't seem to work */
   pInfo->fileSize = (unsigned) -1;  /* impossible value     */
   pInfo->flags    = 0;              /* nothing for now      */

   if (err = xFiles_getLength(pInfo, &imageSize), err)
      return err;

   /* Handle the special case where the image is zero length by building the default
    * header, chunk table and root directory
    */

   if (imageSize == 0)
   {
      if (pInfo->readOnly)
         return &xFiles_CantFake;

      if (err = xFiles_buildNewFilesystem(pInfo), err)
         return err;
   }
   else
   {
      if (err = xFiles_read(pInfo, &pInfo->fileHeader, 0, sizeof(pInfo->fileHeader)), err)
         return err;

      if (pInfo->fileHeader.sig != xFiles_SIG)
         return &xFiles_ImageCorrupt;

      /* If the image is a funny size it probably wasn't closed properly so we
       * need to compact it otherwise future allocations will be non-aligned
       */

      if (imageSize != xFiles_roundDown(pInfo, imageSize))
      {
         if (err = xFiles_Compact(pInfo), err)
            return err;
      }
   }

   /* No error, so link it in */

   xFiles_AddAtHead(&xFiles_openFiles, &pInfo->li);

   return NULL;
}

_kernel_oserror *xFiles_CloseImage(xFiles_info *pInfo)
{
   _kernel_oserror *err;

   if (err = xFiles_FlushFileInfo(pInfo), err)
      return err;

   if (err = xFiles_squashFile(pInfo, TRUE), err)
      return err;

   xFiles_Remove(&xFiles_openFiles, &pInfo->li);

   free(pInfo);
   return NULL;
}

/*********************************************************************************/
/*                                                                               */
/*   Directory functions                                                         */
/*                                                                               */
/*   - Create an empty directory                                                 */
/*   - Create an entry                                                           */
/*   - Lookup an entry                                                           */
/*   - Update file details                                                       */
/*   - Change name (not actually needed: can use create entry / remove entry)    */
/*   - Remove an entry                                                           */
/*   - Fill a buffer with a selection of entries                                 */
/*                                                                               */
/*********************************************************************************/

/* Read a directory's header
 */

_kernel_oserror *xFiles_getDirHeader(xFiles_info *pInfo, unsigned dirObject, xFiles_dirHeader *pHdr)
{
   _kernel_oserror *err;

   if (err = xFiles_readChunk(pInfo, (void *) pHdr, dirObject, 0, sizeof(xFiles_dirHeader)), err)
      return err;

   if (pHdr->sig != xFiles_DIRSIG)
   {
      xFiles_chunk dirChunk;
      (void) xFiles_getChunkInfo(pInfo, dirObject, &dirChunk);
      TRACE("Directory object %d broken (%08x, %08x)\n", dirObject, dirChunk.offset, dirChunk.size);
      return &xFiles_BrokenDir;
   }

   return NULL;
}

/* Write a directory's header
 */

_kernel_oserror *xFiles_setDirHeader(xFiles_info *pInfo, unsigned dirObject, const xFiles_dirHeader *pHdr)
{
   _kernel_oserror *err;

   if (pHdr->sig != xFiles_DIRSIG)
      return &xFiles_BadDirMark;

   if (err = xFiles_writeChunk(pInfo, (void *) pHdr, dirObject, 0, sizeof(xFiles_dirHeader)), err)
      return err;

   return NULL;
}

/* Make space in a directory's hash table. This might involve relocating
 * the directory's contents -- caller beware
 */

_kernel_oserror *xFiles_makeSpaceInHashTable(xFiles_info *pInfo, unsigned dirObject)
{
   xFiles_dirHeader dirHdr;
   xFiles_chunk     dirChunk;
   _kernel_oserror *err;

   if (err = xFiles_getChunkInfo(pInfo, dirObject, &dirChunk), err)
      return err;

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   if (dirHdr.used >= dirHdr.size)
   {
      int shiftBy  = sizeof(xFiles_dirHash) * xFiles_GROWDIRBY;
      int hashPos  = sizeof(xFiles_dirHeader);
      int shiftPos = hashPos + sizeof(xFiles_dirHash) * dirHdr.size;

      if (err = xFiles_midExtendDirectory(pInfo, dirObject, shiftPos, shiftBy), err)
         return err;

      dirHdr.size += xFiles_GROWDIRBY;

      if (err = xFiles_setDirHeader(pInfo, dirObject, &dirHdr), err)
         return err;
   }

   return NULL;
}

_kernel_oserror *xFiles_midExtendDirectory(xFiles_info *pInfo, unsigned dirObject, int pos, int by)
{
   _kernel_oserror *err;

   if (err = xFiles_midExtend(pInfo, dirObject, pos, by), err)
      return err;

   if (err = xFiles_relocateHashes(pInfo, dirObject, pos, by), err)
      return err;

   return NULL;
}

/* Modify the hash table in a directory after changing the size of the directory. All hash
 * offsets which are >= pos will be relocated by 'by'. When this is called the directory
 * header's used field will be valid, but size might not be. Anyway size doesn't matter.
 */

_kernel_oserror *xFiles_relocateHashes(xFiles_info *pInfo, unsigned dirObject, int pos, int by)
{
   xFiles_dirHeader dirHdr;
   xFiles_chunk     dirChunk;
   _kernel_oserror *err;
   int hashSize, hashPos, bitSize;

   if (err = xFiles_getChunkInfo(pInfo, dirObject, &dirChunk), err)
      return err;

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   hashPos  = sizeof(xFiles_dirHeader);
   hashSize = dirHdr.used * sizeof(xFiles_dirHash);

   if (err = xFiles_claimBuffer(hashSize), err)
      return err;

   /* Now set about reading the whole hash table and updating it */

   while (hashSize > 0)
   {
      int howMany;
      xFiles_dirHash *pHash;
      BOOL modified;

      bitSize = _min(hashSize, xFiles_windowBufferSize);

      howMany = bitSize / sizeof(xFiles_dirHash);
      bitSize = howMany * sizeof(xFiles_dirHash);

      if (err = xFiles_readChunk(pInfo, xFiles_windowBuffer, dirObject, hashPos, bitSize), err)
         goto failed;

      /* Update them */

      for (modified = FALSE, pHash = (xFiles_dirHash *) xFiles_windowBuffer; howMany > 0; pHash++, howMany--)
      {
         if (pHash->entryPos >= pos)
         {
            pHash->entryPos += by;
            modified = TRUE;
         }
      }

      if (modified)
      {
         if (err = xFiles_writeChunk(pInfo, xFiles_windowBuffer, dirObject, hashPos, bitSize), err)
            goto failed;
      }

      hashSize -= bitSize;
      hashPos  += bitSize;
   }

   return xFiles_releaseBuffer();

failed:
   (void) xFiles_releaseBuffer();
   return err;
}

/* Create an empty directory returning it's chunk number */

_kernel_oserror *xFiles_cDir(xFiles_info *pInfo, unsigned parent, unsigned *pCnkNum)
{
   xFiles_dirHeader dir;
   _kernel_oserror *err;
   unsigned cnkNum;

   dir.sig     = xFiles_DIRSIG;
   dir.parent  = parent;
   dir.size    =
   dir.used    = 0;

   if (err = xFiles_newChunk(pInfo, &cnkNum), err)
      return err;

   if (err = xFiles_writeAndGrow(pInfo, &dir, cnkNum, 0, sizeof(dir)), err)
      return err;

   if (pCnkNum) *pCnkNum = cnkNum;
   return NULL;
}

/* Create an entry in a directory. This call assumes that the entry doesn't already
 * exist and doesn't do any checks to that effect.
 */

_kernel_oserror *xFiles_createDirEntry(xFiles_info *pInfo, unsigned dirObject,
                                       xFiles_dirHash *pDirHash, xFiles_dirEntry *pDirEnt,
                                       const char *pName)
{
   _kernel_oserror *err;
   xFiles_dirHeader dirHdr;
   xFiles_dirHash   dirHash;
   xFiles_chunk     dirChunk;
   int entrySize, nameLen;

   if (err = xFiles_makeSpaceInHashTable(pInfo, dirObject), err)
      return err;

   /* At this stage it's guaranteed that there's at least one free space
    * in the hash table.
    */

   if (err = xFiles_getChunkInfo(pInfo, dirObject, &dirChunk), err)
      return err;

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   nameLen = strlen(pName);
   pDirEnt->nameLen = nameLen;

   entrySize = sizeof(xFiles_dirEntry) + (nameLen + 4) & ~3;

   if (err = xFiles_setChunkSize(pInfo, dirObject, dirChunk.size + entrySize), err)
      return err;

   /* Write the entry first, then the name, then the hash, then the header */

   if (err = xFiles_writeChunk(pInfo, (void *) pDirEnt, dirObject,
                               dirChunk.size, sizeof(xFiles_dirEntry)), err)
      return err;

   if (err = xFiles_writeChunk(pInfo, (void *) pName, dirObject,
                               dirChunk.size + sizeof(xFiles_dirEntry), nameLen + 1), err)
      return err;

   memset(dirHash.nameStart, 0, 4);
   memcpy(dirHash.nameStart, pName, _min(nameLen, 4));

   dirHash.entryPos = dirChunk.size;
   dirHash.node     = pDirHash->node;

   if (err = xFiles_writeChunk(pInfo, &dirHash, dirObject,
                         sizeof(xFiles_dirHeader) + sizeof(xFiles_dirHash) * dirHdr.used,
                         sizeof(xFiles_dirHash)), err)
      return err;

   dirHdr.used++;

   if (err = xFiles_setDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   return NULL;
}

static int memcicmp(const void *m1, const void *m2, size_t size)
{
   const char *c1 = m1;
   const char *c2 = m2;

   if (memcmp(m1, m2, size) == 0)
      return 0;

   while (size > 0 && tolower(*c1) == tolower(*c2))
      c1++, c2++, size--;

   return (size == 0) ? 0 : tolower(*c1) - tolower(*c2);
}

/* Primitive routine to scan a directory for the specified name. The name ends
 * at the first '.' or '\0'
 */

_kernel_oserror *xFiles_dirLookup(xFiles_info *pInfo, unsigned dirObject, const char *pName,
                                  unsigned *pHashOffset, unsigned *pEntryOffset,
                                  xFiles_dirHash *pDirHash, xFiles_dirEntry *pDirEnt)
{
   _kernel_oserror *err;
   xFiles_dirHeader dirHdr;
   xFiles_dirEntry  dirEnt;
   int              hashSize;
   int              hashPos;
   int              bitSize;
   int              nameLen;
   char            *dotPos;
   char             nameBuf[xFiles_MAXNAME+1];
   unsigned         hashOfs;

   if (dotPos = strchr(pName, '.'), dotPos)
      nameLen = dotPos-pName;
   else
      nameLen = strlen(pName);

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   hashPos  = sizeof(xFiles_dirHeader);
   hashOfs  = hashPos;
   hashSize = dirHdr.used * sizeof(xFiles_dirHash);

   if (err = xFiles_claimBuffer(hashSize), err)
      return err;

   while (hashSize > 0)
   {
      int howMany;
      xFiles_dirHash *pHash;

      bitSize = _min(hashSize, xFiles_windowBufferSize);

      howMany = bitSize / sizeof(xFiles_dirHash);
      bitSize = howMany * sizeof(xFiles_dirHash);

      if (err = xFiles_readChunk(pInfo, xFiles_windowBuffer, dirObject, hashPos, bitSize), err)
         goto failed;

      for (pHash = (xFiles_dirHash *) xFiles_windowBuffer;
           howMany > 0;
           pHash++, hashOfs += sizeof(xFiles_dirHash), howMany--)
      {
         if (memcicmp(pName, pHash->nameStart, _min(nameLen, 4)) != 0)
            continue;

         if (err = xFiles_readChunk(pInfo, &dirEnt, dirObject, pHash->entryPos, sizeof(dirEnt)), err)
            goto failed;

         if (nameLen != dirEnt.nameLen)
            continue;

         if (err = xFiles_readChunk(pInfo, nameBuf, dirObject,
                                    pHash->entryPos + sizeof(dirEnt), dirEnt.nameLen+1), err)
            goto failed;

         if (memcicmp(pName, nameBuf, nameLen) != 0)
            continue;

         /* Found it! */

         if (err = xFiles_releaseBuffer(), err)
            return err;

         *pHashOffset  = hashOfs;
         *pEntryOffset = pHash->entryPos;
         if (pDirEnt)  *pDirEnt  = dirEnt;
         if (pDirHash) *pDirHash = *pHash;

         return NULL;
      }

      hashSize -= bitSize;
      hashPos  += bitSize;
   }

   if (err = xFiles_releaseBuffer(), err)
      return err;

   *pHashOffset  = 0;
   *pEntryOffset = 0;

   return NULL;

failed:
   (void) xFiles_releaseBuffer();
   return err;
}

/* Scan a directory for a particular node.
 */

_kernel_oserror *xFiles_dirLookupByNode(xFiles_info *pInfo, unsigned dirObject, unsigned node,
                                        unsigned *pHashOffset, unsigned *pEntryOffset,
                                        xFiles_dirHash *pDirHash)
{
   _kernel_oserror *err;
   xFiles_dirHeader dirHdr;
   int              hashSize;
   int              hashPos;
   int              bitSize;
   unsigned         hashOfs;

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   hashPos  = sizeof(xFiles_dirHeader);
   hashOfs  = hashPos;
   hashSize = dirHdr.used * sizeof(xFiles_dirHash);

   if (err = xFiles_claimBuffer(hashSize), err)
      return err;

   while (hashSize > 0)
   {
      int howMany;
      xFiles_dirHash *pHash;

      bitSize = _min(hashSize, xFiles_windowBufferSize);

      howMany = bitSize / sizeof(xFiles_dirHash);
      bitSize = howMany * sizeof(xFiles_dirHash);

      if (err = xFiles_readChunk(pInfo, xFiles_windowBuffer, dirObject, hashPos, bitSize), err)
         goto failed;

      for (pHash = (xFiles_dirHash *) xFiles_windowBuffer;
           howMany > 0;
           pHash++, hashOfs += sizeof(xFiles_dirHash), howMany--)
      {
         if (pHash->node == node)
         {
            if (err = xFiles_releaseBuffer(), err)
               return err;

            *pHashOffset  = hashOfs;
            *pEntryOffset = pHash->entryPos;
            if (pDirHash) *pDirHash = *pHash;

            return NULL;
         }
      }

      hashSize -= bitSize;
      hashPos  += bitSize;
   }

   if (err = xFiles_releaseBuffer(), err)
      return err;

   *pHashOffset  = 0;
   *pEntryOffset = 0;

   return NULL;

failed:
   (void) xFiles_releaseBuffer();
   return err;
}

/* Remove an entry from a directory given the offset of the entry's hash. At the moment
 * this is pretty simple minded: it just does to midExtend operations.
 */

_kernel_oserror *xFiles_deleteDirEntry(xFiles_info *pInfo, unsigned dirObject, unsigned hashOffset)
{
   _kernel_oserror *err;
   xFiles_dirHeader dirHdr;
   xFiles_dirHash   dirHash;
   xFiles_dirEntry  dirEnt;
   int entryPos;
   int entrySize;

   if (err = xFiles_getDirHeader(pInfo, dirObject, &dirHdr), err)
      return err;

   if (err = xFiles_readChunk(pInfo, &dirHash, dirObject, hashOffset, sizeof(dirHash)), err)
      return err;

   if (err = xFiles_readChunk(pInfo, &dirEnt, dirObject, dirHash.entryPos, sizeof(dirEnt)), err)
      return err;

   if (err = xFiles_midExtendDirectory(pInfo, dirObject, hashOffset + sizeof(dirHash), -sizeof(dirHash)), err)
      return err;

   entryPos  = dirHash.entryPos - sizeof(dirHash);  /* just been moved down */
   entrySize = sizeof(dirEnt) + (dirEnt.nameLen + 4) & ~3;

   if (err = xFiles_midExtendDirectory(pInfo, dirObject, entryPos + entrySize, -entrySize), err)
      return err;

   dirHdr.used--;
   dirHdr.size--;

   return xFiles_setDirHeader(pInfo, dirObject, &dirHdr);
}

/* Parse a pathname returning the parent directory (or 0 if the path is null which
 * means that this is the root), hashOffset, entryOffset and optionally directory
 * entry for the item referred to. If an element in the path other than the last is
 * actually a file then the result is the same as if the file was not found.
 */

_kernel_oserror *xFiles_parsePath(xFiles_info *pInfo, const char *pName, unsigned *pParent,
                                  unsigned *pHashOffset, unsigned *pEntryOffset,
                                  xFiles_dirHash *pDirHash, xFiles_dirEntry *pDirEnt,
                                  BOOL excludeLeaf)
{
   _kernel_oserror *err;
   const char *pPath, *nextDot;
   unsigned parent;
   unsigned hashOffset = 1, entryOffset = 1;
   unsigned curDir;
   xFiles_dirEntry dirEnt;
   xFiles_dirHash  dirHash;
   xFiles_chunk    rootChunk;

   /*TRACE("xFiles_parsePath(%p, \"%s\", %p, %p, %p, %p, excludeLeaf = %s)\n",
                  pInfo, pName, pParent, pHashOffset, pEntryOffset, pDirEnt, excludeLeaf ? "TRUE" : "FALSE");*/

   curDir = pInfo->fileHeader.rootChunk;

   if (err = xFiles_getChunkInfo(pInfo, curDir, &rootChunk), err) return err;

   /* Fake up a dirHash, dirEnt for the root directory */

   dirHash.node = curDir;

   dirEnt.load  =
   dirEnt.exec  = 0;
   dirEnt.attr  = xFiles_meRead | xFiles_meWrite | xFiles_isDir;
   dirEnt.size  = rootChunk.size;

   pPath = pName;

   for (;;)
   {
      parent = curDir;

      if (*pPath == '\0')
         goto found;

      nextDot = strchr(pPath, '.');

      if (!nextDot && excludeLeaf)
         goto found;

      if (err = xFiles_dirLookup(pInfo, curDir, pPath, &hashOffset, &entryOffset, &dirHash, &dirEnt), err)
         return err;

      if (hashOffset == 0)
         break;

      if (!nextDot)
         goto found;

      if ((dirEnt.attr & xFiles_isDir) == 0)
         break;         /* can't go on if this isn't a directory */

      pPath = nextDot + 1;
      curDir = dirHash.node;
   }

   /* Only gets here if the object couldn't be found */

   if (pParent)      *pParent      = 0;
   if (pHashOffset)  *pHashOffset  = 0;
   if (pEntryOffset) *pEntryOffset = 0;

   return NULL;

   /* If excludeLeaf was true the the hashOffset, entryOffset and dirEnt items
    * are not much use to the caller.
    */

found:
   if (pParent)      *pParent      = parent;
   if (pHashOffset)  *pHashOffset  = excludeLeaf ? 1 : hashOffset;
   if (pEntryOffset) *pEntryOffset = excludeLeaf ? 1 : entryOffset;
   if (pDirHash)     *pDirHash     = dirHash;
   if (pDirEnt)      *pDirEnt      = dirEnt;

   return NULL;
}

