style/Collector.h

   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 "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 */