views:

109

answers:

2

I would like to implement a simple reference counting using smart pointers. The variable pointer represents pointer to stored object, reference_count represents total count of copies of the object.

  • if we initialize an object using NULL: reference_count = -1 else reference_count = 1
  • copy ctor and operator = increment reference_count
  • destructor decrement reference_count and if there is no other reference to pointed object performs its deletion.

Here is my code:

#ifndef smart_pointer_H
#define smart_pointer_H

template < typename T > class smart_pointer
{
    private:
        T*    pointer;      
        int reference_count;    

    public:

        smart_pointer() : pointer(0), reference_count(-1) {}

        smart_pointer(T* p) : pointer(p)
        {
            if (p != NULL)
            {
                this->reference_count = 1;
            }

            else
            {
                this->reference_count = -1;
            }
        }

        smart_pointer(const smart_pointer <T> & p) : pointer(p.pointer),     reference_count(p.reference_count + 1) {}
        bool operator == (const smart_pointer <T>& p) { return pointer == p.pointer; }
        bool operator != (const smart_pointer <T>& p) { return pointer != p.pointer; }


        ~ smart_pointer()
        {
            if(-- reference_count == 0)
        {
                std::cout << "Destructing: " << '\n';
                delete pointer;
            }
        }

        T& operator *  () { return *pointer; }
        T* operator -> () { return pointer; }

        smart_pointer <T> & operator = (const smart_pointer <T> & p)
        {
                if (this != &p)
                {
                    if( -- reference_count == 0)
                    {
                        delete pointer;
                    }

                        pointer = p.pointer;
                        reference_count = p.reference_count + 1;
                }

        return *this;
        }
};    

Here is my testing code, class sample stores 2D point and two pointers to any other 2D points.

template < typename T >
class smart_pointer;

class Point
{
private:
    double x, y;
    smart_pointer <Point> p1;
    smart_pointer <Point> p2;

public:
    Point(double xx, double yy): x(xx), y(yy) {this-> p1 = NULL; this->p2 = NULL;}
    Point(double xx, double yy, smart_pointer <Point> p1, smart_pointer <Point> p2): x(xx), y(yy) {this-> p1 = p1, this->p2 = p2; }
    double getX(){ return x;}
    double getY(){ return y;}
    void setX(double xx)  {this->x = xx;}
    void setY(double yy)  {this->y = yy;}
    void setP1(smart_pointer <Point> p1) {this->p1 = p1;}
    void setP2(smart_pointer <Point> p2) {this->p2 = p2;}

    void print()
    {
         std::cout << "x= " << x << " y= " << y << '\n';
         std::cout << "p1" << '\n';
         if (p1 != NULL)
         {
             p1->print();
         }
         std::cout << "p2" << '\n';
         if (p2 != NULL)
         {
            p2->print();
         }
         std::cout << '\n';
    }

};

List of 2D points:

#include "Point.h"

class PointsList
{
private:
    std::vector <smart_pointer <Point> > points;

public:
    smart_pointer <Point> & operator [] ( int index ) {return points[index];}

public:
    void push_back(smart_pointer <Point> p) {points.push_back(p);}
    void erase(unsigned int index) {points.erase(points.begin() += index );}
    void printPoints()
    {
        std::cout << "List of points" << '\n';
        for (unsigned int i = 0; i < points.size();  i++)
        {
            points[i]->print();

        }

    }
};

Test code:

#include "Point.h"
#include "PointsList.h"

int main()
{
    smart_pointer <Point> pb = NULL;
    pb = (new Point(0,0));
    smart_pointer <Point> p0(new Point(0,0));
    p0->print();
    smart_pointer <Point> p1(new Point(10,10));
    p1->print();
    smart_pointer <Point> p2(new Point(20,20));
    p2->print();
    smart_pointer <Point> p3(new Point(30,30));
    p3->print();

    smart_pointer <Point> pa(p3);
    p0->setP1(p2);
    p0->setP2(p3);
    p0->print();    
    p0 = p1;
    p0->print();
    p0->print();

    PointsList pl1;
    pl1.push_back(p0);
    pl1.push_back(p1);

    PointsList pl2;
    pl2.push_back(p2);
    pl2.push_back(p3);
    pl1.erase(0);
    pl1.printPoints();
    pl2.printPoints();
    return 0;
}

Where are advanteges or disadvanteges of such solution? What about running speed for huge amount of data, casting, possible problems with inheritance, etc. Thanx for your help.

I had one more question to this example: Which type of the smart pointer (shared, scoped) would be for such a data structures the most suitable:

//Class with cross-references to points p1, p2
class PointTopo
{
private:
    double x, y;
    PointTopo * p1;
    Point * p2;

public:
    PointTopo(double xx, double yy): x(xx), y(yy) {this-> p1 = NULL; this->p2 = NULL;}
    ...

};

//Class  with cross references: topological model for Delaunay triangulation
class Edge
{
   private:
      Point2D * start;
      Edge *next;
      Edge *previous;
      Edge *twin;
...
};

Thanks for your help...

+6  A: 

Your reference counting does not work.

If you copy or assign two smart pointers together they need to use the same location to perform the counting.

Currently each object keeps its own count and thus they may become out of sync.

smart_pointer<int>  x(new x);      // x.pointer: <good> x.reference_count: 1
{
    smart_pointer<int>  y;         // y.pointer: NULL   y.reference_count: -1

    y = x;  // x.pointer: <good> x.reference_count: 1
            // y.pointer: <good> y.reference_count: 2

    smart_pointer<int>  z;
    x = z;  // x.pointer: NULL                        x.reference_count:  0 (BAD)
            // z.pointer: NULL                        z.reference_count: -1
            // y.pointer: <bad> (it was deleted by x) y.reference_count:  2
}

Edit:

Illustrate problem as requested in comments.

At the point. Where we have just created z. But not yet done x = z;

x { pointer: 0xabcd1234  reference_count: 1  }
y { pointer: 0xabcd1234  reference_count: 2  }
z { pointer: NULL        reference_count: -1 }


    // So here is your assignment operator.
    // Doing the `x = z` we will walk through the following code.
    //
    smart_pointer <T> & operator = (const smart_pointer <T> & p)
    {
            if (this != &p)
            {
                // We get here.
                // Left hand side is 'x' so this condition will be true.
                if( -- reference_count == 0)
                {
                    // Now we are deleting a pointer.
                    // That is held by 'x'
                    delete pointer;

                    // But 'y' is holding a pointer with the same value.
                    // Now y is holding a pointer to a deleted variable.
                }

                // Here we copy 'z' into 'x'
                // Copy the pointer. That happens to be NULL.
                pointer = p.pointer;

                // Now we copy and increment the reference count.
                // So 'x' has a value of 0 while 'z' has a value of -1.
                // This also breaks you invariant on 'x' that NULL values should
                // have a reference count of -1 (as X is NULL and ref-count is 0)
                reference_count = p.reference_count + 1;
            }

    return *this;
    }

If anybody tries to use 'y' now we have undefined behavior as it contains a pointer to memory that has been de-allocated.

Edit Clasic (but overly simplistic smart pointer:

#include <vector>

template<typename T>
class SP
{
    T*        object;
    size_t*   count;

    public:
        SP(T* data)
        try
        // Use wierd try around initializer list to catch new throwing.
        // If it does we delete data to stop it from leaking.
           :object(data)
           ,count(new int(1))
        { /* This is the constructor */}
        catch(...)
        {delete data;}

        SP():                 object(NULL),       count(NULL)       {}
      //SP(T* data):          object(data),       count(new int(1)  {}  // Ligned up here so it look neat but implemented above to use weird try catch
        SP(SP<T> const& rhs): object(rhs.object), count(rhs.count)  {if (count) {++(*count);}}
        SP<T>& operator=(SP<T> rhs)  // Note implicit copy construction in rhs
        {
            // Using copy swap idium for assignment.
            // The copy is hidden because the parameter is pass by value.
            this->swap(rhs);
        }
        void swap(SP<T>& rhs) throw()
        {
            std::swap(object, rhs.object);
            std::swap(count,  rhs.count);
        }
        ~SP()
        {
            if ((count) && (--(*count) == 0))
            {
                 delete count;
                 delete object;
            }
        }
};
Martin York
Thank you for your comment. But I can not find the problem, maybe I do not understand the problem correctly.smart_pointer <int> z;x = NULL; //x.ref_count = 0, no deletion in destructor will pe performed => no memory leak.
Ian
Which is a good reason not to do this for real. Hold on.
Martin York
The same sort of holes can be pocked into your code with the new copy constructor.
Martin York
+1: The most basic tenets of reference counting is that each object has it's own reference count. You're keeping them in each pointer- so when any given pointer updates the refcount, the others don't get informed.
DeadMG
@MY:Thank you very much for your explanation and comments...
Ian
@ DeadMG: OK. Each smart pointer must have list of referenced objects and after changing its status updates all objects in the list...
Ian
@Ian: I think what DeadMG was saying is: Each dynamic object (not smart pointer) has its own reference count. Thus when you assign smart pointers you need to do two assignemnts internally. 1) dynamic object. 2) dynamic objects count. Now both smart pointers are using the same counter. So you just need to increment it.
Martin York
@Ian: See last edit for classic but simplistic (ie it does not work in all situations).
Martin York
A: 

I'm sure you did a great job, but why not use the smart pointer available in either boost or loki? Both are the product of many years refinement.

Brent Arias
@Mystagogue: Even ignoring both his code and Martin's comments, I would be highly skeptical that he did a great job. Doing a great job implementing smart pointers is really difficult.
Brian
I have met very few people that can even think about all the potential problems (I am not one of those gifted few). Even Scott Myers (of C++ fame) tried to implement a smart pointer in a publication and he is still getting bug reports a decade latter. (Or so he said in a talk he did for the local C++ users group). So if Scott Myers has trouble doing it correctly then I am definately not going to try.
Martin York
@Brian: I was trying to "be easy" on him. :)
Brent Arias
@Martin: When I said "ignoring Martin's comments", I meant ignoring you outright saying his code was wrong. I was taking it for granted that Ian's code was broken based solely on the fact that he was trying to implement smart points, rather than based on any knowledge about his code. I.e. I was saying, "this is so difficult that I'll just assume you made an error. I have no need to actually check your code to see if it works; surely it has fatal bugs somewhere."
Brian