style/Collector.cxx

   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 "macros.h"
   7 #include <stdlib.h>
   8
   9 #if 0
  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 }