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
00045 #include <utility>
00046 #include <iterator>
00047 #include <ext/pb_assoc/detail/cond_dealtor.hpp>
00048 #include <ext/pb_assoc/trivial_iterator_def.hpp>
00049 #include <ext/pb_assoc/detail/types_traits.hpp>
00050 #include <ext/pb_assoc/exception.hpp>
00051 #include <ext/pb_assoc/detail/map_debug_base.hpp>
00052
00053 namespace pb_assoc
00054 {
00055
00056 namespace detail
00057 {
00058
00059 #ifdef PB_ASSOC_LU_MAP_DEBUG_
00060 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00061 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00062 #define PB_ASSOC_DBG_ONLY(X) X
00063 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00064 #define PB_ASSOC_DBG_ASSERT(X)
00065 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00066 #define PB_ASSOC_DBG_ONLY(X) ;
00067 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00068
00069 #define PB_ASSOC_CLASS_T_DEC \
00070 template< \
00071 typename Key, \
00072 typename Data, \
00073 class Eq_Fn, \
00074 class Allocator, \
00075 class Update_Policy>
00076
00077 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00078 #define PB_ASSOC_CLASS_NAME \
00079 lu_map_data_
00080 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00081
00082 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00083 #define PB_ASSOC_CLASS_NAME \
00084 lu_map_no_data_
00085 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00086
00087 #define PB_ASSOC_CLASS_C_DEC \
00088 PB_ASSOC_CLASS_NAME< \
00089 Key, \
00090 Data, \
00091 Eq_Fn, \
00092 Allocator, \
00093 Update_Policy>
00094
00095 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00096 pb_assoc::detail::types_traits< \
00097 Key, \
00098 Data, \
00099 Allocator>
00100
00101 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00102 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
00103 pb_assoc::detail::map_debug_base< \
00104 Key, \
00105 Eq_Fn>
00106 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00107
00108 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00109 #define PB_ASSOC_V2F(X) (X).first
00110 #define PB_ASSOC_V2S(X) (X).second
00111 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
00112 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00113
00114 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00115 #define PB_ASSOC_V2F(X) (X)
00116 #define PB_ASSOC_V2S(X) Data()
00117 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
00118 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00119
00120 #ifdef PB_ASSOC_LU_MAP_DEBUG_
00121 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00122 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00123 #define PB_ASSOC_DBG_ONLY(X) X
00124 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00125 #define PB_ASSOC_DBG_ASSERT(X)
00126 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00127 #define PB_ASSOC_DBG_ONLY(X) ;
00128 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00129
00130
00131
00132 template<typename Key,
00133 typename Data,
00134 class Eq_Fn,
00135 class Allocator,
00136 class Update_Policy>
00137 class PB_ASSOC_CLASS_NAME :
00138 #ifdef PB_ASSOC_LU_MAP_DEBUG_
00139 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
00140 #endif
00141 public Eq_Fn,
00142 public Update_Policy,
00143 public PB_ASSOC_TYPES_TRAITS_C_DEC
00144 {
00145
00146 protected:
00147
00148 typedef typename Allocator::size_type size_type;
00149
00150 typedef
00151 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00152 const_key_reference;
00153
00154 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00155
00156 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00157
00158 typedef
00159 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00160 data_reference;
00161
00162 typedef
00163 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00164 const_data_reference;
00165
00166 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00167
00168 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00169
00170 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00171
00172 typedef
00173 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00174 const_pointer;
00175
00176 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00177
00178 typedef
00179 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00180 const_reference;
00181
00182 typedef Update_Policy update_policy;
00183
00184 typedef typename Update_Policy::metadata_type update_metadata;
00185
00186 struct entry
00187 {
00188 typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type m_value;
00189
00190 update_metadata m_update_metadata;
00191
00192 typename Allocator::template rebind<entry>::other::pointer m_p_next;
00193 };
00194
00195 typedef
00196 typename Allocator::template rebind<entry>::other
00197 entry_allocator;
00198
00199 typedef typename entry_allocator::pointer entry_pointer;
00200
00201 typedef typename entry_allocator::const_pointer const_entry_pointer;
00202
00203 typedef typename entry_allocator::reference entry_reference;
00204
00205 typedef
00206 typename entry_allocator::const_reference
00207 const_entry_reference;
00208
00209 typedef
00210 typename Allocator::template rebind<entry_pointer>::other
00211 entry_pointer_allocator;
00212
00213 typedef typename entry_pointer_allocator::pointer entry_pointer_array;
00214
00215 #define PB_ASSOC_GEN_POS entry_pointer
00216
00217 typedef value_type mapped_value_type;
00218
00219 typedef pointer mapped_pointer;
00220
00221 typedef const_pointer const_mapped_pointer;
00222
00223 typedef reference mapped_reference;
00224
00225 typedef const_reference const_mapped_reference;
00226
00227 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
00228 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
00229 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
00230 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
00231
00232 #undef PB_ASSOC_GEN_POS
00233
00234 typedef find_iterator_ find_iterator;
00235
00236 typedef const_find_iterator_ const_find_iterator;
00237
00238 typedef iterator_ iterator;
00239
00240 typedef const_iterator_ const_iterator;
00241
00242 typedef Eq_Fn eq_fn;
00243
00244 typedef Allocator allocator;
00245
00246 protected:
00247
00248 PB_ASSOC_CLASS_NAME();
00249
00250 PB_ASSOC_CLASS_NAME(const Eq_Fn& r_eq_fn);
00251
00252 PB_ASSOC_CLASS_NAME(const Eq_Fn& r_eq_fn, const Update_Policy& r_update_policy);
00253
00254 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00255
00256 virtual
00257 ~PB_ASSOC_CLASS_NAME();
00258
00259 void
00260 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00261
00262 template<class It>
00263 void
00264 copy_from_range(It first_it, It last_it);
00265
00266 inline size_type
00267 size() const;
00268
00269 inline size_type
00270 max_size() const;
00271
00272 inline bool
00273 empty() const;
00274
00275 Eq_Fn&
00276 get_eq_fn();
00277
00278 const Eq_Fn&
00279 get_eq_fn() const;
00280
00281 inline std::pair<find_iterator, bool>
00282 insert(const_reference r_val);
00283
00284 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00285 inline data_reference
00286 subscript_imp(const_key_reference r_key);
00287 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00288
00289 inline find_iterator
00290 find(const_key_reference r_key);
00291
00292 inline const_find_iterator
00293 find(const_key_reference r_key) const;
00294
00295 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00296 inline const_data_reference
00297 const_subscript_imp(const_key_reference r_key) const;
00298 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00299
00300 inline size_type
00301 erase(const_key_reference r_key);
00302
00303 template<class Pred>
00304 inline size_type
00305 erase_if(Pred& r_pred);
00306
00307 void
00308 clear();
00309
00310 inline iterator
00311 begin();
00312
00313 inline const_iterator
00314 begin() const;
00315
00316 inline iterator
00317 end();
00318
00319 inline const_iterator
00320 end() const;
00321
00322 #ifdef PB_ASSOC_LU_MAP_DEBUG_
00323
00324 virtual void
00325 assert_valid() const;
00326
00327 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00328
00329 private:
00330
00331 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
00332
00333 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00334 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
00335 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00336
00337 typedef
00338 pb_assoc::detail::cond_dealtor<
00339 entry,
00340 Allocator>
00341 cond_dealtor_t;
00342
00343 private:
00344
00345 void
00346 deallocate_all(bool deallocate_root);
00347
00348 inline void
00349 move_next_to_front(entry_pointer p_l) const;
00350
00351 void
00352 initialize();
00353
00354 inline void
00355 insert_new_after(entry_pointer p_l, const_reference r_val);
00356
00357 inline entry_pointer
00358 find_imp(const_key_reference r_key) const
00359 {
00360 entry_pointer p_l = m_p_l;
00361
00362 while (p_l->m_p_next != NULL)
00363 if (Eq_Fn::operator()(
00364 r_key,
00365 PB_ASSOC_V2F(p_l->m_p_next->m_value)))
00366 {
00367 if (Update_Policy::operator()(p_l->m_update_metadata))
00368 {
00369 move_next_to_front(p_l);
00370
00371 return (m_p_l);
00372 }
00373 else
00374 return (p_l);
00375 }
00376 else
00377 p_l = p_l->m_p_next;
00378
00379 return (p_l);
00380 }
00381
00382 inline void
00383 erase_imp(entry_pointer p_l);
00384
00385 inline find_iterator
00386 find_end();
00387
00388 inline const_find_iterator
00389 find_end() const;
00390
00391 void
00392 inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
00393
00394 void
00395 inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const;
00396
00397 void
00398 get_start_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
00399
00400 #ifdef PB_ASSOC_LU_MAP_DEBUG_
00401
00402 void
00403 assert_entry_pointer_array_valid(const entry_pointer_array a_p_lntries) const;
00404
00405 void
00406 assert_entry_pointer_valid(const entry_pointer p_l, store_hash_true_indicator) const;
00407
00408 void
00409 assert_entry_pointer_valid(const entry_pointer p_l, store_hash_false_indicator) const;
00410
00411 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
00412
00413 private:
00414
00415 static entry_allocator s_entry_allocator;
00416
00417 mutable entry_pointer m_p_l;
00418
00419 size_type m_size;
00420
00421 friend class iterator_;
00422
00423 friend class const_iterator_;
00424
00425 static iterator s_end_it;
00426
00427 static const_iterator s_const_end_it;
00428
00429 static find_iterator s_find_end_it;
00430
00431 static const_find_iterator s_const_find_end_it;
00432
00433 };
00434
00435 #include <ext/pb_assoc/detail/lu_map_/constructor_destructor_fn_imps.hpp>
00436 #include <ext/pb_assoc/detail/lu_map_/info_fn_imps.hpp>
00437 #include <ext/pb_assoc/detail/lu_map_/debug_fn_imps.hpp>
00438 #include <ext/pb_assoc/detail/lu_map_/policy_access_fn_imps.hpp>
00439 #include <ext/pb_assoc/detail/lu_map_/iterators_fn_imps.hpp>
00440 #include <ext/pb_assoc/detail/lu_map_/erase_fn_imps.hpp>
00441 #include <ext/pb_assoc/detail/lu_map_/find_fn_imps.hpp>
00442 #include <ext/pb_assoc/detail/lu_map_/insert_fn_imps.hpp>
00443
00444 #undef PB_ASSOC_CLASS_T_DEC
00445
00446 #undef PB_ASSOC_CLASS_C_DEC
00447
00448 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00449
00450 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
00451
00452 #undef PB_ASSOC_CLASS_NAME
00453
00454 #undef PB_ASSOC_V2F
00455 #undef PB_ASSOC_EP2VP
00456 #undef PB_ASSOC_V2S
00457
00458 #undef PB_ASSOC_DBG_ASSERT
00459 #undef PB_ASSOC_DBG_VERIFY
00460 #undef PB_ASSOC_DBG_ONLY
00461
00462 }
00463
00464 }