]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |