insert_fn_imps.hpp revision 169691
1162485Sjulian// -*- C++ -*- 2162485Sjulian 3162485Sjulian// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4162485Sjulian// 5162485Sjulian// This file is part of the GNU ISO C++ Library. This library is free 6162485Sjulian// software; you can redistribute it and/or modify it under the terms 7162485Sjulian// of the GNU General Public License as published by the Free Software 8162485Sjulian// Foundation; either version 2, or (at your option) any later 9162485Sjulian// version. 10162485Sjulian 11162485Sjulian// This library is distributed in the hope that it will be useful, but 12162485Sjulian// WITHOUT ANY WARRANTY; without even the implied warranty of 13162485Sjulian// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14162485Sjulian// General Public License for more details. 15162485Sjulian 16162485Sjulian// You should have received a copy of the GNU General Public License 17162485Sjulian// along with this library; see the file COPYING. If not, write to 18162485Sjulian// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19162485Sjulian// MA 02111-1307, USA. 20162485Sjulian 21162485Sjulian// As a special exception, you may use this file as part of a free 22162485Sjulian// software library without restriction. Specifically, if other files 23162485Sjulian// instantiate templates or use macros or inline functions from this 24162485Sjulian// file, or you compile this file and link it with other files to 25162485Sjulian// produce an executable, this file does not by itself cause the 26162485Sjulian// resulting executable to be covered by the GNU General Public 27162485Sjulian// License. This exception does not however invalidate any other 28162485Sjulian// reasons why the executable file might be covered by the GNU General 29162485Sjulian// Public License. 30162485Sjulian 31162485Sjulian// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32162485Sjulian 33162485Sjulian// Permission to use, copy, modify, sell, and distribute this software 34162485Sjulian// is hereby granted without fee, provided that the above copyright 35162485Sjulian// notice appears in all copies, and that both that copyright notice 36162485Sjulian// and this permission notice appear in supporting documentation. None 37162485Sjulian// of the above authors, nor IBM Haifa Research Laboratories, make any 38162485Sjulian// representation about the suitability of this software for any 39162485Sjulian// purpose. It is provided "as is" without express or implied 40162485Sjulian// warranty. 41162485Sjulian 42162485Sjulian/** 43162485Sjulian * @file insert_fn_imps.hpp 44162485Sjulian * Contains an implementation for thin_heap_. 45162485Sjulian */ 46162485Sjulian 47162485SjulianPB_DS_CLASS_T_DEC 48162485Sjulianinline typename PB_DS_CLASS_C_DEC::point_iterator 49162485SjulianPB_DS_CLASS_C_DEC:: 50162485Sjulianpush(const_reference r_val) 51162485Sjulian{ 52162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 53162485Sjulian 54162485Sjulian node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 55162485Sjulian 56162485Sjulian p_nd->m_metadata = 0; 57162485Sjulian 58162485Sjulian p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL; 59162485Sjulian 60162485Sjulian if (base_type::m_p_root == NULL) 61162485Sjulian { 62162485Sjulian p_nd->m_p_next_sibling = NULL; 63162485Sjulian 64162485Sjulian m_p_max = base_type::m_p_root = p_nd; 65162485Sjulian 66162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 67162485Sjulian 68162485Sjulian return point_iterator(p_nd); 69162485Sjulian } 70162485Sjulian 71162485Sjulian p_nd->m_p_next_sibling = base_type::m_p_root; 72162485Sjulian 73162485Sjulian base_type::m_p_root->m_p_prev_or_parent = NULL; 74162485Sjulian 75162485Sjulian base_type::m_p_root = p_nd; 76162485Sjulian 77162485Sjulian update_max(p_nd); 78162485Sjulian 79162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 80162485Sjulian 81162485Sjulian return point_iterator(p_nd); 82162485Sjulian} 83162485Sjulian 84162485SjulianPB_DS_CLASS_T_DEC 85162485Sjulianinline void 86162485SjulianPB_DS_CLASS_C_DEC:: 87162485Sjulianmake_root(node_pointer p_nd) 88162485Sjulian{ 89162485Sjulian p_nd->m_metadata = 90162485Sjulian p_nd->m_p_l_child == NULL? 91162485Sjulian 0 : 92162485Sjulian 1 + p_nd->m_p_l_child->m_metadata; 93162485Sjulian} 94162485Sjulian 95162485SjulianPB_DS_CLASS_T_DEC 96162485Sjulianinline void 97162485SjulianPB_DS_CLASS_C_DEC:: 98162485Sjulianmake_root_and_link(node_pointer p_nd) 99162485Sjulian{ 100162485Sjulian make_root(p_nd); 101162485Sjulian 102162485Sjulian p_nd->m_p_prev_or_parent = NULL; 103162485Sjulian 104162485Sjulian p_nd->m_p_next_sibling = base_type::m_p_root; 105162485Sjulian 106162485Sjulian if (base_type::m_p_root != NULL) 107162485Sjulian base_type::m_p_root->m_p_prev_or_parent = NULL; 108162485Sjulian 109162485Sjulian base_type::m_p_root = p_nd; 110162485Sjulian 111162485Sjulian update_max(p_nd); 112162485Sjulian} 113162485Sjulian 114162485SjulianPB_DS_CLASS_T_DEC 115162485Sjulianinline void 116162485SjulianPB_DS_CLASS_C_DEC:: 117162485Sjulianfix(node_pointer p_y) 118162485Sjulian{ 119162485Sjulian while (true) 120162485Sjulian { 121162485Sjulian if (p_y->m_p_prev_or_parent == NULL) 122162485Sjulian { 123162485Sjulian fix_root(p_y); 124162485Sjulian 125162485Sjulian return; 126162485Sjulian } 127162485Sjulian else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == NULL) 128162485Sjulian { 129162485Sjulian if (p_y->m_p_l_child != NULL) 130162485Sjulian { 131162485Sjulian fix_sibling_rank_1_unmarked(p_y); 132162485Sjulian 133162485Sjulian return; 134162485Sjulian } 135162485Sjulian 136162485Sjulian fix_sibling_rank_1_marked(p_y); 137162485Sjulian 138162485Sjulian p_y = p_y->m_p_prev_or_parent; 139162485Sjulian } 140162485Sjulian else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1) 141162485Sjulian { 142162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != NULL); 143162485Sjulian 144162485Sjulian if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2) 145162485Sjulian { 146162485Sjulian fix_sibling_general_unmarked(p_y); 147162485Sjulian 148162485Sjulian return; 149162485Sjulian } 150162485Sjulian 151162485Sjulian fix_sibling_general_marked(p_y); 152162485Sjulian 153162485Sjulian p_y = p_y->m_p_prev_or_parent; 154162485Sjulian } 155162485Sjulian else if ((p_y->m_p_l_child == NULL&& 156162485Sjulian p_y->m_metadata == 2) ||(p_y->m_p_l_child != NULL&& 157162485Sjulian p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3)) 158162485Sjulian { 159162485Sjulian node_pointer p_z = p_y->m_p_prev_or_parent; 160162485Sjulian 161162485Sjulian fix_child(p_y); 162162485Sjulian 163162485Sjulian p_y = p_z; 164162485Sjulian } 165162485Sjulian else 166162485Sjulian return; 167162485Sjulian } 168162485Sjulian} 169162485Sjulian 170162485SjulianPB_DS_CLASS_T_DEC 171162485Sjulianinline void 172162485SjulianPB_DS_CLASS_C_DEC:: 173162485Sjulianfix_root(node_pointer p_y) 174162485Sjulian{ 175162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == NULL); 176162485Sjulian 177162485Sjulian make_root(p_y); 178162485Sjulian 179162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, true);) 180162485Sjulian } 181162485Sjulian 182162485SjulianPB_DS_CLASS_T_DEC 183162485Sjulianinline void 184162485SjulianPB_DS_CLASS_C_DEC:: 185162485Sjulianfix_sibling_rank_1_unmarked(node_pointer p_y) 186162485Sjulian{ 187162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 188162485Sjulian 189162485Sjulian _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;) 190162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_w != NULL); 191162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == NULL); 192162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == NULL); 193162485Sjulian 194162485Sjulian p_y->m_p_next_sibling = p_y->m_p_l_child; 195162485Sjulian 196162485Sjulian p_y->m_p_next_sibling->m_p_prev_or_parent = p_y; 197162485Sjulian 198162485Sjulian p_y->m_p_l_child = NULL; 199162485Sjulian 200162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 201162485Sjulian } 202162485Sjulian 203162485SjulianPB_DS_CLASS_T_DEC 204162485Sjulianinline void 205162485SjulianPB_DS_CLASS_C_DEC:: 206162485Sjulianfix_sibling_rank_1_marked(node_pointer p_y) 207162485Sjulian{ 208162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 209162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == NULL); 210162485Sjulian 211162485Sjulian p_y->m_metadata = 0; 212162485Sjulian 213162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 214162485Sjulian } 215162485Sjulian 216162485SjulianPB_DS_CLASS_T_DEC 217162485Sjulianinline void 218162485SjulianPB_DS_CLASS_C_DEC:: 219162485Sjulianfix_sibling_general_unmarked(node_pointer p_y) 220162485Sjulian{ 221162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 222162485Sjulian 223162485Sjulian node_pointer p_w = p_y->m_p_l_child; 224162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_w != NULL); 225162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL); 226162485Sjulian 227162485Sjulian p_y->m_p_l_child = p_w->m_p_next_sibling; 228162485Sjulian p_w->m_p_next_sibling->m_p_prev_or_parent = p_y; 229162485Sjulian 230162485Sjulian p_w->m_p_next_sibling = p_y->m_p_next_sibling; 231162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL); 232162485Sjulian p_w->m_p_next_sibling->m_p_prev_or_parent = p_w; 233162485Sjulian 234162485Sjulian p_y->m_p_next_sibling = p_w; 235162485Sjulian p_w->m_p_prev_or_parent = p_y; 236162485Sjulian 237162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 238162485Sjulian } 239162485Sjulian 240162485SjulianPB_DS_CLASS_T_DEC 241162485Sjulianinline void 242162485SjulianPB_DS_CLASS_C_DEC:: 243162485Sjulianfix_sibling_general_marked(node_pointer p_y) 244162485Sjulian{ 245162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 246162485Sjulian 247162485Sjulian --p_y->m_metadata; 248162485Sjulian 249162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);) 250162485Sjulian } 251162485Sjulian 252162485SjulianPB_DS_CLASS_T_DEC 253162485Sjulianinline void 254162485SjulianPB_DS_CLASS_C_DEC:: 255162485Sjulianfix_child(node_pointer p_y) 256162485Sjulian{ 257162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL); 258162485Sjulian 259162485Sjulian if (p_y->m_p_next_sibling != NULL) 260162485Sjulian p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent; 261162485Sjulian 262162485Sjulian if (p_y->m_p_prev_or_parent->m_p_l_child == p_y) 263162485Sjulian p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling; 264162485Sjulian else 265162485Sjulian p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling; 266162485Sjulian 267162485Sjulian make_root_and_link(p_y); 268162485Sjulian} 269162485Sjulian 270162485SjulianPB_DS_CLASS_T_DEC 271162485Sjulianvoid 272162485SjulianPB_DS_CLASS_C_DEC:: 273162485Sjulianmodify(point_iterator it, const_reference r_new_val) 274162485Sjulian{ 275162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 276162485Sjulian node_pointer p_nd = it.m_p_nd; 277162485Sjulian 278162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 279162485Sjulian 280162485Sjulian const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value); 281162485Sjulian 282162485Sjulian p_nd->m_value = r_new_val; 283162485Sjulian 284162485Sjulian if (smaller) 285162485Sjulian { 286162485Sjulian remove_node(p_nd); 287162485Sjulian 288162485Sjulian p_nd->m_p_l_child = NULL; 289162485Sjulian 290162485Sjulian make_root_and_link(p_nd); 291162485Sjulian 292162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 293162485Sjulian 294162485Sjulian return; 295162485Sjulian } 296162485Sjulian 297162485Sjulian if (p_nd->m_p_prev_or_parent == NULL) 298162485Sjulian { 299162485Sjulian update_max(p_nd); 300162485Sjulian 301162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 302162485Sjulian 303162485Sjulian return; 304162485Sjulian } 305162485Sjulian 306162485Sjulian node_pointer p_y = p_nd->m_p_prev_or_parent; 307162485Sjulian _GLIBCXX_DEBUG_ASSERT(p_y != NULL); 308162485Sjulian 309162485Sjulian if (p_nd->m_p_next_sibling != NULL) 310162485Sjulian p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y; 311162485Sjulian 312162485Sjulian if (p_y->m_p_l_child == p_nd) 313162485Sjulian p_y->m_p_l_child = p_nd->m_p_next_sibling; 314162485Sjulian else 315162485Sjulian p_y->m_p_next_sibling = p_nd->m_p_next_sibling; 316162485Sjulian 317162485Sjulian fix(p_y); 318162485Sjulian 319162485Sjulian make_root_and_link(p_nd); 320162485Sjulian 321162485Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid();) 322162485Sjulian } 323162485Sjulian 324162485SjulianPB_DS_CLASS_T_DEC 325162485Sjulianinline void 326162485SjulianPB_DS_CLASS_C_DEC:: 327162485Sjulianupdate_max(node_pointer p_nd) 328162485Sjulian{ 329162485Sjulian if (m_p_max == NULL || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) 330162485Sjulian m_p_max = p_nd; 331162485Sjulian} 332162485Sjulian 333162485Sjulian