[857] | 1 | /* Copyright 2003-2005 Joaquín M López Muñoz.
|
---|
| 2 | * Distributed under the Boost Software License, Version 1.0.
|
---|
| 3 | * (See accompanying file LICENSE_1_0.txt or copy at
|
---|
| 4 | * http://www.boost.org/LICENSE_1_0.txt)
|
---|
| 5 | *
|
---|
| 6 | * See http://www.boost.org/libs/multi_index for library home page.
|
---|
| 7 | */
|
---|
| 8 |
|
---|
| 9 | #ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
|
---|
| 10 | #define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
|
---|
| 11 |
|
---|
| 12 | #if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
---|
| 13 | #pragma once
|
---|
| 14 | #endif
|
---|
| 15 |
|
---|
| 16 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
---|
| 17 | #include <functional>
|
---|
| 18 |
|
---|
| 19 | namespace boost{
|
---|
| 20 |
|
---|
| 21 | namespace multi_index{
|
---|
| 22 |
|
---|
| 23 | namespace detail{
|
---|
| 24 |
|
---|
| 25 | /* singly-linked node for use by hashed_index */
|
---|
| 26 |
|
---|
| 27 | struct hashed_index_node_impl
|
---|
| 28 | {
|
---|
| 29 | hashed_index_node_impl*& next(){return next_;}
|
---|
| 30 | hashed_index_node_impl*const & next()const{return next_;}
|
---|
| 31 |
|
---|
| 32 | /* interoperability with hashed_index_proxy */
|
---|
| 33 |
|
---|
| 34 | static hashed_index_node_impl* end(hashed_index_node_impl* header)
|
---|
| 35 | {
|
---|
| 36 | return header;
|
---|
| 37 | }
|
---|
| 38 |
|
---|
| 39 | /* algorithmic stuff */
|
---|
| 40 |
|
---|
| 41 | static void increment(
|
---|
| 42 | hashed_index_node_impl*& x,
|
---|
| 43 | hashed_index_node_impl* bbegin,hashed_index_node_impl* bbend)
|
---|
| 44 | {
|
---|
| 45 | std::less_equal<hashed_index_node_impl*> leq;
|
---|
| 46 |
|
---|
| 47 | x=x->next();
|
---|
| 48 | if(leq(bbegin,x)&&leq(x,bbend)){ /* bucket node */
|
---|
| 49 | do{
|
---|
| 50 | ++x;
|
---|
| 51 | }while(x->next()==x);
|
---|
| 52 | x=x->next();
|
---|
| 53 | }
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | static void link(
|
---|
| 57 | hashed_index_node_impl* x,hashed_index_node_impl* pos)
|
---|
| 58 | {
|
---|
| 59 | x->next()=pos->next();
|
---|
| 60 | pos->next()=x;
|
---|
| 61 | };
|
---|
| 62 |
|
---|
| 63 | static void unlink(hashed_index_node_impl* x)
|
---|
| 64 | {
|
---|
| 65 | hashed_index_node_impl* y=x->next();
|
---|
| 66 | while(y->next()!=x){y=y->next();}
|
---|
| 67 | y->next()=x->next();
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | static hashed_index_node_impl* prev(hashed_index_node_impl* x)
|
---|
| 71 | {
|
---|
| 72 | hashed_index_node_impl* y=x->next();
|
---|
| 73 | while(y->next()!=x){y=y->next();}
|
---|
| 74 | return y;
|
---|
| 75 | }
|
---|
| 76 |
|
---|
| 77 | static void unlink_next(hashed_index_node_impl* x)
|
---|
| 78 | {
|
---|
| 79 | x->next()=x->next()->next();
|
---|
| 80 | }
|
---|
| 81 |
|
---|
| 82 | private:
|
---|
| 83 | hashed_index_node_impl();
|
---|
| 84 |
|
---|
| 85 | hashed_index_node_impl* next_;
|
---|
| 86 | };
|
---|
| 87 |
|
---|
| 88 | template<typename Super>
|
---|
| 89 | struct hashed_index_node_trampoline:hashed_index_node_impl{};
|
---|
| 90 |
|
---|
| 91 | template<typename Super>
|
---|
| 92 | struct hashed_index_node:Super,hashed_index_node_trampoline<Super>
|
---|
| 93 | {
|
---|
| 94 | hashed_index_node_impl* impl()
|
---|
| 95 | {return static_cast<impl_type*>(this);}
|
---|
| 96 | const hashed_index_node_impl* impl()const
|
---|
| 97 | {return static_cast<const impl_type*>(this);}
|
---|
| 98 |
|
---|
| 99 | static hashed_index_node* from_impl(hashed_index_node_impl *x)
|
---|
| 100 | {return static_cast<hashed_index_node*>(static_cast<impl_type*>(x));}
|
---|
| 101 | static const hashed_index_node* from_impl(
|
---|
| 102 | const hashed_index_node_impl* x)
|
---|
| 103 | {
|
---|
| 104 | return static_cast<const hashed_index_node*>(
|
---|
| 105 | static_cast<const impl_type*>(x));
|
---|
| 106 | }
|
---|
| 107 |
|
---|
| 108 | static void increment(
|
---|
| 109 | hashed_index_node*& x,
|
---|
| 110 | hashed_index_node_impl* bbegin,hashed_index_node_impl* bend)
|
---|
| 111 | {
|
---|
| 112 | hashed_index_node_impl* xi=x->impl();
|
---|
| 113 | impl_type::increment(xi,bbegin,bend);
|
---|
| 114 | x=from_impl(xi);
|
---|
| 115 | }
|
---|
| 116 |
|
---|
| 117 | /* interoperability with hashed_index_proxy */
|
---|
| 118 |
|
---|
| 119 | static hashed_index_node* end(hashed_index_node* header)
|
---|
| 120 | {
|
---|
| 121 | return from_impl(impl_type::end(header->impl()));
|
---|
| 122 | }
|
---|
| 123 |
|
---|
| 124 | private:
|
---|
| 125 | typedef hashed_index_node_trampoline<Super> impl_type;
|
---|
| 126 | };
|
---|
| 127 |
|
---|
| 128 | } /* namespace multi_index::detail */
|
---|
| 129 |
|
---|
| 130 | } /* namespace multi_index */
|
---|
| 131 |
|
---|
| 132 | } /* namespace boost */
|
---|
| 133 |
|
---|
| 134 | #endif
|
---|