163d1a8abSmrg // -*- C++ -*- 263d1a8abSmrg 3*ec02198aSmrg // Copyright (C) 2005-2020 Free Software Foundation, Inc. 463d1a8abSmrg // 563d1a8abSmrg // This file is part of the GNU ISO C++ Library. This library is free 663d1a8abSmrg // software; you can redistribute it and/or modify it under the terms 763d1a8abSmrg // of the GNU General Public License as published by the Free Software 863d1a8abSmrg // Foundation; either version 3, or (at your option) any later 963d1a8abSmrg // version. 1063d1a8abSmrg 1163d1a8abSmrg // This library is distributed in the hope that it will be useful, but 1263d1a8abSmrg // WITHOUT ANY WARRANTY; without even the implied warranty of 1363d1a8abSmrg // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1463d1a8abSmrg // General Public License for more details. 1563d1a8abSmrg 1663d1a8abSmrg // Under Section 7 of GPL version 3, you are granted additional 1763d1a8abSmrg // permissions described in the GCC Runtime Library Exception, version 1863d1a8abSmrg // 3.1, as published by the Free Software Foundation. 1963d1a8abSmrg 2063d1a8abSmrg // You should have received a copy of the GNU General Public License and 2163d1a8abSmrg // a copy of the GCC Runtime Library Exception along with this program; 2263d1a8abSmrg // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2363d1a8abSmrg // <http://www.gnu.org/licenses/>. 2463d1a8abSmrg 2563d1a8abSmrg // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2663d1a8abSmrg 2763d1a8abSmrg // Permission to use, copy, modify, sell, and distribute this software 2863d1a8abSmrg // is hereby granted without fee, provided that the above copyright 2963d1a8abSmrg // notice appears in all copies, and that both that copyright notice 3063d1a8abSmrg // and this permission notice appear in supporting documentation. None 3163d1a8abSmrg // of the above authors, nor IBM Haifa Research Laboratories, make any 3263d1a8abSmrg // representation about the suitability of this software for any 3363d1a8abSmrg // purpose. It is provided "as is" without express or implied 3463d1a8abSmrg // warranty. 3563d1a8abSmrg 3663d1a8abSmrg /** 3763d1a8abSmrg * @file ranged_probe_fn.hpp 3863d1a8abSmrg * Contains a unified ranged probe functor, allowing the probe tables to deal with 3963d1a8abSmrg * a single class for ranged probeing. 4063d1a8abSmrg */ 4163d1a8abSmrg 4263d1a8abSmrg #ifndef PB_DS_RANGED_PROBE_FN_HPP 4363d1a8abSmrg #define PB_DS_RANGED_PROBE_FN_HPP 4463d1a8abSmrg 4563d1a8abSmrg #include <utility> 4663d1a8abSmrg #include <debug/debug.h> 4763d1a8abSmrg 4863d1a8abSmrg namespace __gnu_pbds 4963d1a8abSmrg { 5063d1a8abSmrg namespace detail 5163d1a8abSmrg { 5263d1a8abSmrg /// Primary template. 5363d1a8abSmrg template<typename Key, typename Hash_Fn, typename _Alloc, 5463d1a8abSmrg typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> 5563d1a8abSmrg class ranged_probe_fn; 5663d1a8abSmrg 5763d1a8abSmrg #define PB_DS_CLASS_T_DEC \ 5863d1a8abSmrg template<typename Key, typename Hash_Fn, typename _Alloc, \ 5963d1a8abSmrg typename Comb_Probe_Fn, typename Probe_Fn> 6063d1a8abSmrg 6163d1a8abSmrg #define PB_DS_CLASS_C_DEC \ 6263d1a8abSmrg ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> 6363d1a8abSmrg 6463d1a8abSmrg /** 6563d1a8abSmrg * Specialization 1 6663d1a8abSmrg * The client supplies a probe function and a ranged probe 6763d1a8abSmrg * function, and requests that hash values not be stored. 6863d1a8abSmrg **/ 6963d1a8abSmrg template<typename Key, typename Hash_Fn, typename _Alloc, 7063d1a8abSmrg typename Comb_Probe_Fn, typename Probe_Fn> 7163d1a8abSmrg class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 7263d1a8abSmrg Probe_Fn, false> 7363d1a8abSmrg : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 7463d1a8abSmrg { 7563d1a8abSmrg protected: 7663d1a8abSmrg typedef typename _Alloc::size_type size_type; 7763d1a8abSmrg typedef Comb_Probe_Fn comb_probe_fn_base; 7863d1a8abSmrg typedef Hash_Fn hash_fn_base; 7963d1a8abSmrg typedef Probe_Fn probe_fn_base; 80*ec02198aSmrg typedef typename rebind_traits<_Alloc, Key>::const_reference 81*ec02198aSmrg key_const_reference; 8263d1a8abSmrg 8363d1a8abSmrg ranged_probe_fn(size_type); 8463d1a8abSmrg 8563d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&); 8663d1a8abSmrg 8763d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); 8863d1a8abSmrg 8963d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 9063d1a8abSmrg const Probe_Fn&); 9163d1a8abSmrg 9263d1a8abSmrg void 9363d1a8abSmrg swap(PB_DS_CLASS_C_DEC&); 9463d1a8abSmrg 9563d1a8abSmrg void 9663d1a8abSmrg notify_resized(size_type); 9763d1a8abSmrg 9863d1a8abSmrg inline size_type 9963d1a8abSmrg operator()(key_const_reference) const; 10063d1a8abSmrg 10163d1a8abSmrg inline size_type 10263d1a8abSmrg operator()(key_const_reference, size_type, size_type) const; 10363d1a8abSmrg }; 10463d1a8abSmrg 10563d1a8abSmrg PB_DS_CLASS_T_DEC 10663d1a8abSmrg PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size)10763d1a8abSmrg ranged_probe_fn(size_type size) 10863d1a8abSmrg { Comb_Probe_Fn::notify_resized(size); } 10963d1a8abSmrg 11063d1a8abSmrg PB_DS_CLASS_T_DEC 11163d1a8abSmrg PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size,const Hash_Fn & r_hash_fn)11263d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 11363d1a8abSmrg : Hash_Fn(r_hash_fn) 11463d1a8abSmrg { Comb_Probe_Fn::notify_resized(size); } 11563d1a8abSmrg 11663d1a8abSmrg PB_DS_CLASS_T_DEC 11763d1a8abSmrg 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)11863d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 11963d1a8abSmrg const Comb_Probe_Fn& r_comb_probe_fn) 12063d1a8abSmrg : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 12163d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 12263d1a8abSmrg 12363d1a8abSmrg PB_DS_CLASS_T_DEC 12463d1a8abSmrg 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)12563d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 12663d1a8abSmrg const Comb_Probe_Fn& r_comb_probe_fn, 12763d1a8abSmrg const Probe_Fn& r_probe_fn) 12863d1a8abSmrg : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 12963d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 13063d1a8abSmrg 13163d1a8abSmrg PB_DS_CLASS_T_DEC 13263d1a8abSmrg void 13363d1a8abSmrg PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)13463d1a8abSmrg swap(PB_DS_CLASS_C_DEC& other) 13563d1a8abSmrg { 13663d1a8abSmrg comb_probe_fn_base::swap(other); 13763d1a8abSmrg std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); 13863d1a8abSmrg } 13963d1a8abSmrg 14063d1a8abSmrg PB_DS_CLASS_T_DEC 14163d1a8abSmrg void 14263d1a8abSmrg PB_DS_CLASS_C_DEC:: notify_resized(size_type size)14363d1a8abSmrg notify_resized(size_type size) 14463d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 14563d1a8abSmrg 14663d1a8abSmrg PB_DS_CLASS_T_DEC 14763d1a8abSmrg inline typename PB_DS_CLASS_C_DEC::size_type 14863d1a8abSmrg PB_DS_CLASS_C_DEC:: operator ()(key_const_reference r_key) const14963d1a8abSmrg operator()(key_const_reference r_key) const 15063d1a8abSmrg { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } 15163d1a8abSmrg 15263d1a8abSmrg PB_DS_CLASS_T_DEC 15363d1a8abSmrg inline typename PB_DS_CLASS_C_DEC::size_type 15463d1a8abSmrg PB_DS_CLASS_C_DEC:: operator ()(key_const_reference,size_type hash,size_type i) const15563d1a8abSmrg operator()(key_const_reference, size_type hash, size_type i) const 15663d1a8abSmrg { 15763d1a8abSmrg return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 15863d1a8abSmrg } 15963d1a8abSmrg 16063d1a8abSmrg #undef PB_DS_CLASS_T_DEC 16163d1a8abSmrg #undef PB_DS_CLASS_C_DEC 16263d1a8abSmrg 16363d1a8abSmrg #define PB_DS_CLASS_T_DEC \ 16463d1a8abSmrg template<typename Key, typename Hash_Fn, typename _Alloc, \ 16563d1a8abSmrg typename Comb_Probe_Fn, typename Probe_Fn> 16663d1a8abSmrg 16763d1a8abSmrg #define PB_DS_CLASS_C_DEC \ 16863d1a8abSmrg ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> 16963d1a8abSmrg 17063d1a8abSmrg /** 17163d1a8abSmrg * Specialization 2- The client supplies a probe function and a ranged 17263d1a8abSmrg * probe function, and requests that hash values not be stored. 17363d1a8abSmrg **/ 17463d1a8abSmrg template<typename Key, typename Hash_Fn, typename _Alloc, 17563d1a8abSmrg typename Comb_Probe_Fn, typename Probe_Fn> 17663d1a8abSmrg class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 17763d1a8abSmrg Probe_Fn, true> 17863d1a8abSmrg : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 17963d1a8abSmrg { 18063d1a8abSmrg protected: 18163d1a8abSmrg typedef typename _Alloc::size_type size_type; 18263d1a8abSmrg typedef std::pair<size_type, size_type> comp_hash; 18363d1a8abSmrg typedef Comb_Probe_Fn comb_probe_fn_base; 18463d1a8abSmrg typedef Hash_Fn hash_fn_base; 18563d1a8abSmrg typedef Probe_Fn probe_fn_base; 186*ec02198aSmrg typedef typename rebind_traits<_Alloc, Key>::const_reference 187*ec02198aSmrg key_const_reference; 18863d1a8abSmrg 18963d1a8abSmrg ranged_probe_fn(size_type); 19063d1a8abSmrg 19163d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&); 19263d1a8abSmrg 19363d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&, 19463d1a8abSmrg const Comb_Probe_Fn&); 19563d1a8abSmrg 19663d1a8abSmrg ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 19763d1a8abSmrg const Probe_Fn&); 19863d1a8abSmrg 19963d1a8abSmrg void 20063d1a8abSmrg swap(PB_DS_CLASS_C_DEC&); 20163d1a8abSmrg 20263d1a8abSmrg void 20363d1a8abSmrg notify_resized(size_type); 20463d1a8abSmrg 20563d1a8abSmrg inline comp_hash 20663d1a8abSmrg operator()(key_const_reference) const; 20763d1a8abSmrg 20863d1a8abSmrg inline size_type 20963d1a8abSmrg operator()(key_const_reference, size_type, size_type) const; 21063d1a8abSmrg 21163d1a8abSmrg inline size_type 21263d1a8abSmrg operator()(key_const_reference, size_type) const; 21363d1a8abSmrg }; 21463d1a8abSmrg 21563d1a8abSmrg PB_DS_CLASS_T_DEC 21663d1a8abSmrg PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size)21763d1a8abSmrg ranged_probe_fn(size_type size) 21863d1a8abSmrg { Comb_Probe_Fn::notify_resized(size); } 21963d1a8abSmrg 22063d1a8abSmrg PB_DS_CLASS_T_DEC 22163d1a8abSmrg PB_DS_CLASS_C_DEC:: ranged_probe_fn(size_type size,const Hash_Fn & r_hash_fn)22263d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 22363d1a8abSmrg : Hash_Fn(r_hash_fn) 22463d1a8abSmrg { Comb_Probe_Fn::notify_resized(size); } 22563d1a8abSmrg 22663d1a8abSmrg PB_DS_CLASS_T_DEC 22763d1a8abSmrg 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)22863d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 22963d1a8abSmrg const Comb_Probe_Fn& r_comb_probe_fn) 23063d1a8abSmrg : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 23163d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 23263d1a8abSmrg 23363d1a8abSmrg PB_DS_CLASS_T_DEC 23463d1a8abSmrg 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)23563d1a8abSmrg ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 23663d1a8abSmrg const Comb_Probe_Fn& r_comb_probe_fn, 23763d1a8abSmrg const Probe_Fn& r_probe_fn) 23863d1a8abSmrg : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 23963d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 24063d1a8abSmrg 24163d1a8abSmrg PB_DS_CLASS_T_DEC 24263d1a8abSmrg void 24363d1a8abSmrg PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)24463d1a8abSmrg swap(PB_DS_CLASS_C_DEC& other) 24563d1a8abSmrg { 24663d1a8abSmrg comb_probe_fn_base::swap(other); 24763d1a8abSmrg std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 24863d1a8abSmrg } 24963d1a8abSmrg 25063d1a8abSmrg PB_DS_CLASS_T_DEC 25163d1a8abSmrg void 25263d1a8abSmrg PB_DS_CLASS_C_DEC:: notify_resized(size_type size)25363d1a8abSmrg notify_resized(size_type size) 25463d1a8abSmrg { comb_probe_fn_base::notify_resized(size); } 25563d1a8abSmrg 25663d1a8abSmrg PB_DS_CLASS_T_DEC 25763d1a8abSmrg inline typename PB_DS_CLASS_C_DEC::comp_hash 25863d1a8abSmrg PB_DS_CLASS_C_DEC:: operator ()(key_const_reference r_key) const25963d1a8abSmrg operator()(key_const_reference r_key) const 26063d1a8abSmrg { 26163d1a8abSmrg const size_type hash = hash_fn_base::operator()(r_key); 26263d1a8abSmrg return std::make_pair(comb_probe_fn_base::operator()(hash), hash); 26363d1a8abSmrg } 26463d1a8abSmrg 26563d1a8abSmrg PB_DS_CLASS_T_DEC 26663d1a8abSmrg inline typename PB_DS_CLASS_C_DEC::size_type 26763d1a8abSmrg PB_DS_CLASS_C_DEC:: operator ()(key_const_reference,size_type hash,size_type i) const26863d1a8abSmrg operator()(key_const_reference, size_type hash, size_type i) const 26963d1a8abSmrg { 27063d1a8abSmrg return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 27163d1a8abSmrg } 27263d1a8abSmrg 27363d1a8abSmrg PB_DS_CLASS_T_DEC 27463d1a8abSmrg inline typename PB_DS_CLASS_C_DEC::size_type 27563d1a8abSmrg PB_DS_CLASS_C_DEC:: operator ()(key_const_reference r_key,size_type hash) const27663d1a8abSmrg operator() 27763d1a8abSmrg #ifdef _GLIBCXX_DEBUG 27863d1a8abSmrg (key_const_reference r_key, size_type hash) const 27963d1a8abSmrg #else 28063d1a8abSmrg (key_const_reference /*r_key*/, size_type hash) const 28163d1a8abSmrg #endif 28263d1a8abSmrg { 28363d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); 28463d1a8abSmrg return hash; 28563d1a8abSmrg } 28663d1a8abSmrg 28763d1a8abSmrg #undef PB_DS_CLASS_T_DEC 28863d1a8abSmrg #undef PB_DS_CLASS_C_DEC 28963d1a8abSmrg 29063d1a8abSmrg /** 29163d1a8abSmrg * Specialization 3 and 4 29263d1a8abSmrg * The client does not supply a hash function or probe function, 29363d1a8abSmrg * and requests that hash values not be stored. 29463d1a8abSmrg **/ 29563d1a8abSmrg template<typename Key, typename _Alloc, typename Comb_Probe_Fn> 29663d1a8abSmrg class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, 29763d1a8abSmrg null_type, false> 29863d1a8abSmrg : public Comb_Probe_Fn 29963d1a8abSmrg { 30063d1a8abSmrg protected: 30163d1a8abSmrg typedef typename _Alloc::size_type size_type; 30263d1a8abSmrg typedef Comb_Probe_Fn comb_probe_fn_base; 303*ec02198aSmrg typedef typename rebind_traits<_Alloc, Key>::const_reference 304*ec02198aSmrg key_const_reference; 30563d1a8abSmrg ranged_probe_fn(size_type size)30663d1a8abSmrg ranged_probe_fn(size_type size) 30763d1a8abSmrg { Comb_Probe_Fn::notify_resized(size); } 30863d1a8abSmrg ranged_probe_fn(size_type,const Comb_Probe_Fn & r_comb_probe_fn)30963d1a8abSmrg ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) 31063d1a8abSmrg : Comb_Probe_Fn(r_comb_probe_fn) 31163d1a8abSmrg { } 31263d1a8abSmrg ranged_probe_fn(size_type,const null_type &,const Comb_Probe_Fn & r_comb_probe_fn,const null_type &)31363d1a8abSmrg ranged_probe_fn(size_type, const null_type&, 31463d1a8abSmrg const Comb_Probe_Fn& r_comb_probe_fn, 31563d1a8abSmrg const null_type&) 31663d1a8abSmrg : Comb_Probe_Fn(r_comb_probe_fn) 31763d1a8abSmrg { } 31863d1a8abSmrg 31963d1a8abSmrg void swap(ranged_probe_fn & other)32063d1a8abSmrg swap(ranged_probe_fn& other) 32163d1a8abSmrg { comb_probe_fn_base::swap(other); } 32263d1a8abSmrg }; 32363d1a8abSmrg } // namespace detail 32463d1a8abSmrg } // namespace __gnu_pbds 32563d1a8abSmrg 32663d1a8abSmrg #endif 32763d1a8abSmrg 328