libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file ranged_probe_fn.hpp
  38  * Contains a unified ranged probe functor, allowing the probe tables to deal with
  39  *    a single class for ranged probeing.
  40  */
  41
  42 #ifndef PB_DS_RANGED_PROBE_FN_HPP
  43 #define PB_DS_RANGED_PROBE_FN_HPP
  44
  45 #include <utility>
  46 #include <debug/debug.h>
  47
  48 namespace __gnu_pbds
  49 {
  50   namespace detail
  51   {
  52     template<typename Key, typename Hash_Fn, typename _Alloc,
  53              typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
  54     class ranged_probe_fn;
  55
  56 #define PB_DS_CLASS_T_DEC \
  57     template<typename Key, typename Hash_Fn, typename _Alloc, \
  58              typename Comb_Probe_Fn, typename Probe_Fn>
  59
  60 #define PB_DS_CLASS_C_DEC \
  61     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false>
  62
  63     /**
  64      * Specialization 1
  65      * The client supplies a probe function and a ranged probe
  66      * function, and requests that hash values not be stored.
  67      **/
  68     template<typename Key, typename Hash_Fn, typename _Alloc,
  69              typename Comb_Probe_Fn, typename Probe_Fn>
  70     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
  71                           Probe_Fn, false>
  72     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
  73     {
  74     protected:
  75       typedef typename _Alloc::size_type size_type;
  76       typedef Comb_Probe_Fn comb_probe_fn_base;
  77       typedef Hash_Fn hash_fn_base;
  78       typedef Probe_Fn probe_fn_base;
  79       typedef typename _Alloc::template rebind<Key>::other key_allocator;
  80       typedef typename key_allocator::const_reference key_const_reference;
  81
  82       ranged_probe_fn(size_type);
  83
  84       ranged_probe_fn(size_type, const Hash_Fn&);
  85
  86       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);
  87
  88       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
  89                       const Probe_Fn&);
  90
  91       void
  92       swap(PB_DS_CLASS_C_DEC&);
  93
  94       void
  95       notify_resized(size_type);
  96
  97       inline size_type
  98       operator()(key_const_reference) const;
  99
 100       inline size_type
 101       operator()(key_const_reference, size_type, size_type) const;
 102     };
 103
 104     PB_DS_CLASS_T_DEC
 105     PB_DS_CLASS_C_DEC::
 106     ranged_probe_fn(size_type size)
 107     { Comb_Probe_Fn::notify_resized(size); }
 108
 109     PB_DS_CLASS_T_DEC
 110     PB_DS_CLASS_C_DEC::
 111     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
 112     : Hash_Fn(r_hash_fn)
 113     { Comb_Probe_Fn::notify_resized(size); }
 114
 115     PB_DS_CLASS_T_DEC
 116     PB_DS_CLASS_C_DEC::
 117     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 118                     const Comb_Probe_Fn& r_comb_probe_fn)
 119     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
 120     { comb_probe_fn_base::notify_resized(size); }
 121
 122     PB_DS_CLASS_T_DEC
 123     PB_DS_CLASS_C_DEC::
 124     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 125                     const Comb_Probe_Fn& r_comb_probe_fn,
 126                     const Probe_Fn& r_probe_fn)
 127     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
 128     { comb_probe_fn_base::notify_resized(size); }
 129
 130     PB_DS_CLASS_T_DEC
 131     void
 132     PB_DS_CLASS_C_DEC::
 133     swap(PB_DS_CLASS_C_DEC& other)
 134     {
 135       comb_probe_fn_base::swap(other);
 136       std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
 137     }
 138
 139     PB_DS_CLASS_T_DEC
 140     void
 141     PB_DS_CLASS_C_DEC::
 142     notify_resized(size_type size)
 143     { comb_probe_fn_base::notify_resized(size); }
 144
 145     PB_DS_CLASS_T_DEC
 146     inline typename PB_DS_CLASS_C_DEC::size_type
 147     PB_DS_CLASS_C_DEC::
 148     operator()(key_const_reference r_key) const
 149     { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
 150
 151     PB_DS_CLASS_T_DEC
 152     inline typename PB_DS_CLASS_C_DEC::size_type
 153     PB_DS_CLASS_C_DEC::
 154     operator()(key_const_reference, size_type hash, size_type i) const
 155     {
 156       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
 157     }
 158
 159 #undef PB_DS_CLASS_T_DEC
 160 #undef PB_DS_CLASS_C_DEC
 161
 162 #define PB_DS_CLASS_T_DEC \
 163     template<typename Key, typename Hash_Fn, typename _Alloc, \
 164              typename Comb_Probe_Fn, typename Probe_Fn>
 165
 166 #define PB_DS_CLASS_C_DEC \
 167     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true>
 168
 169     /**
 170      * Specialization 2- The client supplies a probe function and a ranged
 171      *    probe function, and requests that hash values not be stored.
 172      **/
 173     template<typename Key, typename Hash_Fn, typename _Alloc,
 174              typename Comb_Probe_Fn, typename Probe_Fn>
 175     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
 176                           Probe_Fn, true>
 177     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
 178     {
 179     protected:
 180       typedef typename _Alloc::size_type size_type;
 181       typedef std::pair<size_type, size_type> comp_hash;
 182       typedef Comb_Probe_Fn comb_probe_fn_base;
 183       typedef Hash_Fn hash_fn_base;
 184       typedef Probe_Fn probe_fn_base;
 185       typedef typename _Alloc::template rebind<Key>::other key_allocator;
 186       typedef typename key_allocator::const_reference key_const_reference;
 187
 188       ranged_probe_fn(size_type);
 189
 190       ranged_probe_fn(size_type, const Hash_Fn&);
 191
 192       ranged_probe_fn(size_type, const Hash_Fn&,
 193                       const Comb_Probe_Fn&);
 194
 195       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
 196                       const Probe_Fn&);
 197
 198       void
 199       swap(PB_DS_CLASS_C_DEC&);
 200
 201       void
 202       notify_resized(size_type);
 203
 204       inline comp_hash
 205       operator()(key_const_reference) const;
 206
 207       inline size_type
 208       operator()(key_const_reference, size_type, size_type) const;
 209
 210       inline size_type
 211       operator()(key_const_reference, size_type) const;
 212     };
 213
 214     PB_DS_CLASS_T_DEC
 215     PB_DS_CLASS_C_DEC::
 216     ranged_probe_fn(size_type size)
 217     { Comb_Probe_Fn::notify_resized(size); }
 218
 219     PB_DS_CLASS_T_DEC
 220     PB_DS_CLASS_C_DEC::
 221     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
 222     : Hash_Fn(r_hash_fn)
 223     { Comb_Probe_Fn::notify_resized(size); }
 224
 225     PB_DS_CLASS_T_DEC
 226     PB_DS_CLASS_C_DEC::
 227     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 228                     const Comb_Probe_Fn& r_comb_probe_fn)
 229     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
 230     { comb_probe_fn_base::notify_resized(size); }
 231
 232     PB_DS_CLASS_T_DEC
 233     PB_DS_CLASS_C_DEC::
 234     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 235                     const Comb_Probe_Fn& r_comb_probe_fn,
 236                     const Probe_Fn& r_probe_fn)
 237     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
 238     { comb_probe_fn_base::notify_resized(size); }
 239
 240     PB_DS_CLASS_T_DEC
 241     void
 242     PB_DS_CLASS_C_DEC::
 243     swap(PB_DS_CLASS_C_DEC& other)
 244     {
 245       comb_probe_fn_base::swap(other);
 246       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
 247     }
 248
 249     PB_DS_CLASS_T_DEC
 250     void
 251     PB_DS_CLASS_C_DEC::
 252     notify_resized(size_type size)
 253     { comb_probe_fn_base::notify_resized(size); }
 254
 255     PB_DS_CLASS_T_DEC
 256     inline typename PB_DS_CLASS_C_DEC::comp_hash
 257     PB_DS_CLASS_C_DEC::
 258     operator()(key_const_reference r_key) const
 259     {
 260       const size_type hash = hash_fn_base::operator()(r_key);
 261       return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
 262     }
 263
 264     PB_DS_CLASS_T_DEC
 265     inline typename PB_DS_CLASS_C_DEC::size_type
 266     PB_DS_CLASS_C_DEC::
 267     operator()(key_const_reference, size_type hash, size_type i) const
 268     {
 269       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
 270     }
 271
 272     PB_DS_CLASS_T_DEC
 273     inline typename PB_DS_CLASS_C_DEC::size_type
 274     PB_DS_CLASS_C_DEC::
 275     operator()
 276 #ifdef _GLIBCXX_DEBUG
 277       (key_const_reference r_key, size_type hash) const
 278 #else
 279       (key_const_reference /*r_key*/, size_type hash) const
 280 #endif
 281     {
 282       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
 283       return hash;
 284     }
 285
 286 #undef PB_DS_CLASS_T_DEC
 287 #undef PB_DS_CLASS_C_DEC
 288
 289     /**
 290      * Specialization 3 and 4
 291      * The client does not supply a hash function or probe function,
 292      * and requests that hash values not be stored.
 293      **/
 294     template<typename Key, typename _Alloc, typename Comb_Probe_Fn>
 295     class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn,
 296                           null_type, false>
 297     : public Comb_Probe_Fn
 298     {
 299     protected:
 300       typedef typename _Alloc::size_type size_type;
 301       typedef Comb_Probe_Fn comb_probe_fn_base;
 302       typedef typename _Alloc::template rebind<Key>::other key_allocator;
 303       typedef typename key_allocator::const_reference key_const_reference;
 304
 305       ranged_probe_fn(size_type size)
 306       { Comb_Probe_Fn::notify_resized(size); }
 307
 308       ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
 309       : Comb_Probe_Fn(r_comb_probe_fn)
 310       { }
 311
 312       ranged_probe_fn(size_type, const null_type&,
 313                       const Comb_Probe_Fn& r_comb_probe_fn,
 314                       const null_type&)
 315       : Comb_Probe_Fn(r_comb_probe_fn)
 316       { }
 317
 318       void
 319       swap(ranged_probe_fn& other)
 320       { comb_probe_fn_base::swap(other); }
 321     };
 322   } // namespace detail
 323 } // namespace __gnu_pbds
 324
 325 #endif
 326