summaryrefslogtreecommitdiffstats
path: root/libcxx/test/std/containers
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Fix compile error in test. Can't use `operator[]` for multimap.Marshall Clow2015-11-161-1/+1
| | | | llvm-svn: 253271
* More tests for LWG#2156Marshall Clow2015-11-164-0/+64
| | | | llvm-svn: 253257
* LWG#2156 loosened the requirements on unordered containers 'rehash' calls. ↵Marshall Clow2015-11-164-0/+48
| | | | | | Add tests to make sure we meet these requirements. Since we met the stricter ones, no code change needed to meet the looser ones. llvm-svn: 253223
* Make it possible to build a no-exceptions variant of libcxx.Asiri Rathnayake2015-11-1012-0/+12
| | | | | | | | | | | | Fixes a small omission in libcxx that prevents libcxx being built when -DLIBCXX_ENABLE_EXCEPTIONS=0 is specified. This patch adds XFAILS to all those tests that are currently failing on the new -fno-exceptions library variant. Follow-up patches will update the tests (progressively) to cope with the new library variant. Change-Id: I4b801bd8d8e4fe7193df9e55f39f1f393a8ba81a llvm-svn: 252598
* Suppress array initialization warnings in std::experimental::apply testsEric Fiselier2015-10-0116-23/+46
| | | | llvm-svn: 248987
* Recommit rL245802: Cleanup fancy pointer rebinding in list using ↵Eric Fiselier2015-08-231-0/+27
| | | | | | | | | | | | __rebind_pointer. Currently we need an #ifdef branch every time we use pointer traits to rebind a pointer because it is done differently in C++11 and C++03. This patch introduces the __rebind_pointer utility to clean this up. Also add a test that list and it's iterators can be instantiated with incomplete element types. llvm-svn: 245806
* implement more of N4258 - Cleaning up noexcept in the standard library. ↵Marshall Clow2015-08-182-0/+85
| | | | | | Specifically add new noexcept stuff to vector and string's move-assignment operations llvm-svn: 245330
* Fix a handful of tests that fail in C++03Eric Fiselier2015-07-281-1/+7
| | | | llvm-svn: 243392
* Fix warnings in unordered_mapEric Fiselier2015-07-1928-85/+39
| | | | llvm-svn: 242634
* Fix warnings in forwardlistEric Fiselier2015-07-193-6/+6
| | | | llvm-svn: 242633
* Fix warnings in deque testsEric Fiselier2015-07-1910-57/+24
| | | | llvm-svn: 242632
* Commit file missing from r242629Eric Fiselier2015-07-191-0/+8
| | | | llvm-svn: 242630
* Fix warnings in array and assoc containersEric Fiselier2015-07-1819-25/+90
| | | | llvm-svn: 242629
* Add missing instrumentation in vector::insert - Patch from Anna ZaksEric Fiselier2015-07-182-284/+0
| | | | | | This patch was reviewed as D10859. http://reviews.llvm.org/D10859 llvm-svn: 242617
* Move bits from N4258. Mark vector's move-constructor unconditionally ↵Marshall Clow2015-07-142-0/+10
| | | | | | noexcept in C++1z llvm-svn: 242148
* Implement the first part of N4258: 'Cleaning up noexcept in the Library'. ↵Marshall Clow2015-07-1313-12/+1017
| | | | | | 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-072-0/+393
| | | | llvm-svn: 241555
* Implement N4279 and LWG#2664 for <map>. Reviewed as ↵Marshall Clow2015-07-072-0/+381
| | | | | | 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-3049-1/+1716
| | | | | | 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
* Fix PR#23767. Add tests for iterator invalidation for ↵Marshall Clow2015-06-054-0/+246
| | | | | | deque::erase/pop_front/pop_back llvm-svn: 239196
* While applying N4258, I forgot about LWG#2455, which modified the ↵Marshall Clow2015-06-043-20/+1
| | | | | | modifications. Correct those - h/t: Howard llvm-svn: 239004
* More N4258 changes. This time vector's constructorsMarshall Clow2015-06-044-5/+48
| | | | llvm-svn: 238990
* Fix broken test I just addedMarshall Clow2015-05-261-3/+3
| | | | llvm-svn: 238234
* Add tests to ensure that string/vector/array have contiguous iterators - ↵Marshall Clow2015-05-262-0/+83
| | | | | | which they did. Mark N4284 as complete llvm-svn: 238233
* Fix test that was failing on C++03 b/c it was using initializer listsMarshall Clow2015-05-161-2/+2
| | | | llvm-svn: 237527
* Fix for LWG Issue 2059: C++0x ambiguity problem with map::eraseMarshall Clow2015-05-108-0/+180
| | | | llvm-svn: 236950
* Remove some debugging printout lines. No functionality change.Marshall Clow2015-05-101-2/+0
| | | | llvm-svn: 236949
* Make the new tests better; make sure that we're testing the case where no ↵Marshall Clow2015-03-302-4/+11
| | | | | | reallocation has to happen llvm-svn: 233641
* While testing Erik's code coverage scripts, I found a hole in the test suite ↵Marshall Clow2015-03-302-16/+74
| | | | | | - vector::assign where a reallocation was not required had no tests. Add some llvm-svn: 233557
* [libcxx] Move tuple_size and tuple_element overloads for pair and array out ↵Eric Fiselier2015-03-172-18/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | of !defined(_LIBCPP_HAS_NO_VARIADICS) block. Summary: There is no reason to guard `tuple_size`, `tuple_element` and `get<I>(...)` for pair and array inside of `<__tuple>` so that they are only available when we have variadic templates. This requires there be redundant declarations and definitions. It also makes it easy to get things wrong. For example the following code should compile (and does in c++11). ``` #define _LIBCPP_HAS_NO_VARIADICS #include <array> int main() { static_assert((std::tuple_size<std::array<int, 10> volatile>::value == 10), ""); } ``` This patch lifts the non-variadic parts of `tuple_size`, `tuple_types`, and `get<I>(...)` to the top of `<__tuple>` where they don't require variadic templates. This patch also removes `<__tuple_03>` because there is no longer a need for it. Reviewers: danalbert, K-ballo, mclow.lists Reviewed By: mclow.lists Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D7774 llvm-svn: 232492
* Use generic feature name for sanitizers that replace new and deleteEric Fiselier2015-03-103-3/+3
| | | | llvm-svn: 231841
* [libcxx] Fix __RAII_IncreaseAnnotator for increases >= 1Eric Fiselier2015-03-101-0/+34
| | | | | | | | | | | | | | Summary: Fix suggested by @mclow.lists on D8109. Store the size of the un-poisoned vector upon construction instead of calculating it later. Reviewers: titus, mclow.lists, kcc, EricWF Reviewed By: EricWF Subscribers: mclow.lists, cfe-commits Differential Revision: http://reviews.llvm.org/D8172 llvm-svn: 231729
* Move test to use correct suffixEric Fiselier2015-03-091-0/+0
| | | | llvm-svn: 231704
* Fix an exception-safety bug in <deque>. Reference: PR#22650. Not closing the ↵Marshall Clow2015-03-092-1/+41
| | | | | | bug because there's more work to do here llvm-svn: 231672
OpenPOWER on IntegriCloud