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