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/hash_fn/ranged_hash_fn.hpp>
00050 #include <ext/pb_assoc/detail/hash_types_traits.hpp>
00051 #include <ext/pb_assoc/detail/types_traits.hpp>
00052 #include <ext/pb_assoc/exception.hpp>
00053 #include <ext/pb_assoc/detail/map_debug_base.hpp>
00054 #include <ext/pb_assoc/detail/eq_fn/hash_eq_fn.hpp>
00055
00056 namespace pb_assoc
00057 {
00058
00059 namespace detail
00060 {
00061
00062 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00063 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00064 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00065 #define PB_ASSOC_DBG_ONLY(X) X
00066 #else // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00067 #define PB_ASSOC_DBG_ASSERT(X)
00068 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00069 #define PB_ASSOC_DBG_ONLY(X) ;
00070 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00071
00072 #define PB_ASSOC_CLASS_T_DEC \
00073 template< \
00074 typename Key, \
00075 typename Data, \
00076 class Hash_Fn, \
00077 class Eq_Fn, \
00078 class Allocator, \
00079 bool Store_Hash, \
00080 class Comb_Hash_Fn, \
00081 class Resize_Policy>
00082
00083 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00084 #define PB_ASSOC_CLASS_NAME \
00085 cc_ht_map_data_
00086 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00087
00088 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00089 #define PB_ASSOC_CLASS_NAME \
00090 cc_ht_map_no_data_
00091 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00092
00093 #define PB_ASSOC_CLASS_C_DEC \
00094 PB_ASSOC_CLASS_NAME< \
00095 Key, \
00096 Data, \
00097 Hash_Fn, \
00098 Eq_Fn, \
00099 Allocator, \
00100 Store_Hash, \
00101 Comb_Hash_Fn, \
00102 Resize_Policy >
00103
00104 #define PB_ASSOC_HASH_EQ_FN_C_DEC \
00105 pb_assoc::detail::hash_eq_fn< \
00106 Key, \
00107 Eq_Fn, \
00108 Allocator, \
00109 Store_Hash>
00110
00111 #define PB_ASSOC_RANGED_HASH_FN_C_DEC \
00112 pb_assoc::detail::ranged_hash_fn< \
00113 Key, \
00114 Hash_Fn, \
00115 Allocator, \
00116 Comb_Hash_Fn, \
00117 Store_Hash>
00118
00119 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00120 types_traits< \
00121 Key, \
00122 Data, \
00123 Allocator>
00124
00125 #define PB_ASSOC_HASH_TYPES_TRAITS_C_DEC \
00126 hash_types_traits< \
00127 typename Allocator::size_type, \
00128 Store_Hash>
00129
00130 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00131 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
00132 pb_assoc::detail::map_debug_base< \
00133 Key, \
00134 Eq_Fn>
00135 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00136
00137 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00138 #define PB_ASSOC_V2F(X) (X).first
00139 #define PB_ASSOC_V2S(X) (X).second
00140 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00141
00142 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00143 #define PB_ASSOC_V2F(X) (X)
00144 #define PB_ASSOC_V2S(X) Mapped_Data()
00145 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00146
00147 #define PB_ASSOC_STATIC_ASSERT(UNIQUE, E) \
00148 typedef \
00149 pb_assoc::detail::static_assert_dummy_class< \
00150 sizeof(pb_assoc::detail::static_assert<(bool)(E)>)> \
00151 UNIQUE##static_assert_type
00152
00153 template<typename Key,
00154 typename Data,
00155 class Hash_Fn,
00156 class Eq_Fn,
00157 class Allocator,
00158 bool Store_Hash,
00159 class Comb_Hash_Fn,
00160 class Resize_Policy >
00161 class PB_ASSOC_CLASS_NAME:
00162 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00163 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
00164 #endif
00165 public PB_ASSOC_HASH_EQ_FN_C_DEC,
00166 public Resize_Policy,
00167 public PB_ASSOC_RANGED_HASH_FN_C_DEC,
00168 public PB_ASSOC_TYPES_TRAITS_C_DEC,
00169 public PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
00170 {
00171
00172 public:
00173
00174 typedef typename Allocator::size_type size_type;
00175
00176 typedef
00177 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00178 const_key_reference;
00179
00180 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00181
00182 typedef
00183 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00184 data_reference;
00185
00186 typedef
00187 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00188 const_data_reference;
00189
00190 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00191
00192 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00193
00194 typedef
00195 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00196 const_pointer;
00197
00198 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00199
00200 typedef
00201 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00202 const_reference;
00203
00204 protected:
00205
00206 typedef typename PB_ASSOC_HASH_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
00207
00208 struct no_store_hash_entry
00209 {
00210 value_type m_value;
00211
00212 typename Allocator::template rebind<
00213 no_store_hash_entry>::other::pointer m_p_next;
00214 };
00215
00216 struct store_hash_entry
00217 {
00218 value_type m_value;
00219
00220 size_type m_hash;
00221
00222 typename Allocator::template rebind<
00223 store_hash_entry>::other::pointer m_p_next;
00224 };
00225
00226 typedef
00227 typename cond_type<
00228 Store_Hash,
00229 store_hash_entry,
00230 no_store_hash_entry>::type
00231 entry;
00232
00233 typedef
00234 typename Allocator::template rebind<entry>::other
00235 entry_allocator;
00236
00237 typedef typename entry_allocator::pointer entry_pointer;
00238
00239 typedef typename entry_allocator::const_pointer const_entry_pointer;
00240
00241 typedef typename entry_allocator::reference entry_reference;
00242
00243 typedef
00244 typename entry_allocator::const_reference
00245 const_entry_reference;
00246
00247 typedef
00248 typename Allocator::template rebind<entry_pointer>::other
00249 entry_pointer_allocator;
00250
00251 typedef typename entry_pointer_allocator::pointer entry_pointer_array;
00252
00253 typedef value_type mapped_value_type;
00254
00255 typedef pointer mapped_pointer;
00256
00257 typedef const_pointer const_mapped_pointer;
00258
00259 typedef reference mapped_reference;
00260
00261 typedef const_reference const_mapped_reference;
00262
00263 #define PB_ASSOC_GEN_POS std::pair<entry_pointer, size_type>
00264
00265 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
00266 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
00267 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
00268 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
00269
00270 #undef PB_ASSOC_GEN_POS
00271
00272 typedef find_iterator_ find_iterator;
00273
00274 typedef const_find_iterator_ const_find_iterator;
00275
00276 typedef iterator_ iterator;
00277
00278 typedef const_iterator_ const_iterator;
00279
00280 typedef Hash_Fn hash_fn;
00281
00282 typedef Eq_Fn eq_fn;
00283
00284 typedef Allocator allocator;
00285
00286 typedef Resize_Policy resize_policy;
00287
00288 protected:
00289
00290 PB_ASSOC_CLASS_NAME();
00291
00292 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn);
00293
00294 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
00295
00296 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn);
00297
00298 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy);
00299
00300 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00301
00302 virtual
00303 ~PB_ASSOC_CLASS_NAME();
00304
00305 void
00306 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00307
00308 template<class It>
00309 void
00310 copy_from_range(It first_it, It last_it);
00311
00312 inline size_type
00313 size() const;
00314
00315 inline size_type
00316 max_size() const;
00317
00318 inline bool
00319 empty() const;
00320
00321 Hash_Fn&
00322 get_hash_fn();
00323
00324 const Hash_Fn&
00325 get_hash_fn() const;
00326
00327 Eq_Fn&
00328 get_eq_fn();
00329
00330 const Eq_Fn&
00331 get_eq_fn() const;
00332
00333 Comb_Hash_Fn&
00334 get_comb_hash_fn();
00335
00336 const Comb_Hash_Fn&
00337 get_comb_hash_fn() const;
00338
00339 Resize_Policy&
00340 get_resize_policy();
00341
00342 const Resize_Policy&
00343 get_resize_policy() const;
00344
00345 inline std::pair<find_iterator, bool>
00346 insert(const_reference r_val);
00347
00348 inline data_reference
00349 subscript_imp(const_key_reference r_key);
00350
00351 inline find_iterator
00352 find(const_key_reference r_key);
00353
00354 inline const_find_iterator
00355 find(const_key_reference r_key) const;
00356
00357 inline find_iterator
00358 find_end();
00359
00360 inline const_find_iterator
00361 find_end() const;
00362
00363 template<class T>
00364 inline size_type
00365 erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<false>);
00366
00367 template<class T>
00368 inline size_type
00369 erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<true>);
00370
00371 template<class Pred>
00372 inline size_type
00373 erase_if(Pred& r_pred);
00374
00375 void
00376 clear();
00377
00378 inline iterator
00379 begin();
00380
00381 inline const_iterator
00382 begin() const;
00383
00384 inline iterator
00385 end();
00386
00387 inline const_iterator
00388 end() const;
00389
00390 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00391
00392 virtual void
00393 assert_valid() const;
00394
00395 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00396
00397 virtual void
00398 do_resize(size_type new_size);
00399
00400 private:
00401
00402 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
00403
00404 typedef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC my_hash_traits_base;
00405
00406 typedef PB_ASSOC_RANGED_HASH_FN_C_DEC my_ranged_hash_fn_base;
00407
00408 typedef PB_ASSOC_HASH_EQ_FN_C_DEC my_hash_eq_fn_base;
00409
00410 typedef Resize_Policy my_resize_base;
00411
00412 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00413 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
00414 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00415
00416 private:
00417
00418 inline bool
00419 do_resize_if_needed();
00420
00421 inline void
00422 do_resize_if_needed_no_throw();
00423
00424 void
00425 resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size);
00426
00427 inline entry_pointer
00428 resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<false>);
00429
00430 inline entry_pointer
00431 resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<true>);
00432
00433 template<class For_Each_Fn>
00434 void
00435 do_for_each(For_Each_Fn fn);
00436
00437 void
00438 deallocate_links_in_list(entry_pointer p_e);
00439
00440 inline entry_pointer
00441 get_entry(const_reference r_val, int_to_type<false>);
00442
00443 inline entry_pointer
00444 get_entry(const_reference r_val, int_to_type<true>);
00445
00446 inline void
00447 rels_entry(entry_pointer p_e);
00448
00449 void
00450 constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<false>);
00451
00452 void
00453 constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<true>);
00454
00455 void
00456 deallocate_all();
00457
00458 inline data_reference
00459 subscript_imp(const_key_reference r_key, int_to_type<false>);
00460
00461 inline data_reference
00462 subscript_imp(const_key_reference r_key, int_to_type<true>);
00463
00464 inline std::pair<find_iterator, bool>
00465 insert_imp(const_reference r_val, int_to_type<false>);
00466
00467 inline std::pair<find_iterator, bool>
00468 insert_imp(const_reference r_val, int_to_type<true>);
00469
00470 inline pointer
00471 insert_new_imp(const_reference r_val, size_type pos);
00472
00473 inline pointer
00474 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair);
00475
00476 inline const_data_reference
00477 const_subscript_imp(const_key_reference r_key, int_to_type<false>) const;
00478
00479 inline const_data_reference
00480 const_subscript_imp(const_key_reference r_key, int_to_type<true>) const;
00481
00482 inline pointer
00483 find_key_pointer(const_key_reference r_key, int_to_type<false>);
00484
00485 inline pointer
00486 find_key_pointer(const_key_reference r_key, int_to_type<true>);
00487
00488 template<class T>
00489 inline size_type
00490 erase_in_pos_imp(T r_t, bool erase_entry_if_last, size_type pos);
00491
00492 template<class T>
00493 inline size_type
00494 erase_in_pos_imp(T r_t, bool erase_entry_if_last, const comp_hash& r_pos_hash_pair);
00495
00496 inline void
00497 erase_entry_pointer(entry_pointer& r_p_e);
00498
00499 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00500 void
00501 inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
00502 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00503
00504 void
00505 inc_it_state(const_pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
00506
00507 void
00508 get_start_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
00509
00510 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00511
00512 void
00513 assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries) const;
00514
00515 void
00516 assert_entry_pointer_valid(const entry_pointer p_e, store_hash_true_indicator) const;
00517
00518 void
00519 assert_entry_pointer_valid(const entry_pointer p_e, store_hash_false_indicator) const;
00520
00521 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00522
00523 private:
00524 static entry_allocator s_entry_allocator;
00525
00526 static entry_pointer_allocator s_entry_pointer_allocator;
00527
00528 typedef
00529 pb_assoc::detail::cond_dealtor<
00530 entry,
00531 Allocator>
00532 cond_dealtor_t;
00533
00534 entry_pointer_array m_a_p_entries;
00535
00536 size_type m_num_e_p;
00537
00538 size_type m_num_used_e;
00539
00540 friend class iterator_;
00541
00542 friend class const_iterator_;
00543
00544 static iterator s_end_it;
00545
00546 static const_iterator s_const_end_it;
00547
00548 static find_iterator s_find_end_it;
00549
00550 static const_find_iterator s_const_find_end_it;
00551
00552 enum
00553 {
00554 store_hash_ok =
00555 !Store_Hash ||
00556 !pb_assoc::detail::is_same_type<
00557 Hash_Fn,
00558 pb_assoc::null_hash_fn>::value
00559 };
00560
00561 PB_ASSOC_STATIC_ASSERT(sth, store_hash_ok);
00562 };
00563
00564 #include <ext/pb_assoc/detail/cc_ht_map_/constructor_destructor_fn_imps.hpp>
00565 #include <ext/pb_assoc/detail/cc_ht_map_/entry_list_fn_imps.hpp>
00566 #include <ext/pb_assoc/detail/cc_ht_map_/find_fn_imps.hpp>
00567 #include <ext/pb_assoc/detail/cc_ht_map_/resize_fn_imps.hpp>
00568 #include <ext/pb_assoc/detail/cc_ht_map_/debug_fn_imps.hpp>
00569 #include <ext/pb_assoc/detail/cc_ht_map_/size_fn_imps.hpp>
00570 #include <ext/pb_assoc/detail/cc_ht_map_/policy_access_fn_imps.hpp>
00571 #include <ext/pb_assoc/detail/cc_ht_map_/erase_fn_imps.hpp>
00572 #include <ext/pb_assoc/detail/cc_ht_map_/iterators_fn_imps.hpp>
00573 #include <ext/pb_assoc/detail/cc_ht_map_/insert_fn_imps.hpp>
00574
00575 #undef PB_ASSOC_CLASS_T_DEC
00576
00577 #undef PB_ASSOC_CLASS_C_DEC
00578
00579 #undef PB_ASSOC_HASH_EQ_FN_C_DEC
00580
00581 #undef PB_ASSOC_RANGED_HASH_FN_C_DEC
00582
00583 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00584
00585 #undef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
00586
00587 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
00588
00589 #undef PB_ASSOC_CLASS_NAME
00590
00591 #undef PB_ASSOC_V2F
00592 #undef PB_ASSOC_V2S
00593
00594 #undef PB_ASSOC_DBG_ASSERT
00595 #undef PB_ASSOC_DBG_VERIFY
00596 #undef PB_ASSOC_DBG_ONLY
00597
00598 #undef PB_ASSOC_STATIC_ASSERT
00599
00600 }
00601
00602 }