The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2005-2021 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 3, 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	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
    26	
    27	// Permission to use, copy, modify, sell, and distribute this software
    28	// is hereby granted without fee, provided that the above copyright
    29	// notice appears in all copies, and that both that copyright notice
    30	// and this permission notice appear in supporting documentation. None
    31	// of the above authors, nor IBM Haifa Research Laboratories, make any
    32	// representation about the suitability of this software for any
    33	// purpose. It is provided "as is" without express or implied
    34	// warranty.
    35	
    36	/**
    37	 * @file ov_tree_map_/erase_fn_imps.hpp
    38	 * Contains an implementation class for ov_tree_.
    39	 */
    40	
    41	#ifdef PB_DS_CLASS_C_DEC
    42	
    43	PB_DS_CLASS_T_DEC
    44	void
    45	PB_DS_CLASS_C_DEC::
    46	clear()
    47	{
    48	  PB_DS_ASSERT_VALID((*this))
    49	  if (m_size == 0)
    50	    {
    51	      return;
    52	    }
    53	  else
    54	    {
    55	      reallocate_metadata((node_update* )this, 0);
    56	      cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
    57	    }
    58	
    59	  _GLIBCXX_DEBUG_ONLY(debug_base::clear();)
    60	  m_a_values = 0;
    61	  m_size = 0;
    62	  m_end_it = m_a_values;
    63	  PB_DS_ASSERT_VALID((*this))
    64	}
    65	
    66	PB_DS_CLASS_T_DEC
    67	template<typename Pred>
    68	inline typename PB_DS_CLASS_C_DEC::size_type
    69	PB_DS_CLASS_C_DEC::
    70	erase_if(Pred pred)
    71	{
    72	  PB_DS_ASSERT_VALID((*this))
    73	
    74	#ifdef PB_DS_REGRESSION
    75	    typename _Alloc::group_adjustor adjust(m_size);
    76	#endif
    77	
    78	  size_type new_size = 0;
    79	  size_type num_val_ersd = 0;
    80	
    81	  for (iterator source_it = begin(); source_it != m_end_it; ++source_it)
    82	    if (!pred(*source_it))
    83	      ++new_size;
    84	    else
    85	      ++num_val_ersd;
    86	
    87	  if (new_size == 0)
    88	    {
    89	      clear();
    90	      return num_val_ersd;
    91	    }
    92	
    93	  value_vector a_new_values = s_value_alloc.allocate(new_size);
    94	  iterator target_it = a_new_values;
    95	  cond_dtor<size_type> cd(a_new_values, target_it, new_size);
    96	  _GLIBCXX_DEBUG_ONLY(debug_base::clear());
    97	  for (iterator source_it = begin(); source_it != m_end_it; ++source_it)
    98	    {
    99	      if (!pred(*source_it))
   100		{
   101		  new (const_cast<void*>(static_cast<const void*>(target_it)))
   102		    value_type(*source_it);
   103	
   104		  _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it)));
   105		  ++target_it;
   106		}
   107	    }
   108	
   109	  reallocate_metadata((node_update*)this, new_size);
   110	  cd.set_no_action();
   111	
   112	  {
   113	    cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
   114	  }
   115	
   116	  m_a_values = a_new_values;
   117	  m_size = new_size;
   118	  m_end_it = target_it;
   119	  update(node_begin(), (node_update*)this);
   120	  PB_DS_ASSERT_VALID((*this))
   121	  return num_val_ersd;
   122	}
   123	
   124	PB_DS_CLASS_T_DEC
   125	template<typename It>
   126	It
   127	PB_DS_CLASS_C_DEC::
   128	erase_imp(It it)
   129	{
   130	  PB_DS_ASSERT_VALID((*this))
   131	  if (it == end())
   132	    return end();
   133	
   134	  PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(*it))
   135	
   136	#ifdef PB_DS_REGRESSION
   137	    typename _Alloc::group_adjustor adjust(m_size);
   138	#endif
   139	
   140	  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   141	  value_vector a_values = s_value_alloc.allocate(m_size - 1);
   142	  iterator source_it = begin();
   143	  iterator source_end_it = end();
   144	  iterator target_it = a_values;
   145	  iterator ret_it = end();
   146	
   147	  cond_dtor<size_type> cd(a_values, target_it, m_size - 1);
   148	
   149	  _GLIBCXX_DEBUG_ONLY(size_type cnt = 0;)
   150	
   151	  while (source_it != source_end_it)
   152	    {
   153	      if (source_it != it)
   154		{
   155		  _GLIBCXX_DEBUG_ONLY(++cnt;)
   156		  _GLIBCXX_DEBUG_ASSERT(cnt != m_size);
   157		  new (const_cast<void*>(static_cast<const void*>(target_it)))
   158		      value_type(*source_it);
   159	
   160		  ++target_it;
   161		}
   162	      else
   163		ret_it = target_it;
   164	    ++source_it;
   165	    }
   166	
   167	  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
   168	  reallocate_metadata((node_update*)this, m_size - 1);
   169	  cd.set_no_action();
   170	  _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(*it));)
   171	  {
   172	    cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
   173	  }
   174	
   175	  m_a_values = a_values;
   176	  --m_size;
   177	  m_end_it = m_a_values + m_size;
   178	  update(node_begin(), (node_update*)this);
   179	  PB_DS_ASSERT_VALID((*this))
   180	  return It(ret_it);
   181	}
   182	
   183	PB_DS_CLASS_T_DEC
   184	bool
   185	PB_DS_CLASS_C_DEC::
   186	erase(key_const_reference r_key)
   187	{
   188	  point_iterator it = find(r_key);
   189	  if (it == end())
   190	    return false;
   191	  erase(it);
   192	  return true;
   193	}
   194	#endif