detail/splay_tree_/splay_fn_imps.hpp

64 	    const node_pointer p_parent = p_nd->m_p_parent;
65 	    const node_pointer p_grandparent = p_parent->m_p_parent;
74 	    if (p_parent->m_p_left == p_nd&&
75 		p_grandparent->m_p_right == p_parent)
76 	      splay_zig_zag_left(p_nd, p_parent, p_grandparent);
77 	    else if (p_parent->m_p_right == p_nd&&
78 		     p_grandparent->m_p_left == p_parent)
79 	      splay_zig_zag_right(p_nd, p_parent, p_grandparent);
80 	    else if (p_parent->m_p_left == p_nd&&
81 		     p_grandparent->m_p_left == p_parent)
82 	      splay_zig_zig_left(p_nd, p_parent, p_grandparent);
84 	      splay_zig_zig_right(p_nd, p_parent, p_grandparent);
97 splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
99   PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
100   PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
104     PB_ASSOC_DBG_ASSERT(p_parent->m_p_left == p_nd&&
105 			p_grandparent->m_p_right == p_parent);
107   splay_zz_start(p_nd, p_parent, p_grandparent);
112   p_nd->m_p_right = p_parent;
113   p_parent->m_p_parent = p_nd;
118   p_parent->m_p_left = p_b;
120     p_b->m_p_parent = p_parent;
126   splay_zz_end(p_nd, p_parent, p_grandparent);
132 splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
134   PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
135   PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
139     PB_ASSOC_DBG_ASSERT(p_parent->m_p_right == p_nd&&
140 			p_grandparent->m_p_left == p_parent);
142   splay_zz_start(p_nd, p_parent, p_grandparent);
147   p_nd->m_p_left = p_parent;
148   p_parent->m_p_parent = p_nd;
153   p_parent->m_p_right = p_b;
155     p_b->m_p_parent = p_parent;
161   splay_zz_end(p_nd, p_parent, p_grandparent);
167 splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
169   PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
170   PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
174     PB_ASSOC_DBG_ASSERT(p_parent->m_p_left == p_nd&&
177   splay_zz_start(p_nd, p_parent, p_grandparent);
180   node_pointer p_c = p_parent->m_p_right;
182   p_nd->m_p_right = p_parent;
183   p_parent->m_p_parent = p_nd;
185   p_parent->m_p_right = p_grandparent;
186   p_grandparent->m_p_parent = p_parent;
188   p_parent->m_p_left = p_b;
190     p_b->m_p_parent = p_parent;
196   splay_zz_end(p_nd, p_parent, p_grandparent);
202 splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
204   PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
205   PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
209     PB_ASSOC_DBG_ASSERT(p_parent->m_p_right == p_nd&&
212   splay_zz_start(p_nd, p_parent, p_grandparent);
215   node_pointer p_c = p_parent->m_p_left;
217   p_nd->m_p_left = p_parent;
218   p_parent->m_p_parent = p_nd;
220   p_parent->m_p_left = p_grandparent;
221   p_grandparent->m_p_parent = p_parent;
223   p_parent->m_p_right = p_b;
225     p_b->m_p_parent = p_parent;
234   splay_zz_end(p_nd, p_parent, p_grandparent);
242 	       node_pointer p_parent,
244 	       node_pointer /*p_parent*/,
249   PB_ASSOC_DBG_ASSERT(p_parent != NULL);
278 splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
284   apply_update(p_parent, (Node_Updator* )this);