| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp |
|---|
| 0,0 → 1,136 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/constructor_destructor_fn_imps.hpp |
| */ |
| 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 |
| Eq_Fn PB_DS_CLASS_C_DEC::s_eq_fn; |
| PB_DS_CLASS_T_DEC |
| null_type PB_DS_CLASS_C_DEC::s_null_type; |
| PB_DS_CLASS_T_DEC |
| Update_Policy PB_DS_CLASS_C_DEC::s_update_policy; |
| PB_DS_CLASS_T_DEC |
| type_to_type< |
| typename PB_DS_CLASS_C_DEC::update_metadata> PB_DS_CLASS_C_DEC::s_metadata_type_indicator; |
| 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_LU_NAME() : m_p_l(0) |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| template<typename It> |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_LU_NAME(It first_it, It last_it) : m_p_l(0) |
| { |
| copy_from_range(first_it, last_it); |
| PB_DS_ASSERT_VALID((*this)); |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC& other) : |
| m_p_l(0) |
| { |
| __try |
| { |
| for (const_iterator it = other.begin(); it != other.end(); ++it) |
| { |
| entry_pointer p_l = allocate_new_entry(*it, |
| traits_base::m_no_throw_copies_indicator); |
| p_l->m_p_next = m_p_l; |
| m_p_l = p_l; |
| } |
| } |
| __catch(...) |
| { |
| deallocate_all(); |
| __throw_exception_again; |
| } |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| 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) |
| _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) |
| std::swap(m_p_l, other.m_p_l); |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| deallocate_all() |
| { |
| entry_pointer p_l = m_p_l; |
| while (p_l != 0) |
| { |
| entry_pointer p_next_l = p_l->m_p_next; |
| actual_erase_entry(p_l); |
| p_l = p_next_l; |
| } |
| m_p_l = 0; |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| ~PB_DS_LU_NAME() |
| { deallocate_all(); } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp |
|---|
| 0,0 → 1,57 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_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 |
| { |
| size_type calc_size = 0; |
| for (const_iterator it = begin(); it != end(); ++it) |
| { |
| debug_base::check_key_exists(PB_DS_V2F(*it), __file, __line); |
| ++calc_size; |
| } |
| debug_base::check_size(calc_size, __file, __line); |
| } |
| #endif |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp |
|---|
| 0,0 → 1,60 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/entry_metadata_base.hpp |
| * Contains an implementation for a list update map. |
| */ |
| #ifndef PB_DS_LU_MAP_ENTRY_METADATA_BASE_HPP |
| #define PB_DS_LU_MAP_ENTRY_METADATA_BASE_HPP |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| template<typename Metadata> |
| struct lu_map_entry_metadata_base |
| { |
| Metadata m_update_metadata; |
| }; |
| template<> |
| struct lu_map_entry_metadata_base<null_type> |
| { }; |
| } // namespace detail |
| } // namespace __gnu_pbds |
| #endif |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp |
|---|
| 0,0 → 1,134 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/erase_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| erase(key_const_reference r_key) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| if (m_p_l == 0) |
| return false; |
| if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value))) |
| { |
| entry_pointer p_next = m_p_l->m_p_next; |
| actual_erase_entry(m_p_l); |
| m_p_l = p_next; |
| return true; |
| } |
| entry_pointer p_l = m_p_l; |
| while (p_l->m_p_next != 0) |
| if (s_eq_fn(r_key, PB_DS_V2F(p_l->m_p_next->m_value))) |
| { |
| erase_next(p_l); |
| return true; |
| } |
| else |
| p_l = p_l->m_p_next; |
| return false; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| clear() |
| { |
| deallocate_all(); |
| } |
| 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) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| size_type num_ersd = 0; |
| while (m_p_l != 0 && pred(m_p_l->m_value)) |
| { |
| entry_pointer p_next = m_p_l->m_p_next; |
| ++num_ersd; |
| actual_erase_entry(m_p_l); |
| m_p_l = p_next; |
| } |
| if (m_p_l == 0) |
| return num_ersd; |
| entry_pointer p_l = m_p_l; |
| while (p_l->m_p_next != 0) |
| { |
| if (pred(p_l->m_p_next->m_value)) |
| { |
| ++num_ersd; |
| erase_next(p_l); |
| } |
| else |
| p_l = p_l->m_p_next; |
| } |
| PB_DS_ASSERT_VALID((*this)) |
| return num_ersd; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| erase_next(entry_pointer p_l) |
| { |
| _GLIBCXX_DEBUG_ASSERT(p_l != 0); |
| _GLIBCXX_DEBUG_ASSERT(p_l->m_p_next != 0); |
| entry_pointer p_next_l = p_l->m_p_next->m_p_next; |
| actual_erase_entry(p_l->m_p_next); |
| p_l->m_p_next = p_next_l; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| actual_erase_entry(entry_pointer p_l) |
| { |
| _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(p_l->m_value));) |
| p_l->~entry(); |
| s_entry_allocator.deallocate(p_l, 1); |
| } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp |
|---|
| 0,0 → 1,90 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/find_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::entry_pointer |
| PB_DS_CLASS_C_DEC:: |
| find_imp(key_const_reference r_key) const |
| { |
| if (m_p_l == 0) |
| return 0; |
| if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value))) |
| { |
| apply_update(m_p_l, s_metadata_type_indicator); |
| PB_DS_CHECK_KEY_EXISTS(r_key) |
| return m_p_l; |
| } |
| entry_pointer p_l = m_p_l; |
| while (p_l->m_p_next != 0) |
| { |
| entry_pointer p_next = p_l->m_p_next; |
| if (s_eq_fn(r_key, PB_DS_V2F(p_next->m_value))) |
| { |
| if (apply_update(p_next, s_metadata_type_indicator)) |
| { |
| p_l->m_p_next = p_next->m_p_next; |
| p_next->m_p_next = m_p_l; |
| m_p_l = p_next; |
| return m_p_l; |
| } |
| return p_next; |
| } |
| else |
| p_l = p_next; |
| } |
| PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) |
| return 0; |
| } |
| PB_DS_CLASS_T_DEC |
| template<typename Metadata> |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| apply_update(entry_pointer p_l, type_to_type<Metadata>) |
| { return s_update_policy(p_l->m_update_metadata); } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| apply_update(entry_pointer, type_to_type<null_type>) |
| { return s_update_policy(s_null_type); } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp |
|---|
| 0,0 → 1,57 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/info_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| size() const |
| { return std::distance(begin(), end()); } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| max_size() const |
| { return s_entry_allocator.max_size(); } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| empty() const |
| { return (m_p_l == 0); } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp |
|---|
| 0,0 → 1,106 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/insert_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline std::pair< |
| typename PB_DS_CLASS_C_DEC::point_iterator, |
| bool> |
| PB_DS_CLASS_C_DEC:: |
| insert(const_reference r_val) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| entry_pointer p_l = find_imp(PB_DS_V2F(r_val)); |
| if (p_l != 0) |
| { |
| PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val)) |
| return std::make_pair(point_iterator(&p_l->m_value), false); |
| } |
| PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val)) |
| p_l = allocate_new_entry(r_val, traits_base::m_no_throw_copies_indicator); |
| p_l->m_p_next = m_p_l; |
| m_p_l = p_l; |
| PB_DS_ASSERT_VALID((*this)) |
| return std::make_pair(point_iterator(&p_l->m_value), true); |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::entry_pointer |
| PB_DS_CLASS_C_DEC:: |
| allocate_new_entry(const_reference r_val, false_type) |
| { |
| entry_pointer p_l = s_entry_allocator.allocate(1); |
| cond_dealtor_t cond(p_l); |
| new (const_cast<void* >(static_cast<const void* >(&p_l->m_value))) |
| value_type(r_val); |
| cond.set_no_action(); |
| _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
| init_entry_metadata(p_l, s_metadata_type_indicator); |
| return p_l; |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::entry_pointer |
| PB_DS_CLASS_C_DEC:: |
| allocate_new_entry(const_reference r_val, true_type) |
| { |
| entry_pointer p_l = s_entry_allocator.allocate(1); |
| new (&p_l->m_value) value_type(r_val); |
| _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
| init_entry_metadata(p_l, s_metadata_type_indicator); |
| return p_l; |
| } |
| PB_DS_CLASS_T_DEC |
| template<typename Metadata> |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| init_entry_metadata(entry_pointer p_l, type_to_type<Metadata>) |
| { new (&p_l->m_update_metadata) Metadata(s_update_policy()); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| init_entry_metadata(entry_pointer, type_to_type<null_type>) |
| { } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp |
|---|
| 0,0 → 1,80 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/iterators_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::iterator |
| PB_DS_CLASS_C_DEC:: |
| begin() |
| { |
| if (m_p_l == 0) |
| { |
| _GLIBCXX_DEBUG_ASSERT(empty()); |
| return end(); |
| } |
| return iterator(&m_p_l->m_value, m_p_l, this); |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::const_iterator |
| PB_DS_CLASS_C_DEC:: |
| begin() const |
| { |
| if (m_p_l == 0) |
| { |
| _GLIBCXX_DEBUG_ASSERT(empty()); |
| return end(); |
| } |
| return iterator(&m_p_l->m_value, m_p_l, const_cast<PB_DS_CLASS_C_DEC* >(this)); |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::iterator |
| PB_DS_CLASS_C_DEC:: |
| end() |
| { return iterator(0, 0, this); } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::const_iterator |
| PB_DS_CLASS_C_DEC:: |
| end() const |
| { |
| return const_iterator(0, 0, const_cast<PB_DS_CLASS_C_DEC* const>(this)); |
| } |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp |
|---|
| 0,0 → 1,343 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/lu_map_.hpp |
| * Contains a list update 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/types_traits.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp> |
| #include <ext/pb_ds/exception.hpp> |
| #ifdef _GLIBCXX_DEBUG |
| #include <ext/pb_ds/detail/debug_map_base.hpp> |
| #endif |
| #ifdef PB_DS_LU_MAP_TRACE_ |
| #include <iostream> |
| #endif |
| #include <debug/debug.h> |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| #ifdef PB_DS_DATA_TRUE_INDICATOR |
| #define PB_DS_LU_NAME lu_map |
| #endif |
| #ifdef PB_DS_DATA_FALSE_INDICATOR |
| #define PB_DS_LU_NAME lu_set |
| #endif |
| #define PB_DS_CLASS_T_DEC \ |
| template<typename Key, typename Mapped, typename Eq_Fn, \ |
| typename _Alloc, typename Update_Policy> |
| #define PB_DS_CLASS_C_DEC \ |
| PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy> |
| #define PB_DS_LU_TRAITS_BASE \ |
| types_traits<Key, Mapped, _Alloc, false> |
| #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 |
| /// list-based (with updates) associative container. |
| /// Skip to the lu, my darling. |
| template<typename Key, |
| typename Mapped, |
| typename Eq_Fn, |
| typename _Alloc, |
| typename Update_Policy> |
| class PB_DS_LU_NAME : |
| #ifdef _GLIBCXX_DEBUG |
| protected PB_DS_DEBUG_MAP_BASE_C_DEC, |
| #endif |
| public PB_DS_LU_TRAITS_BASE |
| { |
| private: |
| typedef PB_DS_LU_TRAITS_BASE traits_base; |
| struct entry |
| : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> |
| { |
| typename traits_base::value_type m_value; |
| typename _Alloc::template rebind<entry>::other::pointer m_p_next; |
| }; |
| 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 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_; |
| #define PB_DS_GEN_POS entry_pointer |
| #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 |
| #ifdef _GLIBCXX_DEBUG |
| typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
| #endif |
| typedef cond_dealtor<entry, _Alloc> cond_dealtor_t; |
| public: |
| typedef _Alloc allocator_type; |
| typedef typename _Alloc::size_type size_type; |
| typedef typename _Alloc::difference_type difference_type; |
| typedef Eq_Fn eq_fn; |
| typedef Update_Policy update_policy; |
| typedef typename Update_Policy::metadata_type update_metadata; |
| 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; |
| public: |
| PB_DS_LU_NAME(); |
| PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&); |
| virtual |
| ~PB_DS_LU_NAME(); |
| template<typename It> |
| PB_DS_LU_NAME(It, It); |
| void |
| swap(PB_DS_CLASS_C_DEC&); |
| inline size_type |
| size() const; |
| inline size_type |
| max_size() const; |
| inline bool |
| empty() const; |
| inline mapped_reference |
| operator[](key_const_reference r_key) |
| { |
| #ifdef PB_DS_DATA_TRUE_INDICATOR |
| _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
| return insert(std::make_pair(r_key, mapped_type())).first->second; |
| #else |
| insert(r_key); |
| return traits_base::s_null_type; |
| #endif |
| } |
| inline std::pair<point_iterator, bool> |
| insert(const_reference); |
| inline point_iterator |
| find(key_const_reference r_key) |
| { |
| _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
| entry_pointer p_e = find_imp(r_key); |
| return point_iterator(p_e == 0 ? 0: &p_e->m_value); |
| } |
| inline point_const_iterator |
| find(key_const_reference r_key) const |
| { |
| _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
| entry_pointer p_e = find_imp(r_key); |
| return point_const_iterator(p_e == 0 ? 0: &p_e->m_value); |
| } |
| 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* file, int line) const; |
| #endif |
| #ifdef PB_DS_LU_MAP_TRACE_ |
| void |
| trace() const; |
| #endif |
| protected: |
| template<typename It> |
| void |
| copy_from_range(It, It); |
| private: |
| #ifdef PB_DS_DATA_TRUE_INDICATOR |
| friend class iterator_; |
| #endif |
| friend class const_iterator_; |
| inline entry_pointer |
| allocate_new_entry(const_reference, false_type); |
| inline entry_pointer |
| allocate_new_entry(const_reference, true_type); |
| template<typename Metadata> |
| inline static void |
| init_entry_metadata(entry_pointer, type_to_type<Metadata>); |
| inline static void |
| init_entry_metadata(entry_pointer, type_to_type<null_type>); |
| void |
| deallocate_all(); |
| void |
| erase_next(entry_pointer); |
| void |
| actual_erase_entry(entry_pointer); |
| void |
| inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const |
| { |
| r_pos = r_pos->m_p_next; |
| r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value; |
| } |
| template<typename Metadata> |
| inline static bool |
| apply_update(entry_pointer, type_to_type<Metadata>); |
| inline static bool |
| apply_update(entry_pointer, type_to_type<null_type>); |
| inline entry_pointer |
| find_imp(key_const_reference) const; |
| static entry_allocator s_entry_allocator; |
| static Eq_Fn s_eq_fn; |
| static Update_Policy s_update_policy; |
| static type_to_type<update_metadata> s_metadata_type_indicator; |
| static null_type s_null_type; |
| mutable entry_pointer m_p_l; |
| }; |
| #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp> |
| #include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp> |
| #undef PB_DS_CLASS_T_DEC |
| #undef PB_DS_CLASS_C_DEC |
| #undef PB_DS_LU_TRAITS_BASE |
| #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
| #undef PB_DS_LU_NAME |
| } // namespace detail |
| } // namespace __gnu_pbds |
| /contrib/toolchain/gcc/5x/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp |
|---|
| 0,0 → 1,59 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2015 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 list_update_map_/trace_fn_imps.hpp |
| * Contains implementations of lu_map_. |
| */ |
| #ifdef PB_DS_LU_MAP_TRACE_ |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| trace() const |
| { |
| std::cerr << m_p_l << std::endl << std::endl; |
| const_entry_pointer p_l = m_p_l; |
| while (p_l != 0) |
| { |
| std::cerr << PB_DS_V2F(p_l->m_value) << std::endl; |
| p_l = p_l->m_p_next; |
| } |
| std::cerr << std::endl; |
| } |
| #endif |