1 
2 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
3 // Copyright (C) 2005-2009 Daniel James
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 
7 // This contains the basic data structure, apart from the actual values. There's
8 // no construction or deconstruction here. So this only depends on the pointer
9 // type.
10 
11 #ifndef BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED
12 #define BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED
13 
14 #include <boost/config.hpp>
15 #include <boost/assert.hpp>
16 #include <boost/detail/workaround.hpp>
17 #include <boost/unordered/detail/fwd.hpp>
18 
19 #if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582)
20 #define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
21 #else
22 #define BOOST_UNORDERED_BORLAND_BOOL(x) x
23 #endif
24 
25 namespace boost { namespace unordered_detail {
26 
27     ////////////////////////////////////////////////////////////////////////////
28     // ungrouped node implementation
29 
30     template <class A>
31     inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr&
next_group(node_ptr ptr)32         ungrouped_node_base<A>::next_group(node_ptr ptr)
33     {
34         return ptr->next_;
35     }
36 
37     template <class A>
group_count(node_ptr)38     inline std::size_t ungrouped_node_base<A>::group_count(node_ptr)
39     {
40         return 1;
41     }
42 
43     template <class A>
add_to_bucket(node_ptr n,bucket & b)44     inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
45     {
46         n->next_ = b.next_;
47         b.next_ = n;
48     }
49 
50     template <class A>
add_after_node(node_ptr n,node_ptr position)51     inline void ungrouped_node_base<A>::add_after_node(node_ptr n,
52         node_ptr position)
53     {
54         n->next_ = position->next_;
55         position->next_ = position;
56     }
57 
58     template <class A>
unlink_nodes(bucket & b,node_ptr begin,node_ptr end)59     inline void ungrouped_node_base<A>::unlink_nodes(bucket& b,
60         node_ptr begin, node_ptr end)
61     {
62         node_ptr* pos = &b.next_;
63         while(*pos != begin) pos = &(*pos)->next_;
64         *pos = end;
65     }
66 
67     template <class A>
unlink_nodes(bucket & b,node_ptr end)68     inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
69     {
70         b.next_ = end;
71     }
72 
73     template <class A>
unlink_node(bucket & b,node_ptr n)74     inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr n)
75     {
76         unlink_nodes(b, n, n->next_);
77     }
78 
79     ////////////////////////////////////////////////////////////////////////////
80     // grouped node implementation
81 
82     // If ptr is the first element in a group, return pointer to next group.
83     // Otherwise returns a pointer to ptr.
84     template <class A>
85     inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr&
next_group(node_ptr ptr)86         grouped_node_base<A>::next_group(node_ptr ptr)
87     {
88         return get(ptr).group_prev_->next_;
89     }
90 
91     template <class A>
92     inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
first_in_group(node_ptr ptr)93         grouped_node_base<A>::first_in_group(node_ptr ptr)
94     {
95         while(next_group(ptr) == ptr)
96             ptr = get(ptr).group_prev_;
97         return ptr;
98     }
99 
100     template <class A>
group_count(node_ptr ptr)101     inline std::size_t grouped_node_base<A>::group_count(node_ptr ptr)
102     {
103         node_ptr start = ptr;
104         std::size_t size = 0;
105         do {
106             ++size;
107             ptr = get(ptr).group_prev_;
108         } while(ptr != start);
109         return size;
110     }
111 
112     template <class A>
add_to_bucket(node_ptr n,bucket & b)113     inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
114     {
115         n->next_ = b.next_;
116         get(n).group_prev_ = n;
117         b.next_ = n;
118     }
119 
120     template <class A>
add_after_node(node_ptr n,node_ptr pos)121     inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos)
122     {
123         n->next_ = next_group(pos);
124         get(n).group_prev_ = get(pos).group_prev_;
125         next_group(pos) = n;
126         get(pos).group_prev_ = n;
127     }
128 
129     // Break a ciruclar list into two, with split as the beginning
130     // of the second group (if split is at the beginning then don't
131     // split).
132     template <class A>
133     inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
split_group(node_ptr split)134         grouped_node_base<A>::split_group(node_ptr split)
135     {
136         node_ptr first = first_in_group(split);
137         if(first == split) return split;
138 
139         node_ptr last = get(first).group_prev_;
140         get(first).group_prev_ = get(split).group_prev_;
141         get(split).group_prev_ = last;
142 
143         return first;
144     }
145 
146     template <class A>
unlink_node(bucket & b,node_ptr n)147     void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n)
148     {
149         node_ptr next = n->next_;
150         node_ptr* pos = &next_group(n);
151 
152         if(*pos != n) {
153             // The node is at the beginning of a group.
154 
155             // Find the previous node pointer:
156             pos = &b.next_;
157             while(*pos != n) pos = &next_group(*pos);
158 
159             // Remove from group
160             if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
161                 get(next).group_prev_ == n)
162             {
163                 get(next).group_prev_ = get(n).group_prev_;
164             }
165         }
166         else if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
167             get(next).group_prev_ == n)
168         {
169             // The deleted node is not at the end of the group, so
170             // change the link from the next node.
171             get(next).group_prev_ = get(n).group_prev_;
172         }
173         else {
174             // The deleted node is at the end of the group, so the
175             // first node in the group is pointing to it.
176             // Find that to change its pointer.
177             node_ptr x = get(n).group_prev_;
178             while(get(x).group_prev_ != n) {
179                 x = get(x).group_prev_;
180             }
181             get(x).group_prev_ = get(n).group_prev_;
182         }
183         *pos = next;
184     }
185 
186     template <class A>
unlink_nodes(bucket & b,node_ptr begin,node_ptr end)187     void grouped_node_base<A>::unlink_nodes(bucket& b,
188         node_ptr begin, node_ptr end)
189     {
190         node_ptr* pos = &next_group(begin);
191 
192         if(*pos != begin) {
193             // The node is at the beginning of a group.
194 
195             // Find the previous node pointer:
196             pos = &b.next_;
197             while(*pos != begin) pos = &next_group(*pos);
198 
199             // Remove from group
200             if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end);
201         }
202         else {
203             node_ptr group1 = split_group(begin);
204             if(BOOST_UNORDERED_BORLAND_BOOL(end)) {
205                 node_ptr group2 = split_group(end);
206 
207                 if(begin == group2) {
208                     node_ptr end1 = get(group1).group_prev_;
209                     node_ptr end2 = get(group2).group_prev_;
210                     get(group1).group_prev_ = end2;
211                     get(group2).group_prev_ = end1;
212                 }
213             }
214         }
215         *pos = end;
216     }
217 
218     template <class A>
unlink_nodes(bucket & b,node_ptr end)219     void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
220     {
221         split_group(end);
222         b.next_ = end;
223     }
224 }}
225 
226 #endif
227