41 #ifdef PB_DS_CLASS_C_DEC
44 inline typename PB_DS_CLASS_C_DEC::node_pointer
46 get_new_node_for_insert(const_reference r_val)
48 return get_new_node_for_insert(r_val, s_no_throw_copies_ind);
52 inline typename PB_DS_CLASS_C_DEC::node_pointer
54 get_new_node_for_insert(const_reference r_val,
false_type)
56 node_pointer p_new_nd = s_node_allocator.allocate(1);
58 cond_dealtor_t cond(p_new_nd);
60 new (
const_cast<void*
>(
61 static_cast<const void*
>(&p_new_nd->m_value)))
62 typename node::value_type(r_val);
72 inline typename PB_DS_CLASS_C_DEC::node_pointer
74 get_new_node_for_insert(const_reference r_val,
true_type)
76 node_pointer p_new_nd = s_node_allocator.allocate(1);
78 new (
const_cast<void*
>(
79 static_cast<const void*
>(&p_new_nd->m_value)))
80 typename node::value_type(r_val);
90 make_child_of(node_pointer p_nd, node_pointer p_new_parent)
92 _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
93 _GLIBCXX_DEBUG_ASSERT(p_new_parent != 0);
95 p_nd->m_p_next_sibling = p_new_parent->m_p_l_child;
97 if (p_new_parent->m_p_l_child != 0)
98 p_new_parent->m_p_l_child->m_p_prev_or_parent = p_nd;
100 p_nd->m_p_prev_or_parent = p_new_parent;
102 p_new_parent->m_p_l_child = p_nd;
106 inline typename PB_DS_CLASS_C_DEC::node_pointer
108 parent(node_pointer p_nd)
112 node_pointer p_pot = p_nd->m_p_prev_or_parent;
114 if (p_pot == 0 || p_pot->m_p_l_child == p_nd)
124 swap_with_parent(node_pointer p_nd, node_pointer p_parent)
126 if (p_parent == m_p_root)
129 _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
130 _GLIBCXX_DEBUG_ASSERT(p_parent != 0);
131 _GLIBCXX_DEBUG_ASSERT(parent(p_nd) == p_parent);
133 const bool nd_direct_child = p_parent->m_p_l_child == p_nd;
134 const bool parent_root = p_parent->m_p_prev_or_parent == 0;
135 const bool parent_direct_child =
136 !parent_root&& p_parent->m_p_prev_or_parent->m_p_l_child == p_parent;
138 std::swap(p_parent->m_p_prev_or_parent, p_nd->m_p_prev_or_parent);
139 std::swap(p_parent->m_p_next_sibling, p_nd->m_p_next_sibling);
140 std::swap(p_parent->m_p_l_child, p_nd->m_p_l_child);
141 std::swap(p_parent->m_metadata, p_nd->m_metadata);
143 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child != 0);
144 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent != 0);
146 if (p_nd->m_p_next_sibling != 0)
147 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd;
149 if (p_parent->m_p_next_sibling != 0)
150 p_parent->m_p_next_sibling->m_p_prev_or_parent = p_parent;
152 if (p_parent->m_p_l_child != 0)
153 p_parent->m_p_l_child->m_p_prev_or_parent = p_parent;
155 if (parent_direct_child)
156 p_nd->m_p_prev_or_parent->m_p_l_child = p_nd;
157 else if (!parent_root)
158 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd;
160 if (!nd_direct_child)
162 p_nd->m_p_l_child->m_p_prev_or_parent = p_nd;
164 p_parent->m_p_prev_or_parent->m_p_next_sibling = p_parent;
168 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child == p_nd);
169 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent == p_parent);
171 p_nd->m_p_l_child = p_parent;
172 p_parent->m_p_prev_or_parent = p_nd;
175 _GLIBCXX_DEBUG_ASSERT(parent(p_parent) == p_nd);
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.