aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT
AgeCommit message (Collapse)Author
2012-08-10Add some missing includes for the build against stdcxx.Joerg Sonnenberger
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161657 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-06Add support for the OpenBSD for Bitrig.Eric Christopher
Patch by David Hill. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161344 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-01Reference IntrusiveRefCntPtr in doxygen doc of RefCountedBase to get a link ↵Axel Naumann
to the pointer class documentation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161112 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-01Add range erase, element insert, and range insert methods toChandler Carruth
TinyPtrVector. With these, it is sufficiently functional for my more normal / pedestrian uses. I've not included some r-value reference stuff here because the value type for a TinyPtrVector is, necessarily, just a pointer. I've added tests that cover the basic behavior of these routines, but they aren't as comprehensive as I'd like. In particular, they don't really test the iterator semantics as thoroughly as they should. Maybe some brave soul will feel enterprising and flesh them out. ;] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161104 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-01Add basic in-bounds asserts to TinyPtrVector::erase.Chandler Carruth
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161103 91177308-0d34-0410-b5e6-96231b3b80d8
2012-08-01Fix shadowed variable warningNick Kledzik
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161097 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-31Implement copy and move assignment for TinyPtrVector. These try toChandler Carruth
re-use allocated vectors as much as possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161041 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-31Clean up trailing whitespace and unnecessary blank lines.Chandler Carruth
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161025 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-31Bring TinyPtrVector under test. Somehow we never picked up unit testsChandler Carruth
for this class. These tests exercise most of the basic properties, but the API for TinyPtrVector is very strange currently. My plan is to start fleshing out the API to match that of SmallVector, but I wanted a test for what is there first. Sadly, it doesn't look reasonable to just re-use the SmallVector tests, as this container can only ever store pointers, and much of the SmallVector testing is to get construction and destruction right. Just to get this basic test working, I had to add value_type to the interface. While here I found a subtle bug in the combination of 'erase', 'begin', and 'end'. Both 'begin' and 'end' wanted to use a null pointer to indicate the "end" iterator of an empty vector, regardless of whether there is actually a vector allocated or the pointer union is null. Everything else was fine with this except for erase. If you erase the last element of a vector after it has held more than one element, we return the end iterator of the underlying SmallVector which need not be a null pointer. Instead, simply use the pointer, and poniter + size() begin/end definitions in the tiny case, and delegate to the inner vector whenever it is present. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161024 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-30Move the SmallVector unit tests to be type-parameterized so that we canChandler Carruth
test more than a single instantiation of SmallVector. Add testing for 0, 1, 2, and 4 element sized "small" buffers. These appear to be essentially untested in the unit tests until now. Fix several tests to be robust in the face of a '0' small buffer. As a consequence of this size buffer, the growth patterns are actually observable in the test -- yes this means that many tests never caused a grow to occur before. For some tests I've merely added a reserve call to normalize behavior. For others, the growth is actually interesting, and so I captured the fact that growth would occur and adjusted the assertions to not assume how rapidly growth occured. Also update the specialization for a '0' small buffer length to have all the same interface points as the normal small vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161001 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-29APInt: Simplify code.Benjamin Kramer
No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160929 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27SmallVector: Crank up verbosity of asserts per Chandler's request.Benjamin Kramer
Also add assertions to validate the iterator in the insert method overloads. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160882 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-27SmallVector::erase: Assert that iterators are actually inside the vector.Benjamin Kramer
The rationale here is that it's hard to write loops containing vector erases and it only shows up if the vector contains non-trivial objects leading to crashes when forming them out of garbage memory. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160854 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Add operator== to APSInt. This will compare the signed bit before doingRichard Trieu
the comparison. This prevents large unsigned integers from being equal to signed negative integers of the same bit width. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160642 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-23Fix a typo (the the => the)Sylvestre Ledru
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160621 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-18Remove tabs.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160471 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-18Allow PointerIntPairs to be created from const void *.Jordan Rose
For a measure of safety, this conversion is only permitted if the stored pointer type can also be created from a const void *. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160456 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Fix broken ipo_ext_iterator constructors.Jakob Stoklund Olesen
These functions have obviously never been used before. They should be identical to the idf_ext_iterator counterparts. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160381 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Allow for customized graph edge pruning in PostOrderIterator.hJakob Stoklund Olesen
Make it possible to prune individual graph edges from a post-order traversal by specializing the po_iterator_storage template. Previously, it was only possible to prune full graph nodes. Edge pruning makes it possible to remove loop back-edges, for example. Also replace the existing DFSetTraits customization hook with a po_iterator_storage method for observing the post-order. DFSetTraits was only used by LoopIterator.h which now provides a po_iterator_storage specialization. Thanks to Sean and Chandler for reviewing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160366 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-15Move IsSameValue from clang's ASTImporter to be methods on theEric Christopher
APInt/APSInt classes. Part of rdar://11875995 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160223 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13Fixed few warnings.Galina Kistanova
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160192 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-08SmallVector: Make use of move semantics to speed up moving objects in ↵Benjamin Kramer
erase() and insert() git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159914 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-03Micro-optimize this function a bit. This shrinks the generated codeChandler Carruth
some, and allows the routine to be inlined into common callers. The various bits that hit this code in their hotpath seem slightly lower on the profile, but I can't really measure a performance improvement as everything seems to still be bottlenecked on likely cache misses. =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159648 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-30Avoid sign compare warning.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159481 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-20Remove 'static' from inline functions defined in header files.Chandler Carruth
There is a pretty staggering amount of this in LLVM's header files, this is not all of the instances I'm afraid. These include all of the functions that (in my build) are used by a non-static inline (or external) function. Specifically, these issues were caught by the new '-Winternal-linkage-in-inline' warning. I'll try to just clean up the remainder of the clearly redundant "static inline" cases on functions (not methods!) defined within headers if I can do so in a reliable way. There were even several cases of a missing 'inline' altogether, or my personal favorite "static bool inline". Go figure. ;] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158800 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-18Don't copy a potentially-uninitialized variable.David Blaikie
Based on review discussion of r158638 with Chandler Carruth, Tobias von Koch, and Duncan Sands and a -Wmaybe-uninitialized warning from GCC. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158685 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17Bring the return value of SmallVector::insert in line with std::vector::insert.Benjamin Kramer
It always returns the iterator for the first inserted element, or the passed in iterator if the inserted range was empty. Flesh out the unit test more and fix all the cases it uncovered so far. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158645 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17Remove SmallMap, and the several files that were used to implement it.Chandler Carruth
We have SmallDenseMap now that has more correct and predictable semantics, even though it is a more narrow abstraction. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158644 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17SmallVector: return a valid iterator for the rare case of inserting an empty ↵Benjamin Kramer
range into a SmallVector. Patch by Johannes Schaub! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158643 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17Add a unit test for 'swap', and fix a pile of bugs inChandler Carruth
SmallDenseMap::swap. First, make it parse cleanly. Yay for uninstantiated methods. Second, make the inline-buckets case work correctly. This is way trickier than it should be due to the uninitialized values in empty and tombstone buckets. Finally fix a few typos that caused construction/destruction mismatches in the counting unittest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158641 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17Add tests for *DenesMap for both key and value types' construction andChandler Carruth
destruction and fix a bug in SmallDenseMap they caught. This is kind of a poor-man's version of the testing that just adds the addresses to a set on construction and removes them on destruction. We check that double construction and double destruction don't occur. Amusingly enough, this is enough to catch a lot of SmallDenseMap issues because we spend a lot of time with fixed stable addresses in the inline buffer. The SmallDenseMap bug fix included makes grow() not double-destroy in some cases. It also fixes a FIXME there, the code was pretty crappy. We now don't have any wasted initialization, but we do move the entries in inline bucket array an extra time. It's probably a better tradeoff, and is much easier to get correct. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158639 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-17Introduce a SmallDenseMap container that re-uses the existing DenseMapChandler Carruth
implementation. This type includes an inline bucket array which is used initially. Once it is exceeded, an array of 64 buckets is allocated on the heap. The bucket count grows from there as needed. Some highlights of this implementation: - The inline buffer is very carefully aligned, and so supports types with alignment constraints. - It works hard to avoid aliasing issues. - Supports types with non-trivial constructors, destructors, copy constructions, etc. It works reasonably hard to minimize copies and unnecessary initialization. The most common initialization is to set keys to the empty key, and so that should be fast if at all possible. This class has a performance / space trade-off. It tries to optimize for relatively small maps, and so packs the inline bucket array densely into the object. It will be marginally slower than a normal DenseMap in a few use patterns, so it isn't appropriate everywhere. The unit tests for DenseMap have been generalized a bit to support running over different map implementations in addition to different key/value types. They've then been automatically extended to cover the new container through the magic of GoogleTest's typed tests. All of this is still a bit rough though. I'm going to be cleaning up some aspects of the implementation, documenting things better, and adding tests which include non-trivial types. As soon as I'm comfortable with the correctness, I plan to switch existing users of SmallMap over to this class as it is already more correct w.r.t. construction and destruction of objects iin the map. Thanks to Benjamin Kramer for all the reviews of this and the lead-up patches. That said, more review on this would really be appreciated. As I've noted a few times, I'm quite surprised how hard it is to get the semantics for a hashtable-based map container with a small buffer optimization correct. =] git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158638 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-16Merge the SmallBitVector and BitVector unit tests with gtest's typed test ↵Benjamin Kramer
magic and bring SmallBitVector up to date. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158600 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-16Lift the NumElements and NumTombstones members into the super classChandler Carruth
rather than the base class. Add a pile of boilerplate to indirect around this. This is pretty ugly, but it allows the super class to change the representation of these values, which will be key for doing a SmallDenseMap. Suggestions on better method structuring / naming are welcome, but keep in mind that SmallDenseMap won't have an 'unsigned' member to expose a reference to... =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158586 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-16Factor DenseMap into a base class that implements the hashtable logic,Chandler Carruth
and a derived class that provides the allocation and growth strategy. This is the first (and biggest) step toward building a SmallDenseMap that actually behaves exactly the same as DenseMap, and supports all the same types and interface points with the same semantics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158585 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-14SmallMap, FlatArrayMap::copyFromStepan Dyatkovskiy
Replaced memcpy with std::copy, since the first one may work improperly with non POD data. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158457 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-13Group the 'unsigned' members after the pointer to avoid 4 bytes ofChandler Carruth
padding on x86-64. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158421 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-09Hashing: Remove outdated comment. Support for reserved hash values was ↵Benjamin Kramer
removed in r151865. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158276 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-02Add move semantics to APInt.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157883 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-01Provide move semantics for (Small)BitVector.Benjamin Kramer
CodeGen makes a lot of BitVector copies. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157826 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-31IntrusiveRefCntPtr: Simplify operator= as suggested by Richard Smith.Benjamin Kramer
This way the constructors do all the hard work. No intended functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157773 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-29DenseMap's move assignment operator needs to return *thisDouglas Gregor
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157644 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-28add some helper methods to make the type more uniform.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157554 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27DenseMap: Use an early exit when there is nothing to do in DestroyAll().Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157550 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27IntrusiveRefCntPtr: Use the same pattern as the other operator= overloads ↵Benjamin Kramer
when using rvalue refs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157546 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27DenseMap: Provide a move ctor and move semantics for operator[] and ↵Benjamin Kramer
FindAndConstruct. The only missing part is insert(), which uses a pair of parameters and I haven't figured out how to convert it to rvalue references. It's now possible to use a DenseMap with std::unique_ptr values :) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157539 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27DenseMap: Factor destruction into a common helper method.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157538 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-27Move-enable IntrusiveRefCntPtr.Benjamin Kramer
These tend to be copied around a lot, moving it instead saves a ton of memory accesses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157535 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-24Remove the PTX back-end and all of its artifacts (triple, etc.)Justin Holewinski
This back-end was deprecated in favor of the NVPTX back-end. NV_CONTRIB git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157417 91177308-0d34-0410-b5e6-96231b3b80d8
2012-05-22fix the quotient returned by sdivrem() for the case when LHS is negative and ↵Nuno Lopes
RHS is positive based on a patch by Preston Briggs, with some modifications git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157231 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-08 16:31:32 +0000