source: NonGTP/Boost/boost/ptr_container/detail/reversible_ptr_container.hpp @ 857

Revision 857, 20.1 KB checked in by igarcia, 18 years ago (diff)
Line 
1//
2// Boost.Pointer Container
3//
4//  Copyright Thorsten Ottosen 2003-2005. Use, modification and
5//  distribution is subject to the Boost Software License, Version
6//  1.0. (See accompanying file LICENSE_1_0.txt or copy at
7//  http://www.boost.org/LICENSE_1_0.txt)
8//
9// For more information, see http://www.boost.org/libs/ptr_container/
10//
11
12
13#ifndef BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP
14#define BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP
15
16#if defined(_MSC_VER) && (_MSC_VER >= 1200)
17# pragma once
18#endif
19
20#include <boost/ptr_container/detail/scoped_deleter.hpp>
21#include <boost/ptr_container/detail/static_move_ptr.hpp>
22#include <boost/ptr_container/exception.hpp>
23#include <boost/ptr_container/clone_allocator.hpp>
24#include <boost/ptr_container/nullable.hpp>
25
26#ifdef BOOST_NO_SFINAE
27#else
28#include <boost/range/functions.hpp>
29#endif
30
31#include <boost/assert.hpp>
32#include <boost/config.hpp>
33#include <boost/range/result_iterator.hpp>
34#include <boost/utility/enable_if.hpp>
35#include <boost/type_traits/is_pointer.hpp>
36#include <boost/type_traits/is_integral.hpp>
37#include <algorithm>
38#include <exception>
39#include <memory>
40
41namespace boost
42{
43   
44namespace ptr_container_detail
45{
46
47    template< class CloneAllocator >
48    struct clone_deleter
49    {
50        template< class T >
51        void operator()( const T* p ) const
52        {
53            CloneAllocator::deallocate_clone( p );
54        }
55    };
56
57    template< class T >
58    struct is_pointer_or_integral
59    {
60        BOOST_STATIC_CONSTANT(bool, value = is_pointer<T>::value || is_integral<T>::value );
61    };
62
63    struct is_pointer_or_integral_tag {};
64    struct is_range_tag {};
65
66   
67   
68    template
69    <
70        class Config,
71        class CloneAllocator
72    >
73    class reversible_ptr_container
74    {
75    private:
76        BOOST_STATIC_CONSTANT( bool, allow_null = Config::allow_null );
77       
78        typedef BOOST_DEDUCED_TYPENAME Config::value_type Ty_;
79
80        template< bool allow_null_values >
81        struct null_clone_allocator
82        {
83            template< class Iter >
84            static Ty_* allocate_clone_from_iterator( Iter i )
85            {
86                return allocate_clone( Config::get_const_pointer( i ) );
87            }
88           
89            static Ty_* allocate_clone( const Ty_* x )
90            {
91                if( allow_null_values )
92                {
93                    if( x == 0 )
94                        return 0;
95                }
96                else
97                {
98                    BOOST_ASSERT( x != 0 && "Cannot insert clone of null!" );
99                }
100
101                return CloneAllocator::allocate_clone( *x );
102            }
103           
104            static void deallocate_clone( const Ty_* x )
105            {
106                if( allow_null_values )
107                {
108                    if( x == 0 )
109                        return;
110                }
111
112                CloneAllocator::deallocate_clone( x );
113            }
114        };
115
116        typedef BOOST_DEDUCED_TYPENAME Config::void_container_type  Cont;
117#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))   
118        typedef  null_clone_allocator<reversible_ptr_container::allow_null>
119                                                                    null_cloner_type;
120#else
121        typedef null_clone_allocator<allow_null>                    null_cloner_type;
122#endif       
123        typedef clone_deleter<null_cloner_type>                     Deleter;
124
125        Cont      c_;
126
127    protected:
128        Cont& c_private()                { return c_; }
129        const Cont& c_private() const    { return c_; }
130
131    public: // typedefs
132        typedef  BOOST_DEDUCED_TYPENAME Config::object_type 
133                               object_type;
134        typedef  Ty_*          value_type;
135        typedef  Ty_*          pointer;
136        typedef  Ty_&          reference;
137        typedef  const Ty_&    const_reference;
138       
139        typedef  BOOST_DEDUCED_TYPENAME Config::iterator
140                                   iterator;
141        typedef  BOOST_DEDUCED_TYPENAME Config::const_iterator
142                                   const_iterator;
143        typedef  BOOST_DEDUCED_TYPENAME Config::reverse_iterator
144                                   reverse_iterator;
145        typedef  BOOST_DEDUCED_TYPENAME Config::const_reverse_iterator     
146                                   const_reverse_iterator;
147        typedef  BOOST_DEDUCED_TYPENAME Cont::difference_type
148                                   difference_type;
149        typedef  BOOST_DEDUCED_TYPENAME Cont::size_type
150                                   size_type;
151        typedef  BOOST_DEDUCED_TYPENAME Config::allocator_type
152                                   allocator_type;
153
154        typedef ptr_container_detail::static_move_ptr<Ty_,Deleter>
155                                   auto_type;
156           
157    protected:
158           
159        typedef ptr_container_detail::scoped_deleter<Ty_,null_cloner_type>
160                                   scoped_deleter;
161        typedef BOOST_DEDUCED_TYPENAME Cont::iterator
162                                   ptr_iterator;
163        typedef BOOST_DEDUCED_TYPENAME Cont::const_iterator
164                                   ptr_const_iterator;
165    private:
166
167        template< class InputIterator > 
168        void copy( InputIterator first, InputIterator last )
169        {
170            std::copy( first, last, begin() );
171        }
172       
173        void copy( const reversible_ptr_container& r )
174        {
175            copy( r.begin(), r.end() );
176        }
177       
178        void copy_clones_and_release( scoped_deleter& sd ) // nothrow
179        {
180            BOOST_ASSERT( size_type( std::distance( sd.begin(), sd.end() ) ) == c_.size() );
181            std::copy( sd.begin(), sd.end(), c_.begin() );
182            sd.release();
183        }
184       
185        void insert_clones_and_release( scoped_deleter& sd ) // strong
186        {
187            c_.insert( sd.begin(), sd.end() );
188            sd.release();
189        }
190
191        template< class ForwardIterator >
192        void clone_assign( ForwardIterator first,
193                           ForwardIterator last ) // strong
194        {
195            BOOST_ASSERT( first != last );
196            scoped_deleter sd( first, last );      // strong
197            copy_clones_and_release( sd );         // nothrow
198        }
199
200        template< class ForwardIterator >
201        void clone_back_insert( ForwardIterator first,
202                                ForwardIterator last )
203        {
204            BOOST_ASSERT( first != last );
205            scoped_deleter sd( first, last );
206            insert_clones_and_release( sd, end() );
207        }
208       
209        void remove_all()
210        {
211            remove( begin(), end() );
212        }
213
214    protected:
215
216        void insert_clones_and_release( scoped_deleter& sd,
217                                        iterator where ) // strong
218        {
219            //
220            // 'c_.insert' always provides the strong guarantee for T* elements
221            // since a copy constructor of a pointer cannot throw
222            //
223            c_.insert( where.base(),
224                       sd.begin(), sd.end() );
225            sd.release();
226        }
227
228        template< class I >
229        void remove( I i )
230        {
231            null_policy_deallocate_clone( Config::get_const_pointer(i) );
232        }
233
234        template< class I >
235        void remove( I first, I last )
236        {
237            for( ; first != last; ++first )
238                remove( first );
239        }
240
241        template< class Range >
242        BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type
243        adl_begin( Range& r )
244        {
245            #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) 
246            return begin( r );
247            #else
248            using boost::begin;
249            return begin( r );
250            #endif
251        }
252
253        template< class Range >
254        BOOST_DEDUCED_TYPENAME range_result_iterator<Range>::type
255        adl_end( Range& r )
256        {
257            #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) 
258            return end( r );
259            #else
260            using boost::end;
261            return end( r );
262            #endif
263        }
264       
265        static void enforce_null_policy( Ty_* x, const char* msg )
266        {
267            if( !allow_null )
268            {
269                if( 0 == x )
270                    throw bad_pointer( msg );
271            }
272        }
273
274        static Ty_* null_policy_allocate_clone( const Ty_* x )
275        {
276            return null_cloner_type::allocate_clone( x );
277        }
278
279        static void null_policy_deallocate_clone( const Ty_* x )
280        {
281            null_cloner_type::deallocate_clone( x );
282        }
283
284    private:
285        template< class ForwardIterator >
286        ForwardIterator advance( ForwardIterator begin, size_type n )
287        {
288            ForwardIterator iter = begin;
289            std::advance( iter, n );
290            return iter;
291        }
292       
293    private:
294        reversible_ptr_container( const reversible_ptr_container& );
295        void operator=( const reversible_ptr_container& );
296       
297    public: // foundation! should be protected!
298        explicit reversible_ptr_container( const allocator_type& a = allocator_type() )
299         : c_( a )
300        {}
301       
302        template< class PtrContainer >
303        explicit reversible_ptr_container( std::auto_ptr<PtrContainer> clone )
304          : c_( allocator_type() )               
305        {
306            swap( *clone );
307        }
308
309    private:
310        template< class I >
311        void constructor_impl( I first, I last, std::input_iterator_tag ) // basic
312        {
313            while( first != last )
314            {
315                insert( end(), null_cloner_type::allocate_clone_from_iterator(first) );
316                ++first;
317            }
318        }
319
320        template< class I >
321        void constructor_impl( I first, I last, std::forward_iterator_tag ) // strong
322        {
323            if( first == last )
324                return;
325            clone_back_insert( first, last );
326        }
327
328
329    public:
330        // overhead: null-initilization of container pointer (very cheap compared to cloning)
331        // overhead: 1 heap allocation (very cheap compared to cloning)
332        template< class InputIterator >
333        reversible_ptr_container( InputIterator first,
334                                  InputIterator last,
335                                  const allocator_type& a = allocator_type() ) // basic, strong
336        : c_( a )
337        {
338            constructor_impl( first, last,
339#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
340#else
341                              BOOST_DEDUCED_TYPENAME
342#endif                             
343                              iterator_category<InputIterator>::type() );
344        }
345
346        template< class Compare >
347        reversible_ptr_container( const Compare& comp,
348                                  const allocator_type& a )
349        : c_( comp, a ) {}
350
351        template< class PtrContainer, class Compare >
352        reversible_ptr_container( std::auto_ptr<PtrContainer> clone,
353                                  Compare comp )
354        : c_( comp, allocator_type() )               
355        {
356            swap( *clone );
357        }
358
359    public:       
360        ~reversible_ptr_container()
361        {
362            remove_all();
363        }
364       
365        template< class PtrContainer >
366        void operator=( std::auto_ptr<PtrContainer> clone )     
367        {
368            swap( *clone );
369        }
370
371    public:
372       
373        allocator_type get_allocator() const                   
374        {
375            return c_.get_allocator();
376        }
377 
378    public: // container requirements
379        iterator                   begin()            { return iterator( c_.begin() ); }
380        const_iterator             begin() const      { return const_iterator( c_.begin() ); }
381        iterator                   end()              { return iterator( c_.end() ); }
382        const_iterator             end() const        { return const_iterator( c_.end() ); }
383        reverse_iterator           rbegin()           { return reverse_iterator( c_.rbegin() ); }
384        const_reverse_iterator     rbegin() const     { return const_reverse_iterator( c_.rbegin() ); }
385        reverse_iterator           rend()             { return reverse_iterator( c_.rend() ); }
386        const_reverse_iterator     rend() const       { return const_reverse_iterator( c_.rend() ); }
387 
388        void swap( reversible_ptr_container& r ) // notrow
389        {
390            c_.swap( r.c_ );
391        }
392         
393        size_type size() const // nothrow
394        {
395            return c_.size();
396        }
397
398        size_type max_size() const // nothrow
399        {
400            return c_.max_size();
401        }
402       
403        bool empty() const // nothrow
404        {
405            return c_.empty();
406        }
407
408    public: // optional container requirements
409
410        bool operator==( const reversible_ptr_container& r ) const // nothrow
411        {
412            if( size() != r.size() )
413                return false;
414            else
415                return std::equal( begin(), end(), r.begin() );
416        }
417
418        bool operator!=( const reversible_ptr_container& r ) const // nothrow
419        {
420            return !(*this == r);
421        }
422       
423        bool operator<( const reversible_ptr_container& r ) const // nothrow
424        {
425             return std::lexicographical_compare( begin(), end(), r.begin(), r.end() );
426        }
427
428        bool operator<=( const reversible_ptr_container& r ) const // nothrow
429        {
430            return !(r < *this);
431        }
432
433        bool operator>( const reversible_ptr_container& r ) const // nothrow
434        {
435            return r < *this;
436        }
437
438        bool operator>=( const reversible_ptr_container& r ) const // nothrow
439        {
440            return !(*this < r);
441        }
442
443    public: // modifiers
444
445        iterator insert( iterator before, Ty_* x )
446        {
447            enforce_null_policy( x, "Null pointer in 'insert()'" );
448
449            auto_type ptr( x );                            // nothrow
450            iterator res( c_.insert( before.base(), x ) ); // strong, commit
451            ptr.release();                                 // nothrow
452            return res;
453        }
454
455        iterator erase( iterator x ) // nothrow
456        {
457            BOOST_ASSERT( !empty() );
458            BOOST_ASSERT( x != end() );
459           
460            remove( x );
461            return iterator( c_.erase( x.base() ) );
462        }
463       
464        iterator erase( iterator first, iterator last ) // nothrow
465        {
466            BOOST_ASSERT( !empty() );
467            remove( first, last );
468            return iterator( c_.erase( first.base(),
469                                       last.base() ) );
470        }
471
472        template< class Range >
473        iterator erase( const Range& r )
474        {
475            return erase( adl_begin(r), adl_end(r) );
476        }
477       
478        void clear()                               
479        {
480            remove_all();
481            c_.clear();
482        }
483       
484    public: // access interface
485       
486        auto_type release( iterator where )
487        {
488            BOOST_ASSERT( where != end() );
489            if( empty() )
490                throw bad_ptr_container_operation( "'release()' on empty container" );
491           
492            auto_type ptr( Config::get_pointer( where ) );  // nothrow
493            c_.erase( where.base() );                       // nothrow
494            return boost::ptr_container_detail::move( ptr );
495        }
496
497        auto_type replace( iterator where, Ty_* x ) // strong 
498        {
499            BOOST_ASSERT( where != end() );
500
501            enforce_null_policy( x, "Null pointer in 'replace()'" );
502           
503            auto_type ptr( x );
504           
505            if( empty() )
506                throw bad_ptr_container_operation( "'replace()' on empty container" );
507
508            auto_type old( Config::get_pointer( where ) );  // nothrow
509           
510//#if defined( __GNUC__ ) || defined( __MWERKS__ ) || defined( __COMO__ )
511            const_cast<void*&>(*where.base()) = ptr.release();               
512//#else
513//            *where.base() = ptr.release(); // nothrow, commit
514//#endif           
515            return boost::ptr_container_detail::move( old );
516        }
517
518        auto_type replace( size_type idx, Ty_* x ) // strong
519        {
520            enforce_null_policy( x, "Null pointer in 'replace()'" );
521           
522            auto_type ptr( x );
523           
524            if( idx >= size() )
525                throw bad_index( "'replace()' out of bounds" );
526           
527            auto_type old( static_cast<Ty_*>( c_[idx] ) ); // nothrow
528            c_[idx] = ptr.release();                       // nothrow, commit
529            return boost::ptr_container_detail::move( old );
530        }
531       
532    }; // 'reversible_ptr_container'
533
534
535#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))   
536#define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
537    typename base_type::auto_type                   \
538    release( typename base_type::iterator i )       \
539    {                                               \
540        return boost::ptr_container_detail::move(base_type::release(i)); \
541    }                                               
542#else
543#define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
544    using base_type::release;
545#endif
546   
547    //
548    // two-phase lookup of template functions
549    // is buggy on most compilers, so we use a macro instead
550    //
551#define BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) \
552                                                    \
553    PC( std::auto_ptr<this_type> r )                \
554    : base_type ( r ) { }                           \
555                                                    \
556    void operator=( std::auto_ptr<this_type> r )    \
557    {                                               \
558        base_type::operator=( r );                  \
559    }                                               \
560                                                    \
561    std::auto_ptr<this_type> release()              \
562    {                                               \
563      std::auto_ptr<this_type> ptr( new this_type );\
564      this->swap( *ptr );                           \
565      return ptr;                                   \
566    }                                               \
567    BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \
568                                                    \
569    std::auto_ptr<this_type> clone() const          \
570    {                                               \
571       return std::auto_ptr<this_type>( new this_type( this->begin(), this->end() ) ); \
572    }
573
574#define BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type )                       \
575    typedef BOOST_DEDUCED_TYPENAME base_type::iterator        iterator;                \
576    typedef BOOST_DEDUCED_TYPENAME base_type::size_type       size_type;               \
577    typedef BOOST_DEDUCED_TYPENAME base_type::const_reference const_reference;         \
578    typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type  allocator_type;          \
579    PC( const allocator_type& a = allocator_type() ) : base_type(a) {}                 \
580    template< class InputIterator >                                                    \
581    PC( InputIterator first, InputIterator last,                                       \
582    const allocator_type& a = allocator_type() ) : base_type( first, last, a ) {}     
583   
584
585                 
586#define BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type )           \
587   BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type )                                    \
588   BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type )
589   
590    } // namespace 'ptr_container_detail'
591
592} // namespace 'boost' 
593
594#endif
Note: See TracBrowser for help on using the repository browser.