/* 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 || pos >= -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 || pos >= -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 (dirEnt.nameLen == 0 || dirEnt.nameLen > 256)
			{
				xFiles_chunk cnk;

				if (nameLen != 12)
					continue;

				memcpy(nameBuf, pHash->nameStart, 4);
				sprintf(nameBuf + 4, "%08d", pHash->node);

				/* Fix up the rest of the directory entry */

				if (err = xFiles_getChunkInfo(pInfo, pHash->node, &cnk), err)
					return err;

				dirEnt.load =
						dirEnt.exec = 0xFFFFFFFF;
				dirEnt.size = cnk.size;
				dirEnt.attr = xFiles_meRead | xFiles_meWrite;
			}
			else
			{
				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 two 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;
}
