-
Notifications
You must be signed in to change notification settings - Fork 0
/
BestFit.cc
177 lines (153 loc) · 5.33 KB
/
BestFit.cc
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
//#ident "@(#)BestFit.cc 2.2 BUA MIRZA 20150525"
/** @file BestFit.cc
* De implementatie van BestFit.
*/
#include "BestFit.h"
#include "ansi.h"
// Clean up dead stuff
BestFit::~BestFit()
{
while (!areas.empty()) {
Area *ap = areas.back();
areas.pop_back();
delete ap;
}
}
// Initializes how much memory we own
void BestFit::setSize(int new_size)
{
require(areas.empty()); // prevent changing the size when the freelist is nonempty
Fitter::setSize(new_size);
areas.push_back(new Area(0, new_size)); // and create the first free area (i.e. "all")
}
// Print the current freelist for debugging
void BestFit::dump()
{
std::cerr << AC_BLUE << type << "::areas";
for (ALiterator i = areas.begin() ; i != areas.end() ; ++i) {
std::cerr << ' ' << **i;
}
std::cerr << AA_RESET << std::endl;
}
// Application wants 'wanted' memory
Area *BestFit::alloc(int wanted)
{
require(wanted > 0); // has to be "something",
require(wanted <= size); // but not more than can exist
updateStats(); // update resource map statistics
if(areas.empty()) { // if we have nothing
return 0; // give up immediately
}
// Search thru all available free areas
Area *ap = 0;
ap = searcher(wanted); // first attempt
if(ap) { // success ?
return ap;
}
if(reclaim()) { // could we reclaim fragmented freespace ?
ap = searcher(wanted); // then make a second attempt
if(ap) { // success ?
return ap;
}
}
// Alas, failed to allocate anything
//dump();//DEBUG
return 0; // inform caller we failed
}
// Application returns an area no longer needed
void BestFit::free(Area *ap)
{
require(ap != 0);
if (cflag) {
// EXPENSIVE: check for overlap with all registered free areas
for(ALiterator i = areas.begin() ; i != areas.end() ; ++i) {
check(!ap->overlaps(*i)); // the sanity check
}
}
areas.push_back(ap); // add discarded "old" object to the end of free list
}
// ----- internal utilities -----
/* //////////////////////////////////////////////////////////////////////////////////////////////////// */
// Search for an area with at least 'wanted' memory
Area *BestFit::searcher(int wanted)
{
require(wanted > 0); // has to be "something",
require(wanted <= size); // but not more than can exist,
require(!areas.empty()); // provided we do have something to give
Area *tmpArea = NULL;
ALiterator currentIndex;
// Search through all available areas
for(ALiterator i = areas.begin() ; i != areas.end() ; ++i)
{
Area *ap = *i; // Candidate item
if(ap->getSize() == wanted) // Perfect size
{
tmpArea = ap;
currentIndex = i;
break;
}
else if(ap->getSize() >= wanted) // Bigger than what we want
{
if(tmpArea == NULL) // No area set before
{
tmpArea = ap; // replace the smallest one by this current one
currentIndex = i;
}
else if(ap->getSize() < tmpArea->getSize()) // New area found smaller than what already set
{
tmpArea = ap; // replace the smallest one by this current one
currentIndex = i;
}
}
}
// Check if anything is found or not
if(tmpArea != NULL)
{
ALiterator next = areas.erase(currentIndex); // Remove this element from the free list
if(tmpArea->getSize() > wanted) // Area too large than wanted
{
Area *rp = tmpArea->split(wanted); // Split into two parts (updating sizes)
areas.insert(next, rp); // Insert remainder before "next" area
}
return tmpArea;
}
return 0; // report failure, no space found
}
/* //////////////////////////////////////////////////////////////////////////////////////////////////// */
// We have run out of useful areas;
// Try to reclaim space by joining fragmented free space
bool BestFit::reclaim()
{
require(!areas.empty()); // sanity check
// Sort resource map by area address
areas.sort(Area::orderByAddress()); // WARNING: expensive N*log(N) operation !
// Search thru all free areas for matches between successive elements
bool changed = false;
ALiterator i = areas.begin();
Area *ap = *i; // The current candidate ...
for(++i ; i != areas.end() ;) {
Area *bp = *i; // ... match it with.
if(bp->getBase() == (ap->getBase() + ap->getSize())) {
// Oke; bp matches ap ... [i.e. bp follows ap]
ALiterator next = areas.erase(i); // remove bp from the list
ap->join(bp); // append area bp to ap (and destroy bp)
++mergers; // update statistics
changed = true; // we changed something
i = next; // revive the 'i' iterator
// and now try match ap with whatever followed bp
} else {
ap = bp; // move on to next free area
++i;
}
}
++reclaims; // update statistics ("reclaims attempted")
return changed;
}
// Update statistics
void BestFit::updateStats()
{
++qcnt; // number of 'alloc's
qsum += areas.size(); // length of resource map
qsum2 += (areas.size() * areas.size()); // same: squared
}
// vim:sw=4:ai:aw:ts=4: