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