1e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// -*- C++ -*- 2e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 3e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// Copyright (C) 2005, 2006, 2007, 2009, 2011 Free Software Foundation, Inc. 4e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// 5e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// This file is part of the GNU ISO C++ Library. This library is free 6e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// software; you can redistribute it and/or modify it under the terms 7e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// of the GNU General Public License as published by the Free Software 8e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// Foundation; either version 3, or (at your option) any later 9e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// version. 10e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 11e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// This library is distributed in the hope that it will be useful, but 12e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// WITHOUT ANY WARRANTY; without even the implied warranty of 13e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// General Public License for more details. 15e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 16e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// Under Section 7 of GPL version 3, you are granted additional 17e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// permissions described in the GCC Runtime Library Exception, version 18e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// 3.1, as published by the Free Software Foundation. 19e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 20e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// You should have received a copy of the GNU General Public License and 21e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// a copy of the GCC Runtime Library Exception along with this program; 22e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// <http://www.gnu.org/licenses/>. 24e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 25e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 27e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// Permission to use, copy, modify, sell, and distribute this software 28e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// is hereby granted without fee, provided that the above copyright 29e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// notice appears in all copies, and that both that copyright notice 30e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// and this permission notice appear in supporting documentation. None 31e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// of the above authors, nor IBM Haifa Research Laboratories, make any 32e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// representation about the suitability of this software for any 33e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// purpose. It is provided "as is" without express or implied 34e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh// warranty. 35e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 36e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh/** 37e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh * @file detail/standard_policies.hpp 38e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh * Contains standard policies for containers. 39e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh */ 40e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 41e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#ifndef PB_DS_STANDARD_POLICIES_HPP 42e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#define PB_DS_STANDARD_POLICIES_HPP 43e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 44e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <memory> 45e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/hash_policy.hpp> 46e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/list_update_policy.hpp> 47e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp> 48e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/tree_policy.hpp> 49e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/trie_policy.hpp> 50e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <ext/pb_ds/tag_and_trait.hpp> 51e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#include <tr1/functional> 52e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 53e7de7d971409d955ca138406d5062499bc554451Andrew Hsiehnamespace __gnu_pbds 54e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh{ 55e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh namespace detail 56e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 57e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_hash_fn. 58e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Key> 59e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_hash_fn 60e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 61e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 62e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef std::tr1::hash<Key> type; 63e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 64e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 65e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_eq_fn. 66e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Key> 67e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_eq_fn 68e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 69e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 70e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef std::equal_to<Key> type; 71e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 72e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 73e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Enumeration for default behavior of stored hash data. 74e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh enum 75e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 76e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh default_store_hash = false 77e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 78e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 79e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_comb_hash_fn. 80e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_comb_hash_fn 81e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 82e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 83e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef direct_mask_range_hashing<> type; 84e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 85e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 86e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_resize_policy. 87e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Comb_Hash_Fn> 88e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_resize_policy 89e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 90e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh private: 91e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef typename Comb_Hash_Fn::size_type size_type; 92e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 93e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef direct_mask_range_hashing<size_type> default_fn; 94e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef is_same<default_fn, Comb_Hash_Fn> same_type; 95e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef hash_exponential_size_policy<size_type> iftrue; 96e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef hash_prime_size_policy iffalse; 97e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; 98e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef typename cond_type::__type size_policy_type; 99e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 100e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef hash_load_check_resize_trigger<false, size_type> trigger; 101e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 102e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh public: 103e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 104e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef hash_standard_resize_policy<size_policy_type, trigger, 105e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh false, size_type> type; 106e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 107e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 108e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Default update policy. 109e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_update_policy 110e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 111e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 112e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef lu_move_to_front_policy<> type; 113e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 114e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 115e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_probe_fn. 116e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Comb_Probe_Fn> 117e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_probe_fn 118e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 119e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh private: 120e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef typename Comb_Probe_Fn::size_type size_type; 121e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef direct_mask_range_hashing<size_type> default_fn; 122e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef is_same<default_fn, Comb_Probe_Fn> same_type; 123e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef linear_probe_fn<size_type> iftrue; 124e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef quadratic_probe_fn<size_type> iffalse; 125e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; 126e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 127e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh public: 128e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 129e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef typename cond_type::__type type; 130e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 131e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 132e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 133e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Primary template, default_trie_access_traits. 134e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Key> 135e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_trie_access_traits; 136e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 137e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#define __dtrie_alloc std::allocator<char> 138e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#define __dtrie_string std::basic_string<Char, Char_Traits, __dtrie_alloc> 139e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 140e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Partial specialization, default_trie_access_traits. 141e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh template<typename Char, typename Char_Traits> 142e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh struct default_trie_access_traits<__dtrie_string> 143e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh { 144e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh private: 145e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef __dtrie_string string_type; 146e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 147e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh public: 148e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh /// Dispatched type. 149e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh typedef trie_string_access_traits<string_type> type; 150e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh }; 151e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 152e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#undef __dtrie_alloc 153e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#undef __dtrie_string 154e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 155e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh } // namespace detail 156e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh} // namespace __gnu_pbds 157e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh 158e7de7d971409d955ca138406d5062499bc554451Andrew Hsieh#endif // #ifndef PB_DS_STANDARD_POLICIES_HPP 159