[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / hash_fn / ranged_probe_fn.hpp

// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file ranged_probe_fn.hpp
 * Contains a unified ranged probe functor, allowing the probe tables to deal with
 *    a single class for ranged probeing.
 */

#ifndef PB_DS_RANGED_PROBE_FN_HPP
#define PB_DS_RANGED_PROBE_FN_HPP

#include <ext/pb_ds/detail/basic_types.hpp>
#include <utility>

namespace pb_ds
{
  namespace detail
  {

#ifdef PB_DS_RANGED_PROBE_FN_DEBUG
#define PB_DS_DBG_ASSERT(X) assert(X)
#define PB_DS_DBG_VERIFY(X) assert(X)
#define PB_DS_DBG_ONLY(X) X
#else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
#define PB_DS_DBG_ASSERT(X)
#define PB_DS_DBG_VERIFY(X) {if((X)==0);}
#define PB_DS_DBG_ONLY(X) ;
#endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG

    template<typename Key,
	     class Hash_Fn,
	     class Allocator,
	     class Comb_Probe_Fn,
	     class Probe_Fn,
	     bool Store_Hash>
    class ranged_probe_fn;

#define PB_DS_CLASS_T_DEC						\
    template<								\
						typename Key,		\
						class Hash_Fn,		\
						class Allocator,	\
						class Comb_Probe_Fn,	\
						class Probe_Fn>

#define PB_DS_CLASS_C_DEC					\
    ranged_probe_fn<						\
						Key,		\
						Hash_Fn,	\
						Allocator,	\
						Comb_Probe_Fn,	\
						Probe_Fn,	\
						false>

    /**
     * Specialization 1- The client supplies a probe function and a ranged
     *    probe function, and requests that hash values not be stored.
     **/
    template<typename Key,
	     class Hash_Fn,
	     class Allocator,
	     class Comb_Probe_Fn,
	     class Probe_Fn>
    class ranged_probe_fn<
      Key,
      Hash_Fn,
      Allocator,
      Comb_Probe_Fn,
      Probe_Fn,
      false> : public Hash_Fn,
	       public Comb_Probe_Fn,
	       public Probe_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;

      typedef Comb_Probe_Fn comb_probe_fn_base;

      typedef Hash_Fn hash_fn_base;

      typedef Probe_Fn probe_fn_base;

      typedef typename Allocator::template rebind<Key>::other key_allocator;

      typedef typename key_allocator::const_reference const_key_reference;

    protected:
      ranged_probe_fn(size_type size);

      ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);

      ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);

      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);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      void
      notify_resized(size_type size);

      inline size_type
      operator()(const_key_reference r_key) const;

      inline size_type
      operator()(const_key_reference r_key, size_type hash, size_type i) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size)
    {
      Comb_Probe_Fn::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
      Hash_Fn(r_hash_fn)
    {
      Comb_Probe_Fn::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
      Hash_Fn(r_hash_fn),
      Comb_Probe_Fn(r_comb_probe_fn)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    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) :
      Hash_Fn(r_hash_fn),
      Comb_Probe_Fn(r_comb_probe_fn),
      Probe_Fn(r_probe_fn)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_probe_fn_base::swap(other);

      std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    {
      return (comb_probe_fn_base::operator()(
					     hash_fn_base::operator()(r_key)));
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
    {
      return (comb_probe_fn_base::operator()(
					     hash + probe_fn_base::operator()(i)));
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC						\
    template<								\
						typename Key,		\
						class Hash_Fn,		\
						class Allocator,	\
						class Comb_Probe_Fn,	\
						class Probe_Fn>

#define PB_DS_CLASS_C_DEC					\
    ranged_probe_fn<						\
						Key,		\
						Hash_Fn,	\
						Allocator,	\
						Comb_Probe_Fn,	\
						Probe_Fn,	\
						true>

    /**
     * Specialization 2- The client supplies a probe function and a ranged
     *    probe function, and requests that hash values not be stored.
     **/
    template<typename Key,
	     class Hash_Fn,
	     class Allocator,
	     class Comb_Probe_Fn,
	     class Probe_Fn>
    class ranged_probe_fn<
      Key,
      Hash_Fn,
      Allocator,
      Comb_Probe_Fn,
      Probe_Fn,
      true> :
      public Hash_Fn,
      public Comb_Probe_Fn,
      public Probe_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;

      typedef typename comp_hash_<size_type>::comp_hash comp_hash;

      typedef Comb_Probe_Fn comb_probe_fn_base;

      typedef Hash_Fn hash_fn_base;

      typedef Probe_Fn probe_fn_base;

      typedef typename Allocator::template rebind<Key>::other key_allocator;

      typedef typename key_allocator::const_reference const_key_reference;

    protected:
      ranged_probe_fn(size_type size);

      ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);

      ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);

      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);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      void
      notify_resized(size_type size);

      inline comp_hash
      operator()(const_key_reference r_key) const;

      inline size_type
      operator()(const_key_reference r_key, size_type hash, size_type i) const;

      inline size_type
      operator()(const_key_reference r_key, size_type hash) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size)
    {
      Comb_Probe_Fn::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
      Hash_Fn(r_hash_fn)
    {
      Comb_Probe_Fn::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
      Hash_Fn(r_hash_fn),
      Comb_Probe_Fn(r_comb_probe_fn)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    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) :
      Hash_Fn(r_hash_fn),
      Comb_Probe_Fn(r_comb_probe_fn),
      Probe_Fn(r_probe_fn)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_probe_fn_base::swap(other);

      std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    {
      comb_probe_fn_base::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::comp_hash
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    {
      const size_type hash = hash_fn_base::operator()(r_key);

      return (std::make_pair(comb_probe_fn_base::operator()(hash), hash));
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
    {
      return (comb_probe_fn_base::operator()(
					     hash + probe_fn_base::operator()(i)));
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()
#ifdef PB_DS_RANGED_PROBE_FN_DEBUG
      (const_key_reference r_key, size_type hash) const
#else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
      (const_key_reference /*r_key*/, size_type hash) const
#endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
    {
      PB_DS_DBG_ASSERT(hash == hash_fn_base::operator()(r_key));

      return (hash);
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC						\
    template<typename Key, class Allocator, class Comb_Probe_Fn>

#define PB_DS_CLASS_C_DEC					\
    ranged_probe_fn<						\
						Key,		\
						null_hash_fn,	\
						Allocator,	\
						Comb_Probe_Fn,	\
						null_probe_fn,	\
						false>

    /**
     * Specialization 3 and 4- The client does not supply a hash function or
     *    probe function, and requests that hash values not be stored.
     **/
    template<typename Key, class Allocator, class Comb_Probe_Fn>
    class ranged_probe_fn<
      Key,
      null_hash_fn,
      Allocator,
      Comb_Probe_Fn,
      null_probe_fn,
      false> :
      public Comb_Probe_Fn,
      public null_hash_fn,
      public null_probe_fn
    {
    protected:
      typedef typename Allocator::size_type size_type;

      typedef Comb_Probe_Fn comb_probe_fn_base;

      typedef typename Allocator::template rebind<Key>::other key_allocator;

      typedef typename key_allocator::const_reference const_key_reference;

    protected:
      ranged_probe_fn(size_type size);

      ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn);

      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);

      void
      swap(PB_DS_CLASS_C_DEC& other);
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size)
    {
      Comb_Probe_Fn::notify_resized(size);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn) :
      Comb_Probe_Fn(r_comb_probe_fn)
    { }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    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) :
      Comb_Probe_Fn(r_comb_probe_fn)
    { }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_probe_fn_base::swap(other);
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#undef PB_DS_DBG_ASSERT
#undef PB_DS_DBG_VERIFY
#undef PB_DS_DBG_ONLY

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_RANGED_PROBE_FN_HPP
Commit	Line	Data
fd1e1726 BK	1	// -- C++ --
fd1e1726 BK	2
4569a895	3	// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
fd1e1726 BK	4	//
fd1e1726 BK	5	// This file is part of the GNU ISO C++ Library. This library is free
4569a895 AT	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.
fd1e1726 BK	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
4569a895 AT	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
fd1e1726	38	// representation about the suitability of this software for any
4569a895 AT	39	// purpose. It is provided "as is" without express or implied
4569a895 AT	40	// warranty.
fd1e1726 BK	41
	42	/**
	43	* @file ranged_probe_fn.hpp
	44	* Contains a unified ranged probe functor, allowing the probe tables to deal with
4569a895	45	* a single class for ranged probeing.
fd1e1726 BK	46	*/
fd1e1726 BK	47
4569a895 AT	48	#ifndef PB_DS_RANGED_PROBE_FN_HPP
4569a895 AT	49	#define PB_DS_RANGED_PROBE_FN_HPP
fd1e1726	50
4569a895	51	#include <ext/pb_ds/detail/basic_types.hpp>
fd1e1726 BK	52	#include <utility>
fd1e1726 BK	53
4569a895	54	namespace pb_ds
fd1e1726	55	{
fd1e1726 BK	56	namespace detail
	57	{
	58
4569a895 AT	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
fd1e1726 BK	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
4569a895 AT	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>
fd1e1726 BK	93
	94	/**
	95	* Specialization 1- The client supplies a probe function and a ranged
4569a895	96	* probe function, and requests that hash values not be stored.
fd1e1726 BK	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
4569a895	116	typedef Comb_Probe_Fn comb_probe_fn_base;
fd1e1726	117
4569a895	118	typedef Hash_Fn hash_fn_base;
fd1e1726	119
4569a895	120	typedef Probe_Fn probe_fn_base;
fd1e1726	121
4569a895	122	typedef typename Allocator::template rebind<Key>::other key_allocator;
fd1e1726 BK	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
4569a895	136	swap(PB_DS_CLASS_C_DEC& other);
fd1e1726 BK	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
4569a895 AT	148	PB_DS_CLASS_T_DEC
4569a895 AT	149	PB_DS_CLASS_C_DEC::
fd1e1726 BK	150	ranged_probe_fn(size_type size)
	151	{
	152	Comb_Probe_Fn::notify_resized(size);
	153	}
	154
4569a895 AT	155	PB_DS_CLASS_T_DEC
4569a895 AT	156	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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
4569a895 AT	163	PB_DS_CLASS_T_DEC
4569a895 AT	164	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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	{
4569a895	169	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	170	}
fd1e1726 BK	171
4569a895 AT	172	PB_DS_CLASS_T_DEC
4569a895 AT	173	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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	{
4569a895	179	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	180	}
fd1e1726 BK	181
4569a895	182	PB_DS_CLASS_T_DEC
fd1e1726	183	void
4569a895 AT	184	PB_DS_CLASS_C_DEC::
4569a895 AT	185	swap(PB_DS_CLASS_C_DEC& other)
fd1e1726	186	{
4569a895	187	comb_probe_fn_base::swap(other);
fd1e1726	188
4569a895	189	std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
fd1e1726 BK	190	}
fd1e1726 BK	191
4569a895	192	PB_DS_CLASS_T_DEC
fd1e1726	193	void
4569a895	194	PB_DS_CLASS_C_DEC::
fd1e1726 BK	195	notify_resized(size_type size)
fd1e1726 BK	196	{
4569a895	197	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	198	}
fd1e1726 BK	199
4569a895 AT	200	PB_DS_CLASS_T_DEC
	201	inline typename PB_DS_CLASS_C_DEC::size_type
	202	PB_DS_CLASS_C_DEC::
fd1e1726 BK	203	operator()(const_key_reference r_key) const
fd1e1726 BK	204	{
4569a895 AT	205	return (comb_probe_fn_base::operator()(
4569a895 AT	206	hash_fn_base::operator()(r_key)));
fd1e1726 BK	207	}
fd1e1726 BK	208
4569a895 AT	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
fd1e1726	213	{
4569a895 AT	214	return (comb_probe_fn_base::operator()(
4569a895 AT	215	hash + probe_fn_base::operator()(i)));
fd1e1726 BK	216	}
fd1e1726 BK	217
4569a895 AT	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>
fd1e1726 BK	237
	238	/**
	239	* Specialization 2- The client supplies a probe function and a ranged
4569a895	240	* probe function, and requests that hash values not be stored.
fd1e1726 BK	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
4569a895	261	typedef typename comp_hash_<size_type>::comp_hash comp_hash;
fd1e1726	262
4569a895	263	typedef Comb_Probe_Fn comb_probe_fn_base;
fd1e1726	264
4569a895	265	typedef Hash_Fn hash_fn_base;
fd1e1726	266
4569a895	267	typedef Probe_Fn probe_fn_base;
fd1e1726 BK	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
4569a895	283	swap(PB_DS_CLASS_C_DEC& other);
fd1e1726 BK	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
4569a895 AT	298	PB_DS_CLASS_T_DEC
4569a895 AT	299	PB_DS_CLASS_C_DEC::
fd1e1726 BK	300	ranged_probe_fn(size_type size)
	301	{
	302	Comb_Probe_Fn::notify_resized(size);
	303	}
	304
4569a895 AT	305	PB_DS_CLASS_T_DEC
4569a895 AT	306	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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
4569a895 AT	313	PB_DS_CLASS_T_DEC
4569a895 AT	314	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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	{
4569a895	319	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	320	}
fd1e1726 BK	321
4569a895 AT	322	PB_DS_CLASS_T_DEC
4569a895 AT	323	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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	{
4569a895	329	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	330	}
fd1e1726 BK	331
4569a895	332	PB_DS_CLASS_T_DEC
fd1e1726	333	void
4569a895 AT	334	PB_DS_CLASS_C_DEC::
4569a895 AT	335	swap(PB_DS_CLASS_C_DEC& other)
fd1e1726	336	{
4569a895	337	comb_probe_fn_base::swap(other);
fd1e1726	338
4569a895	339	std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
fd1e1726 BK	340	}
fd1e1726 BK	341
4569a895	342	PB_DS_CLASS_T_DEC
fd1e1726	343	void
4569a895	344	PB_DS_CLASS_C_DEC::
fd1e1726 BK	345	notify_resized(size_type size)
fd1e1726 BK	346	{
4569a895	347	comb_probe_fn_base::notify_resized(size);
fd1e1726 BK	348	}
fd1e1726 BK	349
4569a895 AT	350	PB_DS_CLASS_T_DEC
	351	inline typename PB_DS_CLASS_C_DEC::comp_hash
	352	PB_DS_CLASS_C_DEC::
fd1e1726 BK	353	operator()(const_key_reference r_key) const
fd1e1726 BK	354	{
4569a895	355	const size_type hash = hash_fn_base::operator()(r_key);
fd1e1726	356
4569a895	357	return (std::make_pair(comb_probe_fn_base::operator()(hash), hash));
fd1e1726 BK	358	}
fd1e1726 BK	359
4569a895 AT	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
fd1e1726	364	{
4569a895 AT	365	return (comb_probe_fn_base::operator()(
4569a895 AT	366	hash + probe_fn_base::operator()(i)));
fd1e1726 BK	367	}
fd1e1726 BK	368
4569a895 AT	369	PB_DS_CLASS_T_DEC
	370	inline typename PB_DS_CLASS_C_DEC::size_type
	371	PB_DS_CLASS_C_DEC::
fd1e1726	372	operator()
4569a895	373	#ifdef PB_DS_RANGED_PROBE_FN_DEBUG
fd1e1726	374	(const_key_reference r_key, size_type hash) const
4569a895	375	#else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
fd1e1726	376	(const_key_reference /r_key/, size_type hash) const
4569a895	377	#endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
fd1e1726	378	{
4569a895	379	PB_DS_DBG_ASSERT(hash == hash_fn_base::operator()(r_key));
fd1e1726 BK	380
	381	return (hash);
	382	}
	383
4569a895 AT	384	#undef PB_DS_CLASS_T_DEC
4569a895 AT	385	#undef PB_DS_CLASS_C_DEC
fd1e1726	386
4569a895 AT	387	#define PB_DS_CLASS_T_DEC \
4569a895 AT	388	template<typename Key, class Allocator, class Comb_Probe_Fn>
fd1e1726	389
4569a895 AT	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>
fd1e1726 BK	398
	399	/**
	400	* Specialization 3 and 4- The client does not supply a hash function or
4569a895	401	* probe function, and requests that hash values not be stored.
fd1e1726 BK	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
4569a895	418	typedef Comb_Probe_Fn comb_probe_fn_base;
fd1e1726 BK	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
4569a895	432	swap(PB_DS_CLASS_C_DEC& other);
fd1e1726 BK	433	};
fd1e1726 BK	434
4569a895 AT	435	PB_DS_CLASS_T_DEC
4569a895 AT	436	PB_DS_CLASS_C_DEC::
fd1e1726 BK	437	ranged_probe_fn(size_type size)
	438	{
	439	Comb_Probe_Fn::notify_resized(size);
	440	}
	441
4569a895 AT	442	PB_DS_CLASS_T_DEC
4569a895 AT	443	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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
4569a895 AT	448	PB_DS_CLASS_T_DEC
4569a895 AT	449	PB_DS_CLASS_C_DEC::
fd1e1726 BK	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
4569a895	454	PB_DS_CLASS_T_DEC
fd1e1726	455	void
4569a895 AT	456	PB_DS_CLASS_C_DEC::
4569a895 AT	457	swap(PB_DS_CLASS_C_DEC& other)
fd1e1726	458	{
4569a895	459	comb_probe_fn_base::swap(other);
fd1e1726 BK	460	}
fd1e1726 BK	461
4569a895 AT	462	#undef PB_DS_CLASS_T_DEC
4569a895 AT	463	#undef PB_DS_CLASS_C_DEC
fd1e1726	464
4569a895 AT	465	#undef PB_DS_DBG_ASSERT
	466	#undef PB_DS_DBG_VERIFY
	467	#undef PB_DS_DBG_ONLY
fd1e1726 BK	468
fd1e1726 BK	469	} // namespace detail
4569a895	470	} // namespace pb_ds
fd1e1726	471
4569a895	472	#endif // #ifndef PB_DS_RANGED_PROBE_FN_HPP
fd1e1726	473