summaryrefslogtreecommitdiffstats
path: root/libcxx/include/__tree
Commit message (Collapse)AuthorAgeFilesLines
* [libc++] Rework compressed pair constructors.Eric Fiselier2019-12-161-5/+5
| | | | | | | | | | | | This patch de-duplicates most compressed pair constructors to use the same code in C++11 and C++03. Part of doing that is deleting the "__second_tag()" and replacing it with a "__value_init_tag()" which has the same effect, but allows for the removal of the special "one-arg" first element constructor. This patch is intended to have no semantic change.
* [libc++] Cleanup and enable multiple warnings.Eric Fiselier2019-12-121-1/+4
| | | | | | | | | | Too many warnings are being disabled too quickly. Warnings are important to keeping libc++ correct. This patch re-enables two warnings: -Wconstant-evaluated and -Wdeprecated-copy. In future, all warnings disabled for the test suite should require an attached bug. The bug should state the plan for re-enabling that warning, or a strong case why it should remain disabled.
* Rename __is_foo_iterator traits to reflect their Cpp17 nature.Eric Fiselier2019-11-181-1/+1
| | | | | | | | | With the upcoming introduction of iterator concepts in ranges, the meaning of "__is_contiguous_iterator" changes drastically. Currently we intend it to mean "does it have this iterator category", but it could now also mean "does it meet the requirements of this concept", and these can be different.
* Fix memory leak in set and map.Eric Fiselier2019-07-111-118/+76
| | | | | | | | When assigning an initializer list into set/map, libc++ would leak memory if the initializer list contained equivalent keys because we failed to check if the insertion was successful. llvm-svn: 365840
* Avoid name conflict with kernel headersEric Fiselier2019-04-241-4/+4
| | | | llvm-svn: 359080
* [libc++] Make sure we don't eagerly diagnose non-const comparators for ↵Louis Dionne2019-04-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Apply D28248: 'Work around GCC PR37804'. Thanks to mdaniels for the patchMarshall Clow2019-01-231-0/+7
| | | | llvm-svn: 351993
* 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
* [libc++] Improve diagnostics for non-const comparators and hashers in ↵Louis Dionne2018-12-061-25/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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-7/+63
| | | | | | | | | | 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
* [NFC][libc++] Consistently use spaces to indentLouis Dionne2018-08-031-3/+3
| | | | | | rdar://problem/19988944 llvm-svn: 338933
* First half of C++17's splicing maps and setsErik Pilkington2018-08-011-6/+164
| | | | | | | | | | | | | 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-13/+6
| | | | | | | | | | | | 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
* SpellingJoerg Sonnenberger2017-08-181-2/+2
| | | | llvm-svn: 311156
* [Libc++] Use #pragma push_macro/pop_macro to better handle min/max on WindowsEric Fiselier2017-05-311-2/+6
| | | | | | | | | | | | | | | | Summary: This patch improves how libc++ handles min/max macros within the headers. Previously libc++ would undef them and emit a warning. This patch changes libc++ to use `#pragma push_macro` to save the macro before undefining it, and `#pragma pop_macro` to restore the macros and the end of the header. Reviewers: mclow.lists, bcraig, compnerd, EricWF Reviewed By: EricWF Subscribers: cfe-commits, krytarowski Differential Revision: https://reviews.llvm.org/D33080 llvm-svn: 304357
* Cleanup remaining _LIBCPP_HAS_NO_<c++11-feature> usages in container headersEric Fiselier2017-04-191-4/+4
| | | | llvm-svn: 300643
* Fix most failures caused by r300140Eric Fiselier2017-04-131-4/+4
| | | | | | | | | | | | | | | | | | | | | 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
* Undefine min/max in __treeEric Fiselier2017-02-041-0/+2
| | | | llvm-svn: 294099
* Diagnose non-const-callable hash functions and comparatorsEric Fiselier2017-01-131-8/+3
| | | | llvm-svn: 291969
* Add _LIBCPP_DIAGNOSE_WARNING and _LIBCPP_DIAGNOSE_ERROR macros.Eric Fiselier2017-01-131-1/+33
| | | | | | | | | | | | | | | | | | 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-0/+7
| | | | | | | | | | | | | | | | 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-19/+19
| | | | | | | | | | | | | 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
* Fix unused parameters and variablesEric Fiselier2016-12-231-2/+2
| | | | llvm-svn: 290459
* [libcxx] Fix max_size() across all containersEric Fiselier2016-11-231-1/+3
| | | | | | | | | | | | Summary: The `max_size()` method of containers should respect both the allocator's reported `max_size` and the range of the `difference_type`. This patch makes all containers choose the smallest of those two values. Reviewers: mclow.lists, EricWF Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D26885 llvm-svn: 287729
* Avoid embedded preprocessor directives in __treeDimitry Andric2016-08-271-5/+8
| | | | | | | | | | Similar to rL242623, move C++ version checks outside of _NOEXCEPT_() macro invocation argument lists, to avoid "embedding a directive within macro arguments has undefined behavior" warnings. Differential Revision: https://reviews.llvm.org/D23961 llvm-svn: 279926
* make the associative containers do the right thing for ↵Marshall Clow2016-08-171-1/+5
| | | | | | propogate_on_container_assignment. Fixes bug #29001. Tests are only for <map> right now - more complete tests will come when we revamp our allocator testing structure. llvm-svn: 279008
* Fix undefined behavior in __treeEric Fiselier2016-07-191-187/+257
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix static assert problem on gcc; remove XFAILs that I put in in r274250Marshall Clow2016-06-301-2/+2
| | | | llvm-svn: 274285
* Implement LWG#2436: 'Comparators for associative containers should always be ↵Marshall Clow2016-06-301-0/+2
| | | | | | CopyConstructible' llvm-svn: 274235
* Teach map/unordered_map how to optimize 'emplace(Key, T)'.Eric Fiselier2016-04-161-0/+21
| | | | | | | | | 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-151-4/+73
| | | | | | | | | | | | | | 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
* Teach __tree how to handle map's __value_typeEric Fiselier2016-03-311-230/+313
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-51/+46
| | | | | | | | | | | | | | | | | 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-58/+169
| | | | | | | | | | | | | | | | | | | | | | | 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/+51
| | | | | | braced-init syntax' llvm-svn: 256859
* Use __rebind_pointer to avoid #ifdef blockEric Fiselier2015-12-301-71/+15
| | | | 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
* Fix warnings in array and assoc containersEric Fiselier2015-07-181-4/+4
| | | | llvm-svn: 242629
* Implement the first part of N4258: 'Cleaning up noexcept in the Library'. ↵Marshall Clow2015-07-131-27/+14
| | | | | | This patch deals with swapping containers, and implements a more strict noexcept specification (a conforming extension) than the standard mandates. llvm-svn: 242056
* In many places, there was an #ifdef/#else block that selected one of two ↵Marshall Clow2015-04-071-7/+1
| | | | | | 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
* Fix another -Wunused-local-typedef warning in include/__tree.Dimitry Andric2015-03-091-1/+0
| | | | | | | | | The _Pp typedef in __tree<_Tp, _Compare, _Allocator>::__count_multi() isn't used anywhere, so adding _LIBCPP_UNUSED is unecessary. Differential Revision: http://reviews.llvm.org/D8140 llvm-svn: 231705
* Allow declaration of map and multimap iterator with incomplete mapped type. ↵Eric Fiselier2015-03-031-22/+38
| | | | | | Patch from eugenis llvm-svn: 231119
* Remove several unused forward declarations. Fixes PR22605.Marshall Clow2015-02-181-8/+0
| | | | llvm-svn: 229728
* Fix PR22366. When move-constructing an associative container and explicitly ↵Marshall Clow2015-01-281-3/+3
| | | | | | passing an allocator that compares different, we were not calling the destructor of the elements in the moved-from container. llvm-svn: 227359
* Remove node from a container before destroying it. Thanks to Alexander ↵Marshall Clow2014-04-111-1/+1
| | | | | | Potapenko for pointing this out. llvm-svn: 206024
* Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant2013-08-221-1/+1
| | | | | | 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-23/+23
| | | | | | explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
* N3644 tests for map/multimap/set/multiset. Drive-by NOEXCEPT for ↵Marshall Clow2013-08-081-2/+11
| | | | | | __tree_const_iterator constructor. Fix comment typos in other tests llvm-svn: 188019
* Implement full support for non-pointer types in custom allocators. This is ↵Howard Hinnant2013-06-191-51/+58
| | | | | | for the associative containers only. This work still needs to be done on the unordered and sequence containers. Fixes http://llvm.org/bugs/show_bug.cgi?id=15978 llvm-svn: 184358
* No functionality change at this time. I've split _LIBCPP_VISIBLE up into ↵Howard Hinnant2013-03-061-21/+21
| | | | | | two flags: _LIBCPP_TYPE_VIS and _LIBCPP_FUNC_VIS. This is in preparation for taking advantage of clang's new __type_visibility__ attribute. llvm-svn: 176593
OpenPOWER on IntegriCloud