nst_reference const_mapped_reference; typedef typename Allocator::template rebind >::other value_type_allocator; typedef typename value_type_allocator::value_type value_type; typedef typename value_type_allocator::pointer pointer; typedef typename value_type_allocator::const_pointer const_pointer; typedef typename value_type_allocator::reference reference; typedef typename value_type_allocator::const_reference const_reference; struct stored_value_type { value_type m_value; }; }; /** * Specialization of value_type_base for the case where the hash value * is stored alongside each value. **/ template struct value_type_base { typedef typename Allocator::template rebind::other mapped_type_allocator; typedef typename mapped_type_allocator::value_type mapped_type; typedef typename mapped_type_allocator::pointer mapped_pointer; typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; typedef typename mapped_type_allocator::reference mapped_reference; typedef typename mapped_type_allocator::const_reference const_mapped_reference; typedef typename Allocator::template rebind >::other value_type_allocator; typedef typename value_type_allocator::value_type value_type; typedef typename value_type_allocator::pointer pointer; typedef typename value_type_allocator::const_pointer const_pointer; typedef typename value_type_allocator::reference reference; typedef typename value_type_allocator::const_reference const_reference; struct stored_value_type { value_type m_value; typename Allocator::size_type m_hash; }; }; #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ value_type_base /** * Specialization of value_type_base for the case where the hash value * is not stored alongside each value. **/ template struct value_type_base { typedef typename Allocator::template rebind::other mapped_type_allocator; typedef typename mapped_type_allocator::value_type mapped_type; typedef typename mapped_type_allocator::pointer mapped_pointer; typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; typedef typename mapped_type_allocator::reference mapped_reference; typedef typename mapped_type_allocator::const_reference const_mapped_reference; typedef Key value_type; typedef typename Allocator::template rebind::other value_type_allocator; typedef typename value_type_allocator::pointer pointer; typedef typename value_type_allocator::const_pointer const_pointer; typedef typename value_type_allocator::reference reference; typedef typename value_type_allocator::const_reference const_reference; struct stored_value_type { value_type m_value; }; static null_mapped_type s_null_mapped; }; PB_DS_CLASS_T_DEC null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ value_type_base /** * Specialization of value_type_base for the case where the hash value * is stored alongside each value. **/ template struct value_type_base { typedef typename Allocator::template rebind::other mapped_type_allocator; typedef typename mapped_type_allocator::value_type mapped_type; typedef typename mapped_type_allocator::pointer mapped_pointer; typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; typedef typename mapped_type_allocator::reference mapped_reference; typedef typename mapped_type_allocator::const_reference const_mapped_reference; typedef Key value_type; typedef typename Allocator::template rebind::other value_type_allocator; typedef typename value_type_allocator::pointer pointer; typedef typename value_type_allocator::const_pointer const_pointer; typedef typename value_type_allocator::reference reference; typedef typename value_type_allocator::const_reference const_reference; struct stored_value_type { value_type m_value; typename Allocator::size_type m_hash; }; static null_mapped_type s_null_mapped; }; PB_DS_CLASS_T_DEC null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC template struct no_throw_copies { typedef integral_constant::value && is_simple::value> indicator; }; template struct no_throw_copies { typedef integral_constant::value> indicator; }; } // namespace detail } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file type_utils.hpp * Contains utilities for handnling types. All of these classes are based on * "Modern C++" by Andrei Alxandrescu. */ #ifndef PB_DS_TYPE_UTILS_HPP #define PB_DS_TYPE_UTILS_HPP #include #include #include #include #include namespace __gnu_pbds { namespace detail { using std::tr1::is_same; using std::tr1::is_const; using std::tr1::is_pointer; using std::tr1::is_reference; using std::tr1::is_fundamental; using std::tr1::is_member_object_pointer; using std::tr1::is_member_pointer; using std::tr1::is_base_of; using std::tr1::remove_const; using std::tr1::remove_reference; // Need integral_const <-> integral_const, so // because of this use the following typedefs instead of importing // std::tr1's. using std::tr1::integral_constant; typedef std::tr1::integral_constant true_type; typedef std::tr1::integral_constant false_type; using __gnu_cxx::__conditional_type; using __gnu_cxx::__numeric_traits; template struct is_const_pointer { enum { value = is_const::value && is_pointer::value }; }; template struct is_const_reference { enum { value = is_const::value && is_reference::value }; }; template struct is_simple { enum { value = is_fundamental::type>::value || is_pointer::type>::value || is_member_pointer::value }; }; template class is_pair { private: template struct is_pair_imp { enum { value = 0 }; }; template struct is_pair_imp > { enum { value = 1 }; }; public: enum { value = is_pair_imp::value }; }; // Use C++0x's static_assert if possible. #ifdef __GXX_EXPERIMENTAL_CXX0X__ #define PB_DS_STATIC_ASSERT(UNIQUE, E) static_assert(E, #UNIQUE) #else template struct __static_assert; template<> struct __static_assert { }; template struct __static_assert_dumclass { enum { v = 1 }; }; #define PB_DS_STATIC_ASSERT(UNIQUE, E) \ typedef __gnu_pbds::detail::__static_assert_dumclass)> UNIQUE##__static_assert_type #endif template struct type_to_type { typedef Type type; }; } // namespace detail } // namespace __gnu_pbds #endif [ .X ..\(debug_no_store_hash_fn_imps.hpp]gp_ht_map_.hpp^80constructor_destructor_no_store_hash_fn_imps.hpp_(insert_store_hash_fn_imps.hpp`resize_fn_imps.hppainsert_fn_imps.hppb$debug_store_hash_fn_imps.hppc( insert_no_store_hash_fn_imps.hppdinfo_fn_imps.hppetrace_fn_imps.hppf$policy_access_fn_imps.hppg$find_store_hash_fn_imps.hpph( resize_no_store_hash_fn_imps.hppifind_fn_imps.hppj8-constructor_destructor_store_hash_fn_imps.hppkdebug_fn_imps.hpplerase_fn_imps.hppmiterator_fn_imps.hppn standard_policies.hppo(erase_no_store_hash_fn_imps.hppp(find_no_store_hash_fn_imps.hppq$erase_store_hash_fn_imps.hppr(resize_store_hash_fn_imps.hppsÀ"constructor_destructor_fn_imps.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_no_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s debug-mode functions. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_entry_array_valid(const entry_array a_entries, false_type) const { size_type iterated_num_used_e = 0; for (size_type pos = 0; pos < m_num_e; ++pos) { const_entry_pointer p_e = &a_entries[pos]; switch(p_e->m_stat) { case empty_entry_status: case erased_entry_status: break; case valid_entry_status: { const_key_reference r_key = PB_DS_V2F(p_e->m_value); debug_base::check_key_exists(r_key); ++iterated_num_used_e; break; } default: _GLIBCXX_DEBUG_ASSERT(0); }; } _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file gp_ht_map_.hpp * Contains an implementation class for gp_ht_map_. */ #include #include #include #include #include #include #ifdef PB_DS_HT_MAP_TRACE_ #include #endif #ifdef _GLIBCXX_DEBUG #include #endif #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME gp_ht_map_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME gp_ht_map_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_CLASS_NAME #define PB_DS_HASH_EQ_FN_C_DEC \ hash_eq_fn #define PB_DS_RANGED_PROBE_FN_C_DEC \ ranged_probe_fn #define PB_DS_TYPES_TRAITS_C_DEC \ types_traits #ifdef _GLIBCXX_DEBUG #define PB_DS_DEBUG_MAP_BASE_C_DEC \ debug_map_base::other::const_reference> #endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first #define PB_DS_V2S(X) (X).second #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_V2F(X) (X) #define PB_DS_V2S(X) Mapped() #endif template class PB_DS_CLASS_NAME : #ifdef _GLIBCXX_DEBUG protected PB_DS_DEBUG_MAP_BASE_C_DEC, #endif public PB_DS_HASH_EQ_FN_C_DEC, public Resize_Policy, public PB_DS_RANGED_PROBE_FN_C_DEC, public PB_DS_TYPES_TRAITS_C_DEC { private: typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef typename traits_base::value_type value_type_; typedef typename traits_base::pointer pointer_; typedef typename traits_base::const_pointer const_pointer_; typedef typename traits_base::reference reference_; typedef typename traits_base::const_reference const_reference_; typedef typename traits_base::comp_hash comp_hash; enum entry_status { empty_entry_status, valid_entry_status, erased_entry_status } __attribute__ ((packed)); struct entry : public traits_base::stored_value_type { entry_status m_stat; }; typedef typename Allocator::template rebind::other entry_allocator; typedef typename entry_allocator::pointer entry_pointer; typedef typename entry_allocator::const_pointer const_entry_pointer; typedef typename entry_allocator::reference entry_reference; typedef typename entry_allocator::const_reference const_entry_reference; typedef typename entry_allocator::pointer entry_array; typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; typedef Resize_Policy resize_base; #define PB_DS_GEN_POS typename Allocator::size_type #include #include #include #include #undef PB_DS_GEN_POS public: typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Probe_Fn probe_fn; typedef Comb_Probe_Fn comb_probe_fn; typedef Resize_Policy resize_policy; enum { store_hash = Store_Hash }; typedef typename traits_base::key_type key_type; typedef typename traits_base::key_pointer key_pointer; typedef typename traits_base::const_key_pointer const_key_pointer; typedef typename traits_base::key_reference key_reference; typedef typename traits_base::const_key_reference const_key_reference; typedef typename traits_base::mapped_type mapped_type; typedef typename traits_base::mapped_pointer mapped_pointer; typedef typename traits_base::const_mapped_pointer const_mapped_pointer; typedef typename traits_base::mapped_reference mapped_reference; typedef typename traits_base::const_mapped_reference const_mapped_reference; typedef typename traits_base::value_type value_type; typedef typename traits_base::pointer pointer; typedef typename traits_base::const_pointer const_pointer; typedef typename traits_base::reference reference; typedef typename traits_base::const_reference const_reference; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef point_iterator_ point_iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_point_iterator_ point_iterator; #endif typedef const_point_iterator_ const_point_iterator; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef iterator_ iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_iterator_ iterator; #endif typedef const_iterator_ const_iterator; PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); PB_DS_CLASS_NAME(const Hash_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, const Probe_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, const Probe_Fn&, const Resize_Policy&); template void copy_from_range(It first_it, It last_it); virtual ~PB_DS_CLASS_NAME(); void swap(PB_DS_CLASS_C_DEC& other); inline size_type size() const; inline size_type max_size() const; inline bool empty() const; Hash_Fn& get_hash_fn(); const Hash_Fn& get_hash_fn() const; Eq_Fn& get_eq_fn(); const Eq_Fn& get_eq_fn() const; Probe_Fn& get_probe_fn(); const Probe_Fn& get_probe_fn() const; Comb_Probe_Fn& get_comb_probe_fn(); const Comb_Probe_Fn& get_comb_probe_fn() const; Resize_Policy& get_resize_policy(); const Resize_Policy& get_resize_policy() const; inline std::pair insert(const_reference r_val) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) return insert_imp(r_val, traits_base::m_store_extra_indicator); } inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR return subscript_imp(r_key, traits_base::m_store_extra_indicator); #else insert(r_key); return traits_base::s_null_mapped; #endif } inline point_iterator find(const_key_reference r_key); inline const_point_iterator find(const_key_reference r_key) const; inline point_iterator find_end(); inline const_point_iterator find_end() const; inline bool erase(const_key_reference r_key); template inline size_type erase_if(Pred prd); void clear(); inline iterator begin(); inline const_iterator begin() const; inline iterator end(); inline const_iterator end() const; #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif #ifdef PB_DS_HT_MAP_TRACE_ void trace() const; #endif private: #ifdef PB_DS_DATA_TRUE_INDICATOR friend class iterator_; #endif friend class const_iterator_; void deallocate_all(); void initialize(); void erase_all_valid_entries(entry_array, size_type); inline bool do_resize_if_needed(); inline void do_resize_if_needed_no_throw(); void resize_imp(size_type); virtual void do_resize(size_type); void resize_imp(entry_array, size_type); inline void resize_imp_reassign(entry_pointer, entry_array, false_type); inline void resize_imp_reassign(entry_pointer, entry_array, true_type); inline size_type find_ins_pos(const_key_reference, false_type); inline comp_hash find_ins_pos(const_key_reference, true_type); inline std::pair insert_imp(const_reference, false_type); inline std::pair insert_imp(const_reference, true_type); inline pointer insert_new_imp(const_reference r_val, size_type pos) { _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); if (do_resize_if_needed()) pos = find_ins_pos(PB_DS_V2F(r_val), traits_base::m_store_extra_indicator); _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); entry* const p_e = m_entries + pos; new (&p_e->m_value) value_type(r_val); p_e->m_stat = valid_entry_status; resize_base::notify_inserted(++m_num_used_e); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) _GLIBCXX_DEBUG_ONLY(assert_valid();) return &p_e->m_value; } inline pointer insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) { _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != valid_entry_status); if (do_resize_if_needed()) r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), traits_base::m_store_extra_indicator); _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != valid_entry_status); entry* const p_e =2222 2!2"2 m_entries + r_pos_hash_pair.first; new (&p_e->m_value) value_type(r_val); p_e->m_hash = r_pos_hash_pair.second; p_e->m_stat = valid_entry_status; resize_base::notify_inserted(++m_num_used_e); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) _GLIBCXX_DEBUG_ONLY(assert_valid();) return &p_e->m_value; } #ifdef PB_DS_DATA_TRUE_INDICATOR inline mapped_reference subscript_imp(const_key_reference key, false_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) const size_type pos = find_ins_pos(key, traits_base::m_store_extra_indicator); entry_pointer p_e = &m_entries[pos]; if (p_e->m_stat != valid_entry_status) return insert_new_imp(value_type(key, mapped_type()), pos)->second; _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) return p_e->m_value.second; } inline mapped_reference subscript_imp(const_key_reference key, true_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) comp_hash pos_hash_pair = find_ins_pos(key, traits_base::m_store_extra_indicator); if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) return insert_new_imp(value_type(key, mapped_type()), pos_hash_pair)->second; _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key)); return (m_entries + pos_hash_pair.first)->m_value.second; } #endif inline pointer find_key_pointer(const_key_reference key, false_type) { const size_type hash = ranged_probe_fn_base::operator()(key); size_type i; resize_base::notify_find_search_start(); // Loop until entry is found or until all possible entries accessed. for (i = 0; i < m_num_e; ++i) { const size_type pos = ranged_probe_fn_base::operator()(key, hash, i); entry* const p_e = m_entries + pos; switch (p_e->m_stat) { case empty_entry_status: { resize_base::notify_find_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) return NULL; } break; case valid_entry_status: if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) { resize_base::notify_find_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) return pointer(&p_e->m_value); } break; case erased_entry_status: break; default: _GLIBCXX_DEBUG_ASSERT(0); }; resize_base::notify_find_search_collision(); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) resize_base::notify_find_search_end(); return NULL; } inline pointer find_key_pointer(const_key_reference key, true_type) { comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); size_type i; resize_base::notify_find_search_start(); // Loop until entry is found or until all possible entries accessed. for (i = 0; i < m_num_e; ++i) { const size_type pos = ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); entry* const p_e = m_entries + pos; switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_find_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) return NULL; } break; case valid_entry_status: if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, key, pos_hash_pair.second)) { resize_base::notify_find_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) return pointer(&p_e->m_value); } break; case erased_entry_status: break; default: _GLIBCXX_DEBUG_ASSERT(0); }; resize_base::notify_find_search_collision(); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) resize_base::notify_find_search_end(); return NULL; } inline bool erase_imp(const_key_reference, true_type); inline bool erase_imp(const_key_reference, false_type); inline void erase_entry(entry_pointer p_e); #ifdef PB_DS_DATA_TRUE_INDICATOR void inc_it_state(pointer& r_p_value, size_type& r_pos) const { inc_it_state((const_mapped_pointer& )r_p_value, r_pos); } #endif void inc_it_state(const_pointer& r_p_value, size_type& r_pos) const { _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL); for (++r_pos; r_pos < m_num_e; ++r_pos) { const_entry_pointer p_e =& m_entries[r_pos]; if (p_e->m_stat == valid_entry_status) { r_p_value =& p_e->m_value; return; } } r_p_value = NULL; } void get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const { for (r_pos = 0; r_pos < m_num_e; ++r_pos) { const_entry_pointer p_e = &m_entries[r_pos]; if (p_e->m_stat == valid_entry_status) { r_p_value = &p_e->m_value; return; } } r_p_value = NULL; } void get_start_it_state(pointer& r_p_value, size_type& r_pos) { for (r_pos = 0; r_pos < m_num_e; ++r_pos) { entry_pointer p_e = &m_entries[r_pos]; if (p_e->m_stat == valid_entry_status) { r_p_value = &p_e->m_value; return; } } r_p_value = NULL; } #ifdef _GLIBCXX_DEBUG void assert_entry_array_valid(const entry_array, false_type) const; void assert_entry_array_valid(const entry_array, true_type) const; #endif static entry_allocator s_entry_allocator; static iterator s_end_it; static const_iterator s_const_end_it; size_type m_num_e; size_type m_num_used_e; entry_pointer m_entries; enum { store_hash_ok = !Store_Hash || !is_same::value }; PB_DS_STATIC_ASSERT(sth, store_hash_ok); }; #include #include #include #include #include #include #include #include #include #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_HASH_EQ_FN_C_DEC #undef PB_DS_RANGED_PROBE_FN_C_DEC #undef PB_DS_TYPES_TRAITS_C_DEC #undef PB_DS_DEBUG_MAP_BASE_C_DEC #undef PB_DS_CLASS_NAME #undef PB_DS_V2F #undef PB_DS_V2S } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructor_destructor_no_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s constructors, destructor, * and related functions. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, false_type) { _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status)k; entry* const p_e = m_entries + pos; new (&p_e->m_value) mapped_value_type(r_val); p_e->m_stat = valid_entry_status; _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(p_e->m_value.first);) } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s find related functions, * when the hash value is stored. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::comp_hash PB_DS_CLASS_C_DEC:: find_ins_pos(const_key_reference r_key, true_type) { _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); size_type i; /* The insertion position is initted to a non-legal value to indicate * that it has not been initted yet. */ size_type ins_pos = m_num_e; resize_base::notify_insert_search_start(); for (i = 0; i < m_num_e; ++i) { const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); entry* const p_e = m_entries + pos; switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_insert_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return ((ins_pos == m_num_e) ? std::make_pair(pos, pos_hash_pair.second) : std::make_pair(ins_pos, pos_hash_pair.second)); } break; case erased_entry_status: if (ins_pos == m_num_e) ins_pos = pos; break; case valid_entry_status: if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, r_key, pos_hash_pair.second)) { resize_base::notify_insert_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) return std::make_pair(pos, pos_hash_pair.second); } break; default: _GLIBCXX_DEBUG_ASSERT(0); }; resize_base::notify_insert_search_collision(); } resize_base::notify_insert_search_end(); if (ins_pos == m_num_e) __throw_insert_error(); return std::make_pair(ins_pos, pos_hash_pair.second); } PB_DS_CLASS_T_DEC inline std::pair PB_DS_CLASS_C_DEC:: insert_imp(const_reference r_val, true_type) { const_key_reference r_key = PB_DS_V2F(r_val); comp_hash pos_hash_pair = find_ins_pos(r_key, traits_base::m_store_extra_indicator); _GLIBCXX_DEBUG_ASSERT(pos_hash_pair.first < m_num_e); entry_pointer p_e =& m_entries[pos_hash_pair.first]; if (p_e->m_stat == valid_entry_status) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); return std::make_pair(&p_e->m_value, false); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file resize_fn_imps.hpp * Contains implementations of gp_ht_map_'s resize related functions. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: do_resize_if_needed() { if (!resize_base::is_resize_needed()) return false; resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); return true; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: do_resize(size_type n) { resize_imp(resize_base::get_nearest_larger_size(n)); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: do_resize_if_needed_no_throw() { if (!resize_base::is_resize_needed()) return; try { resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); } catch(...) { } _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: resize_imp(size_type new_size) { #ifdef PB_DS_REGRESSION typename Allocator::group_throw_prob_adjustor adjust(m_num_e); #endif if (new_size == m_num_e) return; _GLIBCXX_DEBUG_ONLY(assert_valid();) const size_type old_size = m_num_e; entry_array a_entries_resized = NULL; // Following line might throw an exception. a_entries_resized = s_entry_allocator.allocate(new_size); ranged_probe_fn_base::notify_resized(new_size); m_num_e = new_size; for (size_type i = 0; i < m_num_e; ++i) a_entries_resized[i].m_stat = empty_entry_status; try { resize_imp(a_entries_resized, old_size); } catch(...) { erase_all_valid_entries(a_entries_resized, new_size); m_num_e = old_size; s_entry_allocator.deallocate(a_entries_resized, new_size); ranged_probe_fn_base::notify_resized(old_size); __throw_exception_again; } // At this point no exceptions can be thrown. _GLIBCXX_DEBUG_ONLY(assert_entry_array_valid(a_entries_resized, traits_base::m_store_extra_indicator);) Resize_Policy::notify_resized(new_size); erase_all_valid_entries(m_entries, old_size); s_entry_allocator.deallocate(m_entries, old_size); m_entries = a_entries_resized; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: resize_imp(entry_array a_entries_resized, size_type old_size) { for (size_type pos = 0; pos < old_size; ++pos) if (m_entries[pos].m_stat == valid_entry_status) resize_imp_reassign(m_entries + pos, a_entries_resized, traits_base::m_store_extra_indicator); } #include #include // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_fn_imps.hpp * Contains implementations of gp_ht_map_'s insert related functions. */ #include #include // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s debug-mode functions. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_entry_array_valid(const entry_array a_entries, true_type) const { size_type iterated_num_used_e = 0; for (size_type pos = 0; pos < m_num_e; ++pos) { const_entry_pointer p_e =& a_entries[pos]; switch(p_e->m_stat) { case empty_entry_status: case erased_entry_status: break; case valid_entry_status: { const_key_reference r_key = PB_DS_V2F(p_e->m_value); debug_base::check_key_exists(r_key); const comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); _GLIBCXX_DEBUG_ASSERT(p_e->m_hash == pos_hash_pair.second); ++iterated_num_used_e; break; } default: _GLIBCXX_DEBUG_ASSERT(0); }; } _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_no_store_hash_fn_imps.hpp * Contains implementations of gp_ht_map_'s insert related functions, * when the hash value is not stored. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: find_ins_pos(const_key_reference r_key, false_type) { size_type hash = ranged_probe_fn_base::operator()(r_key); size_type i; /* The insertion position is initted to a non-legal value to indicate * that it has not been initted yet. */ size_type ins_pos = m_num_e; resize_base::notify_insert_search_start(); for (i = 0; i < m_num_e; ++i) { const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); _GLIBCXX_DEBUG_ASSERT(pos < m_num_e); entry* const p_e = m_entries + pos; switch(p_e->m_stat) { case empty_entry_status: { resize_base::notify_insert_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return (ins_pos == m_num_e) ? pos : ins_pos; } break; case erased_entry_status: if (ins_pos == m_num_e) ins_pos = pos; break; case valid_entry_status: if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_insert_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) return pos; } break; default: _GLIBCXX_DEBUG_ASSERT(0); }; resize_base::notify_insert_search_collision(); } resize_base::notify_insert_search_end(); if (ins_pos == m_num_e) __throw_insert_error(); return ins_pos; } PB_DS_CLASS_T_DEC inline std::pair PB_DS_CLASS_C_DEC:: insert_imp(const_reference r_val, false_type) { const_key_reference r_key = PB_DS_V2F(r_val); const size_type pos = find_ins_pos(r_key, traits_base::m_store_extra_indicator); if (m_entries[pos].m_stat == valid_entry_status) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) return std::make_pair(&(m_entries + pos)->m_value, false); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); return std::make_pair(insert_new_imp(r_val, pos), true); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file info_fn_imps.hpp * Contains implementations of gp_ht_map_'s entire container info related * functions. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const { return m_num_used_e; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const { return s_entry_allocator.max_size(); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const { return (size() == 0); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file trace_fn_imps.hpp * Contains implementations of gp_ht_map_'s trace-mode fun