/* 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 |