xref: /dports/editors/e93/e93/text.c

// Lowest level Text handling functions
// Copyright (C) 2000 Core Technologies.

// This file is part of e93.
//
// e93 is free software; you can redistribute it and/or modify
// it under the terms of the e93 LICENSE AGREEMENT.
//
// e93 is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// e93 LICENSE AGREEMENT for more details.
//
// You should have received a copy of the e93 LICENSE AGREEMENT
// along with e93; see the file "LICENSE.TXT".

#include	"includes.h"

// NOTE: text is managed using a "all in memory" model
// so, as far as most functions are concerned, the entire
// text data structure is kept in memory while it is being edited
// The OS swapping functions are charged with mapping the data in and out
//
// To manage the text data efficiently, and to keep memory
// from fragmenting, all text is kept in "Chunks"
// Each chunk allocates CHUNK_SIZE bytes of space from the free memory pool
// and the text of the document is split among them. The chunks are linked
// to each other in order. When text is inserted, additional chunks are allocated
// as necessary, and linked into the list at the appropriate location.
// Chunks keep track of how many bytes are currently used within them.
// Lines are allowed to span chunks.
// Chunks are not allowed to contain 0 bytes.


static void DisposeChunk(CHUNK_HEADER *chunk)
// deallocate the memory used by chunk
{
	MDisposePtr(chunk->data);
	MDisposePtr(chunk);
}

static CHUNK_HEADER *CreateChunk()
// create a chunk header, and its corresponding data
// if there is a problem, SetError, and return NULL
{
	CHUNK_HEADER
		*chunk;

	if((chunk=(CHUNK_HEADER *)MNewPtrClr(sizeof(CHUNK_HEADER))))
	{
		if((chunk->data=(UINT8 *)MNewPtr(CHUNK_SIZE)))
		{
			return(chunk);
		}
		MDisposePtr(chunk);
	}
	return((CHUNK_HEADER *)NULL);
}

bool UniverseSanityCheck(TEXT_UNIVERSE *universe)
// check the sanity of the text universe, report result
// if there is something wrong, crash or SetError, and return false
{
	CHUNK_HEADER
		*previousChunk,
		*currentChunk;
	UINT32
		totalChunks,
		actualTotalLines,
		chunkTotalBytes,
		chunkTotalLines;
	UINT32
		i;
	bool
		sawCachedChunk,
		fail;

	fail=sawCachedChunk=false;
	chunkTotalBytes=0;
	chunkTotalLines=0;
	totalChunks=0;
	previousChunk=NULL;
	currentChunk=universe->firstChunkHeader;
	while(currentChunk)
	{
		totalChunks++;
		if(currentChunk==universe->cacheChunkHeader)		// see if this is the cached chunk
		{
			sawCachedChunk=true;
			if(chunkTotalLines!=universe->cacheLines)
			{
				SetError("Cache lines %d does not agree with %d\n",universe->cacheLines,chunkTotalLines);
				fail=true;
			}
			if(chunkTotalBytes!=universe->cacheBytes)
			{
				SetError("Cache bytes %d does not agree with actual %d\n",universe->cacheBytes,chunkTotalBytes);
				fail=true;
			}
		}
		if(currentChunk->previousHeader==previousChunk)
		{
			if(currentChunk->totalBytes)
			{
				actualTotalLines=0;
				for(i=0;i<currentChunk->totalBytes;i++)
				{
					if(currentChunk->data[i]=='\n')
					{
						actualTotalLines++;
					}
				}
				if(actualTotalLines==currentChunk->totalLines)
				{
					chunkTotalBytes+=currentChunk->totalBytes;
					chunkTotalLines+=currentChunk->totalLines;
					previousChunk=currentChunk;
					currentChunk=currentChunk->nextHeader;
				}
				else
				{
					SetError("Incorrect number of lines @ %X (he said there were %d, I saw %d)\n",currentChunk,currentChunk->totalLines,actualTotalLines);
					fail=true;
				}
			}
			else
			{
				SetError("Empty chunk @ %X\n",currentChunk);
				fail=true;
			}
		}
		else
		{
			SetError("Incorrect previous header %X @ %X\n",currentChunk->previousHeader,currentChunk);
			fail=true;
		}
	}
	if(!fail)
	{
		if(universe->lastChunkHeader==previousChunk)
		{
			if(chunkTotalBytes==universe->totalBytes)
			{
				if(chunkTotalLines==universe->totalLines)
				{
					if(!universe->cacheChunkHeader||sawCachedChunk)
					{
						if(totalChunks)
						{
							SetError("Total chunks %d, efficiency: %d%%\n",totalChunks,((universe->totalBytes/CHUNK_SIZE)*100)/(totalChunks));
						}
						else
						{
							SetError("Total chunks %d\n",totalChunks);
						}
					}
					else
					{
						SetError("Invalid cache chunk header: %X\n",universe->cacheChunkHeader);
						fail=true;
					}
				}
				else
				{
					SetError("Total lines mismatch: chunks=%d, universe=%d\n",chunkTotalLines,universe->totalLines);
					fail=true;
				}
			}
			else
			{
				SetError("Total bytes mismatch: chunks=%d, universe=%d\n",chunkTotalBytes,universe->totalBytes);
				fail=true;
			}
		}
		else
		{
			SetError("The universe's last chunk did not match last one found\n");
			fail=true;
		}
	}
	return(!fail);
}

static void GetPosStartChunkAndDirection(TEXT_UNIVERSE *universe,UINT32 position,CHUNK_HEADER **chunk,UINT32 *currentBytes,UINT32 *currentLines,bool *backwards)
// return a chunk, and a direction to start searching,
// given a position that is desired
// NOTE: this uses the current cache information to help speed things up
// NOTE ALSO: position must not be out of range
{
	if(universe->cacheChunkHeader)					// if there is a cached chunk, see which direction we should go from it
	{
		*backwards=(position<universe->cacheBytes);	// see which direction from the cache we need to go
		*currentBytes=universe->cacheBytes;
		*currentLines=universe->cacheLines;
		*chunk=universe->cacheChunkHeader;
	}
	else
	{
		*backwards=false;							// work from the start
		*currentBytes=0;
		*currentLines=0;
		*chunk=universe->firstChunkHeader;
	}
}

static void GetLineStartChunkAndDirection(TEXT_UNIVERSE *universe,UINT32 line,CHUNK_HEADER **chunk,UINT32 *currentBytes,UINT32 *currentLines,bool *backwards)
// return a chunk, and a direction to start searching,
// given a line number that is desired
// NOTE: this uses the current cache information to help speed things up
// NOTE ALSO: line must not be out of range
{
	if(universe->cacheChunkHeader)					// if there is a cached chunk, see which direction we should go from it
	{
		*backwards=(line<=universe->cacheLines);	// see which direction from the cache we need to go
		*currentBytes=universe->cacheBytes;
		*currentLines=universe->cacheLines;
		*chunk=universe->cacheChunkHeader;
	}
	else
	{
		*backwards=false;							// work from the start
		*currentBytes=0;
		*currentLines=0;
		*chunk=universe->firstChunkHeader;
	}
}

void PositionToChunkPositionPastEnd(TEXT_UNIVERSE *universe,UINT32 position,CHUNK_HEADER **chunk,UINT32 *offset)
// locate the chunk which contains the byte at position within universe
// if there are no chunks in the universe, return chunk set to NULL, offset set to 0
// if the given position is past the end of the universe, return with chunk pointed to the
// last chunk of the universe, and offset as the last chunk's total-bytes
// NOTE: this will update the cache position to the chunk which is returned
{
	CHUNK_HEADER
		*currentChunk;
	UINT32
		currentPosition,
		currentLine;
	bool
		backwards;

	if(position>=universe->totalBytes)							// quick test to get us to the end faster (and avoid some checks in the loop below)
	{
		if((universe->cacheChunkHeader=(*chunk)=universe->lastChunkHeader))	// point to the last chunk (if there is one)
		{
			universe->cacheBytes=universe->totalBytes-universe->lastChunkHeader->totalBytes;
			universe->cacheLines=universe->totalLines-universe->lastChunkHeader->totalLines;
			(*offset)=universe->lastChunkHeader->totalBytes;	// pass back max offset
		}
		else
		{
			(*offset)=0;
		}
	}
	else
	{
		GetPosStartChunkAndDirection(universe,position,&currentChunk,&currentPosition,&currentLine,&backwards);
		if(backwards)
		{
			while(currentPosition>position)
			{
				currentChunk=currentChunk->previousHeader;
				currentPosition-=currentChunk->totalBytes;
				currentLine-=currentChunk->totalLines;
			}
		}
		else
		{
			while((currentPosition+=currentChunk->totalBytes)<=position)
			{
				currentLine+=currentChunk->totalLines;
				currentChunk=currentChunk->nextHeader;
			}
			currentPosition-=currentChunk->totalBytes;
		}
		universe->cacheChunkHeader=(*chunk)=currentChunk;
		universe->cacheBytes=currentPosition;
		universe->cacheLines=currentLine;
		(*offset)=position-currentPosition;
	}
}

void PositionToChunkPosition(TEXT_UNIVERSE *universe,UINT32 position,CHUNK_HEADER **chunk,UINT32 *offset)
// locate the chunk which contains the byte at position within universe
// if there is no chunk in universe at position, return NULL/0
// NOTE: this will update the cache position to the chunk which is returned
{
	PositionToChunkPositionPastEnd(universe,position,chunk,offset);
	if((*chunk)&&((*offset)>=(*chunk)->totalBytes))			// if past end, then return NULL/0
	{
		*chunk=NULL;
		*offset=0;
	}
}

void PositionToLinePosition(TEXT_UNIVERSE *universe,UINT32 position,UINT32 *line,UINT32 *lineOffset,CHUNK_HEADER **chunk,UINT32 *chunkOffset)
// locate the line which contains the byte at position within universe
// also return chunk, and chunkOffset that point to the START of line
// if position is past the end of universe, line will be the last line
// and lineOffset will be one past the last character of line
// chunk/chunkOffset will point to the start of the last line (if there is one, NULL/0 if not)
// NOTE: this will update the cache position to the chunk which contained position
{
	CHUNK_HEADER
		*currentChunk;
	UINT32
		currentOffset,
		currentPosition,
		currentLine,
		lineStartOffset,
		numNewLines;
	bool
		backwards;

	currentOffset=0;
	if(position>=universe->totalBytes)						// quick test to get us to the end faster (and avoid some checks in the loop below)
	{
		if((universe->cacheChunkHeader=currentChunk=universe->lastChunkHeader))	// point to the last chunk (if there is one)
		{
			universe->cacheBytes=universe->totalBytes-universe->lastChunkHeader->totalBytes;
			universe->cacheLines=currentLine=universe->totalLines-universe->lastChunkHeader->totalLines;
			currentOffset=universe->lastChunkHeader->totalBytes;	// max offset to begin searching backwards from
		}
	}
	else
	{
		GetPosStartChunkAndDirection(universe,position,&currentChunk,&currentPosition,&currentLine,&backwards);
		if(backwards)
		{
			while(currentPosition>position)
			{
				currentChunk=currentChunk->previousHeader;
				currentPosition-=currentChunk->totalBytes;
				currentLine-=currentChunk->totalLines;
			}
		}
		else
		{
			while((currentPosition+=currentChunk->totalBytes)<=position)
			{
				currentLine+=currentChunk->totalLines;
				currentChunk=currentChunk->nextHeader;
			}
			currentPosition-=currentChunk->totalBytes;
		}
		universe->cacheChunkHeader=currentChunk;
		universe->cacheBytes=currentPosition;
		universe->cacheLines=currentLine;
		currentOffset=position-currentPosition;					// offset to the given position
	}

	*lineOffset=0;												// at the moment, no offset
	if(currentChunk)											// if this is valid, then there were some bytes in the universe
	{
		// walk backwards from the current position until the beginning of the current chunk, and then until the first newline encountered (if there are any)
		numNewLines=0;											// tells how many new lines seen in this chunk backwards from current position
		lineStartOffset=0;
		while(currentOffset)
		{
			if(currentChunk->data[--currentOffset]=='\n')
			{
				if(!numNewLines)
				{
					lineStartOffset=currentOffset+1;			// offset into the chunk that points to the start of the line
				}
				numNewLines++;
			}
			if(!numNewLines)									// increment length into the line until a newline is seen
			{
				(*lineOffset)++;
			}
		}
		*line=currentLine+numNewLines;							// this tells which line the position fell into
		if(!numNewLines)
		{
			while(currentChunk->previousHeader&&!(currentChunk->previousHeader->totalLines))	// push back through all chunks which do not contain new lines
			{
				currentChunk=currentChunk->previousHeader;
				(*lineOffset)+=currentChunk->totalBytes;		// this many more bytes into the line
			}
			if(currentChunk->previousHeader)					// step back into one which contains newlines
			{
				currentChunk=currentChunk->previousHeader;
				currentOffset=lineStartOffset=currentChunk->totalBytes;
			}
			while(currentOffset&&currentChunk->data[--currentOffset]!='\n')
			{
				(*lineOffset)++;								// keep moving back
				lineStartOffset=currentOffset;					// offset in chunk to start of line
			}
		}
		if(lineStartOffset>=currentChunk->totalBytes)
		{
			*chunk=currentChunk->nextHeader;					// move one past (possibly off the end)
			*chunkOffset=0;
		}
		else
		{
			*chunk=currentChunk;
			*chunkOffset=lineStartOffset;
		}
	}
	else
	{
		*chunk=NULL;
		*chunkOffset=0;
		*line=universe->totalLines;								// since it is past the end, the line is this, work backwards to get the offset
	}
}

void LineToChunkPosition(TEXT_UNIVERSE *universe,UINT32 line,CHUNK_HEADER **chunk,UINT32 *offset,UINT32 *position)
// locate the chunk which contains the byte at the start of line within universe
// position is the absolute offset within the text to the start of line
// if no chunk contains a byte that starts line, chunk will be NULL, offset will be 0
// position will be the number of bytes in the text buffer
// NOTE: this will update the cache position to the chunk which is returned
{
	CHUNK_HEADER
		*currentChunk;
	UINT32
		currentByte,
		currentLine;
	bool
		backwards;

	if(line>universe->totalLines||!(universe->firstChunkHeader))
	{
		if((universe->cacheChunkHeader=universe->lastChunkHeader))	// point to the last chunk (if there is one)
		{
			universe->cacheBytes=universe->totalBytes-universe->lastChunkHeader->totalBytes;
			universe->cacheLines=currentLine=universe->totalLines-universe->lastChunkHeader->totalLines;
		}
		(*chunk)=NULL;
		(*offset)=0;
		(*position)=universe->totalBytes;
	}
	else
	{
		GetLineStartChunkAndDirection(universe,line,&currentChunk,&currentByte,&currentLine,&backwards);	// find out where to start searching from
		if(backwards)
		{
			while(currentChunk->previousHeader&&currentLine>=line)		// run through the chunks until we get to the one BEFORE or during which this line starts
			{
				currentChunk=currentChunk->previousHeader;
				currentLine-=currentChunk->totalLines;
				currentByte-=currentChunk->totalBytes;
			}
		}
		else
		{
			while((currentLine+=currentChunk->totalLines)<line)			// run through the chunks looking for the start of the given line
			{
				currentByte+=currentChunk->totalBytes;
				currentChunk=currentChunk->nextHeader;					// keep going
			}
			currentLine-=currentChunk->totalLines;						// back up, to start of chunk which contains the requested line
		}
		*offset=0;
		while(currentLine<line)											// move through until enough lines have been counted
		{
			if(currentChunk->data[(*offset)++]=='\n')
			{
				currentLine++;
			}
			currentByte++;
		}
		(*position)=currentByte;
		(*chunk)=currentChunk;
		if((*offset)>=currentChunk->totalBytes)							// if needed, move to the next chunk
		{
			(*chunk)=currentChunk->nextHeader;
			(*offset)=0;
		}
	}
}


void AddToChunkPosition(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **newChunk,UINT32 *newOffset,UINT32 distanceToMove)
// move forward from chunk/offset by distanceToMove
// if distanceToMove pushes us off the end, return NULL, 0
// It is ok to pass newChunk as a pointer to chunk
// NOTE: this does not update the cache position
{
	while(chunk&&(distanceToMove>=(chunk->totalBytes-offset)))
	{
		distanceToMove-=(chunk->totalBytes-offset);
		chunk=chunk->nextHeader;
		offset=0;
	}
	if((*newChunk=chunk))
	{
		*newOffset=offset+distanceToMove;
	}
	else
	{
		*newOffset=0;
	}
}

void ChunkPositionToNextLine(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **newChunk,UINT32 *newOffset,UINT32 *distanceMoved)
// locate the line that begins after chunk, and offset
// if chunk is NULL, return NULL, and distanceMoved=0, otherwise
// attempt to locate the start of the next line, returning chunk, and offset.
// if there is no next line start, return NULL, and distance moved as the amount we traversed before
// discovering there was no next line
// It is ok to pass newChunk as a pointer to chunk
// NOTE: this does not update the cache position
{
	bool
		found;

	(*distanceMoved)=0;

	if(chunk)
	{
		found=false;
		if(chunk->totalLines)									// see if there are any lines in this chunk (if not, dont bother looking for next new line)
		{
			while(!found&&offset<chunk->totalBytes)
			{
				if(chunk->data[offset]=='\n')
				{
					found=true;
				}
				else
				{
					(*distanceMoved)++;
					offset++;
				}
			}
			if(!found)
			{
				chunk=chunk->nextHeader;
				offset=0;
			}
		}
		else
		{
			(*distanceMoved)=chunk->totalBytes-offset;			// if no lines, skip the rest of the first chunk
			chunk=chunk->nextHeader;
			offset=0;
		}

		if(!found)
		{
			while(chunk&&!chunk->totalLines)					// run through the chunks looking for one that contains a line
			{
				(*distanceMoved)+=chunk->totalBytes;
				chunk=chunk->nextHeader;						// skip all chunks with no lines in them
			}
			if(chunk)											// this is the chunk that contains the new line we were looking for, so locate it
			{
				while(chunk->data[offset]!='\n')
				{
					offset++;
				}
				(*distanceMoved)+=offset;
				found=true;
			}
		}
		if(found)												// at this point, we have found the new line, chunk, and offset point to the new line character, so skip over it, and return what's next
		{
			(*distanceMoved)++;
			offset++;
			if(offset>=chunk->totalBytes)						// push through to the next chunk
			{
				chunk=chunk->nextHeader;
				offset=0;
			}
		}
	}
	(*newChunk)=chunk;
	(*newOffset)=offset;
}

static void CopyTextToChunk(CHUNK_HEADER *chunk,UINT32 offset,UINT8 *text,UINT32 numBytes,UINT32 *numLines)
// copy text into chunk at offset for numBytes
// also count up how many new-lines were seen during the copy
// return numLines as the total number of new-line characters that were copied
{
	UINT8
		*dst;
	UINT32
		i;

	dst=&(chunk->data[offset]);
	(*numLines)=0;
	for(i=0;i<numBytes;i++)
	{
		if((dst[i]=text[i])=='\n')
		{
			(*numLines)++;
		}
	}
}

static void CopyChunkToChunk(CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **sourceChunk,UINT32 *sourceOffset,UINT32 numBytes,UINT32 *numLines)
// copy the text starting at sourceChunk/sourceOffset into chunk at offset for numBytes
// also count up how many new-lines were seen during the copy
// return numLines as the total number of new-line characters that were copied
// also return with sourceChunk/sourceOffset pointing to the byte just after the last one copied
{
	CHUNK_HEADER
		*sChunk;
	UINT8
		*src,
		*dst;
	UINT32
		i,
		sOffset,
		sourceLimit;

	dst=&(chunk->data[offset]);
	(*numLines)=0;
	if((sChunk=(*sourceChunk)))
	{
		src=sChunk->data;
		sOffset=*sourceOffset;
		sourceLimit=sChunk->totalBytes;
		for(i=0;i<numBytes&&sChunk;i++)
		{
			if((dst[i]=src[sOffset])=='\n')
			{
				(*numLines)++;
			}
			if(++sOffset>=sourceLimit)
			{
				sOffset=0;
				if((sChunk=sChunk->nextHeader))
				{
					src=sChunk->data;
					sourceLimit=sChunk->totalBytes;
				}
			}
		}
		(*sourceChunk)=sChunk;
		(*sourceOffset)=sOffset;
	}
}

static void DetermineNewLines(CHUNK_HEADER *chunk,UINT32 offset,UINT32 numBytes,UINT32 *numLines)
// count the number of new-line characters at offset of chunk, for numBytes
// return numLines as the total number of new-line characters that were counted
{
	UINT8
		*dst;
	UINT32
		i;

	dst=&(chunk->data[offset]);
	(*numLines)=0;
	for(i=0;i<numBytes;i++)
	{
		if((dst[i])=='\n')
		{
			(*numLines)++;
		}
	}
}

static void DisposeChunkList(CHUNK_HEADER *startChunk)
// dispose of a linked list of chunks
{
	CHUNK_HEADER
		*nextChunk;

	while(startChunk)
	{
		nextChunk=startChunk->nextHeader;
		DisposeChunk(startChunk);
		startChunk=nextChunk;
	}
}

static bool CreateChunkList(CHUNK_HEADER **startChunk,CHUNK_HEADER **endChunk,UINT32 numChunks)
// create a linked list of empty chunks
// if there is a problem, SetError, free anything allocated, and return false
{
	bool
		fail;
	CHUNK_HEADER
		*chunk;

	(*startChunk)=(*endChunk)=NULL;
	fail=false;
	while(numChunks&&!fail)
	{
		if((chunk=CreateChunk()))
		{
			if(*endChunk)
			{
				(*endChunk)->nextHeader=chunk;
				chunk->previousHeader=(*endChunk);
				(*endChunk)=chunk;
			}
			else
			{
				(*startChunk)=(*endChunk)=chunk;
			}
			numChunks--;
		}
		else
		{
			DisposeChunkList(*startChunk);					// remove the partially created chunk list
			fail=true;
		}
	}
	return(!fail);
}

// Text insertion cases
// these routines handle all of the possible cases that can occur while
// inserting text

static bool InsertWithRoomInChunk(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **textChunk,UINT32 *textOffset,UINT32 numBytes)
// the chunk that the text is going to be inserted into
// contains enough free space to accept the entire inserted text
{
	UINT32
		linesInserted;

	MMoveMem(&(chunk->data[offset]),&(chunk->data[offset+numBytes]),chunk->totalBytes-offset);	// move data within the chunk to make room
	CopyChunkToChunk(chunk,offset,textChunk,textOffset,numBytes,&linesInserted);
	chunk->totalBytes+=numBytes;							// bump number of bytes in this chunk
	chunk->totalLines+=linesInserted;						// bump number of lines in this chunk
	universe->totalBytes+=numBytes;							// adjust universal understanding
	universe->totalLines+=linesInserted;
	return(true);											// this cannot fail
}

static bool InsertWithRoomInTwoChunks(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **textChunk,UINT32 *textOffset,UINT32 numBytes)
// the chunk where the text insertion starts, and the next chunk contain enough free space
// to allow the text to be inserted
{
	CHUNK_HEADER
		*secondChunk;
	UINT32
		linesInserted,
		tempInserted;
	UINT32
		amountToMove,
		distanceToMove;

	secondChunk=chunk->nextHeader;
	if(numBytes+offset<=CHUNK_SIZE)								// see if the added text can be contained completely within the first chunk
	{
		distanceToMove=numBytes-(CHUNK_SIZE-chunk->totalBytes);	// for speed, we would like to move as much as possible to the second chunk, but for memory efficiency, we would like to move as little as possible! (memory efficiency turns out to be better)

		MMoveMem(secondChunk->data,&(secondChunk->data[distanceToMove]),secondChunk->totalBytes);	// move second chunk's data out of the way for the add
		CopyTextToChunk(secondChunk,0,&(chunk->data[chunk->totalBytes-distanceToMove]),distanceToMove,&tempInserted);	// move data from first chunk to second chunk
		chunk->totalBytes-=distanceToMove;
		secondChunk->totalBytes+=distanceToMove;				// this many more bytes now in use in second chunk
		chunk->totalLines-=tempInserted;
		secondChunk->totalLines+=tempInserted;

		MMoveMem(&(chunk->data[offset]),&(chunk->data[offset+numBytes]),chunk->totalBytes-offset);	// move data within the chunk to make room
		CopyChunkToChunk(chunk,offset,textChunk,textOffset,numBytes,&linesInserted);	// copy the data into the chunk
		chunk->totalBytes+=numBytes;							// bump number of bytes in this chunk
		chunk->totalLines+=linesInserted;						// bump number of lines in this chunk
		universe->totalBytes+=numBytes;							// adjust universal understanding
		universe->totalLines+=linesInserted;
	}
	else
	{
		distanceToMove=numBytes-(CHUNK_SIZE-chunk->totalBytes);	// need to push second chunk data forward this distance
		MMoveMem(secondChunk->data,&(secondChunk->data[distanceToMove]),secondChunk->totalBytes);	// move second chunk's data out of the way for the add
		secondChunk->totalBytes+=distanceToMove;				// this many more bytes now in use in second chunk
		amountToMove=chunk->totalBytes-offset;					// number of bytes to move from first to second

		CopyTextToChunk(secondChunk,offset+numBytes-CHUNK_SIZE,&(chunk->data[offset]),amountToMove,&tempInserted);	// move data from first chunk to second chunk
		chunk->totalLines-=tempInserted;
		secondChunk->totalLines+=tempInserted;

		CopyChunkToChunk(chunk,offset,textChunk,textOffset,CHUNK_SIZE-offset,&tempInserted);	// copy source text into first chunk
		chunk->totalBytes=CHUNK_SIZE;
		chunk->totalLines+=tempInserted;

		CopyChunkToChunk(secondChunk,0,textChunk,textOffset,numBytes-(CHUNK_SIZE-offset),&linesInserted);	// copy remaining text into second chunk
		secondChunk->totalLines+=linesInserted;
		universe->totalLines+=linesInserted+tempInserted;		// add number of lines added in first chunk

		universe->totalBytes+=numBytes;							// adjust universal understanding
	}
	return(true);												// this cannot fail
}

static bool InsertWithNoRoom(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **textChunk,UINT32 *textOffset,UINT32 numBytes)
// the text to be inserted cannot fit within its two adjacent chunks
// so, chunks will have to be created, and the text put into them
{
	UINT32
		linesInserted,
		tempInserted;
	UINT32
		numChunks,
		maxToMove,
		bytesToMove;
	CHUNK_HEADER
		*startChunk,
		*endChunk;

	numChunks=(numBytes-(CHUNK_SIZE-(chunk->totalBytes))+CHUNK_SIZE-1)/CHUNK_SIZE;
	if(CreateChunkList(&startChunk,&endChunk,numChunks))					// create just enough chunks to hold the data
	{
		chunk->nextHeader->previousHeader=endChunk;							// link new chunks onto the list
		endChunk->nextHeader=chunk->nextHeader;
		chunk->nextHeader=startChunk;
		startChunk->previousHeader=chunk;
		universe->totalBytes+=numBytes;										// more bytes in the universe now

		if(numBytes<(CHUNK_SIZE-offset))									// see if the bytes we are adding can be added into the first chunk
		{
			bytesToMove=chunk->totalBytes+numBytes-CHUNK_SIZE;
			CopyTextToChunk(endChunk,0,&(chunk->data[chunk->totalBytes-bytesToMove]),bytesToMove,&tempInserted);	// move data from old last chunk to new last chunk
			endChunk->totalBytes=bytesToMove;								// this many bytes in end chunk
			endChunk->totalLines=tempInserted;
			chunk->totalLines-=tempInserted;
			MMoveMem(&(chunk->data[offset]),&(chunk->data[offset+numBytes]),chunk->totalBytes-bytesToMove-offset);	// move data within the original chunk to make room

			CopyChunkToChunk(chunk,offset,textChunk,textOffset,numBytes,&tempInserted);	// copy text into this chunk
			chunk->totalBytes=CHUNK_SIZE;									// this is now completely full
			chunk->totalLines+=tempInserted;								// added this many lines
			universe->totalLines+=tempInserted;								// add to the universe too
		}
		else
		{
			if((numBytes+offset)/CHUNK_SIZE<numChunks)						// see if we can move the stuff after the given offset all the way into the end chunk
			{
				CopyTextToChunk(endChunk,0,&(chunk->data[offset]),chunk->totalBytes-offset,&tempInserted);	// move data from old last chunk to new last chunk
			}
			else
			{
				if(chunk->totalBytes==offset)								// minor kludge to make sure we are left pointing to the correct spot
				{
					tempInserted=0;
				}
				else
				{
					CopyTextToChunk(endChunk,(numBytes+offset)%CHUNK_SIZE,&(chunk->data[offset]),chunk->totalBytes-offset,&tempInserted);	// move data from old last chunk to new last chunk
				}
			}
			endChunk->totalBytes=chunk->totalBytes-offset;					// this many bytes in end chunk at the moment
			chunk->totalBytes=offset;										// this many bytes in here
			chunk->totalLines-=tempInserted;								// removed lines from here
			endChunk->totalLines=tempInserted;								// placed them here
			linesInserted=0;
			while(numBytes&&chunk)
			{
				maxToMove=CHUNK_SIZE-offset;								// can move this many bytes
				if(numBytes>maxToMove)
				{
					bytesToMove=maxToMove;
				}
				else
				{
					bytesToMove=numBytes;
				}
				CopyChunkToChunk(chunk,offset,textChunk,textOffset,bytesToMove,&tempInserted);	// copy text into this chunk
				chunk->totalBytes+=bytesToMove;								// bump number of bytes in this chunk
				chunk->totalLines+=tempInserted;							// bump number of lines in this chunk
				linesInserted+=tempInserted;								// keep track of total number of lines inserted so far
				numBytes-=bytesToMove;										// this many less bytes to move now
				chunk=chunk->nextHeader;									// point to next chunk to fill
				offset=0;													// from this point on, the offset is always 0
			}
			universe->totalLines+=linesInserted;							// increment the number of lines in the universe
		}
		return(true);														// done
	}
	return(false);
}

static bool InsertAtLastChunk(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,CHUNK_HEADER **textChunk,UINT32 *textOffset,UINT32 numBytes)
// text is being inserted into the last chunk of the universe, and
// the chunk does not contain enough free space to hold it
// NOTE: this code must handle the case where offset is CHUNK_SIZE
{
	UINT32
		linesInserted,
		tempInserted;
	UINT32
		numChunks,
		maxToMove,
		bytesToMove;
	CHUNK_HEADER
		*startChunk,
		*endChunk;

	numChunks=(numBytes-(CHUNK_SIZE-(chunk->totalBytes))+CHUNK_SIZE-1)/CHUNK_SIZE;
	if(CreateChunkList(&startChunk,&endChunk,numChunks))					// create just enough chunks to hold the data
	{
		chunk->nextHeader=startChunk;										// link new chunks onto the list
		startChunk->previousHeader=chunk;
		universe->lastChunkHeader=endChunk;									// update the universe
		universe->totalBytes+=numBytes;										// more bytes in the universe now
		if((numBytes+offset)/CHUNK_SIZE<numChunks)
		{
			CopyTextToChunk(endChunk,0,&(chunk->data[offset]),chunk->totalBytes-offset,&tempInserted);	// move data from old last chunk to new last chunk
		}
		else
		{
			if(chunk->totalBytes==offset)									// minor kludge to make sure we are left pointing to the correct spot
			{
				tempInserted=0;
			}
			else
			{
				CopyTextToChunk(endChunk,(numBytes+offset)%CHUNK_SIZE,&(chunk->data[offset]),chunk->totalBytes-offset,&tempInserted);	// move data from old last chunk to new last chunk
			}
		}
		endChunk->totalBytes=chunk->totalBytes-offset;						// this many bytes in end chunk at the moment
		chunk->totalBytes=offset;											// this many bytes in here
		chunk->totalLines-=tempInserted;									// removed lines from here
		endChunk->totalLines=tempInserted;									// placed them here
		linesInserted=0;
		while(numBytes&&chunk)
		{
			maxToMove=CHUNK_SIZE-offset;									// can move this many bytes
			if(numBytes>maxToMove)
			{
				bytesToMove=maxToMove;
			}
			else
			{
				bytesToMove=numBytes;
			}
			CopyChunkToChunk(chunk,offset,textChunk,textOffset,bytesToMove,&tempInserted);	// copy text into this chunk
			chunk->totalBytes+=bytesToMove;									// bump number of bytes in this chunk
			chunk->totalLines+=tempInserted;								// bump number of lines in this chunk
			linesInserted+=tempInserted;									// keep track of total number of lines inserted so far
			numBytes-=bytesToMove;											// this many less bytes to move now
			chunk=chunk->nextHeader;										// point to next chunk to fill
			offset=0;														// from this point on, the offset is always 0
		}
		universe->totalLines+=linesInserted;								// increment the number of lines in the universe
		return(true);														// done
	}
	return(false);
}

static bool InsertWithNoChunks(TEXT_UNIVERSE *universe,CHUNK_HEADER **textChunk,UINT32 *textOffset,UINT32 numBytes)
// text insertion is happening in an empty text universe
{
	UINT32
		linesInserted,
		tempInserted;
	UINT32
		bytesToMove;
	CHUNK_HEADER
		*chunk,
		*startChunk,
		*endChunk;

	if(CreateChunkList(&startChunk,&endChunk,(numBytes+CHUNK_SIZE-1)/CHUNK_SIZE))	// create just enough chunks to hold the data
	{
		universe->firstChunkHeader=startChunk;
		universe->lastChunkHeader=endChunk;
		universe->totalBytes=numBytes;
		chunk=startChunk;
		linesInserted=0;
		while(chunk&&numBytes)
		{
			if(numBytes>CHUNK_SIZE)
			{
				bytesToMove=CHUNK_SIZE;
			}
			else
			{
				bytesToMove=numBytes;
			}
			CopyChunkToChunk(chunk,0,textChunk,textOffset,bytesToMove,&tempInserted);	// copy the data into the chunk
			chunk->totalBytes=bytesToMove;									// set number of bytes in this chunk
			chunk->totalLines=tempInserted;									// set number of lines in this chunk
			linesInserted+=tempInserted;									// keep track of total number of lines inserted so far
			numBytes-=bytesToMove;											// this many less bytes to move now
			chunk=chunk->nextHeader;										// point to next chunk to fill
		}
		universe->totalLines=linesInserted;									// remember the number of lines in the universe
		return(true);														// done
	}
	return(false);
}

bool InsertUniverseChunks(TEXT_UNIVERSE *universe,UINT32 position,CHUNK_HEADER *textChunk,UINT32 textOffset,UINT32 numBytes)
// insert numBytes of text from textChunk/textOffset into universe starting at position
// if there is a problem, SetError, and return false
// this routine is allowed to either succeed, or fail completely, under no circumstance
// is it allowed to insert only part of the given text
// NOTE: it is illegal for textChunk/textOffset to point to less data than numBytes
// NOTE ALSO: to accommodate inserting unchunked text, textChunk is allowed to be
// larger than CHUNK_SIZE, and textChunk's totalLines field does not have to be accurate
// Finally, this is does not guarantee that it will not alter the chunk list of
// universe before the point of insertion.
// NOTE: if bytes are inserted, this will update the cache to point to the chunk that the insertion started in
{
	bool
		fail;
	CHUNK_HEADER
		*chunk;
	UINT32
		offset;

	fail=false;
	if(numBytes)														// only do more work if bytes to insert
	{
		PositionToChunkPosition(universe,position,&chunk,&offset);		// locate the position, move the cache there
		if(chunk)														// see if inserting within the text
		{
			if(offset>chunk->totalBytes)								// if this is out of range, fudge it back!
			{
				offset=chunk->totalBytes;
			}
			if((offset==0)&&(chunk->previousHeader)&&(chunk->previousHeader->totalBytes<CHUNK_SIZE))	// if inserting at the very start of a chunk, it is more efficient to look one back (if possible)
			{
				universe->cacheChunkHeader=chunk=chunk->previousHeader;
				universe->cacheBytes-=chunk->totalBytes;				// move the cache back one, so it will not be effected by the insert
				universe->cacheLines-=chunk->totalLines;
				offset=chunk->totalBytes;
			}
			if(numBytes<=CHUNK_SIZE-(chunk->totalBytes))				// see if the bytes can be placed in empty space of this chunk
			{
				fail=!InsertWithRoomInChunk(universe,chunk,offset,&textChunk,&textOffset,numBytes);
			}
			else
			{
				if(chunk->nextHeader)									// is there another chunk after this one?
				{
					if(numBytes<=(2*CHUNK_SIZE)-(chunk->totalBytes+chunk->nextHeader->totalBytes))	// is there room in the combined free space of this chunk, and the next one?
					{
						fail=!InsertWithRoomInTwoChunks(universe,chunk,offset,&textChunk,&textOffset,numBytes);
					}
					else
					{
						fail=!InsertWithNoRoom(universe,chunk,offset,&textChunk,&textOffset,numBytes);
					}
				}
				else	// last chunk does not have enough space to hold the text
				{
					fail=!InsertAtLastChunk(universe,chunk,offset,&textChunk,&textOffset,numBytes);
				}
			}
		}
		else
		{
			// inserting text at the very end (cache is set to NULL in this case)
			if((chunk=universe->lastChunkHeader))
			{
				if(numBytes<=CHUNK_SIZE-(chunk->totalBytes))			// see if the bytes can be placed in empty space of this chunk
				{
					fail=!InsertWithRoomInChunk(universe,chunk,chunk->totalBytes,&textChunk,&textOffset,numBytes);
				}
				else
				{
					fail=!InsertAtLastChunk(universe,chunk,chunk->totalBytes,&textChunk,&textOffset,numBytes);
				}
			}
			else
			{
				fail=!InsertWithNoChunks(universe,&textChunk,&textOffset,numBytes);
			}
		}
	}
	return(!fail);
}

bool InsertUniverseText(TEXT_UNIVERSE *universe,UINT32 position,UINT8 *text,UINT32 numBytes)
// insert numBytes of text into universe starting at position
// if there is a problem, SetError, and return false
// this routine is allowed to either succeed, or fail completely, under no circumstance
// is it allowed to insert only part of the given text
// if there is a problem, SetError, and return false
// NOTE: this will update the cache to point to the chunk that the insertion started in
{
	CHUNK_HEADER
		psuedoChunk;														// used to create a chunk that points to text

	psuedoChunk.previousHeader=psuedoChunk.nextHeader=NULL;					// set up fake chunk header, so we can call insert chunk routine
	psuedoChunk.data=text;
	psuedoChunk.totalBytes=numBytes;
	psuedoChunk.totalLines=0;												// this does not have to be set accurately
	return(InsertUniverseChunks(universe,position,&psuedoChunk,0,numBytes));
}

bool ExtractUniverseText(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,UINT8 *text,UINT32 numBytes,CHUNK_HEADER **nextChunk,UINT32 *nextOffset)
// extract numBytes of text from universe at chunk/offset
// if there are not numBytes of text in universe at chunk/offset, then
// as many as possible will be returned
// it is acceptable to pass chunk as NULL, in which case, no bytes will ever be returned
// text must be large enough to accept numBytes or bad things will happen
// if there is a problem, SetError, and return false
{
	UINT32
		numToExtract;

	while(numBytes&&chunk)
	{
		if((chunk->totalBytes-offset)<numBytes)
		{
			numToExtract=chunk->totalBytes-offset;
		}
		else
		{
			numToExtract=numBytes;
		}
		MMoveMem(&chunk->data[offset],text,numToExtract);
		numBytes-=numToExtract;
		text+=numToExtract;
		offset+=numToExtract;
		if(offset>=chunk->totalBytes)
		{
			chunk=chunk->nextHeader;
			offset=0;
		}
	}
	(*nextChunk)=chunk;
	(*nextOffset)=offset;
	return(true);
}

static void UnlinkChunkList(TEXT_UNIVERSE *universe,CHUNK_HEADER *startChunk,CHUNK_HEADER *endChunk)
// unlink the chunks from startChunk to endChunk from universe
{
	if(startChunk->previousHeader)
	{
		startChunk->previousHeader->nextHeader=endChunk->nextHeader;
	}
	else
	{
		universe->firstChunkHeader=endChunk->nextHeader;
	}

	if(endChunk->nextHeader)
	{
		endChunk->nextHeader->previousHeader=startChunk->previousHeader;
	}
	else
	{
		universe->lastChunkHeader=startChunk->previousHeader;
	}
	startChunk->previousHeader=endChunk->nextHeader=NULL;			// terminate the list
}

static void DeleteWithinChunk(TEXT_UNIVERSE *universe,CHUNK_HEADER *chunk,UINT32 offset,UINT32 numBytes,CHUNK_HEADER **nextChunk,UINT32 *nextOffset)
// data within one chunk is being deleted
// NOTE: if the cache points to the given chunk, and it is completely deleted,
// the cache will be moved forward to the next chunk in the list
{
	UINT32
		linesDeleted;

	if(numBytes<chunk->totalBytes)	// see if something will remain after the deletion
	{
		DetermineNewLines(chunk,offset,numBytes,&linesDeleted);
		MMoveMem(&(chunk->data[offset+numBytes]),&(chunk->data[offset]),chunk->totalBytes-(offset+numBytes));	// move back any bytes needed
		chunk->totalBytes-=numBytes;
		chunk->totalLines-=linesDeleted;
		universe->totalBytes-=numBytes;
		universe->totalLines-=linesDeleted;
		if(offset>=chunk->totalBytes)
		{
			(*nextChunk)=chunk->nextHeader;
			(*nextOffset)=0;
		}
		else
		{
			(*nextChunk)=chunk;
			(*nextOffset)=offset;
		}
	}
	else
	{
		if(universe->cacheChunkHeader==chunk)		// if cached chunk is going away, then just move it to the next one
		{
			universe->cacheChunkHeader=chunk->nextHeader;
		}
		(*nextChunk)=chunk->nextHeader;
		(*nextOffset)=0;
		UnlinkChunkList(universe,chunk,chunk);
		universe->totalBytes-=chunk->totalBytes;
		universe->totalLines-=chunk->totalLines;
		DisposeChunkList(chunk);
	}
}

bool DeleteUniverseText(TEXT_UNIVERSE *universe,UINT32 position,UINT32 numBytes)
// delete numBytes of text from universe starting at position
// if there is a problem, SetError, and return false
// this routine is allowed to either succeed, or fail completely, under no circumstance
// is it allowed to delete only part of the given text
// NOTE: this will move the cache position to the chunk where the deletion started
{
	UINT32
		numToDelete;
	CHUNK_HEADER
		*chunk;
	UINT32
		offset;
	bool
		fail;

	fail=false;
	if(numBytes)
	{
		PositionToChunkPosition(universe,position,&chunk,&offset);	// locate the position, move the cache there
		while(numBytes&&chunk)
		{
			if((chunk->totalBytes-offset)<numBytes)
			{
				numToDelete=chunk->totalBytes-offset;
			}
			else
			{
				numToDelete=numBytes;
			}
			DeleteWithinChunk(universe,chunk,offset,numToDelete,&chunk,&offset);
			numBytes-=numToDelete;
		}
	}
	return(!fail);
}

TEXT_UNIVERSE *OpenTextUniverse()
// create the data structures necessary to manage
// a universe of text
// if there is a problem, SetError, and return NULL
{
	TEXT_UNIVERSE
		*universe;

	if((universe=(TEXT_UNIVERSE *)MNewPtr(sizeof(TEXT_UNIVERSE))))	// create an empty universe
	{
		universe->firstChunkHeader=universe->lastChunkHeader=universe->cacheChunkHeader=(CHUNK_HEADER *)NULL;
		universe->totalBytes=0;
		universe->totalLines=0;
		universe->cacheBytes=0;
		universe->cacheLines=0;
		return(universe);
	}
	return((TEXT_UNIVERSE *)NULL);
}

void CloseTextUniverse(TEXT_UNIVERSE *universe)
// dispose of a text universe
{
	DisposeChunkList(universe->firstChunkHeader);
	MDisposePtr(universe);
}