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