]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
8d9254fc | 3 | // Copyright (C) 2005-2020 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 | /** | |
a345e45d | 37 | * @file ov_tree_map_/constructors_destructor_fn_imps.hpp |
4569a895 AT |
38 | * Contains an implementation class for ov_tree_. |
39 | */ | |
40 | ||
574dfb67 JW |
41 | #ifdef PB_DS_CLASS_C_DEC |
42 | ||
4569a895 AT |
43 | PB_DS_CLASS_T_DEC |
44 | typename PB_DS_CLASS_C_DEC::value_allocator | |
45 | PB_DS_CLASS_C_DEC::s_value_alloc; | |
46 | ||
47 | PB_DS_CLASS_T_DEC | |
48 | typename PB_DS_CLASS_C_DEC::metadata_allocator | |
49 | PB_DS_CLASS_C_DEC::s_metadata_alloc; | |
50 | ||
51 | PB_DS_CLASS_T_DEC | |
52 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 53 | PB_DS_OV_TREE_NAME() : |
8fc81078 PC |
54 | m_a_values(0), |
55 | m_a_metadata(0), | |
56 | m_end_it(0), | |
4569a895 | 57 | m_size(0) |
f5886803 | 58 | { PB_DS_ASSERT_VALID((*this)) } |
4569a895 AT |
59 | |
60 | PB_DS_CLASS_T_DEC | |
61 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
62 | PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn) : |
63 | cmp_fn(r_cmp_fn), | |
8fc81078 PC |
64 | m_a_values(0), |
65 | m_a_metadata(0), | |
66 | m_end_it(0), | |
4569a895 | 67 | m_size(0) |
f5886803 | 68 | { PB_DS_ASSERT_VALID((*this)) } |
4569a895 AT |
69 | |
70 | PB_DS_CLASS_T_DEC | |
71 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
72 | PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_nodeu) : |
73 | cmp_fn(r_cmp_fn), | |
74 | node_update(r_nodeu), | |
8fc81078 PC |
75 | m_a_values(0), |
76 | m_a_metadata(0), | |
77 | m_end_it(0), | |
4569a895 | 78 | m_size(0) |
f5886803 | 79 | { PB_DS_ASSERT_VALID((*this)) } |
4569a895 AT |
80 | |
81 | PB_DS_CLASS_T_DEC | |
82 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 83 | PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC& other) : |
4569a895 | 84 | #ifdef PB_DS_TREE_TRACE |
a345e45d BK |
85 | trace_base(other), |
86 | #endif | |
87 | cmp_fn(other), | |
4569a895 | 88 | node_update(other), |
8fc81078 PC |
89 | m_a_values(0), |
90 | m_a_metadata(0), | |
91 | m_end_it(0), | |
4569a895 AT |
92 | m_size(0) |
93 | { | |
94 | copy_from_ordered_range(other.begin(), other.end()); | |
f5886803 | 95 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 96 | } |
4569a895 AT |
97 | |
98 | PB_DS_CLASS_T_DEC | |
99 | template<typename It> | |
100 | inline void | |
101 | PB_DS_CLASS_C_DEC:: | |
102 | copy_from_range(It first_it, It last_it) | |
103 | { | |
104 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
a345e45d | 105 | typedef std::map<key_type, mapped_type, Cmp_Fn, |
ec541f1b | 106 | typename rebind_traits<_Alloc, value_type>::allocator_type> |
4569a895 | 107 | map_type; |
a345e45d BK |
108 | #else |
109 | typedef std::set<key_type, Cmp_Fn, | |
ec541f1b | 110 | typename rebind_traits<_Alloc, Key>::allocator_type> |
4569a895 | 111 | map_type; |
a345e45d | 112 | #endif |
4569a895 AT |
113 | |
114 | map_type m(first_it, last_it); | |
4569a895 | 115 | copy_from_ordered_range(m.begin(), m.end()); |
f5886803 | 116 | PB_DS_ASSERT_VALID((*this)) |
4569a895 AT |
117 | } |
118 | ||
119 | PB_DS_CLASS_T_DEC | |
120 | template<typename It> | |
121 | void | |
122 | PB_DS_CLASS_C_DEC:: | |
123 | copy_from_ordered_range(It first_it, It last_it) | |
124 | { | |
1ab79481 BK |
125 | const size_type len = std::distance(first_it, last_it); |
126 | if (len == 0) | |
4569a895 AT |
127 | return; |
128 | ||
1ab79481 | 129 | value_vector a_values = s_value_alloc.allocate(len); |
4569a895 AT |
130 | iterator target_it = a_values; |
131 | It source_it = first_it; | |
132 | It source_end_it = last_it; | |
133 | ||
1ab79481 | 134 | cond_dtor<size_type> cd(a_values, target_it, len); |
4569a895 AT |
135 | while (source_it != source_end_it) |
136 | { | |
a345e45d BK |
137 | void* __v = const_cast<void*>(static_cast<const void*>(target_it)); |
138 | new (__v) value_type(*source_it++); | |
4569a895 AT |
139 | ++target_it; |
140 | } | |
141 | ||
a345e45d | 142 | reallocate_metadata((node_update*)this, len); |
4569a895 | 143 | cd.set_no_action(); |
4569a895 | 144 | m_a_values = a_values; |
1ab79481 | 145 | m_size = len; |
4569a895 | 146 | m_end_it = m_a_values + m_size; |
a345e45d | 147 | update(PB_DS_node_begin_imp(), (node_update*)this); |
4569a895 | 148 | |
47bea7b8 | 149 | #ifdef _GLIBCXX_DEBUG |
f5886803 | 150 | for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it) |
a345e45d | 151 | debug_base::insert_new(PB_DS_V2F(*dbg_it)); |
f5886803 | 152 | #endif |
4569a895 AT |
153 | } |
154 | ||
155 | PB_DS_CLASS_T_DEC | |
156 | template<typename It> | |
157 | void | |
158 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 159 | copy_from_ordered_range(It first_it, It last_it, It other_first_it, |
47bea7b8 | 160 | It other_last_it) |
4569a895 AT |
161 | { |
162 | clear(); | |
a345e45d BK |
163 | const size_type len = std::distance(first_it, last_it) |
164 | + std::distance(other_first_it, other_last_it); | |
4569a895 | 165 | |
1ab79481 | 166 | value_vector a_values = s_value_alloc.allocate(len); |
4569a895 AT |
167 | |
168 | iterator target_it = a_values; | |
169 | It source_it = first_it; | |
170 | It source_end_it = last_it; | |
171 | ||
1ab79481 | 172 | cond_dtor<size_type> cd(a_values, target_it, len); |
4569a895 AT |
173 | while (source_it != source_end_it) |
174 | { | |
47bea7b8 | 175 | new (const_cast<void* >(static_cast<const void* >(target_it))) |
4569a895 | 176 | value_type(*source_it++); |
4569a895 AT |
177 | ++target_it; |
178 | } | |
179 | ||
180 | source_it = other_first_it; | |
181 | source_end_it = other_last_it; | |
182 | ||
183 | while (source_it != source_end_it) | |
184 | { | |
47bea7b8 | 185 | new (const_cast<void* >(static_cast<const void* >(target_it))) |
4569a895 | 186 | value_type(*source_it++); |
4569a895 AT |
187 | ++target_it; |
188 | } | |
189 | ||
1ab79481 | 190 | reallocate_metadata((node_update* )this, len); |
4569a895 | 191 | cd.set_no_action(); |
4569a895 | 192 | m_a_values = a_values; |
1ab79481 | 193 | m_size = len; |
4569a895 | 194 | m_end_it = m_a_values + m_size; |
4569a895 AT |
195 | update(PB_DS_node_begin_imp(), (node_update* )this); |
196 | ||
47bea7b8 | 197 | #ifdef _GLIBCXX_DEBUG |
f5886803 | 198 | for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it) |
a345e45d | 199 | debug_base::insert_new(PB_DS_V2F(*dbg_it)); |
f5886803 | 200 | #endif |
4569a895 AT |
201 | } |
202 | ||
203 | PB_DS_CLASS_T_DEC | |
204 | void | |
205 | PB_DS_CLASS_C_DEC:: | |
206 | swap(PB_DS_CLASS_C_DEC& other) | |
207 | { | |
f5886803 FD |
208 | PB_DS_ASSERT_VALID((*this)) |
209 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 | 210 | value_swap(other); |
a345e45d BK |
211 | std::swap(static_cast<cmp_fn&>(*this), |
212 | static_cast<cmp_fn&>(other)); | |
213 | std::swap(static_cast<traits_base&>(*this), | |
214 | static_cast<traits_base&>(other)); | |
f5886803 FD |
215 | PB_DS_ASSERT_VALID(other) |
216 | PB_DS_ASSERT_VALID((*this)) | |
47bea7b8 | 217 | } |
4569a895 AT |
218 | |
219 | PB_DS_CLASS_T_DEC | |
220 | void | |
221 | PB_DS_CLASS_C_DEC:: | |
222 | value_swap(PB_DS_CLASS_C_DEC& other) | |
223 | { | |
a345e45d | 224 | _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) |
4569a895 | 225 | std::swap(m_a_values, other.m_a_values); |
4569a895 | 226 | std::swap(m_a_metadata, other.m_a_metadata); |
4569a895 | 227 | std::swap(m_size, other.m_size); |
4569a895 | 228 | std::swap(m_end_it, other.m_end_it); |
47bea7b8 | 229 | } |
4569a895 AT |
230 | |
231 | PB_DS_CLASS_T_DEC | |
232 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 233 | ~PB_DS_OV_TREE_NAME() |
4569a895 | 234 | { |
a345e45d | 235 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 236 | cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); |
f5886803 | 237 | reallocate_metadata((node_update*)this, 0); |
4569a895 AT |
238 | } |
239 | ||
240 | PB_DS_CLASS_T_DEC | |
241 | inline void | |
242 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 243 | update(node_iterator, null_node_update_pointer) |
4569a895 AT |
244 | { } |
245 | ||
246 | PB_DS_CLASS_T_DEC | |
247 | template<typename Node_Update> | |
248 | void | |
249 | PB_DS_CLASS_C_DEC:: | |
250 | update(node_iterator nd_it, Node_Update* p_update) | |
251 | { | |
a345e45d BK |
252 | node_const_iterator end_it = PB_DS_node_end_imp(); |
253 | if (nd_it != end_it) | |
254 | { | |
255 | update(nd_it.get_l_child(), p_update); | |
256 | update(nd_it.get_r_child(), p_update); | |
257 | node_update::operator()(nd_it, end_it); | |
258 | } | |
4569a895 | 259 | } |
574dfb67 | 260 | #endif |