diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_')
24 files changed, 2581 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp new file mode 100644 index 000000000..4ac145d3d --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp @@ -0,0 +1,223 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file constructor_destructor_fn_imps.hpp + * Contains implementations of gp_ht_map_'s constructors, destructor, + * and related functions. + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::entry_allocator +PB_DS_CLASS_C_DEC::s_entry_allocator; + +PB_DS_CLASS_T_DEC +template<typename It> +void +PB_DS_CLASS_C_DEC:: +copy_from_range(It first_it, It last_it) +{ + while (first_it != last_it) + insert(*(first_it++)); +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME() +: ranged_probe_fn_base(resize_base::get_nearest_larger_size(1)), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn) +: ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn) +: hash_eq_fn_base(r_eq_fn), + ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, + const Comb_Probe_Fn& r_comb_hash_fn) +: hash_eq_fn_base(r_eq_fn), + ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), + r_hash_fn, r_comb_hash_fn), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, + const Comb_Probe_Fn& comb_hash_fn, const Probe_Fn& prober) +: hash_eq_fn_base(r_eq_fn), + ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), + r_hash_fn, comb_hash_fn, prober), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, + const Comb_Probe_Fn& comb_hash_fn, const Probe_Fn& prober, + const Resize_Policy& r_resize_policy) +: hash_eq_fn_base(r_eq_fn), resize_base(r_resize_policy), + ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), + r_hash_fn, comb_hash_fn, prober), + m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::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(other), +#endif + hash_eq_fn_base(other), + resize_base(other), + ranged_probe_fn_base(other), + m_num_e(other.m_num_e), + m_num_used_e(other.m_num_used_e), + m_entries(s_entry_allocator.allocate(m_num_e)) +{ + for (size_type i = 0; i < m_num_e; ++i) + m_entries[i].m_stat = (entry_status)empty_entry_status; + + __try + { + for (size_type i = 0; i < m_num_e; ++i) + { + m_entries[i].m_stat = other.m_entries[i].m_stat; + if (m_entries[i].m_stat == valid_entry_status) + new (m_entries + i) entry(other.m_entries[i]); + } + } + __catch(...) + { + deallocate_all(); + __throw_exception_again; + } + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +~PB_DS_CLASS_NAME() +{ deallocate_all(); } + +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()); + std::swap(m_num_e, other.m_num_e); + std::swap(m_num_used_e, other.m_num_used_e); + std::swap(m_entries, other.m_entries); + ranged_probe_fn_base::swap(other); + hash_eq_fn_base::swap(other); + resize_base::swap(other); + _GLIBCXX_DEBUG_ONLY(debug_base::swap(other)); + _GLIBCXX_DEBUG_ONLY(assert_valid()); + _GLIBCXX_DEBUG_ONLY(other.assert_valid()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +deallocate_all() +{ + clear(); + erase_all_valid_entries(m_entries, m_num_e); + s_entry_allocator.deallocate(m_entries, m_num_e); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +erase_all_valid_entries(entry_array a_entries_resized, size_type len) +{ + for (size_type pos = 0; pos < len; ++pos) + { + entry_pointer p_e = &a_entries_resized[pos]; + if (p_e->m_stat == valid_entry_status) + p_e->m_value.~value_type(); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +initialize() +{ + Resize_Policy::notify_resized(m_num_e); + Resize_Policy::notify_cleared(); + ranged_probe_fn_base::notify_resized(m_num_e); + for (size_type i = 0; i < m_num_e; ++i) + m_entries[i].m_stat = empty_entry_status; +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..ec8069839 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_no_store_hash_fn_imps.hpp @@ -0,0 +1,53 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file constructor_destructor_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s constructors, destructor, + * and related functions. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, + false_type) +{ + _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status)k; + entry* const p_e = m_entries + pos; + new (&p_e->m_value) mapped_value_type(r_val); + p_e->m_stat = valid_entry_status; + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(p_e->m_value.first);) +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp new file mode 100644 index 000000000..5f3048759 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_store_hash_fn_imps.hpp @@ -0,0 +1,54 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file constructor_destructor_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s constructors, destructor, + * and related functions. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, + true_type) +{ + _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); + entry* const p_e = m_entries + pos; + new (&p_e->m_value) mapped_value_type(r_val); + p_e->m_hash = ranged_probe_fn_base::operator()(PB_DS_V2F(r_val)).second; + p_e->m_stat = valid_entry_status; + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(p_e->m_value.first);) +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp new file mode 100644 index 000000000..d7018c62c --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp @@ -0,0 +1,55 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file debug_fn_imps.hpp + * Contains implementations of gp_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_valid() const +{ + debug_base::check_size(m_num_used_e); + assert_entry_array_valid(m_entries, traits_base::m_store_extra_indicator); +} + +#include <ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp> + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..86b4d7daf --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp @@ -0,0 +1,71 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file debug_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_entry_array_valid(const entry_array a_entries, false_type) const +{ + size_type iterated_num_used_e = 0; + for (size_type pos = 0; pos < m_num_e; ++pos) + { + const_entry_pointer p_e = &a_entries[pos]; + switch(p_e->m_stat) + { + case empty_entry_status: + case erased_entry_status: + break; + case valid_entry_status: + { + const_key_reference r_key = PB_DS_V2F(p_e->m_value); + debug_base::check_key_exists(r_key); + ++iterated_num_used_e; + break; + } + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + } + _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); +} + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp new file mode 100644 index 000000000..961f14361 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/debug_store_hash_fn_imps.hpp @@ -0,0 +1,77 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file debug_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s debug-mode functions. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_entry_array_valid(const entry_array a_entries, true_type) const +{ + size_type iterated_num_used_e = 0; + + for (size_type pos = 0; pos < m_num_e; ++pos) + { + const_entry_pointer p_e =& a_entries[pos]; + switch(p_e->m_stat) + { + case empty_entry_status: + case erased_entry_status: + break; + case valid_entry_status: + { + const_key_reference r_key = PB_DS_V2F(p_e->m_value); + debug_base::check_key_exists(r_key); + + const comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); + + _GLIBCXX_DEBUG_ASSERT(p_e->m_hash == pos_hash_pair.second); + ++iterated_num_used_e; + break; + } + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + } + + _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); +} + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp new file mode 100644 index 000000000..68878eb2a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp @@ -0,0 +1,100 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file erase_fn_imps.hpp + * Contains implementations of gp_ht_map_'s erase related functions. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +erase_entry(entry_pointer p_e) +{ + _GLIBCXX_DEBUG_ASSERT(p_e->m_stat = valid_entry_status); + _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(p_e->m_value));) + p_e->m_value.~value_type(); + p_e->m_stat = erased_entry_status; + _GLIBCXX_DEBUG_ASSERT(m_num_used_e > 0); + resize_base::notify_erased(--m_num_used_e); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear() +{ + for (size_type pos = 0; pos < m_num_e; ++pos) + { + entry_pointer p_e = &m_entries[pos]; + if (p_e->m_stat == valid_entry_status) + erase_entry(p_e); + } + do_resize_if_needed_no_throw(); + resize_base::notify_cleared(); +} + +PB_DS_CLASS_T_DEC +template<typename Pred> +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +erase_if(Pred pred) +{ + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + size_type num_ersd = 0; + for (size_type pos = 0; pos < m_num_e; ++pos) + { + entry_pointer p_e = &m_entries[pos]; + if (p_e->m_stat == valid_entry_status) + if (pred(p_e->m_value)) + { + ++num_ersd; + erase_entry(p_e); + } + } + + do_resize_if_needed_no_throw(); + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + return num_ersd; +} + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase(const_key_reference r_key) +{ return erase_imp(r_key, traits_base::m_store_extra_indicator); } + +#include <ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp> diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..40d578ebe --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp @@ -0,0 +1,85 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file erase_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s erase related functions, + * when the hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase_imp(const_key_reference r_key, false_type) +{ + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + size_type hash = ranged_probe_fn_base::operator()(r_key); + size_type i; + resize_base::notify_erase_search_start(); + + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); + entry* const p_e = m_entries + pos; + switch(p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_erase_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist( + r_key)); + return false; + } + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) + { + resize_base::notify_erase_search_end(); + erase_entry(p_e); + do_resize_if_needed_no_throw(); + return true; + } + break; + case erased_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + resize_base::notify_erase_search_collision(); + } + resize_base::notify_erase_search_end(); + return false; +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp new file mode 100644 index 000000000..8155a5261 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp @@ -0,0 +1,86 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file erase_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s erase related functions, + * when the hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase_imp(const_key_reference r_key, true_type) +{ + const comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); + size_type i; + resize_base::notify_erase_search_start(); + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); + + entry* const p_e = m_entries + pos; + switch(p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_erase_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist( + r_key)); + return false; + } + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, + r_key, pos_hash_pair.second)) + { + resize_base::notify_erase_search_end(); + erase_entry(p_e); + do_resize_if_needed_no_throw(); + return true; + } + break; + case erased_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + + resize_base::notify_erase_search_collision(); + } + resize_base::notify_erase_search_end(); + return false; +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp new file mode 100644 index 000000000..69d53763a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp @@ -0,0 +1,70 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file find_fn_imps.hpp + * Contains implementations of gp_ht_map_'s find related functions. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return find_key_pointer(r_key, traits_base::m_store_extra_indicator); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) const +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return const_cast<PB_DS_CLASS_C_DEC&>(*this).find_key_pointer(r_key, traits_base::m_store_extra_indicator); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find_end() +{ return NULL; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +find_end() const +{ return NULL; } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..298604c80 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_no_store_hash_fn_imps.hpp @@ -0,0 +1,46 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file find_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s find related functions, + * when the hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::pointer +PB_DS_CLASS_C_DEC:: +find_key_pointer(const_key_reference r_key, false_type) + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp new file mode 100644 index 000000000..a44b8326e --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/find_store_hash_fn_imps.hpp @@ -0,0 +1,40 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file find_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s insert related functions, + * when the hash value is stored. + */ diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp new file mode 100644 index 000000000..4741afec0 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp @@ -0,0 +1,677 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file gp_ht_map_.hpp + * Contains an implementation class for gp_ht_map_. + */ + +#include <ext/pb_ds/tag_and_trait.hpp> +#include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp> +#include <ext/pb_ds/detail/types_traits.hpp> +#include <ext/pb_ds/exception.hpp> +#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> +#include <utility> +#ifdef PB_DS_HT_MAP_TRACE_ +#include <iostream> +#endif +#ifdef _GLIBCXX_DEBUG +#include <ext/pb_ds/detail/debug_map_base.hpp> +#endif +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \ + typename Allocator, bool Store_Hash, typename Comb_Probe_Fn, \ + typename Probe_Fn, typename Resize_Policy> + +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_CLASS_NAME gp_ht_map_data_ +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_CLASS_NAME gp_ht_map_no_data_ +#endif + +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \ + Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy> + +#define PB_DS_HASH_EQ_FN_C_DEC \ + hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash> + +#define PB_DS_RANGED_PROBE_FN_C_DEC \ + ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, Store_Hash> + +#define PB_DS_TYPES_TRAITS_C_DEC \ + types_traits<Key, Mapped, Allocator, Store_Hash> + +#ifdef _GLIBCXX_DEBUG +#define PB_DS_DEBUG_MAP_BASE_C_DEC \ + debug_map_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference> +#endif + +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_V2F(X) (X).first +#define PB_DS_V2S(X) (X).second +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_V2F(X) (X) +#define PB_DS_V2S(X) Mapped() +#endif + + template<typename Key, + typename Mapped, + typename Hash_Fn, + typename Eq_Fn, + typename Allocator, + bool Store_Hash, + typename Comb_Probe_Fn, + typename Probe_Fn, + typename Resize_Policy> + class PB_DS_CLASS_NAME : +#ifdef _GLIBCXX_DEBUG + protected PB_DS_DEBUG_MAP_BASE_C_DEC, +#endif + public PB_DS_HASH_EQ_FN_C_DEC, + public Resize_Policy, + public PB_DS_RANGED_PROBE_FN_C_DEC, + public PB_DS_TYPES_TRAITS_C_DEC + { + private: + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; + typedef typename traits_base::value_type value_type_; + typedef typename traits_base::pointer pointer_; + typedef typename traits_base::const_pointer const_pointer_; + typedef typename traits_base::reference reference_; + typedef typename traits_base::const_reference const_reference_; + typedef typename traits_base::comp_hash comp_hash; + + enum entry_status + { + empty_entry_status, + valid_entry_status, + erased_entry_status + } __attribute__ ((packed)); + + struct entry : public traits_base::stored_value_type + { + entry_status m_stat; + }; + + typedef typename Allocator::template rebind<entry>::other entry_allocator; + typedef typename entry_allocator::pointer entry_pointer; + typedef typename entry_allocator::const_pointer const_entry_pointer; + typedef typename entry_allocator::reference entry_reference; + typedef typename entry_allocator::const_reference const_entry_reference; + typedef typename entry_allocator::pointer entry_array; + + typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + + typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; + typedef Resize_Policy resize_base; + +#define PB_DS_GEN_POS typename Allocator::size_type + +#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> +#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> + +#undef PB_DS_GEN_POS + + public: + typedef Allocator allocator_type; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::difference_type difference_type; + typedef Hash_Fn hash_fn; + typedef Eq_Fn eq_fn; + typedef Probe_Fn probe_fn; + typedef Comb_Probe_Fn comb_probe_fn; + typedef Resize_Policy resize_policy; + + enum + { + store_hash = Store_Hash + }; + + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + typedef point_iterator_ point_iterator; +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR + typedef const_point_iterator_ point_iterator; +#endif + + typedef const_point_iterator_ const_point_iterator; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + typedef iterator_ iterator; +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR + typedef const_iterator_ iterator; +#endif + + typedef const_iterator_ const_iterator; + + PB_DS_CLASS_NAME(); + + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); + + PB_DS_CLASS_NAME(const Hash_Fn&); + + PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); + + PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); + + PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, + const Probe_Fn&); + + PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, + const Probe_Fn&, const Resize_Policy&); + + template<typename It> + void + copy_from_range(It first_it, It last_it); + + virtual + ~PB_DS_CLASS_NAME(); + + void + swap(PB_DS_CLASS_C_DEC& other); + + inline size_type + size() const; + + inline size_type + max_size() const; + + inline bool + empty() const; + + Hash_Fn& + get_hash_fn(); + + const Hash_Fn& + get_hash_fn() const; + + Eq_Fn& + get_eq_fn(); + + const Eq_Fn& + get_eq_fn() const; + + Probe_Fn& + get_probe_fn(); + + const Probe_Fn& + get_probe_fn() const; + + Comb_Probe_Fn& + get_comb_probe_fn(); + + const Comb_Probe_Fn& + get_comb_probe_fn() const; + + Resize_Policy& + get_resize_policy(); + + const Resize_Policy& + get_resize_policy() const; + + inline std::pair<point_iterator, bool> + insert(const_reference r_val) + { + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + return insert_imp(r_val, traits_base::m_store_extra_indicator); + } + + inline mapped_reference + operator[](const_key_reference r_key) + { +#ifdef PB_DS_DATA_TRUE_INDICATOR + return subscript_imp(r_key, traits_base::m_store_extra_indicator); +#else + insert(r_key); + return traits_base::s_null_mapped; +#endif + } + + inline point_iterator + find(const_key_reference r_key); + + inline const_point_iterator + find(const_key_reference r_key) const; + + inline point_iterator + find_end(); + + inline const_point_iterator + find_end() const; + + inline bool + erase(const_key_reference r_key); + + template<typename Pred> + inline size_type + erase_if(Pred prd); + + void + clear(); + + inline iterator + begin(); + + inline const_iterator + begin() const; + + inline iterator + end(); + + inline const_iterator + end() const; + +#ifdef _GLIBCXX_DEBUG + void + assert_valid() const; +#endif + +#ifdef PB_DS_HT_MAP_TRACE_ + void + trace() const; +#endif + + private: +#ifdef PB_DS_DATA_TRUE_INDICATOR + friend class iterator_; +#endif + + friend class const_iterator_; + + void + deallocate_all(); + + void + initialize(); + + void + erase_all_valid_entries(entry_array, size_type); + + inline bool + do_resize_if_needed(); + + inline void + do_resize_if_needed_no_throw(); + + void + resize_imp(size_type); + + virtual void + do_resize(size_type); + + void + resize_imp(entry_array, size_type); + + inline void + resize_imp_reassign(entry_pointer, entry_array, false_type); + + inline void + resize_imp_reassign(entry_pointer, entry_array, true_type); + + inline size_type + find_ins_pos(const_key_reference, false_type); + + inline comp_hash + find_ins_pos(const_key_reference, true_type); + + inline std::pair<point_iterator, bool> + insert_imp(const_reference, false_type); + + inline std::pair<point_iterator, bool> + insert_imp(const_reference, true_type); + + inline pointer + insert_new_imp(const_reference r_val, size_type pos) + { + _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); + + if (do_resize_if_needed()) + pos = find_ins_pos(PB_DS_V2F(r_val), + traits_base::m_store_extra_indicator); + + _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); + + entry* const p_e = m_entries + pos; + new (&p_e->m_value) value_type(r_val); + p_e->m_stat = valid_entry_status; + resize_base::notify_inserted(++m_num_used_e); + + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return &p_e->m_value; + } + + inline pointer + insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) + { + _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != + valid_entry_status); + + if (do_resize_if_needed()) + r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), + traits_base::m_store_extra_indicator); + + _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != + valid_entry_status); + + entry* const p_e = m_entries + r_pos_hash_pair.first; + new (&p_e->m_value) value_type(r_val); + p_e->m_hash = r_pos_hash_pair.second; + p_e->m_stat = valid_entry_status; + + resize_base::notify_inserted(++m_num_used_e); + + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return &p_e->m_value; + } + +#ifdef PB_DS_DATA_TRUE_INDICATOR + inline mapped_reference + subscript_imp(const_key_reference key, false_type) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + + const size_type pos = find_ins_pos(key, + traits_base::m_store_extra_indicator); + + entry_pointer p_e = &m_entries[pos]; + if (p_e->m_stat != valid_entry_status) + return insert_new_imp(value_type(key, mapped_type()), pos)->second; + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) + return p_e->m_value.second; + } + + inline mapped_reference + subscript_imp(const_key_reference key, true_type) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + + comp_hash pos_hash_pair = + find_ins_pos(key, traits_base::m_store_extra_indicator); + + if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) + return insert_new_imp(value_type(key, mapped_type()), + pos_hash_pair)->second; + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key)); + return (m_entries + pos_hash_pair.first)->m_value.second; + } +#endif + + inline pointer + find_key_pointer(const_key_reference key, false_type) + { + const size_type hash = ranged_probe_fn_base::operator()(key); + size_type i; + resize_base::notify_find_search_start(); + + // Loop until entry is found or until all possible entries accessed. + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(key, hash, i); + + entry* const p_e = m_entries + pos; + switch (p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_find_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) + + return NULL; + } + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) + { + resize_base::notify_find_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) + + return pointer(&p_e->m_value); + } + break; + case erased_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + + resize_base::notify_find_search_collision(); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) + resize_base::notify_find_search_end(); + return NULL; + } + + inline pointer + find_key_pointer(const_key_reference key, true_type) + { + comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); + size_type i; + resize_base::notify_find_search_start(); + + // Loop until entry is found or until all possible entries accessed. + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = + ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); + + entry* const p_e = m_entries + pos; + + switch(p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_find_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) + + return NULL; + } + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), + p_e->m_hash, + key, pos_hash_pair.second)) + { + resize_base::notify_find_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(key);) + return pointer(&p_e->m_value); + } + break; + case erased_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + + resize_base::notify_find_search_collision(); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(key);) + resize_base::notify_find_search_end(); + return NULL; + } + + inline bool + erase_imp(const_key_reference, true_type); + + inline bool + erase_imp(const_key_reference, false_type); + + inline void + erase_entry(entry_pointer p_e); + +#ifdef PB_DS_DATA_TRUE_INDICATOR + void + inc_it_state(pointer& r_p_value, size_type& r_pos) const + { inc_it_state((const_mapped_pointer& )r_p_value, r_pos); } +#endif + + void + inc_it_state(const_pointer& r_p_value, size_type& r_pos) const + { + _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL); + for (++r_pos; r_pos < m_num_e; ++r_pos) + { + const_entry_pointer p_e =& m_entries[r_pos]; + if (p_e->m_stat == valid_entry_status) + { + r_p_value =& p_e->m_value; + return; + } + } + r_p_value = NULL; + } + + void + get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const + { + for (r_pos = 0; r_pos < m_num_e; ++r_pos) + { + const_entry_pointer p_e = &m_entries[r_pos]; + if (p_e->m_stat == valid_entry_status) + { + r_p_value = &p_e->m_value; + return; + } + } + r_p_value = NULL; + } + + void + get_start_it_state(pointer& r_p_value, size_type& r_pos) + { + for (r_pos = 0; r_pos < m_num_e; ++r_pos) + { + entry_pointer p_e = &m_entries[r_pos]; + if (p_e->m_stat == valid_entry_status) + { + r_p_value = &p_e->m_value; + return; + } + } + r_p_value = NULL; + } + +#ifdef _GLIBCXX_DEBUG + void + assert_entry_array_valid(const entry_array, false_type) const; + + void + assert_entry_array_valid(const entry_array, true_type) const; +#endif + + static entry_allocator s_entry_allocator; + static iterator s_end_it; + static const_iterator s_const_end_it; + + size_type m_num_e; + size_type m_num_used_e; + entry_pointer m_entries; + + enum + { + store_hash_ok = !Store_Hash + || !is_same<Hash_Fn, __gnu_pbds::null_hash_fn>::value + }; + + PB_DS_STATIC_ASSERT(sth, store_hash_ok); + }; + +#include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp> + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_HASH_EQ_FN_C_DEC +#undef PB_DS_RANGED_PROBE_FN_C_DEC +#undef PB_DS_TYPES_TRAITS_C_DEC +#undef PB_DS_DEBUG_MAP_BASE_C_DEC +#undef PB_DS_CLASS_NAME +#undef PB_DS_V2F +#undef PB_DS_V2S + + } // namespace detail +} // namespace __gnu_pbds + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp new file mode 100644 index 000000000..423a9288e --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp @@ -0,0 +1,58 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file info_fn_imps.hpp + * Contains implementations of gp_ht_map_'s entire container info related + * functions. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +size() const +{ return m_num_used_e; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +max_size() const +{ return s_entry_allocator.max_size(); } + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +empty() const +{ return (size() == 0); } diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp new file mode 100644 index 000000000..101ce8c6b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp @@ -0,0 +1,43 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file insert_fn_imps.hpp + * Contains implementations of gp_ht_map_'s insert related functions. + */ + +#include <ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp> + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..3227a4aaa --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_no_store_hash_fn_imps.hpp @@ -0,0 +1,111 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file insert_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s insert related functions, + * when the hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +find_ins_pos(const_key_reference r_key, false_type) +{ + size_type hash = ranged_probe_fn_base::operator()(r_key); + size_type i; + + /* The insertion position is initted to a non-legal value to indicate + * that it has not been initted yet. + */ + size_type ins_pos = m_num_e; + resize_base::notify_insert_search_start(); + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); + _GLIBCXX_DEBUG_ASSERT(pos < m_num_e); + entry* const p_e = m_entries + pos; + switch(p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_insert_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return (ins_pos == m_num_e) ? pos : ins_pos; + } + break; + case erased_entry_status: + if (ins_pos == m_num_e) + ins_pos = pos; + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) + { + resize_base::notify_insert_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) + return pos; + } + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + + resize_base::notify_insert_search_collision(); + } + resize_base::notify_insert_search_end(); + if (ins_pos == m_num_e) + __throw_insert_error(); + return ins_pos; +} + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> +PB_DS_CLASS_C_DEC:: +insert_imp(const_reference r_val, false_type) +{ + const_key_reference r_key = PB_DS_V2F(r_val); + const size_type pos = find_ins_pos(r_key, + traits_base::m_store_extra_indicator); + + if (m_entries[pos].m_stat == valid_entry_status) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) + return std::make_pair(&(m_entries + pos)->m_value, false); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); + return std::make_pair(insert_new_imp(r_val, pos), true); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp new file mode 100644 index 000000000..f4310b629 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/insert_store_hash_fn_imps.hpp @@ -0,0 +1,118 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file insert_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s find related functions, + * when the hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::comp_hash +PB_DS_CLASS_C_DEC:: +find_ins_pos(const_key_reference r_key, true_type) +{ + _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) + comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); + + size_type i; + + /* The insertion position is initted to a non-legal value to indicate + * that it has not been initted yet. + */ + size_type ins_pos = m_num_e; + resize_base::notify_insert_search_start(); + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); + + entry* const p_e = m_entries + pos; + switch(p_e->m_stat) + { + case empty_entry_status: + { + resize_base::notify_insert_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + + return ((ins_pos == m_num_e) ? + std::make_pair(pos, pos_hash_pair.second) : + std::make_pair(ins_pos, pos_hash_pair.second)); + } + break; + case erased_entry_status: + if (ins_pos == m_num_e) + ins_pos = pos; + break; + case valid_entry_status: + if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, + r_key, pos_hash_pair.second)) + { + resize_base::notify_insert_search_end(); + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) + return std::make_pair(pos, pos_hash_pair.second); + } + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + resize_base::notify_insert_search_collision(); + } + resize_base::notify_insert_search_end(); + if (ins_pos == m_num_e) + __throw_insert_error(); + return std::make_pair(ins_pos, pos_hash_pair.second); +} + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> +PB_DS_CLASS_C_DEC:: +insert_imp(const_reference r_val, true_type) +{ + const_key_reference r_key = PB_DS_V2F(r_val); + comp_hash pos_hash_pair = find_ins_pos(r_key, + traits_base::m_store_extra_indicator); + + _GLIBCXX_DEBUG_ASSERT(pos_hash_pair.first < m_num_e); + entry_pointer p_e =& m_entries[pos_hash_pair.first]; + if (p_e->m_stat == valid_entry_status) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); + return std::make_pair(&p_e->m_value, false); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); + return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp new file mode 100644 index 000000000..ff1f80f28 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp @@ -0,0 +1,83 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file iterator_fn_imps.hpp + * Contains implementations of gp_ht_map_'s iterators related functions, e.g., + * begin(). + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC::s_end_it; + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC::s_const_end_it; + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +begin() +{ + pointer_ p_value; + size_type pos; + get_start_it_state(p_value, pos); + return iterator(p_value, pos, this); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +end() +{ return s_end_it; } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +begin() const +{ + const_pointer_ p_value; + size_type pos; + get_start_it_state(p_value, pos); + return const_iterator(p_value, pos, this); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +end() const +{ return s_const_end_it; } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp new file mode 100644 index 000000000..b1a3f7a7e --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp @@ -0,0 +1,100 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file policy_access_fn_imps.hpp + * Contains implementations of gp_ht_map_'s policy agpess + * functions. + */ + +PB_DS_CLASS_T_DEC +Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_hash_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Hash_Fn& +PB_DS_CLASS_C_DEC:: +get_hash_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Eq_Fn& +PB_DS_CLASS_C_DEC:: +get_eq_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Eq_Fn& +PB_DS_CLASS_C_DEC:: +get_eq_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Probe_Fn& +PB_DS_CLASS_C_DEC:: +get_probe_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Probe_Fn& +PB_DS_CLASS_C_DEC:: +get_probe_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Comb_Probe_Fn& +PB_DS_CLASS_C_DEC:: +get_comb_probe_fn() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Comb_Probe_Fn& +PB_DS_CLASS_C_DEC:: +get_comb_probe_fn() const +{ return *this; } + +PB_DS_CLASS_T_DEC +Resize_Policy& +PB_DS_CLASS_C_DEC:: +get_resize_policy() +{ return *this; } + +PB_DS_CLASS_T_DEC +const Resize_Policy& +PB_DS_CLASS_C_DEC:: +get_resize_policy() const +{ return *this; } diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp new file mode 100644 index 000000000..82a8ab0d2 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp @@ -0,0 +1,137 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file resize_fn_imps.hpp + * Contains implementations of gp_ht_map_'s resize related functions. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +do_resize_if_needed() +{ + if (!resize_base::is_resize_needed()) + return false; + resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +do_resize(size_type n) +{ resize_imp(resize_base::get_nearest_larger_size(n)); } + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +do_resize_if_needed_no_throw() +{ + if (!resize_base::is_resize_needed()) + return; + + __try + { + resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e)); + } + __catch(...) + { } + + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +resize_imp(size_type new_size) +{ +#ifdef PB_DS_REGRESSION + typename Allocator::group_throw_prob_adjustor adjust(m_num_e); +#endif + + if (new_size == m_num_e) + return; + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + const size_type old_size = m_num_e; + entry_array a_entries_resized = NULL; + + // Following line might throw an exception. + a_entries_resized = s_entry_allocator.allocate(new_size); + + ranged_probe_fn_base::notify_resized(new_size); + m_num_e = new_size; + + for (size_type i = 0; i < m_num_e; ++i) + a_entries_resized[i].m_stat = empty_entry_status; + + __try + { + resize_imp(a_entries_resized, old_size); + } + __catch(...) + { + erase_all_valid_entries(a_entries_resized, new_size); + m_num_e = old_size; + s_entry_allocator.deallocate(a_entries_resized, new_size); + ranged_probe_fn_base::notify_resized(old_size); + __throw_exception_again; + } + + // At this point no exceptions can be thrown. + _GLIBCXX_DEBUG_ONLY(assert_entry_array_valid(a_entries_resized, traits_base::m_store_extra_indicator);) + + Resize_Policy::notify_resized(new_size); + erase_all_valid_entries(m_entries, old_size); + s_entry_allocator.deallocate(m_entries, old_size); + m_entries = a_entries_resized; + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +resize_imp(entry_array a_entries_resized, size_type old_size) +{ + for (size_type pos = 0; pos < old_size; ++pos) + if (m_entries[pos].m_stat == valid_entry_status) + resize_imp_reassign(m_entries + pos, a_entries_resized, + traits_base::m_store_extra_indicator); +} + +#include <ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp> +#include <ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp> + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp new file mode 100644 index 000000000..1d2839e0a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp @@ -0,0 +1,72 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file resize_no_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s resize related functions, when the + * hash value is not stored. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, + false_type) +{ + const_key_reference r_key = PB_DS_V2F(p_e->m_value); + size_type hash = ranged_probe_fn_base::operator()(r_key); + size_type i; + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); + entry_pointer p_new_e = a_entries_resized + pos; + switch(p_new_e->m_stat) + { + case empty_entry_status: + new (&p_new_e->m_value) value_type(p_e->m_value); + p_new_e->m_stat = valid_entry_status; + return; + case erased_entry_status: + _GLIBCXX_DEBUG_ASSERT(0); + break; + case valid_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + } + __throw_insert_error(); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp new file mode 100644 index 000000000..765e9624b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp @@ -0,0 +1,74 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file resize_store_hash_fn_imps.hpp + * Contains implementations of gp_ht_map_'s resize related functions, when the + * hash value is stored. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, + true_type) +{ + const_key_reference r_key = PB_DS_V2F(p_e->m_value); + size_type hash = ranged_probe_fn_base::operator()(r_key, p_e->m_hash); + + size_type i; + for (i = 0; i < m_num_e; ++i) + { + const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i); + entry_pointer p_new_e = a_entries_resized + pos; + switch(p_new_e->m_stat) + { + case empty_entry_status: + new (&p_new_e->m_value) value_type(p_e->m_value); + p_new_e->m_hash = hash; + p_new_e->m_stat = valid_entry_status; + return; + case erased_entry_status: + _GLIBCXX_DEBUG_ASSERT(0); + break; + case valid_entry_status: + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + } + __throw_insert_error(); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/standard_policies.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/standard_policies.hpp new file mode 100644 index 000000000..479725fd5 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/standard_policies.hpp @@ -0,0 +1,74 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file standard_policies.hpp + * Contains standard policies for gp_ht_map types. + */ + +#ifndef PB_DS_GP_HT_MAP_STANDARD_POLICIES_HPP +#define PB_DS_GP_HT_MAP_STANDARD_POLICIES_HPP + +#include <ext/pb_ds/detail/standard_policies.hpp> +#include <ext/pb_ds/ht_load_check_resize_trigger.hpp> +#include <ext/pb_ds/linear_probe_fn.hpp> +#include <ext/pb_ds/quadratic_probe_fn.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + template<typename Comb_Probe_Fn> + struct default_probe_fn + { + private: + typedef typename Comb_Probe_Fn::size_type size_type; + + public: + typedef + typename __conditional_type< + is_same< + __gnu_pbds::direct_mask_range_hashing<size_t>, + Comb_Probe_Fn>::value, + __gnu_pbds::linear_probe_fn<size_type>, + __gnu_pbds::quadratic_probe_fn<size_type> >::__type + type; + }; + + } // namespace detail +} // namespace __gnu_pbds + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp new file mode 100644 index 000000000..c3fe13c00 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp @@ -0,0 +1,74 @@ +// -*- 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 +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file trace_fn_imps.hpp + * Contains implementations of gp_ht_map_'s trace-mode functions. + */ + +#ifdef PB_DS_HT_MAP_TRACE_ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace() const +{ + std::cerr << static_cast<unsigned long>(m_num_e) << " " << + static_cast<unsigned long>(m_num_used_e) << std::endl; + + for (size_type i = 0; i < m_num_e; ++i) + { + std::cerr << static_cast<unsigned long>(i) << " "; + + switch(m_entries[i].m_stat) + { + case empty_entry_status: + std::cerr << "<empty>"; + break; + case erased_entry_status: + std::cerr << "<erased>"; + break; + case valid_entry_status: + std::cerr << PB_DS_V2F(m_entries[i].m_value); + break; + default: + _GLIBCXX_DEBUG_ASSERT(0); + }; + + std::cerr << std::endl; + } +} + +#endif // #ifdef PB_DS_HT_MAP_TRACE_ |