41 #ifndef PB_DS_HASH_POLICY_HPP
42 #define PB_DS_HASH_POLICY_HPP
56 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
57 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
60 template<
typename Size_Type = std::
size_t>
64 typedef Size_Type size_type;
67 swap(PB_DS_CLASS_C_DEC& other);
77 #undef PB_DS_CLASS_T_DEC
78 #undef PB_DS_CLASS_C_DEC
80 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
81 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
84 template<
typename Size_Type = std::
size_t>
88 typedef Size_Type size_type;
91 swap(PB_DS_CLASS_C_DEC& other);
101 #undef PB_DS_CLASS_T_DEC
102 #undef PB_DS_CLASS_C_DEC
104 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
105 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
108 template<
typename Size_Type = std::
size_t>
116 typedef Size_Type size_type;
119 swap(PB_DS_CLASS_C_DEC& other);
123 notify_resized(size_type size);
133 #undef PB_DS_CLASS_T_DEC
134 #undef PB_DS_CLASS_C_DEC
136 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
137 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
140 template<
typename Size_Type = std::
size_t>
145 typedef Size_Type size_type;
148 swap(PB_DS_CLASS_C_DEC& other);
152 notify_resized(size_type size);
165 #undef PB_DS_CLASS_T_DEC
166 #undef PB_DS_CLASS_C_DEC
168 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
169 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
170 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
174 template<
bool External_Load_Access = false,
typename Size_Type = std::
size_t>
178 typedef Size_Type size_type;
192 float load_max = 0.5);
211 notify_insert_search_start();
214 notify_insert_search_collision();
217 notify_insert_search_end();
220 notify_find_search_start();
223 notify_find_search_collision();
226 notify_find_search_end();
229 notify_erase_search_start();
232 notify_erase_search_collision();
235 notify_erase_search_end();
243 notify_erased(size_type num_entries);
255 notify_externally_resized(size_type new_size);
258 is_resize_needed()
const;
261 is_grow_needed(size_type size, size_type num_entries)
const;
265 do_resize(size_type new_size);
267 typedef PB_DS_SIZE_BASE_C_DEC size_base;
269 #ifdef _GLIBCXX_DEBUG
271 assert_valid(
const char* file,
int line)
const;
276 size_type m_next_shrink_size;
277 size_type m_next_grow_size;
278 bool m_resize_needed;
283 #undef PB_DS_CLASS_T_DEC
284 #undef PB_DS_CLASS_C_DEC
285 #undef PB_DS_SIZE_BASE_C_DEC
287 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
288 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
292 template<
bool External_Load_Access = false,
typename Size_Type = std::
size_t>
296 typedef Size_Type size_type;
311 swap(PB_DS_CLASS_C_DEC& other);
393 calc_resize_needed();
399 bool m_resize_needed;
404 #undef PB_DS_CLASS_T_DEC
405 #undef PB_DS_CLASS_C_DEC
407 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
408 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
412 template<
typename Size_Type = std::
size_t>
416 typedef Size_Type size_type;
423 size_type grow_factor = 2);
426 swap(PB_DS_CLASS_C_DEC& other);
430 get_nearest_larger_size(size_type size)
const;
433 get_nearest_smaller_size(size_type size)
const;
436 size_type m_start_size;
437 size_type m_grow_factor;
442 #undef PB_DS_CLASS_T_DEC
443 #undef PB_DS_CLASS_C_DEC
445 #define PB_DS_CLASS_T_DEC
446 #define PB_DS_CLASS_C_DEC hash_prime_size_policy
462 swap(PB_DS_CLASS_C_DEC& other);
466 get_nearest_larger_size(
size_type size)
const;
469 get_nearest_smaller_size(
size_type size)
const;
477 #undef PB_DS_CLASS_T_DEC
478 #undef PB_DS_CLASS_C_DEC
480 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
482 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
485 template<
typename Size_Policy = hash_exponential_size_policy<>,
486 typename Trigger_Policy = hash_load_check_re
size_trigger<>,
487 bool External_Size_Access = false,
488 typename Size_Type = std::
size_t>
490 :
public Size_Policy,
public Trigger_Policy
493 typedef Size_Type size_type;
494 typedef Trigger_Policy trigger_policy;
495 typedef Size_Policy size_policy;
499 external_size_access = External_Size_Access
514 const Trigger_Policy& r_trigger_policy);
520 swap(PB_DS_CLASS_C_DEC& other);
535 const Trigger_Policy&
546 resize(size_type suggested_new_size);
550 notify_insert_search_start();
553 notify_insert_search_collision();
556 notify_insert_search_end();
559 notify_find_search_start();
562 notify_find_search_collision();
565 notify_find_search_end();
568 notify_erase_search_start();
571 notify_erase_search_collision();
574 notify_erase_search_end();
577 notify_inserted(size_type num_e);
580 notify_erased(size_type num_e);
586 notify_resized(size_type new_size);
589 is_resize_needed()
const;
596 get_new_size(size_type size, size_type num_used_e)
const;
601 do_resize(size_type new_size);
603 typedef Trigger_Policy trigger_policy_base;
605 typedef Size_Policy size_policy_base;
612 #undef PB_DS_CLASS_T_DEC
613 #undef PB_DS_CLASS_C_DEC
void notify_erase_search_start()
Notifies an erase search started.
A probe sequence policy using fixed increments.
void notify_insert_search_end()
Notifies a search ended.
void set_load(float load)
Sets the load; does not resize the container.
hash_exponential_size_policy(size_type start_size=8, size_type grow_factor=2)
Default constructor, or onstructor taking a start_size, or constructor taking a start size and grow_f...
void notify_insert_search_collision()
Notifies a search encountered a collision.
A mod range-hashing class (uses the modulo function).
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object's signifying that a resize is needed...
size_type get_actual_size() const
Returns the actual size of the container.
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a modulo operation).
A size policy whose sequence of sizes form a nearly-exponential sequence of primes.
Trigger_Policy & get_trigger_policy()
Access to the Trigger_Policy object used.
A size policy whose sequence of sizes form an exponential sequence (typically powers of 2...
void resize(size_type suggested_new_size)
Resizes the container to suggested_new_size, a suggested size (the actual size will be determined by ...
void notify_find_search_collision()
Notifies a search encountered a collision.
bool is_grow_needed(size_type size, size_type num_entries) const
Queries whether a grow is needed. This method is called only if this object indicated is needed...
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a bit-mask).
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
void notify_cleared()
Notifies the table was cleared.
void notify_inserted(size_type num_entries)
Notifies an element was inserted.
void notify_find_search_end()
Notifies a search ended.
A resize trigger policy based on a load check. It keeps the load factor between some load factors loa...
Struct holding two objects of arbitrary type.
void notify_insert_search_start()
Notifies an insert search started.
A mask range-hashing class (uses a bitmask).
A probe sequence policy using square increments.
Size_Policy & get_size_policy()
Access to the Size_Policy object used.
cc_hash_max_collision_check_resize_trigger(float load=0.5)
Default constructor, or constructor taking load, a __load factor which it will attempt to maintain...
void notify_erased(size_type num_entries)
Notifies an element was erased.
hash_load_check_resize_trigger(float load_min=0.125, float load_max=0.5)
Default constructor, or constructor taking load_min and load_max load factors between which this poli...
void notify_find_search_start()
Notifies a find search started.
void set_loads(std::pair< float, float > load_pair)
Sets the loads through a pair of the minimal and maximal loads, respectively.
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
void notify_erase_search_collision()
Notifies a search encountered a collision.
bool is_resize_needed() const
Queries whether a resize is needed.
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object's signifying that a resize is needed...
size_type get_new_size(size_type size, size_type num_used_e) const
Queries what the new size should be, when the container is resized naturally. The current __size of t...
std::size_t size_type
Size type.
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
void notify_erase_search_end()
Notifies a search ended.
float get_load() const
Returns the current load.
A resize policy which delegates operations to size and trigger policies.
hash_standard_resize_policy()
Default constructor.
void notify_inserted(size_type num_entries)
Notifies an element was inserted. The total number of entries in the table is num_entries.
hash_prime_size_policy(size_type start_size=8)
Default constructor, or onstructor taking a start_size The policy will use the sequence of sizes appr...
std::pair< float, float > get_loads() const
Returns a pair of the minimal and maximal loads, respectively.
void notify_cleared()
Notifies the table was cleared.
void notify_externally_resized(size_type new_size)
Notifies the table was resized externally.
A resize trigger policy based on collision checks. It keeps the simulated load factor lower than some...
Specifies whether the load factor can be accessed externally. The two options have different trade-of...