libstdc++-v3/include/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
  54 namespace pb_ds
  55 {
  56   namespace detail
  57   {
  58
  59 #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
  60 #define PB_DS_DBG_ASSERT(X) assert(X)
  61 #define PB_DS_DBG_VERIFY(X) assert(X)
  62 #define PB_DS_DBG_ONLY(X) X
  63 #else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
  64 #define PB_DS_DBG_ASSERT(X)
  65 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
  66 #define PB_DS_DBG_ONLY(X) ;
  67 #endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
  68
  69     template<typename Key,
  70              class Hash_Fn,
  71              class Allocator,
  72              class Comb_Probe_Fn,
  73              class Probe_Fn,
  74              bool Store_Hash>
  75     class ranged_probe_fn;
  76
  77 #define PB_DS_CLASS_T_DEC                                               \
  78     template<                                                           \
  79                                                 typename Key,           \
  80                                                 class Hash_Fn,          \
  81                                                 class Allocator,        \
  82                                                 class Comb_Probe_Fn,    \
  83                                                 class Probe_Fn>
  84
  85 #define PB_DS_CLASS_C_DEC                                       \
  86     ranged_probe_fn<                                            \
  87                                                 Key,            \
  88                                                 Hash_Fn,        \
  89                                                 Allocator,      \
  90                                                 Comb_Probe_Fn,  \
  91                                                 Probe_Fn,       \
  92                                                 false>
  93
  94     /**
  95      * Specialization 1- The client supplies a probe function and a ranged
  96      *    probe function, and requests that hash values not be stored.
  97      **/
  98     template<typename Key,
  99              class Hash_Fn,
 100              class Allocator,
 101              class Comb_Probe_Fn,
 102              class Probe_Fn>
 103     class ranged_probe_fn<
 104       Key,
 105       Hash_Fn,
 106       Allocator,
 107       Comb_Probe_Fn,
 108       Probe_Fn,
 109       false> : public Hash_Fn,
 110                public Comb_Probe_Fn,
 111                public Probe_Fn
 112     {
 113     protected:
 114       typedef typename Allocator::size_type size_type;
 115
 116       typedef Comb_Probe_Fn comb_probe_fn_base;
 117
 118       typedef Hash_Fn hash_fn_base;
 119
 120       typedef Probe_Fn probe_fn_base;
 121
 122       typedef typename Allocator::template rebind<Key>::other key_allocator;
 123
 124       typedef typename key_allocator::const_reference const_key_reference;
 125
 126     protected:
 127       ranged_probe_fn(size_type size);
 128
 129       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
 130
 131       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
 132
 133       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);
 134
 135       void
 136       swap(PB_DS_CLASS_C_DEC& other);
 137
 138       void
 139       notify_resized(size_type size);
 140
 141       inline size_type
 142       operator()(const_key_reference r_key) const;
 143
 144       inline size_type
 145       operator()(const_key_reference r_key, size_type hash, size_type i) const;
 146     };
 147
 148     PB_DS_CLASS_T_DEC
 149     PB_DS_CLASS_C_DEC::
 150     ranged_probe_fn(size_type size)
 151     {
 152       Comb_Probe_Fn::notify_resized(size);
 153     }
 154
 155     PB_DS_CLASS_T_DEC
 156     PB_DS_CLASS_C_DEC::
 157     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
 158       Hash_Fn(r_hash_fn)
 159     {
 160       Comb_Probe_Fn::notify_resized(size);
 161     }
 162
 163     PB_DS_CLASS_T_DEC
 164     PB_DS_CLASS_C_DEC::
 165     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
 166       Hash_Fn(r_hash_fn),
 167       Comb_Probe_Fn(r_comb_probe_fn)
 168     {
 169       comb_probe_fn_base::notify_resized(size);
 170     }
 171
 172     PB_DS_CLASS_T_DEC
 173     PB_DS_CLASS_C_DEC::
 174     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) :
 175       Hash_Fn(r_hash_fn),
 176       Comb_Probe_Fn(r_comb_probe_fn),
 177       Probe_Fn(r_probe_fn)
 178     {
 179       comb_probe_fn_base::notify_resized(size);
 180     }
 181
 182     PB_DS_CLASS_T_DEC
 183     void
 184     PB_DS_CLASS_C_DEC::
 185     swap(PB_DS_CLASS_C_DEC& other)
 186     {
 187       comb_probe_fn_base::swap(other);
 188
 189       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
 190     }
 191
 192     PB_DS_CLASS_T_DEC
 193     void
 194     PB_DS_CLASS_C_DEC::
 195     notify_resized(size_type size)
 196     {
 197       comb_probe_fn_base::notify_resized(size);
 198     }
 199
 200     PB_DS_CLASS_T_DEC
 201     inline typename PB_DS_CLASS_C_DEC::size_type
 202     PB_DS_CLASS_C_DEC::
 203     operator()(const_key_reference r_key) const
 204     {
 205       return (comb_probe_fn_base::operator()(
 206                                              hash_fn_base::operator()(r_key)));
 207     }
 208
 209     PB_DS_CLASS_T_DEC
 210     inline typename PB_DS_CLASS_C_DEC::size_type
 211     PB_DS_CLASS_C_DEC::
 212     operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
 213     {
 214       return (comb_probe_fn_base::operator()(
 215                                              hash + probe_fn_base::operator()(i)));
 216     }
 217
 218 #undef PB_DS_CLASS_T_DEC
 219 #undef PB_DS_CLASS_C_DEC
 220
 221 #define PB_DS_CLASS_T_DEC                                               \
 222     template<                                                           \
 223                                                 typename Key,           \
 224                                                 class Hash_Fn,          \
 225                                                 class Allocator,        \
 226                                                 class Comb_Probe_Fn,    \
 227                                                 class Probe_Fn>
 228
 229 #define PB_DS_CLASS_C_DEC                                       \
 230     ranged_probe_fn<                                            \
 231                                                 Key,            \
 232                                                 Hash_Fn,        \
 233                                                 Allocator,      \
 234                                                 Comb_Probe_Fn,  \
 235                                                 Probe_Fn,       \
 236                                                 true>
 237
 238     /**
 239      * Specialization 2- The client supplies a probe function and a ranged
 240      *    probe function, and requests that hash values not be stored.
 241      **/
 242     template<typename Key,
 243              class Hash_Fn,
 244              class Allocator,
 245              class Comb_Probe_Fn,
 246              class Probe_Fn>
 247     class ranged_probe_fn<
 248       Key,
 249       Hash_Fn,
 250       Allocator,
 251       Comb_Probe_Fn,
 252       Probe_Fn,
 253       true> :
 254       public Hash_Fn,
 255       public Comb_Probe_Fn,
 256       public Probe_Fn
 257     {
 258     protected:
 259       typedef typename Allocator::size_type size_type;
 260
 261       typedef typename comp_hash_<size_type>::comp_hash comp_hash;
 262
 263       typedef Comb_Probe_Fn comb_probe_fn_base;
 264
 265       typedef Hash_Fn hash_fn_base;
 266
 267       typedef Probe_Fn probe_fn_base;
 268
 269       typedef typename Allocator::template rebind<Key>::other key_allocator;
 270
 271       typedef typename key_allocator::const_reference const_key_reference;
 272
 273     protected:
 274       ranged_probe_fn(size_type size);
 275
 276       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
 277
 278       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
 279
 280       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);
 281
 282       void
 283       swap(PB_DS_CLASS_C_DEC& other);
 284
 285       void
 286       notify_resized(size_type size);
 287
 288       inline comp_hash
 289       operator()(const_key_reference r_key) const;
 290
 291       inline size_type
 292       operator()(const_key_reference r_key, size_type hash, size_type i) const;
 293
 294       inline size_type
 295       operator()(const_key_reference r_key, size_type hash) const;
 296     };
 297
 298     PB_DS_CLASS_T_DEC
 299     PB_DS_CLASS_C_DEC::
 300     ranged_probe_fn(size_type size)
 301     {
 302       Comb_Probe_Fn::notify_resized(size);
 303     }
 304
 305     PB_DS_CLASS_T_DEC
 306     PB_DS_CLASS_C_DEC::
 307     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
 308       Hash_Fn(r_hash_fn)
 309     {
 310       Comb_Probe_Fn::notify_resized(size);
 311     }
 312
 313     PB_DS_CLASS_T_DEC
 314     PB_DS_CLASS_C_DEC::
 315     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
 316       Hash_Fn(r_hash_fn),
 317       Comb_Probe_Fn(r_comb_probe_fn)
 318     {
 319       comb_probe_fn_base::notify_resized(size);
 320     }
 321
 322     PB_DS_CLASS_T_DEC
 323     PB_DS_CLASS_C_DEC::
 324     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) :
 325       Hash_Fn(r_hash_fn),
 326       Comb_Probe_Fn(r_comb_probe_fn),
 327       Probe_Fn(r_probe_fn)
 328     {
 329       comb_probe_fn_base::notify_resized(size);
 330     }
 331
 332     PB_DS_CLASS_T_DEC
 333     void
 334     PB_DS_CLASS_C_DEC::
 335     swap(PB_DS_CLASS_C_DEC& other)
 336     {
 337       comb_probe_fn_base::swap(other);
 338
 339       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
 340     }
 341
 342     PB_DS_CLASS_T_DEC
 343     void
 344     PB_DS_CLASS_C_DEC::
 345     notify_resized(size_type size)
 346     {
 347       comb_probe_fn_base::notify_resized(size);
 348     }
 349
 350     PB_DS_CLASS_T_DEC
 351     inline typename PB_DS_CLASS_C_DEC::comp_hash
 352     PB_DS_CLASS_C_DEC::
 353     operator()(const_key_reference r_key) const
 354     {
 355       const size_type hash = hash_fn_base::operator()(r_key);
 356
 357       return (std::make_pair(comb_probe_fn_base::operator()(hash), hash));
 358     }
 359
 360     PB_DS_CLASS_T_DEC
 361     inline typename PB_DS_CLASS_C_DEC::size_type
 362     PB_DS_CLASS_C_DEC::
 363     operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
 364     {
 365       return (comb_probe_fn_base::operator()(
 366                                              hash + probe_fn_base::operator()(i)));
 367     }
 368
 369     PB_DS_CLASS_T_DEC
 370     inline typename PB_DS_CLASS_C_DEC::size_type
 371     PB_DS_CLASS_C_DEC::
 372     operator()
 373 #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
 374       (const_key_reference r_key, size_type hash) const
 375 #else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
 376       (const_key_reference /*r_key*/, size_type hash) const
 377 #endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
 378     {
 379       PB_DS_DBG_ASSERT(hash == hash_fn_base::operator()(r_key));
 380
 381       return (hash);
 382     }
 383
 384 #undef PB_DS_CLASS_T_DEC
 385 #undef PB_DS_CLASS_C_DEC
 386
 387 #define PB_DS_CLASS_T_DEC                                               \
 388     template<typename Key, class Allocator, class Comb_Probe_Fn>
 389
 390 #define PB_DS_CLASS_C_DEC                                       \
 391     ranged_probe_fn<                                            \
 392                                                 Key,            \
 393                                                 null_hash_fn,   \
 394                                                 Allocator,      \
 395                                                 Comb_Probe_Fn,  \
 396                                                 null_probe_fn,  \
 397                                                 false>
 398
 399     /**
 400      * Specialization 3 and 4- The client does not supply a hash function or
 401      *    probe function, and requests that hash values not be stored.
 402      **/
 403     template<typename Key, class Allocator, class Comb_Probe_Fn>
 404     class ranged_probe_fn<
 405       Key,
 406       null_hash_fn,
 407       Allocator,
 408       Comb_Probe_Fn,
 409       null_probe_fn,
 410       false> :
 411       public Comb_Probe_Fn,
 412       public null_hash_fn,
 413       public null_probe_fn
 414     {
 415     protected:
 416       typedef typename Allocator::size_type size_type;
 417
 418       typedef Comb_Probe_Fn comb_probe_fn_base;
 419
 420       typedef typename Allocator::template rebind<Key>::other key_allocator;
 421
 422       typedef typename key_allocator::const_reference const_key_reference;
 423
 424     protected:
 425       ranged_probe_fn(size_type size);
 426
 427       ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn);
 428
 429       ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn);
 430
 431       void
 432       swap(PB_DS_CLASS_C_DEC& other);
 433     };
 434
 435     PB_DS_CLASS_T_DEC
 436     PB_DS_CLASS_C_DEC::
 437     ranged_probe_fn(size_type size)
 438     {
 439       Comb_Probe_Fn::notify_resized(size);
 440     }
 441
 442     PB_DS_CLASS_T_DEC
 443     PB_DS_CLASS_C_DEC::
 444     ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn) :
 445       Comb_Probe_Fn(r_comb_probe_fn)
 446     { }
 447
 448     PB_DS_CLASS_T_DEC
 449     PB_DS_CLASS_C_DEC::
 450     ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn) :
 451       Comb_Probe_Fn(r_comb_probe_fn)
 452     { }
 453
 454     PB_DS_CLASS_T_DEC
 455     void
 456     PB_DS_CLASS_C_DEC::
 457     swap(PB_DS_CLASS_C_DEC& other)
 458     {
 459       comb_probe_fn_base::swap(other);
 460     }
 461
 462 #undef PB_DS_CLASS_T_DEC
 463 #undef PB_DS_CLASS_C_DEC
 464
 465 #undef PB_DS_DBG_ASSERT
 466 #undef PB_DS_DBG_VERIFY
 467 #undef PB_DS_DBG_ONLY
 468
 469   } // namespace detail
 470 } // namespace pb_ds
 471
 472 #endif // #ifndef PB_DS_RANGED_PROBE_FN_HPP
 473