eter), and requests that hash * values not be stored. **/ template class ranged_hash_fn : public null_hash_fn, public Comb_Hash_Fn { protected: typedef typename Allocator::size_type size_type; typedef Comb_Hash_Fn comb_hash_fn_base; ranged_hash_fn(size_type); ranged_hash_fn(size_type, const Comb_Hash_Fn&); ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); void swap(PB_DS_CLASS_C_DEC&); }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) : Comb_Hash_Fn(r_comb_hash_fn) { } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) : Comb_Hash_Fn(r_comb_hash_fn) { } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_hash_fn_base::swap(other); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ ranged_hash_fn /** * Specialization 4 * The client does not supply a hash function (by specifying * null_hash_fn as the Hash_Fn parameter), and requests that hash * values be stored. **/ template class ranged_hash_fn : public null_hash_fn, public Comb_Hash_Fn { protected: typedef typename Allocator::size_type size_type; typedef Comb_Hash_Fn comb_hash_fn_base; ranged_hash_fn(size_type); ranged_hash_fn(size_type, const Comb_Hash_Fn&); ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); void swap(PB_DS_CLASS_C_DEC&); }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) : Comb_Hash_Fn(r_comb_hash_fn) { } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) : Comb_Hash_Fn(r_comb_hash_fn) { } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_hash_fn_base::swap(other); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_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 ranged_probe_fn.hpp * Contains a unified ranged probe functor, allowing the probe tables to deal with * a single class for ranged probeing. */ #ifndef PB_DS_RANGED_PROBE_FN_HPP #define PB_DS_RANGED_PROBE_FN_HPP #include #include #include namespace __gnu_pbds { namespace detail { template class ranged_probe_fn; #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ ranged_probe_fn /** * Specialization 1 * The client supplies a probe function and a ranged probe * function, and requests that hash values not be stored. **/ template class ranged_probe_fn : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn { protected: typedef typename Allocator::size_type size_type; typedef Comb_Probe_Fn comb_probe_fn_base; typedef Hash_Fn hash_fn_base; typedef Probe_Fn probe_fn_base; typedef typename Allocator::template rebind::other key_allocator; typedef typename key_allocator::const_reference const_key_reference; ranged_probe_fn(size_type); ranged_probe_fn(size_type, const Hash_Fn&); ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, const Probe_Fn&); void swap(PB_DS_CLASS_C_DEC&); void notify_resized(size_type); inline size_type operator()(const_key_reference) const; inline size_type operator()(const_key_reference, size_type, size_type) const; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size) { Comb_Probe_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) : Hash_Fn(r_hash_fn) { Comb_Probe_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn) : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_probe_fn_base::swap(other); std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(const_key_reference r_key) const { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(const_key_reference, size_type hash, size_type i) const { return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ ranged_probe_fn /** * Specialization 2- The client supplies a probe function and a ranged * probe function, and requests that hash values not be stored. **/ template class ranged_probe_fn : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn { protected: typedef typename Allocator::size_type size_type; typedef std::pair comp_hash; typedef Comb_Probe_Fn comb_probe_fn_base; typedef Hash_Fn hash_fn_base; typedef Probe_Fn probe_fn_base; typedef typename Allocator::template rebind::other key_allocator; typedef typename key_allocator::const_reference const_key_reference; ranged_probe_fn(size_type); ranged_probe_fn(size_type, const Hash_Fn&); ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, const Probe_Fn&); void swap(PB_DS_CLASS_C_DEC&); void notify_resized(size_type); inline comp_hash operator()(const_key_reference) const; inline size_type operator()(const_key_reference, size_type, size_type) const; inline size_type operator()(const_key_reference, size_type) const; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size) { Comb_Probe_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) : Hash_Fn(r_hash_fn) { Comb_Probe_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn) : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_probe_fn_base::swap(other); std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { comb_probe_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::comp_hash PB_DS_CLASS_C_DEC:: operator()(const_key_reference r_key) const { const size_type hash = hash_fn_base::operator()(r_key); return std::make_pair(comb_probe_fn_base::operator()(hash), hash); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(const_key_reference, size_type hash, size_type i) const { return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator() #ifdef _GLIBCXX_DEBUG (const_key_reference r_key, size_type hash) const #else (const_key_reference /*r_key*/, size_type hash) const #endif { _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); return hash; } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC /** * Specialization 3 and 4 * The client does not supply a hash function or probe function, * and requests that hash values not be stored. **/ template class ranged_probe_fn : public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn { protected: typedef typename Allocator::size_type size_type; typedef Comb_Probe_Fn comb_probe_fn_base; typedef typename Allocator::template rebind::other key_allocator; typedef typename key_allocator::const_reference const_key_reference; ranged_probe_fn(size_type size) { Comb_Probe_Fn::notify_resized(size); } ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) : Comb_Probe_Fn(r_comb_probe_fn) { } ranged_probe_fn(size_type, const null_hash_fn&, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn&) : Comb_Probe_Fn(r_comb_probe_fn) { } void swap(ranged_probe_fn& other) { comb_probe_fn_base::swap(other); } }; } // 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 debug_map_base.hpp * Contains a debug-mode base for all maps. */ #ifndef PB_DS_DEBUG_MAP_BASE_HPP #define PB_DS_DEBUG_MAP_BASE_HPP #ifdef _GLIBCXX_DEBUG #include #include #include #include #include namespace __gnu_pbds { namespace detail { // Need std::pair ostream extractor. template inline std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& __out, const std::pair<_Tp1, _Tp2>& p) { return (__out << '(' << p.first << ',' << p.second << ')'); } #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ debug_map_base template class debug_map_base { private: typedef typename std::allocator< Key> key_allocator; typedef typename key_allocator::size_type size_type; typedef Const_Key_Reference const_key_reference; protected: debug_map_base(); debug_map_base(const PB_DS_CLASS_C_DEC& other); ~debug_map_base(); inline void insert_new(const_key_reference r_key); inline void erase_existing(const_key_reference r_key); void clear(); inline void check_key_exists(const_key_reference r_key) const; inline void check_key_does_not_exist(const_key_reference r_key) const; inline void check_size(size_type size) const; void swap(PB_DS_CLASS_C_DEC& other); template void split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&); void join(PB_DS_CLASS_C_DEC& other); private: typedef std::list< Key> key_set; typedef typename key_set::iterator key_set_iterator; typedef typename key_set::const_iterator const_key_set_iterator; #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif const_key_set_iterator find(const_key_reference r_key) const; key_set_iterator find(const_key_reference r_key); key_set m_key_set; Eq_Fn m_eq; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: debug_map_base() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: debug_map_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~debug_map_base() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: insert_new(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) __gnu_cxx::throw_allocator alloc; const double orig_throw_prob = alloc.get_throw_prob(); alloc.set_throw_prob(0); if (find(r_key) != m_key_set.end()) { std::cerr << "insert_new" << r_key << std::endl; std::abort(); } try { m_key_set.push_back(r_key); } catch(...) { std::cerr << "insert_new" << r_key << std::endl; std::abort(); } alloc.set_throw_prob(orig_throw_prob); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: erase_existing(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) key_set_iterator it = find(r_key); if (it == m_key_set.end()) { std::cerr << "erase_existing" << r_key << std::endl; std::abort(); } m_key_set.erase(it); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { _GLIBCXX_DEBUG_ONLY(assert_valid();) m_key_set.clear(); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: check_key_exists(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (find(r_key) == m_key_set.end()) { std::cerr << "check_key_exists" << r_key << std::endl; std::abort(); } _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: check_key_does_not_exist(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) if (find(r_key) != m_key_set.end()) { using std::cerr; using std::endl; cerr << "check_key_does_not_exist" << r_key << endl; std::abort(); } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: check_size(size_type size) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) const size_type key_set_size = m_key_set.size(); if (size != key_set_size) { std::cerr << "check_size " << size << " " << key_set_size << std::endl; std::abort(); } _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();) m_key_set.swap(other.m_key_set); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_key_set_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) typedef const_key_set_iterator iterator_type; for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it) if (m_eq(*it, r_key)) return it; return m_key_set.end(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::key_set_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) key_set_iterator it = m_key_set.begin(); while (it != m_key_set.end()) { if (m_eq(*it, r_key)) return it; ++it; } return it; _GLIBCXX_DEBUG_ONLY(assert_valid();) } #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { const_key_set_iterator prime_it = m_key_set.begin(); while (prime_it != m_key_set.end()) { const_key_set_iterator sec_it = prime_it; ++sec_it; while (sec_it != m_key_set.end()) { _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it)); _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it)); ++sec_it; } ++prime_it; } } #endif PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other) { __gnu_cxx::throw_allocator alloc; const double orig_throw_prob = alloc.get_throw_prob(); alloc.set_throw_prob(0); other.clear(); key_set_iterator it = m_key_set.begin(); while (it != m_key_set.end()) if (cmp_fn(r_key, * it)) { other.insert_new(*it); it = m_key_set.erase(it); } else ++it; alloc.set_throw_prob(orig_throw_prob); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { __gnu_cxx::throw_allocator alloc; const double orig_throw_prob = alloc.get_throw_prob(); alloc.set_throw_prob(0); key_set_iterator it = other.m_key_set.begin(); while (it != other.m_key_set.end()) { insert_new(*it); it = other.m_key_set.erase(it); } _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty()); alloc.set_throw_prob(orig_throw_prob); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC } // namespace detail } // namespace __gnu_pbds #endif #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 standard_policies.hpp * Contains standard policies for containers. */ #ifndef PB_DS_STANDARD_POLICIES_HPP #define PB_DS_STANDARD_POLICIES_HPP #include #include #include #include #include #include #include #include namespace __gnu_pbds { namespace detail { template struct default_hash_fn { typedef std::tr1::hash type; }; template struct default_eq_fn { typedef std::equal_to type; }; enum { default_store_hash = false }; struct default_comb_hash_fn { typedef __gnu_pbds::direct_mask_range_hashing<> type; }; template struct default_resize_policy { private: typedef typename Comb_Hash_Fn::size_type size_type; typedef __gnu_pbds::direct_mask_range_hashing default_fn; typedef is_same same_type; typedef __gnu_pbds::hash_exponential_size_policy iftrue; typedef __gnu_pbds::hash_prime_size_policy iffalse; typedef __conditional_type cond_type; typedef typename cond_type::__type size_policy_type; typedef __gnu_pbds::hash_load_check_resize_trigger trigger; public: typedef __gnu_pbds::hash_standard_resize_policy type; }; struct default_update_policy { typedef __gnu_pbds::move_to_front_lu_policy<> type; }; template struct default_probe_fn { private: typedef typename Comb_Probe_Fn::size_type size_type; typedef __gnu_pbds::direct_mask_range_hashing default_fn; typedef is_same same_type; typedef __gnu_pbds::linear_probe_fn iftrue; typedef __gnu_pbds::quadratic_probe_fn iffalse; typedef __conditional_type cond_type; public: typedef typename cond_type::__type type; }; template struct default_trie_e_access_traits; template struct default_trie_e_access_traits > > { private: typedef std::basic_string > string_type; public: typedef __gnu_pbds::string_trie_e_access_traits type; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_STANDARD_POLICIES_HPP á .X ..â$node_metadata_selector.hppã order_statistics_imp.hppä$sample_tree_node_update.hppå€null_node_update_imp.hpp// -*- 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_metadata_selector.hpp * Contains an implementation class for trees. */ #ifndef PB_DS_TREE_NODE_METADATA_SELECTOR_HPP #define PB_DS_TREE_NODE_METADATA_SELECTOR_HPP #include #include namespace __gnu_pbds { namespace detail { template struct tree_metadata_helper { typedef typename Node_Update::metadata_type type; }; template struct tree_metadata_helper< Node_Update, true> { typedef null_node_metadata type; }; template class Node_Update, class Allocator> struct tree_node_metadata_selector { private: typedef dumconst_node_iterator< Key, Data, Allocator> dumconst_node_it; enum { null_update = is_same< Node_Update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator>, null_tree_node_update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator> >::value }; public: typedef typename tree_metadata_helper< Node_Update< dumconst_node_it, dumconst_node_it, Cmp_Fn, Allocator>, null_update>::type type; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_TREE_NODE_METADATA_SELECTOR_HPP // -*- 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 order_statistics_imp.hpp * Contains forward declarations for order_statistics_key */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: find_by_order(size_type order) { node_iterator it = node_begin(); node_iterator end_it = node_end(); while (it != end_it) { node_iterator l_it = it.get_l_child(); const size_type o = (l_it == end_it)? 0 : l_it.get_metadata(); if (order == o) return (*it); else if (order < o) it = l_it; else { order -= o + 1; it = it.get_r_child(); } } return (PB_DS_BASE_C_DEC::end_iterator()); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: find_by_order(size_type order) const { return (const_cast(this)->find_by_order(order)); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: order_of_key(const_key_reference r_key) const { const_node_iterator it = node_begin(); const_node_iterator end_it = node_end(); const cmp_fn& r_cmp_fn = const_cast(this)->get_cmp_fn(); size_type ord = 0; while (it != end_it) { const_node_iterator l_it = it.get_l_child(); if (r_cmp_fn(r_key, extract_key(*(*it)))) it = l_it; else if (r_cmp_fn(extract_key(*(*it)), r_key)) { ord += (l_it == end_it)? 1 : 1 + l_it.get_metadata(); it = it.get_r_child(); } else { ord += (l_it == end_it)? 0 : l_it.get_metadata(); it = end_it; } } return (ord); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: operator()(node_iterator node_it, const_node_iterator end_nd_it) const { node_iterator l_child_it = node_it.get_l_child(); const size_type l_rank =(l_child_it == end_nd_it)? 0 : l_child_it.get_metadata(); node_iterator r_child_it = node_it.get_r_child(); const size_type r_rank =(r_child_it == end_nd_it)? 0 : r_child_it.get_metadata(); const_cast(node_it.get_metadata())= 1 + l_rank + r_rank; } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~tree_order_statistics_node_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 sample_tree_node_update.hpp * Contains a samle node update functor. */ #ifndef PB_DS_SAMPLE_TREE_NODE_UPDATOR_HPP #define PB_DS_SAMPLE_TREE_NODE_UPDATOR_HPP // A sample node updator. template class sample_tree_node_update { public: // Metadata type. typedef size_t metadata_type; protected: // Default constructor. sample_tree_node_update(); // Updates the rank of a node through a node_iterator node_it; end_nd_it is the end node iterator. inline void operator()(node_iterator node_it, const_node_iterator end_nd_it) const; }; #endif // #ifndef PB_DS_SAMPLE_TREE_NODE_UPDATOR_HPP // -*- 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 null_node_update_imp.hpp * Contains an implementation of null_node_update. */ PB_DS_CLASS_T_DEC template inline void PB_DS_CLASS_C_DEC:: swap(null_tree_node_update< Const_Node_Iterator_, Node_Iterator_, Cmp_Fn_, Allocator_>& /*other*/) { } æ .X ..çchild_iterator.hppènode_iterators.hppé$cond_dtor_entry_dealtor.hppêupdate_fn_imps.hppëleaf.hppìinfo_fn_imps.hppítrace_fn_imps.hppî$policy_access_fn_imps.hppï$synth_e_access_traits.hppðsplit_fn_imps.hppñfind_fn_imps.hppò,#constructors_destructor_fn_imps.hppópoint_iterators.hppôdebug_fn_imps.hppõ node_metadata_base.hppö pat_trie_.hpp÷erase_fn_imps.hppø traits.hppùinternal_node.hppú const_child_iterator.hppû iterators_fn_imps.hppü insert_join_fn_imps.hppýrotate_fn_imps.hppþ$split_join_branch_bag.hppÿhead.hppr_erase_fn_imps.hppü node_base.hpp// -*- 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 child_iterator.hpp * Contains a iterator for a patricia tree. */ struct iterator : public const_iterator { public: typedef std::forward_iterator_tag iterator_category; typedef typename Allocator::difference_type difference_type; typedef node_pointer value_type; typedef node_pointer_pointer pointer; typedef node_pointer_reference reference; inline iterator(node_pointer_pointer p_p_cur = NULL, node_pointer_pointer p_p_end = NULL) : const_iterator(p_p_cur, p_p_end) { } inline bool operator==(const iterator& other) const { return const_iterator::m_p_p_cur == other.m_p_p_cur; } inline bool operator!=(const iterator& other) const { return const_iterator::m_p_p_cur != other.m_p_p_cur; } inline iterator& operator++() { const_iterator::operator++(); return *this; } inline iterator operator++(int) { iterator ret_it(*this); operator++(); return ret_it; } node_pointer_pointer operator->() { _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) return const_iterator::m_p_p_cur; } node_pointer operator*() { _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) return *const_iterator::m_p_p_cur; } }; // -*- 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_iterators.hpp * Contains an implementation class for pat_trie_. */ #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP #define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP #include namespace __gnu_pbds { namespace detail { #define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \ pat_trie_const_node_it_< \ Node, \ Leaf, \ Head, \ Internal_Node, \ Const_Iterator, \ Iterator, \ E_Access_Traits, \ Allocator> #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ pat_trie_node_it_< \ Node, \ Leaf, \ Head, \ Internal_Node, \ Const_Iterator, \ Iterator, \ E_Access_Traits, \ Allocator> // Const node iterator. template class pat_trie_const_node_it_ { protected: typedef typename Allocator::template rebind< Node>::other::pointer node_pointer; typedef typename Allocator::template rebind< Leaf>::other::const_pointer const_leaf_pointer; typedef typename Allocator::template rebind< Leaf>::other::pointer leaf_pointer; typedef typename Allocator::template rebind< Internal_Node>::other::pointer internal_node_pointer; typedef typename Allocator::template rebind< Internal_Node>::other::const_pointer const_internal_node_pointer; typedef typename Allocator::template rebind< E_Access_Traits>::other::const_pointer const_e_access_traits_pointer; private: inline typename E_Access_Traits::const_iterator pref_begin() const { if (m_p_nd->m_type == pat_trie_leaf_node_type) return (m_p_traits->begin( m_p_traits->extract_key( static_cast(m_p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); return (static_cast(m_p_nd)->pref_b_it()); } inline typename E_Access_Traits::const_iterator pref_end() const { if (m_p_nd->m_type == pat_trie_leaf_node_type) return (m_p_traits->end( m_p_traits->extract_key( static_cast(m_p_nd)->value()))); _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); return (static_cast(m_p_nd)->pref_e_it()); } public: // Size type. typedef typename Allocator::size_type size_type; // Category. typedef trivial_iterator_tag iterator_category; // Difference type. typedef trivial_iterator_difference_type difference_type; // __Iterator's value type. typedef Const_Iterator value_type; // __Iterator's reference type. typedef value_type reference; // __Iterator's __const reference type. typedef value_type const_reference; // Element access traits. typedef E_Access_Traits e_access_traits; // A key's element __const iterator. typedef typename e_access_traits::const_iterator const_e_iterator; // Metadata type. typedef typename Node::metadata_type metadata_type; // Const metadata reference type. typedef typename Allocator::template rebind< metadata_type>::other::const_reference const_metadata_reference; // Default constructor. /* inline pat_trie_const_node_it_() */ inline pat_trie_const_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : m_p_nd(const_cast(p_nd)), m_p_traits(p_traits) { } // Subtree valid prefix. inline std::pair valid_prefix() const { return std::make_pair(pref_begin(), pref_end()); } // Const access; returns the __const iterator* associated with // the current leaf. inline const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(num_children() == 0); return Const_Iterator(m_p_nd); } // Metadata access. inline const_metadata_reference get_metadata() const { return m_p_nd->get_metadata(); } // Returns the number of children in the corresponding node. inline size_type num_children() const { if (m_p_nd->m_type == pat_trie_leaf_node_type) return 0; _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); return std::distance(static_cast(m_p_nd)->begin(), static_cast(m_p_nd)->end()); } // Returns a __const node __iterator to the corresponding node's // i-th child. PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC get_child(size_type i) const { _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); typename Internal_Node::iterator it = static_cast(m_p_nd)->begin(); std::advance(it, i); return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits); } // Compares content to a different iterator object. inline bool operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const { return (m_p_nd == other.m_p_nd); } // Compares content (negatively) to a different iterator object. inline bool operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const { return m_p_nd != other.m_p_nd; } private: friend class PB_DS_CLASS_C_DEC; public: node_pointer m_p_nd; const_e_access_traits_pointer m_p_traits; }; // Node iterator. template class pat_trie_node_it_ : public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC { private: typedef typename Allocator::template rebind< Node>::other::pointer node_pointer; typedef Iterator iterator; typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type; typedef typename base_type::const_e_access_traits_pointer const_e_access_traits_pointer; typedef typename base_type::internal_node_pointer internal_node_pointer; public: // Size type. typedef typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type size_type; // __Iterator's value type. typedef Iterator value_type; // __Iterator's reference type. typedef value_type reference; // __Iterator's __const reference type. typedef value_type const_reference; // Default constructor. /* inline pat_trie_node_it_() ; */ inline pat_trie_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits) { } // Access; returns the iterator* associated with the current leaf. inline reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); return Iterator(base_type::m_p_nd); } // Returns a node __iterator to the corresponding node's i-th child. PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC get_child(size_type i) const { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); typename Internal_Node::iterator it = static_cast(base_type::m_p_nd)->begin(); std::advance(it, i); return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits); } private: friend class PB_DS_CLASS_C_DEC; }; #undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC #undef PB_DS_PAT_TRIE_NODE_ITERATOR_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 cond_dtor_entry_dealtor.hpp * Contains a binary tree container conditional deallocator */ class cond_dealtor { public: inline cond_dealtor(leaf_pointer p_nd) : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) { } inline void set_no_action_dtor() { m_no_action_dtor = true; } inline void set_call_destructor() { m_call_destructor = true; } inline ~cond_dealtor() { if (m_no_action_dtor) return; if (m_call_destructor) m_p_nd->~leaf(); s_leaf_allocator.deallocate(m_p_nd, 1); } protected: leaf_pointer m_p_nd; bool m_no_action_dtor; bool m_call_destructor; }; // -*- 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