diff options
Diffstat (limited to 'gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_')
26 files changed, 2662 insertions, 0 deletions
diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp new file mode 100644 index 0000000..d2cda4b --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp @@ -0,0 +1,679 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/cc_ht_map_.hpp + * Contains an implementation class for cc_ht_map_. + */ + +#include <utility> +#include <iterator> +#include <ext/pb_ds/detail/cond_dealtor.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> +#include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp> +#include <ext/pb_ds/detail/types_traits.hpp> +#include <ext/pb_ds/exception.hpp> +#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> +#ifdef _GLIBCXX_DEBUG +#include <ext/pb_ds/detail/debug_map_base.hpp> +#endif +#ifdef PB_DS_HT_MAP_TRACE_ +#include <iostream> +#endif +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_CC_HASH_NAME cc_ht_map +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_CC_HASH_NAME cc_ht_set +#endif + +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Hash_Fn, \ + typename Eq_Fn, typename _Alloc, bool Store_Hash, \ + typename Comb_Hash_Fn, typename Resize_Policy> + +#define PB_DS_CLASS_C_DEC \ + PB_DS_CC_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ + Store_Hash, Comb_Hash_Fn, Resize_Policy> + +#define PB_DS_HASH_EQ_FN_C_DEC \ + hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> + +#define PB_DS_RANGED_HASH_FN_C_DEC \ + ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, Store_Hash> + +#define PB_DS_CC_HASH_TRAITS_BASE \ + types_traits<Key, Mapped, _Alloc, Store_Hash> + +#ifdef _GLIBCXX_DEBUG +#define PB_DS_DEBUG_MAP_BASE_C_DEC \ + debug_map_base<Key, Eq_Fn, \ + typename _Alloc::template rebind<Key>::other::const_reference> +#endif + + + /** + * A collision-chaining hash-based container. + * + * + * @ingroup hash-detail + * + * @tparam Key Key type. + * + * @tparam Mapped Map type. + * + * @tparam Hash_Fn Hashing functor. + * Default is __gnu_cxx::hash. + * + * @tparam Eq_Fn Equal functor. + * Default std::equal_to<Key> + * + * @tparam _Alloc Allocator type. + * + * @tparam Store_Hash If key type stores extra metadata. + * Defaults to false. + * + * @tparam Comb_Hash_Fn Combining hash functor. + * If Hash_Fn is not null_type, then this + * is the ranged-hash functor; otherwise, + * this is the range-hashing functor. + * XXX(See Design::Hash-Based Containers::Hash Policies.) + * Default direct_mask_range_hashing. + * + * @tparam Resize_Policy Resizes hash. + * Defaults to hash_standard_resize_policy, + * using hash_exponential_size_policy and + * hash_load_check_resize_trigger. + * + * + * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_hash_fn, + * detail::types_traits. (Optional: detail::debug_map_base.) + */ + template<typename Key, + typename Mapped, + typename Hash_Fn, + typename Eq_Fn, + typename _Alloc, + bool Store_Hash, + typename Comb_Hash_Fn, + typename Resize_Policy > + class PB_DS_CC_HASH_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_HASH_FN_C_DEC, + public PB_DS_CC_HASH_TRAITS_BASE + { + private: + typedef PB_DS_CC_HASH_TRAITS_BASE traits_base; + typedef typename traits_base::comp_hash comp_hash; + 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_; + + struct entry : public traits_base::stored_data_type + { + typename _Alloc::template rebind<entry>::other::pointer m_p_next; + }; + + typedef cond_dealtor<entry, _Alloc> cond_dealtor_t; + + typedef typename _Alloc::template rebind<entry>::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 _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator; + typedef typename entry_pointer_allocator::pointer entry_pointer_array; + + typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; + typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; + typedef Resize_Policy resize_base; + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + +#define PB_DS_GEN_POS std::pair<entry_pointer, typename _Alloc::size_type> + +#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> + +#undef PB_DS_GEN_POS + + public: + typedef _Alloc allocator_type; + typedef typename _Alloc::size_type size_type; + typedef typename _Alloc::difference_type difference_type; + typedef Hash_Fn hash_fn; + typedef Eq_Fn eq_fn; + typedef Comb_Hash_Fn comb_hash_fn; + typedef Resize_Policy resize_policy; + + /// Value stores hash, true or false. + 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::key_const_pointer key_const_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::key_const_reference key_const_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::mapped_const_pointer mapped_const_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::mapped_const_reference mapped_const_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 point_const_iterator_ point_iterator; +#endif + + typedef point_const_iterator_ point_const_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_CC_HASH_NAME(); + + PB_DS_CC_HASH_NAME(const Hash_Fn&); + + PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&); + + PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); + + PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, + const Resize_Policy&); + + PB_DS_CC_HASH_NAME(const PB_DS_CLASS_C_DEC&); + + virtual + ~PB_DS_CC_HASH_NAME(); + + void + swap(PB_DS_CLASS_C_DEC&); + + template<typename It> + void + copy_from_range(It, It); + + void + initialize(); + + inline size_type + size() const; + + inline size_type + max_size() const; + + /// True if size() == 0. + inline bool + empty() const; + + /// Return current hash_fn. + Hash_Fn& + get_hash_fn(); + + /// Return current const hash_fn. + const Hash_Fn& + get_hash_fn() const; + + /// Return current eq_fn. + Eq_Fn& + get_eq_fn(); + + /// Return current const eq_fn. + const Eq_Fn& + get_eq_fn() const; + + /// Return current comb_hash_fn. + Comb_Hash_Fn& + get_comb_hash_fn(); + + /// Return current const comb_hash_fn. + const Comb_Hash_Fn& + get_comb_hash_fn() const; + + /// Return current resize_policy. + Resize_Policy& + get_resize_policy(); + + /// Return current const resize_policy. + const Resize_Policy& + get_resize_policy() const; + + inline std::pair<point_iterator, bool> + insert(const_reference r_val) + { return insert_imp(r_val, traits_base::m_store_extra_indicator); } + + inline mapped_reference + operator[](key_const_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_type; +#endif + } + + inline point_iterator + find(key_const_reference); + + inline point_const_iterator + find(key_const_reference) const; + + inline point_iterator + find_end(); + + inline point_const_iterator + find_end() const; + + inline bool + erase(key_const_reference); + + template<typename Pred> + inline size_type + erase_if(Pred); + + 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 char*, int) const; +#endif + +#ifdef PB_DS_HT_MAP_TRACE_ + void + trace() const; +#endif + + private: + void + deallocate_all(); + + inline bool + do_resize_if_needed(); + + inline void + do_resize_if_needed_no_throw(); + + void + resize_imp(size_type); + + void + do_resize(size_type); + + void + resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); + + inline entry_pointer + resize_imp_no_exceptions_reassign_pointer(entry_pointer, + entry_pointer_array, + false_type); + + inline entry_pointer + resize_imp_no_exceptions_reassign_pointer(entry_pointer, + entry_pointer_array, + true_type); + + void + deallocate_links_in_list(entry_pointer); + + inline entry_pointer + get_entry(const_reference, false_type); + + inline entry_pointer + get_entry(const_reference, true_type); + + inline void + rels_entry(entry_pointer); + +#ifdef PB_DS_DATA_TRUE_INDICATOR + inline mapped_reference + subscript_imp(key_const_reference r_key, false_type) + { + _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) + const size_type pos = ranged_hash_fn_base::operator()(r_key); + entry_pointer p_e = m_entries[pos]; + resize_base::notify_insert_search_start(); + + while (p_e != 0 + && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) + { + resize_base::notify_insert_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_insert_search_end(); + if (p_e != 0) + { + PB_DS_CHECK_KEY_EXISTS(r_key) + return (p_e->m_value.second); + } + + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; + } + + inline mapped_reference + subscript_imp(key_const_reference r_key, true_type) + { + _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) + comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); + entry_pointer p_e = m_entries[pos_hash_pair.first]; + resize_base::notify_insert_search_start(); + while (p_e != 0 && + !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, + r_key, pos_hash_pair.second)) + { + resize_base::notify_insert_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_insert_search_end(); + if (p_e != 0) + { + PB_DS_CHECK_KEY_EXISTS(r_key) + return p_e->m_value.second; + } + + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return insert_new_imp(value_type(r_key, mapped_type()), + pos_hash_pair)->second; + } +#endif + + inline std::pair<point_iterator, bool> + insert_imp(const_reference, false_type); + + inline std::pair<point_iterator, bool> + insert_imp(const_reference, true_type); + + inline pointer + insert_new_imp(const_reference r_val, size_type pos) + { + if (do_resize_if_needed()) + pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); + + // Following lines might throw an exception. + entry_pointer p_e = get_entry(r_val, + traits_base::m_no_throw_copies_indicator); + + // At this point no exceptions can be thrown. + p_e->m_p_next = m_entries[pos]; + m_entries[pos] = p_e; + resize_base::notify_inserted(++m_num_used_e); + + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) + _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) + return &p_e->m_value; + } + + inline pointer + insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) + { + // Following lines might throw an exception. + if (do_resize_if_needed()) + r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); + + entry_pointer p_e = get_entry(r_val, + traits_base::m_no_throw_copies_indicator); + + // At this point no exceptions can be thrown. + p_e->m_hash = r_pos_hash_pair.second; + p_e->m_p_next = m_entries[r_pos_hash_pair.first]; + m_entries[r_pos_hash_pair.first] = p_e; + resize_base::notify_inserted(++m_num_used_e); + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) + _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) + return &p_e->m_value; + } + + inline pointer + find_key_pointer(key_const_reference r_key, false_type) + { + entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; + resize_base::notify_find_search_start(); + while (p_e != 0 && + !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) + { + resize_base::notify_find_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_find_search_end(); + +#ifdef _GLIBCXX_DEBUG + if (p_e == 0) + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + else + PB_DS_CHECK_KEY_EXISTS(r_key) +#endif + return &p_e->m_value; + } + + inline pointer + find_key_pointer(key_const_reference r_key, true_type) + { + comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); + entry_pointer p_e = m_entries[pos_hash_pair.first]; + resize_base::notify_find_search_start(); + while (p_e != 0 && + !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_find_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_find_search_end(); + +#ifdef _GLIBCXX_DEBUG + if (p_e == 0) + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + else + PB_DS_CHECK_KEY_EXISTS(r_key) +#endif + return &p_e->m_value; + } + + inline bool + erase_in_pos_imp(key_const_reference, size_type); + + inline bool + erase_in_pos_imp(key_const_reference, const comp_hash&); + + inline void + erase_entry_pointer(entry_pointer&); + +#ifdef PB_DS_DATA_TRUE_INDICATOR + void + inc_it_state(pointer& r_p_value, + std::pair<entry_pointer, size_type>& r_pos) const + { + inc_it_state((mapped_const_pointer& )r_p_value, r_pos); + } +#endif + + void + inc_it_state(const_pointer& r_p_value, + std::pair<entry_pointer, size_type>& r_pos) const + { + _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); + r_pos.first = r_pos.first->m_p_next; + if (r_pos.first != 0) + { + r_p_value = &r_pos.first->m_value; + return; + } + + for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) + if (m_entries[r_pos.second] != 0) + { + r_pos.first = m_entries[r_pos.second]; + r_p_value = &r_pos.first->m_value; + return; + } + r_p_value = 0; + } + + void + get_start_it_state(pointer& r_p_value, + std::pair<entry_pointer, size_type>& r_pos) const + { + for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) + if (m_entries[r_pos.second] != 0) + { + r_pos.first = m_entries[r_pos.second]; + r_p_value = &r_pos.first->m_value; + return; + } + r_p_value = 0; + } + +#ifdef _GLIBCXX_DEBUG + void + assert_entry_pointer_array_valid(const entry_pointer_array, + const char*, int) const; + + void + assert_entry_pointer_valid(const entry_pointer, true_type, + const char*, int) const; + + void + assert_entry_pointer_valid(const entry_pointer, false_type, + const char*, int) const; +#endif + +#ifdef PB_DS_HT_MAP_TRACE_ + void + trace_list(const_entry_pointer) const; +#endif + + private: +#ifdef PB_DS_DATA_TRUE_INDICATOR + friend class iterator_; +#endif + + friend class const_iterator_; + + static entry_allocator s_entry_allocator; + static entry_pointer_allocator s_entry_pointer_allocator; + static iterator s_end_it; + static const_iterator s_const_end_it; + static point_iterator s_find_end_it; + static point_const_iterator s_const_find_end_it; + + size_type m_num_e; + size_type m_num_used_e; + entry_pointer_array m_entries; + + enum + { + store_hash_ok = !Store_Hash + || !is_same<Hash_Fn, __gnu_pbds::null_type>::value + }; + + PB_DS_STATIC_ASSERT(sth, store_hash_ok); + }; + +#include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp> + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_HASH_EQ_FN_C_DEC +#undef PB_DS_RANGED_HASH_FN_C_DEC +#undef PB_DS_CC_HASH_TRAITS_BASE +#undef PB_DS_DEBUG_MAP_BASE_C_DEC +#undef PB_DS_CC_HASH_NAME + } // namespace detail +} // namespace __gnu_pbds diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp new file mode 100644 index 0000000..dd2da87 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cmp_fn_imps.hpp @@ -0,0 +1,83 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/cmp_fn_imps.hpp + * Contains implementations of cc_ht_map_'s entire container comparison related + * functions. + */ + +PB_DS_CLASS_T_DEC +template<typename Other_HT_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +operator==(const Other_HT_Map_Type& other) const +{ return cmp_with_other(other); } + +PB_DS_CLASS_T_DEC +template<typename Other_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +cmp_with_other(const Other_Map_Type& other) const +{ + if (size() != other.size()) + return false; + + for (typename Other_Map_Type::const_iterator it = other.begin(); + it != other.end(); ++it) + { + key_const_reference r_key = key_const_reference(PB_DS_V2F(*it)); + + mapped_const_pointer p_mapped_value = + const_cast<PB_DS_CLASS_C_DEC& >(*this). + find_key_pointer(r_key, traits_base::m_store_extra_indicator); + + if (p_mapped_value == 0) + return false; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + if (p_mapped_value->second != it->second) + return false; +#endif + } + return true; +} + +PB_DS_CLASS_T_DEC +template<typename Other_HT_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +operator!=(const Other_HT_Map_Type& other) const +{ return !operator==(other); } diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp new file mode 100644 index 0000000..a38d423 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp @@ -0,0 +1,90 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/cond_key_dtor_entry_dealtor.hpp + * Contains a conditional key destructor, used for exception handling. + */ + +namespace __gnu_pbds +{ + namespace detail + { + /// Conditional dey destructor, cc_hash. + template<typename HT_Map> + class cond_dealtor + { + public: + typedef typename HT_Map::entry entry; + typedef typename HT_Map::entry_allocator entry_allocator; + typedef typename HT_Map::key_type key_type; + + cond_dealtor(entry_allocator* p_a, entry* p_e) + : m_p_a(p_a), m_p_e(p_e), m_key_destruct(false), + m_no_action_destructor(false) + { } + + inline + ~cond_dealtor(); + + void + set_key_destruct() + { m_key_destruct = true; } + + void + set_no_action_destructor() + { m_no_action_destructor = true; } + + protected: + entry_allocator* const m_p_a; + entry* const m_p_e; + + bool m_key_destruct; + bool m_no_action_destructor; + }; + + template<typename HT_Map> + inline + cond_dealtor<HT_Map>:: + ~cond_dealtor() + { + if (m_no_action_destructor) + return; + if (m_key_destruct) + m_p_e->m_value.first.~key_type(); + m_p_a->deallocate(m_p_e, 1); + } + } // namespace detail +} // namespace __gnu_pbds diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp new file mode 100644 index 0000000..3b54c30 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp @@ -0,0 +1,191 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/constructor_destructor_fn_imps.hpp + * Contains implementations of cc_ht_map_'s constructors, destructor, + * and related functions. + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::entry_allocator +PB_DS_CLASS_C_DEC::s_entry_allocator; + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::entry_pointer_allocator +PB_DS_CLASS_C_DEC::s_entry_pointer_allocator; + +PB_DS_CLASS_T_DEC +template<typename It> +void +PB_DS_CLASS_C_DEC:: +copy_from_range(It first_it, It last_it) +{ + while (first_it != last_it) + insert(*(first_it++)); +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME() : + ranged_hash_fn_base(resize_base::get_nearest_larger_size(1)), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME(const Hash_Fn& r_hash_fn) : + ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn) : + PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), + ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + std::fill(m_entries, m_entries + m_num_e, (entry_pointer)0); + Resize_Policy::notify_cleared(); + ranged_hash_fn_base::notify_resized(m_num_e); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, + const Comb_Hash_Fn& r_comb_hash_fn) : + PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), + ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), + r_hash_fn, r_comb_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, + const Comb_Hash_Fn& r_comb_hash_fn, + const Resize_Policy& r_resize_policy) : + PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), + Resize_Policy(r_resize_policy), + ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), + r_hash_fn, r_comb_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CC_HASH_NAME(const PB_DS_CLASS_C_DEC& other) : + PB_DS_HASH_EQ_FN_C_DEC(other), + resize_base(other), ranged_hash_fn_base(other), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_pointer_allocator.allocate(m_num_e)) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) + __try + { + copy_from_range(other.begin(), other.end()); + } + __catch(...) + { + deallocate_all(); + __throw_exception_again; + } + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +~PB_DS_CC_HASH_NAME() +{ deallocate_all(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + + std::swap(m_entries, other.m_entries); + std::swap(m_num_e, other.m_num_e); + std::swap(m_num_used_e, other.m_num_used_e); + ranged_hash_fn_base::swap(other); + hash_eq_fn_base::swap(other); + resize_base::swap(other); + + _GLIBCXX_DEBUG_ONLY(debug_base::swap(other)); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +deallocate_all() +{ + clear(); + s_entry_pointer_allocator.deallocate(m_entries, m_num_e); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +initialize() +{ + std::fill(m_entries, m_entries + m_num_e, entry_pointer(0)); + Resize_Policy::notify_resized(m_num_e); + Resize_Policy::notify_cleared(); + ranged_hash_fn_base::notify_resized(m_num_e); +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp new file mode 100644 index 0000000..90f7808 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp @@ -0,0 +1,55 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s constructors, destructor, + * and related functions. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +constructor_insert_new_imp(mapped_const_reference r_val, size_type pos, + false_type) +{ + // Following lines might throw an exception. + entry_pointer p = get_entry(r_val, traits_base::s_no_throw_copies_indicator); + + // At this point no exceptions can be thrown. + p->m_p_next = m_entries[pos]; + m_entries[pos] = p; + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(r_key);) +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp new file mode 100644 index 0000000..db36fd1 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp @@ -0,0 +1,56 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp + * Contains implementations of cc_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_reference r_val, size_type pos, true_type) +{ + // Following lines might throw an exception. + entry_pointer p = get_entry(r_val, traits_base::s_no_throw_copies_indicator); + + // At this point no exceptions can be thrown. + p->m_p_next = m_entries[pos]; + p->m_hash = ranged_hash_fn_base::operator()((key_const_reference)(PB_DS_V2F(p->m_value))).second; + + m_entries[pos] = p; + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(r_key);) +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp new file mode 100644 index 0000000..a86face --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp @@ -0,0 +1,76 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/debug_fn_imps.hpp + * Contains implementations of cc_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_valid(const char* __file, int __line) const +{ + debug_base::check_size(m_num_used_e, __file, __line); + assert_entry_pointer_array_valid(m_entries, __file, __line); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries, + const char* __file, int __line) const +{ + size_type iterated_num_used_e = 0; + for (size_type pos = 0; pos < m_num_e; ++pos) + { + entry_pointer p_e = a_p_entries[pos]; + while (p_e != 0) + { + ++iterated_num_used_e; + assert_entry_pointer_valid(p_e, traits_base::m_store_extra_indicator, + __file, __line); + p_e = p_e->m_p_next; + } + } + PB_DS_DEBUG_VERIFY(iterated_num_used_e == m_num_used_e); +} + +#include <ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp> + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp new file mode 100644 index 0000000..d1c6905 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp @@ -0,0 +1,50 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/debug_no_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_entry_pointer_valid(const entry_pointer p, false_type, + const char* __file, int __line) const +{ debug_base::check_key_exists(PB_DS_V2F(p->m_value), __file, __line); } + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp new file mode 100644 index 0000000..d686bbb --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/debug_store_hash_fn_imps.hpp @@ -0,0 +1,54 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/debug_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_entry_pointer_valid(const entry_pointer p_e, true_type, + const char* __file, int __line) const +{ + debug_base::check_key_exists(PB_DS_V2F(p_e->m_value), __file, __line); + comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value)); + PB_DS_DEBUG_VERIFY(p_e->m_hash == pos_hash_pair.second); +} + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp new file mode 100644 index 0000000..be2086d --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp @@ -0,0 +1,91 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/entry_list_fn_imps.hpp + * Contains implementations of cc_ht_map_'s entry-list related functions. + */ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +deallocate_links_in_list(entry_pointer p_e) +{ + while (p_e != 0) + { + entry_pointer p_dealloc_e = p_e; + p_e = p_e->m_p_next; + s_entry_allocator.deallocate(p_dealloc_e, 1); + } +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::entry_pointer +PB_DS_CLASS_C_DEC:: +get_entry(const_reference r_val, true_type) +{ + // Following line might throw an exception. + entry_pointer p_e = s_entry_allocator.allocate(1); + + // Following lines* cannot* throw an exception. + new (&p_e->m_value) value_type(r_val); + return p_e; +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::entry_pointer +PB_DS_CLASS_C_DEC:: +get_entry(const_reference r_val, false_type) +{ + // Following line might throw an exception. + entry_pointer p_e = s_entry_allocator.allocate(1); + cond_dealtor_t cond(p_e); + + // Following lines might throw an exception. + new (&p_e->m_value) value_type(r_val); + cond.set_no_action(); + return p_e; +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +rels_entry(entry_pointer p_e) +{ + // The following lines cannot throw exceptions (unless if key-data dtors do). + p_e->m_value.~value_type(); + s_entry_allocator.deallocate(p_e, 1); +} + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp new file mode 100644 index 0000000..e9d9ded --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp @@ -0,0 +1,103 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/erase_fn_imps.hpp + * Contains implementations of cc_ht_map_'s erase related functions. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +erase_entry_pointer(entry_pointer& r_p_e) +{ + _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(r_p_e->m_value))); + + entry_pointer p_e = r_p_e; + r_p_e = r_p_e->m_p_next; + rels_entry(p_e); + _GLIBCXX_DEBUG_ASSERT(m_num_used_e > 0); + resize_base::notify_erased(--m_num_used_e); +} + +PB_DS_CLASS_T_DEC +template<typename Pred> +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +erase_if(Pred pred) +{ + size_type num_ersd = 0; + for (size_type pos = 0; pos < m_num_e; ++pos) + { + while (m_entries[pos] != 0 && pred(m_entries[pos]->m_value)) + { + ++num_ersd; + entry_pointer p_next_e = m_entries[pos]->m_p_next; + erase_entry_pointer(m_entries[pos]); + m_entries[pos] = p_next_e; + } + + entry_pointer p_e = m_entries[pos]; + while (p_e != 0 && p_e->m_p_next != 0) + { + if (pred(p_e->m_p_next->m_value)) + { + ++num_ersd; + erase_entry_pointer(p_e->m_p_next); + } + else + p_e = p_e->m_p_next; + } + } + + do_resize_if_needed_no_throw(); + return num_ersd; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear() +{ + for (size_type pos = 0; pos < m_num_e; ++pos) + while (m_entries[pos] != 0) + erase_entry_pointer(m_entries[pos]); + do_resize_if_needed_no_throw(); + resize_base::notify_cleared(); +} + +#include <ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp> + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp new file mode 100644 index 0000000..e8a9749 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp @@ -0,0 +1,100 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/erase_no_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s erase related functions, + * when the hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase(key_const_reference r_key) +{ + PB_DS_ASSERT_VALID((*this)) + return erase_in_pos_imp(r_key, ranged_hash_fn_base::operator()(r_key)); +} + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase_in_pos_imp(key_const_reference r_key, size_type pos) +{ + PB_DS_ASSERT_VALID((*this)) + entry_pointer p_e = m_entries[pos]; + resize_base::notify_erase_search_start(); + if (p_e == 0) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + PB_DS_ASSERT_VALID((*this)) + return false; + } + + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_EXISTS(r_key) + erase_entry_pointer(m_entries[pos]); + do_resize_if_needed_no_throw(); + PB_DS_ASSERT_VALID((*this)) + return true; + } + + while (true) + { + entry_pointer p_next_e = p_e->m_p_next; + if (p_next_e == 0) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + PB_DS_ASSERT_VALID((*this)) + return false; + } + + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), r_key)) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_EXISTS(r_key) + erase_entry_pointer(p_e->m_p_next); + do_resize_if_needed_no_throw(); + PB_DS_ASSERT_VALID((*this)) + return true; + } + resize_base::notify_erase_search_collision(); + p_e = p_next_e; + } +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp new file mode 100644 index 0000000..a1840e5 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/erase_store_hash_fn_imps.hpp @@ -0,0 +1,94 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/erase_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s erase related functions, + * when the hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase_in_pos_imp(key_const_reference r_key, const comp_hash& r_pos_hash_pair) +{ + PB_DS_ASSERT_VALID((*this)) + entry_pointer p_e = m_entries[r_pos_hash_pair.first]; + resize_base::notify_erase_search_start(); + if (p_e == 0) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + PB_DS_ASSERT_VALID((*this)) + return false; + } + + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, + r_key, r_pos_hash_pair.second)) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_EXISTS(r_key) + erase_entry_pointer(m_entries[r_pos_hash_pair.first]); + do_resize_if_needed_no_throw(); + PB_DS_ASSERT_VALID((*this)) + return true; + } + + while (true) + { + entry_pointer p_next_e = p_e->m_p_next; + if (p_next_e == 0) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + PB_DS_ASSERT_VALID((*this)) + return false; + } + + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), + p_next_e->m_hash, r_key, + r_pos_hash_pair.second)) + { + resize_base::notify_erase_search_end(); + PB_DS_CHECK_KEY_EXISTS(r_key) + erase_entry_pointer(p_e->m_p_next); + do_resize_if_needed_no_throw(); + PB_DS_ASSERT_VALID((*this)) + return true; + } + resize_base::notify_erase_search_collision(); + p_e = p_next_e; + } +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp new file mode 100644 index 0000000..fe8bc6a --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp @@ -0,0 +1,71 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/find_fn_imps.hpp + * Contains implementations of cc_ht_map_'s find related functions. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find(key_const_reference r_key) +{ + PB_DS_ASSERT_VALID((*this)) + return find_key_pointer(r_key, traits_base::m_store_extra_indicator); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_const_iterator +PB_DS_CLASS_C_DEC:: +find(key_const_reference r_key) const +{ + PB_DS_ASSERT_VALID((*this)) + return const_cast<PB_DS_CLASS_C_DEC& >(*this).find_key_pointer(r_key, + traits_base::m_store_extra_indicator); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find_end() +{ return 0; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_const_iterator +PB_DS_CLASS_C_DEC:: +find_end() const +{ return 0; } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp new file mode 100644 index 0000000..ce727a1 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/find_store_hash_fn_imps.hpp @@ -0,0 +1,41 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/find_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s find related functions, + * when the hash value is stored. + */ + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp new file mode 100644 index 0000000..a87f2b6 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp @@ -0,0 +1,100 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/info_fn_imps.hpp + * Contains implementations of cc_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 m_entry_allocator.max_size(); } + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +empty() const +{ return (size() == 0); } + +PB_DS_CLASS_T_DEC +template<typename Other_HT_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +operator==(const Other_HT_Map_Type& other) const +{ return cmp_with_other(other); } + +PB_DS_CLASS_T_DEC +template<typename Other_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +cmp_with_other(const Other_Map_Type& other) const +{ + if (size() != other.size()) + return false; + + for (typename Other_Map_Type::const_iterator it = other.begin(); + it != other.end(); ++it) + { + key_const_reference r_key =(key_const_reference)PB_DS_V2F(*it); + mapped_const_pointer p_mapped_value = + const_cast<PB_DS_CLASS_C_DEC& >(*this). + find_key_pointer(r_key, traits_base::m_store_extra_indicator); + + if (p_mapped_value == 0) + return false; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + if (p_mapped_value->second != it->second) + return false; +#endif + } + return true; +} + +PB_DS_CLASS_T_DEC +template<typename Other_HT_Map_Type> +bool +PB_DS_CLASS_C_DEC:: +operator!=(const Other_HT_Map_Type& other) const +{ return !operator==(other); } diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp new file mode 100644 index 0000000..4553662 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp @@ -0,0 +1,43 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/insert_fn_imps.hpp + * Contains implementations of cc_ht_map_'s insert related functions. + */ + +#include <ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp> + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp new file mode 100644 index 0000000..1257f48 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp @@ -0,0 +1,70 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/insert_no_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s insert related functions, + * when the hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> +PB_DS_CLASS_C_DEC:: +insert_imp(const_reference r_val, false_type) +{ + PB_DS_ASSERT_VALID((*this)) + key_const_reference r_key = PB_DS_V2F(r_val); + const size_type pos = ranged_hash_fn_base::operator()(r_key); + entry_pointer p_e = m_entries[pos]; + resize_base::notify_insert_search_start(); + + while (p_e != 0 && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), + r_key)) + { + resize_base::notify_insert_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_insert_search_end(); + if (p_e != 0) + { + PB_DS_CHECK_KEY_EXISTS(r_key) + return std::make_pair(&p_e->m_value, false); + } + + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return std::make_pair(insert_new_imp(r_val, pos), true); +} + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp new file mode 100644 index 0000000..ef7d102 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/insert_store_hash_fn_imps.hpp @@ -0,0 +1,71 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/insert_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s insert related functions, + * when the hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> +PB_DS_CLASS_C_DEC:: +insert_imp(const_reference r_val, true_type) +{ + PB_DS_ASSERT_VALID((*this)) + key_const_reference key = PB_DS_V2F(r_val); + comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(key); + entry_pointer p_e = m_entries[pos_hash_pair.first]; + resize_base::notify_insert_search_start(); + + while (p_e != 0 && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), + p_e->m_hash, + key, pos_hash_pair.second)) + { + resize_base::notify_insert_search_collision(); + p_e = p_e->m_p_next; + } + + resize_base::notify_insert_search_end(); + if (p_e != 0) + { + PB_DS_CHECK_KEY_EXISTS(key) + return std::make_pair(&p_e->m_value, false); + } + + PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) + return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); +} + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp new file mode 100644 index 0000000..821c6d5 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp @@ -0,0 +1,83 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/iterators_fn_imps.hpp + * Contains implementations of cc_ht_map_'s iterators related functions, e.g., + * begin(). + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC::s_end_it; + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC::s_const_end_it; + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +begin() +{ + pointer p_value; + std::pair<entry_pointer, size_type> pos; + get_start_it_state(p_value, pos); + return iterator(p_value, pos, this); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +end() +{ return s_end_it; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +begin() const +{ + pointer p_value; + std::pair<entry_pointer, size_type> pos; + get_start_it_state(p_value, pos); + return const_iterator(p_value, pos, this); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +end() const +{ return s_const_end_it; } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp new file mode 100644 index 0000000..7f547c3 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp @@ -0,0 +1,88 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/policy_access_fn_imps.hpp + * Contains implementations of cc_ht_map_'s policy access + * functions. + */ + +PB_DS_CLASS_T_DEC +Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_hash_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_hash_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Eq_Fn& +PB_DS_CLASS_C_DEC:: +get_eq_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Eq_Fn& +PB_DS_CLASS_C_DEC:: +get_eq_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Comb_Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_comb_hash_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Comb_Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_comb_hash_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Resize_Policy& +PB_DS_CLASS_C_DEC:: +get_resize_policy() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Resize_Policy& +PB_DS_CLASS_C_DEC:: +get_resize_policy() const +{ return *this; } diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp new file mode 100644 index 0000000..c4889d3 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp @@ -0,0 +1,134 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/resize_fn_imps.hpp + * Contains implementations of cc_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 len) +{ resize_imp(resize_base::get_nearest_larger_size(len)); } + +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(...) + { } + + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +resize_imp(size_type new_size) +{ + PB_DS_ASSERT_VALID((*this)) + if (new_size == m_num_e) + return; + + const size_type old_size = m_num_e; + entry_pointer_array a_p_entries_resized; + + // Following line might throw an exception. + ranged_hash_fn_base::notify_resized(new_size); + + __try + { + // Following line might throw an exception. + a_p_entries_resized = s_entry_pointer_allocator.allocate(new_size); + m_num_e = new_size; + } + __catch(...) + { + ranged_hash_fn_base::notify_resized(old_size); + __throw_exception_again; + } + + // At this point no exceptions can be thrown. + resize_imp_no_exceptions(new_size, a_p_entries_resized, old_size); + Resize_Policy::notify_resized(new_size); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size) +{ + std::fill(a_p_entries_resized, a_p_entries_resized + m_num_e, + entry_pointer(0)); + + for (size_type pos = 0; pos < old_size; ++pos) + { + entry_pointer p_e = m_entries[pos]; + while (p_e != 0) + p_e = resize_imp_no_exceptions_reassign_pointer(p_e, a_p_entries_resized, traits_base::m_store_extra_indicator); + } + + m_num_e = new_size; + _GLIBCXX_DEBUG_ONLY(assert_entry_pointer_array_valid(a_p_entries_resized, + __FILE__, __LINE__);) + s_entry_pointer_allocator.deallocate(m_entries, old_size); + m_entries = a_p_entries_resized; + PB_DS_ASSERT_VALID((*this)) +} + +#include <ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp> + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp new file mode 100644 index 0000000..d316b2d --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp @@ -0,0 +1,54 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/resize_no_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s resize related functions, when the + * hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::entry_pointer +PB_DS_CLASS_C_DEC:: +resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, false_type) +{ + const size_type hash_pos = + ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value)); + + entry_pointer const p_next_e = p_e->m_p_next; + p_e->m_p_next = a_p_entries_resized[hash_pos]; + a_p_entries_resized[hash_pos] = p_e; + return p_next_e; +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp new file mode 100644 index 0000000..19d2c92 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/resize_store_hash_fn_imps.hpp @@ -0,0 +1,54 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/resize_store_hash_fn_imps.hpp + * Contains implementations of cc_ht_map_'s resize related functions, when the + * hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::entry_pointer +PB_DS_CLASS_C_DEC:: +resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, true_type) +{ + const comp_hash pos_hash_pair = + ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash); + + entry_pointer const p_next_e = p_e->m_p_next; + p_e->m_p_next = a_p_entries_resized[pos_hash_pair.first]; + a_p_entries_resized[pos_hash_pair.first] = p_e; + return p_next_e; +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp new file mode 100644 index 0000000..ca0089e --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp @@ -0,0 +1,59 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/size_fn_imps.hpp + * Contains implementations of cc_ht_map_'s entire container size 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 bool +PB_DS_CLASS_C_DEC:: +empty() const +{ return (size() == 0); } + +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(); } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp new file mode 100644 index 0000000..bf53ed1 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp @@ -0,0 +1,72 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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 3, 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// 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 cc_hash_table_map_/trace_fn_imps.hpp + * Contains implementations of cc_ht_map_'s trace-mode functions. + */ + +#ifdef PB_DS_HT_MAP_TRACE_ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace() const +{ + std::cerr << static_cast<unsigned long>(m_num_e) << " " + << static_cast<unsigned long>(m_num_used_e) << std::endl; + + for (size_type i = 0; i < m_num_e; ++i) + { + std::cerr << static_cast<unsigned long>(i) << " "; + trace_list(m_entries[i]); + std::cerr << std::endl; + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace_list(const_entry_pointer p_l) const +{ + size_type iterated_num_used_e = 0; + while (p_l != 0) + { + std::cerr << PB_DS_V2F(p_l->m_value) << " "; + p_l = p_l->m_p_next; + } +} + +#endif |