summaryrefslogtreecommitdiffstats
path: root/libcxx/test/std/containers
Commit message (Collapse)AuthorAgeFilesLines
* Implement P0084r2. Changing emplace return types.Eric Fiselier2016-07-219-80/+104
| | | | llvm-svn: 276230
* Fix undefined behavior in __treeEric Fiselier2016-07-191-0/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch attempts to fix the undefined behavior in __tree by changing the node pointer types used throughout. The pointer types are changed for raw pointers in the current ABI and for fancy pointers in ABI V2 (since the fancy pointer types may not be ABI compatible). The UB in `__tree` arises because tree downcasts the embedded end node and then deferences that pointer. Currently there are 3 node types in __tree. * `__tree_end_node` which contains the `__left_` pointer. This node is embedded within the container. * `__tree_node_base` which contains `__right_`, `__parent_` and `__is_black`. This node is used throughout the tree rebalancing algorithms. * `__tree_node` which contains `__value_`. Currently `__tree` stores the start of the tree, `__begin_node_`, as a pointer to a `__tree_node`. Additionally the iterators store their position as a pointer to a `__tree_node`. In both of these cases the pointee can be the end node. This is fixed by changing them to store `__tree_end_node` pointers instead. To make this change I introduced an `__iter_pointer` typedef which is defined to be a pointer to either `__tree_end_node` in the new ABI or `__tree_node` in the current one. Both `__tree::__begin_node_` and iterator pointers are now stored as `__iter_pointers`. The other situation where `__tree_end_node` is stored as the wrong type is in `__tree_node_base::__parent_`. Currently `__left_`, `__right_`, and `__parent_` are all `__tree_node_base` pointers. Since the end node will only be stored in `__parent_` the fix is to change `__parent_` to be a pointer to `__tree_end_node`. To make this change I introduced a `__parent_pointer` typedef which is defined to be a pointer to either `__tree_end_node` in the new ABI or `__tree_node_base` in the current one. Note that in the new ABI `__iter_pointer` and `__parent_pointer` are the same type (but not in the old one). The confusion between these two types is unfortunate but it was the best solution I could come up with that maintains the ABI. The typedef changes force a ton of explicit type casts to correct pointer types and to make current code compatible with both the old and new pointer typedefs. This is the bulk of the change and it's really messy. Unfortunately I don't know how to avoid it. Please let me know what you think. Reviewers: howard.hinnant, mclow.lists Subscribers: howard.hinnant, bbannier, cfe-commits Differential Revision: https://reviews.llvm.org/D20786 llvm-svn: 276003
* Add includes in test. Patch from STL@microsoft.comEric Fiselier2016-07-181-0/+4
| | | | llvm-svn: 275751
* Always use the allocator to construct/destruct elements of a deque/vector. ↵Marshall Clow2016-07-112-0/+21
| | | | | | Fixes PR#28412. Thanks to Jonathan Wakely for the report. llvm-svn: 275105
* Fix static assert problem on gcc; remove XFAILs that I put in in r274250Marshall Clow2016-06-306-12/+0
| | | | llvm-svn: 274285
* Fix C++03 build.Eric Fiselier2016-06-304-1/+13
| | | | llvm-svn: 274274
* Temporarily XFAIL the incomplete type tests for GCC while I figure out why ↵Marshall Clow2016-06-306-0/+12
| | | | | | adding a static_assert in r274235 broken them llvm-svn: 274250
* Implement LWG#2684: 'priority_queue lacking comparator typedef'. We already ↵Marshall Clow2016-06-301-0/+4
| | | | | | did this, just added tests llvm-svn: 274243
* Implement LWG#2596: 'vector::data() should use addressof'Marshall Clow2016-06-302-3/+41
| | | | llvm-svn: 274241
* Implement LWG#2436: 'Comparators for associative containers should always be ↵Marshall Clow2016-06-3012-0/+348
| | | | | | CopyConstructible' llvm-svn: 274235
* Make std::array typedef tests more portable.Eric Fiselier2016-06-301-4/+25
| | | | llvm-svn: 274210
* Fix unary_function inheritance assumption. Patch from STL@microsoft.comEric Fiselier2016-06-301-2/+2
| | | | llvm-svn: 274205
* Make default_noexcept.pass.cpp container tests more portable. Patch from ↵Eric Fiselier2016-06-2615-27/+42
| | | | | | STL@microsoft.com llvm-svn: 273823
* Finish converting list _LIBCPP_DEBUG tests.Eric Fiselier2016-06-225-81/+7
| | | | llvm-svn: 273394
* Cleanup _LIBCPP_DEBUG tests in std::list. More to come.Eric Fiselier2016-06-2211-515/+7
| | | | llvm-svn: 273393
* Cleanup [list.modifiers] tests.Eric Fiselier2016-06-229-566/+53
| | | | llvm-svn: 273371
* 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
OpenPOWER on IntegriCloud