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