Re: std::ext STL (was: Re: design doc on alternative pointer support)

[Bob Walters <bob dot s dot walters at gmail dot com>]

I think I had looked at the latest patches, but seeing the allocator  
helps make it clearer.

So some of the conventions need to unify the approach:

1) Use of &* combo as a means of casting.  This should be OK because  
it gets optimized away for standard pointers.  I am curious why you  
did not use implicit casting support in your case?  Were there  
unsolvable ambiguities that came up with shifted_ptr?

2) Everything which alloc::pointer may point to must be on the heap.

Are there Others?

I would like to propose that we go with the approach of using a  
pointer-type chooser in the headers, rather than completely  
duplicating the headers.  While stl_tree was ugly when that was done,  
(and list will have similar issues), vector and string were 3 and 1  
line changes, respectively, because there were already internal  
structures which nicely encapsulated the pointers used in the actual  
data structures, so I don't want to get into the convention of  
duplicating the headers.

Soliciting opinions regarding iterators:  In general, I am leaning  
away from requiring that the iterators use alloc::pointer.  I can see  
some reasons why it might be wanted, such as passing iterators between  
processes via shared memory, or making the use of iterators a bit  
'safer' for smart_ptr approaches.  (e.g. can remove an iterator, and  
still use the iterator to refer to the removed node until the iterator  
goes out of scope).  Right now this is true of my stl_tree changes,  
but not of the ones I have proposed for stl_vector, and string.

> The other function _M_clear() will ne to be rewritten.  It is a  
> interesting one because the nodes of a list will not disappear if we  
> delete the first node pointer because the first node still is  
> refered to by the second node, etc.  We need to take a better "smart  
> pointer" approach here.


It's an interesting problem.  In your case, the code needs to cut the  
links between list nodes, and allow the pointer type to determine when  
deallocation should occur.  Can the allocator, in your case, address  
that concern in its destroy/deallocate methods, or would that require  
specializing something based on the specific Link_node type?

Soliciting opinions: One thing that might be reasonable is to have the  
code that is deallocating nodes explicitly set pointers to null prior  
to calling deallocate/destroy so that smart pointer approaches can  
work by simply making deallocate/destroy into no-ops.  This would not  
be too hard to explain (comment) in the code, and I suspect that if  
alternative pointer support is enabled, there will be many cases where  
people want to use some kind of smart pointer implementation.  Phil,  
would this convention work for you?


On Aug 13, 2008, at 4:43 AM, Phil Bouchard wrote:

> ----- Original Message ----- From: "Bob Walters" <bob.s.walters@gmail.com 
> >
> To: "Phil Bouchard" <philippe@fornux.com>; <libstdc++@gcc.gnu.org>
> Sent: Tuesday, August 12, 2008 6:59 PM
> Subject: std::ext STL (was: Re: design doc on alternative pointer  
> support)
>
> [...]
>
> > However, after reviewing your code, I noticed all the stuff commented
> > out in clear(), and other commented out calls to _M_put_node
> > (deallocation), and I assume that is because you specifically are
> > working with a smart pointer.  Is this version of list<> intended to
> > work only with a smart pointer approach?  Have you given any thought
> > to how this template could be made to work in general, with any
> > pointer type, possibly by requiring that the allocator implement  
> > empty
> > destroy() and deallocate() methods to accomodate the smart pointer?
>
> I just want to make sure you are referring to the latest version of  
> the patches.  You will find them attached.  I think stl_list.h.patch  
> is close to my last version but I haven't completed list.tcc.patch  
> yet.  In the latter we can see I reworked:
> - _List_node_base<_Alloc>::hook to work with any pointer's logic.
>
> I think this function is the worse case scenario because it's the  
> only one handling at the same time the three different types:
> - shifted<T> *
> - T &
> - shifted_ptr<T>
>
> This is why I was saying previously that the smart pointer I am  
> using will help define the standards better because of its  
> "value_type" not being of type "T" but "shifted<T>":
>
> Old code:
> template<typename _Alloc> void  
> _List_node_base<_Alloc>::hook(value_type * const __position)
> {
>  this->_M_next = __position;
>  this->_M_prev = __position->_M_prev;
>  __position->_M_prev->_M_next = this;
>  __position->_M_prev = this;
> }
>
> New code:
> template<typename _Alloc> void  
> _List_node_base<_Alloc>::hook(value_type * const __position)
> {
>  static_cast<_List_node_base &>(*__position)._M_next = this->_M_next- 
> >_M_prev;
>  static_cast<_List_node_base &>(*__position)._M_prev = this->_M_prev;
>  this->_M_prev->_M_next = __position;
>  this->_M_prev = __position;
> }
>
> FYI shifted<T> looks like:
> template <typename T> class shifted : public ...
> {
>  typedef T data_type;
>
>  T elem_;
>
>  public:
>      ...
>      operator data_type & ()             { return elem_; }
>      operator data_type const & () const { return elem_; }
>      ...
> };
>
> I am using the cast operator inside class shifted<T> but it is not  
> dangerous since shifted<T> should be referred to thru a pointer  
> (shifted<T> *), not by value (shifted<T> &) hence no implicit cast  
> will occur.  This is isn't the ideal solution but it's a temporary  
> one until I adapt hook() properly.
>
> The other function _M_clear() will ne to be rewritten.  It is a  
> interesting one because the nodes of a list will not disappear if we  
> delete the first node pointer because the first node still is  
> refered to by the second node, etc.  We need to take a better "smart  
> pointer" approach here.
>
>
> Regards,
> -Phil
> <list.tcc.patch><stl_list.h.patch><shifted_allocator.hpp>