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& |
---|
32 | ungrouped_node_base<A>::next_group(node_ptr ptr) |
---|
33 | { |
---|
34 | return ptr->next_; |
---|
35 | } |
---|
36 | |
---|
37 | template <class A> |
---|
38 | inline std::size_t ungrouped_node_base<A>::group_count(node_ptr) |
---|
39 | { |
---|
40 | return 1; |
---|
41 | } |
---|
42 | |
---|
43 | template <class A> |
---|
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> |
---|
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> |
---|
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> |
---|
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> |
---|
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& |
---|
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 |
---|
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> |
---|
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> |
---|
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> |
---|
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 |
---|
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> |
---|
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> |
---|
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> |
---|
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 |
---|