boost/multi_index/detail/index_saver.hpp

   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_INDEX_SAVER_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_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 <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