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 |
---|