detail/thin_heap_/insert_fn_imps.hpp

117 fix(node_pointer p_y)
121       if (p_y->m_p_prev_or_parent == NULL)
123 	  fix_root(p_y);
127       else if (p_y->m_metadata == 1&&  p_y->m_p_next_sibling == NULL)
129 	  if (p_y->m_p_l_child != NULL)
131 	      fix_sibling_rank_1_unmarked(p_y);
136 	  fix_sibling_rank_1_marked(p_y);
138 	  p_y = p_y->m_p_prev_or_parent;
140       else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1)
142 	  _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != NULL);
144 	  if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2)
146 	      fix_sibling_general_unmarked(p_y);
151 	  fix_sibling_general_marked(p_y);
153 	  p_y = p_y->m_p_prev_or_parent;
155       else if ((p_y->m_p_l_child == NULL&&
156                 p_y->m_metadata == 2) ||(p_y->m_p_l_child != NULL&&
157 					 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3))
159 	  node_pointer p_z = p_y->m_p_prev_or_parent;
161 	  fix_child(p_y);
163 	  p_y = p_z;
173 fix_root(node_pointer p_y)
175   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == NULL);
177   make_root(p_y);
179   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, true);)
185 fix_sibling_rank_1_unmarked(node_pointer p_y)
187   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
189   _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;)
192   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == NULL);
194   p_y->m_p_next_sibling = p_y->m_p_l_child;
196   p_y->m_p_next_sibling->m_p_prev_or_parent = p_y;
198   p_y->m_p_l_child = NULL;
200   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
206 fix_sibling_rank_1_marked(node_pointer p_y)
208   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
209   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == NULL);
211   p_y->m_metadata = 0;
213   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
219 fix_sibling_general_unmarked(node_pointer p_y)
221   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
223   node_pointer p_w = p_y->m_p_l_child;
227   p_y->m_p_l_child = p_w->m_p_next_sibling;
228   p_w->m_p_next_sibling->m_p_prev_or_parent = p_y;
230   p_w->m_p_next_sibling = p_y->m_p_next_sibling;
234   p_y->m_p_next_sibling = p_w;
235   p_w->m_p_prev_or_parent = p_y;
237   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
243 fix_sibling_general_marked(node_pointer p_y)
245   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
247   --p_y->m_metadata;
249   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
255 fix_child(node_pointer p_y)
257   _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
259   if (p_y->m_p_next_sibling != NULL)
260     p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent;
262   if (p_y->m_p_prev_or_parent->m_p_l_child == p_y)
263     p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling;
265     p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling;
267   make_root_and_link(p_y);
306   node_pointer p_y = p_nd->m_p_prev_or_parent;
307   _GLIBCXX_DEBUG_ASSERT(p_y != NULL);
310     p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y;
312   if (p_y->m_p_l_child == p_nd)
313     p_y->m_p_l_child = p_nd->m_p_next_sibling;
315     p_y->m_p_next_sibling = p_nd->m_p_next_sibling;
317   fix(p_y);