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