diff options
author | Remko Tronçon <git@el-tramo.be> | 2011-03-11 20:22:35 (GMT) |
---|---|---|
committer | Remko Tronçon <git@el-tramo.be> | 2011-03-11 22:22:04 (GMT) |
commit | 59aa5d7e29ca142ae324ad97e6a5f0353d1a6b89 (patch) | |
tree | e450b95ff4c0ba7f770723402a2634773f1a0451 /3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp | |
parent | 3ff52013d810f94b6095e93f550f58133e2df239 (diff) | |
download | swift-contrib-59aa5d7e29ca142ae324ad97e6a5f0353d1a6b89.zip swift-contrib-59aa5d7e29ca142ae324ad97e6a5f0353d1a6b89.tar.bz2 |
Store JID->Avatar mappings.
Resolves: #653
Diffstat (limited to '3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp new file mode 100644 index 0000000..8135074 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp @@ -0,0 +1,200 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * 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 |