summaryrefslogtreecommitdiffstats
path: root/libcxx/include/map
Commit message (Collapse)AuthorAgeFilesLines
* [libc++] Use _EnableIf instead of std::enable_if in deduction guides for map ↵Louis Dionne2019-07-191-12/+12
| | | | | | and set llvm-svn: 366594
* Add contains method to associative containers. This patch implements ↵Zoe Carver2019-07-161-2/+14
| | | | | | P0458R2, adding contains to map, multimap, unordered_map, unordered_multimap, set, multiset, unordered_set, and unordered_multiset. llvm-svn: 366170
* [libc++] Take 2: Implement CTAD for map and multimapLouis Dionne2019-06-201-4/+57
| | | | | | | | | | | This is a re-application of r362986 (which was reverted in r363688) with fixes for the issue that caused it to be reverted. Thanks to Arthur O'Dwyer for the patch. Differential Revision: https://reviews.llvm.org/D58587 llvm-svn: 363968
* [libc++] Revert the addition of map/multimap CTADLouis Dionne2019-06-181-55/+2
| | | | | | | | | | | | | This was found to be broken on Clang trunk. This is a revert of the following commits (the subsequent commits added XFAILs to the tests that were missing from the original submission): r362986: Implement deduction guides for map/multimap. r363014: Add some XFAILs r363097: Add more XFAILs r363197: Add even more XFAILs llvm-svn: 363688
* Implement deduction guides for map/multimap. Reviewed as ↵Marshall Clow2019-06-101-2/+55
| | | | | | https://reviews.llvm.org/D58587. Thanks to Quuxplusone for the submission. llvm-svn: 362986
* [libc++] Make sure we don't eagerly diagnose non-const comparators for ↵Louis Dionne2019-04-111-2/+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/+22
| | | | | | 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-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [libcxx] Fix usage of _C2, which is a "nasty macro" in some environmentsLouis Dionne2018-11-011-16/+16
| | | | | | The problem was pointed out in https://reviews.llvm.org/D48896#inline-475775. llvm-svn: 345834
* Second half of C++17's splicing maps and setsErik Pilkington2018-10-311-0/+92
| | | | | | | | | | 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
* Fix Bug 38644: multimap::clear() missing exception specifier. Add noexcept ↵Marshall Clow2018-08-221-1/+1
| | | | | | tests for all the containers that have clear(). llvm-svn: 340385
* First half of C++17's splicing maps and setsErik Pilkington2018-08-011-0/+83
| | | | | | | | | | | | | 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-34/+85
| | | | | | | | | | | | 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
* Use multi-key tree search for {map, set}::{count, equal_range}Eric Fiselier2018-02-101-3/+3
| | | | | | | | | | | | | | | | | | | | | | | Patch from ngolovliov@gmail.com Reviewed as: https://reviews.llvm.org/D42344 As described in llvm.org/PR30959, the current implementation of std::{map, key}::{count, equal_range} in libcxx is non-conforming. Quoting the C++14 standard [associative.reqmts]p3 > The phrase “equivalence of keys” means the equivalence relation imposed by > the comparison and not the operator== on keys. That is, two keys k1 and k2 are > considered to be equivalent if for the comparison object comp, > comp(k1, k2) == false && comp(k2, k1) == false. In the same section, the requirements table states the following: > a.equal_range(k) equivalent to make_pair(a.lower_bound(k), a.upper_bound(k)) > a.count(k) returns the number of elements with key equivalent to k The behaviour of libstdc++ seems to conform to the standard here. llvm-svn: 324799
* 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> macros in std::map and std::multimapEric Fiselier2017-04-181-58/+37
| | | | llvm-svn: 300600
* Fix most failures caused by r300140Eric Fiselier2017-04-131-2/+2
| | | | | | | | | | | | | | | | | | | | | r300140 introduced a bunch of failures by changing the internal interface provided by __compressed_pair. This patch fixes all of the failures caused by the new interface by changing the existing code to use it. In addition to those changes this patch also fixes two separate issues causing test failures: 1) Fix the member swap definition for __map_value_compare. Previously the swap was incorrectly configured to swap the comparator as const. 2) Fix an assertion failure in futures.task.members/ctor_func_alloc.pass.cpp that incorrectly expected a move to take place when a single copy is sufficient. There is one remaining failure regarding make_shared. I'll commit a fix for that shortly. llvm-svn: 300148
* Add _LIBCPP_DIAGNOSE_WARNING and _LIBCPP_DIAGNOSE_ERROR macros.Eric Fiselier2017-01-131-3/+1
| | | | | | | | | | | | | | | | | | Clang recently added a `diagnose_if(cond, msg, type)` attribute which can be used to generate diagnostics when `cond` is a constant expression that evaluates to true. Otherwise no attribute has no effect. This patch adds _LIBCPP_DIAGNOSE_ERROR/WARNING macros which use this new attribute. Additionally this patch implements a diagnostic message when a non-const-callable comparator is given to a container. Note: For now the warning version of the diagnostic is useless within libc++ since warning diagnostics are suppressed by the system header pragma. I'm going to work on fixing this. llvm-svn: 291961
* [libcxx] Fix PR31402: map::__find_equal_key has undefined behavior.Eric Fiselier2017-01-051-68/+13
| | | | | | | | | | | | | | | | Summary: This patch fixes llvm.org/PR31402 by replacing `map::__find_equal_key` with `__tree::__find_equal`, which has already addressed the same undefined behavior. Unfortunately I haven't been able to write a test case which causes the UBSAN diagnostic mentioned in the bug report. I can write tests which exercise the UB but for some reason they do not cause UBSAN to fail. Any help writing a test case would be appreciated. Reviewers: mclow.lists, vsk, EricWF Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D28131 llvm-svn: 291087
* [NFC] Rename _LIBCPP_TYPE_VIS_ONLY to _LIBCPP_TEMPLATE_VISEric Fiselier2017-01-041-12/+12
| | | | | | | | | | | | | 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
* Support allocators with explicit conversion constructors. Fixes bug #29000Marshall Clow2016-08-171-14/+14
| | | | 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
* Add is_swappable/is_nothrow_swappable traitsEric Fiselier2016-04-211-2/+2
| | | | llvm-svn: 267079
* Fix LWG issue 2345 - Add insert(value_type&&)Eric Fiselier2016-04-181-15/+9
| | | | llvm-svn: 266585
* Fix LWG issue 2469 - Use piecewise construction in map::operator[].Eric Fiselier2016-03-311-67/+40
| | | | | | | | | | | | | | | 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'. This patch also switches try_emplace over to __tree.__emplace_unique_key_args. llvm-svn: 264989
* Teach __tree how to handle map's __value_typeEric Fiselier2016-03-311-226/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch is fairly large and contains a number of changes. The changes all work towards allowing __tree to properly handle __value_type esspecially when inserting into the __tree. I chose not to break this change into smaller patches because it wouldn't be possible to write meaningful standard-compliant tests for each patch. It is very similar to r260513 "[libcxx] Teach __hash_table how to handle unordered_map's __hash_value_type". Changes in <map> * Remove __value_type's constructors because it should never be constructed directly. * Make map::emplace and multimap::emplace forward to __tree and remove the old definitions * Remove "__construct_node" map and multimap member functions. Almost all of the construction is done within __tree. * Fix map's move constructor to access "__value_type.__nc" directly and pass this object to __tree::insert. Changes in <__tree> * Add traits to detect, handle, and unwrap, map's "__value_type". * Convert methods taking "value_type" to take "__container_value_type" instead. Previously these methods caused unwanted implicit conversions from "std::pair<Key, Value>" to "__value_type<Key, Value>". * Delete __tree_node and __tree_node_base's constructors and assignment operators. The node types should never be constructed because the "__value_" member of __tree_node must be constructed directly by the allocator. * Make the __tree_node_destructor class and "__construct_node" methods unwrap "__node_value_type" into "__container_value_type" before invoking the allocator. The user's allocator can only be used to construct and destroy the container's value_type. Passing it map's "__value_type" was incorrect. * Cleanup the "__insert" and "__emplace" methods. Have __insert forward to an __emplace function wherever possible to reduce code duplication. __insert_unique(value_type const&) and __insert_unique(value_type&&) forward to __emplace_unique_key_args. These functions will not allocate a new node if the value is already in the tree. * Change the __find* functions to take the "key_type" directly instead of passing in "value_type" and unwrapping the key later. This change allows the find functions to be used without having to construct a "value_type" first. This allows for a number of optimizations. * Teach __move_assign and __assign_multi methods to unwrap map's __value_type. llvm-svn: 264986
* Remove all usages of "const" node pointer typedefs in the assoc containers.Eric Fiselier2016-02-201-59/+20
| | | | | | | | | | | | | | | | | The "const" pointer typedefs such as "__node_const_pointer" and "__node_base_const_pointer" are identical to their non-const pointer types. This patch changes all usages of "const" pointer type names to their respective non-const typedef. Since "fancy pointers to const" cannot be converted back to a non-const pointer type according to the allocator requirements it is important that we never actually use "const" pointers. Furthermore since "__node_const_pointer" and "__node_pointer" already name the same type, it's very confusing to use both names. Especially when defining const/non-const overloads for member functions. llvm-svn: 261419
* Cleanup node-type handling in the associative containers.Eric Fiselier2016-02-201-19/+13
| | | | | | | | | | | | | | | | | | | | | | | This patch is very similar to r260431. This patch is the first in a series of patches that's meant to better support map. 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 __tree about this special value_type. This patch creates a "__tree_node_types" traits class that contains all of the typedefs needed by the associative containers and their iterators. These typedefs include ones for each node type and node pointer type, as well as special typedefs for "map"'s value type. Although the associative containers already supported incomplete types, this patch makes it official by adding tests. This patch will be followed up shortly with various cleanups within __tree and fixes for various map bugs and problems. llvm-svn: 261416
* First half of LWG#2354: 'Unnecessary copying when inserting into maps with ↵Marshall Clow2016-01-051-0/+24
| | | | | | braced-init syntax' llvm-svn: 256859
* Use __rebind_pointer to avoid #ifdef blockEric Fiselier2015-12-301-14/+4
| | | | llvm-svn: 256654
* Add static_assert to set/multiset/map/multimap/forward_list/deque that the ↵Marshall Clow2015-11-261-0/+6
| | | | | | allocator's value_type match the container's value_type. vector/unordered/list/string already do this. Add tests for all the containers to verify this. llvm-svn: 254119
* 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-9/+27
| | | | | | This patch deals with swapping containers, and implements a more strict noexcept specification (a conforming extension) than the standard mandates. llvm-svn: 242056
* Implement N4279 and LWG#2664 for <map>. Reviewed as ↵Marshall Clow2015-07-071-0/+131
| | | | | | http://reviews.llvm.org/D10669 llvm-svn: 241539
* Add tests for LWG#2299. While doing so, I noticed that the tests we have for ↵Marshall Clow2015-06-301-2/+2
| | | | | | the transparent comparators don't actually call them. Fix those tests, too. Now one of them is failing, due to a missing const in <map>. Add that (twice). Next step is to do the same for <unordered_map> llvm-svn: 241091
* [libcxx] Fix detection of __is_final.Eric Fiselier2015-06-131-4/+3
| | | | | | | | | | | | | | 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
* 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
* Allow declaration of map and multimap iterator with incomplete mapped type. ↵Eric Fiselier2015-03-031-9/+20
| | | | | | Patch from eugenis llvm-svn: 231119
* Fix bug 20740 - std::set/std::map don't support heterogeneous lookup for ↵Marshall Clow2014-08-241-2/+14
| | | | | | count(). Thanks to Jim Porter for the bug report llvm-svn: 216353
* Remove some unnecessary noexcept conditions. Thanks to Richard Smith for the ↵Marshall Clow2014-04-161-2/+0
| | | | | | catch. llvm-svn: 206424
* Fix bug I introduced (enabling implicit conversions from compare function to ↵Marshall Clow2014-03-101-2/+18
| | | | | | map) in r202994. Thanks to Sebastian Redl for the catch. llvm-svn: 203443
* Implement LWG 2193. Default constructors for standard library containers are ↵Marshall Clow2014-03-051-2/+2
| | | | | | explicit. Note that libc++ already did this for string/deque/forward_list/list/vector and the unordered containers; implement it for set/multiset/map/multimap. Add tests for all the containers. Two drive-by fixes as well: add a missing explicit in <deque>, and remove a tab that snuck into a container test. This issue is also LLVM bug 15724, and resolves it. llvm-svn: 202994
* Fix for PR18735 - self-assignment for map/multimap gives incorrect results ↵Marshall Clow2014-02-081-8/+12
| | | | | | in C++03 llvm-svn: 201021
* SCARY/N2913 iterator support between the multi and non-multi versions of the ↵Howard Hinnant2013-09-301-85/+71
| | | | | | 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
* 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
* LWG Issue #2210 Part 5 - map/multimap; no, really - the last one was ↵Marshall Clow2013-09-111-1/+37
| | | | | | set/multiset. THIS is map/multimap llvm-svn: 190474
OpenPOWER on IntegriCloud