diff options
Diffstat (limited to 'private/crt32/heap/heapsrch.c')
| -rw-r--r-- | private/crt32/heap/heapsrch.c | 150 |
1 files changed, 150 insertions, 0 deletions
diff --git a/private/crt32/heap/heapsrch.c b/private/crt32/heap/heapsrch.c new file mode 100644 index 000000000..2b07277cd --- /dev/null +++ b/private/crt32/heap/heapsrch.c @@ -0,0 +1,150 @@ +/*** +*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); +} |