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_hash_fn.hpp
  38.  * Contains a unified ranged hash functor, allowing the hash tables
  39.  * to deal with a single class for ranged hashing.
  40.  */
  41.  
  42. #ifndef PB_DS_RANGED_HASH_FN_HPP
  43. #define PB_DS_RANGED_HASH_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_Hash_Fn, bool Store_Hash>
  55.     class ranged_hash_fn;
  56.  
  57. #define PB_DS_CLASS_T_DEC \
  58.     template<typename Key, typename Hash_Fn, typename _Alloc, \
  59.              typename Comb_Hash_Fn>
  60.  
  61. #define PB_DS_CLASS_C_DEC \
  62.     ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, false>
  63.  
  64.     /**
  65.      * Specialization 1
  66.      * The client supplies a hash function and a ranged hash function,
  67.      * and requests that hash values not be stored.
  68.      **/
  69.     template<typename Key, typename Hash_Fn, typename _Alloc,
  70.              typename Comb_Hash_Fn>
  71.     class ranged_hash_fn< Key, Hash_Fn, _Alloc, Comb_Hash_Fn, false>
  72.     : public Hash_Fn, public Comb_Hash_Fn
  73.     {
  74.     protected:
  75.       typedef typename _Alloc::size_type size_type;
  76.       typedef Hash_Fn hash_fn_base;
  77.       typedef Comb_Hash_Fn comb_hash_fn_base;
  78.       typedef typename _Alloc::template rebind< Key>::other key_allocator;
  79.       typedef typename key_allocator::const_reference key_const_reference;
  80.  
  81.       ranged_hash_fn(size_type);
  82.  
  83.       ranged_hash_fn(size_type, const Hash_Fn&);
  84.  
  85.       ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);
  86.  
  87.       void
  88.       swap(PB_DS_CLASS_C_DEC&);
  89.  
  90.       void
  91.       notify_resized(size_type);
  92.  
  93.       inline size_type
  94.       operator()(key_const_reference) const;
  95.     };
  96.  
  97.     PB_DS_CLASS_T_DEC
  98.     PB_DS_CLASS_C_DEC::
  99.     ranged_hash_fn(size_type size)
  100.     { Comb_Hash_Fn::notify_resized(size); }
  101.  
  102.     PB_DS_CLASS_T_DEC
  103.     PB_DS_CLASS_C_DEC::
  104.     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn)
  105.     : Hash_Fn(r_hash_fn)
  106.     { Comb_Hash_Fn::notify_resized(size); }
  107.  
  108.     PB_DS_CLASS_T_DEC
  109.     PB_DS_CLASS_C_DEC::
  110.     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
  111.                    const Comb_Hash_Fn& r_comb_hash_fn)
  112.     : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
  113.     { comb_hash_fn_base::notify_resized(size); }
  114.  
  115.     PB_DS_CLASS_T_DEC
  116.     void
  117.     PB_DS_CLASS_C_DEC::
  118.     swap(PB_DS_CLASS_C_DEC& other)
  119.     {
  120.       comb_hash_fn_base::swap(other);
  121.       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
  122.     }
  123.  
  124.     PB_DS_CLASS_T_DEC
  125.     void
  126.     PB_DS_CLASS_C_DEC::
  127.     notify_resized(size_type size)
  128.     { comb_hash_fn_base::notify_resized(size); }
  129.  
  130.     PB_DS_CLASS_T_DEC
  131.     inline typename PB_DS_CLASS_C_DEC::size_type
  132.     PB_DS_CLASS_C_DEC::
  133.     operator()(key_const_reference r_key) const
  134.     { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));}
  135.  
  136. #undef PB_DS_CLASS_T_DEC
  137. #undef PB_DS_CLASS_C_DEC
  138.  
  139. #define PB_DS_CLASS_T_DEC \
  140.     template<typename Key, typename Hash_Fn, typename _Alloc, \
  141.              typename Comb_Hash_Fn>
  142.  
  143. #define PB_DS_CLASS_C_DEC \
  144.     ranged_hash_fn<Key,Hash_Fn, _Alloc, Comb_Hash_Fn, true>
  145.  
  146.     /**
  147.      * Specialization 2
  148.      * The client supplies a hash function and a ranged hash function,
  149.      * and requests that hash values be stored.
  150.      **/
  151.     template<typename Key, typename Hash_Fn, typename _Alloc,
  152.              typename Comb_Hash_Fn>
  153.     class ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, true>
  154.     : public Hash_Fn, public Comb_Hash_Fn
  155.     {
  156.     protected:
  157.       typedef typename _Alloc::size_type size_type;
  158.       typedef std::pair<size_type, size_type> comp_hash;
  159.       typedef Hash_Fn hash_fn_base;
  160.       typedef Comb_Hash_Fn comb_hash_fn_base;
  161.       typedef typename _Alloc::template rebind<Key>::other key_allocator;
  162.       typedef typename key_allocator::const_reference key_const_reference;
  163.  
  164.       ranged_hash_fn(size_type);
  165.  
  166.       ranged_hash_fn(size_type, const Hash_Fn&);
  167.  
  168.       ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);
  169.  
  170.       void
  171.       swap(PB_DS_CLASS_C_DEC&);
  172.  
  173.       void
  174.       notify_resized(size_type);
  175.  
  176.       inline comp_hash
  177.       operator()(key_const_reference) const;
  178.  
  179.       inline comp_hash
  180.       operator()(key_const_reference, size_type) const;
  181.     };
  182.  
  183.     PB_DS_CLASS_T_DEC
  184.     PB_DS_CLASS_C_DEC::
  185.     ranged_hash_fn(size_type size)
  186.     { Comb_Hash_Fn::notify_resized(size); }
  187.  
  188.     PB_DS_CLASS_T_DEC
  189.     PB_DS_CLASS_C_DEC::
  190.     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
  191.       Hash_Fn(r_hash_fn)
  192.     { Comb_Hash_Fn::notify_resized(size); }
  193.  
  194.     PB_DS_CLASS_T_DEC
  195.     PB_DS_CLASS_C_DEC::
  196.     ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
  197.                    const Comb_Hash_Fn& r_comb_hash_fn)
  198.     : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
  199.     { comb_hash_fn_base::notify_resized(size); }
  200.  
  201.     PB_DS_CLASS_T_DEC
  202.     void
  203.     PB_DS_CLASS_C_DEC::
  204.     swap(PB_DS_CLASS_C_DEC& other)
  205.     {
  206.       comb_hash_fn_base::swap(other);
  207.       std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
  208.     }
  209.  
  210.     PB_DS_CLASS_T_DEC
  211.     void
  212.     PB_DS_CLASS_C_DEC::
  213.     notify_resized(size_type size)
  214.     { comb_hash_fn_base::notify_resized(size); }
  215.  
  216.     PB_DS_CLASS_T_DEC
  217.     inline typename PB_DS_CLASS_C_DEC::comp_hash
  218.     PB_DS_CLASS_C_DEC::
  219.     operator()(key_const_reference r_key) const
  220.     {
  221.       const size_type hash = hash_fn_base::operator()(r_key);
  222.       return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
  223.     }
  224.  
  225.     PB_DS_CLASS_T_DEC
  226.     inline typename PB_DS_CLASS_C_DEC::comp_hash
  227.     PB_DS_CLASS_C_DEC::
  228.     operator()
  229. #ifdef _GLIBCXX_DEBUG
  230.       (key_const_reference r_key, size_type hash) const
  231. #else
  232.       (key_const_reference /*r_key*/, size_type hash) const
  233. #endif
  234.     {
  235.       _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
  236.       return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
  237.     }
  238.  
  239. #undef PB_DS_CLASS_T_DEC
  240. #undef PB_DS_CLASS_C_DEC
  241.  
  242. #define PB_DS_CLASS_T_DEC \
  243.     template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
  244.  
  245. #define PB_DS_CLASS_C_DEC \
  246.     ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, false>
  247.  
  248.     /**
  249.      * Specialization 3
  250.      * The client does not supply a hash function (by specifying
  251.      * null_type as the Hash_Fn parameter), and requests that hash
  252.      * values not be stored.
  253.      **/
  254.     template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
  255.     class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, false>
  256.     : public Comb_Hash_Fn
  257.     {
  258.     protected:
  259.       typedef typename _Alloc::size_type size_type;
  260.       typedef Comb_Hash_Fn comb_hash_fn_base;
  261.  
  262.       ranged_hash_fn(size_type);
  263.  
  264.       ranged_hash_fn(size_type, const Comb_Hash_Fn&);
  265.  
  266.       ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
  267.  
  268.       void
  269.       swap(PB_DS_CLASS_C_DEC&);
  270.     };
  271.  
  272.     PB_DS_CLASS_T_DEC
  273.     PB_DS_CLASS_C_DEC::
  274.     ranged_hash_fn(size_type size)
  275.     { Comb_Hash_Fn::notify_resized(size); }
  276.  
  277.     PB_DS_CLASS_T_DEC
  278.     PB_DS_CLASS_C_DEC::
  279.     ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
  280.       Comb_Hash_Fn(r_comb_hash_fn)
  281.     { }
  282.  
  283.     PB_DS_CLASS_T_DEC
  284.     PB_DS_CLASS_C_DEC::
  285.     ranged_hash_fn(size_type size, const null_type& r_null_type,
  286.                    const Comb_Hash_Fn& r_comb_hash_fn)
  287.     : Comb_Hash_Fn(r_comb_hash_fn)
  288.     { }
  289.  
  290.     PB_DS_CLASS_T_DEC
  291.     void
  292.     PB_DS_CLASS_C_DEC::
  293.     swap(PB_DS_CLASS_C_DEC& other)
  294.     { comb_hash_fn_base::swap(other); }
  295.  
  296. #undef PB_DS_CLASS_T_DEC
  297. #undef PB_DS_CLASS_C_DEC
  298.  
  299. #define PB_DS_CLASS_T_DEC \
  300.     template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
  301.  
  302. #define PB_DS_CLASS_C_DEC \
  303.     ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, true>
  304.  
  305.     /**
  306.      * Specialization 4
  307.      * The client does not supply a hash function (by specifying
  308.      * null_type as the Hash_Fn parameter), and requests that hash
  309.      * values be stored.
  310.      **/
  311.     template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
  312.     class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, true>
  313.     : public Comb_Hash_Fn
  314.     {
  315.     protected:
  316.       typedef typename _Alloc::size_type size_type;
  317.       typedef Comb_Hash_Fn comb_hash_fn_base;
  318.  
  319.       ranged_hash_fn(size_type);
  320.  
  321.       ranged_hash_fn(size_type, const Comb_Hash_Fn&);
  322.  
  323.       ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
  324.  
  325.       void
  326.       swap(PB_DS_CLASS_C_DEC&);
  327.     };
  328.  
  329.     PB_DS_CLASS_T_DEC
  330.     PB_DS_CLASS_C_DEC::
  331.     ranged_hash_fn(size_type size)
  332.     { Comb_Hash_Fn::notify_resized(size); }
  333.  
  334.     PB_DS_CLASS_T_DEC
  335.     PB_DS_CLASS_C_DEC::
  336.     ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn)
  337.     : Comb_Hash_Fn(r_comb_hash_fn)
  338.     { }
  339.  
  340.     PB_DS_CLASS_T_DEC
  341.     PB_DS_CLASS_C_DEC::
  342.     ranged_hash_fn(size_type size, const null_type& r_null_type,
  343.                    const Comb_Hash_Fn& r_comb_hash_fn)
  344.     : Comb_Hash_Fn(r_comb_hash_fn)
  345.     { }
  346.  
  347.     PB_DS_CLASS_T_DEC
  348.     void
  349.     PB_DS_CLASS_C_DEC::
  350.     swap(PB_DS_CLASS_C_DEC& other)
  351.     { comb_hash_fn_base::swap(other); }
  352.  
  353. #undef PB_DS_CLASS_T_DEC
  354. #undef PB_DS_CLASS_C_DEC
  355.  
  356.   } // namespace detail
  357. } // namespace __gnu_pbds
  358.  
  359. #endif
  360.