13123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// -*- C++ -*- 23123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 33123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 43123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// 53123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// This file is part of the GNU ISO C++ Library. This library is free 63123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// software; you can redistribute it and/or modify it under the terms 73123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// of the GNU General Public License as published by the Free Software 83123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Foundation; either version 3, or (at your option) any later 93123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// version. 103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// This library is distributed in the hope that it will be useful, but 123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// WITHOUT ANY WARRANTY; without even the implied warranty of 133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// General Public License for more details. 153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Under Section 7 of GPL version 3, you are granted additional 173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// permissions described in the GCC Runtime Library Exception, version 183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// 3.1, as published by the Free Software Foundation. 193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// You should have received a copy of the GNU General Public License and 213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// a copy of the GCC Runtime Library Exception along with this program; 223123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 233123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// <http://www.gnu.org/licenses/>. 243123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 253123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 263123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 273123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// Permission to use, copy, modify, sell, and distribute this software 283123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// is hereby granted without fee, provided that the above copyright 293123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// notice appears in all copies, and that both that copyright notice 303123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// and this permission notice appear in supporting documentation. None 313123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// of the above authors, nor IBM Haifa Research Laboratories, make any 323123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// representation about the suitability of this software for any 333123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// purpose. It is provided "as is" without express or implied 343123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh// warranty. 353123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 363123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh/** 373123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh * @file rc_binomial_heap_/debug_fn_imps.hpp 383123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh * Contains an implementation for rc_binomial_heap_. 393123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh */ 403123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 413123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#ifdef _GLIBCXX_DEBUG 423123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 433123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_T_DEC 443123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehvoid 453123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_C_DEC:: 463123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehassert_valid(const char* __file, int __line) const 473123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh{ 483123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh base_type::assert_valid(false, __file, __line); 493123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (!base_type::empty()) 503123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 513123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(base_type::m_p_max != 0); 523123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh base_type::assert_max(__file, __line); 533123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh } 543123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 553123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh m_rc.assert_valid(__file, __line); 563123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 573123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (m_rc.empty()) 583123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 593123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh base_type::assert_valid(true, __file, __line); 603123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(next_2_pointer(base_type::m_p_root) == 0); 613123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return; 623123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh } 633123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 643123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh node_const_pointer p_nd = next_2_pointer(base_type::m_p_root); 653123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh typename rc_t::const_iterator it = m_rc.end(); 663123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh --it; 673123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 683123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh while (p_nd != 0) 693123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh { 703123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(*it == p_nd); 713123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh node_const_pointer p_next = p_nd->m_p_next_sibling; 723123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(p_next != 0); 733123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(p_nd->m_metadata == p_next->m_metadata); 743123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(p_next->m_p_next_sibling == 0 || 753123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh p_next->m_metadata < p_next->m_p_next_sibling->m_metadata); 763123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 773123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh --it; 783123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh p_nd = next_2_pointer(next_after_0_pointer(p_nd)); 793123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh } 803123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh PB_DS_DEBUG_VERIFY(it + 1 == m_rc.begin()); 813123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh} 823123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 833123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_T_DEC 843123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehtypename PB_DS_CLASS_C_DEC::node_const_pointer 853123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_C_DEC:: 863123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehnext_2_pointer(node_const_pointer p_nd) 873123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh{ 883123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_nd == 0) 893123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return 0; 903123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 913123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh node_pointer p_next = p_nd->m_p_next_sibling; 923123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 933123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_next == 0) 943123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return 0; 953123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 963123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_nd->m_metadata == p_next->m_metadata) 973123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return p_nd; 983123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 993123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return next_2_pointer(p_next); 1003123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh} 1013123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1023123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_T_DEC 1033123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehtypename PB_DS_CLASS_C_DEC::node_const_pointer 1043123853ede6209e485fb7110bdcd38aea0f33d23Andrew HsiehPB_DS_CLASS_C_DEC:: 1053123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsiehnext_after_0_pointer(node_const_pointer p_nd) 1063123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh{ 1073123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_nd == 0) 1083123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return 0; 1093123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1103123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh node_pointer p_next = p_nd->m_p_next_sibling; 1113123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1123123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_next == 0) 1133123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return 0; 1143123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1153123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh if (p_nd->m_metadata < p_next->m_metadata) 1163123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return p_next; 1173123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1183123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh return next_after_0_pointer(p_next); 1193123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh} 1203123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh 1213123853ede6209e485fb7110bdcd38aea0f33d23Andrew Hsieh#endif 122