Debian Codegraph @

style/Collector.cxx

raw
1 // Copyright (c) 1996 James Clark
2 // See the file copying.txt for copying permission.
3
4 #include "config.h"
5 #include "Collector.h"
6 #include <OpenSP/macros.h>
7 #include <stdlib.h>
8
9 #if 1
10 #define DEBUG
11 #endif
12
13 Collector::Collector(size_t maxSize)
14 : freePtr_(&allObjectsList_), currentColor_(Object::someColor),
15 blocks_(0), lastTraced_(0), totalObjects_(0), maxSize_(maxSize)
16 {
17 allObjectsList_.makeHead();
18 permanentFinalizersList_.makeHead();
19 }
20
21 Collector::~Collector()
22 {
23 if (freePtr_ != &allObjectsList_) {
24 for (Object *p = allObjectsList_.next(); p != freePtr_; p = p->next()) {
25 if (!p->hasFinalizer_)
26 break;
27 p->finalize();
28 }
29 }
30 {
31 for (Object *p = permanentFinalizersList_.next();
32 p != &permanentFinalizersList_;
33 p = p->next()) {
34 ASSERT(p->hasFinalizer_);
35 p->finalize();
36 }
37 }
38 while (blocks_) {
39 Block *tem = blocks_;
40 blocks_ = blocks_->next;
41 delete tem;
42 }
43 }
44
45 void Collector::makeSpace()
46 {
47 unsigned long nLive = collect();
48 // Ensure that at least one-quarter of the heap is free, but don't allocate fewer
49 // than 512 objects.
50 if (freePtr_ == &allObjectsList_ || totalObjects_ - nLive < (totalObjects_ >> 2)
51 || totalObjects_ < 128) {
52 size_t allocObjs;
53 if (totalObjects_ < 128)
54 allocObjs = 512;
55 else {
56 allocObjs = (totalObjects_ >> 2) - (totalObjects_ - nLive);
57 if (allocObjs < 512)
58 allocObjs = 512;
59 }
60 if (freePtr_ == &allObjectsList_) {
61 blocks_ = new Block(blocks_, allocObjs, maxSize_, freePtr_->prev());
62 freePtr_ = blocks_->firstObj;
63 }
64 else
65 blocks_ = new Block(blocks_, allocObjs, maxSize_, freePtr_);
66 totalObjects_ += allocObjs;
67 }
68 #ifdef DEBUG
69 check();
70 #endif
71 }
72
73 void Collector::check()
74 {
75 size_t n = 0;
76
77 bool allocated = 1;
78 bool allowFinalizer = 1;
79 for (Object *p = allObjectsList_.next();
80 p != &allObjectsList_;
81 p = p->next()) {
82 if (p == freePtr_)
83 allocated = 0;
84 else if (allocated) {
85 if (p->color() != currentColor_)
86 abort();
87 if (allowFinalizer) {
88 if (!p->hasFinalizer_)
89 allowFinalizer = 0;
90 }
91 else if (p->hasFinalizer_)
92 abort();
93 }
94 if (p->next()->prev() != p)
95 abort();
96 if (p->prev()->next() != p)
97 abort();
98 n++;
99 }
100 if (n != totalObjects_)
101 abort();
102
103 }
104
105 // Link block in after follow.
106
107 Collector::Block::Block(Block *p, size_t n, size_t sz, Object *follow)
108 : next(p)
109 {
110 Object *next = follow->next_;
111 Object *prev = follow;
112 Object *cur = (Object *)::operator new(n * sz);
113 firstObj = follow->next_ = cur;
114 for (size_t i = 0; i < n; i++) {
115 Object *tem = (i == n - 1 ? next : (Object *)((char *)cur + sz));
116 cur->next_ = tem;
117 cur->prev_ = prev;
118 prev = cur;
119 cur = tem;
120 }
121 next->prev_ = prev;
122 }
123
124 unsigned long Collector::collect()
125 {
126 Object *oldFreePtr = freePtr_;
127 unsigned long nLive = 0;
128 currentColor_ = (currentColor_ == Object::someColor
129 ? Object::anotherColor
130 : Object::someColor);
131 lastTraced_ = &allObjectsList_;
132 traceStaticRoots();
133 traceDynamicRoots();
134 if (lastTraced_ != &allObjectsList_) {
135 Object *scanPtr = allObjectsList_.next();
136 for (;;) {
137 if (scanPtr->hasSubObjects())
138 scanPtr->traceSubObjects(*this);
139 nLive++;
140 Object *next = scanPtr->next();
141 if (scanPtr->hasFinalizer_)
142 scanPtr->moveAfter(&allObjectsList_);
143 if (scanPtr == lastTraced_) {
144 freePtr_ = next;
145 break;
146 }
147 scanPtr = next;
148 }
149 }
150 else
151 freePtr_ = allObjectsList_.next();
152 lastTraced_ = 0;
153 for (Object *p = freePtr_; p != oldFreePtr; p = p->next()) {
154 if (!p->hasFinalizer_)
155 break;
156 p->finalize();
157 }
158 #ifdef DEBUG
159 check();
160 #endif
161 return nLive;
162 }
163
164 void Collector::makePermanent(Object *obj)
165 {
166 if (!obj->hasSubObjects()) {
167 // Handle the simple case quickly.
168 if (obj->color() != Object::permanentColor) {
169 totalObjects_--;
170 obj->setColor(Object::permanentColor);
171 obj->readOnly_ = 1;
172 if (obj->hasFinalizer_)
173 obj->moveAfter(&permanentFinalizersList_);
174 else {
175 obj->next_->prev_ = obj->prev_;
176 obj->prev_->next_ = obj->next_;
177 }
178 }
179 }
180 else {
181 Object::Color saveColor = currentColor_;
182 currentColor_ = Object::permanentColor;
183 lastTraced_ = &allObjectsList_;
184 trace(obj);
185 if (lastTraced_ != &allObjectsList_) {
186 Object *scanPtr = allObjectsList_.next();
187 for (;;) {
188 scanPtr->readOnly_ = 1;
189 if (scanPtr->hasSubObjects())
190 scanPtr->traceSubObjects(*this);
191 totalObjects_--;
192 Object *next = scanPtr->next();
193 if (scanPtr->hasFinalizer_)
194 scanPtr->moveAfter(&permanentFinalizersList_);
195 else {
196 // unlink from allObjectsList_
197 scanPtr->next_->prev_ = scanPtr->prev_;
198 scanPtr->prev_->next_ = scanPtr->next_;
199 }
200 if (scanPtr == lastTraced_)
201 break;
202 scanPtr = next;
203 }
204 }
205 lastTraced_ = 0;
206 currentColor_ = saveColor;
207 }
208 }
209
210 void Collector::makeReadOnly1(Object *obj)
211 {
212 Object::Color saveColor = currentColor_;
213 currentColor_ = (currentColor_ == Object::someColor
214 ? Object::anotherColor
215 : Object::someColor);
216 lastTraced_ = &allObjectsList_;
217 trace(obj);
218 if (lastTraced_ != &allObjectsList_) {
219 Object *scanPtr = allObjectsList_.next();
220 Object *firstNonFinal = 0;
221 Object *lim;
222 for (;;) {
223 if (scanPtr->hasSubObjects())
224 scanPtr->traceSubObjects(*this);
225 Object *next = scanPtr->next();
226 if (scanPtr->hasFinalizer_)
227 scanPtr->moveAfter(&allObjectsList_);
228 else if (!firstNonFinal)
229 firstNonFinal = scanPtr;
230 if (scanPtr == lastTraced_) {
231 lim = next;
232 break;
233 }
234 scanPtr = next;
235 }
236 // We have 1 or more objects to be made read-only in currentColor
237 // Followed by 0 or more objects with finalizers in saveColor
238 // Followed by 0 or more objects without finalizers in saveColor
239 for (scanPtr = allObjectsList_.next(); scanPtr != lim; scanPtr = scanPtr->next()) {
240 scanPtr->readOnly_ = 1;
241 scanPtr->setColor(saveColor);
242 }
243 if (firstNonFinal) {
244 for (;
245 scanPtr != freePtr_ && scanPtr->hasFinalizer_;
246 scanPtr = scanPtr->next())
247 ;
248 if (scanPtr != lim) {
249 Object *last = lim->prev();
250 // Move section of list from firstNonFinal up to lastTraced but not including
251 // lim to before scanPtr
252 firstNonFinal->prev()->next_ = last->next();
253 last->next()->prev_ = firstNonFinal->prev();
254 firstNonFinal->prev_ = scanPtr->prev();
255 last->next_ = scanPtr->prev()->next();
256 firstNonFinal->prev()->next_ = firstNonFinal;
257 last->next()->prev_ = last;
258 }
259 }
260 }
261 lastTraced_ = 0;
262 currentColor_ = saveColor;
263 #ifdef DEBUG
264 check();
265 #endif
266 }
267
268 void Collector::traceDynamicRoots()
269 {
270 for (DynamicRoot *p = dynRootList_.next_; p != &dynRootList_; p = p->next_)
271 p->trace(*this);
272 }
273
274 Collector::DynamicRoot::~DynamicRoot()
275 {
276 unlink();
277 }
278
279 void Collector::unallocateObject(void *obj)
280 {
281 ((Object *)obj)->moveAfter(freePtr_);
282 }