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