summaryrefslogtreecommitdiffstats
path: root/libcxx/include/__hash_table
Commit message (Collapse)AuthorAgeFilesLines
...
* Enable and fix warnings during the build.Eric Fiselier2015-07-181-4/+8
| | | | | | | | | | | | | | | | | Although CMake adds warning flags, they are ignored in the libc++ headers because the headers '#pragma system header' themselves. This patch disables the system header pragma when building libc++ and fixes the warnings that arose. The warnings fixed were: 1. <memory> - anonymous structs are a GNU extension 2. <functional> - anonymous structs are a GNU extension. 3. <__hash_table> - Embedded preprocessor directives have undefined behavior. 4. <string> - Definition is missing noexcept from declaration. 5. <__std_stream> - Unused variable. llvm-svn: 242623
* Implement the first part of N4258: 'Cleaning up noexcept in the Library'. ↵Marshall Clow2015-07-131-46/+18
| | | | | | This patch deals with swapping containers, and implements a more strict noexcept specification (a conforming extension) than the standard mandates. llvm-svn: 242056
* Fix PR12999 - unordered_set::insert calls operator new when no insert occursEric Fiselier2015-06-131-2/+39
| | | | | | | | | | | | | | | | | | | | | | | Summary: when `unordered_set::insert(value_type&&)` was called it would be treated like `unordered_set::emplace(Args&&)` and it would allocate and construct a node before trying to insert it. This caused unnecessary allocations when the value was already in the set. This patch adds an overload to `__hash_table::__insert_unique` that specifically handles `value_type&&` more link `value_type const &`. This patch also adds a single unified insert function for values into `__hash_table` called `__insert_unique_value` that handles the cases for `__insert_unique(value_type&&)` and `__insert_unique(value_type const &)`. This patch fixes PR12999: http://llvm.org/bugs/show_bug.cgi?id=12999. Reviewers: mclow.lists, titus, danalbert Reviewed By: danalbert Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D7570 llvm-svn: 239666
* In many places, there was an #ifdef/#else block that selected one of two ↵Marshall Clow2015-04-071-14/+2
| | | | | | 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
* Remove several unused forward declarations. Fixes PR22605.Marshall Clow2015-02-181-2/+0
| | | | llvm-svn: 229728
* Handle function name conflicts in _LIBCPP_MSVCRT modeSaleem Abdulrasool2015-02-131-0/+1
| | | | | | | | | | Visual Studio's SAL extension uses a macro named __deallocate. This macro is used pervasively, and gets included through various different ways. This conflicts with the similarly named interfaces in libc++. Introduce a undef header similar to __undef_min_max to handle this. This fixes a number of errors due to the macro replacing the function name. llvm-svn: 229162
* Rename pow2 functions in __hash_table to reflect that they are hash specificEric Fiselier2015-02-021-8/+8
| | | | llvm-svn: 227866
* NFC. Move definition of _LIBCPP_ASSERT into __debug header and remove ↵Eric Fiselier2014-08-101-5/+1
| | | | | | | | | | | | | | | | | | 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
* Rename _LIBCPP_DEBUG2 to _LIBCPP_DEBUG.Howard Hinnant2013-08-231-1/+1
| | | | llvm-svn: 189140
* Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant2013-08-221-3/+3
| | | | | | 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-21/+21
| | | | | | explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
* N3644 support for <unordered_set> and <unordered_map>Marshall Clow2013-08-071-0/+6
| | | | llvm-svn: 187915
* debug mode for unordered_map. Also picked up a missing check and test in ↵Howard Hinnant2013-08-021-0/+5
| | | | | | unordered_multimap. This wraps up debug mode for the unordered containers. llvm-svn: 187659
* Ok, 3 major changes for debug mode in one commit:Howard Hinnant2013-08-021-16/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1. I had been detecting and trapping iterator == and \!= among iterators in different containers as an error. But the trapping itself is actually an error. Consider: #include <iostream> #include <vector> #include <algorithm> template <class C> void display(const C& c) { std::cout << "{"; bool first = true; for (const auto& x : c) { if (\!first) std::cout << ", "; first = false; std::cout << x; } std::cout << "}\n"; } int main() { typedef std::vector<int> V; V v1 = {1, 3, 5}; V v2 = {2, 4, 6}; display(v1); display(v2); V::iterator i = std::find(v1.begin(), v1.end(), 1); V::iterator j = std::find(v2.begin(), v2.end(), 2); if (*i == *j) i = j; // perfectly legal // ... if (i \!= j) // the only way to check v2.push_back(*i); display(v1); display(v2); } It is legal to assign an iterator from one container to another of the same type. This is required to work. One might want to test whether or not such an assignment had been made. The way one performs such a check is using the iterator's ==, \!= operator. This is a logical and necessary function and does not constitute an error. 2. I had a header circular dependence bug when _LIBCPP_DEBUG2 is defined. This caused a problem in several of the libc++ tests. Fixed. 3. There is a serious problem when _LIBCPP_DEBUG2=1 at the moment in that std::basic_string is inoperable. std::basic_string uses __wrap_iterator to implement its iterators. __wrap_iterator has been rigged up in debug mode to support vector. But string hasn't been rigged up yet. This means that one gets false positives when using std::string in debug mode. I've upped std::string's priority in www/debug_mode.html. llvm-svn: 187636
* Debug mode for unordered_multiset. The exercise spotted a few places I had ↵Howard Hinnant2013-07-291-2/+35
| | | | | | | | | | | | | | missed on unordered_set, so I picked those up as well. There are actually two debug modes: 1. -D_LIBCPP_DEBUG2 or -D_LIBCPP_DEBUG2=1 This is a relatively expensive debug mode, but very thorough. This is normally what you want to debug with, but may turn O(1) operations into O(N) operations. 2. -D_LIBCPP_DEBUG2=0 This is "debug lite." Only preconditions that can be checked with O(1) expense are checked. For example range checking on an indexing operation. But not iterator validity. llvm-svn: 187369
* Debug mode for unordered_set. I believe this to be fairly complete forHoward Hinnant2013-07-231-32/+500
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Implement full support for non-pointer types in custom allocators. This is ↵Howard Hinnant2013-06-221-23/+33
| | | | | | 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-20/+20
| | | | | | 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
* Dimitry Andric: many visibility fixes. Howard: Much appreciated. Can you ↵Howard Hinnant2012-09-141-3/+3
| | | | | | send me a patch to CREDITS.TXT? llvm-svn: 163862
* This commit establishes a new bucket_count policy in the unordered ↵Howard Hinnant2012-07-061-39/+64
| | | | | | containers: The policy now allows a power-of-2 number of buckets to be requested (and that request honored) by the client. And if the number of buckets is set to a power of 2, then the constraint of the hash to the number of buckets uses & instead of %. If the client does not specify a number of buckets, then the policy remains unchanged: a prime number of buckets is selected. The growth policy is that the number of buckets is roughly doubled when needed. While growing, either the prime, or the power-of-2 strategy will be preserved. There is a small run time cost for putting in this switch. For very cheap hash functions, e.g. identity for int, the cost can be as high as 18%. However with more typical use cases, e.g. strings, the cost is in the noise level. I've measured cases with very cheap hash functions (int) that using a power-of-2 number of buckets can make look up about twice as fast. However I've also noted that a power-of-2 number of buckets is more susceptible to accidental catastrophic collisions. Though I've also noted that accidental catastrophic collisions are also possible when using a prime number of buckets (but seems far less likely). In short, this patch adds an extra tuning knob for those clients trying to get the last bit of performance squeezed out of their hash containers. Casual users of the hash containers will not notice the introduction of this tuning knob. Those clients who swear by power-of-2 hash containers can now opt-in to that strategy. Clients who prefer a prime number of buckets can continue as they have. llvm-svn: 159836
* As an extension, support incomplete types in the unordered containers to ↵Howard Hinnant2011-12-121-1/+1
| | | | | | match what we already do in the associative containers. llvm-svn: 146376
* Quash a whole bunch of warningsHoward Hinnant2011-12-011-2/+2
| | | | llvm-svn: 145624
* Further macro protection by replacing _[A-Z] with _[A-Z]pHoward Hinnant2011-11-291-32/+32
| | | | llvm-svn: 145410
* Add protection from min/max macrosHoward Hinnant2011-11-291-0/+2
| | | | llvm-svn: 145407
* Windows support by Ruben Van Boxem.Howard Hinnant2011-10-171-0/+2
| | | | llvm-svn: 142235
* Fixed PR10507 (http://llvm.org/bugs/show_bug.cgi?id=10507)Howard Hinnant2011-07-311-3/+4
| | | | llvm-svn: 136595
* Revert r136546, which was submitted without review.Chandler Carruth2011-07-301-1/+0
| | | | | | | | | Original change: Destruct elements of hash tables when removing individual entries from the hash_table. I think this is the correct solution to PR10507, but I'm not sure since this is a little bit cargo-culted. Howard, please review. llvm-svn: 136576
* Destruct elements of hash tables when removing individual entries fromAlexis Hunt2011-07-301-0/+1
| | | | | | | the hash_table. I think this is the correct solution to PR10507, but I'm not sure since this is a little bit cargo-culted. Howard, please review. llvm-svn: 136546
* Fix uninitialized loop counter. http://llvm.org/bugs/show_bug.cgi?id=10278Howard Hinnant2011-07-051-1/+1
| | | | llvm-svn: 134405
* _STD -> _VSTD to avoid macro clash on windowsHoward Hinnant2011-06-301-52/+52
| | | | llvm-svn: 134190
* Provide names for template and function parameters in forward declarations. ↵Howard Hinnant2011-06-141-8/+9
| | | | | | The purpose is to aid automated documentation tools. llvm-svn: 133008
* noexcept for <unordered_map>.Howard Hinnant2011-06-041-56/+151
| | | | llvm-svn: 132646
* Fixed two problems found by Chris Jefferson: Made operator>> for char ↵Howard Hinnant2011-02-271-2/+2
| | | | | | consistent with gcc. Opened an LWG issue on this one. 2) Renamed some private typedefs which are causing boost grief. llvm-svn: 126576
* Qualify calls to addressof with std::. Bug 9106Howard Hinnant2011-02-021-18/+18
| | | | llvm-svn: 124726
* license changeHoward Hinnant2010-11-161-2/+2
| | | | llvm-svn: 119395
* visibility-decoration.Howard Hinnant2010-09-211-69/+119
| | | | llvm-svn: 114451
* Fix whitespaceHoward Hinnant2010-09-041-1/+1
| | | | llvm-svn: 113089
* Changed __config to react to all of clang's currently documented has_feature ↵Howard Hinnant2010-09-041-26/+34
| | | | | | flags, and renamed _LIBCPP_MOVE to _LIBCPP_HAS_NO_RVALUE_REFERENCES to be more consistent with the rest of the libc++'s flags, and with clang's nomenclature. llvm-svn: 113086
* Fixing whitespace problemsHoward Hinnant2010-08-221-23/+23
| | | | llvm-svn: 111750
* Wiped out some non-ascii characters that snuck into the copyright.Howard Hinnant2010-05-111-1/+1
| | | | llvm-svn: 103516
* libcxx initial importHoward Hinnant2010-05-111-0/+1761
llvm-svn: 103490
OpenPOWER on IntegriCloud