inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file iterators_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() { return iterator(m_p_head->m_p_min); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const { return const_iterator(m_p_head->m_p_min); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() { return iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { return const_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: rbegin() const { if (empty()) return rend(); return --end(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: rbegin() { if (empty()) return rend(); return --end(); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: rend() { return reverse_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator PB_DS_CLASS_C_DEC:: rend() const { return const_reverse_iterator(m_p_head); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_begin() const { return const_node_iterator(m_p_head->m_p_parent, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_begin() { return node_iterator(m_p_head->m_p_parent, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_node_iterator PB_DS_CLASS_C_DEC:: node_end() const { return const_node_iterator(NULL, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_iterator PB_DS_CLASS_C_DEC:: node_end() { return node_iterator(NULL, this); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_join_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); split_join_branch_bag bag; if (!join_prep(other, bag)) { _GLIBCXX_DEBUG_ONLY(assert_valid();); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); return; } m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, other.m_p_head->m_p_parent, 0, bag); m_p_head->m_p_parent->m_p_parent = m_p_head; m_size += other.m_size; other.initialize(); _GLIBCXX_DEBUG_ONLY(other.assert_valid();); m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); _GLIBCXX_DEBUG_ONLY(assert_valid();); } PB_DS_CLASS_T_DEC bool PB_DS_CLASS_C_DEC:: join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) if (other.m_size == 0) return false; if (m_size == 0) { value_swap(other); return false; } const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast( m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast( other.m_p_head->m_p_min)->value())); const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast( other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast(m_p_head->m_p_min)->value())); if (!greater && !lesser) __throw_join_error(); rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); _GLIBCXX_DEBUG_ONLY(debug_base::join(other);) return true; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) { if (p_l->m_type == pat_trie_leaf_node_type) { if (p_r->m_type == pat_trie_leaf_node_type) { rec_join_prep(static_cast(p_l), static_cast(p_r), r_bag); return; } _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); rec_join_prep(static_cast(p_l), static_cast(p_r), r_bag); return; } _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); if (p_r->m_type == pat_trie_leaf_node_type) { rec_join_prep(static_cast(p_l), static_cast(p_r), r_bag); return; } _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); rec_join_prep(static_cast(p_l), static_cast(p_r), r_bag); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, split_join_branch_bag& r_bag) { r_bag.add_branch(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/, split_join_branch_bag& r_bag) { r_bag.add_branch(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/, split_join_branch_bag& r_bag) { r_bag.add_branch(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag) { if (p_l->get_e_ind() == p_r->get_e_ind() && synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), p_r->pref_b_it(), p_r->pref_e_it())) { for (typename internal_node::const_iterator it = p_r->begin(); it != p_r->end(); ++ it) { const_node_pointer p_l_join_child = p_l->get_join_child(*it, this); if (p_l_join_child != NULL) rec_join_prep(p_l_join_child, * it, r_bag); } return; } if (p_r->get_e_ind() < p_l->get_e_ind() && p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) { const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); if (p_r_join_child != NULL) rec_join_prep(p_r_join_child, p_l, r_bag); return; } if (p_r->get_e_ind() < p_l->get_e_ind() && p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) { const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); if (p_r_join_child != NULL) rec_join_prep(p_r_join_child, p_l, r_bag); return; } r_bag.add_branch(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ASSERT(p_r != NULL); if (p_l == NULL) { apply_update(p_r, (node_update* )this); return (p_r); } if (p_l->m_type == pat_trie_leaf_node_type) { if (p_r->m_type == pat_trie_leaf_node_type) { node_pointer p_ret = rec_join(static_cast(p_l), static_cast(p_r), r_bag); apply_update(p_ret, (node_update* )this); return p_ret; } _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); node_pointer p_ret = rec_join(static_cast(p_l), static_cast(p_r), checked_ind, r_bag); apply_update(p_ret, (node_update* )this); return p_ret; } _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); if (p_r->m_type == pat_trie_leaf_node_type) { node_pointer p_ret = rec_join(static_cast(p_l), static_cast(p_r), checked_ind, r_bag); apply_update(p_ret, (node_update* )this); return p_ret; } _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); node_pointer p_ret = rec_join(static_cast(p_l), static_cast(p_r), r_bag); apply_update(p_ret, (node_update* )this); return p_ret; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ASSERT(p_r != NULL); if (p_l == NULL) return (p_r); node_pointer p_ret = insert_branch(p_l, p_r, r_bag); _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); return p_ret; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) { #ifdef _GLIBCXX_DEBUG const size_type lhs_leafs = recursive_count_leafs(p_l); const size_type rhs_leafs = recursive_count_leafs(p_r); #endif _GLIBCXX_DEBUG_ASSERT(p_r != NULL); node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); return p_ret; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ASSERT(p_l != NULL); _GLIBCXX_DEBUG_ASSERT(p_r != NULL); #ifdef _GLIBCXX_DEBUG const size_type lhs_leafs = recursive_count_leafs(p_l); const size_type rhs_leafs = recursive_count_leafs(p_r); #endif if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) { node_pointer p_ret = insert_branch(p_l, p_r, r_bag); _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); return p_ret; } node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), pref_end(p_r), this); if (p_pot_child != p_r) { node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), r_bag); p_l->replace_child(p_new_child, pref_begin(p_new_child), pref_end(p_new_child), this); } _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); return p_l; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) { _GLIBCXX_DEBUG_ASSERT(p_l != NULL); _GLIBCXX_DEBUG_ASSERT(p_r != NULL); #ifdef _GLIBCXX_DEBUG const size_type lhs_leafs = recursive_count_leafs(p_l); const size_type rhs_leafs = recursive_count_leafs(p_r); #endif if (p_l->get_e_ind() == p_r->get_e_ind() && synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), p_r->pref_b_it(), p_r->pref_e_it())) { for (typename internal_node::iterator it = p_r->begin(); it != p_r->end(); ++ it) { node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), * it, 0, r_bag); p_l->replace_child(p_new_child, pref_begin(p_new_child), pref_end(p_new_child), this); } p_r->~internal_node(); s_internal_node_allocator.deallocate(p_r, 1); _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); return p_l; } if (p_l->get_e_ind() < p_r->get_e_ind() && p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) { node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), p_r, 0, r_bag); p_l->replace_child(p_new_child, pref_begin(p_new_child), pref_end(p_new_child), this); _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) return p_l; } if (p_r->get_e_ind() < p_l->get_e_ind() && p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) { node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 0, r_bag); p_r->replace_child(p_new_child, pref_begin(p_new_child), pref_end(p_new_child), this); _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); return p_r; } node_pointer p_ret = insert_branch(p_l, p_r5555, r_bag); _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); return p_ret; } PB_DS_CLASS_T_DEC inline std::pair PB_DS_CLASS_C_DEC:: insert(const_reference r_val) { node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type && synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast(p_lf)->value()), PB_DS_V2F(r_val))) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val))); _GLIBCXX_DEBUG_ONLY(assert_valid();) return std::make_pair(iterator(p_lf), false); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); cond_dealtor cond(p_new_lf); new (p_new_lf) leaf(r_val); apply_update(p_new_lf, (node_update* )this); cond.set_call_destructor(); split_join_branch_bag bag; bag.add_branch(); m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); m_p_head->m_p_parent->m_p_parent = m_p_head; cond.set_no_action_dtor(); ++m_size; update_min_max_for_inserted_leaf(p_new_lf); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) _GLIBCXX_DEBUG_ONLY(assert_valid();) return std::make_pair(point_iterator(p_new_lf), true); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r) { size_type diff_pos = 0; while (b_l != e_l) { if (b_r == e_r) return (diff_pos); if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) return (diff_pos); ++b_l; ++b_r; ++diff_pos; } _GLIBCXX_DEBUG_ASSERT(b_r != e_r); return diff_pos; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::internal_node_pointer PB_DS_CLASS_C_DEC:: insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) { typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l); typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l); typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r); typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r); const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, right_b_it, right_e_it); internal_node_pointer p_new_nd = r_bag.get_branch(); new (p_new_nd) internal_node(diff_ind, left_b_it); p_new_nd->add_child(p_l, left_b_it, left_e_it, this); p_new_nd->add_child(p_r, right_b_it, right_e_it, this); p_l->m_p_parent = p_new_nd; p_r->m_p_parent = p_new_nd; _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);) return (p_new_nd); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) { if (m_p_head->m_p_min == m_p_head || synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), PB_DS_V2F(static_cast(m_p_head->m_p_min)->value()))) m_p_head->m_p_min = p_new_lf; if (m_p_head->m_p_max == m_p_head || synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value()))) m_p_head->m_p_max = p_new_lf; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file rotate_fn_imps.hpp * Contains imps for rotating nodes. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_left(node_pointer p_x) { node_pointer p_y = p_x->m_p_right; p_x->m_p_right = p_y->m_p_left; if (p_y->m_p_left != NULL) p_y->m_p_left->m_p_parent = p_x; p_y->m_p_parent = p_x->m_p_parent; if (p_x == m_p_head->m_p_parent) m_p_head->m_p_parent = p_y; else if (p_x == p_x->m_p_parent->m_p_left) p_x->m_p_parent->m_p_left = p_y; else p_x->m_p_parent->m_p_right = p_y; p_y->m_p_left = p_x; p_x->m_p_parent = p_y; _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) apply_update(p_x, (Node_Update* )this); apply_update(p_x->m_p_parent, (Node_Update* )this); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_right(node_pointer p_x) { node_pointer p_y = p_x->m_p_left; p_x->m_p_left = p_y->m_p_right; if (p_y->m_p_right != NULL) p_y->m_p_right->m_p_parent = p_x; p_y->m_p_parent = p_x->m_p_parent; if (p_x == m_p_head->m_p_parent) m_p_head->m_p_parent = p_y; else if (p_x == p_x->m_p_parent->m_p_right) p_x->m_p_parent->m_p_right = p_y; else p_x->m_p_parent->m_p_left = p_y; p_y->m_p_right = p_x; p_x->m_p_parent = p_y; _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) apply_update(p_x, (Node_Update* )this); apply_update(p_x->m_p_parent, (Node_Update* )this); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rotate_parent(node_pointer p_nd) { node_pointer p_parent = p_nd->m_p_parent; if (p_nd == p_parent->m_p_left) rotate_right(p_parent); else rotate_left(p_parent); _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd); _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || p_nd->m_p_right == p_parent); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer /*p_nd*/, __gnu_pbds::null_node_update* /*p_update*/) { } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: apply_update(node_pointer p_nd, Node_Update_* p_update) { p_update->operator()(& PB_DS_V2F(p_nd->m_value),(p_nd->m_p_left == NULL) ? NULL : & PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == NULL) ? NULL : & PB_DS_V2F(p_nd->m_p_right->m_value)); } PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: update_to_top(node_pointer p_nd, Node_Update_* p_update) { while (p_nd != m_p_head) { apply_update(p_nd, p_update); p_nd = p_nd->m_p_parent; } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update_to_top(node_pointer /*p_nd*/, __gnu_pbds::null_node_update* /*p_update*/) { } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file split_join_branch_bag.hpp * Contains an implementation class for pat_trie_. */ class split_join_branch_bag { private: typedef std::list< internal_node_pointer, typename Allocator::template rebind< internal_node_pointer>::other> bag_t; public: void add_branch() { internal_node_pointer p_nd = s_internal_node_allocator.allocate(1); try { m_bag.push_back(p_nd); } catch(...) { s_internal_node_allocator.deallocate(p_nd, 1); __throw_exception_again; } } internal_node_pointer get_branch() { _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); internal_node_pointer p_nd =* m_bag.begin(); m_bag.pop_front(); return p_nd; } ~split_join_branch_bag() { while (!m_bag.empty()) { internal_node_pointer p_nd =* m_bag.begin(); s_internal_node_allocator.deallocate(p_nd, 1); m_bag.pop_front(); } } inline bool empty() const { return m_bag.empty(); } private: bag_t m_bag; }; // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file head.hpp * Contains a leaf for a patricia tree. */ #ifndef PB_DS_PAT_TRIE_IHEAD_HPP #define PB_DS_PAT_TRIE_IHEAD_HPP #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ pat_trie_head #define PB_DS_BASE_C_DEC \ pat_trie_node_base template struct pat_trie_head : public PB_DS_BASE_C_DEC { private: typedef E_Access_Traits e_access_traits; typedef typename Allocator::template rebind< e_access_traits>::other::const_pointer const_e_access_traits_pointer; typedef typename Allocator::template rebind< PB_DS_BASE_C_DEC>::other::pointer node_pointer; #ifdef _GLIBCXX_DEBUG typedef typename PB_DS_BASE_C_DEC::subtree_debug_info subtree_debug_info; #endif public: pat_trie_head(); #ifdef _GLIBCXX_DEBUG virtual subtree_debug_info assert_valid_imp(const_e_access_traits_pointer p_traits) const; #endif public: node_pointer m_p_min; node_pointer m_p_max; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: pat_trie_head() : PB_DS_BASE_C_DEC(pat_trie_head_node_type) { } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::subtree_debug_info PB_DS_CLASS_C_DEC:: assert_valid_imp(const_e_access_traits_pointer /*p_traits*/) const { _GLIBCXX_DEBUG_ASSERT(false); return subtree_debug_info(); } #endif #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file r_erase_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: actual_erase_node(node_pointer p_z) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); p_z->~node(); s_node_allocator.deallocate(p_z, 1); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: update_min_max_for_erased_node(node_pointer p_z) { if (m_size == 1) { m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; return; } if (m_p_head->m_p_left == p_z) { iterator it(p_z); ++it; m_p_head->m_p_left = it.m_p_nd; } else if (m_p_head->m_p_right == p_z) { iterator it(p_z); --it; m_p_head->m_p_right = it.m_p_nd; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid(true, true);) clear_imp(m_p_head->m_p_parent); m_size = 0; initialize(); _GLIBCXX_DEBUG_ONLY(debug_base::clear();) _GLIBCXX_DEBUG_ONLY(assert_valid(true, true);) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear_imp(node_pointer p_nd) { if (p_nd == NULL) return; clear_imp(p_nd->m_p_left); clear_imp(p_nd->m_p_right); p_nd->~Node(); s_node_allocator.deallocate(p_nd, 1); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file node_base.hpp * Contains a pat_trie_node_base base for a patricia tree. */ #ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP #define PB_DS_PAT_TRIE_NODE_BASE_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ pat_trie_node_base #define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ pat_trie_subtree_debug_info enum pat_trie_node_type { pat_trie_internal_node_type, pat_trie_leaf_node_type, pat_trie_head_node_type }; template struct pat_trie_node_base : public pat_trie_node_metadata_base< Metadata, Allocator> { public: typedef typename Allocator::template rebind< pat_trie_node_base>::other::pointer node_pointer; typedef typename Allocator::template rebind< E_Access_Traits>::other::const_pointer const_e_access_traits_pointer; #ifdef _GLIBCXX_DEBUG typedef std::pair< typename E_Access_Traits::const_iterator, typename E_Access_Traits::const_iterator> subtree_debug_info; #endif pat_trie_node_base(pat_trie_node_type type); #ifdef _GLIBCXX_DEBUG void assert_valid(const_e_access_traits_pointer p_traits) const; virtual subtree_debug_info assert_valid_imp(const_e_access_traits_pointer p_traits) const = 0; #endif node_pointer m_p_parent; const pat_trie_node_type m_type; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: pat_trie_node_base(pat_trie_node_type type) : m_type(type) { } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid(const_e_access_traits_pointer p_traits) const { assert_valid_imp(p_traits); } #endif #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC } // namespace detail } // namespace __gnu_pbds #endif  .X ..<2cc_hash_max_collision_check_resize_trigger_imp.hpp4,hash_load_check_resize_trigger_size_base.hpp0&hash_load_check_resize_trigger_imp.hpp,#hash_standard_resize_policy_imp.hpp sample_resize_policy.hpp sample_size_policy.hpp $sample_resize_trigger.hpp (hash_prime_size_policy_imp.hpp $hash_exponential_size_policy_imp.hpp// -*- C++ -*- // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cc_hash_max_collision_check_resize_trigger_imp.hpp * Contains a resize trigger implementation. */ PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: cc_hash_max_collision_check_resize_trigger(float load) : m_load(load), m_size(0), m_num_col(0), m_max_col(0), m_resize_needed(false) { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_start() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_collision() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_end() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_start() { m_num_col = 0; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_collision() { ++m_num_col; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_end() { calc_resize_needed(); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_start() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_collision() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_end() { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_inserted(size_type) { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erased(size_type) { m_resize_needed = true; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_cleared() { m_resize_needed = false; } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: is_resize_needed() const { return m_resize_needed; } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const { return m_num_col >= m_max_col; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type new_size) { m_size = new_size; #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ std::cerr << "chmccrt::notify_resized " << static_cast(new_size) << std::endl; #endif calc_max_num_coll(); calc_resize_needed(); m_num_col = 0; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: calc_max_num_coll() { // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) } const double ln_arg = 2 * m_size * std::log(double(m_size)); m_max_col = size_type(std::ceil(std::sqrt(2 * m_load * std::log(ln_arg)))); #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ std::cerr << "chmccrt::calc_max_num_coll " << static_cast(m_size) << " " << static_cast(m_max_col) << std::endl; #endif } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_externally_resized(size_type new_size) { notify_resized(new_size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_load, other.m_load); std::swap(m_size, other.m_size); std::swap(m_num_col, other.m_num_col); std::swap(m_max_col, other.m_max_col); std::swap(m_resize_needed, other.m_resize_needed); } PB_DS_CLASS_T_DEC inline float PB_DS_CLASS_C_DEC:: get_load() const { PB_DS_STATIC_ASSERT(access, external_load_access); return m_load; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: calc_resize_needed() { m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: set_load(float load) { PB_DS_STATIC_ASSERT(access, external_load_access); m_load = load; calc_max_num_coll(); calc_resize_needed(); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file hash_load_check_resize_trigger_size_base.hpp * Contains an base holding size for some resize policies. */ #ifndef PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP #define PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP namespace __gnu_pbds { namespace detail { // Primary template. template class hash_load_check_resize_trigger_size_base; // Specializations. template class hash_load_check_resize_trigger_size_base { protected: typedef Size_Type size_type; hash_load_check_resize_trigger_size_base(): m_size(0) { } inline void swap(hash_load_check_resize_trigger_size_base& other) { std::swap(m_size, other.m_size); } inline void set_size(size_type size) { m_size = size; } inline size_type get_size() const { return m_size; } private: size_type m_size; }; template class hash_load_check_resize_trigger_size_base { protected: typedef Size_Type size_type; protected: inline void swap(hash_load_check_resize_trigger_size_base& other) { } inline void set_size(size_type size) { } }; } // namespace detail } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file hash_load_check_resize_trigger_imp.hpp * Contains a resize trigger implementation. */ PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: hash_load_check_resize_trigger(float load_min, float load_max) : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0), m_next_grow_size(0), m_resize_needed(false) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_start() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_collision() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_find_search_end() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_start() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_collision() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_insert_search_end() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_start() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_collision() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erase_search_end() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_inserted(size_type num_entries) { m_resize_needed = (num_entries >= m_next_grow_size); size_base::set_size(num_entries); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: notify_erased(size_type num_entries) { size_base::set_size(num_entries); m_resize_needed = num_entries <= m_next_shrink_size; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: is_resize_needed() const { _GLIBCXX_DEBUG_ONLY(assert_valid();) return m_resize_needed; } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: is_grow_needed(size_type /*size*/, size_type num_entries) const { _GLIBCXX_DEBUG_ASSERT(m_resize_needed); return num_entries >= m_next_grow_size; } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~hash_load_check_resize_trigger() { } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type new_size) { m_resize_needed = false; m_next_grow_size = size_type(m_load_max * new_size - 1); m_next_shrink_size = size_type(m_load_min * new_size); #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ std::cerr << "hlcrt::notify_resized " << static_cast(new_size) << " " << static_cast(m_load_min) << " " << static_cast(m_load_max) << " " << static_cast(m_next_shrink_size) << " " << static_cast(m_next_grow_size) << " " << std::endl; #endif _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_externally_resized(size_type new_size) { m_resize_needed = false; size_type new_grow_size = size_type(m_load_max * new_size - 1); size_type new_shrink_size = size_type(m_load_min * new_size); if (new_grow_size >= m_next_grow_size) { _GLIBCXX_DEBUG_ASSERT(new_shrink_size > m_next_shrink_size); m_next_grow_size = new_grow_size; _GLIBCXX_DEBUG_ONLY(assert_valid();) #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ std::cerr << "hlcrt::notify_externally_resized1 " << static_cast(new_size) << " " << static_cast(m_load_min) << " " << static_cast(m_load_max) << " " << static_cast(m_next_shrink_size) << " " << static_cast(m_next_grow_size) << " " << std::endl; #endif return; } _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size); m_next_shrink_size = new_shrink_size; #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ std::cerr << "hlcrt::notify_externally_resized2 " << static_cast(new_size) << " " << static_cast(m_load_min) << " " << static_cast(m_load_max) << " " << static_cast(m_next_shrink_size) << " " << static_cast(m_next_grow_size) << " " << std::endl; #endif _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_cleared() { _GLIBCXX_DEBUG_ONLY(assert_valid();) size_base::set_size(0); m_resize_needed = (0 < m_next_shrink_size); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) size_base::swap(other); std::swap(m_load_min, other.m_load_min); std::swap(m_load_max, other.m_load_max); std::swap(m_resize_needed, other.m_resize_needed); std::swap(m_next_grow_size, other.m_next_grow_size); std::swap(m_next_shrink_size, other.m_next_shrink_size); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC inline std::pair PB_DS_CLASS_C_DEC:: get_loads() const { PB_DS_STATIC_ASSERT(access, external_load_access); return std::make_pair(m_load_min, m_load_max); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: set_loads(std::pair load_pair) { PB_DS_STATIC_ASSERT(access, external_load_access); const float old_load_min = m_load_min; const float old_load_max = m_load_max; const size_type old_next_shrink_size = m_next_shrink_size; const size_type old_next_grow_size = m_next_grow_size; const bool old_resize_needed = m_resize_needed; try { m_load_min = load_pair.first; m_load_max = load_pair.second; do_resize(static_cast(size_base::get_size() / ((m_load_min + m_load_max) / 2))); } catch(...) { m_load_min = old_load_min; m_load_max = old_load_max; m_next_shrink_size = old_next_shrink_size; m_next_grow_size = old_next_grow_size; m_resize_needed = old_resize_needed; __throw_exception_again; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: do_resize(size_type) { std::abort(); } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { _GLIBCXX_DEBUG_ASSERT(m_load_max > m_load_min); _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= m_next_shrink_size); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file hash_standard_resize_policy_imp.hpp * Contains a resize policy implementation. */ PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: hash_standard_resize_policy() : m_size(Size_Policy::get_nearest_larger_size(1)) { trigger_policy_base::notify_externally_resized(m_size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: hash_standard_resize_policy(const Size_Policy& r_size_policy) : Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1)) { trigger_policy_base::notify_externally_resized(m_size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: hash_standard_resize_policy(const Size_Policy& r_size_policy, const Trigger_Policy& r_trigger_policy) : Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy), m_size(Size_Policy::get_nearest_larger_size(1)) { trigger_policy_base::notify_externally_resized(m_size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~hash_standard_resize_policy() { } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { trigger_policy_base::swap(other); size_policy_base::swap(other); std::swap(m_size, other.m_size); } PB_DS_CL