Debian Codegraph @

style/Collector.h

raw
1 // Copyright (c) 1996 James Clark
2 // See the file copying.txt for copying permission.
3
4 #ifndef Collector_INCLUDED
5 #define Collector_INCLUDED 1
6
7 #include <stddef.h>
8 #include <OpenSP/Boolean.h>
9
10 // A garbage collector.
11
12 class Collector {
13 public:
14 struct Block;
15
16 class Object {
17 friend struct Block;
18 friend class Collector;
19 public:
20 bool readOnly() const { return readOnly_; }
21 bool permanent() const { return color_ == permanentColor; }
22 protected:
23 Object() : readOnly_(0) { }
24 virtual ~Object() { }
25 // If we copy an object, don't copy inappropriate info.
26 Object(const Object &obj) { hasSubObjects_ = obj.hasSubObjects_; }
27 // For objects with subobjects, this must be overriden
28 // to call Collector::trace for each direct subobject.
29 virtual void traceSubObjects(Collector &) const { }
30 private:
31 enum Color {
32 someColor,
33 anotherColor,
34 permanentColor
35 };
36 Object *next() const { return next_; }
37 Object *prev() const { return prev_; }
38 void makeHead() { prev_ = next_ = this; }
39 Color color() const { return Color(color_); }
40 void setColor(Color color) { color_ = color; }
41 void moveAfter(Object *tail);
42 bool hasSubObjects() const { return hasSubObjects_; }
43 void finalize() { this->~Object(); }
44 private:
45 Object *prev_;
46 Object *next_;
47 char color_;
48 char hasFinalizer_;
49 protected:
50 char hasSubObjects_;
51 char readOnly_;
52 };
53
54 class DynamicRoot {
55 public:
56 DynamicRoot(Collector &);
57 virtual ~DynamicRoot();
58 virtual void trace(Collector &) const { }
59 DynamicRoot(const DynamicRoot &);
60 void operator=(const DynamicRoot &);
61 private:
62 DynamicRoot();
63 void link(const DynamicRoot *);
64 void unlink();
65
66 DynamicRoot *next_;
67 DynamicRoot *prev_;
68 friend class Collector;
69 };
70
71 class ObjectDynamicRoot : public DynamicRoot {
72 public:
73 ObjectDynamicRoot(Collector &, Object * = 0);
74 ObjectDynamicRoot &operator=(Object *obj);
75 void trace(Collector &) const;
76 operator Object *() const { return obj_; }
77 private:
78 Object *obj_;
79 };
80
81 struct Block {
82 Block(Block *, size_t, size_t, Object *);
83 ~Block();
84 Block *next;
85 Object *firstObj;
86 };
87
88 Collector(size_t maxSize);
89 virtual ~Collector();
90 void *allocateObject(bool hasFinalizer);
91 // This is called only when the constructor throws an exception.
92 void unallocateObject(void *);
93 void trace(const Object *obj);
94 // Permanent objects must not be altered in such a way that
95 // they contain pointers to non-permanent objects.
96 void makePermanent(Object *);
97 // Returns the number of live objects.
98 unsigned long collect();
99 void makeReadOnly(Object *);
100 bool objectMaybeLive(Object *);
101 protected:
102 virtual void traceStaticRoots() const { }
103 private:
104 Collector(const Collector &); // undefined
105 void operator=(const Collector &); // undefined
106 Object *freePtr_;
107 Object allObjectsList_; // doubly-linked circular list of all objects
108 Object permanentFinalizersList_;
109 Object *lastTraced_;
110 DynamicRoot dynRootList_; // doubly-linked circular list
111 Object::Color currentColor_;
112 Block *blocks_;
113 unsigned long totalObjects_;
114 size_t maxSize_;
115
116 void makeSpace();
117 void traceDynamicRoots();
118 void check();
119 void makeReadOnly1(Object *);
120 friend class DynamicRoot;
121 friend class Object;
122 };
123
124
125 inline
126 void Collector::Object::moveAfter(Object *tail)
127 {
128 // unlink from old position
129 next_->prev_ = prev_;
130 prev_->next_ = next_;
131 // link in following tail
132 next_ = tail->next_;
133 tail->next_->prev_ = this;
134 prev_ = tail;
135 tail->next_ = this;
136 }
137
138 inline
139 void *Collector::allocateObject(bool hasFinalizer)
140 {
141 if (freePtr_ == &allObjectsList_)
142 makeSpace();
143 Object *tem = freePtr_;
144 freePtr_ = freePtr_->next();
145 tem->setColor(currentColor_);
146 tem->hasFinalizer_ = hasFinalizer;
147 if (hasFinalizer)
148 tem->moveAfter(&allObjectsList_);
149 return tem;
150 }
151
152 inline
153 void Collector::trace(const Object *obj)
154 {
155 if (obj && obj->color() != currentColor_
156 && obj->color() != Object::permanentColor) {
157 ((Object *)obj)->setColor(currentColor_);
158 ((Object *)obj)->moveAfter(lastTraced_);
159 lastTraced_ = (Object *)obj;
160 }
161 }
162
163 inline
164 void Collector::DynamicRoot::link(const DynamicRoot *root)
165 {
166 DynamicRoot *list = (DynamicRoot *)root;
167 // link in just after list
168 prev_ = list;
169 next_ = list->next_;
170 list->next_->prev_ = this;
171 list->next_ = this;
172 }
173
174 inline
175 void Collector::DynamicRoot::unlink()
176 {
177 next_->prev_ = prev_;
178 prev_->next_ = next_;
179 }
180
181 inline
182 Collector::DynamicRoot::DynamicRoot(Collector &c)
183 {
184 link(&c.dynRootList_);
185 }
186
187 inline
188 Collector::DynamicRoot::DynamicRoot()
189 : next_(this), prev_(this)
190 {
191 }
192
193 inline
194 Collector::DynamicRoot::DynamicRoot(const DynamicRoot &root)
195 {
196 link(&root);
197 }
198
199 inline
200 void Collector::DynamicRoot::operator=(const DynamicRoot &root)
201 {
202 unlink();
203 link(&root);
204 }
205
206 inline
207 Collector::ObjectDynamicRoot::ObjectDynamicRoot(Collector &c, Object *obj)
208 : Collector::DynamicRoot(c), obj_(obj)
209 {
210 }
211
212 inline
213 Collector::ObjectDynamicRoot &
214 Collector::ObjectDynamicRoot::operator=(Object *obj)
215 {
216 obj_ = obj;
217 return *this;
218 }
219
220 inline
221 void Collector::ObjectDynamicRoot::trace(Collector &c) const
222 {
223 c.trace(obj_);
224 }
225
226 inline
227 Collector::Block::~Block()
228 {
229 ::operator delete(firstObj);
230 }
231
232 inline
233 bool Collector::objectMaybeLive(Object *obj)
234 {
235 return obj->color() == currentColor_ || obj->color() == Object::permanentColor;
236 }
237
238 inline
239 void Collector::makeReadOnly(Object *obj)
240 {
241 if (!obj->hasSubObjects())
242 obj->readOnly_ = 1;
243 else if (!obj->readOnly())
244 makeReadOnly1(obj);
245 }
246
247 #endif /* not Collector_INCLUDED */