GNU C++ STL: gp_ht_map_.hpp Source File

00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005 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
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00031 
00032 // Permission to use, copy, modify, sell, and distribute this software
00033 // is hereby granted without fee, provided that the above copyright
00034 // notice appears in all copies, and that both that copyright notice and
00035 // this permission notice appear in supporting documentation. None of
00036 // the above authors, nor IBM Haifa Research Laboratories, make any
00037 // representation about the suitability of this software for any
00038 // purpose. It is provided "as is" without express or implied warranty.
00039 
00045 #include <ext/pb_assoc/detail/cond_dealtor.hpp>
00046 #include <ext/pb_assoc/trivial_iterator_def.hpp>
00047 #include <ext/pb_assoc/detail/hash_fn/ranged_probe_fn.hpp>
00048 #include <ext/pb_assoc/detail/hash_types_traits.hpp>
00049 #include <ext/pb_assoc/detail/types_traits.hpp>
00050 #include <ext/pb_assoc/exception.hpp>
00051 #include <ext/pb_assoc/detail/map_debug_base.hpp>
00052 #include <ext/pb_assoc/detail/eq_fn/hash_eq_fn.hpp>
00053 #ifdef PB_ASSOC_BASIC_REGRESSION
00054 #include <pb_assoc/testsuite/regression/basic_test/throw_prob_adjustor.hpp>
00055 #endif // #ifdef PB_ASSOC_BASIC_REGRESSION
00056 #include <utility>
00057 
00058 namespace pb_assoc
00059 {
00060 
00061   namespace detail
00062   {
00063 
00064 #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00065 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00066 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00067 #define PB_ASSOC_DBG_ONLY(X) X
00068 #else // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00069 #define PB_ASSOC_DBG_ASSERT(X)
00070 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00071 #define PB_ASSOC_DBG_ONLY(X) ;
00072 #endif // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00073 
00074 #define PB_ASSOC_CLASS_T_DEC \
00075     template< \
00076         typename Key, \
00077         typename Data, \
00078         class Hash_Fn, \
00079         class Eq_Fn, \
00080         class Allocator, \
00081         bool Store_Hash, \
00082         class Comb_Probe_Fn, \
00083         class Probe_Fn, \
00084         class Resize_Policy>
00085 
00086 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00087 #define PB_ASSOC_CLASS_NAME \
00088     gp_ht_map_data_
00089 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00090 
00091 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00092 #define PB_ASSOC_CLASS_NAME \
00093     gp_ht_map_no_data_
00094 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00095 
00096 #define PB_ASSOC_CLASS_C_DEC \
00097     PB_ASSOC_CLASS_NAME< \
00098         Key, \
00099         Data, \
00100         Hash_Fn, \
00101         Eq_Fn, \
00102         Allocator, \
00103         Store_Hash, \
00104         Comb_Probe_Fn, \
00105         Probe_Fn, \
00106         Resize_Policy>
00107 
00108 #define PB_ASSOC_HASH_EQ_FN_C_DEC \
00109     pb_assoc::detail::hash_eq_fn< \
00110         Key, \
00111         Eq_Fn, \
00112         Allocator, \
00113         Store_Hash>
00114 
00115 #define PB_ASSOC_RANGED_PROBE_FN_C_DEC \
00116     pb_assoc::detail::ranged_probe_fn< \
00117         Key, \
00118         Hash_Fn, \
00119         Allocator, \
00120         Comb_Probe_Fn, \
00121         Probe_Fn, \
00122         Store_Hash>
00123 
00124 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00125     types_traits< \
00126         Key, \
00127         Data, \
00128         Allocator>
00129 
00130 #define PB_ASSOC_HASH_TYPES_TRAITS_C_DEC \
00131     hash_types_traits< \
00132         typename Allocator::size_type, \
00133         Store_Hash>
00134 
00135 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00136 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
00137     pb_assoc::detail::map_debug_base< \
00138         Key, \
00139         Eq_Fn>
00140 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00141 
00142 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00143 #define PB_ASSOC_V2F(X) (X).first
00144 #define PB_ASSOC_V2S(X) (X).second
00145 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00146 
00147 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00148 #define PB_ASSOC_V2F(X) (X)
00149 #define PB_ASSOC_V2S(X) Mapped_Data()
00150 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00151 
00152 #define PB_ASSOC_STATIC_ASSERT(UNIQUE, E) \
00153     typedef \
00154         pb_assoc::detail::static_assert_dummy_class< \
00155             sizeof(pb_assoc::detail::static_assert<(bool)(E)>)> \
00156             UNIQUE##static_assert_type
00157 
00158     template<typename Key,
00159          typename Data,
00160          class Hash_Fn,
00161          class Eq_Fn,
00162          class Allocator,
00163          bool Store_Hash,
00164          class Comb_Probe_Fn,
00165          class Probe_Fn,
00166          class Resize_Policy>
00167     class PB_ASSOC_CLASS_NAME :
00168 #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00169       protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
00170 #endif // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00171       public PB_ASSOC_HASH_EQ_FN_C_DEC,
00172       public Resize_Policy,
00173       public PB_ASSOC_RANGED_PROBE_FN_C_DEC,
00174       public PB_ASSOC_TYPES_TRAITS_C_DEC,
00175       public PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
00176     {
00177 
00178     public:
00179 
00180       typedef typename Allocator::size_type size_type;
00181 
00182       typedef
00183       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00184       const_key_reference;
00185 
00186       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00187 
00188       typedef
00189       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00190       data_reference;
00191 
00192       typedef
00193       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00194       const_data_reference;
00195 
00196       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00197 
00198       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00199 
00200       typedef
00201       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00202       const_pointer;
00203 
00204       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00205 
00206       typedef
00207       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00208       const_reference;
00209 
00210     protected:
00211 
00212       typedef typename PB_ASSOC_HASH_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
00213 
00214       enum ENTRY_STATUS
00215     {
00216       EMPTY_ENTRY_STATUS,
00217       VALID_ENTRY_STATUS,
00218       ERASED_ENTRY_STATUS
00219     };
00220 
00221       typedef char entry_status;
00222 
00223       struct store_hash_entry
00224       {
00225     value_type m_value;
00226 
00227     entry_status m_stat;
00228 
00229     size_type m_hash;
00230       };
00231 
00232       struct no_store_hash_entry
00233       {
00234     value_type m_value;
00235 
00236     entry_status m_stat;
00237       };
00238 
00239       typedef
00240       typename cond_type<
00241     Store_Hash,
00242     store_hash_entry,
00243     no_store_hash_entry>::type
00244       entry;
00245 
00246       typedef
00247       typename Allocator::template rebind<entry>::other
00248       entry_allocator;
00249 
00250       typedef typename entry_allocator::pointer entry_pointer;
00251 
00252       typedef typename entry_allocator::const_pointer const_entry_pointer;
00253 
00254       typedef typename entry_allocator::reference entry_reference;
00255 
00256       typedef
00257       typename entry_allocator::const_reference
00258       const_entry_reference;
00259 
00260       typedef typename entry_allocator::pointer entry_array;
00261 
00262       typedef value_type mapped_value_type;
00263 
00264       typedef pointer mapped_pointer;
00265 
00266       typedef const_pointer const_mapped_pointer;
00267 
00268       typedef reference mapped_reference;
00269 
00270       typedef const_reference const_mapped_reference;
00271 
00272 #define PB_ASSOC_GEN_POS size_type
00273 
00274 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
00275 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
00276 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
00277 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
00278 
00279 #undef PB_ASSOC_GEN_POS
00280 
00281       typedef find_iterator_ find_iterator;
00282 
00283       typedef const_find_iterator_ const_find_iterator;
00284 
00285       typedef iterator_ iterator;
00286 
00287       typedef const_iterator_ const_iterator;
00288 
00289       typedef Hash_Fn hash_fn;
00290 
00291       typedef Eq_Fn eq_fn;
00292 
00293       typedef Allocator allocator;
00294 
00295       typedef Probe_Fn probe_fn;
00296 
00297       typedef Comb_Probe_Fn comb_hash_fn;
00298 
00299       typedef Resize_Policy resize_policy;
00300 
00301     protected:
00302 
00303       PB_ASSOC_CLASS_NAME();
00304 
00305       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00306 
00307       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn);
00308 
00309       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
00310 
00311       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn);
00312 
00313       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
00314 
00315       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy);
00316 
00317       template<class It>
00318       void
00319       copy_from_range(It first_it, It last_it);
00320 
00321       virtual
00322       ~PB_ASSOC_CLASS_NAME();
00323 
00324       void
00325       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00326 
00327       inline size_type
00328       size() const;
00329 
00330       inline size_type
00331       max_size() const;
00332 
00333       inline bool
00334       empty() const;
00335 
00336       Hash_Fn& 
00337       get_hash_fn();
00338 
00339       const Hash_Fn& 
00340       get_hash_fn() const;
00341 
00342       Eq_Fn& 
00343       get_eq_fn();
00344 
00345       const Eq_Fn& 
00346       get_eq_fn() const;
00347 
00348       Probe_Fn& 
00349       get_probe_fn();
00350 
00351       const Probe_Fn& 
00352       get_probe_fn() const;
00353 
00354       Comb_Probe_Fn& 
00355       get_comb_probe_fn();
00356 
00357       const Comb_Probe_Fn& 
00358       get_comb_probe_fn() const;
00359 
00360       Resize_Policy& 
00361       get_resize_policy();
00362 
00363       const Resize_Policy& 
00364       get_resize_policy() const;
00365 
00366       inline std::pair<find_iterator, bool>
00367       insert(const_reference r_val);
00368 
00369       inline data_reference
00370       subscript_imp(const_key_reference r_key);
00371 
00372       inline find_iterator
00373       find(const_key_reference r_key);
00374 
00375       inline const_find_iterator
00376       find(const_key_reference r_key) const;
00377 
00378       inline find_iterator
00379       find_end();
00380 
00381       inline const_find_iterator
00382       find_end() const;
00383 
00384       inline size_type
00385       erase(const_key_reference r_key, int_to_type<false>);
00386 
00387       inline size_type
00388       erase(const_key_reference r_key, int_to_type<true>);
00389 
00390       template<class Pred>
00391       inline size_type
00392       erase_if(Pred prd);
00393 
00394       void
00395       clear();
00396 
00397       inline iterator
00398       begin();
00399 
00400       inline const_iterator
00401       begin() const;
00402 
00403       inline iterator
00404       end();
00405 
00406       inline const_iterator
00407       end() const;
00408 
00409 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00410 
00411       virtual void
00412       assert_valid() const;
00413 
00414 #endif // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00415 
00416       virtual void
00417       do_resize(size_type new_size);
00418 
00419     private:
00420 
00421       typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
00422 
00423       typedef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC my_hash_traits_base;
00424 
00425       typedef PB_ASSOC_RANGED_PROBE_FN_C_DEC my_ranged_probe_fn_base;
00426 
00427 #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00428       typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
00429 #endif // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00430 
00431       typedef PB_ASSOC_HASH_EQ_FN_C_DEC my_hash_eq_fn_base;
00432 
00433       typedef Resize_Policy my_resize_base;
00434 
00435       friend class iterator_;
00436 
00437       friend class const_iterator_;
00438 
00439     private:
00440 
00441       void
00442       deallocate_all();
00443 
00444       void
00445       initialize();
00446 
00447       inline void
00448       constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<true>);
00449 
00450       inline void
00451       constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<false>);
00452 
00453       void
00454       erase_all_valid_entries(entry_array a_entries_resized, size_type size);
00455 
00456       inline bool
00457       do_resize_if_needed();
00458 
00459       inline void
00460       do_resize_if_needed_no_throw();
00461 
00462       void
00463       resize_imp(entry_array a_entries_resized, size_type old_size);
00464 
00465       inline void
00466       resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, int_to_type<false>);
00467 
00468       inline void
00469       resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, int_to_type<true>);
00470 
00471       inline size_type
00472       find_ins_pos(const_key_reference r_key, int_to_type<false>);
00473 
00474       inline comp_hash
00475       find_ins_pos(const_key_reference r_key, int_to_type<true>);
00476 
00477       inline std::pair<find_iterator, bool>
00478       insert_imp(const_reference r_val, int_to_type<false>);
00479 
00480       inline std::pair<find_iterator, bool>
00481       insert_imp(const_reference r_val, int_to_type<true>);
00482 
00483       inline pointer
00484       insert_new_imp(const_reference r_val, size_type pos);
00485 
00486       inline pointer
00487       insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair);
00488 
00489       inline data_reference
00490       subscript_imp(const_key_reference r_key, int_to_type<false>);
00491 
00492       inline data_reference
00493       subscript_imp(const_key_reference r_key, int_to_type<true>);
00494 
00495       inline const_data_reference
00496       const_subscript_imp(const_key_reference r_key) const;
00497 
00498       inline pointer
00499       find_key_pointer(const_key_reference r_key, int_to_type<false>);
00500 
00501       inline pointer
00502       find_key_pointer(const_key_reference r_key, int_to_type<true>);
00503 
00504       inline const_data_reference
00505       const_subscript_imp(const_key_reference r_key, int_to_type<false>) const;
00506 
00507       inline const_data_reference
00508       const_subscript_imp(const_key_reference r_key, int_to_type<true>) const;
00509 
00510       inline size_type
00511       erase_in_pos_imp(const_key_reference r_key, const comp_hash& r_pos_hash_pair);
00512 
00513       inline void
00514       erase_entry(entry_pointer p_e);
00515 
00516 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00517       void
00518       inc_it_state(pointer& r_p_value, size_type& r_pos) const;
00519 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00520 
00521       void
00522       inc_it_state(const_pointer& r_p_value, size_type& r_pos) const;
00523 
00524       void
00525       get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const;
00526 
00527       void
00528       get_start_it_state(pointer& r_p_value, size_type& r_pos);
00529 
00530 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
00531 
00532       void
00533       assert_entry_array_valid(const entry_array a_entries, int_to_type<false>) const;
00534 
00535       void
00536       assert_entry_array_valid(const entry_array a_entries, int_to_type<true>) const;
00537 
00538 #endif // #ifdef PB_ASSOC_GP_HT_MAP_DEBUG_
00539 
00540     private:
00541       static entry_allocator s_entry_allocator;
00542 
00543       entry_pointer m_a_entries;
00544 
00545       size_type m_num_e;
00546 
00547       size_type m_num_used_e;
00548 
00549       static iterator s_end_it;
00550 
00551       static const_iterator s_const_end_it;
00552 
00553       enum
00554     {
00555       store_hash_ok =
00556       !Store_Hash ||
00557       !pb_assoc::detail::is_same_type<
00558       Hash_Fn,
00559       pb_assoc::null_hash_fn>::value
00560     };
00561 
00562       PB_ASSOC_STATIC_ASSERT(sth, store_hash_ok);
00563     };
00564 
00565 #include <ext/pb_assoc/detail/gp_ht_map_/constructor_destructor_fn_imps.hpp>
00566 #include <ext/pb_assoc/detail/gp_ht_map_/find_fn_imps.hpp>
00567 #include <ext/pb_assoc/detail/gp_ht_map_/resize_fn_imps.hpp>
00568 #include <ext/pb_assoc/detail/gp_ht_map_/debug_fn_imps.hpp>
00569 #include <ext/pb_assoc/detail/gp_ht_map_/info_fn_imps.hpp>
00570 #include <ext/pb_assoc/detail/gp_ht_map_/policy_access_fn_imps.hpp>
00571 #include <ext/pb_assoc/detail/gp_ht_map_/erase_fn_imps.hpp>
00572 #include <ext/pb_assoc/detail/gp_ht_map_/iterator_fn_imps.hpp>
00573 #include <ext/pb_assoc/detail/gp_ht_map_/insert_fn_imps.hpp>
00574 
00575 #undef PB_ASSOC_CLASS_T_DEC
00576 
00577 #undef PB_ASSOC_CLASS_C_DEC
00578 
00579 #undef PB_ASSOC_HASH_EQ_FN_C_DEC
00580 
00581 #undef PB_ASSOC_RANGED_PROBE_FN_C_DEC
00582 
00583 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00584 
00585 #undef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
00586 
00587 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
00588 
00589 #undef PB_ASSOC_CLASS_NAME
00590 
00591 #undef PB_ASSOC_V2F
00592 #undef PB_ASSOC_V2S
00593 
00594 #undef PB_ASSOC_DBG_ASSERT
00595 #undef PB_ASSOC_DBG_VERIFY
00596 #undef PB_ASSOC_DBG_ONLY
00597 
00598 #undef PB_ASSOC_STATIC_ASSERT
00599 
00600   } // namespace detail
00601 
00602 } // namespace pb_assoc