multi_index/detail/seq_index_ops.hpp

0001 /* Copyright 2003-2020 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <boost/core/no_exceptions_support.hpp>
0018 #include <boost/multi_index/detail/seq_index_node.hpp>
0019 #include <boost/limits.hpp>
0020 #include <boost/type_traits/aligned_storage.hpp>
0021 #include <boost/type_traits/alignment_of.hpp>
0022 #include <cstddef>
0023
0024 namespace boost{
0025
0026 namespace multi_index{
0027
0028 namespace detail{
0029
0030 /* Common code for sequenced_index memfuns having templatized and
0031  * non-templatized versions.
0032  */
0033
0034 template <typename SequencedIndex,typename Predicate>
0035 void sequenced_index_remove(SequencedIndex& x,Predicate pred)
0036 {
0037   typedef typename SequencedIndex::iterator iterator;
0038   iterator first=x.begin(),last=x.end();
0039   while(first!=last){
0040     if(pred(*first))x.erase(first++);
0041     else ++first;
0042   }
0043 }
0044
0045 template <typename SequencedIndex,class BinaryPredicate>
0046 void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
0047 {
0048   typedef typename SequencedIndex::iterator iterator;
0049   iterator first=x.begin();
0050   iterator last=x.end();
0051   if(first!=last){
0052     for(iterator middle=first;++middle!=last;middle=first){
0053       if(binary_pred(*middle,*first))x.erase(middle);
0054       else first=middle;
0055     }
0056   }
0057 }
0058
0059 template <typename SequencedIndex,typename Compare>
0060 void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
0061 {
0062   typedef typename SequencedIndex::iterator iterator;
0063   if(&x!=&y){
0064     iterator first0=x.begin(),last0=x.end();
0065     iterator first1=y.begin(),last1=y.end();
0066     while(first0!=last0&&first1!=last1){
0067       if(comp(*first1,*first0))x.splice(first0,y,first1++);
0068       else ++first0;
0069     }
0070     x.splice(last0,y,first1,last1);
0071   }
0072 }
0073
0074 /* sorting  */
0075
0076 /* auxiliary stuff */
0077
0078 template<typename Node,typename Compare>
0079 void sequenced_index_collate(
0080   BOOST_DEDUCED_TYPENAME Node::impl_type* x,
0081   BOOST_DEDUCED_TYPENAME Node::impl_type* y,
0082   Compare comp)
0083 {
0084   typedef typename Node::impl_type    impl_type;
0085   typedef typename Node::impl_pointer impl_pointer;
0086
0087   impl_pointer first0=x->next();
0088   impl_pointer last0=x;
0089   impl_pointer first1=y->next();
0090   impl_pointer last1=y;
0091   while(first0!=last0&&first1!=last1){
0092     if(comp(
0093         Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
0094       impl_pointer tmp=first1->next();
0095       impl_type::relink(first0,first1);
0096       first1=tmp;
0097     }
0098     else first0=first0->next();
0099   }
0100   impl_type::relink(last0,first1,last1);
0101 }
0102
0103 /* Some versions of CGG require a bogus typename in counter_spc
0104  * inside sequenced_index_sort if the following is defined
0105  * also inside sequenced_index_sort.
0106  */
0107
0108 BOOST_STATIC_CONSTANT(
0109   std::size_t,
0110   sequenced_index_sort_max_fill=
0111     (std::size_t)std::numeric_limits<std::size_t>::digits+1);
0112
0113 #include <boost/multi_index/detail/ignore_wstrict_aliasing.hpp>
0114
0115 template<typename Node,typename Compare>
0116 void sequenced_index_sort(Node* header,Compare comp)
0117 {
0118   /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
0119    * The implementation is a little convoluted: in the original code
0120    * counter elements and carry are std::lists: here we do not want
0121    * to use multi_index instead, so we do things at a lower level, managing
0122    * directly the internal node representation.
0123    * Incidentally, the implementations I've seen of this algorithm (SGI,
0124    * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
0125    * use any dynamic storage.
0126    */
0127
0128   if(header->next()==header->impl()||
0129      header->next()->next()==header->impl())return;
0130
0131   typedef typename Node::impl_type      impl_type;
0132   typedef typename Node::impl_pointer   impl_pointer;
0133
0134   typedef typename aligned_storage<
0135     sizeof(impl_type),
0136     alignment_of<impl_type>::value
0137   >::type                               carry_spc_type;
0138   carry_spc_type                        carry_spc;
0139   impl_type&                            carry=
0140     *reinterpret_cast<impl_type*>(&carry_spc);
0141   typedef typename aligned_storage<
0142     sizeof(
0143       impl_type
0144         [sequenced_index_sort_max_fill]),
0145     alignment_of<
0146       impl_type
0147         [sequenced_index_sort_max_fill]
0148     >::value
0149   >::type                               counter_spc_type;
0150   counter_spc_type                      counter_spc;
0151   impl_type*                            counter=
0152     reinterpret_cast<impl_type*>(&counter_spc);
0153   std::size_t                           fill=0;
0154
0155   carry.prior()=carry.next()=static_cast<impl_pointer>(&carry);
0156   counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]);
0157
0158   BOOST_TRY{
0159     while(header->next()!=header->impl()){
0160       impl_type::relink(carry.next(),header->next());
0161       std::size_t i=0;
0162       while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){
0163         sequenced_index_collate<Node>(&carry,&counter[i++],comp);
0164       }
0165       impl_type::swap(
0166         static_cast<impl_pointer>(&carry),
0167         static_cast<impl_pointer>(&counter[i]));
0168       if(i==fill){
0169         ++fill;
0170         counter[fill].prior()=counter[fill].next()=
0171           static_cast<impl_pointer>(&counter[fill]);
0172       }
0173     }
0174
0175     for(std::size_t i=1;i<fill;++i){
0176       sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
0177     }
0178     impl_type::swap(
0179       header->impl(),static_cast<impl_pointer>(&counter[fill-1]));
0180   }
0181   BOOST_CATCH(...)
0182   {
0183     impl_type::relink(
0184       header->impl(),carry.next(),static_cast<impl_pointer>(&carry));
0185     for(std::size_t i=0;i<=fill;++i){
0186       impl_type::relink(
0187         header->impl(),counter[i].next(),
0188         static_cast<impl_pointer>(&counter[i]));
0189     }
0190     BOOST_RETHROW;
0191   }
0192   BOOST_CATCH_END
0193 }
0194
0195 #include <boost/multi_index/detail/restore_wstrict_aliasing.hpp>
0196
0197 } /* namespace multi_index::detail */
0198
0199 } /* namespace multi_index */
0200
0201 } /* namespace boost */
0202
0203 #endif