Go to the documentation of this file.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 #ifndef PB_DS_HASH_POLICY_HPP
00042 #define PB_DS_HASH_POLICY_HPP
00043
00044 #include <bits/c++config.h>
00045 #include <algorithm>
00046 #include <vector>
00047 #include <cmath>
00048 #include <ext/pb_ds/exception.hpp>
00049 #include <ext/pb_ds/detail/type_utils.hpp>
00050 #include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
00051 #include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
00052 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>
00053
00054 namespace __gnu_pbds
00055 {
00056
00057
00058 struct null_hash_fn
00059 { };
00060
00061
00062
00063 struct null_probe_fn
00064 { };
00065
00066 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00067 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
00068
00069
00070 template<typename Size_Type = std::size_t>
00071 class linear_probe_fn
00072 {
00073 public:
00074 typedef Size_Type size_type;
00075
00076 void
00077 swap(PB_DS_CLASS_C_DEC& other);
00078
00079 protected:
00080
00081 inline size_type
00082 operator()(size_type i) const;
00083 };
00084
00085 #include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>
00086
00087 #undef PB_DS_CLASS_T_DEC
00088 #undef PB_DS_CLASS_C_DEC
00089
00090 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00091 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
00092
00093
00094 template<typename Size_Type = std::size_t>
00095 class quadratic_probe_fn
00096 {
00097 public:
00098 typedef Size_Type size_type;
00099
00100 void
00101 swap(PB_DS_CLASS_C_DEC& other);
00102
00103 protected:
00104
00105 inline size_type
00106 operator()(size_type i) const;
00107 };
00108
00109 #include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>
00110
00111 #undef PB_DS_CLASS_T_DEC
00112 #undef PB_DS_CLASS_C_DEC
00113
00114 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00115 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
00116
00117
00118 template<typename Size_Type = std::size_t>
00119 class direct_mask_range_hashing
00120 : public detail::mask_based_range_hashing<Size_Type>
00121 {
00122 private:
00123 typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;
00124
00125 public:
00126 typedef Size_Type size_type;
00127
00128 void
00129 swap(PB_DS_CLASS_C_DEC& other);
00130
00131 protected:
00132 void
00133 notify_resized(size_type size);
00134
00135
00136
00137 inline size_type
00138 operator()(size_type hash) const;
00139 };
00140
00141 #include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
00142
00143 #undef PB_DS_CLASS_T_DEC
00144 #undef PB_DS_CLASS_C_DEC
00145
00146 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00147 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
00148
00149
00150 template<typename Size_Type = std::size_t>
00151 class direct_mod_range_hashing
00152 : public detail::mod_based_range_hashing<Size_Type>
00153 {
00154 public:
00155 typedef Size_Type size_type;
00156
00157 void
00158 swap(PB_DS_CLASS_C_DEC& other);
00159
00160 protected:
00161 void
00162 notify_resized(size_type size);
00163
00164
00165
00166 inline size_type
00167 operator()(size_type hash) const;
00168
00169 private:
00170 typedef detail::mod_based_range_hashing<size_type> mod_based_base;
00171 };
00172
00173 #include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
00174
00175 #undef PB_DS_CLASS_T_DEC
00176 #undef PB_DS_CLASS_C_DEC
00177
00178 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
00179 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
00180 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
00181
00182
00183
00184 template<bool External_Load_Access = false, typename Size_Type = std::size_t>
00185 class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC
00186 {
00187 public:
00188 typedef Size_Type size_type;
00189
00190 enum
00191 {
00192 external_load_access = External_Load_Access
00193 };
00194
00195
00196
00197
00198 hash_load_check_resize_trigger(float load_min = 0.125,
00199 float load_max = 0.5);
00200
00201 void
00202 swap(hash_load_check_resize_trigger& other);
00203
00204 virtual
00205 ~hash_load_check_resize_trigger();
00206
00207
00208 inline std::pair<float, float>
00209 get_loads() const;
00210
00211
00212
00213 void
00214 set_loads(std::pair<float, float> load_pair);
00215
00216 protected:
00217 inline void
00218 notify_insert_search_start();
00219
00220 inline void
00221 notify_insert_search_collision();
00222
00223 inline void
00224 notify_insert_search_end();
00225
00226 inline void
00227 notify_find_search_start();
00228
00229 inline void
00230 notify_find_search_collision();
00231
00232 inline void
00233 notify_find_search_end();
00234
00235 inline void
00236 notify_erase_search_start();
00237
00238 inline void
00239 notify_erase_search_collision();
00240
00241 inline void
00242 notify_erase_search_end();
00243
00244
00245
00246 inline void
00247 notify_inserted(size_type num_entries);
00248
00249 inline void
00250 notify_erased(size_type num_entries);
00251
00252
00253 void
00254 notify_cleared();
00255
00256
00257
00258 void
00259 notify_resized(size_type new_size);
00260
00261 void
00262 notify_externally_resized(size_type new_size);
00263
00264 inline bool
00265 is_resize_needed() const;
00266
00267 inline bool
00268 is_grow_needed(size_type size, size_type num_entries) const;
00269
00270 private:
00271 virtual void
00272 do_resize(size_type new_size);
00273
00274 typedef PB_DS_SIZE_BASE_C_DEC size_base;
00275
00276 #ifdef _GLIBCXX_DEBUG
00277 void
00278 assert_valid() const;
00279 #endif
00280
00281 float m_load_min;
00282 float m_load_max;
00283 size_type m_next_shrink_size;
00284 size_type m_next_grow_size;
00285 bool m_resize_needed;
00286 };
00287
00288 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
00289
00290 #undef PB_DS_CLASS_T_DEC
00291 #undef PB_DS_CLASS_C_DEC
00292 #undef PB_DS_SIZE_BASE_C_DEC
00293
00294 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
00295 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
00296
00297
00298
00299 template<bool External_Load_Access = false, typename Size_Type = std::size_t>
00300 class cc_hash_max_collision_check_resize_trigger
00301 {
00302 public:
00303 typedef Size_Type size_type;
00304
00305 enum
00306 {
00307 external_load_access = External_Load_Access
00308 };
00309
00310
00311
00312 cc_hash_max_collision_check_resize_trigger(float load = 0.5);
00313
00314 void
00315 swap(PB_DS_CLASS_C_DEC& other);
00316
00317
00318 inline float
00319 get_load() const;
00320
00321
00322 void
00323 set_load(float load);
00324
00325 protected:
00326 inline void
00327 notify_insert_search_start();
00328
00329 inline void
00330 notify_insert_search_collision();
00331
00332 inline void
00333 notify_insert_search_end();
00334
00335 inline void
00336 notify_find_search_start();
00337
00338 inline void
00339 notify_find_search_collision();
00340
00341 inline void
00342 notify_find_search_end();
00343
00344 inline void
00345 notify_erase_search_start();
00346
00347 inline void
00348 notify_erase_search_collision();
00349
00350 inline void
00351 notify_erase_search_end();
00352
00353 inline void
00354 notify_inserted(size_type num_entries);
00355
00356 inline void
00357 notify_erased(size_type num_entries);
00358
00359 void
00360 notify_cleared();
00361
00362
00363
00364 void
00365 notify_resized(size_type new_size);
00366
00367 void
00368 notify_externally_resized(size_type new_size);
00369
00370 inline bool
00371 is_resize_needed() const;
00372
00373 inline bool
00374 is_grow_needed(size_type size, size_type num_entries) const;
00375
00376 private:
00377 void
00378 calc_max_num_coll();
00379
00380 inline void
00381 calc_resize_needed();
00382
00383 float m_load;
00384 size_type m_size;
00385 size_type m_num_col;
00386 size_type m_max_col;
00387 bool m_resize_needed;
00388 };
00389
00390 #include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
00391
00392 #undef PB_DS_CLASS_T_DEC
00393 #undef PB_DS_CLASS_C_DEC
00394
00395 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00396 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
00397
00398
00399
00400 template<typename Size_Type = std::size_t>
00401 class hash_exponential_size_policy
00402 {
00403 public:
00404 typedef Size_Type size_type;
00405
00406
00407
00408
00409
00410 hash_exponential_size_policy(size_type start_size = 8,
00411 size_type grow_factor = 2);
00412
00413 void
00414 swap(PB_DS_CLASS_C_DEC& other);
00415
00416 protected:
00417 size_type
00418 get_nearest_larger_size(size_type size) const;
00419
00420 size_type
00421 get_nearest_smaller_size(size_type size) const;
00422
00423 private:
00424 size_type m_start_size;
00425 size_type m_grow_factor;
00426 };
00427
00428 #include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
00429
00430 #undef PB_DS_CLASS_T_DEC
00431 #undef PB_DS_CLASS_C_DEC
00432
00433 #define PB_DS_CLASS_T_DEC
00434 #define PB_DS_CLASS_C_DEC hash_prime_size_policy
00435
00436
00437
00438 class hash_prime_size_policy
00439 {
00440 public:
00441
00442 typedef std::size_t size_type;
00443
00444
00445
00446
00447 hash_prime_size_policy(size_type start_size = 8);
00448
00449 inline void
00450 swap(PB_DS_CLASS_C_DEC& other);
00451
00452 protected:
00453 size_type
00454 get_nearest_larger_size(size_type size) const;
00455
00456 size_type
00457 get_nearest_smaller_size(size_type size) const;
00458
00459 private:
00460 size_type m_start_size;
00461 };
00462
00463 #include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
00464
00465 #undef PB_DS_CLASS_T_DEC
00466 #undef PB_DS_CLASS_C_DEC
00467
00468 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
00469
00470 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
00471
00472
00473 template<typename Size_Policy = hash_exponential_size_policy<>,
00474 typename Trigger_Policy = hash_load_check_resize_trigger<>,
00475 bool External_Size_Access = false,
00476 typename Size_Type = std::size_t>
00477 class hash_standard_resize_policy
00478 : public Size_Policy, public Trigger_Policy
00479 {
00480 public:
00481 typedef Size_Type size_type;
00482 typedef Trigger_Policy trigger_policy;
00483 typedef Size_Policy size_policy;
00484
00485 enum
00486 {
00487 external_size_access = External_Size_Access
00488 };
00489
00490
00491 hash_standard_resize_policy();
00492
00493
00494
00495 hash_standard_resize_policy(const Size_Policy& r_size_policy);
00496
00497
00498
00499
00500
00501 hash_standard_resize_policy(const Size_Policy& r_size_policy,
00502 const Trigger_Policy& r_trigger_policy);
00503
00504 virtual
00505 ~hash_standard_resize_policy();
00506
00507 inline void
00508 swap(PB_DS_CLASS_C_DEC& other);
00509
00510
00511 Size_Policy&
00512 get_size_policy();
00513
00514
00515 const Size_Policy&
00516 get_size_policy() const;
00517
00518
00519 Trigger_Policy&
00520 get_trigger_policy();
00521
00522
00523 const Trigger_Policy&
00524 get_trigger_policy() const;
00525
00526
00527 inline size_type
00528 get_actual_size() const;
00529
00530
00531
00532
00533 void
00534 resize(size_type suggested_new_size);
00535
00536 protected:
00537 inline void
00538 notify_insert_search_start();
00539
00540 inline void
00541 notify_insert_search_collision();
00542
00543 inline void
00544 notify_insert_search_end();
00545
00546 inline void
00547 notify_find_search_start();
00548
00549 inline void
00550 notify_find_search_collision();
00551
00552 inline void
00553 notify_find_search_end();
00554
00555 inline void
00556 notify_erase_search_start();
00557
00558 inline void
00559 notify_erase_search_collision();
00560
00561 inline void
00562 notify_erase_search_end();
00563
00564 inline void
00565 notify_inserted(size_type num_e);
00566
00567 inline void
00568 notify_erased(size_type num_e);
00569
00570 void
00571 notify_cleared();
00572
00573 void
00574 notify_resized(size_type new_size);
00575
00576 inline bool
00577 is_resize_needed() const;
00578
00579
00580
00581
00582
00583 size_type
00584 get_new_size(size_type size, size_type num_used_e) const;
00585
00586 private:
00587
00588 virtual void
00589 do_resize(size_type new_size);
00590
00591 typedef Trigger_Policy trigger_policy_base;
00592
00593 typedef Size_Policy size_policy_base;
00594
00595 size_type m_size;
00596 };
00597
00598 #include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
00599
00600 #undef PB_DS_CLASS_T_DEC
00601 #undef PB_DS_CLASS_C_DEC
00602
00603 }
00604
00605 #endif