1/* Copyright 2003-2023 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/core/noncopyable.hpp>
19#include <boost/core/serialization.hpp>
20#include <cstddef>
21
22namespace boost{
23
24namespace multi_index{
25
26namespace 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
37template<typename Node,typename Allocator>
38class index_saver:private noncopyable
39{
40public:
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<<core::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<<core::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
111private:
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<<core::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