]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
4569a895 AT |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
37 | * @file constructors_destructor_fn_imps.hpp | |
38 | * Contains an implementation class for ov_tree_. | |
39 | */ | |
40 | ||
41 | PB_DS_CLASS_T_DEC | |
42 | typename PB_DS_CLASS_C_DEC::value_allocator | |
43 | PB_DS_CLASS_C_DEC::s_value_alloc; | |
44 | ||
45 | PB_DS_CLASS_T_DEC | |
46 | typename PB_DS_CLASS_C_DEC::metadata_allocator | |
47 | PB_DS_CLASS_C_DEC::s_metadata_alloc; | |
48 | ||
49 | PB_DS_CLASS_T_DEC | |
50 | PB_DS_CLASS_C_DEC:: | |
51 | PB_DS_OV_TREE_CLASS_NAME() : | |
52 | m_a_values(NULL), | |
53 | m_a_metadata(NULL), | |
54 | m_end_it(NULL), | |
55 | m_size(0) | |
47bea7b8 | 56 | { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } |
4569a895 AT |
57 | |
58 | PB_DS_CLASS_T_DEC | |
59 | PB_DS_CLASS_C_DEC:: | |
60 | PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : | |
61 | cmp_fn_base(r_cmp_fn), | |
62 | m_a_values(NULL), | |
63 | m_a_metadata(NULL), | |
64 | m_end_it(NULL), | |
65 | m_size(0) | |
47bea7b8 | 66 | { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } |
4569a895 AT |
67 | |
68 | PB_DS_CLASS_T_DEC | |
69 | PB_DS_CLASS_C_DEC:: | |
70 | PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) : | |
71 | cmp_fn_base(r_cmp_fn), | |
72 | node_update(r_node_update), | |
73 | m_a_values(NULL), | |
74 | m_a_metadata(NULL), | |
75 | m_end_it(NULL), | |
76 | m_size(0) | |
47bea7b8 | 77 | { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } |
4569a895 AT |
78 | |
79 | PB_DS_CLASS_T_DEC | |
80 | PB_DS_CLASS_C_DEC:: | |
81 | PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : | |
47bea7b8 | 82 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 83 | debug_base(other), |
47bea7b8 | 84 | #endif |
4569a895 AT |
85 | #ifdef PB_DS_TREE_TRACE |
86 | PB_DS_TREE_TRACE_BASE_C_DEC(other), | |
47bea7b8 | 87 | #endif |
4569a895 AT |
88 | cmp_fn_base(other), |
89 | node_update(other), | |
90 | m_a_values(NULL), | |
91 | m_a_metadata(NULL), | |
92 | m_end_it(NULL), | |
93 | m_size(0) | |
94 | { | |
95 | copy_from_ordered_range(other.begin(), other.end()); | |
47bea7b8 BK |
96 | _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) |
97 | } | |
4569a895 AT |
98 | |
99 | PB_DS_CLASS_T_DEC | |
100 | template<typename It> | |
101 | inline void | |
102 | PB_DS_CLASS_C_DEC:: | |
103 | copy_from_range(It first_it, It last_it) | |
104 | { | |
105 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
106 | typedef | |
107 | std::map< | |
108 | key_type, | |
109 | mapped_type, | |
110 | Cmp_Fn, | |
111 | typename Allocator::template rebind< | |
112 | value_type>::other> | |
113 | map_type; | |
47bea7b8 | 114 | #else |
4569a895 AT |
115 | typedef |
116 | std::set< | |
117 | key_type, | |
118 | Cmp_Fn, | |
119 | typename Allocator::template rebind< | |
120 | Key>::other> | |
121 | map_type; | |
47bea7b8 | 122 | #endif |
4569a895 AT |
123 | |
124 | map_type m(first_it, last_it); | |
4569a895 AT |
125 | copy_from_ordered_range(m.begin(), m.end()); |
126 | } | |
127 | ||
128 | PB_DS_CLASS_T_DEC | |
129 | template<typename It> | |
130 | void | |
131 | PB_DS_CLASS_C_DEC:: | |
132 | copy_from_ordered_range(It first_it, It last_it) | |
133 | { | |
1ab79481 BK |
134 | const size_type len = std::distance(first_it, last_it); |
135 | if (len == 0) | |
4569a895 AT |
136 | return; |
137 | ||
1ab79481 | 138 | value_vector a_values = s_value_alloc.allocate(len); |
4569a895 AT |
139 | iterator target_it = a_values; |
140 | It source_it = first_it; | |
141 | It source_end_it = last_it; | |
142 | ||
1ab79481 | 143 | cond_dtor<size_type> cd(a_values, target_it, len); |
4569a895 AT |
144 | while (source_it != source_end_it) |
145 | { | |
47bea7b8 | 146 | new (const_cast<void* >(static_cast<const void* >(target_it))) |
4569a895 AT |
147 | value_type(*source_it++); |
148 | ||
149 | ++target_it; | |
150 | } | |
151 | ||
1ab79481 | 152 | reallocate_metadata((node_update* )this, len); |
4569a895 | 153 | cd.set_no_action(); |
4569a895 | 154 | m_a_values = a_values; |
1ab79481 | 155 | m_size = len; |
4569a895 | 156 | m_end_it = m_a_values + m_size; |
4569a895 AT |
157 | update(PB_DS_node_begin_imp(), (node_update* )this); |
158 | ||
47bea7b8 | 159 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 160 | const_iterator dbg_it = m_a_values; |
4569a895 AT |
161 | while (dbg_it != m_end_it) |
162 | { | |
551fe1a2 | 163 | debug_base::insert_new(PB_DS_V2F(*dbg_it)); |
4569a895 AT |
164 | dbg_it++; |
165 | } | |
4569a895 | 166 | PB_DS_CLASS_C_DEC::assert_valid(); |
47bea7b8 | 167 | #endif |
4569a895 AT |
168 | } |
169 | ||
170 | PB_DS_CLASS_T_DEC | |
171 | template<typename It> | |
172 | void | |
173 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
174 | copy_from_ordered_range(It first_it, It last_it, It other_first_it, |
175 | It other_last_it) | |
4569a895 AT |
176 | { |
177 | clear(); | |
1ab79481 | 178 | const size_type len = std::distance(first_it, last_it) |
47bea7b8 | 179 | + std::distance(other_first_it, other_last_it); |
4569a895 | 180 | |
1ab79481 | 181 | value_vector a_values = s_value_alloc.allocate(len); |
4569a895 AT |
182 | |
183 | iterator target_it = a_values; | |
184 | It source_it = first_it; | |
185 | It source_end_it = last_it; | |
186 | ||
1ab79481 | 187 | cond_dtor<size_type> cd(a_values, target_it, len); |
4569a895 AT |
188 | while (source_it != source_end_it) |
189 | { | |
47bea7b8 | 190 | new (const_cast<void* >(static_cast<const void* >(target_it))) |
4569a895 | 191 | value_type(*source_it++); |
4569a895 AT |
192 | ++target_it; |
193 | } | |
194 | ||
195 | source_it = other_first_it; | |
196 | source_end_it = other_last_it; | |
197 | ||
198 | while (source_it != source_end_it) | |
199 | { | |
47bea7b8 | 200 | new (const_cast<void* >(static_cast<const void* >(target_it))) |
4569a895 | 201 | value_type(*source_it++); |
4569a895 AT |
202 | ++target_it; |
203 | } | |
204 | ||
1ab79481 | 205 | reallocate_metadata((node_update* )this, len); |
4569a895 | 206 | cd.set_no_action(); |
4569a895 | 207 | m_a_values = a_values; |
1ab79481 | 208 | m_size = len; |
4569a895 | 209 | m_end_it = m_a_values + m_size; |
4569a895 AT |
210 | update(PB_DS_node_begin_imp(), (node_update* )this); |
211 | ||
47bea7b8 | 212 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 213 | const_iterator dbg_it = m_a_values; |
4569a895 AT |
214 | while (dbg_it != m_end_it) |
215 | { | |
551fe1a2 | 216 | debug_base::insert_new(PB_DS_V2F(*dbg_it)); |
4569a895 AT |
217 | dbg_it++; |
218 | } | |
4569a895 | 219 | PB_DS_CLASS_C_DEC::assert_valid(); |
47bea7b8 | 220 | #endif |
4569a895 AT |
221 | } |
222 | ||
223 | PB_DS_CLASS_T_DEC | |
224 | void | |
225 | PB_DS_CLASS_C_DEC:: | |
226 | swap(PB_DS_CLASS_C_DEC& other) | |
227 | { | |
47bea7b8 BK |
228 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
229 | value_swap(other); | |
4569a895 | 230 | std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); |
47bea7b8 BK |
231 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
232 | } | |
4569a895 AT |
233 | |
234 | PB_DS_CLASS_T_DEC | |
235 | void | |
236 | PB_DS_CLASS_C_DEC:: | |
237 | value_swap(PB_DS_CLASS_C_DEC& other) | |
238 | { | |
239 | std::swap(m_a_values, other.m_a_values); | |
4569a895 | 240 | std::swap(m_a_metadata, other.m_a_metadata); |
4569a895 | 241 | std::swap(m_size, other.m_size); |
4569a895 | 242 | std::swap(m_end_it, other.m_end_it); |
551fe1a2 | 243 | _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) |
47bea7b8 | 244 | } |
4569a895 AT |
245 | |
246 | PB_DS_CLASS_T_DEC | |
247 | PB_DS_CLASS_C_DEC:: | |
248 | ~PB_DS_OV_TREE_CLASS_NAME() | |
249 | { | |
47bea7b8 BK |
250 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
251 | cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); | |
4569a895 AT |
252 | reallocate_metadata((node_update* )this, 0); |
253 | } | |
254 | ||
255 | PB_DS_CLASS_T_DEC | |
256 | inline void | |
257 | PB_DS_CLASS_C_DEC:: | |
258 | update(node_iterator /*it*/, null_node_update_pointer) | |
259 | { } | |
260 | ||
261 | PB_DS_CLASS_T_DEC | |
262 | template<typename Node_Update> | |
263 | void | |
264 | PB_DS_CLASS_C_DEC:: | |
265 | update(node_iterator nd_it, Node_Update* p_update) | |
266 | { | |
267 | const_node_iterator end_it = PB_DS_node_end_imp(); | |
4569a895 AT |
268 | if (nd_it == end_it) |
269 | return; | |
4569a895 AT |
270 | update(nd_it.get_l_child(), p_update); |
271 | update(nd_it.get_r_child(), p_update); | |
4569a895 AT |
272 | node_update::operator()(nd_it, end_it); |
273 | } |