diff options
Diffstat (limited to 'libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_')
11 files changed, 0 insertions, 1923 deletions
diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp deleted file mode 100644 index aa3e65ded93..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp +++ /dev/null @@ -1,88 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file cond_dtor.hpp - * Contains a conditional destructor - */ - -class cond_dtor -{ -public: - cond_dtor(pointer a_vec, iterator& r_last_it, size_type total_size) : m_a_vec(a_vec), - m_r_last_it(r_last_it), - m_max_size(total_size), - m_no_action(false) - { } - - ~cond_dtor() - { - if (m_no_action) - return; - - iterator it = m_a_vec; - - while (it != m_r_last_it) - { - it->~value_type(); - - ++it; - } - - if (m_max_size > 0) - value_allocator().deallocate( - const_cast<typename value_allocator::pointer>(m_a_vec), - m_max_size); - } - - inline void - set_no_action() - { - m_no_action = true; - } - -protected: - pointer m_a_vec; - - iterator& m_r_last_it; - - const size_type m_max_size; - - bool m_no_action; -}; diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp deleted file mode 100644 index 3285cfbbd57..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp +++ /dev/null @@ -1,278 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file constructors_destructor_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - -PB_ASSOC_CLASS_T_DEC -typename PB_ASSOC_CLASS_C_DEC::value_allocator -PB_ASSOC_CLASS_C_DEC::s_alloc; - -PB_ASSOC_CLASS_T_DEC -PB_ASSOC_CLASS_C_DEC:: -PB_ASSOC_OV_TREE_CLASS_NAME() : - m_a_values(NULL), - m_end_it(NULL), - m_size(0) -{ - update(node_begin(), (Node_Updator* )this); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -PB_ASSOC_CLASS_C_DEC:: -PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : - my_cmp_fn_base(r_cmp_fn), - m_a_values(NULL), - m_end_it(NULL), - m_size(0) -{ - update(node_begin(), (Node_Updator* )this); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -PB_ASSOC_CLASS_C_DEC:: -PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator) : - my_cmp_fn_base(r_cmp_fn), - Node_Updator(r_node_updator), - m_a_values(NULL), - m_end_it(NULL), - m_size(0) -{ - update(node_begin(), (Node_Updator* )this); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -PB_ASSOC_CLASS_C_DEC:: -PB_ASSOC_OV_TREE_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other) : - my_cmp_fn_base(r_other), - m_a_values(NULL), - m_end_it(NULL), - m_size(0) -{ - copy_from_ordered_range(r_other.begin(), r_other.end()); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -template<class It> -inline void -PB_ASSOC_CLASS_C_DEC:: -copy_from_range(It first_it, It last_it) -{ - enum - { - is_set_type = is_same_type<Data, null_data_type>::value - }; - - typedef - typename cond_type< - is_set_type, - std::set< - Key, - Cmp_Fn, - typename Allocator::template rebind< - Key>::other>, - std::map< - Key, - Data, - Cmp_Fn, - typename Allocator::template rebind< - std::pair<const Key, Data> >::other> >::type - map_type; - - map_type m(first_it, last_it); - - copy_from_ordered_range(m.begin(), m.end()); -} - -PB_ASSOC_CLASS_T_DEC -template<class It> -void -PB_ASSOC_CLASS_C_DEC:: -copy_from_ordered_range(It first_it, It last_it) -{ - clear(); - - const size_type size = std::distance(first_it, last_it); - - pointer a_values = s_alloc.allocate(size); - - iterator target_it = a_values; - It source_it = first_it; - It source_end_it = last_it; - - cond_dtor cd(a_values, target_it, size); - - while (source_it != source_end_it) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it++); - - ++target_it; - } - - cd.set_no_action(); - - m_a_values = a_values; - - m_size = size; - - m_end_it = m_a_values + m_size; - - update(node_begin(), (Node_Updator* )this); - -#ifdef PB_ASSOC_OV_TREE_DEBUG_ - const_iterator dbg_it = m_a_values; - - while (dbg_it != m_end_it) - { - my_map_debug_base::insert_new(PB_ASSOC_V2F(*dbg_it)); - - dbg_it++; - } - - PB_ASSOC_CLASS_C_DEC::assert_valid(); -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ -} - -PB_ASSOC_CLASS_T_DEC -template<class It> -void -PB_ASSOC_CLASS_C_DEC:: -copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it) -{ - clear(); - - const size_type size = - std::distance(first_it, last_it) + - std::distance(other_first_it, other_last_it); - - pointer a_values = s_alloc.allocate(size); - - iterator target_it = a_values; - It source_it = first_it; - It source_end_it = last_it; - - cond_dtor cd(a_values, target_it, size); - - while (source_it != source_end_it) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it++); - - ++target_it; - } - - source_it = other_first_it; - source_end_it = other_last_it; - - while (source_it != source_end_it) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it++); - - ++target_it; - } - - cd.set_no_action(); - - m_a_values = a_values; - - m_size = size; - - m_end_it = m_a_values + m_size; - - update(node_begin(), (Node_Updator* )this); - -#ifdef PB_ASSOC_OV_TREE_DEBUG_ - const_iterator dbg_it = m_a_values; - - while (dbg_it != m_end_it) - { - my_map_debug_base::insert_new(PB_ASSOC_V2F(*dbg_it)); - - dbg_it++; - } - - PB_ASSOC_CLASS_C_DEC::assert_valid(); -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ -} - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -swap(PB_ASSOC_CLASS_C_DEC& r_other) -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - - std::swap(m_a_values, r_other.m_a_values); - - std::swap(m_size, r_other.m_size); - - std::swap(m_end_it, r_other.m_end_it); - - std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )r_other); - - Node_Updator::swap(r_other); - - PB_ASSOC_DBG_ONLY(my_map_debug_base::swap(r_other);) - - PB_ASSOC_DBG_ONLY(assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -PB_ASSOC_CLASS_C_DEC:: -~PB_ASSOC_OV_TREE_CLASS_NAME() -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - - cond_dtor cd(m_a_values, m_end_it, m_size); -} diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp deleted file mode 100644 index 156c540540c..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp +++ /dev/null @@ -1,101 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file debug_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - -#ifdef PB_ASSOC_OV_TREE_DEBUG_ - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -assert_valid() const -{ - if (m_a_mapped_values == NULL || m_end_it == NULL || m_size == 0) - PB_ASSOC_DBG_ASSERT(m_a_mapped_values == NULL&& m_end_it == NULL&& - m_size == 0); - - assert_iterators(); -} - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -assert_iterators() const -{ - my_map_debug_base::check_size(m_size); - - size_type iterated_num = 0; - - const_iterator prev_it = end(); - - PB_ASSOC_DBG_ASSERT( m_end_it == m_a_mapped_values + m_size); - - for (const_iterator it = begin(); it != end(); ++it) - { - ++iterated_num; - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists( - PB_ASSOC_V2F(*it))); - - PB_ASSOC_DBG_ASSERT(lower_bound( - PB_ASSOC_V2F(*it)) == it); - - const_iterator upper_bound_it = upper_bound( - PB_ASSOC_V2F(*it)); - - --upper_bound_it; - - PB_ASSOC_DBG_ASSERT(upper_bound_it == it); - - if (prev_it != end()) - PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()( - PB_ASSOC_V2F(*prev_it), - PB_ASSOC_V2F(*it))); - - prev_it = it; - } - - PB_ASSOC_DBG_ASSERT(iterated_num == m_size); -} - -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp deleted file mode 100644 index d1bbe6cc197..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp +++ /dev/null @@ -1,234 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file erase_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - -PB_ASSOC_CLASS_T_DEC -inline typename PB_ASSOC_CLASS_C_DEC::size_type -PB_ASSOC_CLASS_C_DEC:: -erase(const_key_reference r_key) -{ - iterator it = find(r_key); - - if (it == find_end()) - return (0); - - erase(it); - - return (1); -} - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -clear() -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - - if (m_size == 0) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - return; - } - else - { - cond_dtor cd(m_a_values, m_end_it, m_size); - } - - PB_ASSOC_DBG_ONLY(my_map_debug_base::clear();) - - m_a_values = NULL; - - m_size = 0; - - m_end_it = m_a_values; - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - - PB_ASSOC_DBG_ONLY(assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -template<class Pred> -inline typename PB_ASSOC_CLASS_C_DEC::size_type -PB_ASSOC_CLASS_C_DEC:: -erase_if(Pred pred) -{ - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - -#ifdef PB_ASSOC_BASIC_REGRESSION - throw_prob_adjustor adjust(m_size); -#endif // #ifdef PB_ASSOC_BASIC_REGRESSION - - size_type new_size = 0; - - size_type num_val_ersd = 0; - - iterator source_it = m_a_values; - - for (source_it = begin(); source_it != m_end_it; ++source_it) - { - if (pred(*source_it)) - ++num_val_ersd; - else - ++new_size; - } - - if (new_size == 0) - { - clear(); - - return (num_val_ersd); - } - - pointer a_new_values = s_alloc.allocate(new_size); - - iterator target_it = a_new_values; - - cond_dtor cd(a_new_values, target_it, new_size); - - PB_ASSOC_DBG_ONLY(my_map_debug_base::clear()); - - for (source_it = begin(); source_it != m_end_it; ++source_it) - { - if (!pred(*source_it)) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it); - - PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new( - PB_ASSOC_V2F(*source_it))); - - ++target_it; - } - } - - cd.set_no_action(); - - { - cond_dtor cd1(m_a_values, m_end_it, m_size); - } - - m_a_values = a_new_values; - - m_size = new_size; - - m_end_it = target_it; - - PB_ASSOC_DBG_ONLY(assert_valid();) - - return (num_val_ersd); -} - -PB_ASSOC_CLASS_T_DEC -template<class It> -It -PB_ASSOC_CLASS_C_DEC:: -erase(It it) -{ - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - - if (it == end()) - return end(); - - PB_ASSOC_DBG_ONLY( - PB_ASSOC_CLASS_C_DEC::check_key_exists(PB_ASSOC_V2F(*it));) - -#ifdef PB_ASSOC_BASIC_REGRESSION - throw_prob_adjustor adjust(m_size); -#endif // #ifdef PB_ASSOC_BASIC_REGRESSION - - PB_ASSOC_DBG_ASSERT(m_size > 0); - - pointer a_values = s_alloc.allocate(m_size - 1); - - iterator source_it = begin(); - iterator source_end_it = end(); - iterator target_it = a_values; - iterator ret_it = end(); - - cond_dtor cd(a_values, target_it, m_size - 1); - - PB_ASSOC_DBG_ONLY(size_type cnt = 0;) - - while (source_it != source_end_it) - { - if (source_it != it) - { - PB_ASSOC_DBG_ONLY(++cnt;) - PB_ASSOC_DBG_ASSERT(cnt != m_size); - - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it); - - ++target_it; - } - else - ret_it = target_it; - - ++source_it; - } - - cd.set_no_action(); - - PB_ASSOC_DBG_ONLY( - PB_ASSOC_CLASS_C_DEC::erase_existing(PB_ASSOC_V2F(*it));) - { - cond_dtor cd1(m_a_values, m_end_it, m_size); - } - - m_a_values = a_values; - - --m_size; - - m_end_it = m_a_values + m_size; - - update(node_begin(), (Node_Updator* )this); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - - return (It(ret_it)); -} - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp deleted file mode 100644 index 1615546a412..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp +++ /dev/null @@ -1,44 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file find_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp deleted file mode 100644 index 11ccd3e80e1..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp +++ /dev/null @@ -1,95 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file info_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - -PB_ASSOC_CLASS_T_DEC -bool -PB_ASSOC_CLASS_C_DEC:: -cmp_with_other(const PB_ASSOC_CLASS_C_DEC& r_other) const -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - - if (size() != r_other.size()) - return (false); - - const_iterator other_it = r_other.begin(); - const_iterator it = begin(); - - while (it != end()) - { - if (*it !=* other_it) - return (false); - - ++it; - - ++other_it; - } - - return (true); -} - -PB_ASSOC_CLASS_T_DEC -inline typename PB_ASSOC_CLASS_C_DEC::size_type -PB_ASSOC_CLASS_C_DEC:: -size() const -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - - return (m_size); -} - -PB_ASSOC_CLASS_T_DEC -inline typename PB_ASSOC_CLASS_C_DEC::size_type -PB_ASSOC_CLASS_C_DEC:: -max_size() const -{ - return (s_alloc.max_size()); -} - -PB_ASSOC_CLASS_T_DEC -inline bool -PB_ASSOC_CLASS_C_DEC:: -empty() const -{ - return (size() == 0); -} diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp deleted file mode 100644 index 072eb0fa6b3..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp +++ /dev/null @@ -1,44 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file insert_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp deleted file mode 100644 index 8705b09744a..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp +++ /dev/null @@ -1,44 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file iterators_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp deleted file mode 100644 index 9ec3cd9d7d1..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp +++ /dev/null @@ -1,178 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file node_iterators.hpp - * Contains an implementation class for ov_tree_. - */ - -class const_node_iterator -{ - -public: - - typedef trivial_iterator_tag iterator_category; - - typedef trivial_iterator_difference_type difference_type; - - typedef const_iterator value_type; - - typedef const_iterator* pointer; - - typedef const_iterator* const_pointer; - - typedef const_iterator& reference; - - typedef const iterator& const_reference; - -public: - inline - const_node_iterator(value_pointer p_nd = NULL, value_pointer p_begin_nd = NULL, value_pointer p_end_nd = NULL) : m_p_value(p_nd), - m_p_begin_value(p_begin_nd), - m_p_end_value(p_end_nd) - { } - - inline const_iterator - operator*() const - { - return (m_p_value); - } - - inline const_node_iterator - l_child() const - { - if (m_p_begin_value == m_p_value) - return (const_node_iterator(m_p_begin_value, m_p_begin_value, m_p_begin_value)); - - return (const_node_iterator( - mid_pointer(m_p_begin_value, m_p_value), - m_p_begin_value, - m_p_value)); - } - - inline const_node_iterator - r_child() const - { - if (m_p_value == m_p_end_value) - return (const_node_iterator(m_p_end_value, m_p_end_value, m_p_end_value)); - - return (const_node_iterator( - mid_pointer(m_p_value + 1, m_p_end_value), - m_p_value + 1, - m_p_end_value)); - } - - inline bool - operator==(const const_node_iterator& r_other) const - { - const bool is_end = m_p_begin_value == m_p_end_value; - const bool is_other_end = r_other.m_p_begin_value == r_other.m_p_end_value; - - if (is_end) - return (is_other_end); - - if (is_other_end) - return (is_end); - - if (r_other.m_p_begin_value == r_other.m_p_end_value) - return (m_p_begin_value == m_p_end_value); - - return (m_p_value == r_other.m_p_value); - } - - inline bool - operator!=(const const_node_iterator& r_other) const - { - return (!operator==(r_other)); - } - -private: - friend class PB_ASSOC_CLASS_C_DEC; - -public: - value_pointer m_p_value; - value_pointer m_p_begin_value; - value_pointer m_p_end_value; -}; - -class node_iterator : - public const_node_iterator - -{ - -public: - inline - node_iterator(value_pointer p_nd = NULL, value_pointer p_begin_nd = NULL, value_pointer p_end_nd = NULL) : const_node_iterator(p_nd, p_begin_nd, p_end_nd) - { } - - inline iterator - operator*() const - { - return (iterator(const_node_iterator::m_p_value)); - } - - inline node_iterator - l_child() const - { - if (const_node_iterator::m_p_begin_value == const_node_iterator::m_p_value) - return (node_iterator(const_node_iterator::m_p_begin_value, const_node_iterator::m_p_begin_value, const_node_iterator::m_p_begin_value)); - - return (node_iterator( - mid_pointer(const_node_iterator::m_p_begin_value, const_node_iterator::m_p_value), - const_node_iterator::m_p_begin_value, - const_node_iterator::m_p_value)); - } - - inline node_iterator - r_child() const - { - if (const_node_iterator::m_p_value == const_node_iterator::m_p_end_value) - return (node_iterator(const_node_iterator::m_p_end_value, const_node_iterator::m_p_end_value, const_node_iterator::m_p_end_value)); - - return (node_iterator( - mid_pointer(const_node_iterator::m_p_value + 1, const_node_iterator::m_p_end_value), - const_node_iterator::m_p_value + 1, - const_node_iterator::m_p_end_value)); - } - -private: - - friend class PB_ASSOC_CLASS_C_DEC; -}; - diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/ov_tree_map_.hpp deleted file mode 100644 index 94ff223a734..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/ov_tree_map_.hpp +++ /dev/null @@ -1,628 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file ov_tree_map_.hpp - * Contains an implementation class for ov_tree_. - */ - -#include <map> -#include <set> -#include <ext/pb_assoc/trivial_iterator_def.hpp> -#include <ext/pb_assoc/tree_policy.hpp> -#include <ext/pb_assoc/detail/eq_fn/eq_by_less.hpp> -#include <ext/pb_assoc/detail/types_traits.hpp> -#include <ext/pb_assoc/detail/map_debug_base.hpp> -#include <ext/pb_assoc/detail/type_utils.hpp> -#include <ext/pb_assoc/exception.hpp> -#include <utility> -#include <functional> -#include <algorithm> -#include <vector> -#include <cassert> -#ifdef PB_ASSOC_BASIC_REGRESSION -#include <pb_assoc/testsuite/regression/basic_test/throw_prob_adjustor.hpp> -#endif // #ifdef PB_ASSOC_BASIC_REGRESSION - -namespace pb_assoc -{ - - namespace detail - { - -#ifdef PB_ASSOC_OV_TREE_DEBUG_ -#define PB_ASSOC_DBG_ASSERT(X) assert(X); -#define PB_ASSOC_DBG_VERIFY(X) PB_ASSOC_DBG_ASSERT(X) -#define PB_ASSOC_DBG_ONLY(X) X -#else // #ifdef PB_ASSOC_OV_TREE_DEBUG_ -#define PB_ASSOC_DBG_ASSERT(X) ((void)0) -#define PB_ASSOC_DBG_VERIFY(X) X -#define PB_ASSOC_DBG_ONLY(X) ; -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ - -#define PB_ASSOC_CLASS_T_DEC \ - template< \ - typename Key, \ - typename Data, \ - class Cmp_Fn, \ - class Allocator, \ - class Node_Updator> - -#ifdef PB_ASSOC_DATA_TRUE_INDICATOR -#define PB_ASSOC_OV_TREE_CLASS_NAME \ - ov_tree_data_ -#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR - -#ifdef PB_ASSOC_DATA_FALSE_INDICATOR -#define PB_ASSOC_OV_TREE_CLASS_NAME \ - ov_tree_no_data_ -#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR - -#define PB_ASSOC_CLASS_C_DEC \ - PB_ASSOC_OV_TREE_CLASS_NAME< \ - Key, \ - Data, \ - Cmp_Fn, \ - Allocator, \ - Node_Updator> - -#define PB_ASSOC_TYPES_TRAITS_C_DEC \ - types_traits< \ - Key, \ - Data, \ - Allocator> - -#ifdef PB_ASSOC_USE_MAP_DEBUG_BASE -#define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \ - pb_assoc::detail::map_debug_base< \ - Key, \ - eq_by_less<Key, Cmp_Fn> > -#endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE - -#ifdef PB_ASSOC_DATA_TRUE_INDICATOR -#define PB_ASSOC_V2F(X) (X).first -#define PB_ASSOC_V2S(X) (X).second -#define PB_ASSOC_EP2VP(X)& ((X)->m_value) -#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR - -#ifdef PB_ASSOC_DATA_FALSE_INDICATOR -#define PB_ASSOC_V2F(X) (X) -#define PB_ASSOC_V2S(X) Mapped_Data() -#define PB_ASSOC_EP2VP(X)& ((X)->m_value.first) -#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR - - template<typename Key, - typename Data, - class Cmp_Fn, - class Allocator, - class Node_Updator> - class PB_ASSOC_OV_TREE_CLASS_NAME : -#ifdef PB_ASSOC_OV_TREE_DEBUG_ - protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC, -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ - public Cmp_Fn, - public PB_ASSOC_TYPES_TRAITS_C_DEC, - public Node_Updator - { - - protected: - - typedef typename Allocator::size_type size_type; - - typedef typename Allocator::difference_type difference_type; - - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference - const_key_reference; - - typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type; - - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference - data_reference; - - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference - const_data_reference; - - typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type; - - typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer; - - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer - const_pointer; - - typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference; - - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference - const_reference; - - typedef const_pointer const_find_iterator; - - typedef pointer find_iterator; - - typedef const_find_iterator const_iterator; - - typedef find_iterator iterator; - - typedef pointer value_pointer; - -#include <ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp> - -#include <ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp> - - typedef Cmp_Fn cmp_fn; - - typedef Allocator allocator; - - typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base; - - typedef cmp_fn my_cmp_fn_base; - -#ifdef PB_ASSOC_USE_MAP_DEBUG_BASE - typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base; -#endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE - - protected: - - PB_ASSOC_OV_TREE_CLASS_NAME(); - - PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn); - - PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator); - - PB_ASSOC_OV_TREE_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other); - - ~PB_ASSOC_OV_TREE_CLASS_NAME(); - - void - swap(PB_ASSOC_CLASS_C_DEC& r_other); - - template<class It> - void - copy_from_range(It first_it, It last_it); - - template<class Node_Updator_> - void - update(node_iterator it, Node_Updator_* p_updator) - { - if (it == node_end()) - return; - - update(it.l_child(), p_updator); - update(it.r_child(), p_updator); - - p_updator->operator()(it.m_p_value,(it.l_child() == node_end())? NULL : it.l_child().m_p_value,(it.r_child() == node_end())? NULL : it.r_child().m_p_value); - } - - inline void - update(node_iterator /*it*/, pb_assoc::null_node_updator* ) - { } - - bool - cmp_with_other(const PB_ASSOC_CLASS_C_DEC& r_other) const; - - inline size_type - max_size() const; - - inline bool - empty() const; - - inline size_type - size() const; - - Cmp_Fn& - get_cmp_fn(); - - const Cmp_Fn& - get_cmp_fn() const; - -#ifdef PB_ASSOC_DATA_TRUE_INDICATOR - inline data_reference - subscript_imp(const_key_reference r_key) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - find_iterator it = lower_bound(r_key); - - if (it != find_end()&& !Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*it))) - { - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key)); - - PB_ASSOC_DBG_ONLY(assert_valid();) - - return (it->second); - } - - PB_ASSOC_DBG_ONLY(assert_valid();) - - return (insert_new_val(it, - std::make_pair(r_key, data_type()))->second); - } - - inline const_data_reference - subscript_imp(const_key_reference r_key) const - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key)); - - find_iterator it = lower_bound(r_key); - - PB_ASSOC_DBG_ASSERT(it != find_end()); - - return (it->second); - } -#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR - - inline std::pair<find_iterator, bool> - insert(const_reference r_value) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - const_key_reference r_key = PB_ASSOC_V2F(r_value); - - find_iterator it = lower_bound(r_key); - - if (it != find_end()&& !Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*it))) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key)); - - return (std::make_pair(it, false)); - } - - PB_ASSOC_DBG_ONLY(assert_valid();) - - return (std::make_pair(insert_new_val(it, r_value), true)); - } - - inline static pointer - mid_pointer(pointer p_begin, pointer p_end) - { - PB_ASSOC_DBG_ASSERT(p_end >= p_begin); - - return (p_begin + (p_end - p_begin) / 2); - } - - inline find_iterator - lower_bound(const_key_reference r_key) - { - pointer it = m_a_values; - - difference_type dist = m_size; - - while (dist > 0) - { - const difference_type mid_dist = dist >> 1; - - pointer mid_it = it + mid_dist; - - if (my_cmp_fn_base::operator()( - PB_ASSOC_V2F(*(it + mid_dist)), - r_key)) - { - it = ++mid_it; - - dist -= mid_dist + 1; - } - else - dist = mid_dist; - } - - return (it); - } - - inline const_find_iterator - lower_bound(const_key_reference r_key) const - { - return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).lower_bound(r_key)); - } - - inline find_iterator - upper_bound(const_key_reference r_key) - { - iterator pot_it = lower_bound(r_key); - - if (pot_it != find_end()&& !Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*pot_it))) - { - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key)); - - return (++pot_it); - } - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key)); - - return (pot_it); - } - - inline const_find_iterator - upper_bound(const_key_reference r_key) const - { - return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).upper_bound(r_key)); - } - - inline find_iterator - find(const_key_reference r_key) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - - iterator pot_it = lower_bound(r_key); - - if (pot_it != find_end()&& !Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*pot_it))) - { - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key)); - - return (pot_it); - } - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key)); - - return (find_end()); - } - - inline const_find_iterator - find(const_key_reference r_key) const - { - return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).find(r_key)); - } - - inline size_type - erase(const_key_reference r_key); - - template<class Pred> - inline size_type - erase_if(Pred pred); - - template<class It> - inline It - erase(It it); - - void - clear(); - - void - join(PB_ASSOC_CLASS_C_DEC& r_other); - - void - split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other); - - inline iterator - begin() - { - return (m_a_values); - } - - inline const_iterator - begin() const - { - return (m_a_values); - } - - inline iterator - find_end() - { - return (end()); - } - - inline const_iterator - find_end() const - { - return (end()); - } - - inline iterator - end() - { - return (m_end_it); - } - - inline const_iterator - end() const - { - return (m_end_it); - } - - inline const_node_iterator - node_begin() const - { - return (const_node_iterator(mid_pointer(begin(), end()), begin(), end())); - } - - inline node_iterator - node_begin() - { - return (node_iterator(mid_pointer(begin(), end()), begin(), end())); - } - - inline const_node_iterator - node_end() const - { - return (const_node_iterator(end(), end(), end())); - } - - inline node_iterator - node_end() - { - return (node_iterator(end(), end(), end())); - } - - private: - - inline pointer - insert_new_val(iterator it, const_reference r_value) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - -#ifdef PB_ASSOC_BASIC_REGRESSION - throw_prob_adjustor adjust(m_size); -#endif // #ifdef PB_ASSOC_BASIC_REGRESSION - - PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist( - PB_ASSOC_V2F(r_value))); - - pointer a_values = s_alloc.allocate(m_size + 1); - - iterator source_it = begin(); - iterator source_end_it = end(); - iterator target_it = a_values; - iterator ret_it; - - cond_dtor cd(a_values, target_it, m_size + 1); - - while (source_it != it) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it++); - - ++target_it; - } - - new (const_cast<void* >( - static_cast<const void* >(ret_it = target_it))) - value_type(r_value); - - ++target_it; - - while (source_it != source_end_it) - { - new (const_cast<void* >( - static_cast<const void* >(target_it))) - value_type(*source_it++); - - ++target_it; - } - - cd.set_no_action(); - - if (m_size != 0) - { - cond_dtor cd1(m_a_values, m_end_it, m_size); - } - - ++m_size; - - m_a_values = a_values; - - m_end_it = m_a_values + m_size; - - PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new( - PB_ASSOC_V2F(r_value))); - - update(node_begin(), (Node_Updator* )this); - - PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) - - return (ret_it); - } - -#ifdef PB_ASSOC_OV_TREE_DEBUG_ - - virtual void - assert_valid() const; - - void - assert_iterators() const; - -#endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_ - - template<class It> - void - copy_from_ordered_range(It first_it, It last_it); - - template<class It> - void - copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it); - - private: - typedef - typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type_allocator - value_allocator; - - pointer m_a_values; - - static value_allocator s_alloc; - - pointer m_end_it; - - size_type m_size; - }; - -#include <ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp> -#include <ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp> - -#undef PB_ASSOC_CLASS_C_DEC - -#undef PB_ASSOC_CLASS_T_DEC - -#undef PB_ASSOC_OV_TREE_CLASS_NAME - -#undef PB_ASSOC_TYPES_TRAITS_C_DEC - -#undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC - -#undef PB_ASSOC_V2F -#undef PB_ASSOC_EP2VP -#undef PB_ASSOC_V2S - -#undef PB_ASSOC_DBG_ASSERT -#undef PB_ASSOC_DBG_VERIFY -#undef PB_ASSOC_DBG_ONLY - - } // namespace detail - -} // namespace pb_assoc diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp deleted file mode 100644 index b93084bf386..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp +++ /dev/null @@ -1,189 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. - -// Permission to use, copy, modify, sell, and distribute this software -// is hereby granted without fee, provided that the above copyright -// notice appears in all copies, and that both that copyright notice and -// this permission notice appear in supporting documentation. None of -// the above authors, nor IBM Haifa Research Laboratories, make any -// representation about the suitability of this software for any -// purpose. It is provided "as is" without express or implied warranty. - -/** - * @file split_join_fn_imps.hpp - * Contains an implementation class for ov_tree_. - */ - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other) -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - if (m_size == 0) - { - r_other.clear(); - - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - return; - } - - if (Cmp_Fn::operator()(r_key, PB_ASSOC_V2F(*begin()))) - { - swap(r_other); - - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - return; - } - - if (!Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*(end() - 1)))) - { - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - return; - } - - if (m_size == 1) - { - swap(r_other); - - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - return; - } - -#ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ - for (const_iterator it = begin(); it != end(); ++it) - if (Cmp_Fn::operator()( - r_key, - PB_ASSOC_V2F(*it))) - { - my_map_debug_base::erase_existing(PB_ASSOC_V2F(*it)); - r_other.my_map_debug_base::insert_new(PB_ASSOC_V2F(*it)); - } -#endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ - - iterator it = upper_bound(r_key); - - PB_ASSOC_CLASS_C_DEC new_other(r_other, r_other); - - new_other.copy_from_ordered_range(it, end()); - - PB_ASSOC_CLASS_C_DEC new_this(*this, * this); - - new_this.copy_from_ordered_range(begin(), it); - - // No exceptions from this point. - - r_other.update(r_other.node_begin(), (Node_Updator* )(&r_other)); - - update(node_begin(), (Node_Updator* )this); - - r_other.swap(new_other); - - swap(new_this); - - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - } - -PB_ASSOC_CLASS_T_DEC -void -PB_ASSOC_CLASS_C_DEC:: -join(PB_ASSOC_CLASS_C_DEC& r_other) -{ - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - - if (r_other.m_size == 0) - return; - - if (m_size == 0) - { - swap(r_other); - - return; - } - - const bool greater = Cmp_Fn::operator()( - PB_ASSOC_V2F(*(end() - 1)), - PB_ASSOC_V2F(*r_other.begin())); - - const bool lesser = Cmp_Fn::operator()( - PB_ASSOC_V2F(*(r_other.end() - 1)), - PB_ASSOC_V2F(*begin())); - - if (!greater&& !lesser) - throw cannot_join(); - -#ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ - for (const_iterator other_it = r_other.begin(); other_it != r_other.end(); - ++other_it) - { - my_map_debug_base::insert_new(PB_ASSOC_V2F(*other_it)); - r_other.my_map_debug_base::erase_existing(PB_ASSOC_V2F(*other_it)); - } -#endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_ - - PB_ASSOC_CLASS_C_DEC new_this(*this, * this); - - if (greater) - new_this.copy_from_ordered_range( - begin(), - end(), - r_other.begin(), - r_other.end()); - else - new_this.copy_from_ordered_range( - r_other.begin(), - r_other.end(), - begin(), - end()); - - // No exceptions from this point. - - swap(new_this); - - r_other.clear(); - - PB_ASSOC_DBG_ONLY(assert_valid();) - PB_ASSOC_DBG_ONLY(r_other.assert_valid();) - } |