1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
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);
}
|
