summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Support/SmallPtrSet.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Sync the __builtin_expects for our 3 quadratically probed hash table ↵Benjamin Kramer2015-02-231-9/+10
| | | | | | | | | | | | | | | | | | implementations. This assumes that a) finding the bucket containing the value is LIKELY b) finding an empty bucket is LIKELY c) growing the table is UNLIKELY I also switched the a) and b) cases for SmallPtrSet as we seem to use the set mostly more for insertion than for checking existence. In a simple benchmark consisting of 2^21 insertions of 2^20 unique pointers into a DenseMap or SmallPtrSet a few percent speedup on average, but nothing statistically significant. llvm-svn: 230232
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-7/+9
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* Fix an off by 1 bug that prevented SmallPtrSet from using all of its 'small' ↵Craig Topper2014-08-201-6/+5
| | | | | | capacity. Then fix the early return in the move constructor that prevented 'small' moves from clearing the NumElements in the moved from object. The directed test missed this because it was always testing large moves due to the off by 1 bug. llvm-svn: 216044
* [C++11] Make use of 'nullptr' in the Support library.Craig Topper2014-04-071-1/+1
| | | | llvm-svn: 205697
* [C++11] Remove the R-value reference #if usage from the ADT and SupportChandler Carruth2014-03-011-4/+0
| | | | | | libraries. It is now always 1 in LLVM builds. llvm-svn: 202580
* Rename the non-templated base class of SmallPtrSet toChandler Carruth2014-02-031-13/+15
| | | | | | | | | | | 'SmallPtrSetImplBase'. This more closely matches the organization of SmallVector and should allow introducing a SmallPtrSetImpl which serves the same purpose as SmallVectorImpl: isolating the element type from the particular small size chosen. This in turn allows a lot of simplification of APIs by not coding them against a specific small size which is rarely needed. llvm-svn: 200687
* Lift self-copy protection up to the header file and add self-moveChandler Carruth2013-11-261-2/+3
| | | | | | | | | | | | protection to the same layer. This is in line with Howard's advice on how best to handle self-move assignment as he explained on SO[1]. It also ensures that implementing swap with move assignment continues to work in the case of self-swap. [1]: http://stackoverflow.com/questions/9322174/move-assignment-operator-and-if-this-rhs llvm-svn: 195705
* Fix a self-memcpy which only breaks under Valgrind's memcpyChandler Carruth2013-11-261-0/+3
| | | | | | | implementation. Silliness, but it'll be a trivial performance optimization. This should clear up a failure on the vg_leak bot. llvm-svn: 195704
* Make the moved-from SmallPtrSet be a valid, empty, small-state object.Chandler Carruth2013-11-201-1/+13
| | | | | | | | | | | Enhance the tests to actually require moves in C++11 mode, in addition to testing the moved-from state. Further enhance the tests to cover copy-assignment into a moved-from object and moving a large-state object. (Note that we can't really test small-state vs. large-state as that isn't an observable property of the API really.) This should finish addressing review on r195239. llvm-svn: 195261
* Give SmallPtrSet move semantics when we have R-value references.Chandler Carruth2013-11-201-0/+44
| | | | | | | | | | | | Somehow, this ADT got missed which is moderately terrifying considering the efficiency of move for it. The code to implement move semantics for it is pretty horrible currently but was written to reasonably closely match the rest of the code. Unittests that cover both copying and moving (at a basic level) added. llvm-svn: 195239
* Fixing a possible memory leak from a failing realloc() call.Aaron Ballman2013-11-181-2/+7
| | | | llvm-svn: 195018
* SmallVector and SmallPtrSet allocations now power-of-two aligned.Jean-Luc Duprat2013-03-291-16/+8
| | | | | | This time tested on both OSX and Linux. llvm-svn: 178377
* Revert "Fix allocations of SmallVector and SmallPtrSet so they are more ↵Rafael Espindola2013-03-291-8/+16
| | | | | | | | | | | | | | | | | prone to" This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61. It broke the bots: /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:150: PushPopTest /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:118: Failure Value of: v[i].getValue() Actual: 0 Expected: value Which is: 2 llvm-svn: 178334
* Fix allocations of SmallVector and SmallPtrSet so they are more prone toJean-Luc Duprat2013-03-291-16/+8
| | | | | | being power-of-two sized. llvm-svn: 178332
* SmallPtrSet: Reuse DenseMapInfo's pointer hash function instead of inventing ↵Benjamin Kramer2012-04-181-1/+2
| | | | | | | | | | a bad one ourselves. DenseMap's hash function uses slightly more entropy and reduces hash collisions significantly. I also experimented with Hashing.h, but it didn't gave a lot of improvement while being much more expensive to compute. llvm-svn: 154996
* Copy the right amount of elements.Benjamin Kramer2012-03-071-3/+5
| | | | llvm-svn: 152254
* SmallPtrSet: Copy all the elements when swapping, not just numelements.Benjamin Kramer2012-03-071-5/+4
| | | | | | | This fixes a build failure in webkit. Copying all elements shouldn't be necessary, I'll look out for a better fix soon. llvm-svn: 152252
* SmallPtrSet: Provide a more efficient implementation of swap than the ↵Benjamin Kramer2012-03-061-0/+50
| | | | | | | | | default triple-copy std::swap. This currently assumes that both sets have the same SmallSize to keep the implementation simple, a limitation that can be lifted if someone cares. llvm-svn: 152143
* Prevent infinite growth of SmallPtrSet instances.Jakob Stoklund Olesen2011-03-301-6/+9
| | | | | | | | Rehash but don't grow when full of tombstones. Patch by José Fonseca! llvm-svn: 128566
* Rather than giving SmallPtrSetImpl a member field SmallArray which is magicallyDuncan Sands2010-06-301-3/+6
| | | | | | | | | | | | | | | | replaced by a bigger array in SmallPtrSet (by overridding it), instead just use a pointer to the start of the storage, and have SmallPtrSet pass in the value to use. This has the disadvantage that SmallPtrSet becomes bigger by one pointer. It has the advantage that it no longer uses tricky C++ rules, and is clearly correct while I'm not sure the previous version was. This was inspired by g++-4.6 pointing out that SmallPtrSetImpl was writing off the end of SmallArray, which it was. Since SmallArray is replaced with a bigger array in SmallPtrSet, the write was still to valid memory. But it was writing off the end of the declared array type - sounds kind of dubious to me, like it sounded dubious to g++-4.6. Maybe g++-4.6 is wrong and this construct is perfectly valid and correctly compiled by all compilers, but I think it is better to avoid the whole can of worms by avoiding this construct. llvm-svn: 107285
* Fix several const-correctness issues, resolving some -Wcast-qual warnings.Dan Gohman2008-08-051-2/+2
| | | | llvm-svn: 54349
* Remove attribution from file headers, per discussion on llvmdev.Chris Lattner2007-12-291-2/+2
| | | | llvm-svn: 45418
* make smallptrset more const and type correct, which caught a fewChris Lattner2007-11-061-2/+2
| | | | | | minor bugs. llvm-svn: 43782
* Properly use const qualifiersAnton Korobeynikov2007-08-151-1/+1
| | | | llvm-svn: 41111
* When clearing a SmallPtrSet, if the set had a huge capacity, but theChris Lattner2007-08-051-0/+18
| | | | | | | | | | contents of the set were small, deallocate and shrink the set. This avoids having us to memset as much data, significantly speeding up some pathological cases. For example, this speeds up the verifier from 0.3899s to 0.0763 (5.1x) on the testcase from PR1432 in a release build. llvm-svn: 40837
* Allow SmallPtrSet to hold pointers to const data.Owen Anderson2007-07-271-20/+20
| | | | llvm-svn: 40556
* Make the copy constructor of SmallPtrSet much faster.Owen Anderson2007-07-241-22/+12
| | | | llvm-svn: 40474
* Remember to free the heap allocated array if we're not going to use it.Owen Anderson2007-07-191-2/+4
| | | | llvm-svn: 40043
* Fix an issue where assignments that caused a SmallPtrSet to become non-smallOwen Anderson2007-07-181-4/+8
| | | | | | | would result in calling realloc() on a null pointer. Instead, if we encounter this situation, make a normal call to malloc(). llvm-svn: 40014
* Unbreak the build by putting calls to free into the implementation file andReid Spencer2007-07-171-0/+7
| | | | | | having that implementation file #include <cstdlib>. llvm-svn: 39952
* Use realloc() to (potentially) resize the contents of SmallPtrSet in place.Owen Anderson2007-07-161-10/+9
| | | | llvm-svn: 39926
* Make the assignment operator for SmallPtrSet much faster for normal cases.Owen Anderson2007-07-091-36/+21
| | | | llvm-svn: 38474
* Make the assignment operator for SmallPtrSet return a reference, and fix a ↵Owen Anderson2007-07-091-1/+1
| | | | | | | | | | long-standing bug in the copy ctor while I'm at it. Thanks to Chris Lattner for help with this patch. llvm-svn: 38470
* Fix an error in the assignment operator that was causing an infinite loop in ↵Owen Anderson2007-07-091-3/+11
| | | | | | | | GVNPRE.cpp. Patch by Chis Lattner. llvm-svn: 38467
* implement operator= for smallptrsetChris Lattner2007-07-091-0/+36
| | | | llvm-svn: 38460
* Fix a bug in SmallPtrSet that was causing GVNPRE to enter an infinite loop.Owen Anderson2007-06-221-1/+1
| | | | llvm-svn: 37697
* Two changes:Chris Lattner2007-06-211-4/+5
| | | | | | | | | 1. Make SmallPtrSet::erase faster in the small case by replacing a memmove with a pointer copy. 2. Fix a bug where the null terminator at the end of the array in the small case was not copied llvm-svn: 37696
* Fix PR1329.Jeff Cohen2007-04-141-0/+28
| | | | llvm-svn: 36016
* do not let the table fill up with tombstones.Chris Lattner2007-02-071-1/+5
| | | | llvm-svn: 33973
* Fix a bug in smallptrset::erase: in the small case, return true if theChris Lattner2007-02-051-1/+1
| | | | | | element was in the set. llvm-svn: 33931
* implement SmallPtrSet::eraseChris Lattner2007-01-271-0/+27
| | | | llvm-svn: 33581
* add a noteChris Lattner2007-01-271-1/+2
| | | | llvm-svn: 33578
* Add a new SmallSet ADT specialized for pointers.Chris Lattner2007-01-271-0/+113
llvm-svn: 33577
OpenPOWER on IntegriCloud