Delphi Clinic C++Builder Gate Training & Consultancy Delphi Notes Weblog Dr.Bob's Webshop
Dr.Bob's Kylix Kicks
 Borland C++Builder lost+found #11
See Also: C++Builder Papers and Columns

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.


This webpage © 2000-2017 by Bob Swart (aka Dr.Bob - www.drbob42.com). All Rights Reserved.