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