mingw/lib/gcc/mingw32/4.3.3/include/c++/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file ranged_probe_fn.hpp
  44  * Contains a unified ranged probe functor, allowing the probe tables to deal with
  45  *    a single class for ranged probeing.
  46  */
  47
  48 #ifndef PB_DS_RANGED_PROBE_FN_HPP
  49 #define PB_DS_RANGED_PROBE_FN_HPP
  50
  51 #include <ext/pb_ds/detail/basic_types.hpp>
  52 #include <utility>
  53 #include <debug/debug.h>
  54
  55 namespace __gnu_pbds
  56 {
  57   namespace detail
  58   {
  59     template<typename Key, typename Hash_Fn, typename Allocator,
  60              typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
  61     class ranged_probe_fn;
  62
  63 #define PB_DS_CLASS_T_DEC \
  64     template<typename Key, typename Hash_Fn, typename Allocator, \
  65              typename Comb_Probe_Fn, typename Probe_Fn>
  66
  67 #define PB_DS_CLASS_C_DEC \
  68     ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
  69
  70     /**
  71      * Specialization 1
  72      * The client supplies a probe function and a ranged probe
  73      * function, and requests that hash values not be stored.
  74      **/
  75     template<typename Key, typename Hash_Fn, typename Allocator,
  76              typename Comb_Probe_Fn, typename Probe_Fn>
  77     class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
  78                           Probe_Fn, false>
  79     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
  80     {
  81     protected:
  82       typedef typename Allocator::size_type size_type;
  83       typedef Comb_Probe_Fn comb_probe_fn_base;
  84       typedef Hash_Fn hash_fn_base;
  85       typedef Probe_Fn probe_fn_base;
  86       typedef typename Allocator::template rebind<Key>::other key_allocator;
  87       typedef typename key_allocator::const_reference const_key_reference;
  88
  89       ranged_probe_fn(size_type);
  90
  91       ranged_probe_fn(size_type, const Hash_Fn&);
  92
  93       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);
  94
  95       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
  96                       const Probe_Fn&);
  97
  98       void
  99       swap(PB_DS_CLASS_C_DEC&);
 100
 101       void
 102       notify_resized(size_type);
 103
 104       inline size_type
 105       operator()(const_key_reference) const;
 106
 107       inline size_type
 108       operator()(const_key_reference, size_type, size_type) const;
 109     };
 110
 111     PB_DS_CLASS_T_DEC
 112     PB_DS_CLASS_C_DEC::
 113     ranged_probe_fn(size_type size)
 114     { Comb_Probe_Fn::notify_resized(size); }
 115
 116     PB_DS_CLASS_T_DEC
 117     PB_DS_CLASS_C_DEC::
 118     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
 119     : Hash_Fn(r_hash_fn)
 120     { Comb_Probe_Fn::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     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
 127     { comb_probe_fn_base::notify_resized(size); }
 128
 129     PB_DS_CLASS_T_DEC
 130     PB_DS_CLASS_C_DEC::
 131     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 132                     const Comb_Probe_Fn& r_comb_probe_fn,
 133                     const Probe_Fn& r_probe_fn)
 134     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
 135     { comb_probe_fn_base::notify_resized(size); }
 136
 137     PB_DS_CLASS_T_DEC
 138     void
 139     PB_DS_CLASS_C_DEC::
 140     swap(PB_DS_CLASS_C_DEC& other)
 141     {
 142       comb_probe_fn_base::swap(other);
 143       std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
 144     }
 145
 146     PB_DS_CLASS_T_DEC
 147     void
 148     PB_DS_CLASS_C_DEC::
 149     notify_resized(size_type size)
 150     { comb_probe_fn_base::notify_resized(size); }
 151
 152     PB_DS_CLASS_T_DEC
 153     inline typename PB_DS_CLASS_C_DEC::size_type
 154     PB_DS_CLASS_C_DEC::
 155     operator()(const_key_reference r_key) const
 156     { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
 157
 158     PB_DS_CLASS_T_DEC
 159     inline typename PB_DS_CLASS_C_DEC::size_type
 160     PB_DS_CLASS_C_DEC::
 161     operator()(const_key_reference, size_type hash, size_type i) const
 162     {
 163       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
 164     }
 165
 166 #undef PB_DS_CLASS_T_DEC
 167 #undef PB_DS_CLASS_C_DEC
 168
 169 #define PB_DS_CLASS_T_DEC \
 170     template<typename Key, typename Hash_Fn, typename Allocator, \
 171              typename Comb_Probe_Fn, typename Probe_Fn>
 172
 173 #define PB_DS_CLASS_C_DEC \
 174     ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
 175
 176     /**
 177      * Specialization 2- The client supplies a probe function and a ranged
 178      *    probe function, and requests that hash values not be stored.
 179      **/
 180     template<typename Key, typename Hash_Fn, typename Allocator,
 181              typename Comb_Probe_Fn, typename Probe_Fn>
 182     class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
 183                           Probe_Fn, true>
 184     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
 185     {
 186     protected:
 187       typedef typename Allocator::size_type size_type;
 188       typedef std::pair<size_type, size_type> comp_hash;
 189       typedef Comb_Probe_Fn comb_probe_fn_base;
 190       typedef Hash_Fn hash_fn_base;
 191       typedef Probe_Fn probe_fn_base;
 192       typedef typename Allocator::template rebind<Key>::other key_allocator;
 193       typedef typename key_allocator::const_reference const_key_reference;
 194
 195       ranged_probe_fn(size_type);
 196
 197       ranged_probe_fn(size_type, const Hash_Fn&);
 198
 199       ranged_probe_fn(size_type, const Hash_Fn&,
 200                       const Comb_Probe_Fn&);
 201
 202       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
 203                       const Probe_Fn&);
 204
 205       void
 206       swap(PB_DS_CLASS_C_DEC&);
 207
 208       void
 209       notify_resized(size_type);
 210
 211       inline comp_hash
 212       operator()(const_key_reference) const;
 213
 214       inline size_type
 215       operator()(const_key_reference, size_type, size_type) const;
 216
 217       inline size_type
 218       operator()(const_key_reference, size_type) const;
 219     };
 220
 221     PB_DS_CLASS_T_DEC
 222     PB_DS_CLASS_C_DEC::
 223     ranged_probe_fn(size_type size)
 224     { Comb_Probe_Fn::notify_resized(size); }
 225
 226     PB_DS_CLASS_T_DEC
 227     PB_DS_CLASS_C_DEC::
 228     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
 229     : Hash_Fn(r_hash_fn)
 230     { Comb_Probe_Fn::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     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
 237     { comb_probe_fn_base::notify_resized(size); }
 238
 239     PB_DS_CLASS_T_DEC
 240     PB_DS_CLASS_C_DEC::
 241     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
 242                     const Comb_Probe_Fn& r_comb_probe_fn,
 243                     const Probe_Fn& r_probe_fn)
 244     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
 245     { comb_probe_fn_base::notify_resized(size); }
 246
 247     PB_DS_CLASS_T_DEC
 248     void
 249     PB_DS_CLASS_C_DEC::
 250     swap(PB_DS_CLASS_C_DEC& other)
 251     {
 252       comb_probe_fn_base::swap(other);
 253       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
 254     }
 255
 256     PB_DS_CLASS_T_DEC
 257     void
 258     PB_DS_CLASS_C_DEC::
 259     notify_resized(size_type size)
 260     { comb_probe_fn_base::notify_resized(size); }
 261
 262     PB_DS_CLASS_T_DEC
 263     inline typename PB_DS_CLASS_C_DEC::comp_hash
 264     PB_DS_CLASS_C_DEC::
 265     operator()(const_key_reference r_key) const
 266     {
 267       const size_type hash = hash_fn_base::operator()(r_key);
 268       return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
 269     }
 270
 271     PB_DS_CLASS_T_DEC
 272     inline typename PB_DS_CLASS_C_DEC::size_type
 273     PB_DS_CLASS_C_DEC::
 274     operator()(const_key_reference, size_type hash, size_type i) const
 275     {
 276       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
 277     }
 278
 279     PB_DS_CLASS_T_DEC
 280     inline typename PB_DS_CLASS_C_DEC::size_type
 281     PB_DS_CLASS_C_DEC::
 282     operator()
 283 #ifdef _GLIBCXX_DEBUG
 284       (const_key_reference r_key, size_type hash) const
 285 #else
 286       (const_key_reference /*r_key*/, size_type hash) const
 287 #endif
 288     {
 289       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
 290       return hash;
 291     }
 292
 293 #undef PB_DS_CLASS_T_DEC
 294 #undef PB_DS_CLASS_C_DEC
 295
 296     /**
 297      * Specialization 3 and 4
 298      * The client does not supply a hash function or probe function,
 299      * and requests that hash values not be stored.
 300      **/
 301     template<typename Key, typename Allocator, typename Comb_Probe_Fn>
 302     class ranged_probe_fn<Key, null_hash_fn, Allocator, Comb_Probe_Fn,
 303                           null_probe_fn, false>
 304     : public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn
 305     {
 306     protected:
 307       typedef typename Allocator::size_type size_type;
 308       typedef Comb_Probe_Fn comb_probe_fn_base;
 309       typedef typename Allocator::template rebind<Key>::other key_allocator;
 310       typedef typename key_allocator::const_reference const_key_reference;
 311
 312       ranged_probe_fn(size_type size)
 313       { Comb_Probe_Fn::notify_resized(size); }
 314
 315       ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
 316       : Comb_Probe_Fn(r_comb_probe_fn)
 317       { }
 318
 319       ranged_probe_fn(size_type, const null_hash_fn&,
 320                       const Comb_Probe_Fn& r_comb_probe_fn,
 321                       const null_probe_fn&)
 322       : Comb_Probe_Fn(r_comb_probe_fn)
 323       { }
 324
 325       void
 326       swap(ranged_probe_fn& other)
 327       { comb_probe_fn_base::swap(other); }
 328     };
 329   } // namespace detail
 330 } // namespace __gnu_pbds
 331
 332 #endif
 333