summaryrefslogtreecommitdiffstats
path: root/libcxx/include/unordered_map
Commit message (Collapse)AuthorAgeFilesLines
* [libc++] Fix typos causing compilation errors when _LIBCPP_DEBUG_LEVEL >= 2Oleg Ranevskyy2016-09-261-2/+2
| | | | | | | | | | | | Summary: This patch fixes a couple of typos that cause compilation errors when application includes <unordered_map> and enables the libc++'s debugging capabilities. Reviewers: EricWF Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24883 llvm-svn: 282446
* Support allocators with explicit conversion constructors. Fixes bug #29000Marshall Clow2016-08-171-12/+12
| | | | 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
* Cleanup: move visibility/linkage attributes to the first declaration.Evgeniy Stepanov2016-04-221-10/+20
| | | | | | http://reviews.llvm.org/D15404 llvm-svn: 267093
* Mark LWG issue 2469 as done. Also simplify try_emplace and insert_or_assign ↵Eric Fiselier2016-04-181-63/+31
| | | | | | implementations in unordered_map llvm-svn: 266591
* Fix LWG issue 2345 - Add insert(value_type&&)Eric Fiselier2016-04-181-67/+82
| | | | llvm-svn: 266585
* Fix LWG issue 2469 - Use piecewise construction in unordered_map::operator[].Eric Fiselier2016-02-111-30/+21
| | | | | | | | | | | | | 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-111-21/+30
| | | | llvm-svn: 260556
* Teach __hash_table how to handle unordered_map's __hash_value_type.Eric Fiselier2016-02-111-30/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-111-208/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Remove changes that snuck in within r260431Eric Fiselier2016-02-101-9/+0
| | | | llvm-svn: 260443
* Recommit r260012 - Cleanup node-type handling in the unordered containers.Eric Fiselier2016-02-101-20/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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-081-27/+20
| | | | llvm-svn: 260172
* Cleanup node-type handling in the unordered containersEric Fiselier2016-02-071-20/+27
| | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert "unordered_map: Reuse insert logic in emplace when possible, NFC"Duncan P. N. Exon Smith2016-01-231-27/+3
| | | | | | | | This reverts commit r258575. EricWF sent me an email (no link since it was off-list) requesting to review this pre-commit instead of post-commit. llvm-svn: 258625
* unordered_map: Reuse insert logic in emplace when possible, NFCDuncan P. N. Exon Smith2016-01-221-3/+27
| | | | | | | | | | | | | | | | An upcoming commit will add an optimization to insert() that avoids unnecessary mallocs when we can safely extract the key type. This commit shares code between emplace() and insert(): - if emplace() is given a single argument, and - value_type is constructible from that argument so that we have a single code path for the two. I also updated the debug version of emplace_hint() to defer to emplace(), like the non-debug version does. In both cases, there should be NFC here. llvm-svn: 258575
* Use __rebind_pointer to avoid #ifdef blockEric Fiselier2015-12-301-16/+4
| | | | 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
* Implement the first part of N4258: 'Cleaning up noexcept in the Library'. ↵Marshall Clow2015-07-131-0/+44
| | | | | | 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-071-0/+131
| | | | llvm-svn: 241555
* [libcxx] Fix detection of __is_final.Eric Fiselier2015-06-131-8/+4
| | | | | | | | | | | | | | 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
* Replace two naked references of 'std::' with the macro '_VSTD::'. No ↵Marshall Clow2015-05-061-2/+2
| | | | | | functionality change. llvm-svn: 236593
* 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
* NFC. Move definition of _LIBCPP_ASSERT into __debug header and remove ↵Eric Fiselier2014-08-101-0/+2
| | | | | | | | | | | | | | | | | | external include guards. Things done in this patch: 1. Make __debug include __config since it uses macros from it. 2. The current method of defining _LIBCPP_ASSERT is prone to redefinitions. Move the null _LIBCPP_ASSERT definition into the __debug header to prevent this. 3. Remove external <__debug> include gaurds. <__debug> guards almost all of its contents internally. There is no reason to be doing it externally. This patch should not change any functionality. llvm-svn: 215332
* Fix for PR18735 - self-assignment for map/multimap gives incorrect results ↵Marshall Clow2014-02-081-12/+16
| | | | | | in C++03 llvm-svn: 201021
* SCARY/N2913 iterator support between the multi and non-multi versions of the ↵Howard Hinnant2013-09-301-86/+67
| | | | | | 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
* LWG Issue 2210 (Part #6): unordered_map and unordered_multimapMarshall Clow2013-09-121-0/+80
| | | | llvm-svn: 190576
* 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
* Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant2013-08-221-2/+2
| | | | | | 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-13/+13
| | | | | | explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
* Debug mode for unordered_multimap. Some mods were done for unordered_map as ↵Howard Hinnant2013-07-301-0/+40
| | | | | | well to keep all the tests passing. However unordered_map is at the very least still missing tests, if not functionality (if it isn't tested, it probably isn't working). llvm-svn: 187446
* Debug mode for unordered_set. I believe this to be fairly complete forHoward Hinnant2013-07-231-4/+120
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unordered_set, however it is not complete yet for unordered_multiset, unordered_map or unordered_multimap. There has been a lot of work done for these other three containers, however that work was done just to keep all of the tests passing. You can try this out with -D_LIBCPP_DEBUG2. You will have to link to a libc++.dylib that has been compiled with src/debug.cpp. So far, vector (but not vector<bool>), list, and unordered_set are treated. I hope to get the other three unordered containers up fairly quickly now that unordered_set is done. The flag _LIBCPP_DEBUG2 will eventually be changed to _LIBCPP_DEBUG, but not today. This is my second effort at getting debug mode going for libc++, and I'm not quite yet ready to throw all of the work under the first attempt away. The basic design is that all of the debug information is kept in a central database, instead of in the containers. This has been done as an attempt to have debug mode and non-debug mode be ABI compatible with each other. There are some circumstances where if you construct a container in an environment without debug mode and pass it into debug mode, the checking will get confused and let you know with a readable error message. Passing containers the other way: from debug mode out to a non-debugging mode container should be 100% safe (at least that is the goal). llvm-svn: 186991
* Remove implicit conversion from __value_type to value_type in ↵Howard Hinnant2013-07-051-30/+18
| | | | | | [unordered_][multi]map. This fixes http://llvm.org/bugs/show_bug.cgi?id=16549 llvm-svn: 185711
* Removed extension in [unordered_][multi]map which allowed one to emplace ↵Howard Hinnant2013-07-041-72/+15
| | | | | | using just an argument for the key, as opposed to using piecewise_construct. However a bug report exposed that this created an unfortunate ambiguity. People who are currently using the extension will be notified the next time they compile, and will have to change to using piecewise_construct. There are no ABI issues with the removal of this extension. This fixes http://llvm.org/bugs/show_bug.cgi?id=16542 llvm-svn: 185666
* Simplify comparators of [unordered_][multi]map. This fixes ↵Howard Hinnant2013-07-041-46/+0
| | | | | | http://llvm.org/bugs/show_bug.cgi?id=16538 llvm-svn: 185665
* Implement full support for non-pointer types in custom allocators. This is ↵Howard Hinnant2013-06-221-20/+132
| | | | | | for the unordered containers only. This work still needs to be done on the sequence containers. llvm-svn: 184635
* No functionality change at this time. I've split _LIBCPP_VISIBLE up into ↵Howard Hinnant2013-03-061-13/+13
| | | | | | 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
* The rules for emplace in map, multimap, unordered_map and unordered_multimap ↵Howard Hinnant2012-05-251-126/+143
| | | | | | changed a while back and I'm just now updating to these new rules. In a nutshell, you've got to know you're emplacing to a pair and use one of pair's constructors. I made one extension: If you want to emplace the key and default construct the mapped_type, you can just emplace(key), as opposed to emplace(piecewise_construct, forward_as_tuple(key), forward_as_tuple()). llvm-svn: 157503
* As an extension, support incomplete types in the unordered containers to ↵Howard Hinnant2011-12-121-26/+70
| | | | | | match what we already do in the associative containers. llvm-svn: 146376
* Fix http://llvm.org/bugs/show_bug.cgi?id=11461. Credit Alberto Ganesh Barbati.Howard Hinnant2011-12-111-2/+10
| | | | llvm-svn: 146345
* Further macro protection by replacing _[A-Z] with _[A-Z]pHoward Hinnant2011-11-291-25/+25
| | | | llvm-svn: 145410
* Windows support by Ruben Van Boxem.Howard Hinnant2011-10-171-0/+2
| | | | llvm-svn: 142235
* Fixed PR10574: http://llvm.org/bugs/show_bug.cgi?id=10574Howard Hinnant2011-08-121-0/+28
| | | | llvm-svn: 137522
* http://llvm.org/bugs/show_bug.cgi?id=10455Howard Hinnant2011-07-231-2/+2
| | | | llvm-svn: 135854
* Correct for new rules regarding implicitly deleted special members. ↵Howard Hinnant2011-07-011-2/+12
| | | | | | http://llvm.org/bugs/show_bug.cgi?id=10191 llvm-svn: 134248
* _STD -> _VSTD to avoid macro clash on windowsHoward Hinnant2011-06-301-45/+45
| | | | llvm-svn: 134190
* More fixes: One of my fixes to type_traits earlier today was incorrect, so ↵Howard Hinnant2011-06-191-23/+23
| | | | | | that is reverted. Recently clang appears to have tightened up its definition of is_convertible and that has caused some failures in [unordered_][multi]map. I've switched to using is_constructible to restablish the desired functionality in [unordered_][multi]map. Specifically, inserting rvalues of move-only types for the keys. llvm-svn: 133402
* noexcept for <unordered_map>.Howard Hinnant2011-06-041-96/+173
| | | | llvm-svn: 132646
* Qualify calls to addressof with std::. Bug 9106Howard Hinnant2011-02-021-10/+10
| | | | llvm-svn: 124726
OpenPOWER on IntegriCloud