Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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