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
00046 PB_ASSOC_CLASS_T_DEC
00047 inline typename PB_ASSOC_CLASS_C_DEC::size_type
00048 PB_ASSOC_CLASS_C_DEC::
00049 find_ins_pos(const_key_reference r_key, int_to_type<false>)
00050 {
00051 size_type hash = my_ranged_probe_fn_base::operator()(r_key);
00052
00053 size_type i;
00054
00055
00056
00057
00058 size_type ins_pos = m_num_e;
00059
00060 my_resize_base::notify_insert_search_start();
00061
00062 for (i = 0; i < m_num_e; ++i)
00063 {
00064 const size_type pos =
00065 my_ranged_probe_fn_base::operator()(r_key, hash, i);
00066
00067 entry* const p_e = m_a_entries + pos;
00068
00069 switch(p_e->m_stat)
00070 {
00071 case EMPTY_ENTRY_STATUS:
00072 {
00073 my_resize_base::notify_insert_search_end();
00074
00075 PB_ASSOC_DBG_ONLY(
00076 my_map_debug_base::check_key_does_not_exist(r_key);)
00077
00078 return ((ins_pos == m_num_e)? pos : ins_pos);
00079 }
00080 break;
00081 case ERASED_ENTRY_STATUS:
00082 if (ins_pos == m_num_e)
00083 ins_pos = pos;
00084 break;
00085 case VALID_ENTRY_STATUS:
00086 if (my_hash_eq_fn_base::operator()(
00087 PB_ASSOC_V2F(p_e->m_value), r_key))
00088 {
00089 my_resize_base::notify_insert_search_end();
00090
00091 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key);)
00092
00093 return (pos);
00094 }
00095 break;
00096 default:
00097 PB_ASSOC_DBG_ASSERT(0);
00098 };
00099
00100 my_resize_base::notify_insert_search_collision();
00101 }
00102
00103 my_resize_base::notify_insert_search_end();
00104
00105 if (ins_pos == m_num_e)
00106 throw cannot_insert();
00107
00108 return (ins_pos);
00109 }
00110
00111 PB_ASSOC_CLASS_T_DEC
00112 inline typename PB_ASSOC_CLASS_C_DEC::data_reference
00113 PB_ASSOC_CLASS_C_DEC::
00114 subscript_imp(const_key_reference r_key, int_to_type<false>)
00115 {
00116 PB_ASSOC_DBG_ONLY(assert_valid();)
00117
00118 const size_type pos =
00119 find_ins_pos(r_key, my_hash_traits_base::s_store_hash_indicator);
00120
00121 entry_pointer p_e =& m_a_entries[pos];
00122
00123 if (p_e->m_stat != VALID_ENTRY_STATUS)
00124 return (insert_new_imp(
00125 value_type(r_key, Data()), pos)->second);
00126
00127 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key);)
00128
00129 return (p_e->m_value.second);
00130 }
00131
00132 PB_ASSOC_CLASS_T_DEC
00133 inline std::pair<typename PB_ASSOC_CLASS_C_DEC::find_iterator, bool>
00134 PB_ASSOC_CLASS_C_DEC::
00135 insert_imp(const_reference r_val, int_to_type<false>)
00136 {
00137 const_key_reference r_key = PB_ASSOC_V2F(r_val);
00138
00139 const size_type pos =
00140 find_ins_pos(r_key, my_hash_traits_base::s_store_hash_indicator);
00141
00142 if (m_a_entries[pos].m_stat == VALID_ENTRY_STATUS)
00143 {
00144 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key);)
00145
00146 return (std::make_pair(&m_a_entries[pos].m_value, false));
00147 }
00148
00149 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key));
00150
00151 return (std::make_pair(
00152 insert_new_imp(r_val, pos),
00153 true));
00154 }
00155
00156 PB_ASSOC_CLASS_T_DEC
00157 inline typename PB_ASSOC_CLASS_C_DEC::pointer
00158 PB_ASSOC_CLASS_C_DEC::
00159 insert_new_imp(const_reference r_val, size_type pos)
00160 {
00161 PB_ASSOC_DBG_ASSERT(m_a_entries[pos].m_stat != VALID_ENTRY_STATUS);
00162
00163 if (do_resize_if_needed())
00164 pos = find_ins_pos(PB_ASSOC_V2F(r_val),
00165 my_hash_traits_base::s_store_hash_indicator);
00166
00167 PB_ASSOC_DBG_ASSERT(m_a_entries[pos].m_stat != VALID_ENTRY_STATUS);
00168
00169 entry* const p_e = m_a_entries + pos;
00170
00171 new (&p_e->m_value) value_type(r_val);
00172
00173 p_e->m_stat = VALID_ENTRY_STATUS;
00174
00175 my_resize_base::notify_inserted(++m_num_used_e);
00176
00177 PB_ASSOC_DBG_ONLY(my_map_debug_base::
00178 insert_new(p_e->m_value.first);)
00179
00180 PB_ASSOC_DBG_ONLY(assert_valid();)
00181
00182 return (static_cast<pointer>(&p_e->m_value));
00183 }
00184