epoc32/include/stdapis/boost/multi_index/detail/index_saver.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-2005 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_INDEX_SAVER_HPP
    10 #define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_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 <boost/multi_index/detail/index_matcher.hpp>
    18 #include <boost/noncopyable.hpp>
    19 #include <boost/serialization/nvp.hpp>
    20 #include <cstddef>
    21 
    22 namespace boost{
    23 
    24 namespace multi_index{
    25 
    26 namespace detail{
    27 
    28 /* index_saver accepts a base sequence of previously saved elements
    29  * and saves a possibly reordered subsequence in an efficient manner,
    30  * serializing only the information needed to rearrange the subsequence
    31  * based on the original order of the base.
    32  * multi_index_container is in charge of supplying the info about the
    33  * base sequence, and each index can subsequently save itself using the
    34  * const interface of index_saver.
    35  */
    36 
    37 template<typename Node,typename Allocator>
    38 class index_saver:private noncopyable
    39 {
    40 public:
    41   index_saver(const Allocator& al,std::size_t size):alg(al,size){}
    42 
    43   template<class Archive>
    44   void add(Node* node,Archive& ar,const unsigned int)
    45   {
    46     ar<<serialization::make_nvp("position",*node);
    47     alg.add(node);
    48   }
    49 
    50   template<class Archive>
    51   void add_track(Node* node,Archive& ar,const unsigned int)
    52   {
    53     ar<<serialization::make_nvp("position",*node);
    54   }
    55 
    56   template<typename IndexIterator,class Archive>
    57   void save(
    58     IndexIterator first,IndexIterator last,Archive& ar,
    59     const unsigned int)const
    60   {
    61     /* calculate ordered positions */
    62 
    63     alg.execute(first,last);
    64 
    65     /* Given a consecutive subsequence of displaced elements
    66      * x1,...,xn, the following information is serialized:
    67      *
    68      *   p0,p1,...,pn,0
    69      *
    70      * where pi is a pointer to xi and p0 is a pointer to the element
    71      * preceding x1. Crealy, from this information is possible to
    72      * restore the original order on loading time. If x1 is the first
    73      * element in the sequence, the following is serialized instead:
    74      *
    75      *   p1,p1,...,pn,0
    76      *
    77      * For each subsequence of n elements, n+2 pointers are serialized.
    78      * An optimization policy is applied: consider for instance the
    79      * sequence
    80      *
    81      *   a,B,c,D
    82      * 
    83      * where B and D are displaced, but c is in its correct position.
    84      * Applying the schema described above we would serialize 6 pointers:
    85      *
    86      *  p(a),p(B),0
    87      *  p(c),p(D),0
    88      * 
    89      * but this can be reduced to 5 pointers by treating c as a displaced
    90      * element:
    91      *
    92      *  p(a),p(B),p(c),p(D),0
    93      */
    94 
    95     std::size_t last_saved=3; /* distance to last pointer saved */
    96     for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){
    97       if(!alg.is_ordered(get_node(it))){
    98         if(last_saved>1)save_node(get_node(prev),ar);
    99         save_node(get_node(it),ar);
   100         last_saved=0;
   101       }
   102       else if(last_saved==2)save_node(null_node(),ar);
   103     }
   104     if(last_saved<=2)save_node(null_node(),ar);
   105 
   106     /* marks the end of the serialization info for [first,last) */
   107 
   108     save_node(null_node(),ar);
   109   }
   110 
   111 private:
   112   template<typename IndexIterator>
   113   static Node* get_node(IndexIterator it)
   114   {
   115     return it.get_node();
   116   }
   117 
   118   static Node* null_node(){return 0;}
   119 
   120   template<typename Archive>
   121   static void save_node(Node* node,Archive& ar)
   122   {
   123     ar<<serialization::make_nvp("pointer",node);
   124   }
   125 
   126   index_matcher::algorithm<Node,Allocator> alg;
   127 };
   128 
   129 } /* namespace multi_index::detail */
   130 
   131 } /* namespace multi_index */
   132 
   133 } /* namespace boost */
   134 
   135 #endif