contrib/gcc-4.1/libstdc++-v3/include/ext/pb_assoc/detail/hash_fn/ranged_hash_fn.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file ranged_hash_fn.hpp
  42  * Contains a unified ranged hash functor, allowing the hash tables to deal with
  43  *      a single class for ranged hashing.
  44  */
  45
  46 #ifndef RANGED_HASH_FN_HPP
  47 #define RANGED_HASH_FN_HPP
  48
  49 #include <utility>
  50
  51 namespace pb_assoc
  52 {
  53
  54   namespace detail
  55   {
  56
  57 #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
  58 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
  59 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
  60 #define PB_ASSOC_DBG_ONLY(X) X
  61 #else // #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
  62 #define PB_ASSOC_DBG_ASSERT(X)
  63 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
  64 #define PB_ASSOC_DBG_ONLY(X) ;
  65 #endif // #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
  66
  67     template<typename Key,
  68              class Hash_Fn,
  69              class Allocator,
  70              class Comb_Hash_Fn,
  71              bool Store_Hash>
  72     class ranged_hash_fn;
  73
  74 #define PB_ASSOC_CLASS_T_DEC \
  75         template< \
  76                 typename Key, \
  77                 class Hash_Fn, \
  78                 class Allocator, \
  79                 class Comb_Hash_Fn>
  80
  81 #define PB_ASSOC_CLASS_C_DEC \
  82         ranged_hash_fn< \
  83                 Key, \
  84                 Hash_Fn, \
  85                 Allocator, \
  86                 Comb_Hash_Fn, \
  87                 false>
  88
  89     /**
  90      * Specialization 1- The client supplies a hash function and a ranged
  91      *  hash function, and requests that hash values not be stored.
  92      **/
  93     template<typename Key,
  94              class Hash_Fn,
  95              class Allocator,
  96              class Comb_Hash_Fn>
  97     class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> : public Hash_Fn,
  98                                                                          public Comb_Hash_Fn
  99     {
 100     protected:
 101       typedef typename Allocator::size_type size_type;
 102
 103       typedef Hash_Fn my_hash_fn_base;
 104
 105       typedef Comb_Hash_Fn my_comb_hash_fn_base;
 106
 107       typedef typename Allocator::template rebind<Key>::other key_allocator;
 108
 109       typedef typename key_allocator::const_reference const_key_reference;
 110
 111     protected:
 112       ranged_hash_fn(size_type size);
 113
 114       ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn);
 115
 116       ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 117
 118       void
 119       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 120
 121       void
 122       notify_resized(size_type size);
 123
 124       inline size_type
 125       operator()(const_key_reference r_key) const;
 126     };
 127
 128     PB_ASSOC_CLASS_T_DEC
 129     PB_ASSOC_CLASS_C_DEC::
 130     ranged_hash_fn(size_type size)
 131     {
 132       Comb_Hash_Fn::notify_resized(size);
 133     }
 134
 135     PB_ASSOC_CLASS_T_DEC
 136     PB_ASSOC_CLASS_C_DEC::
 137     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
 138       Hash_Fn(r_hash_fn)
 139     {
 140       Comb_Hash_Fn::notify_resized(size);
 141     }
 142
 143     PB_ASSOC_CLASS_T_DEC
 144     PB_ASSOC_CLASS_C_DEC::
 145     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
 146       Hash_Fn(r_hash_fn),
 147       Comb_Hash_Fn(r_comb_hash_fn)
 148     {
 149       my_comb_hash_fn_base::notify_resized(size);
 150     }
 151
 152     PB_ASSOC_CLASS_T_DEC
 153     void
 154     PB_ASSOC_CLASS_C_DEC::
 155     swap(PB_ASSOC_CLASS_C_DEC& r_other)
 156     {
 157       my_comb_hash_fn_base::swap(r_other);
 158
 159       std::swap((Hash_Fn& )(*this), (Hash_Fn& )r_other);
 160     }
 161
 162     PB_ASSOC_CLASS_T_DEC
 163     void
 164     PB_ASSOC_CLASS_C_DEC::
 165     notify_resized(size_type size)
 166     {
 167       my_comb_hash_fn_base::notify_resized(size);
 168     }
 169
 170     PB_ASSOC_CLASS_T_DEC
 171     inline typename PB_ASSOC_CLASS_C_DEC::size_type
 172     PB_ASSOC_CLASS_C_DEC::
 173     operator()(const_key_reference r_key) const
 174     {
 175       return (my_comb_hash_fn_base::operator()(
 176                                                my_hash_fn_base::operator()(r_key)));
 177     }
 178
 179 #undef PB_ASSOC_CLASS_T_DEC
 180 #undef PB_ASSOC_CLASS_C_DEC
 181
 182 #define PB_ASSOC_CLASS_T_DEC \
 183         template< \
 184                 typename Key, \
 185                 class Hash_Fn, \
 186                 class Allocator, \
 187                 class Comb_Hash_Fn>
 188
 189 #define PB_ASSOC_CLASS_C_DEC \
 190         ranged_hash_fn< \
 191                 Key, \
 192                 Hash_Fn, \
 193                 Allocator, \
 194                 Comb_Hash_Fn, \
 195                 true>
 196
 197     /**
 198      * Specialization 2- The client supplies a hash function and a ranged
 199      *  hash function, and requests that hash values be stored.
 200      **/
 201     template<typename Key,
 202              class Hash_Fn,
 203              class Allocator,
 204              class Comb_Hash_Fn>
 205     class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, true> :
 206       public Hash_Fn,
 207       public Comb_Hash_Fn
 208     {
 209     protected:
 210       typedef typename Allocator::size_type size_type;
 211
 212       typedef std::pair<size_type, size_type> comp_hash;
 213
 214       typedef Hash_Fn my_hash_fn_base;
 215
 216       typedef Comb_Hash_Fn my_comb_hash_fn_base;
 217
 218       typedef typename Allocator::template rebind<Key>::other key_allocator;
 219
 220       typedef typename key_allocator::const_reference const_key_reference;
 221
 222     protected:
 223       ranged_hash_fn(size_type size);
 224
 225       ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn);
 226
 227       ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 228
 229       void
 230       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 231
 232       void
 233       notify_resized(size_type size);
 234
 235       inline comp_hash
 236       operator()(const_key_reference r_key) const;
 237
 238       inline comp_hash
 239       operator()(const_key_reference r_key, size_type hash) const;
 240     };
 241
 242     PB_ASSOC_CLASS_T_DEC
 243     PB_ASSOC_CLASS_C_DEC::
 244     ranged_hash_fn(size_type size)
 245     {
 246       Comb_Hash_Fn::notify_resized(size);
 247     }
 248
 249     PB_ASSOC_CLASS_T_DEC
 250     PB_ASSOC_CLASS_C_DEC::
 251     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
 252       Hash_Fn(r_hash_fn)
 253     {
 254       Comb_Hash_Fn::notify_resized(size);
 255     }
 256
 257     PB_ASSOC_CLASS_T_DEC
 258     PB_ASSOC_CLASS_C_DEC::
 259     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
 260       Hash_Fn(r_hash_fn),
 261       Comb_Hash_Fn(r_comb_hash_fn)
 262     {
 263       my_comb_hash_fn_base::notify_resized(size);
 264     }
 265
 266     PB_ASSOC_CLASS_T_DEC
 267     void
 268     PB_ASSOC_CLASS_C_DEC::
 269     swap(PB_ASSOC_CLASS_C_DEC& r_other)
 270     {
 271       my_comb_hash_fn_base::swap(r_other);
 272
 273       std::swap((Hash_Fn& )(*this), (Hash_Fn& )r_other);
 274     }
 275
 276     PB_ASSOC_CLASS_T_DEC
 277     void
 278     PB_ASSOC_CLASS_C_DEC::
 279     notify_resized(size_type size)
 280     {
 281       my_comb_hash_fn_base::notify_resized(size);
 282     }
 283
 284     PB_ASSOC_CLASS_T_DEC
 285     inline typename PB_ASSOC_CLASS_C_DEC::comp_hash
 286     PB_ASSOC_CLASS_C_DEC::
 287     operator()(const_key_reference r_key) const
 288     {
 289       const size_type hash = my_hash_fn_base::operator()(r_key);
 290
 291       return (std::make_pair(my_comb_hash_fn_base::operator()(hash), hash));
 292     }
 293
 294     PB_ASSOC_CLASS_T_DEC
 295     inline typename PB_ASSOC_CLASS_C_DEC::comp_hash
 296     PB_ASSOC_CLASS_C_DEC::
 297     operator()
 298 #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
 299       (const_key_reference r_key, size_type hash) const
 300 #else // #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
 301       (const_key_reference /*r_key*/, size_type hash) const
 302 #endif // #ifdef PB_ASSOC_RANGED_HASH_FN_DEBUG
 303     {
 304       PB_ASSOC_DBG_ASSERT(hash == my_hash_fn_base::operator()(r_key));
 305
 306       return (std::make_pair(my_comb_hash_fn_base::operator()(hash), hash));
 307     }
 308
 309 #undef PB_ASSOC_CLASS_T_DEC
 310 #undef PB_ASSOC_CLASS_C_DEC
 311
 312 #define PB_ASSOC_CLASS_T_DEC \
 313         template<typename Key, class Allocator, class Comb_Hash_Fn>
 314
 315 #define PB_ASSOC_CLASS_C_DEC \
 316         ranged_hash_fn< \
 317                 Key, \
 318                 null_hash_fn, \
 319                 Allocator, \
 320                 Comb_Hash_Fn, \
 321                 false>
 322
 323     /**
 324      * Specialization 3- The client does not supply a hash function
 325      *  (by specifying null_hash_fn as the Hash_Fn parameter),
 326      *  and requests that hash values not be stored.
 327
 328     **/
 329     template<typename Key, class Allocator, class Comb_Hash_Fn>
 330     class ranged_hash_fn<Key, null_hash_fn, Allocator,
 331                          Comb_Hash_Fn, false> :
 332       public null_hash_fn,
 333       public Comb_Hash_Fn
 334     {
 335     protected:
 336
 337       typedef typename Allocator::size_type size_type;
 338
 339       typedef Comb_Hash_Fn my_comb_hash_fn_base;
 340
 341     protected:
 342       ranged_hash_fn(size_type size);
 343
 344       ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn);
 345
 346       ranged_hash_fn(size_type size, const null_hash_fn&r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 347
 348       void
 349       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 350     };
 351
 352     PB_ASSOC_CLASS_T_DEC
 353     PB_ASSOC_CLASS_C_DEC::
 354     ranged_hash_fn(size_type size)
 355     {
 356       Comb_Hash_Fn::notify_resized(size);
 357     }
 358
 359     PB_ASSOC_CLASS_T_DEC
 360     PB_ASSOC_CLASS_C_DEC::
 361     ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
 362       Comb_Hash_Fn(r_comb_hash_fn)
 363     { }
 364
 365     PB_ASSOC_CLASS_T_DEC
 366     PB_ASSOC_CLASS_C_DEC::
 367     ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
 368       Comb_Hash_Fn(r_comb_hash_fn)
 369     { }
 370
 371     PB_ASSOC_CLASS_T_DEC
 372     void
 373     PB_ASSOC_CLASS_C_DEC::
 374     swap(PB_ASSOC_CLASS_C_DEC& r_other)
 375     {
 376       my_comb_hash_fn_base::swap(r_other);
 377     }
 378
 379 #undef PB_ASSOC_CLASS_T_DEC
 380 #undef PB_ASSOC_CLASS_C_DEC
 381
 382 #define PB_ASSOC_CLASS_T_DEC \
 383         template<typename Key, class Allocator, class Comb_Hash_Fn>
 384
 385 #define PB_ASSOC_CLASS_C_DEC \
 386         ranged_hash_fn< \
 387                 Key, \
 388                 null_hash_fn, \
 389                 Allocator, \
 390                 Comb_Hash_Fn, \
 391                 true>
 392
 393     /**
 394      * Specialization 4- The client does not supply a hash function
 395      *  (by specifying null_hash_fn as the Hash_Fn parameter),
 396      *  and requests that hash values be stored.
 397
 398     **/
 399     template<typename Key, class Allocator, class Comb_Hash_Fn>
 400     class ranged_hash_fn<Key, null_hash_fn, Allocator,
 401                          Comb_Hash_Fn, true> :
 402       public null_hash_fn,
 403       public Comb_Hash_Fn
 404     {
 405     protected:
 406       typedef typename Allocator::size_type size_type;
 407
 408       typedef Comb_Hash_Fn my_comb_hash_fn_base;
 409
 410     protected:
 411       ranged_hash_fn(size_type size);
 412
 413       ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn);
 414
 415       ranged_hash_fn(size_type size, const null_hash_fn&r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 416
 417       void
 418       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 419     };
 420
 421     PB_ASSOC_CLASS_T_DEC
 422     PB_ASSOC_CLASS_C_DEC::
 423     ranged_hash_fn(size_type size)
 424     {
 425       Comb_Hash_Fn::notify_resized(size);
 426     }
 427
 428     PB_ASSOC_CLASS_T_DEC
 429     PB_ASSOC_CLASS_C_DEC::
 430     ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
 431       Comb_Hash_Fn(r_comb_hash_fn)
 432     { }
 433
 434     PB_ASSOC_CLASS_T_DEC
 435     PB_ASSOC_CLASS_C_DEC::
 436     ranged_hash_fn(size_type size, const null_hash_fn&r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
 437       Comb_Hash_Fn(r_comb_hash_fn)
 438     { }
 439
 440     PB_ASSOC_CLASS_T_DEC
 441     void
 442     PB_ASSOC_CLASS_C_DEC::
 443     swap(PB_ASSOC_CLASS_C_DEC& r_other)
 444     {
 445       my_comb_hash_fn_base::swap(r_other);
 446     }
 447
 448 #undef PB_ASSOC_CLASS_T_DEC
 449 #undef PB_ASSOC_CLASS_C_DEC
 450
 451 #undef PB_ASSOC_DBG_ASSERT
 452 #undef PB_ASSOC_DBG_VERIFY
 453 #undef PB_ASSOC_DBG_ONLY
 454
 455   } // namespace detail
 456
 457 } // namespace pb_assoc
 458
 459 #endif // #ifndef RANGED_HASH_FN_HPP