summaryrefslogtreecommitdiffstats
path: root/libcxx/include/unordered_map
Commit message (Collapse)AuthorAgeFilesLines
* Add contains method to associative containers. This patch implements ↵Zoe Carver2019-07-161-0/+10
| | | | | | P0458R2, adding contains to map, multimap, unordered_map, unordered_multimap, set, multiset, unordered_set, and unordered_multiset. llvm-svn: 366170
* [libc++] Implement P0433: deduction guides for <unordered_map>Louis Dionne2019-07-151-6/+140
| | | | | | | | Thanks to Arthur O'Dwyer for the patch. Differential Revision: https://reviews.llvm.org/D58590 llvm-svn: 366124
* [NFC][libcxx] Remove trailing whitespaceLouis Dionne2019-05-291-8/+8
| | | | | | It's incredibly annoying when trying to create diffs llvm-svn: 361981
* [libc++] Make sure we don't eagerly diagnose non-const comparators for ↵Louis Dionne2019-04-111-4/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | containers of incomplete types Summary: In r348529, I improved the library-defined diagnostic for using containers with a non-const comparator/hasher. However, the check is now performed too early, which leads to the diagnostic being emitted in cases where it shouldn't. See PR41360 for details. This patch moves the diagnostic to the destructor of the containers, which means that the diagnostic will only be emitted when the container is instantiated at a point where the comparator and the key/value are required to be complete. We still retain better diagnostics than before r348529, because the diagnostics are performed in the containers themselves instead of __tree and __hash_table. As a drive-by fix, I improved the diagnostic to mention that we can't find a _viable_ const call operator, as suggested by EricWF in PR41360. Reviewers: EricWF, mclow.lists Subscribers: christof, jkorous, dexonsmith, libcxx-commits, zoecarver Tags: #libc Differential Revision: https://reviews.llvm.org/D60540 llvm-svn: 358189
* [libc++] Avoid UB in the no-exceptions mode in a few placesLouis Dionne2019-02-121-6/+2
| | | | | | | | | | | | | | | | | | | | | | | Summary: A few places in the library seem to behave unexpectedly when the library is compiled or used with exceptions disabled. For example, not throwing an exception when a pointer is NULL can lead us to dereference the pointer later on, which is UB. This patch fixes such occurences. It's hard to tell whether there are other places where the no-exceptions mode misbehaves like this, because the replacement for throwing an exception does not always seem to be abort()ing, but at least this patch will improve the situation somewhat. See http://lists.llvm.org/pipermail/libcxx-dev/2019-January/000172.html Reviewers: mclow.lists, EricWF Subscribers: christof, jkorous, dexonsmith, libcxx-commits Differential Revision: https://reviews.llvm.org/D57761 llvm-svn: 353850
* Update more file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | | to reflect the new license. These used slightly different spellings that defeated my regular expressions. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351648
* Implement P1209 - Adopt Consistent Container Erasure from Library ↵Marshall Clow2018-12-141-0/+20
| | | | | | Fundamentals 2 for C++20. Reviewed as https://reviews.llvm.org/D55532 llvm-svn: 349178
* [libc++] Improve diagnostics for non-const comparators and hashers in ↵Louis Dionne2018-12-061-2/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | associative containers Summary: When providing a non-const-callable comparator in a map or set, the warning diagnostic does not include the point of instantiation of the container that triggered the warning, which makes it difficult to track down the problem. This commit improves the diagnostic by placing it directly in the body of the associative container. The same change is applied to unordered associative containers, which had a similar problem. Finally, this commit cleans up the forward declarations of several map and unordered_map helpers, which are not needed anymore. <rdar://problem/41370747> Reviewers: EricWF, mclow.lists Subscribers: christof, dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D48955 llvm-svn: 348529
* Second half of C++17's splicing maps and setsErik Pilkington2018-10-311-0/+97
| | | | | | | | | | This commit adds a merge member function to all the map and set containers, which splices nodes from the source container. This completes support for P0083r3. Differential revision: https://reviews.llvm.org/D48896 llvm-svn: 345744
* Implement the infrastructure for feature-test macros. Very few actual ↵Marshall Clow2018-09-121-0/+1
| | | | | | feature test macros, though. Reviewed as: https://reviews.llvm.org/D51955 llvm-svn: 342073
* First half of C++17's splicing maps and setsErik Pilkington2018-08-011-1/+86
| | | | | | | | | | | | | This commit adds a node handle type, (located in __node_handle), and adds extract() and insert() members to all map and set types, as well as their implementations in __tree and __hash_table. The second half of this feature is adding merge() members, which splice nodes in bulk from one container into another. This will be committed in a follow-up. Differential revision: https://reviews.llvm.org/D46845 llvm-svn: 338472
* Fix a strict aliasing violation in map and unordered_map.Erik Pilkington2018-06-041-31/+81
| | | | | | | | | | | | These containers type-punned between pair<K, V> and pair<const K, V> as an optimization. This commit instead provides access to the pair via a pair of references that assign through to the underlying object. It's still undefined to mutate a const object, but clang doesn't optimize on this for data members, so this should be safe. Differential revision: https://reviews.llvm.org/D47607 llvm-svn: 333948
* First part of P0600 - '[[nodiscard] in the standard library'. Mark the ↵Marshall Clow2017-11-151-2/+2
| | | | | | 'empty()' methods of all the containers as nodiscard. If you're calling empty() w/o looking at the result, you probably meanto to call 'clear()'. c++2a only llvm-svn: 318269
* Cleanup _LIBCPP_HAS_NO_<c++11-feature> in std::unordered_map and ↵Eric Fiselier2017-04-181-85/+47
| | | | | | | | std::unordered_multimap This completes the cleanup of the containers, at least within the tests. llvm-svn: 300620
* Fix more bad member swap definitions in unordered_map.Eric Fiselier2017-04-131-2/+2
| | | | | | | | | | | The __unordered_map_equal and __unordered_map_hash wrappers attempt to swap const qualified predicates whenever the predicate is empty, and is subject to the EBO. Swapping const values seems blatently incorrect. This patch removes the const qualifier so the values are swapped as non-const. llvm-svn: 300154
* Diagnose non-const-callable hash functions and comparatorsEric Fiselier2017-01-131-6/+2
| | | | llvm-svn: 291969
* [NFC] Rename _LIBCPP_TYPE_VIS_ONLY to _LIBCPP_TEMPLATE_VISEric Fiselier2017-01-041-13/+13
| | | | | | | | | | | | | The name _LIBCPP_TYPE_VIS_ONLY is no longer accurate because both _LIBCPP_TYPE_VIS and _LIBCPP_TYPE_VIS_ONLY expand to __attribute__((__type_visibility__)) with Clang. The only remaining difference is that _LIBCPP_TYPE_VIS_ONLY can be applied to templates whereas _LIBCPP_TYPE_VIS cannot (due to dllimport/dllexport not being allowed on templates). This patch renames _LIBCPP_TYPE_VIS_ONLY to _LIBCPP_TEMPLATE_VIS. llvm-svn: 291035
* Add tests for unordered container tests and std::stringEric Fiselier2016-12-281-1/+1
| | | | llvm-svn: 290655
* Fix unused parameters and variablesEric Fiselier2016-12-231-3/+17
| | | | llvm-svn: 290459
* [libc++] Fix typos causing compilation errors when _LIBCPP_DEBUG_LEVEL >= 2Oleg Ranevskyy2016-09-261-2/+2
| | | | | | | | | | | | Summary: This patch fixes a couple of typos that cause compilation errors when application includes <unordered_map> and enables the libc++'s debugging capabilities. Reviewers: EricWF Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24883 llvm-svn: 282446
* Support allocators with explicit conversion constructors. Fixes bug #29000Marshall Clow2016-08-171-12/+12
| | | | llvm-svn: 278904
* Change a couple ifdefs from '#if __cplusplus >= 2011xxx' to '#ifndef ↵Marshall Clow2016-07-181-2/+2
| | | | | | _LIBCPP_CXX03_LANG'. No functionality change. llvm-svn: 275787
* Cleanup: move visibility/linkage attributes to the first declaration.Evgeniy Stepanov2016-04-221-10/+20
| | | | | | http://reviews.llvm.org/D15404 llvm-svn: 267093
* Mark LWG issue 2469 as done. Also simplify try_emplace and insert_or_assign ↵Eric Fiselier2016-04-181-63/+31
| | | | | | implementations in unordered_map llvm-svn: 266591
* Fix LWG issue 2345 - Add insert(value_type&&)Eric Fiselier2016-04-181-67/+82
| | | | llvm-svn: 266585
* Fix LWG issue 2469 - Use piecewise construction in unordered_map::operator[].Eric Fiselier2016-02-111-30/+21
| | | | | | | | | | | | | unordered_map's allocator may only be used to construct objects of 'value_type', or in this case 'pair<const Key, Value>'. In order to respect this requirement in operator[], which requires default constructing the 'mapped_type', we have to use pair's piecewise constructor with '(tuple<Kep>, tuple<>)'. Unfortunately we still need to provide a fallback implementation for C++03 since we don't have <tuple>. Even worse this fallback is the last remaining user of '__hash_map_node_destructor' and '__construct_node_with_key'. llvm-svn: 260601
* Revert r260514 because it has a bogus commit message.Eric Fiselier2016-02-111-21/+30
| | | | llvm-svn: 260556
* Teach __hash_table how to handle unordered_map's __hash_value_type.Eric Fiselier2016-02-111-30/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch is fairly large and contains a number of changes. The main change is teaching '__hash_table' how to handle '__hash_value_type'. Unfortunately this change is a rampant layering violation, but it's required to make unordered_map conforming without re-writing all of __hash_table. After this change 'unordered_map' can delegate to '__hash_table' in almost all cases. The major changes found in this patch are: * Teach __hash_table to differentiate between the true container value type and the node value type by introducing the "__container_value_type" and "__node_value_type" typedefs. In the case of unordered_map '__container_value_type' is 'pair<const Key, Value>' and '__node_value_type' is '__hash_value_type'. * Switch almost all overloads in '__hash_table' previously taking 'value_type' (AKA '__node_value_type) to take '__container_value_type' instead. Previously 'pair<K, V>' would be implicitly converted to '__hash_value_type<K, V>' because of the function signature. * Add '__get_key', '__get_value', '__get_ptr', and '__move' static functions to '__key_value_types'. These functions allow '__hash_table' to unwrap '__node_value_type' objects into '__container_value_type' and its sub-parts. * Pass '__hash_value_type::__value_' to 'a.construct(p, ...)' instead of '__hash_value_type' itself. The C++14 standard requires that 'a.construct()' and 'a.destroy()' are only ever instantiated for the containers value type. * Remove '__hash_value_type's constructors and destructors. We should never construct an instance of this type. (TODO this is UB but we already do it in plenty of places). * Add a generic "try-emplace" function to '__hash_table' called '__emplace_unique_key_args(Key const&, Args...)'. The following changes were done as cleanup: * Introduce the '_LIBCPP_CXX03_LANG' macro to be used in place of '_LIBCPP_HAS_NO_VARIADICS' or '_LIBCPP_HAS_NO_RVALUE_REFERENCE'. * Cleanup C++11 only overloads that assume an incomplete C++11 implementation. For example this patch removes the __construct_node overloads that do manual pack expansion. * Forward 'unordered_map::emplace' to '__hash_table' and remove dead code resulting from the change. This includes almost all 'unordered_map::__construct_node' overloads. The following changes are planed for future revisions: * Fix LWG issue #2469 by delegating 'unordered_map::operator[]' to use '__emplace_unique_key_args'. * Rewrite 'unordered_map::try_emplace' in terms of '__emplace_unique_key_args'. * Optimize '__emplace_unique' to call '__emplace_unique_key_args' when possible. This prevent unneeded allocations when inserting duplicate entries. The additional follow up work needed after this patch: * Respect the lifetime rules for '__hash_value_type' by actually constructing it. * Make '__insert_multi' act similar to '__insert_unique' for objects of type 'T&' and 'T const &&' with 'T = __container_value_type'. llvm-svn: 260514
* Teach __hash_table how to handle unordered_map's __hash_value_type.Eric Fiselier2016-02-111-208/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch is fairly large and contains a number of changes. The main change is teaching '__hash_table' how to handle '__hash_value_type'. Unfortunately this change is a rampant layering violation, but it's required to make unordered_map conforming without re-writing all of __hash_table. After this change 'unordered_map' can delegate to '__hash_table' in almost all cases. The major changes found in this patch are: * Teach __hash_table to differentiate between the true container value type and the node value type by introducing the "__container_value_type" and "__node_value_type" typedefs. In the case of unordered_map '__container_value_type' is 'pair<const Key, Value>' and '__node_value_type' is '__hash_value_type'. * Switch almost all overloads in '__hash_table' previously taking 'value_type' (AKA '__node_value_type) to take '__container_value_type' instead. Previously 'pair<K, V>' would be implicitly converted to '__hash_value_type<K, V>' because of the function signature. * Add '__get_key', '__get_value', '__get_ptr', and '__move' static functions to '__key_value_types'. These functions allow '__hash_table' to unwrap '__node_value_type' objects into '__container_value_type' and its sub-parts. * Pass '__hash_value_type::__value_' to 'a.construct(p, ...)' instead of '__hash_value_type' itself. The C++14 standard requires that 'a.construct()' and 'a.destroy()' are only ever instantiated for the containers value type. * Remove '__hash_value_type's constructors and destructors. We should never construct an instance of this type. (TODO this is UB but we already do it in plenty of places). * Add a generic "try-emplace" function to '__hash_table' called '__emplace_unique_key_args(Key const&, Args...)'. The following changes were done as cleanup: * Introduce the '_LIBCPP_CXX03_LANG' macro to be used in place of '_LIBCPP_HAS_NO_VARIADICS' or '_LIBCPP_HAS_NO_RVALUE_REFERENCE'. * Cleanup C++11 only overloads that assume an incomplete C++11 implementation. For example this patch removes the __construct_node overloads that do manual pack expansion. * Forward 'unordered_map::emplace' to '__hash_table' and remove dead code resulting from the change. This includes almost all 'unordered_map::__construct_node' overloads. The following changes are planed for future revisions: * Fix LWG issue #2469 by delegating 'unordered_map::operator[]' to use '__emplace_unique_key_args'. * Rewrite 'unordered_map::try_emplace' in terms of '__emplace_unique_key_args'. * Optimize '__emplace_unique' to call '__emplace_unique_key_args' when possible. This prevent unneeded allocations when inserting duplicate entries. The additional follow up work needed after this patch: * Respect the lifetime rules for '__hash_value_type' by actually constructing it. * Make '__insert_multi' act similar to '__insert_unique' for objects of type 'T&' and 'T const &&' with 'T = __container_value_type'. llvm-svn: 260513
* Remove changes that snuck in within r260431Eric Fiselier2016-02-101-9/+0
| | | | llvm-svn: 260443
* Recommit r260012 - Cleanup node-type handling in the unordered containers.Eric Fiselier2016-02-101-20/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | This time I kept <ext/hash_map> working! This patch is the first in a series of patches that's meant to better support unordered_map. unordered_map has a special "value_type" that differs from pair<const Key, Value>. In order to meet the EmplaceConstructible and CopyInsertable requirements we need to teach __hash_table about this special value_type. This patch creates a "__hash_node_types" traits class that contains all of the typedefs needed by the unordered containers and it's iterators. These typedefs include ones for each node type and node pointer type, as well as special typedefs for "unordered_map"'s value type. As a result of this change all of the unordered containers now all support incomplete types. As a drive-by fix I changed the difference_type in __hash_table to always be ptrdiff_t. There is a corresponding change to size_type but it cannot take affect until an ABI break. This patch will be followed up shortly with fixes for various unordered_map bugs and problems. llvm-svn: 260431
* Revert r260012 due to __gnu_cxx::hash_map breakageEric Fiselier2016-02-081-27/+20
| | | | llvm-svn: 260172
* Cleanup node-type handling in the unordered containersEric Fiselier2016-02-071-20/+27
| | | | | | | | | | | | | | | | | | | | | | | | | This patch is the first in a series of patches that's meant to better support unordered_map. unordered_map has a special "value_type" that differs from pair<const Key, Value>. In order to meet the EmplaceConstructible and CopyInsertable requirements we need to teach __hash_table about this special value_type. This patch creates a "__hash_node_types" traits class that contains all of the typedefs needed by the unordered containers and it's iterators. These typedefs include ones for each node type and node pointer type, as well as special typedefs for "unordered_map"'s value type. As a result of this change all of the unordered containers now all support incomplete types. As a drive-by fix I changed the difference_type in __hash_table to always be ptrdiff_t. There is a corresponding change to size_type but it cannot take affect until an ABI break. This patch will be followed up shortly with fixes for various unordered_map fixes. llvm-svn: 260012
* Revert "unordered_map: Reuse insert logic in emplace when possible, NFC"Duncan P. N. Exon Smith2016-01-231-27/+3
| | | | | | | | This reverts commit r258575. EricWF sent me an email (no link since it was off-list) requesting to review this pre-commit instead of post-commit. llvm-svn: 258625
* unordered_map: Reuse insert logic in emplace when possible, NFCDuncan P. N. Exon Smith2016-01-221-3/+27
| | | | | | | | | | | | | | | | An upcoming commit will add an optimization to insert() that avoids unnecessary mallocs when we can safely extract the key type. This commit shares code between emplace() and insert(): - if emplace() is given a single argument, and - value_type is constructible from that argument so that we have a single code path for the two. I also updated the debug version of emplace_hint() to defer to emplace(), like the non-debug version does. In both cases, there should be NFC here. llvm-svn: 258575
* Use __rebind_pointer to avoid #ifdef blockEric Fiselier2015-12-301-16/+4
| | | | llvm-svn: 256654
* Fix warnings about pessimizing return moves for C++11 and higherDimitry Andric2015-08-191-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Throughout the libc++ headers, there are a few instances where _VSTD::move() is used to return a local variable. Howard commented in r189039 that these were there "for non-obvious reasons such as to help things limp along in C++03 language mode". However, when compiling these headers with warnings on, and in C++11 or higher mode (like we do in FreeBSD), they cause the following complaints about pessimizing moves: In file included from tests.cpp:26: In file included from tests.hpp:29: /usr/include/c++/v1/map:1368:12: error: moving a local object in a return statement prevents copy elision [-Werror,-Wpessimizing-move] return _VSTD::move(__h); // explicitly moved for C++03 ^ /usr/include/c++/v1/__config:368:15: note: expanded from macro '_VSTD' #define _VSTD std::_LIBCPP_NAMESPACE ^ Attempt to fix this by adding a _LIBCPP_EXPLICIT_MOVE() macro to __config, which gets defined to _VSTD::move for pre-C++11, and to nothing for C++11 and later. I am not completely satisfied with the macro name (I also considered _LIBCPP_COMPAT_MOVE and some other variants), so suggestions are welcome. :) Reviewers: mclow.lists, howard.hinnant, EricWF Subscribers: arthur.j.odwyer, cfe-commits Differential Revision: http://reviews.llvm.org/D11394 llvm-svn: 245421
* Implement the first part of N4258: 'Cleaning up noexcept in the Library'. ↵Marshall Clow2015-07-131-0/+44
| | | | | | This patch deals with swapping containers, and implements a more strict noexcept specification (a conforming extension) than the standard mandates. llvm-svn: 242056
* The rest of N4279 and LWG#2464 - for unordered_mapMarshall Clow2015-07-071-0/+131
| | | | llvm-svn: 241555
* [libcxx] Fix detection of __is_final.Eric Fiselier2015-06-131-8/+4
| | | | | | | | | | | | | | Summary: Currently we only enable the use of __is_final(...) with Clang. GCC also provides __is_final(...) since 4.7 in all standard modes. This patch creates the macro _LIBCPP_HAS_IS_FINAL to note the availability of `__is_final`. Reviewers: danalbert, mclow.lists Reviewed By: mclow.lists Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D8795 llvm-svn: 239664
* Fix for LWG Issue 2059: C++0x ambiguity problem with map::eraseMarshall Clow2015-05-101-0/+6
| | | | llvm-svn: 236950
* Replace two naked references of 'std::' with the macro '_VSTD::'. No ↵Marshall Clow2015-05-061-2/+2
| | | | | | functionality change. llvm-svn: 236593
* In many places, there was an #ifdef/#else block that selected one of two ↵Marshall Clow2015-04-071-14/+4
| | | | | | implmentations of rebind_alloc based on whether or not we had template aliases. Create a helper struct to encapsulate that bit of logic, and replace all the ifdefs with uses of that struct. No functionality change intented. llvm-svn: 234296
* NFC. Move definition of _LIBCPP_ASSERT into __debug header and remove ↵Eric Fiselier2014-08-101-0/+2
| | | | | | | | | | | | | | | | | | external include guards. Things done in this patch: 1. Make __debug include __config since it uses macros from it. 2. The current method of defining _LIBCPP_ASSERT is prone to redefinitions. Move the null _LIBCPP_ASSERT definition into the __debug header to prevent this. 3. Remove external <__debug> include gaurds. <__debug> guards almost all of its contents internally. There is no reason to be doing it externally. This patch should not change any functionality. llvm-svn: 215332
* Fix for PR18735 - self-assignment for map/multimap gives incorrect results ↵Marshall Clow2014-02-081-12/+16
| | | | | | in C++03 llvm-svn: 201021
* SCARY/N2913 iterator support between the multi and non-multi versions of the ↵Howard Hinnant2013-09-301-86/+67
| | | | | | associative and unordered containers. I beleive lack of support for this was accidentally recently introduced (by me) and this is fixing a regression. This time tests are put in to prevent such a regression in the future. llvm-svn: 191692
* LWG Issue 2210 (Part #6): unordered_map and unordered_multimapMarshall Clow2013-09-121-0/+80
| | | | llvm-svn: 190576
* A collection of minor type-o fixes. The first two aren't testable, but all ↵Howard Hinnant2013-09-121-1/+1
| | | | | | tests pass with them. I stumbled across them while experimenting with a std::move that checks its argument for non-const. The third corrects a test that is currently failing. llvm-svn: 190563
* Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant2013-08-221-2/+2
| | | | | | the unnecessary ones, and commented the ones that are there for non-obvious reasons such as to help things limp along in C++03 language mode. llvm-svn: 189039
* Nico Rieck: this patch series fixes visibility issues on Windows as ↵Howard Hinnant2013-08-121-13/+13
| | | | | | explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
OpenPOWER on IntegriCloud