visus
/
toolchain-gcc-arm-embedded
Watch 1
Star 0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
Branch: main
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/ext/hash_map

600 lines
17KB
Raw Permalink Blame History 

  1. // Hashing map implementation -*- C++ -*-

  2. 

  3. // Copyright (C) 2001-2020 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/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.       _GLIBCXX_NODISCARD 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.       _GLIBCXX_NODISCARD 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