Chris@101: /* Copyright 2003-2014 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <boost/detail/allocator_utilities.hpp>
Chris@101: #include <utility>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@101: /* Certain C++ requirements on unordered associative containers (see LWG issue
Chris@101:  * #579) imply a data structure where nodes are linked in a single list, which
Chris@101:  * in its turn forces implementors to add additional overhed per node to
Chris@101:  * associate each with its corresponding bucket. Others resort to storing hash
Chris@101:  * values, we use an alternative structure providing unconditional O(1)
Chris@101:  * manipulation, even in situations of unfair hash distribution, plus some
Chris@101:  * lookup speedups. For unique indices we maintain a doubly linked list of
Chris@101:  * nodes except that if N is the first node of a bucket its associated
Chris@101:  * bucket node is embedded between N and the preceding node in the following
Chris@101:  * manner:
Chris@101:  *
Chris@101:  *        +---+   +---+       +---+   +---+
Chris@101:  *     <--+   |<--+   |    <--+   |<--+   |
Chris@101:  *   ...  | B0|   | B1|  ...  | B1|   | B2|  ...
Chris@101:  *        |   |-+ |   +-->    |   |-+ |   +-->
Chris@101:  *        +-+-+ | +---+       +-+-+ | +---+
Chris@101:  *              |   ^               |   ^
Chris@101:  *              |   |               |   |
Chris@101:  *              | +-+               | +-+
Chris@101:  *              | |                 | |
Chris@101:  *              v |                 v |  
Chris@101:  *       --+---+---+---+--   --+---+---+---+--
Chris@101:  *     ... |   | B1|   |  ...  |   | B2|   | ...
Chris@101:  *       --+---+---+---+--   --+---+---+---+--
Chris@101:  *
Chris@101:  *
Chris@101:  * The fist and last nodes of buckets can be checked with
Chris@101:  *
Chris@101:  *   first node of a bucket: Npn != N
Chris@101:  *   last node of a bucket:  Nnp != N
Chris@101:  *
Chris@101:  * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers
Chris@101:  * only). Pure insert and erase (without lookup) can be unconditionally done
Chris@101:  * in O(1).
Chris@101:  * For non-unique indices we add the following additional complexity: when
Chris@101:  * there is a group of 3 or more equivalent elements, they are linked as
Chris@101:  * follows:
Chris@101:  *
Chris@101:  *         +-----------------------+
Chris@101:  *         |                       v
Chris@101:  *   +---+ | +---+       +---+   +---+
Chris@101:  *   |   | +-+   |       |   |<--+   |
Chris@101:  *   | F |   | S |  ...  | P |   | L |
Chris@101:  *   |   +-->|   |       |   +-+ |   |
Chris@101:  *   +---+   +---+       +---+ | +---+
Chris@101:  *     ^                       |
Chris@101:  *     +-----------------------+
Chris@101:  * 
Chris@101:  * F, S, P and L are the first, second, penultimate and last node in the
Chris@101:  * group, respectively (S and P can coincide if the group has size 3.) This
Chris@101:  * arrangement is used to skip equivalent elements in O(1) when doing lookup,
Chris@101:  * while preserving O(1) insert/erase. The following invariants identify
Chris@101:  * special positions (some of the operations have to be carefully implemented
Chris@101:  * as Xnn is not valid if Xn points to a bucket):
Chris@101:  *
Chris@101:  *   first node of a bucket: Npnp  == N
Chris@101:  *   last node of a bucket:  Nnpp  == N
Chris@101:  *   first node of a group:  Nnp != N && Nnppn == N
Chris@101:  *   second node of a group: Npn != N && Nppnn == N
Chris@101:  *   n-1 node of a group:    Nnp != N && Nnnpp == N
Chris@101:  *   last node of a group:   Npn != N && Npnnp == N
Chris@101:  * 
Chris@101:  * The memory overhead is one pointer per bucket plus two pointers per node,
Chris@101:  * probably unbeatable. The resulting structure is bidirectonally traversable,
Chris@101:  * though currently we are just providing forward iteration.
Chris@101:  */
Chris@16: 
Chris@16: template<typename Allocator>
Chris@101: struct hashed_index_node_impl;
Chris@101: 
Chris@101: /* half-header (only prior() pointer) to use for the bucket array */
Chris@101: 
Chris@101: template<typename Allocator>
Chris@101: struct hashed_index_base_node_impl
Chris@16: {
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:       Allocator,hashed_index_base_node_impl
Chris@101:   >::type::pointer                          base_pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,hashed_index_base_node_impl
Chris@101:   >::type::const_pointer                    const_base_pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@16:     Allocator,
Chris@101:     hashed_index_node_impl<Allocator>
Chris@101:   >::type::pointer                          pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@16:     Allocator,
Chris@101:     hashed_index_node_impl<Allocator>
Chris@101:   >::type::const_pointer                    const_pointer;
Chris@16: 
Chris@101:   pointer& prior(){return prior_;}
Chris@101:   pointer  prior()const{return prior_;}
Chris@16: 
Chris@101: private:
Chris@101:   pointer prior_;
Chris@101: };
Chris@16: 
Chris@101: /* full header (prior() and next()) for the nodes */
Chris@101: 
Chris@101: template<typename Allocator>
Chris@101: struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
Chris@101: {
Chris@101: private:
Chris@101:   typedef hashed_index_base_node_impl<Allocator> super;
Chris@101: 
Chris@101: public:  
Chris@101:   typedef typename super::base_pointer           base_pointer;
Chris@101:   typedef typename super::const_base_pointer     const_base_pointer;
Chris@101:   typedef typename super::pointer                pointer;
Chris@101:   typedef typename super::const_pointer          const_pointer;
Chris@101: 
Chris@101:   base_pointer& next(){return next_;}
Chris@101:   base_pointer  next()const{return next_;}
Chris@101: 
Chris@101:   static pointer pointer_from(base_pointer x)
Chris@16:   {
Chris@101:     return static_cast<pointer>(static_cast<hashed_index_node_impl*>(&*x));
Chris@101:   }
Chris@16: 
Chris@101:   static base_pointer base_pointer_from(pointer x)
Chris@101:   {
Chris@101:     return static_cast<base_pointer>(&*x);
Chris@101:   }
Chris@101: 
Chris@101: private:
Chris@101:   base_pointer next_;
Chris@101: };
Chris@101: 
Chris@101: /* Boost.MultiIndex requires machinery to reverse unlink operations. A simple
Chris@101:  * way to make a pointer-manipulation function undoable is to templatize
Chris@101:  * its internal pointer assignments with a functor that, besides doing the
Chris@101:  * assignment, keeps track of the original pointer values and can later undo
Chris@101:  * the operations in reverse order.
Chris@101:  */
Chris@101: 
Chris@101: struct default_assigner
Chris@101: {
Chris@101:   template<typename T> void operator()(T& x,const T& val){x=val;}
Chris@101: };
Chris@101: 
Chris@101: template<typename Node>
Chris@101: struct unlink_undo_assigner
Chris@101: {
Chris@101:   typedef typename Node::base_pointer base_pointer;
Chris@101:   typedef typename Node::pointer      pointer;
Chris@101: 
Chris@101:   unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){}
Chris@101: 
Chris@101:   void operator()(pointer& x,pointer val)
Chris@101:   {
Chris@101:     pointer_tracks[pointer_track_count].x=&x;
Chris@101:     pointer_tracks[pointer_track_count++].val=x;
Chris@101:     x=val;
Chris@101:   }
Chris@101: 
Chris@101:   void operator()(base_pointer& x,base_pointer val)
Chris@101:   {
Chris@101:     base_pointer_tracks[base_pointer_track_count].x=&x;
Chris@101:     base_pointer_tracks[base_pointer_track_count++].val=x;
Chris@101:     x=val;
Chris@101:   }
Chris@101: 
Chris@101:   void operator()() /* undo op */
Chris@101:   {
Chris@101:     /* in the absence of aliasing, restitution order is immaterial */
Chris@101: 
Chris@101:     while(pointer_track_count--){
Chris@101:       *(pointer_tracks[pointer_track_count].x)=
Chris@101:         pointer_tracks[pointer_track_count].val;
Chris@101:     }
Chris@101:     while(base_pointer_track_count--){
Chris@101:       *(base_pointer_tracks[base_pointer_track_count].x)=
Chris@101:         base_pointer_tracks[base_pointer_track_count].val;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@101:   struct pointer_track     {pointer*      x; pointer      val;};
Chris@101:   struct base_pointer_track{base_pointer* x; base_pointer val;};
Chris@101: 
Chris@101:   /* We know the maximum number of pointer and base pointer assignments that
Chris@101:    * the two unlink versions do, so we can statically reserve the needed
Chris@101:    * storage.
Chris@101:    */
Chris@101: 
Chris@101:   pointer_track      pointer_tracks[3];
Chris@101:   int                pointer_track_count;
Chris@101:   base_pointer_track base_pointer_tracks[2];
Chris@101:   int                base_pointer_track_count;
Chris@101: };
Chris@101: 
Chris@101: /* algorithmic stuff for unique and non-unique variants */
Chris@101: 
Chris@101: struct hashed_unique_tag{};
Chris@101: struct hashed_non_unique_tag{};
Chris@101: 
Chris@101: template<typename Node,typename Category>
Chris@101: struct hashed_index_node_alg;
Chris@101: 
Chris@101: template<typename Node>
Chris@101: struct hashed_index_node_alg<Node,hashed_unique_tag>
Chris@101: {
Chris@101:   typedef typename Node::base_pointer       base_pointer;
Chris@101:   typedef typename Node::const_base_pointer const_base_pointer;
Chris@101:   typedef typename Node::pointer            pointer;
Chris@101:   typedef typename Node::const_pointer      const_pointer;
Chris@101: 
Chris@101:   static bool is_first_of_bucket(pointer x)
Chris@16:   {
Chris@101:     return x->prior()->next()!=base_pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static pointer after(pointer x)
Chris@101:   {
Chris@101:     return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next());
Chris@101:   }
Chris@101: 
Chris@101:   static pointer after_local(pointer x)
Chris@101:   {
Chris@101:     return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
Chris@101:   }
Chris@101: 
Chris@101:   static pointer next_to_inspect(pointer x)
Chris@101:   {
Chris@101:     return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
Chris@101:   }
Chris@101: 
Chris@101:   static void link(pointer x,base_pointer buc,pointer end)
Chris@101:   {
Chris@101:     if(buc->prior()==pointer(0)){ /* empty bucket */
Chris@101:       x->prior()=end->prior();
Chris@101:       x->next()=end->prior()->next();
Chris@101:       x->prior()->next()=buc;
Chris@101:       buc->prior()=x;
Chris@101:       end->prior()=x;
Chris@101:     }
Chris@101:     else{
Chris@101:       x->prior()=buc->prior()->prior();
Chris@101:       x->next()=base_pointer_from(buc->prior());
Chris@101:       buc->prior()=x;
Chris@101:       x->next()->prior()=x;
Chris@101:     }
Chris@101:   }
Chris@16: 
Chris@16:   static void unlink(pointer x)
Chris@16:   {
Chris@101:     default_assigner assign;
Chris@101:     unlink(x,assign);
Chris@16:   }
Chris@16: 
Chris@101:   typedef unlink_undo_assigner<Node> unlink_undo;
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void unlink(pointer x,Assigner& assign)
Chris@16:   {
Chris@101:     if(is_first_of_bucket(x)){
Chris@101:       if(is_last_of_bucket(x)){
Chris@101:         assign(x->prior()->next()->prior(),pointer(0));
Chris@101:         assign(x->prior()->next(),x->next());
Chris@101:         assign(x->next()->prior()->prior(),x->prior());
Chris@101:       }
Chris@101:       else{
Chris@101:         assign(x->prior()->next()->prior(),pointer_from(x->next()));
Chris@101:         assign(x->next()->prior(),x->prior());
Chris@101:       }
Chris@101:     }
Chris@101:     else if(is_last_of_bucket(x)){
Chris@101:       assign(x->prior()->next(),x->next());
Chris@101:       assign(x->next()->prior()->prior(),x->prior());
Chris@101:     }
Chris@101:     else{
Chris@101:       assign(x->prior()->next(),x->next());
Chris@101:       assign(x->next()->prior(),x->prior());
Chris@101:     }
Chris@16:   }
Chris@16: 
Chris@101:   /* used only at rehashing */
Chris@101: 
Chris@101:   static void append(pointer x,pointer end)
Chris@16:   {
Chris@101:     x->prior()=end->prior();
Chris@101:     x->next()=end->prior()->next();
Chris@101:     x->prior()->next()=base_pointer_from(x);
Chris@101:     end->prior()=x;
Chris@101:   }
Chris@101: 
Chris@101:   static bool unlink_last(pointer end)
Chris@101:   {
Chris@101:     /* returns true iff bucket is emptied */
Chris@101: 
Chris@101:     pointer x=end->prior();
Chris@101:     if(x->prior()->next()==base_pointer_from(x)){
Chris@101:       x->prior()->next()=x->next();
Chris@101:       end->prior()=x->prior();
Chris@101:       return false;
Chris@101:     }
Chris@101:     else{
Chris@101:       x->prior()->next()->prior()=pointer(0);
Chris@101:       x->prior()->next()=x->next();
Chris@101:       end->prior()=x->prior();
Chris@101:       return true;
Chris@101:     }
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@101:   static pointer pointer_from(base_pointer x)
Chris@101:   {
Chris@101:     return Node::pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static base_pointer base_pointer_from(pointer x)
Chris@101:   {
Chris@101:     return Node::base_pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static bool is_last_of_bucket(pointer x)
Chris@101:   {
Chris@101:     return x->next()->prior()!=x;
Chris@101:   }
Chris@101: };
Chris@101: 
Chris@101: template<typename Node>
Chris@101: struct hashed_index_node_alg<Node,hashed_non_unique_tag>
Chris@101: {
Chris@101:   typedef typename Node::base_pointer       base_pointer;
Chris@101:   typedef typename Node::const_base_pointer const_base_pointer;
Chris@101:   typedef typename Node::pointer            pointer;
Chris@101:   typedef typename Node::const_pointer      const_pointer;
Chris@101: 
Chris@101:   static bool is_first_of_bucket(pointer x)
Chris@101:   {
Chris@101:     return x->prior()->next()->prior()==x;
Chris@101:   }
Chris@101: 
Chris@101:   static bool is_first_of_group(pointer x)
Chris@101:   {
Chris@101:     return
Chris@101:       x->next()->prior()!=x&&
Chris@101:       x->next()->prior()->prior()->next()==base_pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static pointer after(pointer x)
Chris@101:   {
Chris@101:     if(x->next()->prior()==x)return pointer_from(x->next());
Chris@101:     if(x->next()->prior()->prior()==x)return x->next()->prior();
Chris@101:     if(x->next()->prior()->prior()->next()==base_pointer_from(x))
Chris@101:       return pointer_from(x->next());
Chris@101:     return pointer_from(x->next())->next()->prior();
Chris@101:   }
Chris@101: 
Chris@101:   static pointer after_local(pointer x)
Chris@101:   {
Chris@101:     if(x->next()->prior()==x)return pointer_from(x->next());
Chris@101:     if(x->next()->prior()->prior()==x)return pointer(0);
Chris@101:     if(x->next()->prior()->prior()->next()==base_pointer_from(x))
Chris@101:       return pointer_from(x->next());
Chris@101:     return pointer_from(x->next())->next()->prior();
Chris@101:   }
Chris@101: 
Chris@101:   static pointer next_to_inspect(pointer x)
Chris@101:   {
Chris@101:     if(x->next()->prior()==x)return pointer_from(x->next());
Chris@101:     if(x->next()->prior()->prior()==x)return pointer(0);
Chris@101:     if(x->next()->prior()->next()->prior()!=x->next()->prior())
Chris@101:       return pointer(0);
Chris@101:     return pointer_from(x->next()->prior()->next());
Chris@101:   }
Chris@101: 
Chris@101:   static void link(pointer x,base_pointer buc,pointer end)
Chris@101:   {
Chris@101:     if(buc->prior()==pointer(0)){ /* empty bucket */
Chris@101:       x->prior()=end->prior();
Chris@101:       x->next()=end->prior()->next();
Chris@101:       x->prior()->next()=buc;
Chris@101:       buc->prior()=x;
Chris@101:       end->prior()=x;
Chris@101:     }
Chris@101:     else{
Chris@101:       x->prior()=buc->prior()->prior();
Chris@101:       x->next()=base_pointer_from(buc->prior());
Chris@101:       buc->prior()=x;
Chris@101:       x->next()->prior()=x;
Chris@101:     }
Chris@101:   };
Chris@101: 
Chris@101:   static void link(pointer x,pointer first,pointer last)
Chris@101:   {
Chris@101:     x->prior()=first->prior();
Chris@101:     x->next()=base_pointer_from(first);
Chris@101:     if(is_first_of_bucket(first)){
Chris@101:       x->prior()->next()->prior()=x;
Chris@101:     }
Chris@101:     else{
Chris@101:       x->prior()->next()=base_pointer_from(x);
Chris@101:     }
Chris@101: 
Chris@101:     if(first==last){
Chris@101:       last->prior()=x;
Chris@101:     }
Chris@101:     else if(first->next()==base_pointer_from(last)){
Chris@101:       first->prior()=last;
Chris@101:       first->next()=base_pointer_from(x);
Chris@101:     }
Chris@101:     else{
Chris@101:       pointer second=pointer_from(first->next()),
Chris@101:               lastbutone=last->prior();
Chris@101:       second->prior()=first;
Chris@101:       first->prior()=last;
Chris@101:       lastbutone->next()=base_pointer_from(x);
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   static void unlink(pointer x)
Chris@101:   {
Chris@101:     default_assigner assign;
Chris@101:     unlink(x,assign);
Chris@101:   }
Chris@101: 
Chris@101:   typedef unlink_undo_assigner<Node> unlink_undo;
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void unlink(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     if(x->prior()->next()==base_pointer_from(x)){
Chris@101:       if(x->next()->prior()==x){
Chris@101:         left_unlink(x,assign);
Chris@101:         right_unlink(x,assign);
Chris@101:       }
Chris@101:       else if(x->next()->prior()->prior()==x){           /* last of bucket */
Chris@101:         left_unlink(x,assign);
Chris@101:         right_unlink_last_of_bucket(x,assign);
Chris@101:       }
Chris@101:       else if(x->next()->prior()->prior()->next()==
Chris@101:               base_pointer_from(x)){                /* first of group size */
Chris@101:         left_unlink(x,assign);
Chris@101:         right_unlink_first_of_group(x,assign);
Chris@101:       }
Chris@101:       else{                                                /* n-1 of group */
Chris@101:         unlink_last_but_one_of_group(x,assign);
Chris@101:       }
Chris@101:     }
Chris@101:     else if(x->prior()->next()->prior()==x){            /* first of bucket */
Chris@101:       if(x->next()->prior()==x){
Chris@101:         left_unlink_first_of_bucket(x,assign);
Chris@101:         right_unlink(x,assign);
Chris@101:       }
Chris@101:       else if(x->next()->prior()->prior()==x){           /* last of bucket */
Chris@101:         assign(x->prior()->next()->prior(),pointer(0));
Chris@101:         assign(x->prior()->next(),x->next());
Chris@101:         assign(x->next()->prior()->prior(),x->prior());
Chris@101:       }
Chris@101:       else{                                              /* first of group */
Chris@101:         left_unlink_first_of_bucket(x,assign);
Chris@101:         right_unlink_first_of_group(x,assign);
Chris@101:       }
Chris@101:     }
Chris@101:     else if(x->next()->prior()->prior()==x){   /* last of group and bucket */
Chris@101:       left_unlink_last_of_group(x,assign);
Chris@101:       right_unlink_last_of_bucket(x,assign);
Chris@101:     }
Chris@101:     else if(pointer_from(x->prior()->prior()->next())
Chris@101:             ->next()==base_pointer_from(x)){            /* second of group */
Chris@101:       unlink_second_of_group(x,assign);
Chris@101:     }
Chris@101:     else{                              /* last of group, ~(last of bucket) */
Chris@101:       left_unlink_last_of_group(x,assign);
Chris@101:       right_unlink(x,assign);
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   /* used only at rehashing */
Chris@101: 
Chris@101:   static void link_range(
Chris@101:     pointer first,pointer last,base_pointer buc,pointer cend)
Chris@101:   {
Chris@101:     if(buc->prior()==pointer(0)){ /* empty bucket */
Chris@101:       first->prior()=cend->prior();
Chris@101:       last->next()=cend->prior()->next();
Chris@101:       first->prior()->next()=buc;
Chris@101:       buc->prior()=first;
Chris@101:       cend->prior()=last;
Chris@101:     }
Chris@101:     else{
Chris@101:       first->prior()=buc->prior()->prior();
Chris@101:       last->next()=base_pointer_from(buc->prior());
Chris@101:       buc->prior()=first;
Chris@101:       last->next()->prior()=last;
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   static void append_range(pointer first,pointer last,pointer cend)
Chris@101:   {
Chris@101:     first->prior()=cend->prior();
Chris@101:     last->next()=cend->prior()->next();
Chris@101:     first->prior()->next()=base_pointer_from(first);
Chris@101:     cend->prior()=last;
Chris@101:   }
Chris@101: 
Chris@101:   static std::pair<pointer,bool> unlink_last_group(pointer end)
Chris@101:   {
Chris@101:     /* returns first of group true iff bucket is emptied */
Chris@101: 
Chris@101:     pointer x=end->prior();
Chris@101:     if(x->prior()->next()==base_pointer_from(x)){
Chris@101:       x->prior()->next()=x->next();
Chris@101:       end->prior()=x->prior();
Chris@101:       return std::make_pair(x,false);
Chris@101:     }
Chris@101:     else if(x->prior()->next()->prior()==x){
Chris@101:       x->prior()->next()->prior()=pointer(0);
Chris@101:       x->prior()->next()=x->next();
Chris@101:       end->prior()=x->prior();
Chris@101:       return std::make_pair(x,true);
Chris@101:     }
Chris@101:     else{
Chris@101:       pointer y=pointer_from(x->prior()->next());
Chris@101: 
Chris@101:       if(y->prior()->next()==base_pointer_from(y)){
Chris@101:         y->prior()->next()=x->next();
Chris@101:         end->prior()=y->prior();
Chris@101:         return std::make_pair(y,false);
Chris@101:       }
Chris@101:       else{
Chris@101:         y->prior()->next()->prior()=pointer(0);
Chris@101:         y->prior()->next()=x->next();
Chris@101:         end->prior()=y->prior();
Chris@101:         return std::make_pair(y,true);
Chris@101:       }
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   static void unlink_range(pointer first,pointer last)
Chris@101:   {
Chris@101:     if(is_first_of_bucket(first)){
Chris@101:       if(is_last_of_bucket(last)){
Chris@101:         first->prior()->next()->prior()=pointer(0);
Chris@101:         first->prior()->next()=last->next();
Chris@101:         last->next()->prior()->prior()=first->prior();
Chris@101:       }
Chris@101:       else{
Chris@101:         first->prior()->next()->prior()=pointer_from(last->next());
Chris@101:         last->next()->prior()=first->prior();
Chris@101:       }
Chris@101:     }
Chris@101:     else if(is_last_of_bucket(last)){
Chris@101:       first->prior()->next()=last->next();
Chris@101:       last->next()->prior()->prior()=first->prior();
Chris@101:     }
Chris@101:     else{
Chris@101:       first->prior()->next()=last->next();
Chris@101:       last->next()->prior()=first->prior();
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101: private:
Chris@101:   static pointer pointer_from(base_pointer x)
Chris@101:   {
Chris@101:     return Node::pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static base_pointer base_pointer_from(pointer x)
Chris@101:   {
Chris@101:     return Node::base_pointer_from(x);
Chris@101:   }
Chris@101: 
Chris@101:   static bool is_last_of_bucket(pointer x)
Chris@101:   {
Chris@101:     return x->next()->prior()->prior()==x;
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void left_unlink(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     assign(x->prior()->next(),x->next());
Chris@101:   }
Chris@101:   
Chris@101:   template<typename Assigner>
Chris@101:   static void right_unlink(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     assign(x->next()->prior(),x->prior());
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     assign(x->prior()->next()->prior(),pointer_from(x->next()));
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void right_unlink_last_of_bucket(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     assign(x->next()->prior()->prior(),x->prior());
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void right_unlink_first_of_group(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     pointer second=pointer_from(x->next()),
Chris@101:             last=second->prior(),
Chris@101:             lastbutone=last->prior();
Chris@101:     if(second==lastbutone){
Chris@101:       assign(second->next(),base_pointer_from(last));
Chris@101:       assign(second->prior(),x->prior());
Chris@101:     }
Chris@101:     else{
Chris@101:       assign(lastbutone->next(),base_pointer_from(second));
Chris@101:       assign(second->next()->prior(),last);
Chris@101:       assign(second->prior(),x->prior());
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void left_unlink_last_of_group(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     pointer lastbutone=x->prior(),
Chris@101:             first=pointer_from(lastbutone->next()),
Chris@101:             second=pointer_from(first->next());
Chris@101:     if(lastbutone==second){
Chris@101:       assign(lastbutone->prior(),first);
Chris@101:       assign(lastbutone->next(),x->next());
Chris@101:     }
Chris@101:     else{
Chris@101:       assign(second->prior(),lastbutone);
Chris@101:       assign(lastbutone->prior()->next(),base_pointer_from(first));
Chris@101:       assign(lastbutone->next(),x->next());
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     pointer first=pointer_from(x->next()),
Chris@101:             second=pointer_from(first->next()),
Chris@101:             last=second->prior();
Chris@101:     if(second==x){
Chris@101:       assign(last->prior(),first);
Chris@101:       assign(first->next(),base_pointer_from(last));
Chris@101:     }
Chris@101:     else{
Chris@101:       assign(last->prior(),x->prior());
Chris@101:       assign(x->prior()->next(),base_pointer_from(first));
Chris@101:     }
Chris@101:   }
Chris@101: 
Chris@101:   template<typename Assigner>
Chris@101:   static void unlink_second_of_group(pointer x,Assigner& assign)
Chris@101:   {
Chris@101:     pointer last=x->prior(),
Chris@101:             lastbutone=last->prior(),
Chris@101:             first=pointer_from(lastbutone->next());
Chris@101:     if(lastbutone==x){
Chris@101:       assign(first->next(),base_pointer_from(last));
Chris@101:       assign(last->prior(),first);
Chris@101:     }
Chris@101:     else{
Chris@101:       assign(first->next(),x->next());
Chris@101:       assign(x->next()->prior(),last);
Chris@101:     }
Chris@101:   }
Chris@16: };
Chris@16: 
Chris@16: template<typename Super>
Chris@16: struct hashed_index_node_trampoline:
Chris@101:   hashed_index_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       typename Super::allocator_type,
Chris@101:       char
Chris@101:     >::type
Chris@101:   >
Chris@16: {
Chris@101:   typedef typename boost::detail::allocator::rebind_to<
Chris@101:     typename Super::allocator_type,
Chris@101:     char
Chris@101:   >::type                                               impl_allocator_type;
Chris@101:   typedef hashed_index_node_impl<impl_allocator_type>   impl_type;
Chris@16: };
Chris@16: 
Chris@101: template<typename Super,typename Category>
Chris@101: struct hashed_index_node:
Chris@101:   Super,hashed_index_node_trampoline<Super>
Chris@16: {
Chris@16: private:
Chris@16:   typedef hashed_index_node_trampoline<Super> trampoline;
Chris@16: 
Chris@16: public:
Chris@101:   typedef typename trampoline::impl_type          impl_type;
Chris@101:   typedef hashed_index_node_alg<
Chris@101:     impl_type,Category>                           node_alg;
Chris@101:   typedef typename trampoline::base_pointer       impl_base_pointer;
Chris@101:   typedef typename trampoline::const_base_pointer const_impl_base_pointer;
Chris@101:   typedef typename trampoline::pointer            impl_pointer;
Chris@101:   typedef typename trampoline::const_pointer      const_impl_pointer;
Chris@101: 
Chris@101:   impl_pointer&      prior(){return trampoline::prior();}
Chris@101:   impl_pointer       prior()const{return trampoline::prior();}
Chris@101:   impl_base_pointer& next(){return trampoline::next();}
Chris@101:   impl_base_pointer  next()const{return trampoline::next();}
Chris@16: 
Chris@16:   impl_pointer impl()
Chris@16:   {
Chris@16:     return static_cast<impl_pointer>(
Chris@16:       static_cast<impl_type*>(static_cast<trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   const_impl_pointer impl()const
Chris@16:   {
Chris@16:     return static_cast<const_impl_pointer>(
Chris@16:       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   static hashed_index_node* from_impl(impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<hashed_index_node*>(
Chris@16:       static_cast<trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@16:   static const hashed_index_node* from_impl(const_impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<const hashed_index_node*>(
Chris@16:       static_cast<const trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@101:   /* interoperability with hashed_index_iterator */
Chris@101: 
Chris@101:   static void increment(hashed_index_node*& x)
Chris@16:   {
Chris@101:     x=from_impl(node_alg::after(x->impl()));
Chris@101:   }
Chris@101: 
Chris@101:   static void increment_local(hashed_index_node*& x)
Chris@101:   {
Chris@101:     x=from_impl(node_alg::after_local(x->impl()));
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif