111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2005-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Permission to use, copy, modify, sell, and distribute this software 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// is hereby granted without fee, provided that the above copyright 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// notice appears in all copies, and that both that copyright notice 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// and this permission notice appear in supporting documentation. None 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the above authors, nor IBM Haifa Research Laboratories, make any 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// representation about the suitability of this software for any 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// purpose. It is provided "as is" without express or implied 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// warranty. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @file detail/standard_policies.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains standard policies for containers. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef PB_DS_STANDARD_POLICIES_HPP 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_STANDARD_POLICIES_HPP 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <memory> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/hash_policy.hpp> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/list_update_policy.hpp> 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp> 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tree_policy.hpp> 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/trie_policy.hpp> 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tag_and_trait.hpp> 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <tr1/functional> 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_hash_fn. 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key> 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_hash_fn 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::tr1::hash<Key> type; 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_eq_fn. 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key> 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_eq_fn 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::equal_to<Key> type; 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Enumeration for default behavior of stored hash data. 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert enum 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default_store_hash = false 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_comb_hash_fn. 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_comb_hash_fn 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef direct_mask_range_hashing<> type; 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_resize_policy. 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Comb_Hash_Fn> 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_resize_policy 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename Comb_Hash_Fn::size_type size_type; 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef direct_mask_range_hashing<size_type> default_fn; 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef is_same<default_fn, Comb_Hash_Fn> same_type; 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef hash_exponential_size_policy<size_type> iftrue; 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef hash_prime_size_policy iffalse; 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename cond_type::__type size_policy_type; 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef hash_load_check_resize_trigger<false, size_type> trigger; 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef hash_standard_resize_policy<size_policy_type, trigger, 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert false, size_type> type; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Default update policy. 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_update_policy 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef lu_move_to_front_policy<> type; 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_probe_fn. 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Comb_Probe_Fn> 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_probe_fn 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename Comb_Probe_Fn::size_type size_type; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef direct_mask_range_hashing<size_type> default_fn; 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef is_same<default_fn, Comb_Probe_Fn> same_type; 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef linear_probe_fn<size_type> iftrue; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef quadratic_probe_fn<size_type> iffalse; 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename cond_type::__type type; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Primary template, default_trie_access_traits. 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key> 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_trie_access_traits; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define __dtrie_alloc std::allocator<char> 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define __dtrie_string std::basic_string<Char, Char_Traits, __dtrie_alloc> 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Partial specialization, default_trie_access_traits. 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Char, typename Char_Traits> 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct default_trie_access_traits<__dtrie_string> 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef __dtrie_string string_type; 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Dispatched type. 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef trie_string_access_traits<string_type> type; 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef __dtrie_alloc 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef __dtrie_string 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif // #ifndef PB_DS_STANDARD_POLICIES_HPP 159