Resource management--circular linked list

[hoodmane]

I am working on code to create a type of circular linked list. I have a class CLNode for the actual nodes of the list and a second class CLPtr for pointers to the nodes. The node class is entirely private, and all access must be done through the pointers. The nodes contain a shared pointer to an integer which gives the number of "CLPtr"s that point to an element of the list. Whenever CLPtr's constructor and destructor keep this number up to date.

If after CLPtr's destructor notices that it is the last CLPtr pointing to the list, it "delete"s the node. The node's destructor then recursively destroys the list. If the previous link is nonnull, it sets its "next" link to null, then if the next link is not null, it sets the next link's previous link to null and "delete"s it. The code for the destructor follows:

template <class T>
CLNode<T,U>::~CLNode()
{
     cout<<"Deleting node: "<<*this<<endl;
     if(links[1-direction]!=0)
     {
         cout<<"root"<<endl;
         getPrevious().links[direction]=0;
     }
     if(links[direction]!=0)
     {
         getNext().links[1-direction]=0;
         cout<<"about to delete "<<getNext()<<endl;         
         delete links[direction];
         cout<<"returning to "<<*this<<endl;
     }
     cout<<"finished "<<*this<<endl;

}

If the list is 1,2,3,4 and the pointer points to 3 it prints:

Destroying CLPTR.  1 CLPTRs remain for this CL list.
Destroying CLPTR.  0 CLPTRs remain for this CL list.
about to delete 3
Deleting node: 3
root
about to delete 4
Deleting node: 4
about to delete 1
Deleting node: 1
about to delete 2
Deleting node: 2
finished 2
returning to 1
finished 1
returning to 4
finished 4
______________________
finished 3

At the line, a popup sometimes comes up that says "LinkedList.exe has stopped working". Any suggestions for why this happens? Is there a better way to do this?

I'm working on a minimal working example to post.

[Alex F]

Provided code is not enough to say what is wrong. Generally, it is wrong design desision to delete another nodes from the node destructor. Every class must release only its own resources. Other nodes should be released by high level class (list).
BTW, did you try to debug this?

[hoodmane]

The source of the error is definitely not apparent from the code that I posted. The problem that I'm having is that the source it isn't apparent at all. It's not even consistent---sometimes it causes a problem, sometimes it doesn't. From systematically removing different parts of the code, I have determined that the error comes from the end of the recursion in the destructor I posted.

And yes, I definitely tried to debug it.

That sounds like a good idea; I'll try it and see if it works better. Just do clarify, you are saying that the CLPtr destructor should directly "delete" each node?

Edit: I tried making a member function in CLPtr that recursively did exactly what the code I had for the CLNode destroyer did. It didn't work any better. I also tried writing an iterative version; same problem.

I'll post a minimal working copy of the code. At the moment, there's a lot of clutter/unrelated stuff that I have to remove.

[Alex F]

Just do clarify, you are saying that the CLPtr destructor should directly "delete" each node?

I don't know what is CLPtr. If this is kind of list class, which owns a node - yes, this is what I mean. Class should have knowledge about classes that it owns, but should not know anything about its owner and another instances of the same class (except of obvious next-previous pointers for the list node). Relation between different instances of the node class is list class responsibility.

[monarch_dodra]

Make your node a dumb data structure.

Move the logic from the node into the container.

The container owns the nodes, so 'it' is responsible for their management.

At best, the nodes can cleanup up their own owned data, if for example, your nodes had pointers to data.

[hoodmane]

@Alex F
Yeah, CLPtr is an iterator for the list. It has a pointer to a node and a dereference operator that returns the datum contained in the node. I believe you are saying that even though the a CLPtr object only ever has a pointer to a single node, it is still the owner of all the nodes that are linked to that node. (Or rather it shares ownership with all the other CLPtr objects that point somewhere else in the same "cluster" of nodes.) So for that reason, the CLPtr code is responsible for all maintenance of the structure?

@monarch_dodra
Okay, I'll restructure the code in that way. In my current design, the nodes to which the data point are owned by other classes and it is not the Node's responsibility to clean them up.
Is it okay to overload some operators in the Node class to simplify the CLPtr code?
Do you think this will fix the problem or will it just improve the overall code design?

[monarch_dodra]

Is it okay to overload some operators in the Node class to simplify the CLPtr code?

The problem when writing methods for a class, when the goal is to simplify another class, is that you will leave un-expected side effects.

For example, in your earliest example, node's destructor was able to destroy some of its neighbors. While this might look cool at first (because all you have to de is destroy the head when you want to clear a list), you end up surprised by the behavior of more complicated functions, like those that destroy a single node (let alone splice a list).

My recommendation is to only write methods in node that are directly related to node and its own internal management. Now, if your CLPtr class needs to do things to node, I recommend writing CLPtr:oThingsToNode(node*). This way, you are making both intent, and ownership of behavior cristal clear.

That said, in programming, you have got to do whatever you got to do to make things work

[superbonzo]

Yeah, CLPtr is an iterator for the list. It has a pointer to a node and a dereference operator that returns the datum contained in the node. I believe you are saying that even though the a CLPtr object only ever has a pointer to a single node, it is still the owner of all the nodes that are linked to that node. (Or rather it shares ownership with all the other CLPtr objects that point somewhere else in the same "cluster" of nodes.) So for that reason, the CLPtr code is responsible for all maintenance of the structure?

No, as AlexF said, that would be true only if CLPtr were a kind of list class. For example, an std::list<> owns its nodes ( that are structures hidden inside the std::list implementation, as suggested by monarch_dodra ) and is the sole responsible of their life time management; in turn, nodes data are exposed through std::list<>::iterator's which have both the responsability of node data access and nodes traversal. In your example, CLPtr plays the role of an iterator and so no, neither CLNode nor CLPtr should manage other nodes life time ( the reasons being the one alluded in AlexF and monarch_dodra posts ).

BTW, note that this is true even if the original intent of your design is exactly to tie the list lifetime to the lifetime of its node referents; indeed, take a look at the boost shared_container_iterator for an example.

[hoodmane]

@Monarch_Dodra
That makes sense to me. Writing code that makes some operations look really simple at the expense of giving others unexpected side effects is probably not a good trade-off. When manipulating the node that a CLPtr points to, wouldn't it be better to make the function a member function of CLPtr? But for a CLPtr-related function that takes nodes as arguments, making a static function in CLPtr is the way to go?

@superbonozo
I'm not sure I understand what you are saying. When there all CLPtr's to a list go out of scope, there is no way to regain access to the CLNode's. Which class should be responsible for destroying the CLNode's when this occurs?

[superbonzo]

@superbonozo
I'm not sure I understand what you are saying. When there all CLPtr's to a list go out of scope, there is no way to regain access to the CLNode's. Which class should be responsible for destroying the CLNode's when this occurs?

The point we're making is that if you try to manage nodes lifetimes from the nodes themselves ( or iterators to them ) you'll likely end up with troubles because in order for your algorithms to work you need to have a tight control on when the nodes are actually destroyed which is difficult and error prone in this case.

The simplest solution to this problem is to give exclusive ownership of "elements" to a unique centralized manager, that is, in STL jargon, the "container". When the container is destroyed its elements are destroyed.

BTW, is there a reason why you're not using STL directly ?

[monarch_dodra]

@Monarch_Dodra
That makes sense to me. Writing code that makes some operations look really simple at the expense of giving others unexpected side effects is probably not a good trade-off. When manipulating the node that a CLPtr points to, wouldn't it be better to make the function a member function of CLPtr? But for a CLPtr-related function that takes nodes as arguments, making a static function in CLPtr is the way to go?

I'm afraid you've lost me on this one...

[hoodmane]

@monarch_dodra
Never mind I think I figured it out.


@SuperBonozo
So you make a third container class that has functions that return iterators and when that is destroyed, it is responsible for all cleanup? Is the container also responsible for cleaning up remaining iterators?


I'll explain why I'm not using STL; please tell me what you think (I suppose that if the decision was in error, this is at least a learning experience).

This is part of a project in which I have a planar graph and a fixed geometrical embedding in the euclidean plane (all edges straight and vertex coordinates known). I need to add code to the graph to create the Poincaré dual of the graph ( http://en.wikipedia.org/wiki/Dual_graph ).

As it turns out, to get the dual graph, all I need is to construct a closed walk for each face. This is the sequence of vertices and edges that you would see if you walked around the perimeter of the face. So it seemed natural to me to make two circular doubly linked lists and crosslink them, so that from a given edge you can get to the next edge in the walk, the previous edge in the walk, the next vertex in a walk, or the previous vertex in the walk.

And so this is why I want to make this data structure. I've worked out by hand the set of operations that are necessary for this to work, and I think that the code will be conceptually much simpler if I put some of the details of the walk construction in a different class.

[superbonzo]

So you make a third container class that has functions that return iterators and when that is destroyed, it is responsible for all cleanup?

yes, or better, following the well-proven STL design, the user should see only two kind of classes: the container and the iterators; the former is responsible of managing the sequence as a whole ( including its lifetime ), the latter is responsible for data access and sequence traversal. Then, there's also the element data, of course.

Is the container also responsible for cleaning up remaining iterators?

no, iterators are usually lightweight types with value semantics ( say, similar to pointers ) and they are owned by the user ( most of the times, they simply appear as automatic variables ... )

I'll explain why I'm not using STL ...

well, this doesn't explain why you're not using STL ... anyway, take a look at the boost graph library for a highly flexible graph interface

[monarch_dodra]

A circular list is a difficult object to use: What is the first item, what is the last? If you use iterators, do you realize that begin() points to the same object as end()? This can be problematic with algorithms, and will require modifying the classic iteration loop.

While a circular list might be what best represents the real life problem, it might not be the optimal computer science data structure. I'd stick to a normal linked list.

That said, I'm not an expert on what you are trying to solve, and if a circular list is indead what you need, I'd recommend writing an adaptor, rather than a full fledged container.

An adapter is a pseudo container that contains another container, and merely changes the interface to make it look to the outside like another one. The simpler examples are the stack and queue, which are just adapters of other containers.

In this case, you'll also have to adapt the iterator for it to go round and round and round...

Something like this: It's not complete, but should contain the bulk of what you need

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

class circular_list
{
public:
  struct iterator : public std::iterator<std::bidirectional_iterator_tag, int>
  {
  friend class circular_list;
  public:

    iterator() : _it()
               , _pList(0)
    {}

    iterator(const iterator& iOther) : _it(iOther._it)
                                     , _pList(iOther._pList)
    {}

    iterator& operator=(const iterator& iOther)
    {
      _it = iOther._it;
      _pList = iOther._pList;
      return *this;
    }


    iterator& operator++()
    {
      ++_it;
      if(_it == _pList->end()){_it = _pList->begin();}
      return *this;
    }

    iterator& operator--()
    {
      if(_it == _pList->begin()){_it = _pList->end();}
      ++_it;
      return *this;
    }

    int& operator*(){return *_it;}

    friend bool operator==(const iterator& iLhs, const iterator& iRhs)
    {return iLhs._it == iRhs._it;}
    friend bool operator!=(const iterator& iLhs, const iterator& iRhs)
    {return iLhs._it != iRhs._it;}

  private:
    iterator(std::list<int>* pList, std::list<int>::iterator it)
      : _it(it)
      , _pList(pList)
    {}

    std::list<int>::iterator _it;
    std::list<int>* _pList;
  };

public:
  //typedefs for better stl complicance
  typedef std::list<int>::reference reference;
  typedef std::list<int>::const_reference const_reference;
  //typedef std::list<int>::iterator iterator; //not a typedef
  //typedef std::list<int>::const_iterator const_iterator; //not implemented
  typedef std::list<int>::size_type size_type;
  typedef std::list<int>::difference_type difference_type;
  typedef std::list<int>::value_type value_type;
  typedef std::list<int>::allocator_type allocator_type;
  typedef std::list<int>::pointer pointer;
  typedef std::list<int>::const_pointer const_pointer;
  //typedef std::list<int>::reverse_iterator reverse_iterator; //not implemented
  //typedef std::list<int>::const_reverse_iterator const_reverse_iterator; //not implemented

  //simple forwards
  bool empty(){return _list.empty();}
  bool size(){return _list.size();}
  bool front(){return _list.front();}
  //bool back(){return _list.back();} //does it make sense to have a back?

  void push_front(int v){_list.push_front(v);}
  void push_back(int v){_list.push_back(v);}
  void insert(iterator it, int v){_list.insert(it._it, v);}

  void pop_front(int){_list.pop_front();}
  void poph_back(int){_list.pop_back();}
  void erase(iterator it){_list.erase(it._it);}

  iterator begin(){return iterator(&_list, _list.begin());}
  iterator end(){return begin();}

private:
  std::list<int> _list;
};

int main()
{
  circular_list cl;
  cl.push_back(1);
  cl.push_back(2);
  cl.push_back(3);
  cl.push_back(4);

  std::cout << "test1: Going round and round and round..." << std::endl;
  {
    circular_list::iterator it = cl.begin();
    if(!cl.empty())
    {
      for(int i=0; i<55; ++i, ++it)
        {std::cout << *it;}
    }
  }
  std::cout << std::endl << std::endl;

  std::cout << "test2: Read everything to output..." << std::endl;
  {
    circular_list::iterator it = cl.begin();
    circular_list::iterator it_end = cl.end();
    if(!cl.empty())
    {
      do
      {
        std::cout << *it ;
      }
      while(++it != it_end);
    }
  }
  std::cout << std::endl << std::endl;
}

output:

test1: Going round and round and round...
1234123412341234123412341234123412341234123412341234123

test2: Read everything to output...
1234

[superbonzo]

uhm, I would advice against such an adaptor because it does not fulfill the container concept requirements ( just consider that size() should be equal to std:istance( begin(), end ) ); IMHO, if one really wants such an infinite sequence view of a bidirectional container It's better to write an iterator adaptor instead. Actually, I don't think the OP really needs one.

BTW, unless I'm missing something, the "friend class circular_list;" is unnecessary because member classes have always access to the containing class private data.