1 /* Copyright 2003-2013 Joaquin M Lopez Munoz. 2 * Distributed under the Boost Software License, Version 1.0. 3 * (See accompanying file LICENSE_1_0.txt or copy at 4 * http://www.boost.org/LICENSE_1_0.txt) 5 * 6 * See http://www.boost.org/libs/multi_index for library home page. 7 */ 8 9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP 10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_HPP 11 12 #if defined(_MSC_VER) 13 #pragma once 14 #endif 15 16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ 17 #include <algorithm> 18 #include <boost/detail/allocator_utilities.hpp> 19 #include <boost/multi_index/detail/auto_space.hpp> 20 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp> 21 #include <boost/noncopyable.hpp> 22 #include <cstddef> 23 24 namespace boost{ 25 26 namespace multi_index{ 27 28 namespace detail{ 29 30 /* This class implements a serialization rearranger for random access 31 * indices. In order to achieve O(n) performance, the following strategy 32 * is followed: the nodes of the index are handled as if in a bidirectional 33 * list, where the next pointers are stored in the original 34 * random_access_index_ptr_array and the prev pointers are stored in 35 * an auxiliary array. Rearranging of nodes in such a bidirectional list 36 * is constant time. Once all the arrangements are performed (on destruction 37 * time) the list is traversed in reverse order and 38 * pointers are swapped and set accordingly so that they recover its 39 * original semantics ( *(node->up())==node ) while retaining the 40 * new order. 41 */ 42 43 template<typename Allocator> 44 class random_access_index_loader_base:private noncopyable 45 { 46 protected: 47 typedef random_access_index_node_impl< 48 typename boost::detail::allocator::rebind_to< 49 Allocator, 50 char 51 >::type 52 > node_impl_type; 53 typedef typename node_impl_type::pointer node_impl_pointer; 54 typedef random_access_index_ptr_array<Allocator> ptr_array; 55 random_access_index_loader_base(const Allocator & al_,ptr_array & ptrs_)56 random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_): 57 al(al_), 58 ptrs(ptrs_), 59 header(*ptrs.end()), 60 prev_spc(al,0), 61 preprocessed(false) 62 {} 63 ~random_access_index_loader_base()64 ~random_access_index_loader_base() 65 { 66 if(preprocessed) 67 { 68 node_impl_pointer n=header; 69 next(n)=n; 70 71 for(std::size_t i=ptrs.size();i--;){ 72 n=prev(n); 73 std::size_t d=position(n); 74 if(d!=i){ 75 node_impl_pointer m=prev(next_at(i)); 76 std::swap(m->up(),n->up()); 77 next_at(d)=next_at(i); 78 std::swap(prev_at(d),prev_at(i)); 79 } 80 next(n)=n; 81 } 82 } 83 } 84 rearrange(node_impl_pointer position_,node_impl_pointer x)85 void rearrange(node_impl_pointer position_,node_impl_pointer x) 86 { 87 preprocess(); /* only incur this penalty if rearrange() is ever called */ 88 if(position_==node_impl_pointer(0))position_=header; 89 next(prev(x))=next(x); 90 prev(next(x))=prev(x); 91 prev(x)=position_; 92 next(x)=next(position_); 93 next(prev(x))=prev(next(x))=x; 94 } 95 96 private: preprocess()97 void preprocess() 98 { 99 if(!preprocessed){ 100 /* get space for the auxiliary prev array */ 101 auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1); 102 prev_spc.swap(tmp); 103 104 /* prev_spc elements point to the prev nodes */ 105 std::rotate_copy( 106 &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data()); 107 108 /* ptrs elements point to the next nodes */ 109 std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1); 110 111 preprocessed=true; 112 } 113 } 114 position(node_impl_pointer x) const115 std::size_t position(node_impl_pointer x)const 116 { 117 return (std::size_t)(x->up()-ptrs.begin()); 118 } 119 next_at(std::size_t n) const120 node_impl_pointer& next_at(std::size_t n)const 121 { 122 return *ptrs.at(n); 123 } 124 prev_at(std::size_t n) const125 node_impl_pointer& prev_at(std::size_t n)const 126 { 127 return *(prev_spc.data()+n); 128 } 129 next(node_impl_pointer x) const130 node_impl_pointer& next(node_impl_pointer x)const 131 { 132 return *(x->up()); 133 } 134 prev(node_impl_pointer x) const135 node_impl_pointer& prev(node_impl_pointer x)const 136 { 137 return prev_at(position(x)); 138 } 139 140 Allocator al; 141 ptr_array& ptrs; 142 node_impl_pointer header; 143 auto_space<node_impl_pointer,Allocator> prev_spc; 144 bool preprocessed; 145 }; 146 147 template<typename Node,typename Allocator> 148 class random_access_index_loader: 149 private random_access_index_loader_base<Allocator> 150 { 151 typedef random_access_index_loader_base<Allocator> super; 152 typedef typename super::node_impl_pointer node_impl_pointer; 153 typedef typename super::ptr_array ptr_array; 154 155 public: random_access_index_loader(const Allocator & al_,ptr_array & ptrs_)156 random_access_index_loader(const Allocator& al_,ptr_array& ptrs_): 157 super(al_,ptrs_) 158 {} 159 rearrange(Node * position_,Node * x)160 void rearrange(Node* position_,Node *x) 161 { 162 super::rearrange( 163 position_?position_->impl():node_impl_pointer(0),x->impl()); 164 } 165 }; 166 167 } /* namespace multi_index::detail */ 168 169 } /* namespace multi_index */ 170 171 } /* namespace boost */ 172 173 #endif 174