libstdc++
ranged_probe_fn.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009 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 ranged_probe_fn.hpp
00038  * Contains a unified ranged probe functor, allowing the probe tables to deal with
00039  *    a single class for ranged probeing.
00040  */
00041 
00042 #ifndef PB_DS_RANGED_PROBE_FN_HPP
00043 #define PB_DS_RANGED_PROBE_FN_HPP
00044 
00045 #include <utility>
00046 #include <debug/debug.h>
00047 
00048 namespace __gnu_pbds
00049 {
00050   namespace detail
00051   {
00052     /// Primary template.
00053     template<typename Key, typename Hash_Fn, typename _Alloc,
00054          typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
00055     class ranged_probe_fn;
00056 
00057 #define PB_DS_CLASS_T_DEC \
00058     template<typename Key, typename Hash_Fn, typename _Alloc, \
00059          typename Comb_Probe_Fn, typename Probe_Fn>
00060 
00061 #define PB_DS_CLASS_C_DEC \
00062     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false>
00063 
00064     /**
00065      * Specialization 1     
00066      * The client supplies a probe function and a ranged probe
00067      * function, and requests that hash values not be stored.
00068      **/
00069     template<typename Key, typename Hash_Fn, typename _Alloc,
00070          typename Comb_Probe_Fn, typename Probe_Fn>
00071     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
00072               Probe_Fn, false> 
00073     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
00074     {
00075     protected:
00076       typedef typename _Alloc::size_type size_type;
00077       typedef Comb_Probe_Fn comb_probe_fn_base;
00078       typedef Hash_Fn hash_fn_base;
00079       typedef Probe_Fn probe_fn_base;
00080       typedef typename _Alloc::template rebind<Key>::other key_allocator;
00081       typedef typename key_allocator::const_reference key_const_reference;
00082 
00083       ranged_probe_fn(size_type);
00084 
00085       ranged_probe_fn(size_type, const Hash_Fn&);
00086 
00087       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);
00088 
00089       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 
00090               const Probe_Fn&);
00091 
00092       void
00093       swap(PB_DS_CLASS_C_DEC&);
00094 
00095       void
00096       notify_resized(size_type);
00097 
00098       inline size_type
00099       operator()(key_const_reference) const;
00100 
00101       inline size_type
00102       operator()(key_const_reference, size_type, size_type) const;
00103     };
00104 
00105     PB_DS_CLASS_T_DEC
00106     PB_DS_CLASS_C_DEC::
00107     ranged_probe_fn(size_type size)
00108     { Comb_Probe_Fn::notify_resized(size); }
00109 
00110     PB_DS_CLASS_T_DEC
00111     PB_DS_CLASS_C_DEC::
00112     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 
00113     : Hash_Fn(r_hash_fn)
00114     { Comb_Probe_Fn::notify_resized(size); }
00115 
00116     PB_DS_CLASS_T_DEC
00117     PB_DS_CLASS_C_DEC::
00118     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 
00119             const Comb_Probe_Fn& r_comb_probe_fn) 
00120     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
00121     { comb_probe_fn_base::notify_resized(size); }
00122 
00123     PB_DS_CLASS_T_DEC
00124     PB_DS_CLASS_C_DEC::
00125     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 
00126             const Comb_Probe_Fn& r_comb_probe_fn, 
00127             const Probe_Fn& r_probe_fn) 
00128     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
00129     { comb_probe_fn_base::notify_resized(size); }
00130 
00131     PB_DS_CLASS_T_DEC
00132     void
00133     PB_DS_CLASS_C_DEC::
00134     swap(PB_DS_CLASS_C_DEC& other)
00135     {
00136       comb_probe_fn_base::swap(other);
00137       std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
00138     }
00139 
00140     PB_DS_CLASS_T_DEC
00141     void
00142     PB_DS_CLASS_C_DEC::
00143     notify_resized(size_type size)
00144     { comb_probe_fn_base::notify_resized(size); }
00145 
00146     PB_DS_CLASS_T_DEC
00147     inline typename PB_DS_CLASS_C_DEC::size_type
00148     PB_DS_CLASS_C_DEC::
00149     operator()(key_const_reference r_key) const
00150     { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
00151 
00152     PB_DS_CLASS_T_DEC
00153     inline typename PB_DS_CLASS_C_DEC::size_type
00154     PB_DS_CLASS_C_DEC::
00155     operator()(key_const_reference, size_type hash, size_type i) const
00156     {
00157       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
00158     }
00159 
00160 #undef PB_DS_CLASS_T_DEC
00161 #undef PB_DS_CLASS_C_DEC
00162 
00163 #define PB_DS_CLASS_T_DEC \
00164     template<typename Key, typename Hash_Fn, typename _Alloc, \
00165          typename Comb_Probe_Fn, typename Probe_Fn>
00166 
00167 #define PB_DS_CLASS_C_DEC \
00168     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true>
00169 
00170     /**
00171      * Specialization 2- The client supplies a probe function and a ranged
00172      *    probe function, and requests that hash values not be stored.
00173      **/
00174     template<typename Key, typename Hash_Fn, typename _Alloc,
00175          typename Comb_Probe_Fn, typename Probe_Fn>
00176     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 
00177               Probe_Fn, true> 
00178     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
00179     {
00180     protected:
00181       typedef typename _Alloc::size_type size_type;
00182       typedef std::pair<size_type, size_type> comp_hash;
00183       typedef Comb_Probe_Fn comb_probe_fn_base;
00184       typedef Hash_Fn hash_fn_base;
00185       typedef Probe_Fn probe_fn_base;
00186       typedef typename _Alloc::template rebind<Key>::other key_allocator;
00187       typedef typename key_allocator::const_reference key_const_reference;
00188 
00189       ranged_probe_fn(size_type);
00190 
00191       ranged_probe_fn(size_type, const Hash_Fn&);
00192 
00193       ranged_probe_fn(size_type, const Hash_Fn&, 
00194               const Comb_Probe_Fn&);
00195 
00196       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 
00197               const Probe_Fn&);
00198 
00199       void
00200       swap(PB_DS_CLASS_C_DEC&);
00201 
00202       void
00203       notify_resized(size_type);
00204 
00205       inline comp_hash
00206       operator()(key_const_reference) const;
00207 
00208       inline size_type
00209       operator()(key_const_reference, size_type, size_type) const;
00210 
00211       inline size_type
00212       operator()(key_const_reference, size_type) const;
00213     };
00214 
00215     PB_DS_CLASS_T_DEC
00216     PB_DS_CLASS_C_DEC::
00217     ranged_probe_fn(size_type size)
00218     { Comb_Probe_Fn::notify_resized(size); }
00219 
00220     PB_DS_CLASS_T_DEC
00221     PB_DS_CLASS_C_DEC::
00222     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 
00223     : Hash_Fn(r_hash_fn)
00224     { Comb_Probe_Fn::notify_resized(size); }
00225 
00226     PB_DS_CLASS_T_DEC
00227     PB_DS_CLASS_C_DEC::
00228     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 
00229             const Comb_Probe_Fn& r_comb_probe_fn) 
00230     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
00231     { comb_probe_fn_base::notify_resized(size); }
00232 
00233     PB_DS_CLASS_T_DEC
00234     PB_DS_CLASS_C_DEC::
00235     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 
00236             const Comb_Probe_Fn& r_comb_probe_fn, 
00237             const Probe_Fn& r_probe_fn) 
00238     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
00239     { comb_probe_fn_base::notify_resized(size); }
00240 
00241     PB_DS_CLASS_T_DEC
00242     void
00243     PB_DS_CLASS_C_DEC::
00244     swap(PB_DS_CLASS_C_DEC& other)
00245     {
00246       comb_probe_fn_base::swap(other);
00247       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
00248     }
00249 
00250     PB_DS_CLASS_T_DEC
00251     void
00252     PB_DS_CLASS_C_DEC::
00253     notify_resized(size_type size)
00254     { comb_probe_fn_base::notify_resized(size); }
00255 
00256     PB_DS_CLASS_T_DEC
00257     inline typename PB_DS_CLASS_C_DEC::comp_hash
00258     PB_DS_CLASS_C_DEC::
00259     operator()(key_const_reference r_key) const
00260     {
00261       const size_type hash = hash_fn_base::operator()(r_key);
00262       return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
00263     }
00264 
00265     PB_DS_CLASS_T_DEC
00266     inline typename PB_DS_CLASS_C_DEC::size_type
00267     PB_DS_CLASS_C_DEC::
00268     operator()(key_const_reference, size_type hash, size_type i) const
00269     {
00270       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
00271     }
00272 
00273     PB_DS_CLASS_T_DEC
00274     inline typename PB_DS_CLASS_C_DEC::size_type
00275     PB_DS_CLASS_C_DEC::
00276     operator()
00277 #ifdef _GLIBCXX_DEBUG
00278       (key_const_reference r_key, size_type hash) const
00279 #else 
00280       (key_const_reference /*r_key*/, size_type hash) const
00281 #endif 
00282     {
00283       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
00284       return hash;
00285     }
00286 
00287 #undef PB_DS_CLASS_T_DEC
00288 #undef PB_DS_CLASS_C_DEC
00289 
00290     /**
00291      * Specialization 3 and 4
00292      * The client does not supply a hash function or probe function,
00293      * and requests that hash values not be stored.
00294      **/
00295     template<typename Key, typename _Alloc, typename Comb_Probe_Fn>
00296     class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, 
00297               null_type, false> 
00298     : public Comb_Probe_Fn
00299     {
00300     protected:
00301       typedef typename _Alloc::size_type size_type;
00302       typedef Comb_Probe_Fn comb_probe_fn_base;
00303       typedef typename _Alloc::template rebind<Key>::other key_allocator;
00304       typedef typename key_allocator::const_reference key_const_reference;
00305 
00306       ranged_probe_fn(size_type size)
00307       { Comb_Probe_Fn::notify_resized(size); }
00308 
00309       ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
00310       : Comb_Probe_Fn(r_comb_probe_fn)
00311       { }
00312 
00313       ranged_probe_fn(size_type, const null_type&, 
00314               const Comb_Probe_Fn& r_comb_probe_fn, 
00315               const null_type&)
00316       : Comb_Probe_Fn(r_comb_probe_fn)
00317       { }
00318 
00319       void
00320       swap(ranged_probe_fn& other)
00321       { comb_probe_fn_base::swap(other); }
00322     };
00323   } // namespace detail
00324 } // namespace __gnu_pbds
00325 
00326 #endif
00327