$include (..\lib\compStch.ext)

/*
 *============================================================================
 *  This program 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
 *
 *  Permission to use for any purpose, modify, copy, and make enhancements
 *  and derivative works of the software is granted if attribution is given to
 *  R.M. Gillmore, dba the ACME Software Deli, as the author
 *
 *  While the ACME Software Deli does not work for money, there is nonetheless
 *  a significant amount of work involved.  The ACME Software Deli maintains the
 *  rights to all code written, though it may be used and distributed as long as
 *  the following conditions are maintained.
 *
 *  1.  The copyright statement at the top of each code block is maintained in
 *      your distribution.
 *  2.  You do not identify yourself as the ACME Software Deli
 *  3.  Any changes made to the software are sent to the ACME Software Deli
 *============================================================================
 */


acmeMallocModule:
do;
$if not noID
declare IDString	(*) byte data
	( '@(#)mem.p86       $Author: rmgillmore $ $Date:: 2025-05-04 19:35:39#$:', 0 );
$endif
$set (acmeMallocSource)

$include (..\lib\comnDefs.ext)
$include (..\lib\mem.ext)
$include (..\lib\sysCalls.ext)
$include (..\lib\string.ext)
$include (..\lib\errCode.ext)
$include (..\lib\ptrMath.ext)
$if LOGGING
$include (..\lib\logger.ext)\
$endif

/*
 *	at the beginning of each block of allocated memory
 */

declare	allocBlock_t		literally	'structure
	(
		nextBlockAddress		pointer,
		blockSize				word,
		isFree					boolean
	)';

declare	NUMBER_MASTER_BLOCKS	literally	'6',
		MAX_BLOCK_SIZE			literally	'1$0000h',
		PARAGRAPH_SIZE			literally	'16';

/*
 *	each of these master blocks will point to a linked list of memory
 *	blocks when mayFragment is True. Otherwise, the master block will point
 *	to a full (unfragmented) block which was returned from DOS
 */

declare	masterBlock_t		literally	'structure
	(
		blockAddress			pointer,
		mayFragment				boolean
	)';

declare	masterBlocks	( NUMBER_MASTER_BLOCKS ) masterBlock_t;

declare	allocBlockSample		allocBlock_t,
		allocBlockSize			literally	'size( allocBlockSample )';

/*
 *	at startup, isInitialized will always be False.  Initialize everything,
 *	then set isInitialized to True so there is no question about the initial
 *	values everywhere
 */

declare	isInitialized		boolean,
		blockAllocated		boolean,

		mergeCount			word;

/*
 * ============================================================================
 *	Function:
 *		paragraphsInBlock()
 *
 *	Intended purpose:
 *		this function simply determines how many paragraphs (16-byte blocks)
 *		are needed to construct a block of the specified size
 *
 *	Returns:
 *		the number of 16-byte blocks
 * ============================================================================
 */

paragraphsInBlock:
procedure ( desiredSize ) dword;
	declare	desiredSize		dword;

	declare	numParas			dword,
			adjustment			dword;

	/*
	 *	calculate the number of 16-byte paragraphs in a block
	 *	of the desired size
	 */

	numParas = shr( desiredSize, 4 );
	adjustment = ( ( desiredSize and 0fh ) <> 0 ) and 1;

	return ( numParas + adjustment );
end paragraphsInBlock;


/*
 * ============================================================================
 *	Function:
 *		getMemoryBlock()
 *
 *	Intended purpose:
 *		get a 64K block of memory
 *
 *	Returns:
 *		the address of the memory block
 * ============================================================================
 */

getMemoryBlockFromOS:
procedure pointer;
	declare blockAddress		pointer;

	declare cpuRegisters,
			carryFlagClear		boolean;

	errno = 0;
	blockAddress = NULL;
	wordRegs.Ax = 4800h;
	wordRegs.Bx = paragraphsInBlock( MAX_BLOCK_SIZE );
	call int86( DOS_CALL, @wordRegs );
	carryFlagClear = carryClear( @wordRegs );

	if ( carryFlagClear ) then
	do;
		blockAddress = build$ptr( selector( wordRegs.Ax ), 0 );
	end;
	else
	do;
		errno = wordRegs.Ax;
		blockAddress = NULL;
	end;

$if LOGGING
	call addToLog( DEBUG, __FILE__, __LINE__,
		@( 'getMemoryBlockFromOS() returning blockAddress: %p', 0 ), blockAddress );
$endif

	return ( blockAddress );
end getMemoryBlockFromOS;

/*
 * ============================================================================
 *	Function:
 *		addBlockToList()
 *
 *	Intended purpose:
 *		we know we have a block allocated, put the allocation block at the
 *		address in the master block list
 *
 *	Returns:
 *		modified masterBlockList (indirectly)
 * ============================================================================
 */

addBlockToList:
procedure ( masterBlockIndex, memoryPtr );
	declare	masterBlockIndex	word,
			memoryPtr			pointer;

	/*
	 *	we know we have a block allocated, put the allocation
	 *	block at the address in the master block list
	 */

	declare	allocationBlockPtr	pointer,
			allocBlock	based	allocationBlockPtr	allocBlock_t;

$if LOGGING
	call addToLog( DEBUG, __FILE__, __LINE__,
		@( 'addBlockToList( %d, %p )', 0 ),
			masterBlockIndex, memoryPtr );
$endif

	masterBlocks( masterBlockIndex ).blockAddress = memoryPtr;
	allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;
	masterBlocks( masterBlockIndex ).mayFragment = True;
	allocBlock.nextBlockAddress = NULL;
	allocBlock.blockSize = MAX_BLOCK_SIZE - size( allocBlock );
	allocBlock.isFree = True;

end addBlockToList;

/*
 * ============================================================================
 *	Function:
 *		initialize()
 *
 *	Intended purpose:
 *		just designed to initialize everything, including the allocation of
 *		a single 64KB block for allocation
 *
 *	Returns:
 *		nothing
 * ============================================================================
 */

initialize:
procedure;
	declare	memoryPtr			pointer;

	call memset( @masterBlocks, 0, size( masterBlocks ) );

	memoryPtr = getMemoryBlockFromOS;
	if ( NULL <> memoryPtr ) then
	do;
		call addBlockToList( 0, memoryPtr );
		blockAllocated = True;
	end;

	isInitialized = True;
end initialize;

/*
 * ============================================================================
 *	Function:
 *		validMasterBlock()
 *
 *	Intended purpose:
 *		this rather simple function ensures that a valid block of allocated
 *		memory exists and is associated with the master block at the specified
 *		block index
 *
 *	Returns:
 *		determination of block validity
 * ============================================================================
 */

validMasterBlock:
procedure ( blockIndex ) boolean;
	declare	blockIndex			word,
			memoryPtr			pointer,

			isValid				boolean;

	isValid = True;
	if ( blockIndex < NUMBER_MASTER_BLOCKS ) then
	do;
		if ( NULL = masterBlocks( blockIndex ).blockAddress ) then
		do;
			memoryPtr = getMemoryBlockFromOS;
			if ( NULL <> memoryPtr ) then
				call addBlockToList( blockIndex, memoryPtr );
			else
				isValid = False;
		end;
	end;
	else
		isValid = False;

	return ( isValid );
end validMasterBlock;

/*
 * ============================================================================
 *	Function:
 *		carveOffChunk()
 *
 *	Intended purpose:
 *		split the block sent into two pieces, inserting the remaining block
 *		into the linked list
 *
 *	Returns:
 *		the address of the chunk that will eventually end up in the caller's
 *		hands to do with as he pleases
 * ============================================================================
 */

carveOffChunk:
procedure ( allocationBlockPtr, blockSize ) pointer;
	declare	allocationBlockPtr	pointer,
			allocBlock	based	allocationBlockPtr	allocBlock_t,
			blockSize			word,

			returnAddress		pointer,

			newAllocBlockPtr	pointer,
			newAllocBlock	based	newAllocBlockPtr	allocBlock_t;

	/*
	 *	create a new allocation block in the proper place
	 *	link it into the list
	 *	adjust the block size for the current block
	 *	set the return address to the first byte of the user space
	 */

	newAllocBlockPtr = incPtr( allocationBlockPtr,
		( allocBlockSize + blockSize ), 1 );

	/*
	 *	insert into the linked list
	 */

	newAllocBlock.nextBlockAddress = allocBlock.nextBlockAddress;
	allocBlock.nextBlockAddress = newAllocBlockPtr;

	/*
	 *	adjust the freedom indicators
	 */

	newAllocBlock.isFree = True;
	allocBlock.isFree = False;

	newAllocBlock.blockSize =
		allocBlock.blockSize - ( allocBlockSize + blockSize );
	allocBlock.blockSize = blockSize;

	returnAddress = incPtr( allocationBlockPtr, allocBlockSize, 1 );

	return ( returnAddress );
end carveOffChunk;

/*
 * ============================================================================
 *	Function:
 *		retrieveBlock()
 *
 *	Intended purpose:
 *		this is the heart of the allocation process.  what we do is walk the
 *		linked lists in the master block array to find a chunk of memory as
 *		large as the user has requested
 *
 *	Returns:
 *		the address of the block being loaned to the caller
 * ============================================================================
 */

retrieveBlock:
procedure ( blockSize ) pointer;
	declare	blockSize			word,

			blockAddress		pointer,
			masterBlockIndex	word,
			done				boolean;

	declare	allocationBlockPtr	pointer,
			allocBlock	based	allocationBlockPtr	allocBlock_t,

			chunkFound			boolean;

	/*
	 *	using the information from the caller, get a chunk of memory for them
	 *	from the pool of masterBlocks
	 */

	blockAddress = NULL;

	/*
	 *	first, find a master block that has available memory
	 */

	masterBlockIndex = 0;
	done = False;
	do while ( ( not done ) and ( masterBlockIndex < NUMBER_MASTER_BLOCKS ) );
		/*
		 *	if the allocBlock may be fragmented, then we have a candidate,
		 *	otherwise, we need to move to the next master block
		 */

		if ( masterBlocks( masterBlockIndex ).mayFragment ) then
		do;
			allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;

			/*
			 *	the easy part is done.  now walk the chain looking for a block
			 *	that is large enough
			 */

			chunkFound = False;
			do while ( ( not chunkFound ) and ( not done ) );

				if ( allocBlock.isFree ) then
				do;
					/*
					 *	we have a candidate, let's see if the free block is
					 *	large enough
					 */

					if ( allocBlock.blockSize < blockSize ) then
					do;
						/*
						 *	obviously not large enough, jump to the
						 *	next candidate
						 */

						allocationBlockPtr = allocBlock.nextBlockAddress;
						if ( NULL = allocationBlockPtr ) then
						do;
							masterBlockIndex = masterBlockIndex + 1;
							if ( validMasterBlock( masterBlockIndex ) ) then
								allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;
							else
							do;
								done = True;
								blockAddress = NULL;
								errno = INSUFFICIENT_MEMORY;
							end;
						end;
					end;	/* candidate block not large enough */
					else if ( allocBlock.blockSize <
								( blockSize + ( allocBlockSize * 2 ) +
									PARAGRAPH_SIZE ) ) then
					do;
						/*
						 *	current block is large enough, so let's use it
						 */

						chunkFound = True;
						allocBlock.isFree = False;
						blockAddress =
							incPtr( allocationBlockPtr, size( allocBlock ), 1 );
						done = True;
					end;
					else
					do;
						/*
						 *	the block is plenty large enough, carve off a chunk
						 *	and lend it to the caller
						 */

						blockAddress = carveOffChunk( allocationBlockPtr, blockSize );
						chunkFound = True;
						done = True;
					end;
				end;	/* block not free */
				else
				do;
					/*
					 *	walk to the next available block
					 */

					if ( NULL <> allocBlock.nextBlockAddress ) then
					do;
						allocationBlockPtr = allocBlock.nextBlockAddress;
					end;
					else
					do;
						masterBlockIndex = masterBlockIndex + 1;
						if ( validMasterBlock( masterBlockIndex ) ) then
							allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;
						else
						do;
							done = True;
							blockAddress = NULL;
							errno = INSUFFICIENT_MEMORY;
						end;
					end;
				end;	/* goto next available block */
			end;	/* while not chunkFound */
		end;
		else
		do;
			/*
			 *	we need to move to the next master block
			 */

			masterBlockIndex = masterBlockIndex + 1;
			if ( validMasterBlock( masterBlockIndex ) ) then
				allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;
			else
			do;
				done = True;
				blockAddress = NULL;
				errno = INSUFFICIENT_MEMORY;
			end;
		end;
	end;	/* not done */

	return ( blockAddress );
end retrieveBlock;

/*
 * ============================================================================
 *	Function:
 *		malloc()
 *
 *	Intended purpose:
 *		This is the ACME Software Deli version of malloc(), implemented for
 *		DOS.  The parameter specifies the minimum number of bytes in a block
 *
 *	Returns:
 *		pointer to the requested block or NULL if no memory available or error
 *
 *		errno is modified
 * ============================================================================
 */

malloc:
procedure ( blockSize ) pointer public;
	declare	blockSize			word,
			blockAddress		pointer;

	if ( not isInitialized ) then
	do;
		call initialize;
	end;

	/*
	 *	using the information from the caller, get a chunk of memory for them
	 *	from the pool of masterBlocks
	 */

	blockAddress = NULL;
	blockAddress = retrieveBlock( blockSize );

	return ( blockAddress );
end malloc;

/*
 * ============================================================================
 *	Function:
 *		calloc()
 *
 *	Intended purpose:
 *		initialize the block received from malloc() with all zeroes
 *
 *	Returns:
 *		nothing
 * ============================================================================
 */

calloc:
procedure ( blockSize ) pointer public;
	declare	blockSize		dword;

	declare	returnPtr		pointer;

	/*
	 *	request a block of RAM from malloc().  if the block is allocated,
	 *	initialize it with zeroes
	 *
	 *	if a block is not returned, do nothing else
	 */

	returnPtr = malloc( blockSize );

	if ( NULL <> returnPtr ) then
	do;

		/*
		 *	because 64K bytes is the same as 32K words, we will use setw()
		 *	rather than setb().
		 *
		 *	BTW, this is a "little sloppy" since we are assuming less than
		 *	64K words being initialized
		 */

		call setw( 0, returnPtr, low( shr( blockSize, 1 ) ) );
	end;

	return ( returnPtr );
end calloc;

/*
 * ============================================================================
 *	Function:
 *		mergeBlocks()
 *
 *	Intended purpose:
 *		when a block has been returned by the user, we will merge it with the
 *		next block if both are available
 *
 *	Returns:
 *		status of the request to merge the blocks
 * ============================================================================
 */

mergeBlocks:
procedure	( blockHeaderPtr );
	declare	blockHeaderPtr	pointer,
			blockHeader		based	blockHeaderPtr	allocBlock_t,

			nextAllocBlockPtr	pointer,
			nextAllocBlock	based	nextAllocBlockPtr	allocBlock_t;

	/*
	 *	is there another block following this one?
	 */

	if ( NULL <> blockHeader.nextBlockAddress ) then
	do;
		/*
		 *	yes, so we will examine its characteristics
		 */

		nextAllocBlockPtr = blockHeader.nextBlockAddress;
		if ( True = nextAllocBlock.isFree ) then
		do;
			/*
			 *	we can now combine these blocks
			 */

			blockHeader.blockSize = blockHeader.blockSize +
				allocBlockSize + nextAllocBlock.blockSize;
			blockHeader.nextBlockAddress = nextAllocBlock.nextBlockAddress;
		end;
	end;

end mergeBlocks;

/*
 * ============================================================================
 *	Function:
 *		sweepingMerge()
 *
 *	Intended purpose:
 *		this function is intended to sweep each of the master blocks looking
 *		for blocks that can be merged together
 *
 *	Returns:
 *		nothing (directly) ; available adjoining blocks in each master block
 *		are combined, making larger blocks available
 * ============================================================================
 */

sweepingMerge:
procedure;
	declare	allocationBlockPtr	pointer,
			allocBlock	based	allocationBlockPtr	allocBlock_t,

			nextBlockPtr	pointer,
			nextBlock	based	nextBlockPtr		allocBlock_t,

			masterBlockIndex	word,
			done				boolean,
			combineComplete		boolean;

	/*
	 *	starting with the first master block, look for a free block, and merge
	 *	with the following block
	 */

	done = False;
	masterBlockIndex = 0;
	do while ( not done );
		if ( ( NULL <> masterBlocks( masterBlockIndex ).blockAddress ) and
				( masterBlocks( masterBlockIndex ).mayFragment ) ) then
		do;
			/*
			 *	walk this master block, combining the allocated blocks
			 */

			allocationBlockPtr = masterBlocks( masterBlockIndex ).blockAddress;
			combineComplete = False;
			do while ( not combineComplete );
				call mergeBlocks( allocationBlockPtr );
				if ( NULL = allocBlock.nextBlockAddress ) then
					combineComplete = True;
				else
				do;
					nextBlockPtr = allocBlock.nextBlockAddress;
					if ( False = nextBlock.isFree ) then
						allocationBlockPtr = allocBlock.nextBlockAddress;
				end;
			end;	/* while not combine complete */
		end;	/*	defined master block */

		/*
		 *	go on to the next master block (if there is one)
		 */

		masterBlockIndex = masterBlockIndex + 1;
		if ( masterBlockIndex >= NUMBER_MASTER_BLOCKS ) then
			done = True;

	end;	/*	while not done */
end sweepingMerge;

/*
 * ============================================================================
 *	Function:
 *		free()
 *
 *	Intended purpose:
 *		This is the ACME Software Deli version of free() ; complimenting
 *		the malloc() function implemented above
 *
 *	Returns:
 *		status of the request to free memory
 * ============================================================================
 */

free:
procedure ( blockAddress ) integer public;
	declare	blockAddress		pointer,
			returnCode			integer;

	declare	allocBlockHeader	pointer,
			allocBlock	based	allocBlockHeader	allocBlock_t;

	returnCode = EXIT_SUCCESS;

	/*
	 *	this is actually easier than one might expect ... simply mark the block
	 *	as available again.  Then, if the next block is already available, merge
	 *	them
	 */

	allocBlockHeader = decPtr( blockAddress, allocBlockSize, 1 );
	allocBlock.isFree = True;

	mergeCount = mergeCount + 1;
	if ( mergeCount >= 5 ) then
	do;
		call sweepingMerge;
		mergeCount = 0;
	end;

	return ( returnCode );
end free;

/*
 * ============================================================================
 *	Function:
 *		resizeBlock()
 *
 *	Intended purpose:
 *		This function will change the size of a memory block which was
 *		allocated using malloc()
 *
 *	Returns:
 *		status of the request to free memory
 * ============================================================================
 */

resizeBlock:
procedure ( blockPtr, newSize ) word public;
	declare	blockPtr				pointer,
			newSize					word;

	declare returnCode				boolean,
			cpuRegisters;

	returnCode = 0;

	/*
	 *	Function 4ah (decimal 74) is used to increase or decrease the size of a
	 *	block of memory that was allocated by function 48h.  Register ES
	 *	contains the segment address of the block that will be changed.
	 *	Register BX contains the desired size of the block in paragraphs (units
	 *	of 16 bytes).
	 *
	 *	The function clears the carry flag if the memory block can be resized as
	 *	requested. If an error occurs, the carry flag is set, and AX contains an
	 *	error code:
	 *		07h - memory control blocks destroyed
	 *		08h - insufficient memory
	 *		09h - invalid memory block address
	 *
	 *	If DOS reported there was insufficient memory to increase the size of a
	 *	memory block, register BX contains the maximum size, in paragraphs, of
	 *	the memory block
	 */

	wordRegs.Ax = 4a00h;
	wordRegs.Es = selector$of( blockPtr );
	wordRegs.Bx = paragraphsInBlock( newSize );

	call int86( DOS_CALL, @wordRegs );
	if ( carryClear( @wordRegs ) ) then
	do;
		returnCode,
			errno = wordRegs.Ax;
	end;

	return ( returnCode );
end resizeBlock;

end acmeMallocModule;