garbagecollection.cpp

内存受限系统软件开发一书的代码。（虽不及Gang of Four的模式掷地有声

#include <iostream>
#include <deque>
#include <algorithm>

#include <assert.h>
#define ASSERT( x ) assert( x );

using namespace std;

// Microsoft nonsense about truncated names:
#pragma warning( disable : 4786 )  


class CollectableObject {
friend int main();

private:
    bool markBit;

public:
    CollectableObject();  
    virtual ~CollectableObject();
    virtual void GetReferences() = 0;
    void HaveReference( CollectableObject* referencedObject);
private:
    void DoMark();

    // Garbage collector functionality:
  
    typedef deque<CollectableObject *> Collection;
    static Collection allCollectableObjects;
public:  
    static void GarbageCollect( CollectableObject* rootNode );
private:
    static void MarkPhase(CollectableObject* rootNode);
    static void SweepPhase();
};


// **************************************************************************
// Garbage Collector functions:
// **************************************************************************

CollectableObject::Collection CollectableObject::allCollectableObjects;
  
/*static*/
void CollectableObject::GarbageCollect( CollectableObject* rootNode ) {
    // Garbage collect, deleting any objects not reachable from rootNode
    // [We're not worrying about stack and static references here]
    MarkPhase(rootNode); 
    SweepPhase();
}

/*static*/ 
void CollectableObject::MarkPhase(CollectableObject* rootNode)        {
    if (rootNode)
	    rootNode->DoMark();  
}
  
/*static*/
void CollectableObject::SweepPhase() {
    for (Collection::iterator iter = allCollectableObjects.begin(); 
         iter != allCollectableObjects.end(); )  {
        CollectableObject* object = *iter;
        if (!object->markBit) {
            iter = allCollectableObjects.erase( iter );
            delete object;
        } else {
            object->markBit = false;
            ++iter;
        }
    }
}

// **************************************************************************
// CollectableObject Member functions
// **************************************************************************



CollectableObject::CollectableObject()  
    : markBit( false ) {
    (void)allCollectableObjects.push_back(this);
}
  
/*virtual*/
CollectableObject::~CollectableObject() 
    // Need virtual dtor, as GarbageCollect code will delete all objects as
    // CollectableObject* 
{} 

void CollectableObject::HaveReference( CollectableObject* referencedObject) { 
    // Only called from GetReferences().  May be called with the null
    // pointer.
    if ( referencedObject != NULL) 
        referencedObject->DoMark();
}
  
void CollectableObject::DoMark() { 
    // Mark function, called recursively.
    if (!markBit) {
        markBit = true;
        GetReferences();
    }       
}




// **************************************************************************
// Test code follows...
// **************************************************************************


// Node, as in the example illustration for cycles in the Reference
// Counting pattern
// Must be allocated on the heap; not stack or static.

class Node : public CollectableObject {
private:
    Node* left;
    Node* right;
public: 
    Node( Node* l = 0, Node* r = 0 ) : left( l ), right( r ) { NodeCount++; }
    ~Node() { NodeCount--; }
    void SetLinks( Node* l, Node* r ) { left = l; right = r; }

private:
    void GetReferences() {
        HaveReference( left );
        HaveReference( right );  
    }

public:
    static int NodeCount;
};

int Node::NodeCount = 0;

void Example() {
    Node* E = new Node( 0, 0 );
    Node* D = new Node( 0, 0 );
    Node* C = new Node( D, E );
    Node* B = new Node( 0, D );
    Node* A = new Node( B, C );
    E->SetLinks( 0, C ); // Create the cycle E to C


    ASSERT( Node::NodeCount == 5 );

    CollectableObject::GarbageCollect( A );

    ASSERT( Node::NodeCount == 5 );

    A->SetLinks( B, 0 ); 
    CollectableObject::GarbageCollect( A );
    ASSERT( Node::NodeCount == 3 );
    A->SetLinks( 0, 0 ); 
    CollectableObject::GarbageCollect( A );
    ASSERT( Node::NodeCount == 1 );
    CollectableObject::GarbageCollect( 0 );
    ASSERT( Node::NodeCount == 0 );
}

int main() {
    // Create the network of nodes:
	
	Example();
    ASSERT( CollectableObject::allCollectableObjects.size() == Node::NodeCount );

    Node* E = new Node( 0, 0 );
    Node* D = new Node( 0, 0 );
    Node* C = new Node( D, E );
    Node* B = new Node( 0, D );
    Node* A = new Node( B, C );
    E->SetLinks( 0, C ); // Create the cycle E to C

    ASSERT( Node::NodeCount == 5 );
    ASSERT( CollectableObject::allCollectableObjects.size() == Node::NodeCount );
 
    CollectableObject::GarbageCollect( A );

    ASSERT( Node::NodeCount == 5 );
    ASSERT( CollectableObject::allCollectableObjects.size() == Node::NodeCount );

    A->SetLinks( 0, C ); // Orphan node B
    CollectableObject::GarbageCollect( A );
    ASSERT( CollectableObject::allCollectableObjects.size() == Node::NodeCount );

    ASSERT( Node::NodeCount == 4 );

    A->SetLinks( 0, 0 ); // Orphan nodes C,D,E
    CollectableObject::GarbageCollect( A ); 
 
    ASSERT( Node::NodeCount == 1 );

    cout << "Successful\n";

    (void)cin.get(); // stop the world, I want to see the result!
    return 0;
}