1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file insert_fn_imps.hpp 44 * Contains an implementation for thin_heap_. 45 */ 46 47PB_DS_CLASS_T_DEC 48inline typename PB_DS_CLASS_C_DEC::point_iterator 49PB_DS_CLASS_C_DEC:: 50push(const_reference r_val) 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid();) 53 54 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 55 56 p_nd->m_metadata = 0; 57 58 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL; 59 60 if (base_type::m_p_root == NULL) 61 { 62 p_nd->m_p_next_sibling = NULL; 63 64 m_p_max = base_type::m_p_root = p_nd; 65 66 _GLIBCXX_DEBUG_ONLY(assert_valid();) 67 68 return point_iterator(p_nd); 69 } 70 71 p_nd->m_p_next_sibling = base_type::m_p_root; 72 73 base_type::m_p_root->m_p_prev_or_parent = NULL; 74 75 base_type::m_p_root = p_nd; 76 77 update_max(p_nd); 78 79 _GLIBCXX_DEBUG_ONLY(assert_valid();) 80 81 return point_iterator(p_nd); 82} 83 84PB_DS_CLASS_T_DEC 85inline void 86PB_DS_CLASS_C_DEC:: 87make_root(node_pointer p_nd) 88{ 89 p_nd->m_metadata = 90 p_nd->m_p_l_child == NULL? 91 0 : 92 1 + p_nd->m_p_l_child->m_metadata; 93} 94 95PB_DS_CLASS_T_DEC 96inline void 97PB_DS_CLASS_C_DEC:: 98make_root_and_link(node_pointer p_nd) 99{ 100 make_root(p_nd); 101 102 p_nd->m_p_prev_or_parent = NULL; 103 104 p_nd->m_p_next_sibling = base_type::m_p_root; 105 106 if (base_type::m_p_root != NULL) 107 base_type::m_p_root->m_p_prev_or_parent = NULL; 108 109 base_type::m_p_root = p_nd; 110 111 update_max(p_nd); 112} 113 114PB_DS_CLASS_T_DEC 115inline void 116PB_DS_CLASS_C_DEC:: 117fix(node_pointer p_y) 118{ 119 while (true) 120 { 121 if (p_y->m_p_prev_or_parent == NULL) 122 { 123 fix_root(p_y); 124 125 return; 126 } 127 else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == NULL) 128 { 129 if (p_y->m_p_l_child != NULL) 130 { 131 fix_sibling_rank_1_unmarked(p_y); 132 133 return; 134 } 135 136 fix_sibling_rank_1_marked(p_y); 137 138 p_y = p_y->m_p_prev_or_parent; 139 } 140 else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1) 141 { 142 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != NULL); 143 144 if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2) 145 { 146 fix_sibling_general_unmarked(p_y); 147 148 return; 149 } 150 151 fix_sibling_general_marked(p_y); 152 153 p_y = p_y->m_p_prev_or_parent; 154 } 155 else if ((p_y->m_p_l_child == NULL&& 156 p_y->m_metadata == 2) ||(p_y->m_p_l_child != NULL&& 157 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3)) 158 { 159 node_pointer p_z = p_y->m_p_prev_or_parent; 160 161 fix_child(p_y); 162 163 p_y = p_z; 164 } 165 else 166 return; 167 } 168} 169 170PB_DS_CLASS_T_DEC 171inline void 172PB_DS_CLASS_C_DEC:: 173fix_root(node_pointer p_y) 174{ 175 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == NULL); 176 177 make_root(p_y); 178 179 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, true);) 180 } 181 182PB_DS_CLASS_T_DEC 183inline void 184PB_DS_CLASS_C_DEC:: 185fix_sibling_rank_1_unmarked(node_pointer p_y) 186{ 187 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 188 189 _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;) 190 _GLIBCXX_DEBUG_ASSERT(p_w != NULL); 191 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == NULL); 192 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == NULL); 193 194 p_y->m_p_next_sibling = p_y->m_p_l_child; 195 196 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y; 197 198 p_y->m_p_l_child = NULL; 199 200 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 201 } 202 203PB_DS_CLASS_T_DEC 204inline void 205PB_DS_CLASS_C_DEC:: 206fix_sibling_rank_1_marked(node_pointer p_y) 207{ 208 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 209 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == NULL); 210 211 p_y->m_metadata = 0; 212 213 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 214 } 215 216PB_DS_CLASS_T_DEC 217inline void 218PB_DS_CLASS_C_DEC:: 219fix_sibling_general_unmarked(node_pointer p_y) 220{ 221 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 222 223 node_pointer p_w = p_y->m_p_l_child; 224 _GLIBCXX_DEBUG_ASSERT(p_w != NULL); 225 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL); 226 227 p_y->m_p_l_child = p_w->m_p_next_sibling; 228 p_w->m_p_next_sibling->m_p_prev_or_parent = p_y; 229 230 p_w->m_p_next_sibling = p_y->m_p_next_sibling; 231 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL); 232 p_w->m_p_next_sibling->m_p_prev_or_parent = p_w; 233 234 p_y->m_p_next_sibling = p_w; 235 p_w->m_p_prev_or_parent = p_y; 236 237 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 238 } 239 240PB_DS_CLASS_T_DEC 241inline void 242PB_DS_CLASS_C_DEC:: 243fix_sibling_general_marked(node_pointer p_y) 244{ 245 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 246 247 --p_y->m_metadata; 248 249 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 250 } 251 252PB_DS_CLASS_T_DEC 253inline void 254PB_DS_CLASS_C_DEC:: 255fix_child(node_pointer p_y) 256{ 257 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 258 259 if (p_y->m_p_next_sibling != NULL) 260 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent; 261 262 if (p_y->m_p_prev_or_parent->m_p_l_child == p_y) 263 p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling; 264 else 265 p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling; 266 267 make_root_and_link(p_y); 268} 269 270PB_DS_CLASS_T_DEC 271void 272PB_DS_CLASS_C_DEC:: 273modify(point_iterator it, const_reference r_new_val) 274{ 275 _GLIBCXX_DEBUG_ONLY(assert_valid();) 276 node_pointer p_nd = it.m_p_nd; 277 278 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 279 280 const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value); 281 282 p_nd->m_value = r_new_val; 283 284 if (smaller) 285 { 286 remove_node(p_nd); 287 288 p_nd->m_p_l_child = NULL; 289 290 make_root_and_link(p_nd); 291 292 _GLIBCXX_DEBUG_ONLY(assert_valid();) 293 294 return; 295 } 296 297 if (p_nd->m_p_prev_or_parent == NULL) 298 { 299 update_max(p_nd); 300 301 _GLIBCXX_DEBUG_ONLY(assert_valid();) 302 303 return; 304 } 305 306 node_pointer p_y = p_nd->m_p_prev_or_parent; 307 _GLIBCXX_DEBUG_ASSERT(p_y != NULL); 308 309 if (p_nd->m_p_next_sibling != NULL) 310 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y; 311 312 if (p_y->m_p_l_child == p_nd) 313 p_y->m_p_l_child = p_nd->m_p_next_sibling; 314 else 315 p_y->m_p_next_sibling = p_nd->m_p_next_sibling; 316 317 fix(p_y); 318 319 make_root_and_link(p_nd); 320 321 _GLIBCXX_DEBUG_ONLY(assert_valid();) 322 } 323 324PB_DS_CLASS_T_DEC 325inline void 326PB_DS_CLASS_C_DEC:: 327update_max(node_pointer p_nd) 328{ 329 if (m_p_max == NULL || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) 330 m_p_max = p_nd; 331} 332 333