Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Hashing map 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_map
  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_MAP
  57. #define _BACKWARD_HASH_MAP 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::_Select1st;
  75.  
  76.   /**
  77.    *  This is an SGI extension.
  78.    *  @ingroup SGIextensions
  79.    *  @doctodo
  80.    */
  81.   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
  82.            class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
  83.     class hash_map
  84.     {
  85.     private:
  86.       typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
  87.                         _Select1st<pair<const _Key, _Tp> >,
  88.                         _EqualKey, _Alloc> _Ht;
  89.  
  90.       _Ht _M_ht;
  91.  
  92.     public:
  93.       typedef typename _Ht::key_type key_type;
  94.       typedef _Tp data_type;
  95.       typedef _Tp mapped_type;
  96.       typedef typename _Ht::value_type value_type;
  97.       typedef typename _Ht::hasher hasher;
  98.       typedef typename _Ht::key_equal key_equal;
  99.      
  100.       typedef typename _Ht::size_type size_type;
  101.       typedef typename _Ht::difference_type difference_type;
  102.       typedef typename _Ht::pointer pointer;
  103.       typedef typename _Ht::const_pointer const_pointer;
  104.       typedef typename _Ht::reference reference;
  105.       typedef typename _Ht::const_reference const_reference;
  106.      
  107.       typedef typename _Ht::iterator iterator;
  108.       typedef typename _Ht::const_iterator const_iterator;
  109.      
  110.       typedef typename _Ht::allocator_type allocator_type;
  111.      
  112.       hasher
  113.       hash_funct() const
  114.       { return _M_ht.hash_funct(); }
  115.  
  116.       key_equal
  117.       key_eq() const
  118.       { return _M_ht.key_eq(); }
  119.  
  120.       allocator_type
  121.       get_allocator() const
  122.       { return _M_ht.get_allocator(); }
  123.  
  124.       hash_map()
  125.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  126.  
  127.       explicit
  128.       hash_map(size_type __n)
  129.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  130.  
  131.       hash_map(size_type __n, const hasher& __hf)
  132.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  133.  
  134.       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
  135.                const allocator_type& __a = allocator_type())
  136.       : _M_ht(__n, __hf, __eql, __a) {}
  137.  
  138.       template<class _InputIterator>
  139.         hash_map(_InputIterator __f, _InputIterator __l)
  140.         : _M_ht(100, hasher(), key_equal(), allocator_type())
  141.         { _M_ht.insert_unique(__f, __l); }
  142.  
  143.       template<class _InputIterator>
  144.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
  145.         : _M_ht(__n, hasher(), key_equal(), allocator_type())
  146.         { _M_ht.insert_unique(__f, __l); }
  147.  
  148.       template<class _InputIterator>
  149.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  150.                  const hasher& __hf)
  151.         : _M_ht(__n, __hf, key_equal(), allocator_type())
  152.         { _M_ht.insert_unique(__f, __l); }
  153.  
  154.       template<class _InputIterator>
  155.         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
  156.                  const hasher& __hf, const key_equal& __eql,
  157.                  const allocator_type& __a = allocator_type())
  158.         : _M_ht(__n, __hf, __eql, __a)
  159.         { _M_ht.insert_unique(__f, __l); }
  160.  
  161.       size_type
  162.       size() const
  163.       { return _M_ht.size(); }
  164.      
  165.       size_type
  166.       max_size() const
  167.       { return _M_ht.max_size(); }
  168.      
  169.       bool
  170.       empty() const
  171.       { return _M_ht.empty(); }
  172.  
  173.       void
  174.       swap(hash_map& __hs)
  175.       { _M_ht.swap(__hs._M_ht); }
  176.  
  177.       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
  178.         friend bool
  179.         operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
  180.                     const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
  181.  
  182.       iterator
  183.       begin()
  184.       { return _M_ht.begin(); }
  185.  
  186.       iterator
  187.       end()
  188.       { return _M_ht.end(); }
  189.  
  190.       const_iterator
  191.       begin() const
  192.       { return _M_ht.begin(); }
  193.  
  194.       const_iterator
  195.       end() const
  196.       { return _M_ht.end(); }
  197.  
  198.       pair<iterator, bool>
  199.       insert(const value_type& __obj)
  200.       { return _M_ht.insert_unique(__obj); }
  201.  
  202.       template<class _InputIterator>
  203.         void
  204.         insert(_InputIterator __f, _InputIterator __l)
  205.         { _M_ht.insert_unique(__f, __l); }
  206.  
  207.       pair<iterator, bool>
  208.       insert_noresize(const value_type& __obj)
  209.       { return _M_ht.insert_unique_noresize(__obj); }
  210.  
  211.       iterator
  212.       find(const key_type& __key)
  213.       { return _M_ht.find(__key); }
  214.  
  215.       const_iterator
  216.       find(const key_type& __key) const
  217.       { return _M_ht.find(__key); }
  218.  
  219.       _Tp&
  220.       operator[](const key_type& __key)
  221.       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
  222.  
  223.       size_type
  224.       count(const key_type& __key) const
  225.       { return _M_ht.count(__key); }
  226.  
  227.       pair<iterator, iterator>
  228.       equal_range(const key_type& __key)
  229.       { return _M_ht.equal_range(__key); }
  230.  
  231.       pair<const_iterator, const_iterator>
  232.       equal_range(const key_type& __key) const
  233.       { return _M_ht.equal_range(__key); }
  234.  
  235.       size_type
  236.       erase(const key_type& __key)
  237.       {return _M_ht.erase(__key); }
  238.  
  239.       void
  240.       erase(iterator __it)
  241.       { _M_ht.erase(__it); }
  242.  
  243.       void
  244.       erase(iterator __f, iterator __l)
  245.       { _M_ht.erase(__f, __l); }
  246.  
  247.       void
  248.       clear()
  249.       { _M_ht.clear(); }
  250.  
  251.       void
  252.       resize(size_type __hint)
  253.       { _M_ht.resize(__hint); }
  254.  
  255.       size_type
  256.       bucket_count() const
  257.       { return _M_ht.bucket_count(); }
  258.  
  259.       size_type
  260.       max_bucket_count() const
  261.       { return _M_ht.max_bucket_count(); }
  262.  
  263.       size_type
  264.       elems_in_bucket(size_type __n) const
  265.       { return _M_ht.elems_in_bucket(__n); }
  266.     };
  267.  
  268.   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
  269.     inline bool
  270.     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
  271.                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
  272.     { return __hm1._M_ht == __hm2._M_ht; }
  273.  
  274.   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
  275.     inline bool
  276.     operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
  277.                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
  278.     { return !(__hm1 == __hm2); }
  279.  
  280.   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
  281.     inline void
  282.     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
  283.          hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
  284.     { __hm1.swap(__hm2); }
  285.  
  286.  
  287.   /**
  288.    *  This is an SGI extension.
  289.    *  @ingroup SGIextensions
  290.    *  @doctodo
  291.    */
  292.   template<class _Key, class _Tp,
  293.            class _HashFn = hash<_Key>,
  294.            class _EqualKey = equal_to<_Key>,
  295.            class _Alloc = allocator<_Tp> >
  296.     class hash_multimap
  297.     {
  298.       // concept requirements
  299.       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
  300.       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
  301.       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
  302.       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
  303.        
  304.     private:
  305.       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
  306.                         _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
  307.           _Ht;
  308.  
  309.       _Ht _M_ht;
  310.  
  311.     public:
  312.       typedef typename _Ht::key_type key_type;
  313.       typedef _Tp data_type;
  314.       typedef _Tp mapped_type;
  315.       typedef typename _Ht::value_type value_type;
  316.       typedef typename _Ht::hasher hasher;
  317.       typedef typename _Ht::key_equal key_equal;
  318.      
  319.       typedef typename _Ht::size_type size_type;
  320.       typedef typename _Ht::difference_type difference_type;
  321.       typedef typename _Ht::pointer pointer;
  322.       typedef typename _Ht::const_pointer const_pointer;
  323.       typedef typename _Ht::reference reference;
  324.       typedef typename _Ht::const_reference const_reference;
  325.      
  326.       typedef typename _Ht::iterator iterator;
  327.       typedef typename _Ht::const_iterator const_iterator;
  328.      
  329.       typedef typename _Ht::allocator_type allocator_type;
  330.      
  331.       hasher
  332.       hash_funct() const
  333.       { return _M_ht.hash_funct(); }
  334.  
  335.       key_equal
  336.       key_eq() const
  337.       { return _M_ht.key_eq(); }
  338.  
  339.       allocator_type
  340.       get_allocator() const
  341.       { return _M_ht.get_allocator(); }
  342.  
  343.       hash_multimap()
  344.       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  345.  
  346.       explicit
  347.       hash_multimap(size_type __n)
  348.       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  349.  
  350.       hash_multimap(size_type __n, const hasher& __hf)
  351.       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  352.  
  353.       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
  354.                     const allocator_type& __a = allocator_type())
  355.       : _M_ht(__n, __hf, __eql, __a) {}
  356.  
  357.       template<class _InputIterator>
  358.         hash_multimap(_InputIterator __f, _InputIterator __l)
  359.         : _M_ht(100, hasher(), key_equal(), allocator_type())
  360.         { _M_ht.insert_equal(__f, __l); }
  361.  
  362.       template<class _InputIterator>
  363.         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
  364.         : _M_ht(__n, hasher(), key_equal(), allocator_type())
  365.         { _M_ht.insert_equal(__f, __l); }
  366.  
  367.       template<class _InputIterator>
  368.         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
  369.                       const hasher& __hf)
  370.         : _M_ht(__n, __hf, key_equal(), allocator_type())
  371.         { _M_ht.insert_equal(__f, __l); }
  372.  
  373.       template<class _InputIterator>
  374.         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
  375.                       const hasher& __hf, const key_equal& __eql,
  376.                       const allocator_type& __a = allocator_type())
  377.         : _M_ht(__n, __hf, __eql, __a)
  378.         { _M_ht.insert_equal(__f, __l); }
  379.  
  380.       size_type
  381.       size() const
  382.       { return _M_ht.size(); }
  383.  
  384.       size_type
  385.       max_size() const
  386.       { return _M_ht.max_size(); }
  387.  
  388.       bool
  389.       empty() const
  390.       { return _M_ht.empty(); }
  391.  
  392.       void
  393.       swap(hash_multimap& __hs)
  394.       { _M_ht.swap(__hs._M_ht); }
  395.  
  396.       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
  397.         friend bool
  398.         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
  399.                    const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
  400.  
  401.       iterator
  402.       begin()
  403.       { return _M_ht.begin(); }
  404.  
  405.       iterator
  406.       end()
  407.       { return _M_ht.end(); }
  408.  
  409.       const_iterator
  410.       begin() const
  411.       { return _M_ht.begin(); }
  412.  
  413.       const_iterator
  414.       end() const
  415.       { return _M_ht.end(); }
  416.  
  417.       iterator
  418.       insert(const value_type& __obj)
  419.       { return _M_ht.insert_equal(__obj); }
  420.  
  421.       template<class _InputIterator>
  422.         void
  423.         insert(_InputIterator __f, _InputIterator __l)
  424.         { _M_ht.insert_equal(__f,__l); }
  425.  
  426.       iterator
  427.       insert_noresize(const value_type& __obj)
  428.       { return _M_ht.insert_equal_noresize(__obj); }
  429.  
  430.       iterator
  431.       find(const key_type& __key)
  432.       { return _M_ht.find(__key); }
  433.  
  434.       const_iterator
  435.       find(const key_type& __key) const
  436.       { return _M_ht.find(__key); }
  437.  
  438.       size_type
  439.       count(const key_type& __key) const
  440.       { return _M_ht.count(__key); }
  441.  
  442.       pair<iterator, iterator>
  443.       equal_range(const key_type& __key)
  444.       { return _M_ht.equal_range(__key); }
  445.  
  446.       pair<const_iterator, const_iterator>
  447.       equal_range(const key_type& __key) const
  448.       { return _M_ht.equal_range(__key); }
  449.  
  450.       size_type
  451.       erase(const key_type& __key)
  452.       { return _M_ht.erase(__key); }
  453.  
  454.       void
  455.       erase(iterator __it)
  456.       { _M_ht.erase(__it); }
  457.  
  458.       void
  459.       erase(iterator __f, iterator __l)
  460.       { _M_ht.erase(__f, __l); }
  461.  
  462.       void
  463.       clear()
  464.       { _M_ht.clear(); }
  465.  
  466.       void
  467.       resize(size_type __hint)
  468.       { _M_ht.resize(__hint); }
  469.  
  470.       size_type
  471.       bucket_count() const
  472.       { return _M_ht.bucket_count(); }
  473.  
  474.       size_type
  475.       max_bucket_count() const
  476.       { return _M_ht.max_bucket_count(); }
  477.      
  478.       size_type
  479.       elems_in_bucket(size_type __n) const
  480.       { return _M_ht.elems_in_bucket(__n); }
  481.     };
  482.  
  483.   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
  484.     inline bool
  485.     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
  486.                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
  487.     { return __hm1._M_ht == __hm2._M_ht; }
  488.  
  489.   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
  490.     inline bool
  491.     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
  492.                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
  493.     { return !(__hm1 == __hm2); }
  494.  
  495.   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
  496.     inline void
  497.     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
  498.          hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
  499.     { __hm1.swap(__hm2); }
  500.  
  501. _GLIBCXX_END_NAMESPACE_VERSION
  502. } // namespace
  503.  
  504. namespace std _GLIBCXX_VISIBILITY(default)
  505. {
  506. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  507.  
  508.   // Specialization of insert_iterator so that it will work for hash_map
  509.   // and hash_multimap.
  510.   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
  511.     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
  512.                                               _EqKey, _Alloc> >
  513.     {
  514.     protected:
  515.       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
  516.         _Container;
  517.       _Container* container;
  518.  
  519.     public:
  520.       typedef _Container          container_type;
  521.       typedef output_iterator_tag iterator_category;
  522.       typedef void                value_type;
  523.       typedef void                difference_type;
  524.       typedef void                pointer;
  525.       typedef void                reference;
  526.      
  527.       insert_iterator(_Container& __x)
  528.       : container(&__x) {}
  529.  
  530.       insert_iterator(_Container& __x, typename _Container::iterator)
  531.       : container(&__x) {}
  532.  
  533.       insert_iterator<_Container>&
  534.       operator=(const typename _Container::value_type& __value)
  535.       {
  536.         container->insert(__value);
  537.         return *this;
  538.       }
  539.  
  540.       insert_iterator<_Container>&
  541.       operator*()
  542.       { return *this; }
  543.  
  544.       insert_iterator<_Container>&
  545.       operator++() { return *this; }
  546.  
  547.       insert_iterator<_Container>&
  548.       operator++(int)
  549.       { return *this; }
  550.     };
  551.  
  552.   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
  553.     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
  554.                                                    _EqKey, _Alloc> >
  555.     {
  556.     protected:
  557.       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
  558.         _Container;
  559.       _Container* container;
  560.       typename _Container::iterator iter;
  561.  
  562.     public:
  563.       typedef _Container          container_type;
  564.       typedef output_iterator_tag iterator_category;
  565.       typedef void                value_type;
  566.       typedef void                difference_type;
  567.       typedef void                pointer;
  568.       typedef void                reference;
  569.  
  570.       insert_iterator(_Container& __x)
  571.       : container(&__x) {}
  572.  
  573.       insert_iterator(_Container& __x, typename _Container::iterator)
  574.       : container(&__x) {}
  575.  
  576.       insert_iterator<_Container>&
  577.       operator=(const typename _Container::value_type& __value)
  578.       {
  579.         container->insert(__value);
  580.         return *this;
  581.       }
  582.  
  583.       insert_iterator<_Container>&
  584.       operator*()
  585.       { return *this; }
  586.  
  587.       insert_iterator<_Container>&
  588.       operator++()
  589.       { return *this; }
  590.  
  591.       insert_iterator<_Container>&
  592.       operator++(int)
  593.       { return *this; }
  594.     };
  595.  
  596. _GLIBCXX_END_NAMESPACE_VERSION
  597. } // namespace
  598.  
  599. #endif
  600.