]>
Commit | Line | Data |
---|---|---|
1 | // -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2005-2014 Free Software Foundation, Inc. | |
4 | // | |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
8 | // Foundation; either version 3, or (at your option) any later | |
9 | // version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
37 | * @file hash_policy.hpp | |
38 | * Contains hash-related policies. | |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_HASH_POLICY_HPP | |
42 | #define PB_DS_HASH_POLICY_HPP | |
43 | ||
44 | #include <bits/c++config.h> | |
45 | #include <algorithm> | |
46 | #include <vector> | |
47 | #include <cmath> | |
48 | #include <ext/pb_ds/exception.hpp> | |
49 | #include <ext/pb_ds/detail/type_utils.hpp> | |
50 | #include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp> | |
51 | #include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp> | |
52 | #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp> | |
53 | ||
54 | namespace __gnu_pbds | |
55 | { | |
56 | #define PB_DS_CLASS_T_DEC template<typename Size_Type> | |
57 | #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type> | |
58 | ||
59 | /// A probe sequence policy using fixed increments. | |
60 | template<typename Size_Type = std::size_t> | |
61 | class linear_probe_fn | |
62 | { | |
63 | public: | |
64 | typedef Size_Type size_type; | |
65 | ||
66 | void | |
67 | swap(PB_DS_CLASS_C_DEC& other); | |
68 | ||
69 | protected: | |
70 | /// Returns the i-th offset from the hash value. | |
71 | inline size_type | |
72 | operator()(size_type i) const; | |
73 | }; | |
74 | ||
75 | #include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp> | |
76 | ||
77 | #undef PB_DS_CLASS_T_DEC | |
78 | #undef PB_DS_CLASS_C_DEC | |
79 | ||
80 | #define PB_DS_CLASS_T_DEC template<typename Size_Type> | |
81 | #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type> | |
82 | ||
83 | /// A probe sequence policy using square increments. | |
84 | template<typename Size_Type = std::size_t> | |
85 | class quadratic_probe_fn | |
86 | { | |
87 | public: | |
88 | typedef Size_Type size_type; | |
89 | ||
90 | void | |
91 | swap(PB_DS_CLASS_C_DEC& other); | |
92 | ||
93 | protected: | |
94 | /// Returns the i-th offset from the hash value. | |
95 | inline size_type | |
96 | operator()(size_type i) const; | |
97 | }; | |
98 | ||
99 | #include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp> | |
100 | ||
101 | #undef PB_DS_CLASS_T_DEC | |
102 | #undef PB_DS_CLASS_C_DEC | |
103 | ||
104 | #define PB_DS_CLASS_T_DEC template<typename Size_Type> | |
105 | #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> | |
106 | ||
107 | /// A mask range-hashing class (uses a bitmask). | |
108 | template<typename Size_Type = std::size_t> | |
109 | class direct_mask_range_hashing | |
110 | : public detail::mask_based_range_hashing<Size_Type> | |
111 | { | |
112 | private: | |
113 | typedef detail::mask_based_range_hashing<Size_Type> mask_based_base; | |
114 | ||
115 | public: | |
116 | typedef Size_Type size_type; | |
117 | ||
118 | void | |
119 | swap(PB_DS_CLASS_C_DEC& other); | |
120 | ||
121 | protected: | |
122 | void | |
123 | notify_resized(size_type size); | |
124 | ||
125 | /// Transforms the __hash value hash into a ranged-hash value | |
126 | /// (using a bit-mask). | |
127 | inline size_type | |
128 | operator()(size_type hash) const; | |
129 | }; | |
130 | ||
131 | #include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp> | |
132 | ||
133 | #undef PB_DS_CLASS_T_DEC | |
134 | #undef PB_DS_CLASS_C_DEC | |
135 | ||
136 | #define PB_DS_CLASS_T_DEC template<typename Size_Type> | |
137 | #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type> | |
138 | ||
139 | /// A mod range-hashing class (uses the modulo function). | |
140 | template<typename Size_Type = std::size_t> | |
141 | class direct_mod_range_hashing | |
142 | : public detail::mod_based_range_hashing<Size_Type> | |
143 | { | |
144 | public: | |
145 | typedef Size_Type size_type; | |
146 | ||
147 | void | |
148 | swap(PB_DS_CLASS_C_DEC& other); | |
149 | ||
150 | protected: | |
151 | void | |
152 | notify_resized(size_type size); | |
153 | ||
154 | /// Transforms the __hash value hash into a ranged-hash value | |
155 | /// (using a modulo operation). | |
156 | inline size_type | |
157 | operator()(size_type hash) const; | |
158 | ||
159 | private: | |
160 | typedef detail::mod_based_range_hashing<size_type> mod_based_base; | |
161 | }; | |
162 | ||
163 | #include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp> | |
164 | ||
165 | #undef PB_DS_CLASS_T_DEC | |
166 | #undef PB_DS_CLASS_C_DEC | |
167 | ||
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> | |
171 | ||
172 | /// A resize trigger policy based on a load check. It keeps the | |
173 | /// load factor between some load factors load_min and load_max. | |
174 | template<bool External_Load_Access = false, typename Size_Type = std::size_t> | |
175 | class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC | |
176 | { | |
177 | public: | |
178 | typedef Size_Type size_type; | |
179 | ||
180 | enum | |
181 | { | |
182 | /// Specifies whether the load factor can be accessed | |
183 | /// externally. The two options have different trade-offs in | |
184 | /// terms of flexibility, genericity, and encapsulation. | |
185 | external_load_access = External_Load_Access | |
186 | }; | |
187 | ||
188 | /// Default constructor, or constructor taking load_min and | |
189 | /// load_max load factors between which this policy will keep the | |
190 | /// actual load. | |
191 | hash_load_check_resize_trigger(float load_min = 0.125, | |
192 | float load_max = 0.5); | |
193 | ||
194 | void | |
195 | swap(hash_load_check_resize_trigger& other); | |
196 | ||
197 | virtual | |
198 | ~hash_load_check_resize_trigger(); | |
199 | ||
200 | /// Returns a pair of the minimal and maximal loads, respectively. | |
201 | inline std::pair<float, float> | |
202 | get_loads() const; | |
203 | ||
204 | /// Sets the loads through a pair of the minimal and maximal | |
205 | /// loads, respectively. | |
206 | void | |
207 | set_loads(std::pair<float, float> load_pair); | |
208 | ||
209 | protected: | |
210 | inline void | |
211 | notify_insert_search_start(); | |
212 | ||
213 | inline void | |
214 | notify_insert_search_collision(); | |
215 | ||
216 | inline void | |
217 | notify_insert_search_end(); | |
218 | ||
219 | inline void | |
220 | notify_find_search_start(); | |
221 | ||
222 | inline void | |
223 | notify_find_search_collision(); | |
224 | ||
225 | inline void | |
226 | notify_find_search_end(); | |
227 | ||
228 | inline void | |
229 | notify_erase_search_start(); | |
230 | ||
231 | inline void | |
232 | notify_erase_search_collision(); | |
233 | ||
234 | inline void | |
235 | notify_erase_search_end(); | |
236 | ||
237 | /// Notifies an element was inserted. The total number of entries | |
238 | /// in the table is num_entries. | |
239 | inline void | |
240 | notify_inserted(size_type num_entries); | |
241 | ||
242 | inline void | |
243 | notify_erased(size_type num_entries); | |
244 | ||
245 | /// Notifies the table was cleared. | |
246 | void | |
247 | notify_cleared(); | |
248 | ||
249 | /// Notifies the table was resized as a result of this object's | |
250 | /// signifying that a resize is needed. | |
251 | void | |
252 | notify_resized(size_type new_size); | |
253 | ||
254 | void | |
255 | notify_externally_resized(size_type new_size); | |
256 | ||
257 | inline bool | |
258 | is_resize_needed() const; | |
259 | ||
260 | inline bool | |
261 | is_grow_needed(size_type size, size_type num_entries) const; | |
262 | ||
263 | private: | |
264 | virtual void | |
265 | do_resize(size_type new_size); | |
266 | ||
267 | typedef PB_DS_SIZE_BASE_C_DEC size_base; | |
268 | ||
269 | #ifdef _GLIBCXX_DEBUG | |
270 | void | |
271 | assert_valid(const char* file, int line) const; | |
272 | #endif | |
273 | ||
274 | float m_load_min; | |
275 | float m_load_max; | |
276 | size_type m_next_shrink_size; | |
277 | size_type m_next_grow_size; | |
278 | bool m_resize_needed; | |
279 | }; | |
280 | ||
281 | #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp> | |
282 | ||
283 | #undef PB_DS_CLASS_T_DEC | |
284 | #undef PB_DS_CLASS_C_DEC | |
285 | #undef PB_DS_SIZE_BASE_C_DEC | |
286 | ||
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> | |
289 | ||
290 | /// A resize trigger policy based on collision checks. It keeps the | |
291 | /// simulated load factor lower than some given load factor. | |
292 | template<bool External_Load_Access = false, typename Size_Type = std::size_t> | |
293 | class cc_hash_max_collision_check_resize_trigger | |
294 | { | |
295 | public: | |
296 | typedef Size_Type size_type; | |
297 | ||
298 | enum | |
299 | { | |
300 | /// Specifies whether the load factor can be accessed | |
301 | /// externally. The two options have different trade-offs in | |
302 | /// terms of flexibility, genericity, and encapsulation. | |
303 | external_load_access = External_Load_Access | |
304 | }; | |
305 | ||
306 | /// Default constructor, or constructor taking load, a __load | |
307 | /// factor which it will attempt to maintain. | |
308 | cc_hash_max_collision_check_resize_trigger(float load = 0.5); | |
309 | ||
310 | void | |
311 | swap(PB_DS_CLASS_C_DEC& other); | |
312 | ||
313 | /// Returns the current load. | |
314 | inline float | |
315 | get_load() const; | |
316 | ||
317 | /// Sets the load; does not resize the container. | |
318 | void | |
319 | set_load(float load); | |
320 | ||
321 | protected: | |
322 | /// Notifies an insert search started. | |
323 | inline void | |
324 | notify_insert_search_start(); | |
325 | ||
326 | /// Notifies a search encountered a collision. | |
327 | inline void | |
328 | notify_insert_search_collision(); | |
329 | ||
330 | /// Notifies a search ended. | |
331 | inline void | |
332 | notify_insert_search_end(); | |
333 | ||
334 | /// Notifies a find search started. | |
335 | inline void | |
336 | notify_find_search_start(); | |
337 | ||
338 | /// Notifies a search encountered a collision. | |
339 | inline void | |
340 | notify_find_search_collision(); | |
341 | ||
342 | /// Notifies a search ended. | |
343 | inline void | |
344 | notify_find_search_end(); | |
345 | ||
346 | /// Notifies an erase search started. | |
347 | inline void | |
348 | notify_erase_search_start(); | |
349 | ||
350 | /// Notifies a search encountered a collision. | |
351 | inline void | |
352 | notify_erase_search_collision(); | |
353 | ||
354 | /// Notifies a search ended. | |
355 | inline void | |
356 | notify_erase_search_end(); | |
357 | ||
358 | /// Notifies an element was inserted. | |
359 | inline void | |
360 | notify_inserted(size_type num_entries); | |
361 | ||
362 | /// Notifies an element was erased. | |
363 | inline void | |
364 | notify_erased(size_type num_entries); | |
365 | ||
366 | /// Notifies the table was cleared. | |
367 | void | |
368 | notify_cleared(); | |
369 | ||
370 | /// Notifies the table was resized as a result of this object's | |
371 | /// signifying that a resize is needed. | |
372 | void | |
373 | notify_resized(size_type new_size); | |
374 | ||
375 | /// Notifies the table was resized externally. | |
376 | void | |
377 | notify_externally_resized(size_type new_size); | |
378 | ||
379 | /// Queries whether a resize is needed. | |
380 | inline bool | |
381 | is_resize_needed() const; | |
382 | ||
383 | /// Queries whether a grow is needed. This method is called only | |
384 | /// if this object indicated is needed. | |
385 | inline bool | |
386 | is_grow_needed(size_type size, size_type num_entries) const; | |
387 | ||
388 | private: | |
389 | void | |
390 | calc_max_num_coll(); | |
391 | ||
392 | inline void | |
393 | calc_resize_needed(); | |
394 | ||
395 | float m_load; | |
396 | size_type m_size; | |
397 | size_type m_num_col; | |
398 | size_type m_max_col; | |
399 | bool m_resize_needed; | |
400 | }; | |
401 | ||
402 | #include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp> | |
403 | ||
404 | #undef PB_DS_CLASS_T_DEC | |
405 | #undef PB_DS_CLASS_C_DEC | |
406 | ||
407 | #define PB_DS_CLASS_T_DEC template<typename Size_Type> | |
408 | #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type> | |
409 | ||
410 | /// A size policy whose sequence of sizes form an exponential | |
411 | /// sequence (typically powers of 2. | |
412 | template<typename Size_Type = std::size_t> | |
413 | class hash_exponential_size_policy | |
414 | { | |
415 | public: | |
416 | typedef Size_Type size_type; | |
417 | ||
418 | /// Default constructor, or onstructor taking a start_size, or | |
419 | /// constructor taking a start size and grow_factor. The policy | |
420 | /// will use the sequence of sizes start_size, start_size* | |
421 | /// grow_factor, start_size* grow_factor^2, ... | |
422 | hash_exponential_size_policy(size_type start_size = 8, | |
423 | size_type grow_factor = 2); | |
424 | ||
425 | void | |
426 | swap(PB_DS_CLASS_C_DEC& other); | |
427 | ||
428 | protected: | |
429 | size_type | |
430 | get_nearest_larger_size(size_type size) const; | |
431 | ||
432 | size_type | |
433 | get_nearest_smaller_size(size_type size) const; | |
434 | ||
435 | private: | |
436 | size_type m_start_size; | |
437 | size_type m_grow_factor; | |
438 | }; | |
439 | ||
440 | #include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp> | |
441 | ||
442 | #undef PB_DS_CLASS_T_DEC | |
443 | #undef PB_DS_CLASS_C_DEC | |
444 | ||
445 | #define PB_DS_CLASS_T_DEC | |
446 | #define PB_DS_CLASS_C_DEC hash_prime_size_policy | |
447 | ||
448 | /// A size policy whose sequence of sizes form a nearly-exponential | |
449 | /// sequence of primes. | |
450 | class hash_prime_size_policy | |
451 | { | |
452 | public: | |
453 | /// Size type. | |
454 | typedef std::size_t size_type; | |
455 | ||
456 | /// Default constructor, or onstructor taking a start_size The | |
457 | /// policy will use the sequence of sizes approximately | |
458 | /// start_size, start_size* 2, start_size* 2^2, ... | |
459 | hash_prime_size_policy(size_type start_size = 8); | |
460 | ||
461 | inline void | |
462 | swap(PB_DS_CLASS_C_DEC& other); | |
463 | ||
464 | protected: | |
465 | size_type | |
466 | get_nearest_larger_size(size_type size) const; | |
467 | ||
468 | size_type | |
469 | get_nearest_smaller_size(size_type size) const; | |
470 | ||
471 | private: | |
472 | size_type m_start_size; | |
473 | }; | |
474 | ||
475 | #include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp> | |
476 | ||
477 | #undef PB_DS_CLASS_T_DEC | |
478 | #undef PB_DS_CLASS_C_DEC | |
479 | ||
480 | #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type> | |
481 | ||
482 | #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type> | |
483 | ||
484 | /// A resize policy which delegates operations to size and trigger policies. | |
485 | template<typename Size_Policy = hash_exponential_size_policy<>, | |
486 | typename Trigger_Policy = hash_load_check_resize_trigger<>, | |
487 | bool External_Size_Access = false, | |
488 | typename Size_Type = std::size_t> | |
489 | class hash_standard_resize_policy | |
490 | : public Size_Policy, public Trigger_Policy | |
491 | { | |
492 | public: | |
493 | typedef Size_Type size_type; | |
494 | typedef Trigger_Policy trigger_policy; | |
495 | typedef Size_Policy size_policy; | |
496 | ||
497 | enum | |
498 | { | |
499 | external_size_access = External_Size_Access | |
500 | }; | |
501 | ||
502 | /// Default constructor. | |
503 | hash_standard_resize_policy(); | |
504 | ||
505 | /// constructor taking some policies r_size_policy will be copied | |
506 | /// by the Size_Policy object of this object. | |
507 | hash_standard_resize_policy(const Size_Policy& r_size_policy); | |
508 | ||
509 | /// constructor taking some policies. r_size_policy will be | |
510 | /// copied by the Size_Policy object of this | |
511 | /// object. r_trigger_policy will be copied by the Trigger_Policy | |
512 | /// object of this object. | |
513 | hash_standard_resize_policy(const Size_Policy& r_size_policy, | |
514 | const Trigger_Policy& r_trigger_policy); | |
515 | ||
516 | virtual | |
517 | ~hash_standard_resize_policy(); | |
518 | ||
519 | inline void | |
520 | swap(PB_DS_CLASS_C_DEC& other); | |
521 | ||
522 | /// Access to the Size_Policy object used. | |
523 | Size_Policy& | |
524 | get_size_policy(); | |
525 | ||
526 | /// Const access to the Size_Policy object used. | |
527 | const Size_Policy& | |
528 | get_size_policy() const; | |
529 | ||
530 | /// Access to the Trigger_Policy object used. | |
531 | Trigger_Policy& | |
532 | get_trigger_policy(); | |
533 | ||
534 | /// Access to the Trigger_Policy object used. | |
535 | const Trigger_Policy& | |
536 | get_trigger_policy() const; | |
537 | ||
538 | /// Returns the actual size of the container. | |
539 | inline size_type | |
540 | get_actual_size() const; | |
541 | ||
542 | /// Resizes the container to suggested_new_size, a suggested size | |
543 | /// (the actual size will be determined by the Size_Policy | |
544 | /// object). | |
545 | void | |
546 | resize(size_type suggested_new_size); | |
547 | ||
548 | protected: | |
549 | inline void | |
550 | notify_insert_search_start(); | |
551 | ||
552 | inline void | |
553 | notify_insert_search_collision(); | |
554 | ||
555 | inline void | |
556 | notify_insert_search_end(); | |
557 | ||
558 | inline void | |
559 | notify_find_search_start(); | |
560 | ||
561 | inline void | |
562 | notify_find_search_collision(); | |
563 | ||
564 | inline void | |
565 | notify_find_search_end(); | |
566 | ||
567 | inline void | |
568 | notify_erase_search_start(); | |
569 | ||
570 | inline void | |
571 | notify_erase_search_collision(); | |
572 | ||
573 | inline void | |
574 | notify_erase_search_end(); | |
575 | ||
576 | inline void | |
577 | notify_inserted(size_type num_e); | |
578 | ||
579 | inline void | |
580 | notify_erased(size_type num_e); | |
581 | ||
582 | void | |
583 | notify_cleared(); | |
584 | ||
585 | void | |
586 | notify_resized(size_type new_size); | |
587 | ||
588 | inline bool | |
589 | is_resize_needed() const; | |
590 | ||
591 | /// Queries what the new size should be, when the container is | |
592 | /// resized naturally. The current __size of the container is | |
593 | /// size, and the number of used entries within the container is | |
594 | /// num_used_e. | |
595 | size_type | |
596 | get_new_size(size_type size, size_type num_used_e) const; | |
597 | ||
598 | private: | |
599 | /// Resizes to new_size. | |
600 | virtual void | |
601 | do_resize(size_type new_size); | |
602 | ||
603 | typedef Trigger_Policy trigger_policy_base; | |
604 | ||
605 | typedef Size_Policy size_policy_base; | |
606 | ||
607 | size_type m_size; | |
608 | }; | |
609 | ||
610 | #include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp> | |
611 | ||
612 | #undef PB_DS_CLASS_T_DEC | |
613 | #undef PB_DS_CLASS_C_DEC | |
614 | ||
615 | } // namespace __gnu_pbds | |
616 | ||
617 | #endif |