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