r_erase_fn_imps.hpp revision 169691
111394Sswallace// -*- C++ -*- 211394Sswallace 311394Sswallace// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 411394Sswallace// 511394Sswallace// This file is part of the GNU ISO C++ Library. This library is free 611394Sswallace// software; you can redistribute it and/or modify it under the terms 711394Sswallace// of the GNU General Public License as published by the Free Software 811394Sswallace// Foundation; either version 2, or (at your option) any later 911394Sswallace// version. 1011394Sswallace 1111394Sswallace// This library is distributed in the hope that it will be useful, but 1211394Sswallace// WITHOUT ANY WARRANTY; without even the implied warranty of 1311394Sswallace// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411394Sswallace// General Public License for more details. 1511394Sswallace 1611394Sswallace// You should have received a copy of the GNU General Public License 1711394Sswallace// along with this library; see the file COPYING. If not, write to 1811394Sswallace// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1911394Sswallace// MA 02111-1307, USA. 2011394Sswallace 2111394Sswallace// As a special exception, you may use this file as part of a free 2211394Sswallace// software library without restriction. Specifically, if other files 2311394Sswallace// instantiate templates or use macros or inline functions from this 2411394Sswallace// file, or you compile this file and link it with other files to 2511394Sswallace// produce an executable, this file does not by itself cause the 2611394Sswallace// resulting executable to be covered by the GNU General Public 2711394Sswallace// License. This exception does not however invalidate any other 2811394Sswallace// reasons why the executable file might be covered by the GNU General 2911394Sswallace// Public License. 3011394Sswallace 3111394Sswallace// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3283366Sjulian 3383366Sjulian// Permission to use, copy, modify, sell, and distribute this software 3411394Sswallace// is hereby granted without fee, provided that the above copyright 3511394Sswallace// notice appears in all copies, and that both that copyright notice 3611394Sswallace// and this permission notice appear in supporting documentation. None 3711394Sswallace// of the above authors, nor IBM Haifa Research Laboratories, make any 3811394Sswallace// representation about the suitability of this software for any 3911394Sswallace// purpose. It is provided "as is" without express or implied 4011394Sswallace// warranty. 4111394Sswallace 4211394Sswallace/** 4311394Sswallace * @file r_erase_fn_imps.hpp 4428750Sbde * Contains an implementation class for bin_search_tree_. 4528750Sbde */ 4628750Sbde 4728750SbdePB_DS_CLASS_T_DEC 4811397Sswallaceinline void 4912662SdgPB_DS_CLASS_C_DEC:: 5011394Sswallaceactual_erase_node(node_pointer p_z) 5111394Sswallace{ 5214331Speter _GLIBCXX_DEBUG_ASSERT(m_size > 0); 5314331Speter --m_size; 5411394Sswallace _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); 5511397Sswallace p_z->~node(); 5611397Sswallace s_node_allocator.deallocate(p_z, 1); 5711397Sswallace} 5811397Sswallace 5911397SswallacePB_DS_CLASS_T_DEC 6011397Sswallaceinline void 6111397SswallacePB_DS_CLASS_C_DEC:: 6211394Sswallaceupdate_min_max_for_erased_node(node_pointer p_z) 6311394Sswallace{ 6411394Sswallace if (m_size == 1) 6583366Sjulian { 6641871Sbde m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; 6711394Sswallace return; 6811394Sswallace } 6911394Sswallace 7011394Sswallace if (m_p_head->m_p_left == p_z) 7111394Sswallace { 7211394Sswallace iterator it(p_z); 7311394Sswallace ++it; 7411394Sswallace m_p_head->m_p_left = it.m_p_nd; 7511394Sswallace } 7611394Sswallace else if (m_p_head->m_p_right == p_z) 7711394Sswallace { 7811394Sswallace iterator it(p_z); 7911394Sswallace --it; 8011394Sswallace m_p_head->m_p_right = it.m_p_nd; 8111394Sswallace } 8211394Sswallace} 8311394Sswallace 8411394SswallacePB_DS_CLASS_T_DEC 8511394Sswallacevoid 8611394SswallacePB_DS_CLASS_C_DEC:: 8792761Salfredclear() 8892761Salfred{ 8911394Sswallace _GLIBCXX_DEBUG_ONLY(assert_valid(true, true);) 9011394Sswallace clear_imp(m_p_head->m_p_parent); 9183366Sjulian m_size = 0; 9211394Sswallace initialize(); 9311394Sswallace _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();) 9483366Sjulian _GLIBCXX_DEBUG_ONLY(assert_valid(true, true);) 9511394Sswallace} 9620652Sbde 9792761SalfredPB_DS_CLASS_T_DEC 9820652Sbdevoid 9920652SbdePB_DS_CLASS_C_DEC:: 10011394Sswallaceclear_imp(node_pointer p_nd) 101{ 102 if (p_nd == NULL) 103 return; 104 clear_imp(p_nd->m_p_left); 105 clear_imp(p_nd->m_p_right); 106 p_nd->~Node(); 107 s_node_allocator.deallocate(p_nd, 1); 108} 109 110