libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2013 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file gp_hash_table_map_/gp_ht_map_.hpp 00038 * Contains an implementation class for general probing hash. 00039 */ 00040 00041 #include <ext/pb_ds/tag_and_trait.hpp> 00042 #include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp> 00043 #include <ext/pb_ds/detail/types_traits.hpp> 00044 #include <ext/pb_ds/exception.hpp> 00045 #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 00046 #include <utility> 00047 #ifdef PB_DS_HT_MAP_TRACE_ 00048 #include <iostream> 00049 #endif 00050 #ifdef _GLIBCXX_DEBUG 00051 #include <ext/pb_ds/detail/debug_map_base.hpp> 00052 #endif 00053 #include <debug/debug.h> 00054 00055 namespace __gnu_pbds 00056 { 00057 namespace detail 00058 { 00059 #ifdef PB_DS_DATA_TRUE_INDICATOR 00060 #define PB_DS_GP_HASH_NAME gp_ht_map 00061 #endif 00062 00063 #ifdef PB_DS_DATA_FALSE_INDICATOR 00064 #define PB_DS_GP_HASH_NAME gp_ht_set 00065 #endif 00066 00067 #define PB_DS_CLASS_T_DEC \ 00068 template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \ 00069 typename _Alloc, bool Store_Hash, typename Comb_Probe_Fn, \ 00070 typename Probe_Fn, typename Resize_Policy> 00071 00072 #define PB_DS_CLASS_C_DEC \ 00073 PB_DS_GP_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ 00074 Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy> 00075 00076 #define PB_DS_HASH_EQ_FN_C_DEC \ 00077 hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> 00078 00079 #define PB_DS_RANGED_PROBE_FN_C_DEC \ 00080 ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, Store_Hash> 00081 00082 #define PB_DS_GP_HASH_TRAITS_BASE \ 00083 types_traits<Key, Mapped, _Alloc, Store_Hash> 00084 00085 #ifdef _GLIBCXX_DEBUG 00086 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 00087 debug_map_base<Key, Eq_Fn, \ 00088 typename _Alloc::template rebind<Key>::other::const_reference> 00089 #endif 00090 00091 00092 /** 00093 * A general-probing hash-based container. 00094 * 00095 * 00096 * @ingroup hash-detail 00097 * 00098 * @tparam Key Key type. 00099 * 00100 * @tparam Mapped Map type. 00101 * 00102 * @tparam Hash_Fn Hashing functor. 00103 * Default is __gnu_cxx::hash. 00104 * 00105 * @tparam Eq_Fn Equal functor. 00106 * Default std::equal_to<Key> 00107 * 00108 * @tparam _Alloc Allocator type. 00109 * 00110 * @tparam Store_Hash If key type stores extra metadata. 00111 * Defaults to false. 00112 * 00113 * @tparam Comb_Probe_Fn Combining probe functor. 00114 * If Hash_Fn is not null_type, then this 00115 * is the ranged-probe functor; otherwise, 00116 * this is the range-hashing functor. 00117 * XXX See Design::Hash-Based Containers::Hash Policies. 00118 * Default direct_mask_range_hashing. 00119 * 00120 * @tparam Probe_Fn Probe functor. 00121 * Defaults to linear_probe_fn, 00122 * also quadratic_probe_fn. 00123 * 00124 * @tparam Resize_Policy Resizes hash. 00125 * Defaults to hash_standard_resize_policy, 00126 * using hash_exponential_size_policy and 00127 * hash_load_check_resize_trigger. 00128 * 00129 * 00130 * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_probe_fn, 00131 * detail::types_traits. (Optional: detail::debug_map_base.) 00132 */ 00133 template<typename Key, 00134 typename Mapped, 00135 typename Hash_Fn, 00136 typename Eq_Fn, 00137 typename _Alloc, 00138 bool Store_Hash, 00139 typename Comb_Probe_Fn, 00140 typename Probe_Fn, 00141 typename Resize_Policy> 00142 class PB_DS_GP_HASH_NAME : 00143 #ifdef _GLIBCXX_DEBUG 00144 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 00145 #endif 00146 public PB_DS_HASH_EQ_FN_C_DEC, 00147 public Resize_Policy, 00148 public PB_DS_RANGED_PROBE_FN_C_DEC, 00149 public PB_DS_GP_HASH_TRAITS_BASE 00150 { 00151 private: 00152 typedef PB_DS_GP_HASH_TRAITS_BASE traits_base; 00153 typedef typename traits_base::value_type value_type_; 00154 typedef typename traits_base::pointer pointer_; 00155 typedef typename traits_base::const_pointer const_pointer_; 00156 typedef typename traits_base::reference reference_; 00157 typedef typename traits_base::const_reference const_reference_; 00158 typedef typename traits_base::comp_hash comp_hash; 00159 00160 enum entry_status 00161 { 00162 empty_entry_status, 00163 valid_entry_status, 00164 erased_entry_status 00165 } __attribute__ ((packed)); 00166 00167 struct entry : public traits_base::stored_data_type 00168 { 00169 entry_status m_stat; 00170 }; 00171 00172 typedef typename _Alloc::template rebind<entry>::other entry_allocator; 00173 typedef typename entry_allocator::pointer entry_pointer; 00174 typedef typename entry_allocator::const_pointer const_entry_pointer; 00175 typedef typename entry_allocator::reference entry_reference; 00176 typedef typename entry_allocator::const_reference const_entry_reference; 00177 typedef typename entry_allocator::pointer entry_array; 00178 00179 typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; 00180 00181 #ifdef _GLIBCXX_DEBUG 00182 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 00183 #endif 00184 00185 typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 00186 typedef Resize_Policy resize_base; 00187 00188 #define PB_DS_GEN_POS typename _Alloc::size_type 00189 00190 #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> 00191 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 00192 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 00193 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 00194 00195 #undef PB_DS_GEN_POS 00196 00197 public: 00198 typedef _Alloc allocator_type; 00199 typedef typename _Alloc::size_type size_type; 00200 typedef typename _Alloc::difference_type difference_type; 00201 typedef Hash_Fn hash_fn; 00202 typedef Eq_Fn eq_fn; 00203 typedef Probe_Fn probe_fn; 00204 typedef Comb_Probe_Fn comb_probe_fn; 00205 typedef Resize_Policy resize_policy; 00206 00207 /// Value stores hash, true or false. 00208 enum 00209 { 00210 store_hash = Store_Hash 00211 }; 00212 00213 typedef typename traits_base::key_type key_type; 00214 typedef typename traits_base::key_pointer key_pointer; 00215 typedef typename traits_base::key_const_pointer key_const_pointer; 00216 typedef typename traits_base::key_reference key_reference; 00217 typedef typename traits_base::key_const_reference key_const_reference; 00218 typedef typename traits_base::mapped_type mapped_type; 00219 typedef typename traits_base::mapped_pointer mapped_pointer; 00220 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 00221 typedef typename traits_base::mapped_reference mapped_reference; 00222 typedef typename traits_base::mapped_const_reference mapped_const_reference; 00223 typedef typename traits_base::value_type value_type; 00224 typedef typename traits_base::pointer pointer; 00225 typedef typename traits_base::const_pointer const_pointer; 00226 typedef typename traits_base::reference reference; 00227 typedef typename traits_base::const_reference const_reference; 00228 00229 #ifdef PB_DS_DATA_TRUE_INDICATOR 00230 typedef point_iterator_ point_iterator; 00231 #endif 00232 00233 #ifdef PB_DS_DATA_FALSE_INDICATOR 00234 typedef point_const_iterator_ point_iterator; 00235 #endif 00236 00237 typedef point_const_iterator_ point_const_iterator; 00238 00239 #ifdef PB_DS_DATA_TRUE_INDICATOR 00240 typedef iterator_ iterator; 00241 #endif 00242 00243 #ifdef PB_DS_DATA_FALSE_INDICATOR 00244 typedef const_iterator_ iterator; 00245 #endif 00246 00247 typedef const_iterator_ const_iterator; 00248 00249 PB_DS_GP_HASH_NAME(); 00250 00251 PB_DS_GP_HASH_NAME(const PB_DS_CLASS_C_DEC&); 00252 00253 PB_DS_GP_HASH_NAME(const Hash_Fn&); 00254 00255 PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&); 00256 00257 PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); 00258 00259 PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 00260 const Probe_Fn&); 00261 00262 PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 00263 const Probe_Fn&, const Resize_Policy&); 00264 00265 template<typename It> 00266 void 00267 copy_from_range(It, It); 00268 00269 virtual 00270 ~PB_DS_GP_HASH_NAME(); 00271 00272 void 00273 swap(PB_DS_CLASS_C_DEC&); 00274 00275 inline size_type 00276 size() const; 00277 00278 inline size_type 00279 max_size() const; 00280 00281 /// True if size() == 0. 00282 inline bool 00283 empty() const; 00284 00285 /// Return current hash_fn. 00286 Hash_Fn& 00287 get_hash_fn(); 00288 00289 /// Return current const hash_fn. 00290 const Hash_Fn& 00291 get_hash_fn() const; 00292 00293 /// Return current eq_fn. 00294 Eq_Fn& 00295 get_eq_fn(); 00296 00297 /// Return current const eq_fn. 00298 const Eq_Fn& 00299 get_eq_fn() const; 00300 00301 /// Return current probe_fn. 00302 Probe_Fn& 00303 get_probe_fn(); 00304 00305 /// Return current const probe_fn. 00306 const Probe_Fn& 00307 get_probe_fn() const; 00308 00309 /// Return current comb_probe_fn. 00310 Comb_Probe_Fn& 00311 get_comb_probe_fn(); 00312 00313 /// Return current const comb_probe_fn. 00314 const Comb_Probe_Fn& 00315 get_comb_probe_fn() const; 00316 00317 /// Return current resize_policy. 00318 Resize_Policy& 00319 get_resize_policy(); 00320 00321 /// Return current const resize_policy. 00322 const Resize_Policy& 00323 get_resize_policy() const; 00324 00325 inline std::pair<point_iterator, bool> 00326 insert(const_reference r_val) 00327 { 00328 _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid(__FILE__, __LINE__);) 00329 return insert_imp(r_val, traits_base::m_store_extra_indicator); 00330 } 00331 00332 inline mapped_reference 00333 operator[](key_const_reference r_key) 00334 { 00335 #ifdef PB_DS_DATA_TRUE_INDICATOR 00336 return subscript_imp(r_key, traits_base::m_store_extra_indicator); 00337 #else 00338 insert(r_key); 00339 return traits_base::s_null_type; 00340 #endif 00341 } 00342 00343 inline point_iterator 00344 find(key_const_reference); 00345 00346 inline point_const_iterator 00347 find(key_const_reference) const; 00348 00349 inline point_iterator 00350 find_end(); 00351 00352 inline point_const_iterator 00353 find_end() const; 00354 00355 inline bool 00356 erase(key_const_reference); 00357 00358 template<typename Pred> 00359 inline size_type 00360 erase_if(Pred); 00361 00362 void 00363 clear(); 00364 00365 inline iterator 00366 begin(); 00367 00368 inline const_iterator 00369 begin() const; 00370 00371 inline iterator 00372 end(); 00373 00374 inline const_iterator 00375 end() const; 00376 00377 #ifdef _GLIBCXX_DEBUG 00378 void 00379 assert_valid(const char*, int) const; 00380 #endif 00381 00382 #ifdef PB_DS_HT_MAP_TRACE_ 00383 void 00384 trace() const; 00385 #endif 00386 00387 private: 00388 #ifdef PB_DS_DATA_TRUE_INDICATOR 00389 friend class iterator_; 00390 #endif 00391 00392 friend class const_iterator_; 00393 00394 void 00395 deallocate_all(); 00396 00397 void 00398 initialize(); 00399 00400 void 00401 erase_all_valid_entries(entry_array, size_type); 00402 00403 inline bool 00404 do_resize_if_needed(); 00405 00406 inline void 00407 do_resize_if_needed_no_throw(); 00408 00409 void 00410 resize_imp(size_type); 00411 00412 virtual void 00413 do_resize(size_type); 00414 00415 void 00416 resize_imp(entry_array, size_type); 00417 00418 inline void 00419 resize_imp_reassign(entry_pointer, entry_array, false_type); 00420 00421 inline void 00422 resize_imp_reassign(entry_pointer, entry_array, true_type); 00423 00424 inline size_type 00425 find_ins_pos(key_const_reference, false_type); 00426 00427 inline comp_hash 00428 find_ins_pos(key_const_reference, true_type); 00429 00430 inline std::pair<point_iterator, bool> 00431 insert_imp(const_reference, false_type); 00432 00433 inline std::pair<point_iterator, bool> 00434 insert_imp(const_reference, true_type); 00435 00436 inline pointer 00437 insert_new_imp(const_reference r_val, size_type pos) 00438 { 00439 _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 00440 00441 if (do_resize_if_needed()) 00442 pos = find_ins_pos(PB_DS_V2F(r_val), 00443 traits_base::m_store_extra_indicator); 00444 00445 _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 00446 entry* const p_e = m_entries + pos; 00447 new (&p_e->m_value) value_type(r_val); 00448 p_e->m_stat = valid_entry_status; 00449 resize_base::notify_inserted(++m_num_used_e); 00450 00451 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 00452 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 00453 return &p_e->m_value; 00454 } 00455 00456 inline pointer 00457 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 00458 { 00459 _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 00460 valid_entry_status); 00461 00462 if (do_resize_if_needed()) 00463 r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), 00464 traits_base::m_store_extra_indicator); 00465 00466 _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 00467 valid_entry_status); 00468 00469 entry* const p_e = m_entries + r_pos_hash_pair.first; 00470 new (&p_e->m_value) value_type(r_val); 00471 p_e->m_hash = r_pos_hash_pair.second; 00472 p_e->m_stat = valid_entry_status; 00473 00474 resize_base::notify_inserted(++m_num_used_e); 00475 00476 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 00477 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 00478 return &p_e->m_value; 00479 } 00480 00481 #ifdef PB_DS_DATA_TRUE_INDICATOR 00482 inline mapped_reference 00483 subscript_imp(key_const_reference key, false_type) 00484 { 00485 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 00486 00487 const size_type pos = find_ins_pos(key, 00488 traits_base::m_store_extra_indicator); 00489 00490 entry_pointer p_e = &m_entries[pos]; 00491 if (p_e->m_stat != valid_entry_status) 00492 return insert_new_imp(value_type(key, mapped_type()), pos)->second; 00493 00494 PB_DS_CHECK_KEY_EXISTS(key) 00495 return p_e->m_value.second; 00496 } 00497 00498 inline mapped_reference 00499 subscript_imp(key_const_reference key, true_type) 00500 { 00501 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 00502 00503 comp_hash pos_hash_pair = find_ins_pos(key, 00504 traits_base::m_store_extra_indicator); 00505 00506 if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) 00507 return insert_new_imp(value_type(key, mapped_type()), 00508 pos_hash_pair)->second; 00509 00510 PB_DS_CHECK_KEY_EXISTS(key) 00511 return (m_entries + pos_hash_pair.first)->m_value.second; 00512 } 00513 #endif 00514 00515 inline pointer 00516 find_key_pointer(key_const_reference key, false_type) 00517 { 00518 const size_type hash = ranged_probe_fn_base::operator()(key); 00519 resize_base::notify_find_search_start(); 00520 00521 // Loop until entry is found or until all possible entries accessed. 00522 for (size_type i = 0; i < m_num_e; ++i) 00523 { 00524 const size_type pos = ranged_probe_fn_base::operator()(key, 00525 hash, i); 00526 00527 entry* const p_e = m_entries + pos; 00528 switch (p_e->m_stat) 00529 { 00530 case empty_entry_status: 00531 { 00532 resize_base::notify_find_search_end(); 00533 PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 00534 return 0; 00535 } 00536 break; 00537 case valid_entry_status: 00538 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) 00539 { 00540 resize_base::notify_find_search_end(); 00541 PB_DS_CHECK_KEY_EXISTS(key) 00542 return pointer(&p_e->m_value); 00543 } 00544 break; 00545 case erased_entry_status: 00546 break; 00547 default: 00548 _GLIBCXX_DEBUG_ASSERT(0); 00549 }; 00550 00551 resize_base::notify_find_search_collision(); 00552 } 00553 00554 PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 00555 resize_base::notify_find_search_end(); 00556 return 0; 00557 } 00558 00559 inline pointer 00560 find_key_pointer(key_const_reference key, true_type) 00561 { 00562 comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); 00563 resize_base::notify_find_search_start(); 00564 00565 // Loop until entry is found or until all possible entries accessed. 00566 for (size_type i = 0; i < m_num_e; ++i) 00567 { 00568 const size_type pos = 00569 ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); 00570 00571 entry* const p_e = m_entries + pos; 00572 00573 switch(p_e->m_stat) 00574 { 00575 case empty_entry_status: 00576 { 00577 resize_base::notify_find_search_end(); 00578 PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 00579 return 0; 00580 } 00581 break; 00582 case valid_entry_status: 00583 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 00584 p_e->m_hash, 00585 key, pos_hash_pair.second)) 00586 { 00587 resize_base::notify_find_search_end(); 00588 PB_DS_CHECK_KEY_EXISTS(key) 00589 return pointer(&p_e->m_value); 00590 } 00591 break; 00592 case erased_entry_status: 00593 break; 00594 default: 00595 _GLIBCXX_DEBUG_ASSERT(0); 00596 }; 00597 00598 resize_base::notify_find_search_collision(); 00599 } 00600 00601 PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 00602 resize_base::notify_find_search_end(); 00603 return 0; 00604 } 00605 00606 inline bool 00607 erase_imp(key_const_reference, true_type); 00608 00609 inline bool 00610 erase_imp(key_const_reference, false_type); 00611 00612 inline void 00613 erase_entry(entry_pointer); 00614 00615 #ifdef PB_DS_DATA_TRUE_INDICATOR 00616 void 00617 inc_it_state(pointer& r_p_value, size_type& r_pos) const 00618 { inc_it_state((mapped_const_pointer& )r_p_value, r_pos); } 00619 #endif 00620 00621 void 00622 inc_it_state(const_pointer& r_p_value, size_type& r_pos) const 00623 { 00624 _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); 00625 for (++r_pos; r_pos < m_num_e; ++r_pos) 00626 { 00627 const_entry_pointer p_e =& m_entries[r_pos]; 00628 if (p_e->m_stat == valid_entry_status) 00629 { 00630 r_p_value =& p_e->m_value; 00631 return; 00632 } 00633 } 00634 r_p_value = 0; 00635 } 00636 00637 void 00638 get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const 00639 { 00640 for (r_pos = 0; r_pos < m_num_e; ++r_pos) 00641 { 00642 const_entry_pointer p_e = &m_entries[r_pos]; 00643 if (p_e->m_stat == valid_entry_status) 00644 { 00645 r_p_value = &p_e->m_value; 00646 return; 00647 } 00648 } 00649 r_p_value = 0; 00650 } 00651 00652 void 00653 get_start_it_state(pointer& r_p_value, size_type& r_pos) 00654 { 00655 for (r_pos = 0; r_pos < m_num_e; ++r_pos) 00656 { 00657 entry_pointer p_e = &m_entries[r_pos]; 00658 if (p_e->m_stat == valid_entry_status) 00659 { 00660 r_p_value = &p_e->m_value; 00661 return; 00662 } 00663 } 00664 r_p_value = 0; 00665 } 00666 00667 #ifdef _GLIBCXX_DEBUG 00668 void 00669 assert_entry_array_valid(const entry_array, false_type, 00670 const char*, int) const; 00671 00672 void 00673 assert_entry_array_valid(const entry_array, true_type, 00674 const char*, int) const; 00675 #endif 00676 00677 static entry_allocator s_entry_allocator; 00678 static iterator s_end_it; 00679 static const_iterator s_const_end_it; 00680 00681 size_type m_num_e; 00682 size_type m_num_used_e; 00683 entry_pointer m_entries; 00684 00685 enum 00686 { 00687 store_hash_ok = !Store_Hash 00688 || !is_same<Hash_Fn, __gnu_pbds::null_type>::value 00689 }; 00690 00691 PB_DS_STATIC_ASSERT(sth, store_hash_ok); 00692 }; 00693 00694 #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp> 00695 #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp> 00696 #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp> 00697 #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp> 00698 #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp> 00699 #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp> 00700 #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp> 00701 #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp> 00702 #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp> 00703 #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp> 00704 00705 #undef PB_DS_CLASS_T_DEC 00706 #undef PB_DS_CLASS_C_DEC 00707 #undef PB_DS_HASH_EQ_FN_C_DEC 00708 #undef PB_DS_RANGED_PROBE_FN_C_DEC 00709 #undef PB_DS_GP_HASH_TRAITS_BASE 00710 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 00711 #undef PB_DS_GP_HASH_NAME 00712 } // namespace detail 00713 } // namespace __gnu_pbds