The C and C++ Include Header Files

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


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_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_/constructors_destructor_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	typename PB_DS_CLASS_C_DEC::value_allocator
    45	PB_DS_CLASS_C_DEC::s_value_alloc;
    46	
    47	PB_DS_CLASS_T_DEC
    48	typename PB_DS_CLASS_C_DEC::metadata_allocator
    49	PB_DS_CLASS_C_DEC::s_metadata_alloc;
    50	
    51	PB_DS_CLASS_T_DEC
    52	PB_DS_CLASS_C_DEC::
    53	PB_DS_OV_TREE_NAME() :
    54	  m_a_values(0),
    55	  m_a_metadata(0),
    56	  m_end_it(0),
    57	  m_size(0)
    58	{ PB_DS_ASSERT_VALID((*this)) }
    59	
    60	PB_DS_CLASS_T_DEC
    61	PB_DS_CLASS_C_DEC::
    62	PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn) :
    63	  cmp_fn(r_cmp_fn),
    64	  m_a_values(0),
    65	  m_a_metadata(0),
    66	  m_end_it(0),
    67	  m_size(0)
    68	{ PB_DS_ASSERT_VALID((*this)) }
    69	
    70	PB_DS_CLASS_T_DEC
    71	PB_DS_CLASS_C_DEC::
    72	PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_nodeu) :
    73	  cmp_fn(r_cmp_fn),
    74	  node_update(r_nodeu),
    75	  m_a_values(0),
    76	  m_a_metadata(0),
    77	  m_end_it(0),
    78	  m_size(0)
    79	{ PB_DS_ASSERT_VALID((*this)) }
    80	
    81	PB_DS_CLASS_T_DEC
    82	PB_DS_CLASS_C_DEC::
    83	PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC& other) :
    84	#ifdef PB_DS_TREE_TRACE
    85	  trace_base(other),
    86	#endif
    87	  cmp_fn(other),
    88	  node_update(other),
    89	  m_a_values(0),
    90	  m_a_metadata(0),
    91	  m_end_it(0),
    92	  m_size(0)
    93	{
    94	  copy_from_ordered_range(other.begin(), other.end());
    95	  PB_DS_ASSERT_VALID((*this))
    96	}
    97	
    98	PB_DS_CLASS_T_DEC
    99	template<typename It>
   100	inline void
   101	PB_DS_CLASS_C_DEC::
   102	copy_from_range(It first_it, It last_it)
   103	{
   104	#ifdef PB_DS_DATA_TRUE_INDICATOR
   105	  typedef std::map<key_type, mapped_type, Cmp_Fn,
   106			   typename rebind_traits<_Alloc, value_type>::allocator_type>
   107	    map_type;
   108	#else
   109	  typedef std::set<key_type, Cmp_Fn,
   110			   typename rebind_traits<_Alloc, Key>::allocator_type>
   111	    map_type;
   112	#endif
   113	
   114	  map_type m(first_it, last_it);
   115	  copy_from_ordered_range(m.begin(), m.end());
   116	  PB_DS_ASSERT_VALID((*this))
   117	}
   118	
   119	PB_DS_CLASS_T_DEC
   120	template<typename It>
   121	void
   122	PB_DS_CLASS_C_DEC::
   123	copy_from_ordered_range(It first_it, It last_it)
   124	{
   125	  const size_type len = std::distance(first_it, last_it);
   126	  if (len == 0)
   127	    return;
   128	
   129	  value_vector a_values = s_value_alloc.allocate(len);
   130	  iterator target_it = a_values;
   131	  It source_it = first_it;
   132	  It source_end_it = last_it;
   133	
   134	  cond_dtor<size_type> cd(a_values, target_it, len);
   135	  while (source_it != source_end_it)
   136	    {
   137	      void* __v = const_cast<void*>(static_cast<const void*>(target_it));
   138	      new (__v) value_type(*source_it++);
   139	      ++target_it;
   140	    }
   141	
   142	  reallocate_metadata((node_update*)this, len);
   143	  cd.set_no_action();
   144	  m_a_values = a_values;
   145	  m_size = len;
   146	  m_end_it = m_a_values + m_size;
   147	  update(PB_DS_node_begin_imp(), (node_update*)this);
   148	
   149	#ifdef _GLIBCXX_DEBUG
   150	  for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
   151	    debug_base::insert_new(PB_DS_V2F(*dbg_it));
   152	#endif
   153	}
   154	
   155	PB_DS_CLASS_T_DEC
   156	template<typename It>
   157	void
   158	PB_DS_CLASS_C_DEC::
   159	copy_from_ordered_range(It first_it, It last_it, It other_first_it,
   160				It other_last_it)
   161	{
   162	  clear();
   163	  const size_type len = std::distance(first_it, last_it)
   164	    			 + std::distance(other_first_it, other_last_it);
   165	
   166	  value_vector a_values = s_value_alloc.allocate(len);
   167	
   168	  iterator target_it = a_values;
   169	  It source_it = first_it;
   170	  It source_end_it = last_it;
   171	
   172	  cond_dtor<size_type> cd(a_values, target_it, len);
   173	  while (source_it != source_end_it)
   174	    {
   175	      new (const_cast<void* >(static_cast<const void* >(target_it)))
   176		value_type(*source_it++);
   177	      ++target_it;
   178	    }
   179	
   180	  source_it = other_first_it;
   181	  source_end_it = other_last_it;
   182	
   183	  while (source_it != source_end_it)
   184	    {
   185	      new (const_cast<void* >(static_cast<const void* >(target_it)))
   186		value_type(*source_it++);
   187	      ++target_it;
   188	    }
   189	
   190	  reallocate_metadata((node_update* )this, len);
   191	  cd.set_no_action();
   192	  m_a_values = a_values;
   193	  m_size = len;
   194	  m_end_it = m_a_values + m_size;
   195	  update(PB_DS_node_begin_imp(), (node_update* )this);
   196	
   197	#ifdef _GLIBCXX_DEBUG
   198	  for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
   199	    debug_base::insert_new(PB_DS_V2F(*dbg_it));
   200	#endif
   201	}
   202	
   203	PB_DS_CLASS_T_DEC
   204	void
   205	PB_DS_CLASS_C_DEC::
   206	swap(PB_DS_CLASS_C_DEC& other)
   207	{
   208	  PB_DS_ASSERT_VALID((*this))
   209	  PB_DS_ASSERT_VALID(other)
   210	  value_swap(other);
   211	  std::swap(static_cast<cmp_fn&>(*this),
   212		    static_cast<cmp_fn&>(other));
   213	  std::swap(static_cast<traits_base&>(*this),
   214		    static_cast<traits_base&>(other));
   215	  PB_DS_ASSERT_VALID(other)
   216	  PB_DS_ASSERT_VALID((*this))
   217	}
   218	
   219	PB_DS_CLASS_T_DEC
   220	void
   221	PB_DS_CLASS_C_DEC::
   222	value_swap(PB_DS_CLASS_C_DEC& other)
   223	{
   224	  _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
   225	  std::swap(m_a_values, other.m_a_values);
   226	  std::swap(m_a_metadata, other.m_a_metadata);
   227	  std::swap(m_size, other.m_size);
   228	  std::swap(m_end_it, other.m_end_it);
   229	}
   230	
   231	PB_DS_CLASS_T_DEC
   232	PB_DS_CLASS_C_DEC::
   233	~PB_DS_OV_TREE_NAME()
   234	{
   235	  PB_DS_ASSERT_VALID((*this))
   236	  cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
   237	  reallocate_metadata((node_update*)this, 0);
   238	}
   239	
   240	PB_DS_CLASS_T_DEC
   241	inline void
   242	PB_DS_CLASS_C_DEC::
   243	update(node_iterator, null_node_update_pointer)
   244	{ }
   245	
   246	PB_DS_CLASS_T_DEC
   247	template<typename Node_Update>
   248	void
   249	PB_DS_CLASS_C_DEC::
   250	update(node_iterator nd_it, Node_Update* p_update)
   251	{
   252	  node_const_iterator end_it = PB_DS_node_end_imp();
   253	  if (nd_it != end_it)
   254	    {
   255	      update(nd_it.get_l_child(), p_update);
   256	      update(nd_it.get_r_child(), p_update);
   257	      node_update::operator()(nd_it, end_it);
   258	    }
   259	}
   260	#endif