]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 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. | |
4569a895 | 19 | |
748086b7 JJ |
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 BK |
37 | * @file pat_trie_/split_fn_imps.hpp |
38 | * Contains an implementation class for pat_trie. | |
4569a895 AT |
39 | */ |
40 | ||
574dfb67 JW |
41 | #ifdef PB_DS_CLASS_C_DEC |
42 | ||
4569a895 AT |
43 | PB_DS_CLASS_T_DEC |
44 | void | |
45 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 46 | split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) |
4569a895 | 47 | { |
f5886803 FD |
48 | PB_DS_ASSERT_VALID((*this)) |
49 | PB_DS_ASSERT_VALID(other) | |
a345e45d | 50 | branch_bag bag; |
4569a895 | 51 | leaf_pointer p_split_lf = split_prep(r_key, other, bag); |
8fc81078 | 52 | if (p_split_lf == 0) |
4569a895 | 53 | { |
47bea7b8 | 54 | _GLIBCXX_DEBUG_ASSERT(bag.empty()); |
f5886803 FD |
55 | PB_DS_ASSERT_VALID((*this)) |
56 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 | 57 | return; |
4569a895 AT |
58 | } |
59 | ||
47bea7b8 | 60 | _GLIBCXX_DEBUG_ASSERT(!bag.empty()); |
4569a895 | 61 | other.clear(); |
a345e45d BK |
62 | |
63 | m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf), | |
64 | pref_end(p_split_lf), other, bag); | |
4569a895 AT |
65 | |
66 | m_p_head->m_p_parent->m_p_parent = m_p_head; | |
67 | ||
a345e45d BK |
68 | head_pointer __ohead = other.m_p_head; |
69 | __ohead->m_p_max = m_p_head->m_p_max; | |
4569a895 | 70 | m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); |
a345e45d | 71 | __ohead->m_p_min = other.leftmost_descendant(__ohead->m_p_parent); |
4569a895 | 72 | |
47bea7b8 | 73 | other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(), |
4569a895 AT |
74 | other.PB_DS_CLASS_C_DEC::end()); |
75 | m_size -= other.m_size; | |
f5886803 FD |
76 | PB_DS_ASSERT_VALID((*this)) |
77 | PB_DS_ASSERT_VALID(other) | |
4569a895 AT |
78 | } |
79 | ||
80 | PB_DS_CLASS_T_DEC | |
81 | typename PB_DS_CLASS_C_DEC::leaf_pointer | |
82 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
83 | split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other, |
84 | branch_bag& r_bag) | |
4569a895 | 85 | { |
47bea7b8 | 86 | _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); |
4569a895 AT |
87 | if (m_size == 0) |
88 | { | |
89 | other.clear(); | |
f5886803 FD |
90 | PB_DS_ASSERT_VALID((*this)) |
91 | PB_DS_ASSERT_VALID(other) | |
a345e45d | 92 | return 0; |
4569a895 AT |
93 | } |
94 | ||
a345e45d BK |
95 | if (synth_access_traits::cmp_keys(r_key, |
96 | PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) | |
4569a895 AT |
97 | { |
98 | other.clear(); | |
4569a895 | 99 | value_swap(other); |
f5886803 FD |
100 | PB_DS_ASSERT_VALID((*this)) |
101 | PB_DS_ASSERT_VALID(other) | |
a345e45d | 102 | return 0; |
4569a895 AT |
103 | } |
104 | ||
a345e45d BK |
105 | if (!synth_access_traits::cmp_keys(r_key, |
106 | PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()))) | |
4569a895 | 107 | { |
f5886803 FD |
108 | PB_DS_ASSERT_VALID((*this)) |
109 | PB_DS_ASSERT_VALID(other) | |
a345e45d | 110 | return 0; |
4569a895 AT |
111 | } |
112 | ||
113 | iterator it = lower_bound(r_key); | |
114 | ||
a345e45d | 115 | if (!synth_access_traits::equal_keys(PB_DS_V2F(*it), r_key)) |
4569a895 AT |
116 | --it; |
117 | ||
118 | node_pointer p_nd = it.m_p_nd; | |
a345e45d | 119 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); |
4569a895 | 120 | leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd); |
a345e45d | 121 | while (p_nd->m_type != head_node) |
4569a895 AT |
122 | { |
123 | r_bag.add_branch(); | |
4569a895 AT |
124 | p_nd = p_nd->m_p_parent; |
125 | } | |
a345e45d | 126 | _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_access_traits&)(*this), other);) |
4569a895 | 127 | |
a345e45d | 128 | return p_ret_l; |
4569a895 AT |
129 | } |
130 | ||
131 | PB_DS_CLASS_T_DEC | |
132 | typename PB_DS_CLASS_C_DEC::node_pointer | |
133 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
134 | rec_split(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, |
135 | PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) | |
4569a895 | 136 | { |
a345e45d | 137 | if (p_nd->m_type == leaf_node) |
4569a895 | 138 | { |
8fc81078 | 139 | _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0); |
a345e45d | 140 | return p_nd; |
4569a895 AT |
141 | } |
142 | ||
a345e45d BK |
143 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); |
144 | inode_pointer p_ind = static_cast<inode_pointer>(p_nd); | |
4569a895 | 145 | |
a345e45d BK |
146 | node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this); |
147 | node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag); | |
f5886803 | 148 | PB_DS_ASSERT_NODE_VALID(p_child_ret) |
a345e45d BK |
149 | p_ind->replace_child(p_child_ret, b_it, e_it, this); |
150 | apply_update(p_ind, (node_update*)this); | |
4569a895 | 151 | |
a345e45d BK |
152 | inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this); |
153 | const size_type lhs_dist = std::distance(p_ind->begin(), child_it); | |
154 | const size_type lhs_num_children = lhs_dist + 1; | |
47bea7b8 | 155 | _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); |
4569a895 | 156 | |
a345e45d BK |
157 | const size_type rhs_dist = std::distance(p_ind->begin(), p_ind->end()); |
158 | size_type rhs_num_children = rhs_dist - lhs_num_children; | |
4569a895 AT |
159 | if (rhs_num_children == 0) |
160 | { | |
a345e45d BK |
161 | apply_update(p_ind, (node_update*)this); |
162 | return p_ind; | |
4569a895 AT |
163 | } |
164 | ||
a345e45d BK |
165 | other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it, |
166 | rhs_num_children, r_bag); | |
4569a895 | 167 | |
a345e45d | 168 | child_it = p_ind->get_child_it(b_it, e_it, this); |
4569a895 AT |
169 | while (rhs_num_children != 0) |
170 | { | |
a345e45d BK |
171 | ++child_it; |
172 | p_ind->remove_child(child_it); | |
4569a895 AT |
173 | --rhs_num_children; |
174 | } | |
a345e45d | 175 | apply_update(p_ind, (node_update*)this); |
4569a895 | 176 | |
a345e45d BK |
177 | const size_type int_dist = std::distance(p_ind->begin(), p_ind->end()); |
178 | _GLIBCXX_DEBUG_ASSERT(int_dist >= 1); | |
179 | if (int_dist > 1) | |
4569a895 | 180 | { |
a345e45d BK |
181 | p_ind->update_prefixes(this); |
182 | PB_DS_ASSERT_NODE_VALID(p_ind) | |
183 | apply_update(p_ind, (node_update*)this); | |
184 | return p_ind; | |
4569a895 AT |
185 | } |
186 | ||
a345e45d BK |
187 | node_pointer p_ret = *p_ind->begin(); |
188 | p_ind->~inode(); | |
189 | s_inode_allocator.deallocate(p_ind, 1); | |
190 | apply_update(p_ret, (node_update*)this); | |
191 | return p_ret; | |
4569a895 AT |
192 | } |
193 | ||
194 | PB_DS_CLASS_T_DEC | |
195 | void | |
196 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
197 | split_insert_branch(size_type e_ind, a_const_iterator b_it, |
198 | inode_iterator child_b_it, | |
199 | size_type num_children, branch_bag& r_bag) | |
4569a895 | 200 | { |
47bea7b8 | 201 | #ifdef _GLIBCXX_DEBUG |
8fc81078 | 202 | if (m_p_head->m_p_parent != 0) |
f5886803 | 203 | PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) |
a345e45d | 204 | #endif |
4569a895 | 205 | |
a345e45d BK |
206 | const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1; |
207 | const size_type total_num_children = start + num_children; | |
4569a895 AT |
208 | if (total_num_children == 0) |
209 | { | |
8fc81078 | 210 | _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); |
4569a895 AT |
211 | return; |
212 | } | |
213 | ||
214 | if (total_num_children == 1) | |
215 | { | |
8fc81078 | 216 | if (m_p_head->m_p_parent != 0) |
a345e45d | 217 | { |
f5886803 | 218 | PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) |
a345e45d BK |
219 | return; |
220 | } | |
4569a895 | 221 | |
8fc81078 | 222 | _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); |
a345e45d BK |
223 | ++child_b_it; |
224 | m_p_head->m_p_parent = *child_b_it; | |
4569a895 | 225 | m_p_head->m_p_parent->m_p_parent = m_p_head; |
a345e45d | 226 | apply_update(m_p_head->m_p_parent, (node_update*)this); |
f5886803 | 227 | PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) |
47bea7b8 | 228 | return; |
4569a895 AT |
229 | } |
230 | ||
47bea7b8 | 231 | _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); |
a345e45d BK |
232 | inode_pointer p_new_root = r_bag.get_branch(); |
233 | new (p_new_root) inode(e_ind, b_it); | |
4569a895 | 234 | size_type num_inserted = 0; |
4569a895 AT |
235 | while (num_inserted++ < num_children) |
236 | { | |
4569a895 | 237 | ++child_b_it; |
a345e45d BK |
238 | PB_DS_ASSERT_NODE_VALID((*child_b_it)) |
239 | p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), | |
240 | pref_end(*child_b_it), this); | |
4569a895 AT |
241 | } |
242 | ||
8fc81078 | 243 | if (m_p_head->m_p_parent != 0) |
a345e45d | 244 | p_new_root->add_child(m_p_head->m_p_parent, |
4569a895 | 245 | pref_begin(m_p_head->m_p_parent), |
47bea7b8 | 246 | pref_end(m_p_head->m_p_parent), this); |
4569a895 AT |
247 | |
248 | m_p_head->m_p_parent = p_new_root; | |
4569a895 | 249 | p_new_root->m_p_parent = m_p_head; |
a345e45d | 250 | apply_update(m_p_head->m_p_parent, (node_update*)this); |
f5886803 | 251 | PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) |
47bea7b8 | 252 | } |
574dfb67 | 253 | #endif |