Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Hashing set implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-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
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 3, 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. // 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. /*
  26.  * Copyright (c) 1996
  27.  * Silicon Graphics Computer Systems, Inc.
  28.  *
  29.  * Permission to use, copy, modify, distribute and sell this software
  30.  * and its documentation for any purpose is hereby granted without fee,
  31.  * provided that the above copyright notice appear in all copies and
  32.  * that both that copyright notice and this permission notice appear
  33.  * in supporting documentation.  Silicon Graphics makes no
  34.  * representations about the suitability of this software for any
  35.  * purpose.  It is provided "as is" without express or implied warranty.
  36.  *
  37.  *
  38.  * Copyright (c) 1994
  39.  * Hewlett-Packard Company
  40.  *
  41.  * Permission to use, copy, modify, distribute and sell this software
  42.  * and its documentation for any purpose is hereby granted without fee,
  43.  * provided that the above copyright notice appear in all copies and
  44.  * that both that copyright notice and this permission notice appear
  45.  * in supporting documentation.  Hewlett-Packard Company makes no
  46.  * representations about the suitability of this software for any
  47.  * purpose.  It is provided "as is" without express or implied warranty.
  48.  *
  49.  */
  50.  
  51. /** @file backward/hash_set
  52.  *  This file is a GNU extension to the Standard C++ Library (possibly
  53.  *  containing extensions from the HP/SGI STL subset).
  54.  */
  55.  
  56. #ifndef _BACKWARD_HASH_SET
  57. #define _BACKWARD_HASH_SET 1
  58.  
  59. #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
  60. #include "backward_warning.h"
  61. #endif
  62.  
  63. #include <bits/c++config.h>
  64. #include <backward/hashtable.h>
  65. #include <bits/concept_check.h>
  66.  
  67. namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  68. {
  69. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  70.  
  71.   using std::equal_to;
  72.   using std::allocator;
  73.   using std::pair;
  74.   using std::_Identity;
  75.  
  76.   /**
  77.    *  This is an SGI extension.
  78.    *  @ingroup SGIextensions
  79.    *  @doctodo
  80.    */
  81.   template<class _Value, class _HashFcn  = hash<_Value>,
  82.            class _EqualKey = equal_to<_Value>,
  83.            class _Alloc = allocator<_Value> >
  84.     class hash_set
  85.     {
  86.       // concept requirements
  87.       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  88.       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  89.       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  90.  
  91.     private:
  92.       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  93.                         _EqualKey, _Alloc> _Ht;
  94.       _Ht _M_ht;
  95.  
  96.     public:
  97.       typedef typename _Ht::key_type key_type;
  98.       typedef typename _Ht::value_type value_type;
  99.       typedef typename _Ht::hasher hasher;
  100.       typedef typename _Ht::key_equal key_equal;
  101.      
  102.       typedef typename _Ht::size_type size_type;
  103.       typedef typename _Ht::difference_type difference_type;
  104.       typedef typename _Alloc::pointer pointer;
  105.       typedef typename _Alloc::const_pointer const_pointer;
  106.       typedef typename _Alloc::reference reference;
  107.       typedef typename _Alloc::const_reference const_reference;
  108.      
  109.       typedef typename _Ht::const_iterator iterator;
  110.       typedef typename _Ht::const_iterator const_iterator;
  111.      
  112.       typedef typename _Ht::allocator_type allocator_type;
  113.      
  114.       hasher
  115.       hash_funct() const
  116.       { return _M_ht.hash_funct(); }
  117.  
  118.       key_equal
  119.       key_eq() const
  120.       { return _M_ht.key_eq(); }
  121.  
  122.       allocator_type
  123.       get_allocator() const
  124.       { return _M_ht.get_allocator(); }
  125.  
  126.       hash_set()
  127.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  128.  
  129.       explicit
  130.       hash_set(size_type __n)
  131.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  132.  
  133.       hash_set(size_type __n, const hasher& __hf)
  134.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  135.  
  136.       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  137.                const allocator_type& __a = allocator_type())
  138.       : _M_ht(__n, __hf, __eql, __a) {}
  139.  
  140.       template<class _InputIterator>
  141.         hash_set(_InputIterator __f, _InputIterator __l)
  142.         : _M_ht(100, hasher(), key_equal(), allocator_type())
  143.         { _M_ht.insert_unique(__f, __l); }
  144.  
  145.       template<class _InputIterator>
  146.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
  147.         : _M_ht(__n, hasher(), key_equal(), allocator_type())
  148.         { _M_ht.insert_unique(__f, __l); }
  149.  
  150.       template<class _InputIterator>
  151.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  152.                  const hasher& __hf)
  153.         : _M_ht(__n, __hf, key_equal(), allocator_type())
  154.         { _M_ht.insert_unique(__f, __l); }
  155.  
  156.       template<class _InputIterator>
  157.         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
  158.                  const hasher& __hf, const key_equal& __eql,
  159.                  const allocator_type& __a = allocator_type())
  160.         : _M_ht(__n, __hf, __eql, __a)
  161.         { _M_ht.insert_unique(__f, __l); }
  162.  
  163.       size_type
  164.       size() const
  165.       { return _M_ht.size(); }
  166.  
  167.       size_type
  168.       max_size() const
  169.       { return _M_ht.max_size(); }
  170.      
  171.       bool
  172.       empty() const
  173.       { return _M_ht.empty(); }
  174.      
  175.       void
  176.       swap(hash_set& __hs)
  177.       { _M_ht.swap(__hs._M_ht); }
  178.  
  179.       template<class _Val, class _HF, class _EqK, class _Al>
  180.         friend bool
  181.         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
  182.                    const hash_set<_Val, _HF, _EqK, _Al>&);
  183.  
  184.       iterator
  185.       begin() const
  186.       { return _M_ht.begin(); }
  187.      
  188.       iterator
  189.       end() const
  190.       { return _M_ht.end(); }
  191.  
  192.       pair<iterator, bool>
  193.       insert(const value_type& __obj)
  194.       {
  195.         pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
  196.         return pair<iterator,bool>(__p.first, __p.second);
  197.       }
  198.  
  199.       template<class _InputIterator>
  200.         void
  201.         insert(_InputIterator __f, _InputIterator __l)
  202.         { _M_ht.insert_unique(__f, __l); }
  203.  
  204.       pair<iterator, bool>
  205.       insert_noresize(const value_type& __obj)
  206.       {
  207.         pair<typename _Ht::iterator, bool> __p
  208.           = _M_ht.insert_unique_noresize(__obj);
  209.         return pair<iterator, bool>(__p.first, __p.second);
  210.       }
  211.  
  212.       iterator
  213.       find(const key_type& __key) const
  214.       { return _M_ht.find(__key); }
  215.  
  216.       size_type
  217.       count(const key_type& __key) const
  218.       { return _M_ht.count(__key); }
  219.  
  220.       pair<iterator, iterator>
  221.       equal_range(const key_type& __key) const
  222.       { return _M_ht.equal_range(__key); }
  223.  
  224.       size_type
  225.       erase(const key_type& __key)
  226.       {return _M_ht.erase(__key); }
  227.      
  228.       void
  229.       erase(iterator __it)
  230.       { _M_ht.erase(__it); }
  231.      
  232.       void
  233.       erase(iterator __f, iterator __l)
  234.       { _M_ht.erase(__f, __l); }
  235.      
  236.       void
  237.       clear()
  238.       { _M_ht.clear(); }
  239.  
  240.       void
  241.       resize(size_type __hint)
  242.       { _M_ht.resize(__hint); }
  243.      
  244.       size_type
  245.       bucket_count() const
  246.       { return _M_ht.bucket_count(); }
  247.      
  248.       size_type
  249.       max_bucket_count() const
  250.       { return _M_ht.max_bucket_count(); }
  251.      
  252.       size_type
  253.       elems_in_bucket(size_type __n) const
  254.       { return _M_ht.elems_in_bucket(__n); }
  255.     };
  256.  
  257.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  258.     inline bool
  259.     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
  260.                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
  261.     { return __hs1._M_ht == __hs2._M_ht; }
  262.  
  263.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  264.     inline bool
  265.     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
  266.                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
  267.     { return !(__hs1 == __hs2); }
  268.  
  269.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  270.     inline void
  271.     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
  272.          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
  273.     { __hs1.swap(__hs2); }
  274.  
  275.  
  276.   /**
  277.    *  This is an SGI extension.
  278.    *  @ingroup SGIextensions
  279.    *  @doctodo
  280.    */
  281.   template<class _Value,
  282.            class _HashFcn = hash<_Value>,
  283.            class _EqualKey = equal_to<_Value>,
  284.            class _Alloc = allocator<_Value> >
  285.     class hash_multiset
  286.     {
  287.       // concept requirements
  288.       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  289.       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  290.       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  291.  
  292.     private:
  293.       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  294.                         _EqualKey, _Alloc> _Ht;
  295.       _Ht _M_ht;
  296.  
  297.     public:
  298.       typedef typename _Ht::key_type key_type;
  299.       typedef typename _Ht::value_type value_type;
  300.       typedef typename _Ht::hasher hasher;
  301.       typedef typename _Ht::key_equal key_equal;
  302.      
  303.       typedef typename _Ht::size_type size_type;
  304.       typedef typename _Ht::difference_type difference_type;
  305.       typedef typename _Alloc::pointer pointer;
  306.       typedef typename _Alloc::const_pointer const_pointer;
  307.       typedef typename _Alloc::reference reference;
  308.       typedef typename _Alloc::const_reference const_reference;
  309.  
  310.       typedef typename _Ht::const_iterator iterator;
  311.       typedef typename _Ht::const_iterator const_iterator;
  312.      
  313.       typedef typename _Ht::allocator_type allocator_type;
  314.      
  315.       hasher
  316.       hash_funct() const
  317.       { return _M_ht.hash_funct(); }
  318.      
  319.       key_equal
  320.       key_eq() const
  321.       { return _M_ht.key_eq(); }
  322.      
  323.       allocator_type
  324.       get_allocator() const
  325.       { return _M_ht.get_allocator(); }
  326.  
  327.       hash_multiset()
  328.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  329.  
  330.       explicit
  331.       hash_multiset(size_type __n)
  332.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  333.  
  334.       hash_multiset(size_type __n, const hasher& __hf)
  335.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  336.      
  337.       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
  338.                     const allocator_type& __a = allocator_type())
  339.       : _M_ht(__n, __hf, __eql, __a) {}
  340.  
  341.       template<class _InputIterator>
  342.         hash_multiset(_InputIterator __f, _InputIterator __l)
  343.         : _M_ht(100, hasher(), key_equal(), allocator_type())
  344.         { _M_ht.insert_equal(__f, __l); }
  345.  
  346.       template<class _InputIterator>
  347.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
  348.         : _M_ht(__n, hasher(), key_equal(), allocator_type())
  349.         { _M_ht.insert_equal(__f, __l); }
  350.  
  351.       template<class _InputIterator>
  352.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  353.                       const hasher& __hf)
  354.         : _M_ht(__n, __hf, key_equal(), allocator_type())
  355.         { _M_ht.insert_equal(__f, __l); }
  356.  
  357.       template<class _InputIterator>
  358.         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
  359.                       const hasher& __hf, const key_equal& __eql,
  360.                       const allocator_type& __a = allocator_type())
  361.         : _M_ht(__n, __hf, __eql, __a)
  362.         { _M_ht.insert_equal(__f, __l); }
  363.  
  364.       size_type
  365.       size() const
  366.       { return _M_ht.size(); }
  367.  
  368.       size_type
  369.       max_size() const
  370.       { return _M_ht.max_size(); }
  371.  
  372.       bool
  373.       empty() const
  374.       { return _M_ht.empty(); }
  375.  
  376.       void
  377.       swap(hash_multiset& hs)
  378.       { _M_ht.swap(hs._M_ht); }
  379.  
  380.       template<class _Val, class _HF, class _EqK, class _Al>
  381.         friend bool
  382.         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
  383.                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
  384.  
  385.       iterator
  386.       begin() const
  387.       { return _M_ht.begin(); }
  388.      
  389.       iterator
  390.       end() const
  391.       { return _M_ht.end(); }
  392.  
  393.       iterator
  394.       insert(const value_type& __obj)
  395.       { return _M_ht.insert_equal(__obj); }
  396.  
  397.       template<class _InputIterator>
  398.         void
  399.         insert(_InputIterator __f, _InputIterator __l)
  400.         { _M_ht.insert_equal(__f,__l); }
  401.  
  402.       iterator
  403.       insert_noresize(const value_type& __obj)
  404.       { return _M_ht.insert_equal_noresize(__obj); }
  405.  
  406.       iterator
  407.       find(const key_type& __key) const
  408.       { return _M_ht.find(__key); }
  409.  
  410.       size_type
  411.       count(const key_type& __key) const
  412.       { return _M_ht.count(__key); }
  413.  
  414.       pair<iterator, iterator>
  415.       equal_range(const key_type& __key) const
  416.       { return _M_ht.equal_range(__key); }
  417.  
  418.       size_type
  419.       erase(const key_type& __key)
  420.       { return _M_ht.erase(__key); }
  421.  
  422.       void
  423.       erase(iterator __it)
  424.       { _M_ht.erase(__it); }
  425.  
  426.       void
  427.       erase(iterator __f, iterator __l)
  428.       { _M_ht.erase(__f, __l); }
  429.  
  430.       void
  431.       clear()
  432.       { _M_ht.clear(); }
  433.  
  434.       void
  435.       resize(size_type __hint)
  436.       { _M_ht.resize(__hint); }
  437.  
  438.       size_type
  439.       bucket_count() const
  440.       { return _M_ht.bucket_count(); }
  441.  
  442.       size_type
  443.       max_bucket_count() const
  444.       { return _M_ht.max_bucket_count(); }
  445.  
  446.       size_type
  447.       elems_in_bucket(size_type __n) const
  448.       { return _M_ht.elems_in_bucket(__n); }
  449.     };
  450.  
  451.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  452.     inline bool
  453.     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
  454.                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
  455.     { return __hs1._M_ht == __hs2._M_ht; }
  456.  
  457.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  458.     inline bool
  459.     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
  460.                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
  461.     { return !(__hs1 == __hs2); }
  462.  
  463.   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
  464.     inline void
  465.     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
  466.          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
  467.     { __hs1.swap(__hs2); }
  468.  
  469. _GLIBCXX_END_NAMESPACE_VERSION
  470. } // namespace
  471.  
  472. namespace std _GLIBCXX_VISIBILITY(default)
  473. {
  474. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  475.  
  476.   // Specialization of insert_iterator so that it will work for hash_set
  477.   // and hash_multiset.
  478.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  479.     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
  480.                                               _EqualKey, _Alloc> >
  481.     {
  482.     protected:
  483.       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
  484.         _Container;
  485.       _Container* container;
  486.  
  487.     public:
  488.       typedef _Container          container_type;
  489.       typedef output_iterator_tag iterator_category;
  490.       typedef void                value_type;
  491.       typedef void                difference_type;
  492.       typedef void                pointer;
  493.       typedef void                reference;
  494.  
  495.       insert_iterator(_Container& __x)
  496.       : container(&__x) {}
  497.      
  498.       insert_iterator(_Container& __x, typename _Container::iterator)
  499.       : container(&__x) {}
  500.  
  501.       insert_iterator<_Container>&
  502.       operator=(const typename _Container::value_type& __value)
  503.       {
  504.         container->insert(__value);
  505.         return *this;
  506.       }
  507.  
  508.       insert_iterator<_Container>&
  509.       operator*()
  510.       { return *this; }
  511.      
  512.       insert_iterator<_Container>&
  513.       operator++()
  514.       { return *this; }
  515.      
  516.       insert_iterator<_Container>&
  517.       operator++(int)
  518.       { return *this; }
  519.     };
  520.  
  521.   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  522.     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
  523.                                                    _EqualKey, _Alloc> >
  524.     {
  525.     protected:
  526.       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
  527.         _Container;
  528.       _Container* container;
  529.       typename _Container::iterator iter;
  530.  
  531.     public:
  532.       typedef _Container          container_type;
  533.       typedef output_iterator_tag iterator_category;
  534.       typedef void                value_type;
  535.       typedef void                difference_type;
  536.       typedef void                pointer;
  537.       typedef void                reference;
  538.      
  539.       insert_iterator(_Container& __x)
  540.       : container(&__x) {}
  541.      
  542.       insert_iterator(_Container& __x, typename _Container::iterator)
  543.       : container(&__x) {}
  544.  
  545.       insert_iterator<_Container>&
  546.       operator=(const typename _Container::value_type& __value)
  547.       {
  548.         container->insert(__value);
  549.         return *this;
  550.       }
  551.  
  552.       insert_iterator<_Container>&
  553.       operator*()
  554.       { return *this; }
  555.  
  556.       insert_iterator<_Container>&
  557.       operator++()
  558.       { return *this; }
  559.  
  560.       insert_iterator<_Container>&
  561.       operator++(int) { return *this; }
  562.     };
  563.  
  564. _GLIBCXX_END_NAMESPACE_VERSION
  565. } // namespace
  566.  
  567. #endif
  568.