URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
Compare Revisions
- This comparison shows the changes necessary to convert path
/openrisc/tags/gnu-src/gcc-4.5.1/gcc-4.5.1-or32-1.0rc4/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_
- from Rev 424 to Rev 519
- ↔ Reverse comparison
Rev 424 → Rev 519
/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);) |
} |
/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; |
} |
|
/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); |
} |
|
/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(); |
} |
|
/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; } |
/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; } |
|
/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);) |
} |
/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 |
|
/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); |
} |
|
/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 |
/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; } |
|
/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) |
|
/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); } |
/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_ |
/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> |
/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. |
*/ |
/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 |
/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_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> |
|
/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; |
} |
|
/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> |
|
/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 |
/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; |
} |
|
/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(); |
} |
|
/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 |
|