| /* Copyright 2003-2008 Joaquin M Lopez Munoz. |
| * Distributed under the Boost Software License, Version 1.0. |
| * (See accompanying file LICENSE_1_0.txt or copy at |
| * http://www.boost.org/LICENSE_1_0.txt) |
| * |
| * See http://www.boost.org/libs/multi_index for library home page. |
| */ |
| |
| #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP |
| #define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP |
| |
| #if defined(_MSC_VER)&&(_MSC_VER>=1200) |
| #pragma once |
| #endif |
| |
| #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
| #include <boost/multi_index/detail/index_matcher.hpp> |
| #include <boost/noncopyable.hpp> |
| #include <boost/serialization/nvp.hpp> |
| #include <cstddef> |
| |
| namespace boost{ |
| |
| namespace multi_index{ |
| |
| namespace detail{ |
| |
| /* index_saver accepts a base sequence of previously saved elements |
| * and saves a possibly reordered subsequence in an efficient manner, |
| * serializing only the information needed to rearrange the subsequence |
| * based on the original order of the base. |
| * multi_index_container is in charge of supplying the info about the |
| * base sequence, and each index can subsequently save itself using the |
| * const interface of index_saver. |
| */ |
| |
| template<typename Node,typename Allocator> |
| class index_saver:private noncopyable |
| { |
| public: |
| index_saver(const Allocator& al,std::size_t size):alg(al,size){} |
| |
| template<class Archive> |
| void add(Node* node,Archive& ar,const unsigned int) |
| { |
| ar<<serialization::make_nvp("position",*node); |
| alg.add(node); |
| } |
| |
| template<class Archive> |
| void add_track(Node* node,Archive& ar,const unsigned int) |
| { |
| ar<<serialization::make_nvp("position",*node); |
| } |
| |
| template<typename IndexIterator,class Archive> |
| void save( |
| IndexIterator first,IndexIterator last,Archive& ar, |
| const unsigned int)const |
| { |
| /* calculate ordered positions */ |
| |
| alg.execute(first,last); |
| |
| /* Given a consecutive subsequence of displaced elements |
| * x1,...,xn, the following information is serialized: |
| * |
| * p0,p1,...,pn,0 |
| * |
| * where pi is a pointer to xi and p0 is a pointer to the element |
| * preceding x1. Crealy, from this information is possible to |
| * restore the original order on loading time. If x1 is the first |
| * element in the sequence, the following is serialized instead: |
| * |
| * p1,p1,...,pn,0 |
| * |
| * For each subsequence of n elements, n+2 pointers are serialized. |
| * An optimization policy is applied: consider for instance the |
| * sequence |
| * |
| * a,B,c,D |
| * |
| * where B and D are displaced, but c is in its correct position. |
| * Applying the schema described above we would serialize 6 pointers: |
| * |
| * p(a),p(B),0 |
| * p(c),p(D),0 |
| * |
| * but this can be reduced to 5 pointers by treating c as a displaced |
| * element: |
| * |
| * p(a),p(B),p(c),p(D),0 |
| */ |
| |
| std::size_t last_saved=3; /* distance to last pointer saved */ |
| for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){ |
| if(!alg.is_ordered(get_node(it))){ |
| if(last_saved>1)save_node(get_node(prev),ar); |
| save_node(get_node(it),ar); |
| last_saved=0; |
| } |
| else if(last_saved==2)save_node(null_node(),ar); |
| } |
| if(last_saved<=2)save_node(null_node(),ar); |
| |
| /* marks the end of the serialization info for [first,last) */ |
| |
| save_node(null_node(),ar); |
| } |
| |
| private: |
| template<typename IndexIterator> |
| static Node* get_node(IndexIterator it) |
| { |
| return it.get_node(); |
| } |
| |
| static Node* null_node(){return 0;} |
| |
| template<typename Archive> |
| static void save_node(Node* node,Archive& ar) |
| { |
| ar<<serialization::make_nvp("pointer",node); |
| } |
| |
| index_matcher::algorithm<Node,Allocator> alg; |
| }; |
| |
| } /* namespace multi_index::detail */ |
| |
| } /* namespace multi_index */ |
| |
| } /* namespace boost */ |
| |
| #endif |