--- /dev/null
+/* Copyright 2003-2007 Joaquín M López Muñoz.
+ * Distributed under the Boost Software License, Version 1.0.
+ * (See accompanying file LICENSE_1_0.txt or copy at
+ * http://www.boost.org/LICENSE_1_0.txt)
+ *
+ * See http://www.boost.org/libs/multi_index for library home page.
+ */
+
+#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
+#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
+
+#if defined(_MSC_VER)&&(_MSC_VER>=1200)
+#pragma once
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/multi_index/detail/seq_index_node.hpp>
+#include <boost/limits.hpp>
+#include <boost/type_traits/aligned_storage.hpp>
+#include <boost/type_traits/alignment_of.hpp>
+#include <cstddef>
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+/* Common code for sequenced_index memfuns having templatized and
+ * non-templatized versions.
+ */
+
+template <typename SequencedIndex,typename Predicate>
+void sequenced_index_remove(SequencedIndex& x,Predicate pred)
+{
+ typedef typename SequencedIndex::iterator iterator;
+ iterator first=x.begin(),last=x.end();
+ while(first!=last){
+ if(pred(*first))x.erase(first++);
+ else ++first;
+ }
+}
+
+template <typename SequencedIndex,class BinaryPredicate>
+void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
+{
+ typedef typename SequencedIndex::iterator iterator;
+ iterator first=x.begin();
+ iterator last=x.end();
+ if(first!=last){
+ for(iterator middle=first;++middle!=last;middle=first){
+ if(binary_pred(*middle,*first))x.erase(middle);
+ else first=middle;
+ }
+ }
+}
+
+template <typename SequencedIndex,typename Compare>
+void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
+{
+ typedef typename SequencedIndex::iterator iterator;
+ if(&x!=&y){
+ iterator first0=x.begin(),last0=x.end();
+ iterator first1=y.begin(),last1=y.end();
+ while(first0!=last0&&first1!=last1){
+ if(comp(*first1,*first0))x.splice(first0,y,first1++);
+ else ++first0;
+ }
+ x.splice(last0,y,first1,last1);
+ }
+}
+
+/* sorting */
+
+/* auxiliary stuff */
+
+template<typename Node,typename Compare>
+void sequenced_index_collate(
+ BOOST_DEDUCED_TYPENAME Node::impl_type* x,
+ BOOST_DEDUCED_TYPENAME Node::impl_type* y,
+ Compare comp
+ BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
+{
+ typedef typename Node::impl_type impl_type;
+ typedef typename Node::impl_pointer impl_pointer;
+
+ impl_pointer first0=x->next();
+ impl_pointer last0=x;
+ impl_pointer first1=y->next();
+ impl_pointer last1=y;
+ while(first0!=last0&&first1!=last1){
+ if(comp(
+ Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
+ impl_pointer tmp=first1->next();
+ impl_type::relink(first0,first1);
+ first1=tmp;
+ }
+ else first0=first0->next();
+ }
+ impl_type::relink(last0,first1,last1);
+}
+
+/* Some versions of CGG require a bogus typename in counter_spc
+ * inside sequenced_index_sort if the following is defined
+ * also inside sequenced_index_sort.
+ */
+
+BOOST_STATIC_CONSTANT(
+ std::size_t,
+ sequenced_index_sort_max_fill=
+ (std::size_t)std::numeric_limits<std::size_t>::digits+1);
+
+template<typename Node,typename Compare>
+void sequenced_index_sort(Node* header,Compare comp)
+{
+ /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
+ * The implementation is a little convoluted: in the original code
+ * counter elements and carry are std::lists: here we do not want
+ * to use multi_index instead, so we do things at a lower level, managing
+ * directly the internal node representation.
+ * Incidentally, the implementations I've seen of this algorithm (SGI,
+ * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
+ * use any dynamic storage.
+ */
+
+ if(header->next()==header->impl()||
+ header->next()->next()==header->impl())return;
+
+ typedef typename Node::impl_type impl_type;
+ typedef typename Node::impl_pointer impl_pointer;
+
+ typedef typename aligned_storage<
+ sizeof(impl_type),
+ alignment_of<impl_type>::value
+ >::type carry_spc_type;
+ carry_spc_type carry_spc;
+ impl_type& carry=
+ *static_cast<impl_type*>(static_cast<void*>(&carry_spc));
+ typedef typename aligned_storage<
+ sizeof(
+ impl_type
+ [sequenced_index_sort_max_fill]),
+ alignment_of<
+ impl_type
+ [sequenced_index_sort_max_fill]
+ >::value
+ >::type counter_spc_type;
+ counter_spc_type counter_spc;
+ impl_type* counter=
+ static_cast<impl_type*>(static_cast<void*>(&counter_spc));
+ std::size_t fill=0;
+
+ carry.prior()=carry.next()=static_cast<impl_pointer>(&carry);
+ counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]);
+
+ BOOST_TRY{
+ while(header->next()!=header->impl()){
+ impl_type::relink(carry.next(),header->next());
+ std::size_t i=0;
+ while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){
+ sequenced_index_collate<Node>(&carry,&counter[i++],comp);
+ }
+ impl_type::swap(
+ static_cast<impl_pointer>(&carry),
+ static_cast<impl_pointer>(&counter[i]));
+ if(i==fill){
+ ++fill;
+ counter[fill].prior()=counter[fill].next()=
+ static_cast<impl_pointer>(&counter[fill]);
+ }
+ }
+
+ for(std::size_t i=1;i<fill;++i){
+ sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
+ }
+ impl_type::swap(
+ header->impl(),static_cast<impl_pointer>(&counter[fill-1]));
+ }
+ BOOST_CATCH(...)
+ {
+ impl_type::relink(
+ header->impl(),carry.next(),static_cast<impl_pointer>(&carry));
+ for(std::size_t i=0;i<=fill;++i){
+ impl_type::relink(
+ header->impl(),counter[i].next(),
+ static_cast<impl_pointer>(&counter[i]));
+ }
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+}
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#endif
projects / senf.git / blobdiff