/***************************************
 *													*
 * Module: Memory		
 *													*
 * Organize memory handling. 
 *													*
 ***************************************/

/*#FOLD: Includes */
/************
 *
 * Includes:
 *
 ************/

#include <exec/types.h>
#include <intuition/intuition.h>
#include <exec/memory.h>
#include "src/Editor.h"
/*#ENDFD*/
/*#FOLD: Defines */
/***********
 *
 * Defines:
 *
 ***********/

#define BIGBLOCK (10240L-sizeof(struct Memoryblock))
#define BLOCKSIZE (5120L-sizeof(struct Memoryblock))
/*#ENDFD*/
/*#FOLD: External Functions */
/**********************
 *
 * External Functions:
 *
 **********************/

struct Memoryblock *AllocMem();
void NewList(),AddTail(),Remove(),FreeMem();
/*#ENDFD*/
/*#FOLD: External Variables */
/*********************
 *
 * External Variables:
 *
 *********************/ 

extern struct Editor *actualEditor;
/*#ENDFD*/

/***************
 *		*
 * Functions: *
 *		*
 ***************/

/*#FOLD: freeMemoryblock */
/*******************************************
 *
 * freeMemoryblock(blk)
 *
 * frees the memory of
 * Memoryblocks, without regard for
 * lines that lie in it.
 *
 * blk ^ Memoryblock.
 *
 *******************************************/

void freeMemoryblock(blk)
struct Memoryblock  *blk;
{
	Remove(blk);
	FreeMem(blk,blk->length + sizeof(struct Memoryblock));
}
/*#ENDFD*/
/*#FOLD: newerBlock */
/**********************************************
 *
 * newerBlock(len):
 *
 * used memory for new memory block with len length
 * and returns the pointer
 * in case of error => NULL.
 *
 * len = Length of memory block.
 *
 **********************************************/

struct Memoryblock *newerBlock(len)
ULONG										len;
{
	register struct Memoryblock *blk;
	register struct Memorysection *spst;

	/* Allocate memory: */
	if (blk = AllocMem(len+sizeof(struct Memoryblock),MEMF_CLEAR))
	{
		/*Initialize memory block structure: */
		blk->length = len;
		blk->free	= len - sizeof(struct Memorysection);
		NewList(&(blk->freeliste));
		spst = (struct Memorysection *)(blk + 1);
		AddTail(&(blk->freeliste),spst);
		spst->len = (UWORD)blk->free;
	}

	return (blk);
}
/*#ENDFD*/
/*#FOLD: searchMemorysection */
/***********************************************
 *
 * searchMemorysection(block,len)
 *
 * Searches for memory piece with len length in the block block
 * and returns the pointer or zero in case
 * of no room.
 *
 * block ^ Memoryblock.
 * len = Length of line (even).
 *
 ***********************************************/

struct Memorysection *searchMemorysection(block,len)
struct Memoryblock								*block;
UWORD															 len;
{
	register UWORD minl,l;
	register struct Memorysection *st,*fnd = NULL;

	/* Now searches through if enough memory: */
	if ((ULONG)len <= block->free)
	{
		/* Minimal length in case found Length <> len */
		minl = len + sizeof(struct Memorysection) + 2;

		/* Searches through list: */
		for (st = block->freeliste.head; st->succ; st = st->succ)
			if ((l = st->len) == len)
			{
				/* Optimal size found: */
				fnd = st;
				break;
			}
			else
				if ((l >= minl) && (l > ((fnd)? fnd->len : 0)))
					/* Search for largest block: */
					fnd = st;
	}

	return (fnd);
}
/*#ENDFD*/
/*#FOLD: ConvertSpstToZline */
/********************************************
 *
 * ConvertSpstToZline(blk,st,len)
 *
 * Converts memory piece in line.
 * If the piece was longer than the line,
 * the piece is shortened, otherwise the piece is removed
 * from the list.
 *
 * blk ^ memory block of memory piece.
 * st ^ memory piece.
 * len = Length of the line
 *
 ********************************************/

struct Zline *ConvertSpstToZline(blk,st,len)
struct Memoryblock				  *blk;
register struct Memorysection		*st;
register UWORD									 len;
{
	register UWORD l;
	register struct Zline *z;

	z = (struct Zline *)st;

	if (st->len == (l = EVENLEN(len)))
		/* Found piece fits exactly: */
		Remove(st);
	else
	{
		/* distribute piece: */
		((UBYTE *)st) += (l += sizeof (struct Zline));
		( st->succ = ((struct Memorysection *)z)->succ )->pred = st;
		( st->pred = ((struct Memorysection *)z)->pred )->succ = st;
		st->len = ((struct Memorysection *)z)->len - l;
	}
	blk->free -= l;

	z->flags	= 0;
	z->len	= len;

	return (z);
}
/*#ENDFD*/
/*#FOLD: getZline */
/***********************************************
 *
 * getZline(len)
 *
 * Tries to get line with len length and,
 * searches through all of the memory blocks.
 * returns pointer to line or
 * zero if no room.
 *
 * len = Length of the line.
 *
 ***********************************************/

struct Zline *getZline(len)
UWORD							len;
{
	register UWORD l;
	register struct Memoryblock *blk,*fblk = NULL;
	register struct Memorysection *st,*fst = NULL;

	/* make even length: */
	l = EVENLEN(len);

	/* run through list of blocks: */
	for (blk = actualEditor->block.head; blk->succ; blk = blk->succ)
		if (st = searchMemorysection(blk,l))
			if (st->len == l)
			{
				/* found optimal memory piece: */
				fblk	= blk;
				fst	= st;
				break;
			}
			else
				if (st->len > ((fst)? fst->len : 0))
				{
					/* searches for largest memory piece: */
					fblk	= blk;
					fst	= st;
				}

	if (fst)
		return (ConvertSpstToZline(fblk,fst,len));
	else
		/* no piece found: */
		return (NULL);
}
/*#ENDFD*/
/*#FOLD: optimalBlock */
/*********************************************
 *
 * optimalBlock(block)
 *
 * Searches through all of the memory pieces of the block
 * and makes one out of all of the memory pieces
 * that lie one after another.
 *
 * block ^ Memoryblock.
 *
 *********************************************/

void optimalBlock				(blk)
register struct Memoryblock *blk;
{
	register struct Memorysection *st1,*st2,*st1e;

	for (st1 = blk->freeliste.head; st1->succ; st1 = st1->succ)
	{
		/* Certain pointer directly behind st1: */
		st1e = (struct Memorysection *)
				 (((UBYTE *)st1) + st1->len + sizeof(struct Memorysection));

		for (st2 = blk->freeliste.head; st2->succ; st2 = st2->succ)
			if (st1e == st2)
			{
				/* memory piece st2 lies behind st1: */
				st1->len += st2->len + sizeof(struct Memorysection);
				blk->free += sizeof(struct Memorysection);
				Remove(st2);
				st1e = (struct Memorysection *)
						 (((UBYTE *)st1)+st1->len+sizeof(struct Memorysection));

				/* begin at the beginning of the list: */
				st2 = (struct Memorysection *) &(blk->freeliste.head);
			}
	}
}
/*#ENDFD*/
/*#FOLD: garbageCollection */
/****************************************
 *
 * garbageCollection(len)
 *
 * cleans the memory until at least
 * len bytes are free. returns pointer.
 * to memory block where there is room
 * or zero if no room.
 * zero if no room.
 *
 * len = number of bytes that should be accomodated
 *         
 *
 ****************************************/

struct Memoryblock *garbageCollection(len)
UWORD												  len;
{
	struct Memoryblock *blk;
	struct Memorysection *st,spst;
	register UBYTE *ptr,*end;
	register struct Zline *z,*fz;
	register UWORD n;
	register struct Zline **zptr;

	for (blk = actualEditor->block.head; blk->succ; blk = blk->succ)
		/* Only garbage collection if more than one memory piece! */
		if ((st = blk->freeliste.head->succ)? st->succ : FALSE)
		{
			/* test for beginning and end of block memory: */
			ptr = (UBYTE *)(blk + 1);
			end = ptr + blk->length;

			/* lines lie at the beginning: */
			while (ptr < end)
			{
				/* searches for lines that lie at next ptr: */
				fz = NULL;
				for (z = actualEditor->zlines.head; z->succ; z = z->succ)
					if ((z >= ptr) && (z < end))
						if ((z < fz) || (fz == NULL))
							fz = z;

				if (fz)
					if (fz != ptr)
					{
						/* note old pointer: */
						z = fz;
						st = (struct Memorysection *)ptr;
						spst = *st;

						/* writes line after ptr: */
						for (n = (EVENLEN(fz->len) + sizeof(struct Zline)) >> 1;
							  n; n--, ((UWORD	*)ptr)++, ((UWORD	*)fz)++ )
							*((UWORD	*)ptr) =	*((UWORD	*)fz);

						/* pointer correction: */
						fz = (struct Zline *)st;
						fz->succ->pred = fz;
						fz->pred->succ = fz;
						if (actualEditor->actual == z)
							actualEditor->actual = fz;
						if	(actualEditor->lineptr == z)
							actualEditor->lineptr =	fz;
						for (n =	0,	zptr = actualEditor->zlinesptr;
								n <= actualEditor->wch; n++, zptr++)
							if (*zptr == z)
							{
								*zptr = fz;
								break;
							}

						st = (struct Memorysection *)ptr;
						st->succ = spst.succ;
						st->pred = spst.pred;
						st->len = spst.len;
						spst.succ->pred = st;
						spst.pred->succ = st;

						/* push memory pieces together: */
						optimalBlock(blk);
					}
					else
						/* set ptr high: */
						ptr += EVENLEN(fz->len) + sizeof(struct Zline);
				else
					/* no more lines in block! */
					break;
			}	/* of while */

			/* Test if there is enough memory: */
			if (searchMemorysection(blk,len))
				return (blk);
		}	/* of if (at least 2 blocks) */

	return (NULL);
}
/*#ENDFD*/
/*#FOLD: newZline */
/*****************************************
 *
 * newZline(len)
 *
 * get room for new line,
 * fits characters in len.
 * returns pointer to new line,
 * or zero if error.
 *
 * len = number of characters.
 *
 *****************************************/

struct Zline *newZline(len)
UWORD							len;
{
	register struct Zline *z;
	register struct Memoryblock *blk;
	register struct Memorysection *st;
	register UWORD l;

	if (actualEditor->block.head->succ)
		/* blocks already exist: */
		if (z = getZline(len))
			return (z);
		else
			/*  Garbage-Collection:line not directly usable; */
			if (blk = garbageCollection(l = EVENLEN(len)))
				if (st = searchMemorysection(blk,l))
					return (ConvertSpstToZline(blk,st,len));
				else
					/* may not actually be encountered !!! */
					return (NULL);
			else
				/* no reults for Garbage-Collection ->pick new block */
				if (blk = newerBlock(BLOCKSIZE))
				{
					AddTail(&(actualEditor->block),blk);
					return (getZline(len));
				}
				else
					return (NULL);
	else
		/* no block in the block list: */
		if (blk = newerBlock(BIGBLOCK))
		{
			AddTail(&(actualEditor->block),blk);
			return (getZline(len));
		}
		else
			return (NULL);
}
/*#ENDFD*/
/*#FOLD: deleteZline */
/*********************************************
 *
 * deleteZline(line)
 *
 * Delete line from the list of lines.
 * The occupied memory word in the memory
 * section is changed and the corresponding
 * memory block optimized.
 *
 * line ^ line.
 *
 *********************************************/

void deleteZline		 (line)
register struct Zline *line;
{
	register struct Memoryblock *blk,*fblk = NULL;
	register struct Memorysection *st;
	register struct Zline **zptr;
	register UWORD n;

	/* remove line from list: */
	Remove(line);

	/* determine in which block the line lies: */
	for (blk = actualEditor->block.head; blk->succ; blk = blk->succ)
		if ((line > blk) && (line < (((UBYTE *)(blk + 1)) + blk->length)))
		{
			fblk = blk;
			break;
		}

	if (fblk)
	{
		/* convert line into memory peices, insert in list: */
		fblk->free += ( ((struct Memorysection *)line)->len
								= EVENLEN(line->len) );
		AddTail(&(fblk->freeliste),line);

		optimalBlock(fblk);
		if (fblk->length == (fblk->free + sizeof(struct Memorysection)))
			/* Block containsno more lines: Delete! */
			freeMemoryblock(fblk);
	}
}
/*#ENDFD*/