summaryrefslogtreecommitdiffstats
path: root/libcxx/test/std/containers
Commit message (Collapse)AuthorAgeFilesLines
...
* Move remaining _LIBCPP_VERSION tests into test/libcxxEric Fiselier2016-06-2211-220/+0
| | | | llvm-svn: 273367
* Improve portability of vector tests. Patch from STL@microsoft.comEric Fiselier2016-06-151-1/+1
| | | | llvm-svn: 272745
* Replace __cplusplus comparisons and dialect __has_feature checks with ↵Eric Fiselier2016-06-14635-768/+716
| | | | | | | | | TEST_STD_VER. This is a huge cleanup that helps make the libc++ test suite more portable. Patch from STL@microsoft.com. Thanks STL! llvm-svn: 272716
* Found a couple bugs in the test suite. No functionality change.Marshall Clow2016-06-142-0/+4
| | | | llvm-svn: 272679
* Fix vector<bool> tests that were using ints. Patch from STL@microsoft.comEric Fiselier2016-06-145-17/+17
| | | | llvm-svn: 272620
* Make the comparison objects that we pass in for various tests look more like ↵Marshall Clow2016-06-0940-28/+48
| | | | | | actual comparison objects. No functional change. llvm-svn: 272288
* Avoid Shadowing warnings in the associative containers tests. Thanks to STL ↵Marshall Clow2016-06-074-4/+8
| | | | | | for the patch. llvm-svn: 272018
* [libcxx] Fix c++98 test failures.Asiri Rathnayake2016-06-0312-13/+13
| | | | | | | | | Adds XFAIL/UNSUPPORTED lit tags as appropriate. Gets a clean test run for -std=c++98 on Fedora 20. NFC. llvm-svn: 271741
* Remove trailing whitespace in test suite. Approved by Marshall Clow.Eric Fiselier2016-06-01126-543/+543
| | | | llvm-svn: 271435
* Mark LWG issue 2537 as completeEric Fiselier2016-05-312-4/+6
| | | | llvm-svn: 271241
* Mark LWG issue #2585 as completeEric Fiselier2016-05-311-1/+20
| | | | llvm-svn: 271240
* [libcxx] Improve tests to use the UNSUPPORTED lit directiveAsiri Rathnayake2016-05-283-6/+3
| | | | | | | | | | | | | | | | | | | Quite a few libcxx tests seem to follow the format: #if _LIBCPP_STD_VER > X // Do test. #else // Empty test. #endif We should instead use the UNSUPPORTED lit directive to exclude the test on earlier C++ standards. This gives us a more accurate number of test passes for those standards and avoids unnecessary conflicts with other lit directives on the same tests. Reviewers: bcraig, ericwf, mclow.lists Differential revision: http://reviews.llvm.org/D20730 llvm-svn: 271108
* Fix or move various non-standard tests.Eric Fiselier2016-04-2916-756/+0
| | | | | | | | | | | | This patch does the following: * Remove <__config> includes from some container tests. * Guards uses of std::launch::any in async tests because it's an extension. * Move "test/std/extensions" to "test/libcxx/extensions" * Moves various non-standard tests including those in "sequences/vector", "std/localization" and "utilities/meta". llvm-svn: 267981
* Guard libc++ specific c.__invariants() tests in LIBCPP_ASSERT macrosEric Fiselier2016-04-2816-61/+73
| | | | llvm-svn: 267947
* Remove names of unreferenced parameters. Patch from STL@microsoft.comEric Fiselier2016-04-281-1/+1
| | | | llvm-svn: 267852
* Add braces, move braces, and rename variables to avoid shadowing. Patch from ↵Eric Fiselier2016-04-283-2/+6
| | | | | | STL@microsoft.com llvm-svn: 267844
* Fix = that should have been == in test. Thanks to STL@microsoft for the catchMarshall Clow2016-04-271-1/+1
| | | | llvm-svn: 267654
* Fix some non-standard parts of our test suite. Reported by STLEric Fiselier2016-04-2215-3798/+8
| | | | llvm-svn: 267131
* Fix C++03 build breakageEric Fiselier2016-04-221-2/+9
| | | | llvm-svn: 267090
* Complete LWG issue #2016. Allocators must be nothrow swappableEric Fiselier2016-04-2213-34/+39
| | | | llvm-svn: 267085
* Add is_swappable/is_nothrow_swappable traitsEric Fiselier2016-04-212-0/+50
| | | | llvm-svn: 267079
* Fix LWG issue 2345 - Add insert(value_type&&)Eric Fiselier2016-04-1818-533/+672
| | | | llvm-svn: 266585
* Teach map/unordered_map how to optimize 'emplace(Key, T)'.Eric Fiselier2016-04-163-4/+132
| | | | | | | | | In cases where emplace is called with two arguments and the first one matches the key_type we can Key to check for duplicates before allocating. This patch expands on work done by dexonsmith@apple.com. llvm-svn: 266498
* Extract key to avoid preemptive mallocs in insert/emplace in associative ↵Eric Fiselier2016-04-1512-996/+849
| | | | | | | | | | | | | | containers Summary: This patch applies Duncan's work on __hash_table to __tree. Reviewers: mclow.lists, dexonsmith Subscribers: dexonsmith, cfe-commits Differential Revision: http://reviews.llvm.org/D18637 llvm-svn: 266491
* Added a noexcept testMarshall Clow2016-04-071-0/+6
| | | | llvm-svn: 265674
* Fix bug #27260 - add missing swap(reference, reference) to vector<bool>.Marshall Clow2016-04-071-0/+31
| | | | llvm-svn: 265672
* Fix LWG issue 2469 - Use piecewise construction in map::operator[].Eric Fiselier2016-03-312-4/+68
| | | | | | | | | | | | | | | 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-314-0/+479
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Update container_test_types.h and cleanup the related testsEric Fiselier2016-03-316-24/+13
| | | | llvm-svn: 264985
* unord: Extract key to avoid preemptive mallocs in insert/emplaceDuncan P. N. Exon Smith2016-03-172-0/+184
| | | | | | | | | | | | | | | | | | | | | | | | | | unordered_set::emplace and unordered_map::emplace construct a node, then try to insert it. If insertion fails, the node gets deleted. To avoid this unnecessary malloc traffic, check to see if the argument to emplace has the appropriate key_type. If so, we can use that key directly and delay the malloc until we're sure we're inserting something new. Test updates by Eric Fiselier, who rewrote the old allocation tests to include the new cases. There are two orthogonal future directions: 1. Apply the same optimization to set and map. 2. Extend the optimization to when the argument is not key_type, but can be converted to it without side effects. Ideally, we could do this whenever key_type is trivially destructible and the argument is trivially convertible to key_type, but in practise the relevant type traits "blow up sometimes". At least, we should catch a few simple cases (such as when both are primitive types). llvm-svn: 263746
* Add failing tests that I forgot to add to the last commitMarshall Clow2016-03-143-0/+90
| | | | llvm-svn: 263451
* Implement LWG#2566: Requirements on the first template parameter of ↵Marshall Clow2016-03-143-21/+21
| | | | | | container adaptors llvm-svn: 263450
* Add some more tests for the containers type requirementsMarshall Clow2016-03-096-19/+112
| | | | llvm-svn: 263029
* non-member swap for array was mistakenly taking const ref params. Fixed and ↵Marshall Clow2016-03-071-1/+28
| | | | | | added test. Thanks to Ben Craig for the catch llvm-svn: 262866
* Add additional tests to ensure that we DTRT with short lists. This is ↵Marshall Clow2016-02-231-0/+14
| | | | | | LWG#2590, but there are no code changes, just additional tests llvm-svn: 261648
* Cleanup node-type handling in the associative containers.Eric Fiselier2016-02-205-0/+247
| | | | | | | | | | | | | | | | | | | | | | | 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
* Fix LWG issue 2469 - Use piecewise construction in unordered_map::operator[].Eric Fiselier2016-02-112-12/+52
| | | | | | | | | | | | | 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-112-52/+12
| | | | llvm-svn: 260556
* Teach __hash_table how to handle unordered_map's __hash_value_type.Eric Fiselier2016-02-112-12/+52
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-114-0/+500
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Recommit r260012 - Cleanup node-type handling in the unordered containers.Eric Fiselier2016-02-105-0/+304
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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-085-304/+0
| | | | llvm-svn: 260172
* Cleanup node-type handling in the unordered containersEric Fiselier2016-02-075-0/+304
| | | | | | | | | | | | | | | | | | | | | | | | | 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
* [libcxx] Fix undefined behavior in forward_listEric Fiselier2016-01-271-0/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch is similar to the <list> fix but it has a few differences. This patch doesn't use a `__link_pointer` typedef because we don't need to change the linked list pointers because `forward_list` never stores a `__forward_begin_node` in the linked list itself. The issue with `forward_list` is that the iterators store pointers to `__forward_list_node` and not `__forward_begin_node`. This is incorrect because `before_begin()` and `cbefore_begin()` return iterators that point to a `__forward_begin_node`. This means we incorrectly downcast the `__forward_begin_node` pointer to a `__node_pointer`. This downcast itself is sometimes UB but it cannot be safely removed until ABI v2. The more common cause of UB is when we deference the downcast pointer. (for example `__ptr_->__next_`). This can be fixed without an ABI break by upcasting `__ptr_` before accessing it. The fix is as follows: 1. Introduce a `__iter_node_pointer` typedef that works similar to `__link_pointer` in the last patch. In ABI v2 it is always a typedef for `__begin_node_pointer`. 2. Change the `__before_begin()` method to return the correct pointer type (`__begin_node_pointer`), Previously it incorrectly downcasted the `__forward_begin_node` to a `__node_pointer` so it could be used to constructor the iterator types. 3. Change `__forward_list_iterator` and `__forward_list_const_iterator` in the following way: 1. Change `__node_pointer __ptr_;` member to have the `__iter_node_pointer` type instead. 2. Add additional private constructors that accept `__begin_node_pointer` in addition to `__node_pointer` and then correctly cast them to the stored `__iter_node_pointer` type. 3. Add `__get_begin()` and `__get_node_unchecked()` accessor methods that correctly cast `__ptr_` to the expected pointer type. `__get_begin()` is always safe to use and should be preferred. `__get_node_unchecked()` can only be used on a deferencible iterator. 4. Replace direct access to `__forward_list_iterator::__ptr_` with the safe accessor methods. Reviewers: mclow.lists, EricWF Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D15836 llvm-svn: 258888
* Add a bunch of missing includes in the test suite to make it more portable. ↵Marshall Clow2016-01-1254-114/+168
| | | | | | Fixes bugs #26120 and #26121. Thanks to Jonathan Wakely for the reports and the patches. llvm-svn: 257474
* Add explicit include directives; the file was getting implicitly included ↵Marshall Clow2016-01-054-0/+4
| | | | | | already. NFC llvm-svn: 256864
* First half of LWG#2354: 'Unnecessary copying when inserting into maps with ↵Marshall Clow2016-01-054-4/+130
| | | | | | braced-init syntax' llvm-svn: 256859
* [libcxx] LWG2485: get() should be overloaded for const tuple&&. Patch from ↵Eric Fiselier2015-12-181-0/+51
| | | | | | | K-Ballo. Review: http://reviews.llvm.org/D14839 llvm-svn: 255941
* Add static_assert to set/multiset/map/multimap/forward_list/deque that the ↵Marshall Clow2015-11-2612-0/+216
| | | | | | 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
* Remove undefined behavior from tests; specifically, ensure that the value ↵Marshall Clow2015-11-2414-49/+59
| | | | | | type of the allocators match the value type of the containers llvm-svn: 254030
OpenPOWER on IntegriCloud