Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 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 3, 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. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  27. // Permission to use, copy, modify, sell, and distribute this software
  28. // is hereby granted without fee, provided that the above copyright
  29. // notice appears in all copies, and that both that copyright notice
  30. // and this permission notice appear in supporting documentation. None
  31. // of the above authors, nor IBM Haifa Research Laboratories, make any
  32. // representation about the suitability of this software for any
  33. // purpose. It is provided "as is" without express or implied
  34. // warranty.
  35.  
  36. /**
  37.  * @file ranged_probe_fn.hpp
  38.  * Contains a unified ranged probe functor, allowing the probe tables to deal with
  39.  *    a single class for ranged probeing.
  40.  */
  41.  
  42. #ifndef PB_DS_RANGED_PROBE_FN_HPP
  43. #define PB_DS_RANGED_PROBE_FN_HPP
  44.  
  45. #include <utility>
  46. #include <debug/debug.h>
  47.  
  48. namespace __gnu_pbds
  49. {
  50.   namespace detail
  51.   {
  52.     /// Primary template.
  53.     template<typename Key, typename Hash_Fn, typename _Alloc,
  54.              typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
  55.     class ranged_probe_fn;
  56.  
  57. #define PB_DS_CLASS_T_DEC \
  58.     template<typename Key, typename Hash_Fn, typename _Alloc, \
  59.              typename Comb_Probe_Fn, typename Probe_Fn>
  60.  
  61. #define PB_DS_CLASS_C_DEC \
  62.     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false>
  63.  
  64.     /**
  65.      * Specialization 1    
  66.      * The client supplies a probe function and a ranged probe
  67.      * function, and requests that hash values not be stored.
  68.      **/
  69.     template<typename Key, typename Hash_Fn, typename _Alloc,
  70.              typename Comb_Probe_Fn, typename Probe_Fn>
  71.     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
  72.                           Probe_Fn, false>
  73.     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
  74.     {
  75.     protected:
  76.       typedef typename _Alloc::size_type size_type;
  77.       typedef Comb_Probe_Fn comb_probe_fn_base;
  78.       typedef Hash_Fn hash_fn_base;
  79.       typedef Probe_Fn probe_fn_base;
  80.       typedef typename _Alloc::template rebind<Key>::other key_allocator;
  81.       typedef typename key_allocator::const_reference key_const_reference;
  82.  
  83.       ranged_probe_fn(size_type);
  84.  
  85.       ranged_probe_fn(size_type, const Hash_Fn&);
  86.  
  87.       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);
  88.  
  89.       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
  90.                       const Probe_Fn&);
  91.  
  92.       void
  93.       swap(PB_DS_CLASS_C_DEC&);
  94.  
  95.       void
  96.       notify_resized(size_type);
  97.  
  98.       inline size_type
  99.       operator()(key_const_reference) const;
  100.  
  101.       inline size_type
  102.       operator()(key_const_reference, size_type, size_type) const;
  103.     };
  104.  
  105.     PB_DS_CLASS_T_DEC
  106.     PB_DS_CLASS_C_DEC::
  107.     ranged_probe_fn(size_type size)
  108.     { Comb_Probe_Fn::notify_resized(size); }
  109.  
  110.     PB_DS_CLASS_T_DEC
  111.     PB_DS_CLASS_C_DEC::
  112.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
  113.     : Hash_Fn(r_hash_fn)
  114.     { Comb_Probe_Fn::notify_resized(size); }
  115.  
  116.     PB_DS_CLASS_T_DEC
  117.     PB_DS_CLASS_C_DEC::
  118.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
  119.                     const Comb_Probe_Fn& r_comb_probe_fn)
  120.     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
  121.     { comb_probe_fn_base::notify_resized(size); }
  122.  
  123.     PB_DS_CLASS_T_DEC
  124.     PB_DS_CLASS_C_DEC::
  125.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
  126.                     const Comb_Probe_Fn& r_comb_probe_fn,
  127.                     const Probe_Fn& r_probe_fn)
  128.     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
  129.     { comb_probe_fn_base::notify_resized(size); }
  130.  
  131.     PB_DS_CLASS_T_DEC
  132.     void
  133.     PB_DS_CLASS_C_DEC::
  134.     swap(PB_DS_CLASS_C_DEC& other)
  135.     {
  136.       comb_probe_fn_base::swap(other);
  137.       std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
  138.     }
  139.  
  140.     PB_DS_CLASS_T_DEC
  141.     void
  142.     PB_DS_CLASS_C_DEC::
  143.     notify_resized(size_type size)
  144.     { comb_probe_fn_base::notify_resized(size); }
  145.  
  146.     PB_DS_CLASS_T_DEC
  147.     inline typename PB_DS_CLASS_C_DEC::size_type
  148.     PB_DS_CLASS_C_DEC::
  149.     operator()(key_const_reference r_key) const
  150.     { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
  151.  
  152.     PB_DS_CLASS_T_DEC
  153.     inline typename PB_DS_CLASS_C_DEC::size_type
  154.     PB_DS_CLASS_C_DEC::
  155.     operator()(key_const_reference, size_type hash, size_type i) const
  156.     {
  157.       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
  158.     }
  159.  
  160. #undef PB_DS_CLASS_T_DEC
  161. #undef PB_DS_CLASS_C_DEC
  162.  
  163. #define PB_DS_CLASS_T_DEC \
  164.     template<typename Key, typename Hash_Fn, typename _Alloc, \
  165.              typename Comb_Probe_Fn, typename Probe_Fn>
  166.  
  167. #define PB_DS_CLASS_C_DEC \
  168.     ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true>
  169.  
  170.     /**
  171.      * Specialization 2- The client supplies a probe function and a ranged
  172.      *    probe function, and requests that hash values not be stored.
  173.      **/
  174.     template<typename Key, typename Hash_Fn, typename _Alloc,
  175.              typename Comb_Probe_Fn, typename Probe_Fn>
  176.     class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn,
  177.                           Probe_Fn, true>
  178.     : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
  179.     {
  180.     protected:
  181.       typedef typename _Alloc::size_type size_type;
  182.       typedef std::pair<size_type, size_type> comp_hash;
  183.       typedef Comb_Probe_Fn comb_probe_fn_base;
  184.       typedef Hash_Fn hash_fn_base;
  185.       typedef Probe_Fn probe_fn_base;
  186.       typedef typename _Alloc::template rebind<Key>::other key_allocator;
  187.       typedef typename key_allocator::const_reference key_const_reference;
  188.  
  189.       ranged_probe_fn(size_type);
  190.  
  191.       ranged_probe_fn(size_type, const Hash_Fn&);
  192.  
  193.       ranged_probe_fn(size_type, const Hash_Fn&,
  194.                       const Comb_Probe_Fn&);
  195.  
  196.       ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
  197.                       const Probe_Fn&);
  198.  
  199.       void
  200.       swap(PB_DS_CLASS_C_DEC&);
  201.  
  202.       void
  203.       notify_resized(size_type);
  204.  
  205.       inline comp_hash
  206.       operator()(key_const_reference) const;
  207.  
  208.       inline size_type
  209.       operator()(key_const_reference, size_type, size_type) const;
  210.  
  211.       inline size_type
  212.       operator()(key_const_reference, size_type) const;
  213.     };
  214.  
  215.     PB_DS_CLASS_T_DEC
  216.     PB_DS_CLASS_C_DEC::
  217.     ranged_probe_fn(size_type size)
  218.     { Comb_Probe_Fn::notify_resized(size); }
  219.  
  220.     PB_DS_CLASS_T_DEC
  221.     PB_DS_CLASS_C_DEC::
  222.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
  223.     : Hash_Fn(r_hash_fn)
  224.     { Comb_Probe_Fn::notify_resized(size); }
  225.  
  226.     PB_DS_CLASS_T_DEC
  227.     PB_DS_CLASS_C_DEC::
  228.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
  229.                     const Comb_Probe_Fn& r_comb_probe_fn)
  230.     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
  231.     { comb_probe_fn_base::notify_resized(size); }
  232.  
  233.     PB_DS_CLASS_T_DEC
  234.     PB_DS_CLASS_C_DEC::
  235.     ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
  236.                     const Comb_Probe_Fn& r_comb_probe_fn,
  237.                     const Probe_Fn& r_probe_fn)
  238.     : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
  239.     { comb_probe_fn_base::notify_resized(size); }
  240.  
  241.     PB_DS_CLASS_T_DEC
  242.     void
  243.     PB_DS_CLASS_C_DEC::
  244.     swap(PB_DS_CLASS_C_DEC& other)
  245.     {
  246.       comb_probe_fn_base::swap(other);
  247.       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
  248.     }
  249.  
  250.     PB_DS_CLASS_T_DEC
  251.     void
  252.     PB_DS_CLASS_C_DEC::
  253.     notify_resized(size_type size)
  254.     { comb_probe_fn_base::notify_resized(size); }
  255.  
  256.     PB_DS_CLASS_T_DEC
  257.     inline typename PB_DS_CLASS_C_DEC::comp_hash
  258.     PB_DS_CLASS_C_DEC::
  259.     operator()(key_const_reference r_key) const
  260.     {
  261.       const size_type hash = hash_fn_base::operator()(r_key);
  262.       return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
  263.     }
  264.  
  265.     PB_DS_CLASS_T_DEC
  266.     inline typename PB_DS_CLASS_C_DEC::size_type
  267.     PB_DS_CLASS_C_DEC::
  268.     operator()(key_const_reference, size_type hash, size_type i) const
  269.     {
  270.       return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
  271.     }
  272.  
  273.     PB_DS_CLASS_T_DEC
  274.     inline typename PB_DS_CLASS_C_DEC::size_type
  275.     PB_DS_CLASS_C_DEC::
  276.     operator()
  277. #ifdef _GLIBCXX_DEBUG
  278.       (key_const_reference r_key, size_type hash) const
  279. #else
  280.       (key_const_reference /*r_key*/, size_type hash) const
  281. #endif
  282.     {
  283.       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
  284.       return hash;
  285.     }
  286.  
  287. #undef PB_DS_CLASS_T_DEC
  288. #undef PB_DS_CLASS_C_DEC
  289.  
  290.     /**
  291.      * Specialization 3 and 4
  292.      * The client does not supply a hash function or probe function,
  293.      * and requests that hash values not be stored.
  294.      **/
  295.     template<typename Key, typename _Alloc, typename Comb_Probe_Fn>
  296.     class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn,
  297.                           null_type, false>
  298.     : public Comb_Probe_Fn
  299.     {
  300.     protected:
  301.       typedef typename _Alloc::size_type size_type;
  302.       typedef Comb_Probe_Fn comb_probe_fn_base;
  303.       typedef typename _Alloc::template rebind<Key>::other key_allocator;
  304.       typedef typename key_allocator::const_reference key_const_reference;
  305.  
  306.       ranged_probe_fn(size_type size)
  307.       { Comb_Probe_Fn::notify_resized(size); }
  308.  
  309.       ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
  310.       : Comb_Probe_Fn(r_comb_probe_fn)
  311.       { }
  312.  
  313.       ranged_probe_fn(size_type, const null_type&,
  314.                       const Comb_Probe_Fn& r_comb_probe_fn,
  315.                       const null_type&)
  316.       : Comb_Probe_Fn(r_comb_probe_fn)
  317.       { }
  318.  
  319.       void
  320.       swap(ranged_probe_fn& other)
  321.       { comb_probe_fn_base::swap(other); }
  322.     };
  323.   } // namespace detail
  324. } // namespace __gnu_pbds
  325.  
  326. #endif
  327.  
  328.