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