1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2018 Free Software Foundation, Inc. 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 8 // Foundation; either version 3, or (at your option) any later 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 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/>. 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 thin_heap_/insert_fn_imps.hpp 38 * Contains an implementation for thin_heap_. 39 */ 40 41 PB_DS_CLASS_T_DEC 42 inline typename PB_DS_CLASS_C_DEC::point_iterator 43 PB_DS_CLASS_C_DEC:: 44 push(const_reference r_val) 45 { 46 PB_DS_ASSERT_VALID((*this)) 47 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 48 p_nd->m_metadata = 0; 49 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0; 50 if (base_type::m_p_root == 0) 51 { 52 p_nd->m_p_next_sibling = 0; 53 m_p_max = base_type::m_p_root = p_nd; 54 PB_DS_ASSERT_VALID((*this)) 55 return point_iterator(p_nd); 56 } 57 58 p_nd->m_p_next_sibling = base_type::m_p_root; 59 base_type::m_p_root->m_p_prev_or_parent = 0; 60 base_type::m_p_root = p_nd; 61 update_max(p_nd); 62 PB_DS_ASSERT_VALID((*this)) 63 return point_iterator(p_nd); 64 } 65 66 PB_DS_CLASS_T_DEC 67 inline void 68 PB_DS_CLASS_C_DEC:: 69 make_root(node_pointer p_nd) 70 { 71 p_nd->m_metadata = p_nd->m_p_l_child == 0 72 ? 0 : 1 + p_nd->m_p_l_child->m_metadata; 73 } 74 75 PB_DS_CLASS_T_DEC 76 inline void 77 PB_DS_CLASS_C_DEC:: 78 make_root_and_link(node_pointer p_nd) 79 { 80 make_root(p_nd); 81 p_nd->m_p_prev_or_parent = 0; 82 p_nd->m_p_next_sibling = base_type::m_p_root; 83 if (base_type::m_p_root != 0) 84 base_type::m_p_root->m_p_prev_or_parent = 0; 85 86 base_type::m_p_root = p_nd; 87 update_max(p_nd); 88 } 89 90 PB_DS_CLASS_T_DEC 91 inline void 92 PB_DS_CLASS_C_DEC:: 93 fix(node_pointer p_y) 94 { 95 while (true) 96 { 97 if (p_y->m_p_prev_or_parent == 0) 98 { 99 fix_root(p_y); 100 return; 101 } 102 else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == 0) 103 { 104 if (p_y->m_p_l_child != 0) 105 { 106 fix_sibling_rank_1_unmarked(p_y); 107 return; 108 } 109 110 fix_sibling_rank_1_marked(p_y); 111 p_y = p_y->m_p_prev_or_parent; 112 } 113 else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1) 114 { 115 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0); 116 if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2) 117 { 118 fix_sibling_general_unmarked(p_y); 119 return; 120 } 121 122 fix_sibling_general_marked(p_y); 123 p_y = p_y->m_p_prev_or_parent; 124 } 125 else if ((p_y->m_p_l_child == 0&& 126 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&& 127 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3)) 128 { 129 node_pointer p_z = p_y->m_p_prev_or_parent; 130 fix_child(p_y); 131 p_y = p_z; 132 } 133 else 134 return; 135 } 136 } 137 138 PB_DS_CLASS_T_DEC 139 inline void 140 PB_DS_CLASS_C_DEC:: 141 fix_root(node_pointer p_y) 142 { 143 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0); 144 make_root(p_y); 145 PB_DS_ASSERT_NODE_CONSISTENT(p_y, true) 146 } 147 148 PB_DS_CLASS_T_DEC 149 inline void 150 PB_DS_CLASS_C_DEC:: 151 fix_sibling_rank_1_unmarked(node_pointer p_y) 152 { 153 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 154 155 _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;) 156 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 157 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0); 158 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0); 159 160 p_y->m_p_next_sibling = p_y->m_p_l_child; 161 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y; 162 p_y->m_p_l_child = 0; 163 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 164 } 165 166 PB_DS_CLASS_T_DEC 167 inline void 168 PB_DS_CLASS_C_DEC:: 169 fix_sibling_rank_1_marked(node_pointer p_y) 170 { 171 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 172 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0); 173 p_y->m_metadata = 0; 174 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 175 } 176 177 PB_DS_CLASS_T_DEC 178 inline void 179 PB_DS_CLASS_C_DEC:: 180 fix_sibling_general_unmarked(node_pointer p_y) 181 { 182 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 183 184 node_pointer p_w = p_y->m_p_l_child; 185 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 186 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 187 188 p_y->m_p_l_child = p_w->m_p_next_sibling; 189 p_w->m_p_next_sibling->m_p_prev_or_parent = p_y; 190 191 p_w->m_p_next_sibling = p_y->m_p_next_sibling; 192 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 193 p_w->m_p_next_sibling->m_p_prev_or_parent = p_w; 194 195 p_y->m_p_next_sibling = p_w; 196 p_w->m_p_prev_or_parent = p_y; 197 198 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 199 } 200 201 PB_DS_CLASS_T_DEC 202 inline void 203 PB_DS_CLASS_C_DEC:: 204 fix_sibling_general_marked(node_pointer p_y) 205 { 206 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 207 --p_y->m_metadata; 208 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 209 } 210 211 PB_DS_CLASS_T_DEC 212 inline void 213 PB_DS_CLASS_C_DEC:: 214 fix_child(node_pointer p_y) 215 { 216 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 217 218 if (p_y->m_p_next_sibling != 0) 219 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent; 220 221 if (p_y->m_p_prev_or_parent->m_p_l_child == p_y) 222 p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling; 223 else 224 p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling; 225 226 make_root_and_link(p_y); 227 } 228 229 PB_DS_CLASS_T_DEC 230 void 231 PB_DS_CLASS_C_DEC:: 232 modify(point_iterator it, const_reference r_new_val) 233 { 234 PB_DS_ASSERT_VALID((*this)) 235 node_pointer p_nd = it.m_p_nd; 236 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 237 238 const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value); 239 p_nd->m_value = r_new_val; 240 if (smaller) 241 { 242 remove_node(p_nd); 243 p_nd->m_p_l_child = 0; 244 make_root_and_link(p_nd); 245 PB_DS_ASSERT_VALID((*this)) 246 return; 247 } 248 249 if (p_nd->m_p_prev_or_parent == 0) 250 { 251 update_max(p_nd); 252 PB_DS_ASSERT_VALID((*this)) 253 return; 254 } 255 256 node_pointer p_y = p_nd->m_p_prev_or_parent; 257 _GLIBCXX_DEBUG_ASSERT(p_y != 0); 258 259 if (p_nd->m_p_next_sibling != 0) 260 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y; 261 262 if (p_y->m_p_l_child == p_nd) 263 p_y->m_p_l_child = p_nd->m_p_next_sibling; 264 else 265 p_y->m_p_next_sibling = p_nd->m_p_next_sibling; 266 267 fix(p_y); 268 make_root_and_link(p_nd); 269 PB_DS_ASSERT_VALID((*this)) 270 } 271 272 PB_DS_CLASS_T_DEC 273 inline void 274 PB_DS_CLASS_C_DEC:: 275 update_max(node_pointer p_nd) 276 { 277 if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) 278 m_p_max = p_nd; 279 } 280 281