multi_index/detail/index_saver.hpp

0001 /* Copyright 2003-2023 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <boost/multi_index/detail/index_matcher.hpp>
0018 #include <boost/core/noncopyable.hpp>
0019 #include <boost/core/serialization.hpp>
0020 #include <cstddef>
0021
0022 namespace boost{
0023
0024 namespace multi_index{
0025
0026 namespace detail{
0027
0028 /* index_saver accepts a base sequence of previously saved elements
0029  * and saves a possibly reordered subsequence in an efficient manner,
0030  * serializing only the information needed to rearrange the subsequence
0031  * based on the original order of the base.
0032  * multi_index_container is in charge of supplying the info about the
0033  * base sequence, and each index can subsequently save itself using the
0034  * const interface of index_saver.
0035  */
0036
0037 template<typename Node,typename Allocator>
0038 class index_saver:private noncopyable
0039 {
0040 public:
0041   index_saver(const Allocator& al,std::size_t size):alg(al,size){}
0042
0043   template<class Archive>
0044   void add(Node* node,Archive& ar,const unsigned int)
0045   {
0046     ar<<core::make_nvp("position",*node);
0047     alg.add(node);
0048   }
0049
0050   template<class Archive>
0051   void add_track(Node* node,Archive& ar,const unsigned int)
0052   {
0053     ar<<core::make_nvp("position",*node);
0054   }
0055
0056   template<typename IndexIterator,class Archive>
0057   void save(
0058     IndexIterator first,IndexIterator last,Archive& ar,
0059     const unsigned int)const
0060   {
0061     /* calculate ordered positions */
0062
0063     alg.execute(first,last);
0064
0065     /* Given a consecutive subsequence of displaced elements
0066      * x1,...,xn, the following information is serialized:
0067      *
0068      *   p0,p1,...,pn,0
0069      *
0070      * where pi is a pointer to xi and p0 is a pointer to the element
0071      * preceding x1. Crealy, from this information is possible to
0072      * restore the original order on loading time. If x1 is the first
0073      * element in the sequence, the following is serialized instead:
0074      *
0075      *   p1,p1,...,pn,0
0076      *
0077      * For each subsequence of n elements, n+2 pointers are serialized.
0078      * An optimization policy is applied: consider for instance the
0079      * sequence
0080      *
0081      *   a,B,c,D
0082      *
0083      * where B and D are displaced, but c is in its correct position.
0084      * Applying the schema described above we would serialize 6 pointers:
0085      *
0086      *  p(a),p(B),0
0087      *  p(c),p(D),0
0088      *
0089      * but this can be reduced to 5 pointers by treating c as a displaced
0090      * element:
0091      *
0092      *  p(a),p(B),p(c),p(D),0
0093      */
0094
0095     std::size_t last_saved=3; /* distance to last pointer saved */
0096     for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){
0097       if(!alg.is_ordered(get_node(it))){
0098         if(last_saved>1)save_node(get_node(prev),ar);
0099         save_node(get_node(it),ar);
0100         last_saved=0;
0101       }
0102       else if(last_saved==2)save_node(null_node(),ar);
0103     }
0104     if(last_saved<=2)save_node(null_node(),ar);
0105
0106     /* marks the end of the serialization info for [first,last) */
0107
0108     save_node(null_node(),ar);
0109   }
0110
0111 private:
0112   template<typename IndexIterator>
0113   static Node* get_node(IndexIterator it)
0114   {
0115     return it.get_node();
0116   }
0117
0118   static Node* null_node(){return 0;}
0119
0120   template<typename Archive>
0121   static void save_node(Node* node,Archive& ar)
0122   {
0123     ar<<core::make_nvp("pointer",node);
0124   }
0125
0126   index_matcher::algorithm<Node,Allocator> alg;
0127 };
0128
0129 } /* namespace multi_index::detail */
0130
0131 } /* namespace multi_index */
0132
0133 } /* namespace boost */
0134
0135 #endif