libstdc++
standard_policies.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2009, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file detail/standard_policies.hpp
00038  * Contains standard policies for containers.
00039  */
00040 
00041 #ifndef PB_DS_STANDARD_POLICIES_HPP
00042 #define PB_DS_STANDARD_POLICIES_HPP
00043 
00044 #include <memory>
00045 #include <ext/pb_ds/hash_policy.hpp>
00046 #include <ext/pb_ds/list_update_policy.hpp>
00047 #include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp>
00048 #include <ext/pb_ds/tree_policy.hpp>
00049 #include <ext/pb_ds/trie_policy.hpp>
00050 #include <ext/pb_ds/tag_and_trait.hpp>
00051 #include <tr1/functional>
00052 
00053 namespace __gnu_pbds
00054 {
00055   namespace detail
00056   {
00057     /// Primary template, default_hash_fn.
00058     template<typename Key>
00059     struct default_hash_fn
00060     {
00061     /// Dispatched type.
00062       typedef std::tr1::hash<Key>               type;
00063     };
00064 
00065     /// Primary template, default_eq_fn.
00066     template<typename Key>
00067     struct default_eq_fn
00068     {
00069     /// Dispatched type.
00070       typedef std::equal_to<Key>                type;
00071     };
00072 
00073     /// Enumeration for default behavior of stored hash data.
00074     enum
00075       {
00076     default_store_hash = false
00077       };
00078 
00079     /// Primary template, default_comb_hash_fn.
00080     struct default_comb_hash_fn
00081     {
00082     /// Dispatched type.
00083       typedef direct_mask_range_hashing<>           type;
00084     };
00085 
00086     /// Primary template, default_resize_policy.
00087     template<typename Comb_Hash_Fn>
00088     struct default_resize_policy
00089     {
00090     private:
00091       typedef typename Comb_Hash_Fn::size_type          size_type;
00092 
00093       typedef direct_mask_range_hashing<size_type>      default_fn;
00094       typedef is_same<default_fn, Comb_Hash_Fn>         same_type;
00095       typedef hash_exponential_size_policy<size_type>       iftrue;
00096       typedef hash_prime_size_policy                iffalse;
00097       typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
00098       typedef typename cond_type::__type               size_policy_type;
00099 
00100       typedef hash_load_check_resize_trigger<false, size_type>  trigger;
00101 
00102     public:
00103     /// Dispatched type.
00104       typedef hash_standard_resize_policy<size_policy_type, trigger, 
00105                       false, size_type>     type;
00106     };
00107 
00108     /// Default update policy.
00109     struct default_update_policy
00110     {
00111     /// Dispatched type.
00112       typedef lu_move_to_front_policy<>             type;
00113     };
00114 
00115     /// Primary template, default_probe_fn.
00116     template<typename Comb_Probe_Fn>
00117     struct default_probe_fn
00118     {
00119     private:
00120       typedef typename Comb_Probe_Fn::size_type         size_type;
00121       typedef direct_mask_range_hashing<size_type>      default_fn;
00122       typedef is_same<default_fn, Comb_Probe_Fn>        same_type;
00123       typedef linear_probe_fn<size_type>            iftrue;
00124       typedef quadratic_probe_fn<size_type>             iffalse;
00125       typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
00126 
00127     public:
00128     /// Dispatched type.
00129       typedef typename cond_type::__type            type;
00130     };
00131 
00132 
00133     /// Primary template, default_trie_access_traits.
00134     template<typename Key>
00135       struct default_trie_access_traits;
00136 
00137 #define __dtrie_alloc std::allocator<char>  
00138 #define __dtrie_string std::basic_string<Char, Char_Traits, __dtrie_alloc> 
00139 
00140     /// Partial specialization, default_trie_access_traits.
00141     template<typename Char, typename Char_Traits>
00142       struct default_trie_access_traits<__dtrie_string>
00143       {
00144       private:
00145     typedef __dtrie_string                  string_type;
00146 
00147       public:
00148     /// Dispatched type.
00149     typedef trie_string_access_traits<string_type>      type;
00150       };
00151 
00152 #undef __dtrie_alloc
00153 #undef __dtrie_string
00154 
00155   } // namespace detail
00156 } // namespace __gnu_pbds
00157 
00158 #endif // #ifndef PB_DS_STANDARD_POLICIES_HPP