41 #ifndef PB_DS_HASH_POLICY_HPP
42 #define PB_DS_HASH_POLICY_HPP
49 #include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
50 #include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
51 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>
65 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
66 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
69 template<
typename Size_Type =
size_t>
73 typedef Size_Type size_type;
76 swap(PB_DS_CLASS_C_DEC& other);
81 operator()(size_type i)
const;
84 #include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>
86 #undef PB_DS_CLASS_T_DEC
87 #undef PB_DS_CLASS_C_DEC
89 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
90 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
93 template<
typename Size_Type =
size_t>
94 class quadratic_probe_fn
97 typedef Size_Type size_type;
100 swap(PB_DS_CLASS_C_DEC& other);
105 operator()(size_type i)
const;
108 #include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>
110 #undef PB_DS_CLASS_T_DEC
111 #undef PB_DS_CLASS_C_DEC
113 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
114 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
117 template<
typename Size_Type =
size_t>
118 class direct_mask_range_hashing
119 :
public detail::mask_based_range_hashing<Size_Type>
122 typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;
125 typedef Size_Type size_type;
128 swap(PB_DS_CLASS_C_DEC& other);
132 notify_resized(size_type size);
137 operator()(size_type hash)
const;
140 #include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
142 #undef PB_DS_CLASS_T_DEC
143 #undef PB_DS_CLASS_C_DEC
145 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
146 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
149 template<
typename Size_Type =
size_t>
150 class direct_mod_range_hashing
151 :
public detail::mod_based_range_hashing<Size_Type>
154 typedef Size_Type size_type;
157 swap(PB_DS_CLASS_C_DEC& other);
161 notify_resized(size_type size);
166 operator()(size_type hash)
const;
169 typedef detail::mod_based_range_hashing<size_type> mod_based_base;
172 #include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
174 #undef PB_DS_CLASS_T_DEC
175 #undef PB_DS_CLASS_C_DEC
177 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
178 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
179 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
183 template<
bool External_Load_Access = false,
typename Size_Type =
size_t>
184 class hash_load_check_resize_trigger :
private PB_DS_SIZE_BASE_C_DEC
187 typedef Size_Type size_type;
191 external_load_access = External_Load_Access
197 hash_load_check_resize_trigger(
float load_min = 0.125,
198 float load_max = 0.5);
201 swap(hash_load_check_resize_trigger& other);
204 ~hash_load_check_resize_trigger();
217 notify_insert_search_start();
220 notify_insert_search_collision();
223 notify_insert_search_end();
226 notify_find_search_start();
229 notify_find_search_collision();
232 notify_find_search_end();
235 notify_erase_search_start();
238 notify_erase_search_collision();
241 notify_erase_search_end();
246 notify_inserted(size_type num_entries);
249 notify_erased(size_type num_entries);
258 notify_resized(size_type new_size);
261 notify_externally_resized(size_type new_size);
264 is_resize_needed()
const;
267 is_grow_needed(size_type size, size_type num_entries)
const;
271 do_resize(size_type new_size);
273 typedef PB_DS_SIZE_BASE_C_DEC size_base;
275 #ifdef _GLIBCXX_DEBUG
277 assert_valid()
const;
282 size_type m_next_shrink_size;
283 size_type m_next_grow_size;
284 bool m_resize_needed;
287 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
289 #undef PB_DS_CLASS_T_DEC
290 #undef PB_DS_CLASS_C_DEC
291 #undef PB_DS_SIZE_BASE_C_DEC
293 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
294 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
298 template<
bool External_Load_Access = false,
typename Size_Type =
size_t>
299 class cc_hash_max_collision_check_resize_trigger
302 typedef Size_Type size_type;
306 external_load_access = External_Load_Access
311 cc_hash_max_collision_check_resize_trigger(
float load = 0.5);
314 swap(PB_DS_CLASS_C_DEC& other);
322 set_load(
float load);
326 notify_insert_search_start();
329 notify_insert_search_collision();
332 notify_insert_search_end();
335 notify_find_search_start();
338 notify_find_search_collision();
341 notify_find_search_end();
344 notify_erase_search_start();
347 notify_erase_search_collision();
350 notify_erase_search_end();
353 notify_inserted(size_type num_entries);
356 notify_erased(size_type num_entries);
364 notify_resized(size_type new_size);
367 notify_externally_resized(size_type new_size);
370 is_resize_needed()
const;
373 is_grow_needed(size_type size, size_type num_entries)
const;
380 calc_resize_needed();
386 bool m_resize_needed;
389 #include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
391 #undef PB_DS_CLASS_T_DEC
392 #undef PB_DS_CLASS_C_DEC
394 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
395 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
399 template<
typename Size_Type =
size_t>
400 class hash_exponential_size_policy
403 typedef Size_Type size_type;
409 hash_exponential_size_policy(size_type start_size = 8,
410 size_type grow_factor = 2);
413 swap(PB_DS_CLASS_C_DEC& other);
417 get_nearest_larger_size(size_type size)
const;
420 get_nearest_smaller_size(size_type size)
const;
423 size_type m_start_size;
424 size_type m_grow_factor;
427 #include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
429 #undef PB_DS_CLASS_T_DEC
430 #undef PB_DS_CLASS_C_DEC
432 #define PB_DS_CLASS_T_DEC
433 #define PB_DS_CLASS_C_DEC hash_prime_size_policy
437 class hash_prime_size_policy
441 typedef size_t size_type;
446 hash_prime_size_policy(size_type start_size = 8);
449 swap(PB_DS_CLASS_C_DEC& other);
453 get_nearest_larger_size(size_type size)
const;
456 get_nearest_smaller_size(size_type size)
const;
459 size_type m_start_size;
462 #include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
464 #undef PB_DS_CLASS_T_DEC
465 #undef PB_DS_CLASS_C_DEC
467 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
469 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
472 template<
typename Size_Policy = hash_exponential_size_policy<>,
473 typename Trigger_Policy = hash_load_check_re
size_trigger<>,
474 bool External_Size_Access = false,
475 typename Size_Type =
size_t>
476 class hash_standard_resize_policy
477 :
public Size_Policy,
public Trigger_Policy
480 typedef Size_Type size_type;
481 typedef Trigger_Policy trigger_policy;
482 typedef Size_Policy size_policy;
486 external_size_access = External_Size_Access
490 hash_standard_resize_policy();
494 hash_standard_resize_policy(
const Size_Policy& r_size_policy);
500 hash_standard_resize_policy(
const Size_Policy& r_size_policy,
501 const Trigger_Policy& r_trigger_policy);
504 ~hash_standard_resize_policy();
507 swap(PB_DS_CLASS_C_DEC& other);
515 get_size_policy()
const;
519 get_trigger_policy();
522 const Trigger_Policy&
523 get_trigger_policy()
const;
527 get_actual_size()
const;
533 resize(size_type suggested_new_size);
537 notify_insert_search_start();
540 notify_insert_search_collision();
543 notify_insert_search_end();
546 notify_find_search_start();
549 notify_find_search_collision();
552 notify_find_search_end();
555 notify_erase_search_start();
558 notify_erase_search_collision();
561 notify_erase_search_end();
564 notify_inserted(size_type num_e);
567 notify_erased(size_type num_e);
573 notify_resized(size_type new_size);
576 is_resize_needed()
const;
583 get_new_size(size_type size, size_type num_used_e)
const;
588 do_resize(size_type new_size);
590 typedef Trigger_Policy trigger_policy_base;
592 typedef Size_Policy size_policy_base;
597 #include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
599 #undef PB_DS_CLASS_T_DEC
600 #undef PB_DS_CLASS_C_DEC
pair holds two objects of arbitrary type.