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:
index_saver(const Allocator & al,std::size_t size)41   index_saver(const Allocator& al,std::size_t size):alg(al,size){}
42 
43   template<class Archive>
add(Node * node,Archive & ar,const unsigned int)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>
add_track(Node * node,Archive & ar,const unsigned int)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>
save(IndexIterator first,IndexIterator last,Archive & ar,const unsigned int) const57   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>
get_node(IndexIterator it)113   static Node* get_node(IndexIterator it)
114   {
115     return it.get_node();
116   }
117 
null_node()118   static Node* null_node(){return 0;}
119 
120   template<typename Archive>
save_node(Node * node,Archive & ar)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
136