From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../constructor_destructor_fn_imps.hpp | 142 ++++++++ .../detail/list_update_map_/debug_fn_imps.hpp | 57 ++++ .../list_update_map_/entry_metadata_base.hpp | 60 ++++ .../detail/list_update_map_/erase_fn_imps.hpp | 135 ++++++++ .../pb_ds/detail/list_update_map_/find_fn_imps.hpp | 90 ++++++ .../pb_ds/detail/list_update_map_/info_fn_imps.hpp | 57 ++++ .../detail/list_update_map_/insert_fn_imps.hpp | 106 ++++++ .../detail/list_update_map_/iterators_fn_imps.hpp | 80 +++++ .../ext/pb_ds/detail/list_update_map_/lu_map_.hpp | 359 +++++++++++++++++++++ .../detail/list_update_map_/trace_fn_imps.hpp | 59 ++++ 10 files changed, 1145 insertions(+) create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp (limited to 'libstdc++-v3/include/ext/pb_ds/detail/list_update_map_') diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp new file mode 100644 index 000000000..056488521 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp @@ -0,0 +1,142 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 +// 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 +// . + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file constructor_destructor_fn_imps.hpp + * Contains implementations of PB_DS_CLASS_NAME. + */ + +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_lu_metadata PB_DS_CLASS_C_DEC::s_null_lu_metadata; + +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 +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_CLASS_NAME() : m_p_l(0) +{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } + +PB_DS_CLASS_T_DEC +template +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(It first_it, It last_it) : m_p_l(0) +{ + copy_from_range(first_it, last_it); + _GLIBCXX_DEBUG_ONLY(assert_valid();); +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : +#ifdef _GLIBCXX_DEBUG + debug_base(), +#endif +m_p_l(0) +{ + __try + { + for (const_iterator it = other.begin(); it != other.end(); ++it) + { + entry_pointer p_l = allocate_new_entry(*it, + PB_DS_TYPES_TRAITS_C_DEC::m_no_throw_copies_indicator); + + p_l->m_p_next = m_p_l; + m_p_l = p_l; + } + } + __catch(...) + { + deallocate_all(); + __throw_exception_again; + } + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) + std::swap(m_p_l, other.m_p_l); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} + +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_CLASS_NAME() +{ deallocate_all(); } + diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp new file mode 100644 index 000000000..95e9e22b1 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp @@ -0,0 +1,57 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 +// . + +// 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 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 +{ + size_type calc_size = 0; + for (const_iterator it = begin(); it != end(); ++it) + { + debug_base::check_key_exists(PB_DS_V2F(*it)); + ++calc_size; + } + debug_base::check_size(calc_size); +} + +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp new file mode 100644 index 000000000..021ef50d8 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp @@ -0,0 +1,60 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 +// . + +// 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 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 + struct lu_map_entry_metadata_base + { + Metadata m_update_metadata; + }; + + template<> + struct lu_map_entry_metadata_base + { }; + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp new file mode 100644 index 000000000..c481aaa2d --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp @@ -0,0 +1,135 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// 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 implementations of lu_map_. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase(const_key_reference r_key) +{ + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + 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 +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +erase_if(Pred pred) +{ + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + 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; + } + + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + 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_l); + _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); +} + diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp new file mode 100644 index 000000000..0c872cbe0 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp @@ -0,0 +1,90 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// 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 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(const_key_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); + _GLIBCXX_DEBUG_ONLY(debug_base::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; + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return 0; +} + +PB_DS_CLASS_T_DEC +template +inline bool +PB_DS_CLASS_C_DEC:: +apply_update(entry_pointer p_l, type_to_type) +{ 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) +{ return s_update_policy(s_null_lu_metadata); } + diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp new file mode 100644 index 000000000..31f743cf1 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp @@ -0,0 +1,57 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file info_fn_imps.hpp + * Contains implementations of 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); } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp new file mode 100644 index 000000000..3e294fbdc --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp @@ -0,0 +1,106 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file insert_fn_imps.hpp + * Contains implementations of 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) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + entry_pointer p_l = find_imp(PB_DS_V2F(r_val)); + + if (p_l != 0) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val));) + return std::make_pair(point_iterator(&p_l->m_value), false); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::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; + _GLIBCXX_DEBUG_ONLY(assert_valid();) + 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(static_cast(&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 +inline void +PB_DS_CLASS_C_DEC:: +init_entry_metadata(entry_pointer p_l, type_to_type) +{ 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) +{ } + diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp new file mode 100644 index 000000000..ac3163858 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp @@ -0,0 +1,80 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// 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 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(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(this)); +} + diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp new file mode 100644 index 000000000..aa8dd1b52 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp @@ -0,0 +1,359 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// 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 lu_map_.hpp + * Contains a list update map. + */ + +#include +#include +#include +#include +#include +#include +#include +#ifdef _GLIBCXX_DEBUG +#include +#endif +#ifdef PB_DS_LU_MAP_TRACE_ +#include +#endif +#include + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template + +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_CLASS_NAME lu_map_data_ +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_CLASS_NAME lu_map_no_data_ +#endif + +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME + +#define PB_DS_TYPES_TRAITS_C_DEC \ + types_traits + +#ifdef _GLIBCXX_DEBUG +#define PB_DS_DEBUG_MAP_BASE_C_DEC \ + debug_map_base::other::const_reference> +#endif + +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_V2F(X) (X).first +#define PB_DS_V2S(X) (X).second +#define PB_DS_EP2VP(X)& ((X)->m_value) +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_V2F(X) (X) +#define PB_DS_V2S(X) Mapped_Data() +#define PB_DS_EP2VP(X)& ((X)->m_value.first) +#endif + + /* Skip to the lu, my darling. */ + // list-based (with updates) associative container. + template + class PB_DS_CLASS_NAME : +#ifdef _GLIBCXX_DEBUG + protected PB_DS_DEBUG_MAP_BASE_C_DEC, +#endif + public PB_DS_TYPES_TRAITS_C_DEC + { + private: + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; + + struct entry + : public lu_map_entry_metadata_base + { + typename traits_base::value_type m_value; + typename Allocator::template rebind::other::pointer m_p_next; + }; + + typedef typename Allocator::template rebind::other entry_allocator; + typedef typename entry_allocator::pointer entry_pointer; + typedef typename entry_allocator::const_pointer const_entry_pointer; + typedef typename entry_allocator::reference entry_reference; + typedef typename entry_allocator::const_reference const_entry_reference; + + typedef typename Allocator::template rebind::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 +#include +#include +#include + +#undef PB_DS_GEN_POS + + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + + typedef cond_dealtor cond_dealtor_t; + + public: + typedef Allocator allocator_type; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::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::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + typedef point_iterator_ point_iterator; +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR + typedef const_point_iterator_ point_iterator; +#endif + + typedef const_point_iterator_ const_point_iterator; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + typedef iterator_ iterator; +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR + typedef const_iterator_ iterator; +#endif + + typedef const_iterator_ const_iterator; + + public: + PB_DS_CLASS_NAME(); + + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); + + virtual + ~PB_DS_CLASS_NAME(); + + template + PB_DS_CLASS_NAME(It first_it, It last_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[](const_key_reference r_key) + { +#ifdef PB_DS_DATA_TRUE_INDICATOR + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return insert(std::make_pair(r_key, mapped_type())).first->second; +#else + insert(r_key); + return traits_base::s_null_mapped; +#endif + } + + inline std::pair + insert(const_reference); + + inline point_iterator + find(const_key_reference r_key) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + entry_pointer p_e = find_imp(r_key); + return point_iterator(p_e == 0 ? 0: &p_e->m_value); + } + + inline const_point_iterator + find(const_key_reference r_key) const + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + entry_pointer p_e = find_imp(r_key); + return const_point_iterator(p_e == 0 ? 0: &p_e->m_value); + } + + inline bool + erase(const_key_reference); + + template + 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; +#endif + +#ifdef PB_DS_LU_MAP_TRACE_ + void + trace() const; +#endif + + protected: + + template + 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 + inline static void + init_entry_metadata(entry_pointer, type_to_type); + + inline static void + init_entry_metadata(entry_pointer, type_to_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 + inline static bool + apply_update(entry_pointer, type_to_type); + + inline static bool + apply_update(entry_pointer, type_to_type); + + inline entry_pointer + find_imp(const_key_reference) const; + + static entry_allocator s_entry_allocator; + static Eq_Fn s_eq_fn; + static Update_Policy s_update_policy; + static type_to_type s_metadata_type_indicator; + static null_lu_metadata s_null_lu_metadata; + + mutable entry_pointer m_p_l; + }; + +#include +#include +#include +#include +#include +#include +#include +#include + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_TYPES_TRAITS_C_DEC +#undef PB_DS_DEBUG_MAP_BASE_C_DEC +#undef PB_DS_CLASS_NAME +#undef PB_DS_V2F +#undef PB_DS_EP2VP +#undef PB_DS_V2S + + } // namespace detail +} // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp new file mode 100644 index 000000000..009610998 --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp @@ -0,0 +1,59 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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 +// . + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file trace_fn_imps.hpp + * Contains implementations of 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 + -- cgit v1.2.3