The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/splay_tree_/splay_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 splay_tree_/splay_fn_imps.hpp
    38	 * Contains an implementation class for splay_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	splay(node_pointer p_nd)
    47	{
    48	  while (p_nd->m_p_parent != base_type::m_p_head)
    49	    {
    50	#ifdef _GLIBCXX_DEBUG
    51	      {
    52		node_pointer p_head = base_type::m_p_head;
    53		assert_special_imp(p_head, __FILE__, __LINE__);
    54	      }
    55	#endif
    56	
    57	      PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
    58	
    59	      if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head)
    60		{
    61		  base_type::rotate_parent(p_nd);
    62		  _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent);
    63		}
    64	      else
    65		{
    66		  const node_pointer p_parent = p_nd->m_p_parent;
    67		  const node_pointer p_grandparent = p_parent->m_p_parent;
    68	
    69	#ifdef _GLIBCXX_DEBUG
    70		  const size_type total =
    71		    base_type::recursive_count(p_grandparent);
    72		  _GLIBCXX_DEBUG_ASSERT(total >= 3);
    73	#endif
    74	
    75		  if (p_parent->m_p_left == p_nd &&
    76		      p_grandparent->m_p_right == p_parent)
    77		    splay_zig_zag_left(p_nd, p_parent, p_grandparent);
    78		  else if (p_parent->m_p_right == p_nd &&
    79			   p_grandparent->m_p_left == p_parent)
    80		    splay_zig_zag_right(p_nd, p_parent, p_grandparent);
    81		  else if (p_parent->m_p_left == p_nd &&
    82			   p_grandparent->m_p_left == p_parent)
    83		    splay_zig_zig_left(p_nd, p_parent, p_grandparent);
    84		  else
    85		    splay_zig_zig_right(p_nd, p_parent, p_grandparent);
    86		  _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd));
    87		}
    88	
    89	      PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
    90	    }
    91	}
    92	
    93	PB_DS_CLASS_T_DEC
    94	inline void
    95	PB_DS_CLASS_C_DEC::
    96	splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent,
    97			   node_pointer p_grandparent)
    98	{
    99	  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
   100	  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
   101	
   102	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
   103	
   104	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
   105				p_grandparent->m_p_right == p_parent);
   106	
   107	  splay_zz_start(p_nd, p_parent, p_grandparent);
   108	
   109	  node_pointer p_b = p_nd->m_p_right;
   110	  node_pointer p_c = p_nd->m_p_left;
   111	
   112	  p_nd->m_p_right = p_parent;
   113	  p_parent->m_p_parent = p_nd;
   114	
   115	  p_nd->m_p_left = p_grandparent;
   116	  p_grandparent->m_p_parent = p_nd;
   117	
   118	  p_parent->m_p_left = p_b;
   119	  if (p_b != 0)
   120	    p_b->m_p_parent = p_parent;
   121	
   122	  p_grandparent->m_p_right = p_c;
   123	  if (p_c != 0)
   124	    p_c->m_p_parent = p_grandparent;
   125	
   126	  splay_zz_end(p_nd, p_parent, p_grandparent);
   127	}
   128	
   129	PB_DS_CLASS_T_DEC
   130	inline void
   131	PB_DS_CLASS_C_DEC::
   132	splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent,
   133			    node_pointer p_grandparent)
   134	{
   135	  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
   136	  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
   137	
   138	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
   139	
   140	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
   141		  		p_grandparent->m_p_left == p_parent);
   142	
   143	  splay_zz_start(p_nd, p_parent, p_grandparent);
   144	
   145	  node_pointer p_b = p_nd->m_p_left;
   146	  node_pointer p_c = p_nd->m_p_right;
   147	
   148	  p_nd->m_p_left = p_parent;
   149	  p_parent->m_p_parent = p_nd;
   150	
   151	  p_nd->m_p_right = p_grandparent;
   152	  p_grandparent->m_p_parent = p_nd;
   153	
   154	  p_parent->m_p_right = p_b;
   155	  if (p_b != 0)
   156	    p_b->m_p_parent = p_parent;
   157	
   158	  p_grandparent->m_p_left = p_c;
   159	  if (p_c != 0)
   160	    p_c->m_p_parent = p_grandparent;
   161	
   162	  splay_zz_end(p_nd, p_parent, p_grandparent);
   163	}
   164	
   165	PB_DS_CLASS_T_DEC
   166	inline void
   167	PB_DS_CLASS_C_DEC::
   168	splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent,
   169			   node_pointer p_grandparent)
   170	{
   171	  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
   172	  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
   173	
   174	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
   175	
   176	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
   177			     p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
   178	
   179	  splay_zz_start(p_nd, p_parent, p_grandparent);
   180	
   181	  node_pointer p_b = p_nd->m_p_right;
   182	  node_pointer p_c = p_parent->m_p_right;
   183	
   184	  p_nd->m_p_right = p_parent;
   185	  p_parent->m_p_parent = p_nd;
   186	
   187	  p_parent->m_p_right = p_grandparent;
   188	  p_grandparent->m_p_parent = p_parent;
   189	
   190	  p_parent->m_p_left = p_b;
   191	  if (p_b != 0)
   192	    p_b->m_p_parent = p_parent;
   193	
   194	  p_grandparent->m_p_left = p_c;
   195	  if (p_c != 0)
   196	    p_c->m_p_parent = p_grandparent;
   197	
   198	  splay_zz_end(p_nd, p_parent, p_grandparent);
   199	}
   200	
   201	PB_DS_CLASS_T_DEC
   202	inline void
   203	PB_DS_CLASS_C_DEC::
   204	splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent,
   205			    node_pointer p_grandparent)
   206	{
   207	  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
   208	  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
   209	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
   210	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
   211			  p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
   212	
   213	  splay_zz_start(p_nd, p_parent, p_grandparent);
   214	
   215	  node_pointer p_b = p_nd->m_p_left;
   216	  node_pointer p_c = p_parent->m_p_left;
   217	
   218	  p_nd->m_p_left = p_parent;
   219	  p_parent->m_p_parent = p_nd;
   220	
   221	  p_parent->m_p_left = p_grandparent;
   222	  p_grandparent->m_p_parent = p_parent;
   223	
   224	  p_parent->m_p_right = p_b;
   225	  if (p_b != 0)
   226	    p_b->m_p_parent = p_parent;
   227	
   228	  p_grandparent->m_p_right = p_c;
   229	  if (p_c != 0)
   230	    p_c->m_p_parent = p_grandparent;
   231	
   232	  base_type::update_to_top(p_grandparent, (node_update*)this);
   233	  splay_zz_end(p_nd, p_parent, p_grandparent);
   234	}
   235	
   236	PB_DS_CLASS_T_DEC
   237	inline void
   238	PB_DS_CLASS_C_DEC::
   239	splay_zz_start(node_pointer p_nd,
   240	#ifdef _GLIBCXX_DEBUG
   241		       node_pointer p_parent,
   242	#else
   243		       node_pointer /*p_parent*/,
   244	#endif
   245		       node_pointer p_grandparent)
   246	{
   247	  _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
   248	  _GLIBCXX_DEBUG_ASSERT(p_parent != 0);
   249	  _GLIBCXX_DEBUG_ASSERT(p_grandparent != 0);
   250	
   251	  const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head;
   252	
   253	  if (grandparent_head)
   254	    {
   255	      base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent;
   256	      p_nd->m_p_parent = base_type::m_p_head;
   257	      return;
   258	    }
   259	
   260	  node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
   261	
   262	  p_nd->m_p_parent = p_greatgrandparent;
   263	
   264	  if (p_grandparent == p_greatgrandparent->m_p_left)
   265	    p_greatgrandparent->m_p_left = p_nd;
   266	  else
   267	    p_greatgrandparent->m_p_right = p_nd;
   268	}
   269	
   270	PB_DS_CLASS_T_DEC
   271	inline void
   272	PB_DS_CLASS_C_DEC::
   273	splay_zz_end(node_pointer p_nd, node_pointer p_parent,
   274		     node_pointer p_grandparent)
   275	{
   276	  if (p_nd->m_p_parent == base_type::m_p_head)
   277	    base_type::m_p_head->m_p_parent = p_nd;
   278	
   279	  this->apply_update(p_grandparent, (node_update*)this);
   280	  this->apply_update(p_parent, (node_update*)this);
   281	  this->apply_update(p_nd, (node_update*)this);
   282	  PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
   283	}
   284	#endif