| Delphi Clinic | C++Builder Gate | Training & Consultancy | Delphi Notes Weblog | Dr.Bob's Webshop |
 |
 |
 |
| Delphi Clinic | C++Builder Gate | Training & Consultancy | Delphi Notes Weblog | Dr.Bob's Webshop |
|
|
|
|
Stand up and be counted
I sometimes point you to 'Advanced C++ Programming Styles and Idioms' written by James Coplien. One
of the idioms is called reference counting. The goal of that idiom is to be able to make references to another
object that will only be destroyed if the last reference to it is destroyed.
I attended the C++ World Conference 1999 in Miami, Florida in the beginning of December 1999, and Andrew
Koenig presented a double feature about recent ideas in generic programming. Use-counting and how to do
that was one of the topics in his presentation, and I have to pay tribute to him for making it possible to write
this issue of lost+found. Enjoy!
Classic approach
The classic approach to reference counting is to embed a pointer to the object referenced in the referencing
object itself. In the referenced object, we embed a use count. Furthermore, we use a friend relationship
between the reference and the referencee to be able to get at the internals of the referencee:
class Object
{
public:
friend Reference;
Object();
~Object();
private:
unsigned long count; // number of references to me
int member;
int another;
};
class Reference
{
public:
Reference()
{
(object = new Object())->count = 1;
}
Reference(const Reference& that)
{
(object = that.object)->count++;
}
Reference& operator=(const Reference& that)
{
if (--object->count <= 0 && object != that.object)
{
delete object;
}
(object = that.object)->count++;
return *this;
}
~Reference()
{
if (--object->count <= 0) delete object;
}
int GetMember()
{
return object->member;
}
private:
Object* object;
}
Non-intrusive approach
Ok. Nice, you would say. But what if I need to have a use count in a case where I cannot modify the object
that is referenced? Then you can use a different approach called non-intrusive usecounting. The technique
is based on letting an object exists in parallel with the object that is referenced from others:
class Use
{
public:
Use(): count(new int(1)) {}
Use(const Use& that): count(that.count) {++*count};
Use& operator=(const Use& that)
{
++*that.count;
if (--*count <= 0) delete count;
count = that.count;
return *this;
}
~Use() {if --*count <= 0) delete count;}
operator int() const {return *count;}
private:
int* count;
}
class Reference
{
public:
Reference()
: use(),
object(new Object)
{}
Reference(const Reference& that)
: use(that.use),
object(that.object)
{}
Reference& operator=(const Reference& that)
{
if (this != &that)
{
if (use == 1) delete object;
use = that.use;
object = that.object;
}
return *this;
}
~Reference()
{
if (use == 1) delete object;
}
int GetMember()
{
return object->member;
}
private:
Use use;
Object* object;
}
Koenig's Disgust
Now, if you look at it, the Use class sort of emulates the use-counting mechanism in the classic approach.
However, Andrew Koenig was a bit disgusted about this approach. Why? One of the drawbacks of this
approach is that we must allocate memory twice instead of once. Once for the object and once for the use
counter. The other thing is that it does not protect from manipulating the pointer to the object directly,
possibly deleting the object pointed to. The other thing is that it is difficult to get the operations of the
reference, the object referred to and the use counter itself exception safe. Even the use counting class itself
is subject to exception safety problems.
Koenig's Delight
Among others, Andrew thought by himself if there were methods in which the use counting class could be
made exception safe. The jump came when realizing that we do not use use-counting to actually count the
number of references to an object, but only want to know if there is still another reference to a particular
object or not. His solution was to use a doubly linked list in the Use class to determine if and when the last
reference to an object is deleted:
class Use
{
public:
Use(): prev(this), next(this) {}
Use(const Use& that) {Insert(that);}
Use& operator=(const Use& that)
{
AssignAndTest(that);
return *this;
}
~Use() {Remove()}
void Insert(const Use& that) const
{
prev = &that;
next = that.next;
prev->next = next->prev = this;
}
void Remove()
{
next->prev = prev;
prev->next = next;
}
bool AssignAndTest(const Use& that)
{
bool result = Unique();
if (this != &that)
{
Remove();
Insert(that);
}
return result;
}
bool Unique()
{
return (prev == next);
}
private:
Use* prev;
Use* next;
};
Now we have a linked list of Use objects. Since objects of the Use class are embedded in the Reference
class, it seems like those to are linked together. Its implementation then becomes:
class Reference
{
public:
Reference()
: use(),
object(new Object)
{}
Reference(const Reference& that)
: use(that.use),
object(that.object)
{}
Reference& operator=(const Reference& that)
{
if (this != &that)
{
if (use.Unique() == true) delete object;
use = that.use;
object = that.object;
}
return *this;
}
~Reference()
{
if (use.Unique() == true) delete object;
}
int GetMember()
{
return object->member;
}
private:
Use use;
Object* object;
}
Conclusion
Yes, the use class is larger than the one that allocates an integer to keep track of outstanding references. It
might even be a little bit slower, but that depends on the speed of the allocator opposed to the speed of
execution in the new Use class. However, using the newer class makes it easier to create exception safe
reference object classes, since we eliminated the use of dynamic memory in the use counting class.
The most important lesson however is that the term 'use-counting' took on a life of its own. Everybody
understands it as a class that makes it possible to count the number of references. However, most of the
times we only need it to know if there are outstanding references or not. In that case, we are able to use
another design to achieve our object, and that was one of the lessons learnt in Andrew Koenig's
presentation at the conference.