Mercurial > hg > CbC > CbC_gcc
comparison libstdc++-v3/include/bits/hashtable.h @ 157:dafe684d005c
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 May 2020 18:08:54 +0900 |
parents | 1830386684a0 |
children |
comparison
equal
deleted
inserted
replaced
156:a4a7bdaf5ae6 | 157:dafe684d005c |
---|---|
707 | 707 |
708 // Get the node before __n in the bucket __bkt | 708 // Get the node before __n in the bucket __bkt |
709 __node_base* | 709 __node_base* |
710 _M_get_previous_node(size_type __bkt, __node_base* __n); | 710 _M_get_previous_node(size_type __bkt, __node_base* __n); |
711 | 711 |
712 // Insert node __n with key __k and hash code __code, in bucket __bkt | 712 // Insert node __n with key __k and hash code __code0, in bucket __bkt |
713 // if no rehash (assumes no element with same key already present). | 713 // if no rehash (assumes no element with same key already present). |
714 // Takes ownership of __n if insertion succeeds, throws otherwise. | 714 // Takes ownership of __n if insertion succeeds, throws otherwise. |
715 iterator | 715 iterator |
716 _M_insert_unique_node(const key_type& __k, size_type __bkt, | 716 _M_insert_unique_node(const key_type& __k, size_type __bkt, |
717 __hash_code __code, __node_type* __n, | 717 __hash_code __code0, __node_type* __n, |
718 size_type __n_elt = 1); | 718 size_type __n_elt = 1); |
719 | 719 |
720 // Insert node __n with key __k and hash code __code. | 720 // Insert node __n with key __k and hash code __code0. |
721 // Takes ownership of __n if insertion succeeds, throws otherwise. | 721 // Takes ownership of __n if insertion succeeds, throws otherwise. |
722 iterator | 722 iterator |
723 _M_insert_multi_node(__node_type* __hint, const key_type& __k, | 723 _M_insert_multi_node(__node_type* __hint, const key_type& __k, |
724 __hash_code __code, __node_type* __n); | 724 __hash_code __code0, __node_type* __n); |
725 | 725 |
726 template<typename... _Args> | 726 template<typename... _Args> |
727 std::pair<iterator, bool> | 727 std::pair<iterator, bool> |
728 _M_emplace(true_type, _Args&&... __args); | 728 _M_emplace(true_type, _Args&&... __args); |
729 | 729 |
834 else | 834 else |
835 { | 835 { |
836 __glibcxx_assert(get_allocator() == __nh.get_allocator()); | 836 __glibcxx_assert(get_allocator() == __nh.get_allocator()); |
837 | 837 |
838 const key_type& __k = __nh._M_key(); | 838 const key_type& __k = __nh._M_key(); |
839 __hash_code __code = this->_M_hash_code(__k); | 839 __hash_code __code0 = this->_M_hash_code(__k); |
840 size_type __bkt = _M_bucket_index(__k, __code); | 840 size_type __bkt = _M_bucket_index(__k, __code0); |
841 if (__node_type* __n = _M_find_node(__bkt, __k, __code)) | 841 if (__node_type* __n = _M_find_node(__bkt, __k, __code0)) |
842 { | 842 { |
843 __ret.node = std::move(__nh); | 843 __ret.node = std::move(__nh); |
844 __ret.position = iterator(__n); | 844 __ret.position = iterator(__n); |
845 __ret.inserted = false; | 845 __ret.inserted = false; |
846 } | 846 } |
847 else | 847 else |
848 { | 848 { |
849 __ret.position | 849 __ret.position |
850 = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr); | 850 = _M_insert_unique_node(__k, __bkt, __code0, __nh._M_ptr); |
851 __nh._M_ptr = nullptr; | 851 __nh._M_ptr = nullptr; |
852 __ret.inserted = true; | 852 __ret.inserted = true; |
853 } | 853 } |
854 } | 854 } |
855 return __ret; | 855 return __ret; |
863 return end(); | 863 return end(); |
864 | 864 |
865 __glibcxx_assert(get_allocator() == __nh.get_allocator()); | 865 __glibcxx_assert(get_allocator() == __nh.get_allocator()); |
866 | 866 |
867 const key_type& __k = __nh._M_key(); | 867 const key_type& __k = __nh._M_key(); |
868 auto __code = this->_M_hash_code(__k); | 868 auto __code0 = this->_M_hash_code(__k); |
869 auto __ret | 869 auto __ret |
870 = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr); | 870 = _M_insert_multi_node(__hint._M_cur, __k, __code0, __nh._M_ptr); |
871 __nh._M_ptr = nullptr; | 871 __nh._M_ptr = nullptr; |
872 return __ret; | 872 return __ret; |
873 } | 873 } |
874 | 874 |
875 private: | 875 private: |
906 /// Extract a node. | 906 /// Extract a node. |
907 node_type | 907 node_type |
908 extract(const _Key& __k) | 908 extract(const _Key& __k) |
909 { | 909 { |
910 node_type __nh; | 910 node_type __nh; |
911 __hash_code __code = this->_M_hash_code(__k); | 911 __hash_code __code0 = this->_M_hash_code(__k); |
912 std::size_t __bkt = _M_bucket_index(__k, __code); | 912 std::size_t __bkt = _M_bucket_index(__k, __code0); |
913 if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code)) | 913 if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code0)) |
914 __nh = _M_extract_node(__bkt, __prev_node); | 914 __nh = _M_extract_node(__bkt, __prev_node); |
915 return __nh; | 915 return __nh; |
916 } | 916 } |
917 | 917 |
918 /// Merge from a compatible container into one with unique keys. | 918 /// Merge from a compatible container into one with unique keys. |
927 auto __n_elt = __src.size(); | 927 auto __n_elt = __src.size(); |
928 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) | 928 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) |
929 { | 929 { |
930 auto __pos = __i++; | 930 auto __pos = __i++; |
931 const key_type& __k = this->_M_extract()(*__pos); | 931 const key_type& __k = this->_M_extract()(*__pos); |
932 __hash_code __code = this->_M_hash_code(__k); | 932 __hash_code __code0 = this->_M_hash_code(__k); |
933 size_type __bkt = _M_bucket_index(__k, __code); | 933 size_type __bkt = _M_bucket_index(__k, __code0); |
934 if (_M_find_node(__bkt, __k, __code) == nullptr) | 934 if (_M_find_node(__bkt, __k, __code0) == nullptr) |
935 { | 935 { |
936 auto __nh = __src.extract(__pos); | 936 auto __nh = __src.extract(__pos); |
937 _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr, | 937 _M_insert_unique_node(__k, __bkt, __code0, __nh._M_ptr, |
938 __n_elt); | 938 __n_elt); |
939 __nh._M_ptr = nullptr; | 939 __nh._M_ptr = nullptr; |
940 __n_elt = 1; | 940 __n_elt = 1; |
941 } | 941 } |
942 else if (__n_elt != 1) | 942 else if (__n_elt != 1) |
1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1448 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1448 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1449 find(const key_type& __k) | 1449 find(const key_type& __k) |
1450 -> iterator | 1450 -> iterator |
1451 { | 1451 { |
1452 __hash_code __code = this->_M_hash_code(__k); | 1452 __hash_code __code0 = this->_M_hash_code(__k); |
1453 std::size_t __bkt = _M_bucket_index(__k, __code); | 1453 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1454 __node_type* __p = _M_find_node(__bkt, __k, __code); | 1454 __node_type* __p = _M_find_node(__bkt, __k, __code0); |
1455 return __p ? iterator(__p) : end(); | 1455 return __p ? iterator(__p) : end(); |
1456 } | 1456 } |
1457 | 1457 |
1458 template<typename _Key, typename _Value, | 1458 template<typename _Key, typename _Value, |
1459 typename _Alloc, typename _ExtractKey, typename _Equal, | 1459 typename _Alloc, typename _ExtractKey, typename _Equal, |
1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1464 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1464 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1465 find(const key_type& __k) const | 1465 find(const key_type& __k) const |
1466 -> const_iterator | 1466 -> const_iterator |
1467 { | 1467 { |
1468 __hash_code __code = this->_M_hash_code(__k); | 1468 __hash_code __code0 = this->_M_hash_code(__k); |
1469 std::size_t __bkt = _M_bucket_index(__k, __code); | 1469 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1470 __node_type* __p = _M_find_node(__bkt, __k, __code); | 1470 __node_type* __p = _M_find_node(__bkt, __k, __code0); |
1471 return __p ? const_iterator(__p) : end(); | 1471 return __p ? const_iterator(__p) : end(); |
1472 } | 1472 } |
1473 | 1473 |
1474 template<typename _Key, typename _Value, | 1474 template<typename _Key, typename _Value, |
1475 typename _Alloc, typename _ExtractKey, typename _Equal, | 1475 typename _Alloc, typename _ExtractKey, typename _Equal, |
1479 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1479 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1480 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1480 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1481 count(const key_type& __k) const | 1481 count(const key_type& __k) const |
1482 -> size_type | 1482 -> size_type |
1483 { | 1483 { |
1484 __hash_code __code = this->_M_hash_code(__k); | 1484 __hash_code __code0 = this->_M_hash_code(__k); |
1485 std::size_t __bkt = _M_bucket_index(__k, __code); | 1485 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1486 __node_type* __p = _M_bucket_begin(__bkt); | 1486 __node_type* __p = _M_bucket_begin(__bkt); |
1487 if (!__p) | 1487 if (!__p) |
1488 return 0; | 1488 return 0; |
1489 | 1489 |
1490 std::size_t __result = 0; | 1490 std::size_t __result = 0; |
1491 for (;; __p = __p->_M_next()) | 1491 for (;; __p = __p->_M_next()) |
1492 { | 1492 { |
1493 if (this->_M_equals(__k, __code, __p)) | 1493 if (this->_M_equals(__k, __code0, __p)) |
1494 ++__result; | 1494 ++__result; |
1495 else if (__result) | 1495 else if (__result) |
1496 // All equivalent values are next to each other, if we | 1496 // All equivalent values are next to each other, if we |
1497 // found a non-equivalent value after an equivalent one it | 1497 // found a non-equivalent value after an equivalent one it |
1498 // means that we won't find any new equivalent value. | 1498 // means that we won't find any new equivalent value. |
1511 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1511 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1512 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1512 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1513 equal_range(const key_type& __k) | 1513 equal_range(const key_type& __k) |
1514 -> pair<iterator, iterator> | 1514 -> pair<iterator, iterator> |
1515 { | 1515 { |
1516 __hash_code __code = this->_M_hash_code(__k); | 1516 __hash_code __code0 = this->_M_hash_code(__k); |
1517 std::size_t __bkt = _M_bucket_index(__k, __code); | 1517 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1518 __node_type* __p = _M_find_node(__bkt, __k, __code); | 1518 __node_type* __p = _M_find_node(__bkt, __k, __code0); |
1519 | 1519 |
1520 if (__p) | 1520 if (__p) |
1521 { | 1521 { |
1522 __node_type* __p1 = __p->_M_next(); | 1522 __node_type* __p1 = __p->_M_next(); |
1523 while (__p1 && _M_bucket_index(__p1) == __bkt | 1523 while (__p1 && _M_bucket_index(__p1) == __bkt |
1524 && this->_M_equals(__k, __code, __p1)) | 1524 && this->_M_equals(__k, __code0, __p1)) |
1525 __p1 = __p1->_M_next(); | 1525 __p1 = __p1->_M_next(); |
1526 | 1526 |
1527 return std::make_pair(iterator(__p), iterator(__p1)); | 1527 return std::make_pair(iterator(__p), iterator(__p1)); |
1528 } | 1528 } |
1529 else | 1529 else |
1538 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1538 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1539 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1539 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1540 equal_range(const key_type& __k) const | 1540 equal_range(const key_type& __k) const |
1541 -> pair<const_iterator, const_iterator> | 1541 -> pair<const_iterator, const_iterator> |
1542 { | 1542 { |
1543 __hash_code __code = this->_M_hash_code(__k); | 1543 __hash_code __code0 = this->_M_hash_code(__k); |
1544 std::size_t __bkt = _M_bucket_index(__k, __code); | 1544 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1545 __node_type* __p = _M_find_node(__bkt, __k, __code); | 1545 __node_type* __p = _M_find_node(__bkt, __k, __code0); |
1546 | 1546 |
1547 if (__p) | 1547 if (__p) |
1548 { | 1548 { |
1549 __node_type* __p1 = __p->_M_next(); | 1549 __node_type* __p1 = __p->_M_next(); |
1550 while (__p1 && _M_bucket_index(__p1) == __bkt | 1550 while (__p1 && _M_bucket_index(__p1) == __bkt |
1551 && this->_M_equals(__k, __code, __p1)) | 1551 && this->_M_equals(__k, __code0, __p1)) |
1552 __p1 = __p1->_M_next(); | 1552 __p1 = __p1->_M_next(); |
1553 | 1553 |
1554 return std::make_pair(const_iterator(__p), const_iterator(__p1)); | 1554 return std::make_pair(const_iterator(__p), const_iterator(__p1)); |
1555 } | 1555 } |
1556 else | 1556 else |
1565 typename _Traits> | 1565 typename _Traits> |
1566 auto | 1566 auto |
1567 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1567 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1568 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1568 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1569 _M_find_before_node(size_type __bkt, const key_type& __k, | 1569 _M_find_before_node(size_type __bkt, const key_type& __k, |
1570 __hash_code __code) const | 1570 __hash_code __code0) const |
1571 -> __node_base* | 1571 -> __node_base* |
1572 { | 1572 { |
1573 __node_base* __prev_p = _M_buckets[__bkt]; | 1573 __node_base* __prev_p = _M_buckets[__bkt]; |
1574 if (!__prev_p) | 1574 if (!__prev_p) |
1575 return nullptr; | 1575 return nullptr; |
1576 | 1576 |
1577 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; | 1577 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; |
1578 __p = __p->_M_next()) | 1578 __p = __p->_M_next()) |
1579 { | 1579 { |
1580 if (this->_M_equals(__k, __code, __p)) | 1580 if (this->_M_equals(__k, __code0, __p)) |
1581 return __prev_p; | 1581 return __prev_p; |
1582 | 1582 |
1583 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) | 1583 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) |
1584 break; | 1584 break; |
1585 __prev_p = __p; | 1585 __prev_p = __p; |
1670 -> pair<iterator, bool> | 1670 -> pair<iterator, bool> |
1671 { | 1671 { |
1672 // First build the node to get access to the hash code | 1672 // First build the node to get access to the hash code |
1673 _Scoped_node __node { this, std::forward<_Args>(__args)... }; | 1673 _Scoped_node __node { this, std::forward<_Args>(__args)... }; |
1674 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); | 1674 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); |
1675 __hash_code __code = this->_M_hash_code(__k); | 1675 __hash_code __code0 = this->_M_hash_code(__k); |
1676 size_type __bkt = _M_bucket_index(__k, __code); | 1676 size_type __bkt = _M_bucket_index(__k, __code0); |
1677 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) | 1677 if (__node_type* __p = _M_find_node(__bkt, __k, __code0)) |
1678 // There is already an equivalent node, no insertion | 1678 // There is already an equivalent node, no insertion |
1679 return std::make_pair(iterator(__p), false); | 1679 return std::make_pair(iterator(__p), false); |
1680 | 1680 |
1681 // Insert the node | 1681 // Insert the node |
1682 auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node); | 1682 auto __pos = _M_insert_unique_node(__k, __bkt, __code0, __node._M_node); |
1683 __node._M_node = nullptr; | 1683 __node._M_node = nullptr; |
1684 return { __pos, true }; | 1684 return { __pos, true }; |
1685 } | 1685 } |
1686 | 1686 |
1687 template<typename _Key, typename _Value, | 1687 template<typename _Key, typename _Value, |
1697 { | 1697 { |
1698 // First build the node to get its hash code. | 1698 // First build the node to get its hash code. |
1699 _Scoped_node __node { this, std::forward<_Args>(__args)... }; | 1699 _Scoped_node __node { this, std::forward<_Args>(__args)... }; |
1700 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); | 1700 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); |
1701 | 1701 |
1702 __hash_code __code = this->_M_hash_code(__k); | 1702 __hash_code __code0 = this->_M_hash_code(__k); |
1703 auto __pos | 1703 auto __pos |
1704 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); | 1704 = _M_insert_multi_node(__hint._M_cur, __k, __code0, __node._M_node); |
1705 __node._M_node = nullptr; | 1705 __node._M_node = nullptr; |
1706 return __pos; | 1706 return __pos; |
1707 } | 1707 } |
1708 | 1708 |
1709 template<typename _Key, typename _Value, | 1709 template<typename _Key, typename _Value, |
1712 typename _Traits> | 1712 typename _Traits> |
1713 auto | 1713 auto |
1714 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1714 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1715 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1715 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1716 _M_insert_unique_node(const key_type& __k, size_type __bkt, | 1716 _M_insert_unique_node(const key_type& __k, size_type __bkt, |
1717 __hash_code __code, __node_type* __node, | 1717 __hash_code __code0, __node_type* __node, |
1718 size_type __n_elt) | 1718 size_type __n_elt) |
1719 -> iterator | 1719 -> iterator |
1720 { | 1720 { |
1721 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); | 1721 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); |
1722 std::pair<bool, std::size_t> __do_rehash | 1722 std::pair<bool, std::size_t> __do_rehash |
1724 __n_elt); | 1724 __n_elt); |
1725 | 1725 |
1726 if (__do_rehash.first) | 1726 if (__do_rehash.first) |
1727 { | 1727 { |
1728 _M_rehash(__do_rehash.second, __saved_state); | 1728 _M_rehash(__do_rehash.second, __saved_state); |
1729 __bkt = _M_bucket_index(__k, __code); | 1729 __bkt = _M_bucket_index(__k, __code0); |
1730 } | 1730 } |
1731 | 1731 |
1732 this->_M_store_code(__node, __code); | 1732 this->_M_store_code(__node, __code0); |
1733 | 1733 |
1734 // Always insert at the beginning of the bucket. | 1734 // Always insert at the beginning of the bucket. |
1735 _M_insert_bucket_begin(__bkt, __node); | 1735 _M_insert_bucket_begin(__bkt, __node); |
1736 ++_M_element_count; | 1736 ++_M_element_count; |
1737 return iterator(__node); | 1737 return iterator(__node); |
1743 typename _Traits> | 1743 typename _Traits> |
1744 auto | 1744 auto |
1745 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1745 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1746 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1746 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1747 _M_insert_multi_node(__node_type* __hint, const key_type& __k, | 1747 _M_insert_multi_node(__node_type* __hint, const key_type& __k, |
1748 __hash_code __code, __node_type* __node) | 1748 __hash_code __code0, __node_type* __node) |
1749 -> iterator | 1749 -> iterator |
1750 { | 1750 { |
1751 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); | 1751 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); |
1752 std::pair<bool, std::size_t> __do_rehash | 1752 std::pair<bool, std::size_t> __do_rehash |
1753 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); | 1753 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); |
1754 | 1754 |
1755 if (__do_rehash.first) | 1755 if (__do_rehash.first) |
1756 _M_rehash(__do_rehash.second, __saved_state); | 1756 _M_rehash(__do_rehash.second, __saved_state); |
1757 | 1757 |
1758 this->_M_store_code(__node, __code); | 1758 this->_M_store_code(__node, __code0); |
1759 size_type __bkt = _M_bucket_index(__k, __code); | 1759 size_type __bkt = _M_bucket_index(__k, __code0); |
1760 | 1760 |
1761 // Find the node before an equivalent one or use hint if it exists and | 1761 // Find the node before an equivalent one or use hint if it exists and |
1762 // if it is equivalent. | 1762 // if it is equivalent. |
1763 __node_base* __prev | 1763 __node_base* __prev |
1764 = __builtin_expect(__hint != nullptr, false) | 1764 = __builtin_expect(__hint != nullptr, false) |
1765 && this->_M_equals(__k, __code, __hint) | 1765 && this->_M_equals(__k, __code0, __hint) |
1766 ? __hint | 1766 ? __hint |
1767 : _M_find_before_node(__bkt, __k, __code); | 1767 : _M_find_before_node(__bkt, __k, __code0); |
1768 if (__prev) | 1768 if (__prev) |
1769 { | 1769 { |
1770 // Insert after the node before the equivalent one. | 1770 // Insert after the node before the equivalent one. |
1771 __node->_M_nxt = __prev->_M_nxt; | 1771 __node->_M_nxt = __prev->_M_nxt; |
1772 __prev->_M_nxt = __node; | 1772 __prev->_M_nxt = __node; |
1773 if (__builtin_expect(__prev == __hint, false)) | 1773 if (__builtin_expect(__prev == __hint, false)) |
1774 // hint might be the last bucket node, in this case we need to | 1774 // hint might be the last bucket node, in this case we need to |
1775 // update next bucket. | 1775 // update next bucket. |
1776 if (__node->_M_nxt | 1776 if (__node->_M_nxt |
1777 && !this->_M_equals(__k, __code, __node->_M_next())) | 1777 && !this->_M_equals(__k, __code0, __node->_M_next())) |
1778 { | 1778 { |
1779 size_type __next_bkt = _M_bucket_index(__node->_M_next()); | 1779 size_type __next_bkt = _M_bucket_index(__node->_M_next()); |
1780 if (__next_bkt != __bkt) | 1780 if (__next_bkt != __bkt) |
1781 _M_buckets[__next_bkt] = __node; | 1781 _M_buckets[__next_bkt] = __node; |
1782 } | 1782 } |
1802 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, | 1802 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, |
1803 size_type __n_elt) | 1803 size_type __n_elt) |
1804 -> pair<iterator, bool> | 1804 -> pair<iterator, bool> |
1805 { | 1805 { |
1806 const key_type& __k = this->_M_extract()(__v); | 1806 const key_type& __k = this->_M_extract()(__v); |
1807 __hash_code __code = this->_M_hash_code(__k); | 1807 __hash_code __code0 = this->_M_hash_code(__k); |
1808 size_type __bkt = _M_bucket_index(__k, __code); | 1808 size_type __bkt = _M_bucket_index(__k, __code0); |
1809 | 1809 |
1810 if (__node_type* __node = _M_find_node(__bkt, __k, __code)) | 1810 if (__node_type* __node = _M_find_node(__bkt, __k, __code0)) |
1811 return { iterator(__node), false }; | 1811 return { iterator(__node), false }; |
1812 | 1812 |
1813 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; | 1813 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; |
1814 auto __pos | 1814 auto __pos |
1815 = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt); | 1815 = _M_insert_unique_node(__k, __bkt, __code0, __node._M_node, __n_elt); |
1816 __node._M_node = nullptr; | 1816 __node._M_node = nullptr; |
1817 return { __pos, true }; | 1817 return { __pos, true }; |
1818 } | 1818 } |
1819 | 1819 |
1820 // Insert v unconditionally. | 1820 // Insert v unconditionally. |
1830 const _NodeGenerator& __node_gen, false_type) | 1830 const _NodeGenerator& __node_gen, false_type) |
1831 -> iterator | 1831 -> iterator |
1832 { | 1832 { |
1833 // First compute the hash code so that we don't do anything if it | 1833 // First compute the hash code so that we don't do anything if it |
1834 // throws. | 1834 // throws. |
1835 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); | 1835 __hash_code __code0 = this->_M_hash_code(this->_M_extract()(__v)); |
1836 | 1836 |
1837 // Second allocate new node so that we don't rehash if it throws. | 1837 // Second allocate new node so that we don't rehash if it throws. |
1838 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; | 1838 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; |
1839 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); | 1839 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); |
1840 auto __pos | 1840 auto __pos |
1841 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); | 1841 = _M_insert_multi_node(__hint._M_cur, __k, __code0, __node._M_node); |
1842 __node._M_node = nullptr; | 1842 __node._M_node = nullptr; |
1843 return __pos; | 1843 return __pos; |
1844 } | 1844 } |
1845 | 1845 |
1846 template<typename _Key, typename _Value, | 1846 template<typename _Key, typename _Value, |
1899 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1899 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1900 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1900 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1901 _M_erase(true_type, const key_type& __k) | 1901 _M_erase(true_type, const key_type& __k) |
1902 -> size_type | 1902 -> size_type |
1903 { | 1903 { |
1904 __hash_code __code = this->_M_hash_code(__k); | 1904 __hash_code __code0 = this->_M_hash_code(__k); |
1905 std::size_t __bkt = _M_bucket_index(__k, __code); | 1905 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1906 | 1906 |
1907 // Look for the node before the first matching node. | 1907 // Look for the node before the first matching node. |
1908 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); | 1908 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code0); |
1909 if (!__prev_n) | 1909 if (!__prev_n) |
1910 return 0; | 1910 return 0; |
1911 | 1911 |
1912 // We found a matching node, erase it. | 1912 // We found a matching node, erase it. |
1913 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); | 1913 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); |
1923 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | 1923 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1924 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: | 1924 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: |
1925 _M_erase(false_type, const key_type& __k) | 1925 _M_erase(false_type, const key_type& __k) |
1926 -> size_type | 1926 -> size_type |
1927 { | 1927 { |
1928 __hash_code __code = this->_M_hash_code(__k); | 1928 __hash_code __code0 = this->_M_hash_code(__k); |
1929 std::size_t __bkt = _M_bucket_index(__k, __code); | 1929 std::size_t __bkt = _M_bucket_index(__k, __code0); |
1930 | 1930 |
1931 // Look for the node before the first matching node. | 1931 // Look for the node before the first matching node. |
1932 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); | 1932 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code0); |
1933 if (!__prev_n) | 1933 if (!__prev_n) |
1934 return 0; | 1934 return 0; |
1935 | 1935 |
1936 // _GLIBCXX_RESOLVE_LIB_DEFECTS | 1936 // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1937 // 526. Is it undefined if a function in the standard changes | 1937 // 526. Is it undefined if a function in the standard changes |
1947 __n_last = __n_last->_M_next(); | 1947 __n_last = __n_last->_M_next(); |
1948 if (!__n_last) | 1948 if (!__n_last) |
1949 break; | 1949 break; |
1950 __n_last_bkt = _M_bucket_index(__n_last); | 1950 __n_last_bkt = _M_bucket_index(__n_last); |
1951 } | 1951 } |
1952 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); | 1952 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code0, __n_last)); |
1953 | 1953 |
1954 // Deallocate nodes. | 1954 // Deallocate nodes. |
1955 size_type __result = 0; | 1955 size_type __result = 0; |
1956 do | 1956 do |
1957 { | 1957 { |