epoc32/include/stdapis/boost/multi_index/detail/rnd_index_loader.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
     1 /* Copyright 2003-2006 Joaquín M López Muñoz.
     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)&&(_MSC_VER>=1200)
    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/multi_index/detail/auto_space.hpp>
    19 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
    20 #include <boost/noncopyable.hpp>
    21 #include <cstddef>
    22 
    23 namespace boost{
    24 
    25 namespace multi_index{
    26 
    27 namespace detail{
    28 
    29 /* This class implements a serialization rearranger for random access
    30  * indices. In order to achieve O(n) performance, the following strategy
    31  * is followed: the nodes of the index are handled as if in a bidirectional
    32  * list, where the next pointers are stored in the original
    33  * random_access_index_ptr_array and the prev pointers are stored in
    34  * an auxiliary array. Rearranging of nodes in such a bidirectional list
    35  * is constant time. Once all the arrangements are performed (on destruction
    36  * time) the list is traversed in reverse order and
    37  * pointers are swapped and set accordingly so that they recover its
    38  * original semantics ( *(node->up())==node ) while retaining the
    39  * new order.
    40  */
    41 
    42 template<typename Allocator>
    43 class random_access_index_loader_base:private noncopyable
    44 {
    45 protected:
    46   typedef random_access_index_node_impl            node_type;
    47   typedef random_access_index_ptr_array<Allocator> ptr_array_type;
    48 
    49   random_access_index_loader_base(const Allocator& al_,ptr_array_type& ptrs_):
    50     al(al_),
    51     ptrs(ptrs_),
    52     header(*ptrs.end()),
    53     prev_spc(al,0),
    54     preprocessed(false)
    55   {}
    56 
    57   ~random_access_index_loader_base()
    58   {
    59     if(preprocessed)
    60     {
    61       node_type* n=header;
    62       next(n)=n;
    63 
    64       for(std::size_t i=ptrs.size();i--;){
    65         n=prev(n);
    66         std::size_t d=position(n);
    67         if(d!=i){
    68           node_type* m=prev(next_at(i));
    69           std::swap(m->up(),n->up());
    70           next_at(d)=next_at(i);
    71           std::swap(prev_at(d),prev_at(i));
    72         }
    73         next(n)=n;
    74       }
    75     }
    76   }
    77 
    78   void rearrange(node_type* position,node_type *x)
    79   {
    80     preprocess(); /* only incur this penalty if rearrange() is ever called */
    81     if(!position)position=header;
    82     next(prev(x))=next(x);
    83     prev(next(x))=prev(x);
    84     prev(x)=position;
    85     next(x)=next(position);
    86     next(prev(x))=prev(next(x))=x;
    87   }
    88 
    89 private:
    90   void preprocess()
    91   {
    92     if(!preprocessed){
    93       /* get space for the auxiliary prev array */
    94       auto_space<node_type*,Allocator> tmp(al,ptrs.size()+1);
    95       prev_spc.swap(tmp);
    96 
    97       /* prev_spc elements point to the prev nodes */
    98       std::rotate_copy(ptrs.begin(),ptrs.end(),ptrs.end()+1,prev_spc.data());
    99 
   100       /* ptrs elements point to the next nodes */
   101       std::rotate(ptrs.begin(),ptrs.begin()+1,ptrs.end()+1);
   102 
   103       preprocessed=true;
   104     }
   105   }
   106 
   107   std::size_t position(node_type* x)const
   108   {
   109     return (std::size_t)(x->up()-ptrs.begin());
   110   }
   111 
   112   node_type*& next_at(std::size_t n)const
   113   {
   114     return *ptrs.at(n);
   115   }
   116 
   117   node_type*& prev_at(std::size_t n)const
   118   {
   119     return prev_spc.data()[n];
   120   }
   121 
   122   node_type*& next(node_type* x)const
   123   {
   124     return *(x->up());
   125   }
   126 
   127   node_type*& prev(node_type* x)const
   128   {
   129     return prev_at(position(x));
   130   }
   131 
   132   Allocator                        al;
   133   ptr_array_type&                  ptrs;
   134   node_type*                       header;
   135   auto_space<node_type*,Allocator> prev_spc;
   136   bool                             preprocessed;
   137 };
   138 
   139 template<typename Node,typename Allocator>
   140 class random_access_index_loader:
   141   private random_access_index_loader_base<Allocator>
   142 {
   143   typedef random_access_index_loader_base<Allocator> super;
   144   typedef typename super::ptr_array_type             ptr_array_type;
   145 
   146 public:
   147   random_access_index_loader(const Allocator& al_,ptr_array_type& ptrs_):
   148     super(al_,ptrs_)
   149   {}
   150 
   151   void rearrange(Node* position,Node *x)
   152   {
   153     super::rearrange(position?position->impl():0,x->impl());
   154   }
   155 };
   156 
   157 } /* namespace multi_index::detail */
   158 
   159 } /* namespace multi_index */
   160 
   161 } /* namespace boost */
   162 
   163 #endif