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 #ifndef HASH_POLICY_HPP
00046 #define HASH_POLICY_HPP
00047
00048 #include <algorithm>
00049 #include <vector>
00050 #include <cmath>
00051 #include <ext/pb_assoc/exception.hpp>
00052 #include <ext/pb_assoc/detail/hash_fn/mask_based_range_hashing.hpp>
00053 #include <ext/pb_assoc/detail/hash_fn/mod_based_range_hashing.hpp>
00054 #include <ext/pb_assoc/detail/resize_policy/size_base.hpp>
00055
00056 namespace pb_assoc
00057 {
00058 struct null_hash_fn
00059 { };
00060
00061 struct null_probe_fn
00062 { };
00063
00064 #define PB_ASSOC_CLASS_T_DEC \
00065 template<typename Const_Key_Ref, typename Size_Type>
00066
00067 #define PB_ASSOC_CLASS_C_DEC \
00068 linear_probe_fn< \
00069 Const_Key_Ref, \
00070 Size_Type>
00071
00072 template<typename Const_Key_Ref, typename Size_Type = size_t>
00073 class linear_probe_fn
00074 {
00075 public:
00076 typedef Size_Type size_type;
00077
00078 void
00079 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00080
00081 protected:
00082 inline size_type
00083 operator()(Const_Key_Ref r_key, size_type i) const;
00084 };
00085
00086 #include <ext/pb_assoc/detail/hash_fn/linear_probe_fn_imp.hpp>
00087
00088 #undef PB_ASSOC_CLASS_T_DEC
00089 #undef PB_ASSOC_CLASS_C_DEC
00090
00091 #define PB_ASSOC_CLASS_T_DEC \
00092 template<class Const_Key_Ref, typename Size_Type>
00093
00094 #define PB_ASSOC_CLASS_C_DEC \
00095 quadratic_probe_fn<Const_Key_Ref, Size_Type>
00096
00097 template<typename Const_Key_Ref, typename Size_Type = size_t>
00098 class quadratic_probe_fn
00099 {
00100 public:
00101 typedef Size_Type size_type;
00102
00103 void
00104 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00105
00106 protected:
00107 inline size_type
00108 operator()(Const_Key_Ref r_key, size_type i) const;
00109 };
00110
00111 #include <ext/pb_assoc/detail/hash_fn/quadratic_probe_fn_imp.hpp>
00112
00113 #undef PB_ASSOC_CLASS_T_DEC
00114 #undef PB_ASSOC_CLASS_C_DEC
00115
00116 #define PB_ASSOC_CLASS_T_DEC \
00117 template<typename Size_Type>
00118
00119 #define PB_ASSOC_CLASS_C_DEC \
00120 direct_mask_range_hashing<Size_Type>
00121
00122 template<typename Size_Type = size_t>
00123 class direct_mask_range_hashing
00124 : public pb_assoc::detail::mask_based_range_hashing<Size_Type>
00125 {
00126 public:
00127 typedef Size_Type size_type;
00128
00129 void
00130 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00131
00132 protected:
00133 void
00134 notify_resized(size_type size);
00135
00136 inline size_type
00137 operator()(size_type hash) const;
00138
00139 private:
00140 typedef pb_assoc::detail::mask_based_range_hashing<Size_Type>
00141 my_mask_based_base;
00142 };
00143
00144 #define PB_ASSOC_MASK_BASED_C_DEC \
00145 pb_assoc::detail::mask_based_range_hashing< \
00146 Size_Type>
00147
00148 #include <ext/pb_assoc/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
00149
00150 #undef PB_ASSOC_CLASS_T_DEC
00151 #undef PB_ASSOC_CLASS_C_DEC
00152
00153 #undef PB_ASSOC_MASK_BASED_C_DEC
00154
00155 #define PB_ASSOC_CLASS_T_DEC \
00156 template<typename Size_Type>
00157
00158 #define PB_ASSOC_CLASS_C_DEC \
00159 direct_mod_range_hashing<Size_Type>
00160
00161 #define PB_ASSOC_MOD_BASED_C_DEC \
00162 pb_assoc::detail::mod_based_range_hashing<Size_Type>
00163
00164 template<typename Size_Type = size_t>
00165 class direct_mod_range_hashing : public PB_ASSOC_MOD_BASED_C_DEC
00166 {
00167 public:
00168 typedef Size_Type size_type;
00169
00170 void
00171 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00172
00173 protected:
00174
00175
00176
00177
00178 void
00179 notify_resized(size_type size);
00180
00181 inline size_type
00182 operator()(size_type hash) const;
00183
00184 private:
00185 typedef PB_ASSOC_MOD_BASED_C_DEC my_mod_based_base;
00186 };
00187
00188 #include <ext/pb_assoc/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
00189
00190 #undef PB_ASSOC_CLASS_T_DEC
00191 #undef PB_ASSOC_CLASS_C_DEC
00192
00193 #undef PB_ASSOC_MOD_BASED_C_DEC
00194
00195 #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
00196 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00197 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00198 #define PB_ASSOC_DBG_ONLY(X) X
00199 #else // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
00200 #define PB_ASSOC_DBG_ASSERT(X)
00201 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00202 #define PB_ASSOC_DBG_ONLY(X) ;
00203 #endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
00204
00205 #define PB_ASSOC_CLASS_T_DEC \
00206 template<bool External_Load_Access, typename Size_Type>
00207
00208 #define PB_ASSOC_CLASS_C_DEC \
00209 hash_load_check_resize_trigger<External_Load_Access, Size_Type>
00210
00211 #define PB_ASSOC_SIZE_BASE_C_DEC \
00212 pb_assoc::detail::size_base<Size_Type, External_Load_Access>
00213
00214 template<bool External_Load_Access = false, typename Size_Type = size_t>
00215 class hash_load_check_resize_trigger : private PB_ASSOC_SIZE_BASE_C_DEC
00216 {
00217 public:
00218 typedef Size_Type size_type;
00219
00220 enum
00221 {
00222 external_load_access = External_Load_Access
00223 };
00224
00225 hash_load_check_resize_trigger(float load_min = 0.125,
00226 float load_max = 0.5);
00227
00228 void
00229 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00230
00231 virtual
00232 ~hash_load_check_resize_trigger();
00233
00234 inline std::pair<float, float>
00235 get_loads() const;
00236
00237 void
00238 set_loads(std::pair<float, float> load_pair);
00239
00240 protected:
00241 inline void
00242 notify_insert_search_start();
00243
00244 inline void
00245 notify_insert_search_collision();
00246
00247 inline void
00248 notify_insert_search_end();
00249
00250 inline void
00251 notify_find_search_start();
00252
00253 inline void
00254 notify_find_search_collision();
00255
00256 inline void
00257 notify_find_search_end();
00258
00259 inline void
00260 notify_erase_search_start();
00261
00262 inline void
00263 notify_erase_search_collision();
00264
00265 inline void
00266 notify_erase_search_end();
00267
00268 inline void
00269 notify_inserted(size_type num_entries);
00270
00271 inline void
00272 notify_erased(size_type num_entries);
00273
00274 void
00275 notify_cleared();
00276
00277 void
00278 notify_resized(size_type new_size);
00279
00280 void
00281 notify_externally_resized(size_type new_size);
00282
00283 inline bool
00284 is_resize_needed() const;
00285
00286 inline bool
00287 is_grow_needed(size_type size, size_type num_entries) const;
00288
00289 inline bool
00290 is_shrink_needed(size_type size, size_type num_entries) const;
00291
00292 typedef PB_ASSOC_SIZE_BASE_C_DEC my_size_base;
00293
00294 private:
00295 inline std::pair<float, float>
00296 get_loads_imp(pb_assoc::detail::int_to_type<true>) const;
00297
00298 void
00299 set_loads_imp(std::pair<float, float>,
00300 pb_assoc::detail::int_to_type<true>);
00301
00302 virtual void
00303 do_resize(size_type new_size);
00304
00305 #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
00306 void
00307 assert_valid() const;
00308 #endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
00309
00310 float m_load_min, m_load_max;
00311
00312 size_type m_next_shrink_size;
00313
00314 size_type m_next_grow_size;
00315
00316 bool m_resize_needed;
00317
00318 static pb_assoc::detail::int_to_type<External_Load_Access>
00319 s_external_load_access_ind;
00320 };
00321
00322 #include <ext/pb_assoc/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
00323
00324 #undef PB_ASSOC_CLASS_T_DEC
00325 #undef PB_ASSOC_CLASS_C_DEC
00326
00327 #undef PB_ASSOC_SIZE_BASE_C_DEC
00328
00329 #undef PB_ASSOC_DBG_ASSERT
00330 #undef PB_ASSOC_DBG_VERIFY
00331 #undef PB_ASSOC_DBG_ONLY
00332
00333 #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
00334 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00335 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00336 #define PB_ASSOC_DBG_ONLY(X) X
00337 #else // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
00338 #define PB_ASSOC_DBG_ASSERT(X)
00339 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00340 #define PB_ASSOC_DBG_ONLY(X) ;
00341 #endif // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
00342
00343 #define PB_ASSOC_CLASS_T_DEC \
00344 template<bool External_Load_Access, typename Size_Type>
00345
00346 #define PB_ASSOC_CLASS_C_DEC \
00347 cc_hash_max_collision_check_resize_trigger< \
00348 External_Load_Access, \
00349 Size_Type>
00350
00351 template<bool External_Load_Access = false, typename Size_Type = size_t>
00352 class cc_hash_max_collision_check_resize_trigger
00353 {
00354 public:
00355 typedef Size_Type size_type;
00356
00357 enum
00358 {
00359 external_load_access = External_Load_Access
00360 };
00361
00362 cc_hash_max_collision_check_resize_trigger(float load = 0.5);
00363
00364 void
00365 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00366
00367 inline float
00368 get_load() const;
00369
00370 protected:
00371 inline void
00372 notify_insert_search_start();
00373
00374 inline void
00375 notify_insert_search_collision();
00376
00377 inline void
00378 notify_insert_search_end();
00379
00380 inline void
00381 notify_find_search_start();
00382
00383 inline void
00384 notify_find_search_collision();
00385
00386 inline void
00387 notify_find_search_end();
00388
00389 inline void
00390 notify_erase_search_start();
00391
00392 inline void
00393 notify_erase_search_collision();
00394
00395 inline void
00396 notify_erase_search_end();
00397
00398 inline void
00399 notify_inserted(size_type num_entries);
00400
00401 inline void
00402 notify_erased(size_type num_entries);
00403
00404 void
00405 notify_cleared();
00406
00407 void
00408 notify_resized(size_type new_size);
00409
00410 void
00411 notify_externally_resized(size_type new_size);
00412
00413 inline bool
00414 is_resize_needed() const;
00415
00416 inline bool
00417 is_grow_needed(size_type size, size_type num_entries) const;
00418
00419 inline bool
00420 is_shrink_needed(size_type size, size_type num_entries) const;
00421
00422 private:
00423 template<typename Key>
00424 class max_col_checker
00425 {
00426 public:
00427 max_col_checker(size_type size, size_type* p_max_col)
00428 : m_p_max_col(p_max_col), m_a_col(size, 0)
00429 { }
00430
00431 void
00432 operator()(const std::pair<const Key, size_type>& r_key_pos_pair)
00433 { ++m_a_col[r_key_pos_pair.second]; }
00434
00435 private:
00436 std::vector<size_type> m_a_col;
00437
00438 size_type* const m_p_max_col;
00439 };
00440
00441 private:
00442 inline float
00443 get_load_imp(pb_assoc::detail::int_to_type<true>) const;
00444
00445 float m_load;
00446
00447 size_type m_size;
00448
00449 size_type m_num_col;
00450
00451 size_type m_max_col;
00452
00453 bool m_resize_needed;
00454
00455 static pb_assoc::detail::int_to_type<External_Load_Access>
00456 s_external_load_access_ind;
00457 };
00458
00459 #include <ext/pb_assoc/detail/resize_policy/cc_hash_max_collision_resize_trigger_imp.hpp>
00460
00461 #undef PB_ASSOC_CLASS_T_DEC
00462 #undef PB_ASSOC_CLASS_C_DEC
00463
00464 #undef PB_ASSOC_DBG_ASSERT
00465 #undef PB_ASSOC_DBG_VERIFY
00466 #undef PB_ASSOC_DBG_ONLY
00467
00468 #define PB_ASSOC_CLASS_T_DEC \
00469 template<typename Size_Type>
00470
00471 #define PB_ASSOC_CLASS_C_DEC \
00472 hash_exponential_size_policy< \
00473 Size_Type>
00474
00475 template<typename Size_Type = size_t>
00476 class hash_exponential_size_policy
00477 {
00478 public:
00479 typedef Size_Type size_type;
00480
00481 hash_exponential_size_policy(size_type start_size = 8,
00482 size_type grow_factor = 2);
00483
00484 void
00485 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00486
00487 protected:
00488 size_type
00489 get_init_size(size_type suggested_size) const;
00490
00491 size_type
00492 get_nearest_larger_size(size_type cur_size) const;
00493
00494 size_type
00495 get_nearest_smaller_size(size_type cur_size) const;
00496
00497 #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
00498 void
00499 assert_is_one_of_my_sizes(size_type size) const;
00500 #endif // #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
00501
00502 private:
00503 size_type m_start_size;
00504 size_type m_grow_factor;
00505 };
00506
00507 #include <ext/pb_assoc/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
00508
00509 #undef PB_ASSOC_CLASS_T_DEC
00510 #undef PB_ASSOC_CLASS_C_DEC
00511
00512 #undef PB_ASSOC_DBG_ASSERT
00513 #undef PB_ASSOC_DBG_VERIFY
00514 #undef PB_ASSOC_DBG_ONLY
00515
00516 #define PB_ASSOC_CLASS_T_DEC
00517
00518 #define PB_ASSOC_CLASS_C_DEC \
00519 hash_prime_size_policy
00520
00521 #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
00522 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00523 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00524 #define PB_ASSOC_DBG_ONLY(X) X
00525 #else // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
00526 #define PB_ASSOC_DBG_ASSERT(X)
00527 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00528 #define PB_ASSOC_DBG_ONLY(X) ;
00529 #endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
00530
00531 struct hash_prime_size_policy
00532 {
00533 typedef size_t size_type;
00534
00535 inline void
00536 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00537
00538 protected:
00539 inline size_type
00540 get_init_size(size_type suggested_size) const;
00541
00542 inline size_type
00543 get_nearest_larger_size(size_type cur_size) const;
00544
00545 inline size_type
00546 get_nearest_smaller_size(size_type cur_size) const;
00547
00548 inline size_type
00549 get_nearest_larger_size_imp(size_type size) const;
00550
00551 #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
00552 void
00553 assert_is_one_of_my_sizes(size_type size) const;
00554 #endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
00555 };
00556
00557 #include <ext/pb_assoc/detail/resize_policy/hash_prime_size_policy_imp.hpp>
00558
00559 #undef PB_ASSOC_CLASS_T_DEC
00560 #undef PB_ASSOC_CLASS_C_DEC
00561
00562 #undef PB_ASSOC_DBG_ASSERT
00563 #undef PB_ASSOC_DBG_VERIFY
00564 #undef PB_ASSOC_DBG_ONLY
00565
00566 #define PB_ASSOC_CLASS_T_DEC \
00567 template< \
00568 class Size_Policy, \
00569 class Trigger_Policy, \
00570 bool External_Size_Access, \
00571 typename Size_Type>
00572
00573 #define PB_ASSOC_CLASS_C_DEC \
00574 hash_standard_resize_policy< \
00575 Size_Policy, \
00576 Trigger_Policy, \
00577 External_Size_Access, \
00578 Size_Type>
00579
00580 template<class Size_Policy = pb_assoc::hash_exponential_size_policy<>,
00581 class Trigger_Policy = pb_assoc::hash_load_check_resize_trigger<>,
00582 bool External_Size_Access = false,
00583 typename Size_Type = size_t>
00584 class hash_standard_resize_policy : public Size_Policy, public Trigger_Policy
00585 {
00586 public:
00587 typedef Size_Type size_type;
00588 typedef Trigger_Policy trigger_policy;
00589 typedef Size_Policy size_policy;
00590
00591 enum
00592 {
00593 external_size_access = External_Size_Access
00594 };
00595
00596 hash_standard_resize_policy(size_type suggested_size = 8);
00597
00598 hash_standard_resize_policy(const Size_Policy&,
00599 size_type suggested_size = 8);
00600
00601 hash_standard_resize_policy(const Size_Policy&, const Trigger_Policy&,
00602 size_type suggested_size = 8);
00603
00604 virtual
00605 ~hash_standard_resize_policy();
00606
00607 inline void
00608 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00609
00610 Size_Policy&
00611 get_size_policy();
00612
00613 const Size_Policy&
00614 get_size_policy() const;
00615
00616 Trigger_Policy&
00617 get_trigger_policy();
00618
00619 const Trigger_Policy&
00620 get_trigger_policy() const;
00621
00622 inline size_type
00623 get_actual_size() const;
00624
00625 void
00626 resize(size_type suggested_new_size);
00627
00628 protected:
00629
00630 inline void
00631 notify_insert_search_start();
00632
00633 inline void
00634 notify_insert_search_collision();
00635
00636 inline void
00637 notify_insert_search_end();
00638
00639 inline void
00640 notify_find_search_start();
00641
00642 inline void
00643 notify_find_search_collision();
00644
00645 inline void
00646 notify_find_search_end();
00647
00648 inline void
00649 notify_erase_search_start();
00650
00651 inline void
00652 notify_erase_search_collision();
00653
00654 inline void
00655 notify_erase_search_end();
00656
00657 inline void
00658 notify_inserted(size_type num_e);
00659
00660 inline void
00661 notify_erased(size_type num_e);
00662
00663 void
00664 notify_cleared();
00665
00666 void
00667 notify_resized(size_type new_size);
00668
00669 size_type
00670 get_init_size() const;
00671
00672 inline bool
00673 is_resize_needed() const;
00674
00675 size_type
00676 get_new_size(size_type size, size_type num_used_e) const;
00677
00678 private:
00679 typedef Trigger_Policy my_trigger_policy_base;
00680
00681 typedef Size_Policy my_size_policy_base;
00682
00683 typedef
00684 pb_assoc::detail::int_to_type<false>
00685 external_resize_false_indicator;
00686
00687 typedef
00688 pb_assoc::detail::int_to_type<true>
00689 external_resize_true_indicator;
00690
00691 inline size_type
00692 get_actual_size(external_resize_true_indicator) const;
00693
00694 void
00695 resize(size_type new_size, external_resize_true_indicator);
00696
00697 virtual void
00698 do_resize(size_type new_size);
00699
00700 static pb_assoc::detail::int_to_type<External_Size_Access>
00701 s_external_size_access_indicator;
00702
00703 size_type m_size;
00704 };
00705
00706 #include <ext/pb_assoc/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
00707
00708 #undef PB_ASSOC_CLASS_T_DEC
00709 #undef PB_ASSOC_CLASS_C_DEC
00710
00711 #undef PB_ASSOC_DBG_ASSERT
00712 #undef PB_ASSOC_DBG_VERIFY
00713 #undef PB_ASSOC_DBG_ONLY
00714
00715 }
00716
00717 #endif // #ifndef HASH_POLICY_HPP