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