1281494Sandrew// -*- C++ -*- 2281494Sandrew 3281494Sandrew// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4281494Sandrew// 5281494Sandrew// This file is part of the GNU ISO C++ Library. This library is free 6281494Sandrew// software; you can redistribute it and/or modify it under the terms 7281494Sandrew// of the GNU General Public License as published by the Free Software 8281494Sandrew// Foundation; either version 2, or (at your option) any later 9281494Sandrew// version. 10281494Sandrew 11281494Sandrew// This library is distributed in the hope that it will be useful, but 12281494Sandrew// WITHOUT ANY WARRANTY; without even the implied warranty of 13281494Sandrew// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14281494Sandrew// General Public License for more details. 15281494Sandrew 16281494Sandrew// You should have received a copy of the GNU General Public License 17281494Sandrew// along with this library; see the file COPYING. If not, write to 18281494Sandrew// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19281494Sandrew// MA 02111-1307, USA. 20281494Sandrew 21281494Sandrew// As a special exception, you may use this file as part of a free 22281494Sandrew// software library without restriction. Specifically, if other files 23281494Sandrew// instantiate templates or use macros or inline functions from this 24281494Sandrew// file, or you compile this file and link it with other files to 25281494Sandrew// produce an executable, this file does not by itself cause the 26281494Sandrew// resulting executable to be covered by the GNU General Public 27281494Sandrew// License. This exception does not however invalidate any other 28281494Sandrew// reasons why the executable file might be covered by the GNU General 29281494Sandrew// Public License. 30281494Sandrew 31281494Sandrew// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32281494Sandrew 33281494Sandrew// Permission to use, copy, modify, sell, and distribute this software 34281494Sandrew// is hereby granted without fee, provided that the above copyright 35281494Sandrew// notice appears in all copies, and that both that copyright notice 36284103Sandrew// and this permission notice appear in supporting documentation. None 37284103Sandrew// of the above authors, nor IBM Haifa Research Laboratories, make any 38285009Sbr// representation about the suitability of this software for any 39284103Sandrew// purpose. It is provided "as is" without express or implied 40291581Sandrew// warranty. 41291581Sandrew 42291581Sandrew/** 43291581Sandrew * @file insert_fn_imps.hpp 44291581Sandrew * Contains an implementation for rb_tree_. 45291581Sandrew */ 46291581Sandrew 47291581SandrewPB_DS_CLASS_T_DEC 48291581Sandrewinline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> 49291581SandrewPB_DS_CLASS_C_DEC:: 50291581Sandrewinsert(const_reference r_value) 51291581Sandrew{ 52291581Sandrew _GLIBCXX_DEBUG_ONLY(assert_valid();) 53291581Sandrew std::pair<point_iterator, bool> ins_pair = base_type::insert_leaf(r_value); 54291581Sandrew if (ins_pair.second == true) 55291581Sandrew { 56291581Sandrew ins_pair.first.m_p_nd->m_red = true; 57281494Sandrew _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();) 58281494Sandrew insert_fixup(ins_pair.first.m_p_nd); 59319204Sandrew } 60281494Sandrew 61284103Sandrew _GLIBCXX_DEBUG_ONLY(assert_valid();) 62281494Sandrew return ins_pair; 63319204Sandrew} 64319204Sandrew 65291581SandrewPB_DS_CLASS_T_DEC 66281494Sandrewinline void 67291581SandrewPB_DS_CLASS_C_DEC:: 68281494Sandrewinsert_fixup(node_pointer p_nd) 69281494Sandrew{ 70281494Sandrew _GLIBCXX_DEBUG_ASSERT(p_nd->m_red == true); 71288123Skib while (p_nd != base_type::m_p_head->m_p_parent && p_nd->m_p_parent->m_red) 72288123Skib { 73288123Skib if (p_nd->m_p_parent == p_nd->m_p_parent->m_p_parent->m_p_left) 74288123Skib { 75288123Skib node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_right; 76288123Skib if (p_y != NULL && p_y->m_red) 77288123Skib { 78291581Sandrew p_nd->m_p_parent->m_red = false; 79291581Sandrew p_y->m_red = false; 80281494Sandrew p_nd->m_p_parent->m_p_parent->m_red = true; 81284103Sandrew p_nd = p_nd->m_p_parent->m_p_parent; 82281494Sandrew } 83281494Sandrew else 84281494Sandrew { 85291581Sandrew if (p_nd == p_nd->m_p_parent->m_p_right) 86291581Sandrew { 87291581Sandrew p_nd = p_nd->m_p_parent; 88291581Sandrew base_type::rotate_left(p_nd); 89291581Sandrew } 90291581Sandrew p_nd->m_p_parent->m_red = false; 91291581Sandrew p_nd->m_p_parent->m_p_parent->m_red = true; 92291581Sandrew base_type::rotate_right(p_nd->m_p_parent->m_p_parent); 93291581Sandrew } 94281494Sandrew } 95292194Sandrew else 96292194Sandrew { 97292194Sandrew node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_left; 98292194Sandrew if (p_y != NULL && p_y->m_red) 99291581Sandrew { 100291581Sandrew p_nd->m_p_parent->m_red = false; 101291581Sandrew p_y->m_red = false; 102291581Sandrew p_nd->m_p_parent->m_p_parent->m_red = true; 103291581Sandrew p_nd = p_nd->m_p_parent->m_p_parent; 104291581Sandrew } 105292194Sandrew else 106292194Sandrew { 107292194Sandrew if (p_nd == p_nd->m_p_parent->m_p_left) 108291581Sandrew { 109291581Sandrew p_nd = p_nd->m_p_parent; 110291581Sandrew base_type::rotate_right(p_nd); 111284103Sandrew } 112284103Sandrew p_nd->m_p_parent->m_red = false; 113284103Sandrew p_nd->m_p_parent->m_p_parent->m_red = true; 114281494Sandrew base_type::rotate_left(p_nd->m_p_parent->m_p_parent); 115281494Sandrew } 116281494Sandrew } 117281494Sandrew } 118281494Sandrew 119288115Skib base_type::update_to_top(p_nd, (node_update* )this); 120281494Sandrew base_type::m_p_head->m_p_parent->m_red = false; 121281494Sandrew} 122281494Sandrew