/***
*heapsrch.c - search the heap for a free block
*
*	Copyright (c) 1989-1991, Microsoft Corporation. All rights reserved.
*
*Purpose:
*	Defines the _heap_search() function.
*
*Revision History:
*	06-30-89   GJF	Module created. Yea, it's ugly, but it seems to work.
*	07-21-89   GJF	Now assumes proverdesc points to the descriptor for
*			first free block in the heap, if any, or is plastdesc,
*			if there are no free blocks
*	11-08-89   GJF	Fixed copyright, added register attribute to vars
*	12-18-89   GJF	Removed some redundant code, updated the description,
*			changed include file name to heap.h, added explicit
*			_cdecl to function definition.
*	12-19-89   GJF	Got rid of code to maintain plastdesc
*	03-11-90   GJF	Replaced _cdecl with _CALLTYPE1, added #include
*			<cruntime.h> and removed #include <register.h>.
*	09-28-90   GJF	New-style function declarator.
*	03-05-91   GJF	Changed strategy for rover - old version available
*			by #define-ing _OLDROVER_.
*
*******************************************************************************/

#include <cruntime.h>
#include <heap.h>
#include <stddef.h>

#define LOOP_FOREVER	while(1)

/***
*_PBLKDESC _heap_search(unsigned size) - Find a free block of a least size
*	bytes.
*
*Purpose:
*	Finds a free block of at least size bytes. Searches the list of block
*	descriptors from *proverdesc to the end (marked by the sentinel). The
*	search is strictly first fit. Adjacent free blocks are coalesced as
*	they are encountered during the search.
*
*Entry:
*	unsigned size	- size of block requested
*
*Exit:
*	Success:  Pointer to descriptor for free memory block of at least size
*		bytes
*	Failure:  NULL
*
*Uses:
*
*Exceptions:
*
*******************************************************************************/

_PBLKDESC _CALLTYPE1 _heap_search (
	unsigned size
	)
{
	REG1 _PBLKDESC pdesc;
	REG2 _PBLKDESC pdesc2;
	_PBLKDESC pretdesc = NULL;

	/* search from proverdesc thru plastdesc, looking for free block of
	 * at least size bytes. coalesce adjacent free blocks during the
	 * search. the search is strictly first fit. that is, it terminates
	 * when the first block is found of adequate size.
	 */
	for ( pdesc = _heap_desc.proverdesc ; pdesc != &(_heap_desc.sentinel) ;
	pdesc = pdesc->pnextdesc )
		/* is pdesc free?
		 */
		if ( _IS_FREE(pdesc) )
			/* coalesce loop
			 */
			LOOP_FOREVER {
				/* if pdesc is big enough, return it
				 */
				if ( _BLKSIZE(pdesc) >= size ) {
					pretdesc = pdesc;
					goto searchdone;
				}

				/* see if the next block is free and, if so,
				 * coalesce it with pdesc
				 */
				pdesc2 = pdesc->pnextdesc;
				if ( _IS_FREE(pdesc2) ) {
					/* coalesce pdesc2 with pdesc
					 */
					pdesc->pnextdesc = pdesc2->pnextdesc;
					_PUTEMPTY(pdesc2);
				}
				else
					break;
			} /* end LOOP_FOREVER */

#ifndef _OLDROVER_

	for ( pdesc = _heap_desc.pfirstdesc ; pdesc != _heap_desc.proverdesc ;
	pdesc = pdesc->pnextdesc )
		/* is pdesc free?
		 */
		if ( _IS_FREE(pdesc) )
			/* coalesce loop
			 */
			LOOP_FOREVER {
				/* if pdesc is big enough, return it
				 */
				if ( _BLKSIZE(pdesc) >= size ) {
					pretdesc = pdesc;
					goto searchdone;
				}

				/* see if the next block is free and, if so,
				 * coalesce it with pdesc
				 */
				pdesc2 = pdesc->pnextdesc;
				if ( _IS_FREE(pdesc2) ) {
					/* coalesce pdesc2 with pdesc
					 */
					pdesc->pnextdesc = pdesc2->pnextdesc;
					_PUTEMPTY(pdesc2);

					/* special handling for the case where
					 * the rover has been coalesced (search
					 * ends)
					 */
					if ( _heap_desc.proverdesc == pdesc2 )
					{
						_heap_desc.proverdesc = pdesc;
						if ( _BLKSIZE(pdesc) >= size )
							pretdesc = pdesc;
						goto searchdone;
					}
				}
				else
					break;
			} /* end LOOP_FOREVER */

#endif	/* _OLDROVER_ */

searchdone:

	/* common exit for all code paths. win, lose or draw, this is the
	 * only code path back to the caller.
	 */
	return(pretdesc);
}