URL
https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk
Subversion Repositories openrisc_2011-10-31
[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc3/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [assoc_container.hpp] - Rev 424
Go to most recent revision | Compare with Previous | Blame | View Log
// -*- C++ -*- // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 3, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // <http://www.gnu.org/licenses/>. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file assoc_container.hpp * Contains associative containers. */ #ifndef PB_DS_ASSOC_CNTNR_HPP #define PB_DS_ASSOC_CNTNR_HPP #include <ext/typelist.h> #include <ext/pb_ds/tag_and_trait.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/detail/container_base_dispatch.hpp> #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp> namespace __gnu_pbds { /** @defgroup pbds Policy-Based Data Structures * @ingroup extensions * * This is a library of policy-based elementary data structures: * associative containers and priority queues. It is designed for * high-performance, flexibility, semantic safety, and conformance * to the corresponding containers in std (except for some points * where it differs by design). * * For details, see: * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html * * @{ */ #define PB_DS_BASE_C_DEC \ detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type /// An abstract basic associative container. template<typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator> class container_base : public PB_DS_BASE_C_DEC { private: typedef typename PB_DS_BASE_C_DEC base_type; public: typedef Tag container_category; typedef Allocator allocator_type; typedef typename allocator_type::size_type size_type; typedef typename allocator_type::difference_type difference_type; // key_type typedef typename allocator_type::template rebind<Key>::other::value_type key_type; typedef typename allocator_type::template rebind<key_type>::other key_rebind; typedef typename key_rebind::reference key_reference; typedef typename key_rebind::const_reference const_key_reference; typedef typename key_rebind::pointer key_pointer; typedef typename key_rebind::const_pointer const_key_pointer; // mapped_type typedef Mapped mapped_type; typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind; typedef typename mapped_rebind::reference mapped_reference; typedef typename mapped_rebind::const_reference const_mapped_reference; typedef typename mapped_rebind::pointer mapped_pointer; typedef typename mapped_rebind::const_pointer const_mapped_pointer; // value_type typedef typename base_type::value_type value_type; typedef typename allocator_type::template rebind<value_type>::other value_rebind; typedef typename value_rebind::reference reference; typedef typename value_rebind::const_reference const_reference; typedef typename value_rebind::pointer pointer; typedef typename value_rebind::const_pointer const_pointer; // iterators typedef typename base_type::iterator iterator; typedef typename base_type::const_iterator const_iterator; typedef typename base_type::point_iterator point_iterator; typedef typename base_type::const_point_iterator const_point_iterator; virtual ~container_base() { } protected: #define PB_DS_CLASS_NAME container_base #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> #undef PB_DS_CLASS_NAME }; #undef PB_DS_BASE_C_DEC #define PB_DS_BASE_C_DEC \ container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \ typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator> /// An abstract basic hash-based associative container. template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, typename Resize_Policy, bool Store_Hash, typename Tag, typename Policy_TL, typename Allocator> class basic_hash_table : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: virtual ~basic_hash_table() { } protected: #define PB_DS_CLASS_NAME basic_hash_table #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> #undef PB_DS_CLASS_NAME private: basic_hash_table& operator=(const base_type&); }; #undef PB_DS_BASE_C_DEC #define PB_DS_BASE_C_DEC \ basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ cc_hash_tag, \ typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator> /// A concrete collision-chaining hash-based associative container. template<typename Key, typename Mapped, typename Hash_Fn = typename detail::default_hash_fn<Key>::type, typename Eq_Fn = typename detail::default_eq_fn<Key>::type, typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type, bool Store_Hash = detail::default_store_hash, typename Allocator = std::allocator<char> > class cc_hash_table : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Resize_Policy resize_policy; typedef Comb_Hash_Fn comb_hash_fn; // Default constructor. cc_hash_table() { } // Constructor taking some policy objects. r_hash_fn will be // copied by the Hash_Fn object of the container object. cc_hash_table(const hash_fn& h) : base_type(h) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, and // r_eq_fn will be copied by the eq_fn object of the container // object. cc_hash_table(const hash_fn& h, const eq_fn& e) : base_type(h, e) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, r_eq_fn // will be copied by the eq_fn object of the container object, and // r_comb_hash_fn will be copied by the comb_hash_fn object of the // container object. cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) : base_type(h, e, ch) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, r_eq_fn // will be copied by the eq_fn object of the container object, // r_comb_hash_fn will be copied by the comb_hash_fn object of the // container object, and r_resize_policy will be copied by the // resize_policy object of the container object. cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, const resize_policy& rp) : base_type(h, e, ch, rp) { } // Constructor taking __iterators to a range of value_types. The // value_types between first_it and last_it will be inserted into // the container object. template<typename It> cc_hash_table(It first, It last) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h) : base_type(h) { copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // and r_eq_fn will be copied by the eq_fn object of the container // object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) : base_type(h, e) { copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // r_eq_fn will be copied by the eq_fn object of the container // object, and r_comb_hash_fn will be copied by the comb_hash_fn // object of the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) : base_type(h, e, ch) { copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // r_eq_fn will be copied by the eq_fn object of the container // object, r_comb_hash_fn will be copied by the comb_hash_fn // object of the container object, and r_resize_policy will be // copied by the resize_policy object of the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, const resize_policy& rp) : base_type(h, e, ch, rp) { copy_from_range(first, last); } cc_hash_table(const cc_hash_table& other) : base_type((const base_type&)other) { } virtual ~cc_hash_table() { } cc_hash_table& operator=(const cc_hash_table& other) { if (this != &other) { cc_hash_table tmp(other); swap(tmp); } return *this; } void swap(cc_hash_table& other) { base_type::swap(other); } }; #undef PB_DS_BASE_C_DEC #define PB_DS_BASE_C_DEC \ basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ gp_hash_tag, \ typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator> /// A concrete general-probing hash-based associative container. template<typename Key, typename Mapped, typename Hash_Fn = typename detail::default_hash_fn<Key>::type, typename Eq_Fn = typename detail::default_eq_fn<Key>::type, typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type, typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type, bool Store_Hash = detail::default_store_hash, typename Allocator = std::allocator<char> > class gp_hash_table : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Comb_Probe_Fn comb_probe_fn; typedef Probe_Fn probe_fn; typedef Resize_Policy resize_policy; // Default constructor. gp_hash_table() { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object. gp_hash_table(const hash_fn& h) : base_type(h) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, and // r_eq_fn will be copied by the eq_fn object of the container // object. gp_hash_table(const hash_fn& h, const eq_fn& e) : base_type(h, e) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, r_eq_fn // will be copied by the eq_fn object of the container object, and // r_comb_probe_fn will be copied by the comb_probe_fn object of // the container object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) : base_type(h, e, cp) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, r_eq_fn // will be copied by the eq_fn object of the container object, // r_comb_probe_fn will be copied by the comb_probe_fn object of // the container object, and r_probe_fn will be copied by the // probe_fn object of the container object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p) : base_type(h, e, cp, p) { } // Constructor taking some policy objects. r_hash_fn will be // copied by the hash_fn object of the container object, r_eq_fn // will be copied by the eq_fn object of the container object, // r_comb_probe_fn will be copied by the comb_probe_fn object of // the container object, r_probe_fn will be copied by the probe_fn // object of the container object, and r_resize_policy will be // copied by the Resize_Policy object of the container object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p, const resize_policy& rp) : base_type(h, e, cp, p, rp) { } // Constructor taking __iterators to a range of value_types. The // value_types between first_it and last_it will be inserted into // the container object. template<typename It> gp_hash_table(It first, It last) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h) : base_type(h) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // and r_eq_fn will be copied by the eq_fn object of the container // object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) : base_type(h, e) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // r_eq_fn will be copied by the eq_fn object of the container // object, and r_comb_probe_fn will be copied by the comb_probe_fn // object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) : base_type(h, e, cp) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // r_eq_fn will be copied by the eq_fn object of the container // object, r_comb_probe_fn will be copied by the comb_probe_fn // object of the container object, and r_probe_fn will be copied // by the probe_fn object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p) : base_type(h, e, cp, p) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. r_hash_fn // will be copied by the hash_fn object of the container object, // r_eq_fn will be copied by the eq_fn object of the container // object, r_comb_probe_fn will be copied by the comb_probe_fn // object of the container object, r_probe_fn will be copied by // the probe_fn object of the container object, and // r_resize_policy will be copied by the resize_policy object of // the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p, const resize_policy& rp) : base_type(h, e, cp, p, rp) { base_type::copy_from_range(first, last); } gp_hash_table(const gp_hash_table& other) : base_type((const base_type&)other) { } virtual ~gp_hash_table() { } gp_hash_table& operator=(const gp_hash_table& other) { if (this != &other) { gp_hash_table tmp(other); swap(tmp); } return *this; } void swap(gp_hash_table& other) { base_type::swap(other); } }; #undef PB_DS_BASE_C_DEC #define PB_DS_BASE_C_DEC \ container_base<Key, Mapped, Tag, Policy_Tl, Allocator> /// An abstract basic tree-like (tree, trie) associative container. template<typename Key, typename Mapped, typename Tag, typename Node_Update, typename Policy_Tl, typename Allocator> class basic_tree : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: typedef Node_Update node_update; virtual ~basic_tree() { } protected: #define PB_DS_CLASS_NAME basic_tree #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> #undef PB_DS_CLASS_NAME }; #undef PB_DS_BASE_C_DEC #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \ detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator> #define PB_DS_BASE_C_DEC \ basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \ typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator> /// A concrete basic tree-based associative container. template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, typename Tag = rb_tree_tag, template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_> class Node_Update = __gnu_pbds::null_tree_node_update, typename Allocator = std::allocator<char> > class tree : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: // Comparison functor type. typedef Cmp_Fn cmp_fn; tree() { } // Constructor taking some policy objects. r_cmp_fn will be copied // by the Cmp_Fn object of the container object. tree(const cmp_fn& c) : base_type(c) { } // Constructor taking __iterators to a range of value_types. The // value_types between first_it and last_it will be inserted into // the container object. template<typename It> tree(It first, It last) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects The value_types between first_it and // last_it will be inserted into the container object. r_cmp_fn // will be copied by the cmp_fn object of the container object. template<typename It> tree(It first, It last, const cmp_fn& c) : base_type(c) { base_type::copy_from_range(first, last); } tree(const tree& other) : base_type((const base_type&)other) { } virtual ~tree() { } tree& operator=(const tree& other) { if (this != &other) { tree tmp(other); swap(tmp); } return *this; } void swap(tree& other) { base_type::swap(other); } }; #undef PB_DS_BASE_C_DEC #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \ detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator> #define PB_DS_BASE_C_DEC \ basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \ typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator> /// A concrete basic trie-based associative container. template<typename Key, typename Mapped, typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type, typename Tag = pat_trie_tag, template<typename Const_Node_Iterator, typename Node_Iterator, typename E_Access_Traits_, typename Allocator_> class Node_Update = null_trie_node_update, typename Allocator = std::allocator<char> > class trie : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: // Element access traits type. typedef E_Access_Traits e_access_traits; trie() { } // Constructor taking some policy objects. r_e_access_traits will // be copied by the E_Access_Traits object of the container // object. trie(const e_access_traits& t) : base_type(t) { } // Constructor taking __iterators to a range of value_types. The // value_types between first_it and last_it will be inserted into // the container object. template<typename It> trie(It first, It last) { base_type::copy_from_range(first, last); } // Constructor taking __iterators to a range of value_types and // some policy objects. The value_types between first_it and // last_it will be inserted into the container object. template<typename It> trie(It first, It last, const e_access_traits& t) : base_type(t) { base_type::copy_from_range(first, last); } trie(const trie& other) : base_type((const base_type&)other) { } virtual ~trie() { } trie& operator=(const trie& other) { if (this != &other) { trie tmp(other); swap(tmp); } return *this; } void swap(trie& other) { base_type::swap(other); } }; #undef PB_DS_BASE_C_DEC #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS #define PB_DS_BASE_C_DEC \ container_base<Key, Mapped, list_update_tag, \ typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator> /// A list-update based associative container. template<typename Key, typename Mapped, class Eq_Fn = typename detail::default_eq_fn<Key>::type, class Update_Policy = detail::default_update_policy::type, class Allocator = std::allocator<char> > class list_update : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: typedef Eq_Fn eq_fn; typedef Update_Policy update_policy; typedef Allocator allocator; list_update() { } // Constructor taking __iterators to a range of value_types. The // value_types between first_it and last_it will be inserted into // the container object. template<typename It> list_update(It first, It last) { base_type::copy_from_range(first, last); } list_update(const list_update& other) : base_type((const base_type&)other) { } virtual ~list_update() { } list_update& operator=(const list_update& other) { if (this !=& other) { list_update tmp(other); swap(tmp); } return *this; } void swap(list_update& other) { base_type::swap(other); } }; #undef PB_DS_BASE_C_DEC // @} group pbds } // namespace __gnu_pbds #endif
Go to most recent revision | Compare with Previous | Blame | View Log