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