/*
* garbageCollector.h
*
* description:This file implements a garbage collector of C++.
* Created on: 2009-3-30
* Author: Song Caixing
*/
#ifndef GARBAGECOLLECTOR_H_
#define GARBAGECOLLECTOR_H_
#include <list>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <typeinfo>
using std::list;
using std::cout;
using std::endl;
using std::setw;
using std::setfill;
//#define DISPLAY
//exception class
class OutOfRangeExc{
std::string eMsg;
public:
OutOfRangeExc(const char* msg = "Error : idex out of range!"):eMsg(msg){}
const std::string what()const{
return eMsg;
}
};
//a iterator-like class to support GCPtr
template <class T>class Iter{
T *ptr; //point to current memory
T *start; //point to start memory
T *end; //point to end memory
int length;
public:
Iter() : ptr(NULL),start(NULL),end(NULL),length(0){}
Iter(T *ptr, T *first, T *last)
: ptr(ptr),start(first),end(last){
length = end - start;
}
int size()const {
return length;
}
//define pointer-like operators as follows
T &operator * ()const{
if ( (ptr >= end) || (ptr < start) ){
throw OutOfRangeExc();
}
return *ptr;
}
T *operator -> ()const{
if ( (ptr >= end) || (ptr < start) ){
throw OutOfRangeExc();
}
return ptr;
}
T &operator [] (int i){
if (i >= size() || i < 0){
throw OutOfRangeExc();
}
return ptr[i];
}
Iter<T> operator ++ (){
ptr++;
return *this;
}
Iter<T> operator -- (){
ptr--;
return *this;
}
//postfix ++
Iter<T> operator ++ (int){
T *tmp = ptr;
ptr++;
return Iter<T>(tmp,start,end);
}
//postfix --
Iter<T> operator -- (int){
T *tmp = ptr;
ptr--;
return Iter<T>(tmp,start,end);
}
Iter<T> operator - (int offset){
ptr -= offset;
return *this;
}
Iter<T> operator + (int offset){
ptr += offset;
return *this;
}
int operator - (Iter<T> it){
return ptr - it.ptr;
}
bool operator > (Iter<T> it){
return ptr > it.ptr;
}
bool operator <= (Iter<T> it){
return !(*this > it);
}
bool operator < (Iter<T> it){
return ptr < it.ptr;
}
bool operator >= (Iter<T> it){
return !(*this < it);
}
bool operator == (Iter<T> it){
return ptr == it.ptr;
}
bool operator != (Iter<T> it){
return !(*this == it);
}
};
//GCInfo class defines element that stored in the garbage collector
//collector information list
//Actually,it would be much better to implement this class inside
//GCPtr,but that remains some compile problems with GCC compiler
template <class P>class GCInfo
{
public:
//declare all data member public for convenience
//factually this is not a good design
int refCount; //reference counting
P *memPtr; //point to memory allocated
bool isArray;//true if pointing to an array
int arraySize;//if array,specifies array size
GCInfo(P *mPtr,int size = 0) : memPtr(mPtr),arraySize(size)
{
refCount = 1;
isArray = size > 0 ? true : false;
}
friend bool operator == (const GCInfo<P> &g1, const GCInfo<P> &g2){
return g1.memPtr == g2.memPtr;
}
};
//essential class GCPtr -- core of garbage collector
template <class T, int size = 0>class GCPtr{
//list in which allocated memories are stored
static list<GCInfo<T> > gclist;
//points to the allocated memory to which this GCPtr
//pointer currently points
T *curAddr;
bool isArray;
int arraySize;
//true if this GCPtr object is the first GCPtr object
static bool first;
//private member function
typename list<GCInfo<T> >::iterator findPtrInfo(T*);
public:
typedef Iter<T> GCIter;
//constructor
GCPtr(T *p = NULL) : curAddr(p),arraySize(size){
isArray = (size > 0) ? true : false;
#ifdef DISPLAY
cout << "[--DISPLAY--] Constructing GCPtr.";
if (isArray){
cout << " Size is " << arraySize << endl;
}
else cout << endl;
#endif
if (first){
atexit(shutDown); //register shutdown as exit function
first = false;
}
typename list<GCInfo<T> >::iterator itr = findPtrInfo(p);
if (itr != gclist.end()){
itr->refCount++;
}
else{//else create a new GCInfo object
GCInfo<T> obj(p,size);
gclist.push_front(obj);
}
}
//copy-constructor
GCPtr<T,size> (const GCPtr<T,size> &gc){
typename list<GCInfo<T> >::iterator p = findPtrInfo(gc.curAddr);
p->refCount++;
curAddr = gc.curAddr;
arraySize = gc.arraySize;
isArray = arraySize > 0 ? true : false;
#ifdef DISPLAY
cout << "[--DISPLAY--] Constructing copy.";
if (isArray){
cout << "Size is " << arraySize << endl;
}
else cout << endl;
#endif
}
T &operator * ()const{
return *curAddr;
}
T *operator -> ()const{
return curAddr;
}
T &operator [] (int i)const{
if (i > size){
throw OutOfRangeExc();
}
return curAddr[i];
}
Iter<T> begin()const{
int sz = isArray ? arraySize : 1;
return Iter<T>(curAddr,curAddr,curAddr+sz);
}
Iter<T> end()const{
int sz = isArray ? arraySize : 1;
return Iter<T>(curAddr+sz,curAddr,curAddr+sz);
}
operator T* ()const{
return curAddr;
}
static int gclistSize(){
return gclist.size();
}
GCPtr<T,size> &operator = (GCPtr<T,size>&);
T *operator = (T*);
static bool collect(); //garbage collect function
static void shutDown();
static void showList();
~GCPtr();
};
//assign values for static data members
template <class T, int size >
list<GCInfo<T> > GCPtr<T,size>::gclist;
template <class T, int size>
bool GCPtr<T,size>::first = true;
//member functions of GCPtr
template <class T, int size>
GCPtr<T,size>& GCPtr<T,size>:: operator = (GCPtr<T,size> &r){
typename list<GCInfo<T> >::iterator p;
p = findPtrInfo(r.curAddr);
p->refCount++;
this->curAddr = r.curAddr;
this->arraySize = r.arraySize;
this->isArray = r.isArray;
p = findPtrInfo(this->curAddr);
p->refCount--;
return *this;
}
template <class T, int size>
T* GCPtr<T,size>::operator = (T *t){
typename list<GCInfo<T> >::iterator p;
p = findPtrInfo(t);
if ( p != gclist.end() ){
p->refCount++;
}
else{
GCInfo<T> obj(t,size);
gclist.push_front(obj);
}
p = findPtrInfo(curAddr);
p->refCount--;
curAddr = t;
return *this;
}
template <class T, int size>
bool GCPtr<T,size>::collect(){
bool freed = false;//mark whether at least one
//memory is freed
#ifdef DISPLAY
cout << "[--DISPLAY--] Before garbage collection for ";
showList();
#endif
typename list<GCInfo<T> >::iterator p;
do{
for ( p = gclist.begin(); p != gclist.end(); p++ ){
if ( p->refCount > 0 ){
continue;
}
freed = true;
//gclist.remove(*p);
if (p->memPtr){
if (p->isArray){
#ifdef DISPLAY
cout << "[--DISPLAY--] Deleting array of size "
<< p->arraySize << endl;
#endif
delete []p->memPtr;
}
else{
#ifdef DISPLAY
cout << "[--DISPLAY--] Deleting:"
<< static_cast<void*>(p->memPtr)
<< "(value=" << *p->memPtr
<< ")" << endl;
#endif
delete p->memPtr;
}
}
gclist.remove(*p);
break; //research gclist
}
}while ( p != gclist.end() );
#ifdef DISPLAY
cout << "[--DISPLAY--] After garbage collection for ";
showList();
#endif
return freed;
}
template <class T, int size>
void GCPtr<T,size>::showList(){
typename list<GCInfo<T> >::iterator p;
cout << " gclist<" <<typeid(T).name() << ","
<< size << ">:" << endl
<< "[--DISPLAY--] Memory Refer-counting value"
<< endl;
if ( gclist.begin() == gclist.end() ){
cout << "[--DISPLAY--] --- Empty --- \n"
<< endl << endl;
return;
}
for ( p = gclist.begin(); p != gclist.end(); p++){
cout << "[--DISPLAY--] [" << setfill('0') << set
