00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 PB_ASSOC_CLASS_T_DEC
00046 inline std::pair<typename PB_ASSOC_CLASS_C_DEC::find_iterator, bool>
00047 PB_ASSOC_CLASS_C_DEC::
00048 insert_leaf(const_mapped_reference r_mapped_value)
00049 {
00050 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00051
00052 if (m_size == 0)
00053 return (std::make_pair(
00054 insert_imp_empty(r_mapped_value),
00055 true));
00056
00057 node_pointer p_nd = m_p_head->m_p_parent;
00058 node_pointer p_pot = m_p_head;
00059
00060 while (p_nd != NULL)
00061 if (!Cmp_Fn::operator()(
00062 PB_ASSOC_V2F(p_nd->m_value),
00063 PB_ASSOC_V2F(r_mapped_value)))
00064 {
00065 p_pot = p_nd;
00066
00067 p_nd = p_nd->m_p_left;
00068 }
00069 else
00070 p_nd = p_nd->m_p_right;
00071
00072 if (p_pot == m_p_head)
00073 return (std::make_pair(
00074 insert_leaf_new(r_mapped_value, m_p_head->m_p_right, false),
00075 true));
00076
00077 if (!Cmp_Fn::operator()(
00078 PB_ASSOC_V2F(r_mapped_value),
00079 PB_ASSOC_V2F(p_pot->m_value)))
00080 {
00081 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00082
00083 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(
00084 PB_ASSOC_V2F(r_mapped_value)));
00085
00086 return (std::make_pair(p_pot, false));
00087 }
00088
00089 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(
00090 PB_ASSOC_V2F(r_mapped_value)));
00091
00092 p_nd = p_pot->m_p_left;
00093 if (p_nd == NULL)
00094 return (std::make_pair(
00095 insert_leaf_new(r_mapped_value, p_pot, true),
00096 true));
00097
00098 while (p_nd->m_p_right != NULL)
00099 p_nd = p_nd->m_p_right;
00100
00101 return (std::make_pair(
00102 insert_leaf_new(r_mapped_value, p_nd, false),
00103 true));
00104 }
00105
00106 PB_ASSOC_CLASS_T_DEC
00107 inline typename PB_ASSOC_CLASS_C_DEC::iterator
00108 PB_ASSOC_CLASS_C_DEC::
00109 insert_leaf_new(const_mapped_reference r_mapped_value, node_pointer p_nd, bool left_nd)
00110 {
00111 node_pointer p_new_nd =
00112 get_new_node_for_leaf_insert(r_mapped_value, my_traits_base::s_no_throw_copies_indicator);
00113
00114 if (left_nd)
00115 {
00116 PB_ASSOC_DBG_ASSERT(p_nd->m_p_left == NULL);
00117 PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()(
00118 PB_ASSOC_V2F(r_mapped_value),
00119 PB_ASSOC_V2F(p_nd->m_value)));
00120
00121 p_nd->m_p_left = p_new_nd;
00122
00123 if (m_p_head->m_p_left == p_nd)
00124 m_p_head->m_p_left = p_new_nd;
00125 }
00126 else
00127 {
00128 PB_ASSOC_DBG_ASSERT(p_nd->m_p_right == NULL);
00129 PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()(
00130 PB_ASSOC_V2F(p_nd->m_value),
00131 PB_ASSOC_V2F(r_mapped_value)));
00132
00133 p_nd->m_p_right = p_new_nd;
00134
00135 if (m_p_head->m_p_right == p_nd)
00136 m_p_head->m_p_right = p_new_nd;
00137 }
00138
00139 p_new_nd->m_p_parent = p_nd;
00140
00141 p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
00142
00143 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_nd));
00144
00145 update_to_top(p_new_nd, (Node_Updator* )this);
00146
00147 PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new(
00148 PB_ASSOC_V2F(r_mapped_value)));
00149
00150 return (iterator(p_new_nd));
00151 }
00152
00153 PB_ASSOC_CLASS_T_DEC
00154 inline typename PB_ASSOC_CLASS_C_DEC::iterator
00155 PB_ASSOC_CLASS_C_DEC::
00156 insert_imp_empty(const_mapped_reference r_mapped_value)
00157 {
00158 node_pointer p_new_node =
00159 get_new_node_for_leaf_insert(r_mapped_value, my_traits_base::s_no_throw_copies_indicator);
00160
00161 m_p_head->m_p_left = m_p_head->m_p_right =
00162 m_p_head->m_p_parent = p_new_node;
00163
00164 p_new_node->m_p_parent = m_p_head;
00165
00166 p_new_node->m_p_left = p_new_node->m_p_right = NULL;
00167
00168 PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new(
00169 PB_ASSOC_V2F(r_mapped_value)));
00170
00171 update_to_top(m_p_head->m_p_parent, (Node_Updator* )this);
00172
00173 return (iterator(p_new_node));
00174 }
00175
00176 PB_ASSOC_CLASS_T_DEC
00177 inline typename PB_ASSOC_CLASS_C_DEC::node_pointer
00178 PB_ASSOC_CLASS_C_DEC::
00179 get_new_node_for_leaf_insert(const_mapped_reference r_val, pb_assoc::detail::int_to_type<false>)
00180 {
00181 node_pointer p_new_nd = s_node_allocator.allocate(1);
00182
00183 cond_dealtor_t cond(p_new_nd);
00184
00185 new (const_cast<void* >(
00186 static_cast<const void* >(&p_new_nd->m_value)))
00187 typename Node::value_type(r_val);
00188
00189 cond.set_no_action();
00190
00191 p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
00192
00193 ++m_size;
00194
00195 return (p_new_nd);
00196 }
00197
00198 PB_ASSOC_CLASS_T_DEC
00199 inline typename PB_ASSOC_CLASS_C_DEC::node_pointer
00200 PB_ASSOC_CLASS_C_DEC::
00201 get_new_node_for_leaf_insert(const_mapped_reference r_val, pb_assoc::detail::int_to_type<true>)
00202 {
00203 node_pointer p_new_nd = s_node_allocator.allocate(1);
00204
00205 new (const_cast<void* >(
00206 static_cast<const void* >(&p_new_nd->m_value)))
00207 typename Node::value_type(r_val);
00208
00209 p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
00210
00211 ++m_size;
00212
00213 return (p_new_nd);
00214 }
00215