X-Git-Url: http://g0dil.de/git?a=blobdiff_plain;f=boost_ext%2Fboost%2Fmulti_index%2Fdetail%2Frnd_index_loader.hpp;fp=boost_ext%2Fboost%2Fmulti_index%2Fdetail%2Frnd_index_loader.hpp;h=69ec8b73abbfd1b952c16d625021e9e4e184422e;hb=4123b4fe58a7fd4659fa01476581690b47c83600;hp=0000000000000000000000000000000000000000;hpb=79564b90f6c9f7cd0bc5b11a6146bb7067b11a75;p=senf.git

diff --git a/boost_ext/boost/multi_index/detail/rnd_index_loader.hpp b/boost_ext/boost/multi_index/detail/rnd_index_loader.hpp
new file mode 100644
index 0000000..69ec8b7
--- /dev/null
+++ b/boost_ext/boost/multi_index/detail/rnd_index_loader.hpp
@@ -0,0 +1,176 @@
+/* Copyright 2003-2007 Joaquín M López Muñoz.
+ * 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_RND_INDEX_LOADER_HPP
+#define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_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 <algorithm>
+#include <boost/detail/allocator_utilities.hpp>
+#include <boost/multi_index/detail/auto_space.hpp>
+#include <boost/multi_index/detail/prevent_eti.hpp>
+#include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
+#include <boost/noncopyable.hpp>
+#include <cstddef>
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+/* This class implements a serialization rearranger for random access
+ * indices. In order to achieve O(n) performance, the following strategy
+ * is followed: the nodes of the index are handled as if in a bidirectional
+ * list, where the next pointers are stored in the original
+ * random_access_index_ptr_array and the prev pointers are stored in
+ * an auxiliary array. Rearranging of nodes in such a bidirectional list
+ * is constant time. Once all the arrangements are performed (on destruction
+ * time) the list is traversed in reverse order and
+ * pointers are swapped and set accordingly so that they recover its
+ * original semantics ( *(node->up())==node ) while retaining the
+ * new order.
+ */
+
+template<typename Allocator>
+class random_access_index_loader_base:private noncopyable
+{
+protected:
+  typedef typename prevent_eti<
+    Allocator,
+    random_access_index_node_impl<
+      typename boost::detail::allocator::rebind_to<
+        Allocator,
+        void
+      >::type
+    >
+  >::type                                           node_impl_type;
+  typedef typename node_impl_type::pointer          node_impl_pointer;
+  typedef random_access_index_ptr_array<Allocator>  ptr_array;
+
+  random_access_index_loader_base(const Allocator& al_,ptr_array& ptrs_):
+    al(al_),
+    ptrs(ptrs_),
+    header(*ptrs.end()),
+    prev_spc(al,0),
+    preprocessed(false)
+  {}
+
+  ~random_access_index_loader_base()
+  {
+    if(preprocessed)
+    {
+      node_impl_pointer n=header;
+      next(n)=n;
+
+      for(std::size_t i=ptrs.size();i--;){
+        n=prev(n);
+        std::size_t d=position(n);
+        if(d!=i){
+          node_impl_pointer m=prev(next_at(i));
+          std::swap(m->up(),n->up());
+          next_at(d)=next_at(i);
+          std::swap(prev_at(d),prev_at(i));
+        }
+        next(n)=n;
+      }
+    }
+  }
+
+  void rearrange(node_impl_pointer position,node_impl_pointer x)
+  {
+    preprocess(); /* only incur this penalty if rearrange() is ever called */
+    if(position==node_impl_pointer(0))position=header;
+    next(prev(x))=next(x);
+    prev(next(x))=prev(x);
+    prev(x)=position;
+    next(x)=next(position);
+    next(prev(x))=prev(next(x))=x;
+  }
+
+private:
+  void preprocess()
+  {
+    if(!preprocessed){
+      /* get space for the auxiliary prev array */
+      auto_space<node_impl_pointer,Allocator> tmp(al,ptrs.size()+1);
+      prev_spc.swap(tmp);
+
+      /* prev_spc elements point to the prev nodes */
+      std::rotate_copy(
+        &*ptrs.begin(),&*ptrs.end(),&*ptrs.end()+1,&*prev_spc.data());
+
+      /* ptrs elements point to the next nodes */
+      std::rotate(&*ptrs.begin(),&*ptrs.begin()+1,&*ptrs.end()+1);
+
+      preprocessed=true;
+    }
+  }
+
+  std::size_t position(node_impl_pointer x)const
+  {
+    return (std::size_t)(x->up()-ptrs.begin());
+  }
+
+  node_impl_pointer& next_at(std::size_t n)const
+  {
+    return *ptrs.at(n);
+  }
+
+  node_impl_pointer& prev_at(std::size_t n)const
+  {
+    return *(prev_spc.data()+n);
+  }
+
+  node_impl_pointer& next(node_impl_pointer x)const
+  {
+    return *(x->up());
+  }
+
+  node_impl_pointer& prev(node_impl_pointer x)const
+  {
+    return prev_at(position(x));
+  }
+
+  Allocator                               al;
+  ptr_array&                              ptrs;
+  node_impl_pointer                       header;
+  auto_space<node_impl_pointer,Allocator> prev_spc;
+  bool                                    preprocessed;
+};
+
+template<typename Node,typename Allocator>
+class random_access_index_loader:
+  private random_access_index_loader_base<Allocator>
+{
+  typedef random_access_index_loader_base<Allocator> super;
+  typedef typename super::node_impl_pointer          node_impl_pointer;
+  typedef typename super::ptr_array                  ptr_array;
+
+public:
+  random_access_index_loader(const Allocator& al_,ptr_array& ptrs_):
+    super(al_,ptrs_)
+  {}
+
+  void rearrange(Node* position,Node *x)
+  {
+    super::rearrange(position?position->impl():node_impl_pointer(0),x->impl());
+  }
+};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#endif