GNU C++ STL: ranged_probe_fn.hpp Source File

00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00031 
00032 // Permission to use, copy, modify, sell, and distribute this software
00033 // is hereby granted without fee, provided that the above copyright
00034 // notice appears in all copies, and that both that copyright notice and
00035 // this permission notice appear in supporting documentation. None of
00036 // the above authors, nor IBM Haifa Research Laboratories, make any
00037 // representation about the suitability of this software for any
00038 // purpose. It is provided "as is" without express or implied warranty.
00039 
00046 #ifndef RANGED_PROBE_FN_HPP
00047 #define RANGED_PROBE_FN_HPP
00048 
00049 #include <ext/pb_assoc/hash_policy.hpp>
00050 #include <utility>
00051 
00052 namespace pb_assoc
00053 {
00054 
00055   namespace detail
00056   {
00057 
00058 #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00059 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00060 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00061 #define PB_ASSOC_DBG_ONLY(X) X
00062 #else // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00063 #define PB_ASSOC_DBG_ASSERT(X)
00064 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00065 #define PB_ASSOC_DBG_ONLY(X) ;
00066 #endif // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00067 
00068     template<typename Key,
00069          class Hash_Fn,
00070          class Allocator,
00071          class Comb_Probe_Fn,
00072          class Probe_Fn,
00073          bool Store_Hash>
00074     class ranged_probe_fn;
00075 
00076 #define PB_ASSOC_CLASS_T_DEC \
00077     template< \
00078         typename Key, \
00079         class Hash_Fn, \
00080         class Allocator, \
00081         class Comb_Probe_Fn, \
00082         class Probe_Fn>
00083 
00084 #define PB_ASSOC_CLASS_C_DEC \
00085     ranged_probe_fn< \
00086         Key, \
00087         Hash_Fn, \
00088         Allocator, \
00089         Comb_Probe_Fn, \
00090         Probe_Fn, \
00091         false>
00092 
00097     template<typename Key,
00098          class Hash_Fn,
00099          class Allocator,
00100          class Comb_Probe_Fn,
00101          class Probe_Fn>
00102     class ranged_probe_fn<
00103       Key,
00104       Hash_Fn,
00105       Allocator,
00106       Comb_Probe_Fn,
00107       Probe_Fn,
00108       false> : public Hash_Fn,
00109            public Comb_Probe_Fn,
00110            public Probe_Fn
00111     {
00112     protected:
00113       typedef typename Allocator::size_type size_type;
00114 
00115       typedef Comb_Probe_Fn my_comb_probe_fn_base;
00116 
00117       typedef Hash_Fn my_hash_fn_base;
00118 
00119       typedef Probe_Fn my_probe_fn_base;
00120 
00121       typedef typename Allocator::template rebind< Key>::other key_allocator;
00122 
00123       typedef typename key_allocator::const_reference const_key_reference;
00124 
00125     protected:
00126       ranged_probe_fn(size_type size);
00127 
00128       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
00129 
00130       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
00131 
00132       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);
00133 
00134       void
00135       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00136 
00137       void
00138       notify_resized(size_type size);
00139 
00140       inline size_type
00141       operator()(const_key_reference r_key) const;
00142 
00143       inline size_type
00144       operator()(const_key_reference r_key, size_type hash, size_type i) const;
00145     };
00146 
00147     PB_ASSOC_CLASS_T_DEC
00148     PB_ASSOC_CLASS_C_DEC::
00149     ranged_probe_fn(size_type size)
00150     {
00151       Comb_Probe_Fn::notify_resized(size);
00152     }
00153 
00154     PB_ASSOC_CLASS_T_DEC
00155     PB_ASSOC_CLASS_C_DEC::
00156     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
00157       Hash_Fn(r_hash_fn)
00158     {
00159       Comb_Probe_Fn::notify_resized(size);
00160     }
00161 
00162     PB_ASSOC_CLASS_T_DEC
00163     PB_ASSOC_CLASS_C_DEC::
00164     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
00165       Hash_Fn(r_hash_fn),
00166       Comb_Probe_Fn(r_comb_probe_fn)
00167     {
00168       my_comb_probe_fn_base::notify_resized(size);
00169     }
00170 
00171     PB_ASSOC_CLASS_T_DEC
00172     PB_ASSOC_CLASS_C_DEC::
00173     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) :
00174       Hash_Fn(r_hash_fn),
00175       Comb_Probe_Fn(r_comb_probe_fn),
00176       Probe_Fn(r_probe_fn)
00177     {
00178       my_comb_probe_fn_base::notify_resized(size);
00179     }
00180 
00181     PB_ASSOC_CLASS_T_DEC
00182     void
00183     PB_ASSOC_CLASS_C_DEC::
00184     swap(PB_ASSOC_CLASS_C_DEC& r_other)
00185     {
00186       my_comb_probe_fn_base::swap(r_other);
00187 
00188       std::swap((Hash_Fn& )(*this), (Hash_Fn& )r_other);
00189     }
00190 
00191     PB_ASSOC_CLASS_T_DEC
00192     void
00193     PB_ASSOC_CLASS_C_DEC::
00194     notify_resized(size_type size)
00195     {
00196       my_comb_probe_fn_base::notify_resized(size);
00197     }
00198 
00199     PB_ASSOC_CLASS_T_DEC
00200     inline typename PB_ASSOC_CLASS_C_DEC::size_type
00201     PB_ASSOC_CLASS_C_DEC::
00202     operator()(const_key_reference r_key) const
00203     {
00204       return (my_comb_probe_fn_base::operator()(
00205                         my_hash_fn_base::operator()(r_key)));
00206     }
00207 
00208     PB_ASSOC_CLASS_T_DEC
00209     inline typename PB_ASSOC_CLASS_C_DEC::size_type
00210     PB_ASSOC_CLASS_C_DEC::
00211     operator()(const_key_reference r_key, size_type hash, size_type i) const
00212     {
00213       return (my_comb_probe_fn_base::operator()(
00214                         hash + my_probe_fn_base::operator()(r_key, i)));
00215     }
00216 
00217 #undef PB_ASSOC_CLASS_T_DEC
00218 #undef PB_ASSOC_CLASS_C_DEC
00219 
00220 #define PB_ASSOC_CLASS_T_DEC \
00221     template< \
00222         typename Key, \
00223         class Hash_Fn, \
00224         class Allocator, \
00225         class Comb_Probe_Fn, \
00226         class Probe_Fn>
00227 
00228 #define PB_ASSOC_CLASS_C_DEC \
00229     ranged_probe_fn< \
00230         Key, \
00231         Hash_Fn, \
00232         Allocator, \
00233         Comb_Probe_Fn, \
00234         Probe_Fn, \
00235         true>
00236 
00241     template<typename Key,
00242          class Hash_Fn,
00243          class Allocator,
00244          class Comb_Probe_Fn,
00245          class Probe_Fn>
00246     class ranged_probe_fn<
00247       Key,
00248       Hash_Fn,
00249       Allocator,
00250       Comb_Probe_Fn,
00251       Probe_Fn,
00252       true> :
00253       public Hash_Fn,
00254       public Comb_Probe_Fn,
00255       public Probe_Fn
00256     {
00257     protected:
00258       typedef typename Allocator::size_type size_type;
00259 
00260       typedef std::pair<size_type, size_type> comp_hash;
00261 
00262       typedef Comb_Probe_Fn my_comb_probe_fn_base;
00263 
00264       typedef Hash_Fn my_hash_fn_base;
00265 
00266       typedef Probe_Fn my_probe_fn_base;
00267 
00268       typedef typename Allocator::template rebind<Key>::other key_allocator;
00269 
00270       typedef typename key_allocator::const_reference const_key_reference;
00271 
00272     protected:
00273       ranged_probe_fn(size_type size);
00274 
00275       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
00276 
00277       ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
00278 
00279       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);
00280 
00281       void
00282       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00283 
00284       void
00285       notify_resized(size_type size);
00286 
00287       inline comp_hash
00288       operator()(const_key_reference r_key) const;
00289 
00290       inline size_type
00291       operator()(const_key_reference r_key, size_type hash, size_type i) const;
00292 
00293       inline size_type
00294       operator()(const_key_reference r_key, size_type hash) const;
00295     };
00296 
00297     PB_ASSOC_CLASS_T_DEC
00298     PB_ASSOC_CLASS_C_DEC::
00299     ranged_probe_fn(size_type size)
00300     {
00301       Comb_Probe_Fn::notify_resized(size);
00302     }
00303 
00304     PB_ASSOC_CLASS_T_DEC
00305     PB_ASSOC_CLASS_C_DEC::
00306     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
00307       Hash_Fn(r_hash_fn)
00308     {
00309       Comb_Probe_Fn::notify_resized(size);
00310     }
00311 
00312     PB_ASSOC_CLASS_T_DEC
00313     PB_ASSOC_CLASS_C_DEC::
00314     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
00315       Hash_Fn(r_hash_fn),
00316       Comb_Probe_Fn(r_comb_probe_fn)
00317     {
00318       my_comb_probe_fn_base::notify_resized(size);
00319     }
00320 
00321     PB_ASSOC_CLASS_T_DEC
00322     PB_ASSOC_CLASS_C_DEC::
00323     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) :
00324       Hash_Fn(r_hash_fn),
00325       Comb_Probe_Fn(r_comb_probe_fn),
00326       Probe_Fn(r_probe_fn)
00327     {
00328       my_comb_probe_fn_base::notify_resized(size);
00329     }
00330 
00331     PB_ASSOC_CLASS_T_DEC
00332     void
00333     PB_ASSOC_CLASS_C_DEC::
00334     swap(PB_ASSOC_CLASS_C_DEC& r_other)
00335     {
00336       my_comb_probe_fn_base::swap(r_other);
00337 
00338       std::swap((Hash_Fn& )(*this), (Hash_Fn& )r_other);
00339     }
00340 
00341     PB_ASSOC_CLASS_T_DEC
00342     void
00343     PB_ASSOC_CLASS_C_DEC::
00344     notify_resized(size_type size)
00345     {
00346       my_comb_probe_fn_base::notify_resized(size);
00347     }
00348 
00349     PB_ASSOC_CLASS_T_DEC
00350     inline typename PB_ASSOC_CLASS_C_DEC::comp_hash
00351     PB_ASSOC_CLASS_C_DEC::
00352     operator()(const_key_reference r_key) const
00353     {
00354       const size_type hash = my_hash_fn_base::operator()(r_key);
00355 
00356       return (std::make_pair(my_comb_probe_fn_base::operator()(hash), hash));
00357     }
00358 
00359     PB_ASSOC_CLASS_T_DEC
00360     inline typename PB_ASSOC_CLASS_C_DEC::size_type
00361     PB_ASSOC_CLASS_C_DEC::
00362     operator()(const_key_reference r_key, size_type hash, size_type i) const
00363     {
00364       return (my_comb_probe_fn_base::operator()(
00365                         hash + my_probe_fn_base::operator()(r_key, i)));
00366     }
00367 
00368     PB_ASSOC_CLASS_T_DEC
00369     inline typename PB_ASSOC_CLASS_C_DEC::size_type
00370     PB_ASSOC_CLASS_C_DEC::
00371     operator()
00372 #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00373       (const_key_reference r_key, size_type hash) const
00374 #else // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00375       (const_key_reference /*r_key*/, size_type hash) const
00376 #endif // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
00377     {
00378       PB_ASSOC_DBG_ASSERT(hash == my_hash_fn_base::operator()(r_key));
00379 
00380       return (hash);
00381     }
00382 
00383 #undef PB_ASSOC_CLASS_T_DEC
00384 #undef PB_ASSOC_CLASS_C_DEC
00385 
00386 #define PB_ASSOC_CLASS_T_DEC \
00387     template<typename Key, class Allocator, class Comb_Probe_Fn>
00388 
00389 #define PB_ASSOC_CLASS_C_DEC \
00390     ranged_probe_fn< \
00391         Key, \
00392         null_hash_fn, \
00393         Allocator, \
00394         Comb_Probe_Fn, \
00395         null_probe_fn, \
00396         false>
00397 
00402     template<typename Key, class Allocator, class Comb_Probe_Fn>
00403     class ranged_probe_fn<
00404       Key,
00405       null_hash_fn,
00406       Allocator,
00407       Comb_Probe_Fn,
00408       null_probe_fn,
00409       false> :
00410       public Comb_Probe_Fn,
00411       public null_hash_fn,
00412       public null_probe_fn
00413     {
00414     protected:
00415       typedef typename Allocator::size_type size_type;
00416 
00417       typedef Comb_Probe_Fn my_comb_probe_fn_base;
00418 
00419       typedef typename Allocator::template rebind<Key>::other key_allocator;
00420 
00421       typedef typename key_allocator::const_reference const_key_reference;
00422 
00423     protected:
00424       ranged_probe_fn(size_type size);
00425 
00426       ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn);
00427 
00428       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);
00429 
00430       void
00431       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00432     };
00433 
00434     PB_ASSOC_CLASS_T_DEC
00435     PB_ASSOC_CLASS_C_DEC::
00436     ranged_probe_fn(size_type size)
00437     {
00438       Comb_Probe_Fn::notify_resized(size);
00439     }
00440 
00441     PB_ASSOC_CLASS_T_DEC
00442     PB_ASSOC_CLASS_C_DEC::
00443     ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn) :
00444       Comb_Probe_Fn(r_comb_probe_fn)
00445     { }
00446 
00447     PB_ASSOC_CLASS_T_DEC
00448     PB_ASSOC_CLASS_C_DEC::
00449     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) :
00450       Comb_Probe_Fn(r_comb_probe_fn)
00451     { }
00452 
00453     PB_ASSOC_CLASS_T_DEC
00454     void
00455     PB_ASSOC_CLASS_C_DEC::
00456     swap(PB_ASSOC_CLASS_C_DEC& r_other)
00457     {
00458       my_comb_probe_fn_base::swap(r_other);
00459     }
00460 
00461 #undef PB_ASSOC_CLASS_T_DEC
00462 #undef PB_ASSOC_CLASS_C_DEC
00463 
00464 #undef PB_ASSOC_DBG_ASSERT
00465 #undef PB_ASSOC_DBG_VERIFY
00466 #undef PB_ASSOC_DBG_ONLY
00467 
00468   } // namespace detail
00469 
00470 } // namespace pb_assoc
00471 
00472 #endif // #ifndef RANGED_PROBE_FN_HPP
00473