Skip to content
  1. Jun 28, 2012
  2. Jun 26, 2012
  3. Jun 24, 2012
  4. Jun 22, 2012
  5. Jun 21, 2012
  6. Jun 20, 2012
  7. Jun 19, 2012
    • Chandler Carruth's avatar
      Fix PR13148, an inf-loop in StringMap. · 198422a4
      Chandler Carruth authored
      StringMap suffered from the same bug as DenseMap: when you explicitly
      construct it with a small number of buckets, you can arrange for the
      tombstone-based growth path to be followed when the number of buckets
      was less than '8'. In that case, even with a full map, it would compare
      '0' as not less than '0', and refuse to grow the table, leading to
      inf-loops trying to find an empty bucket on the next insertion. The fix
      is very simple: use '<=' as the comparison. The same fix was applied to
      DenseMap as well during its recent refactoring.
      
      Thanks to Alex Bolz for the great report and test case. =]
      
      llvm-svn: 158725
      198422a4
    • Chandler Carruth's avatar
      Remove some superfluous SCOPED_TRACEs from this unit test. · fc3856d9
      Chandler Carruth authored
      GoogleTest already prints errors with all the information about which
      test case contained the error.
      
      llvm-svn: 158724
      fc3856d9
  8. Jun 17, 2012
    • Benjamin Kramer's avatar
    • Benjamin Kramer's avatar
      Add missing unittest files to the cmake build. · 6bc197e4
      Benjamin Kramer authored
      llvm-svn: 158647
      6bc197e4
    • Benjamin Kramer's avatar
      Remove SmallMap unittests, unbreaking the build. · ae7f7937
      Benjamin Kramer authored
      I don't know how useful these are for SmallDenseMap, I'll leave that decision to Chandler.
      
      llvm-svn: 158646
      ae7f7937
    • Benjamin Kramer's avatar
      Bring the return value of SmallVector::insert in line with std::vector::insert. · 23a9c3e0
      Benjamin Kramer authored
      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.
      
      llvm-svn: 158645
      23a9c3e0
    • Benjamin Kramer's avatar
      SmallVector: return a valid iterator for the rare case of inserting an empty... · 371b9b0e
      Benjamin Kramer authored
      SmallVector: return a valid iterator for the rare case of inserting an empty range into a SmallVector.
      
      Patch by Johannes Schaub!
      
      llvm-svn: 158643
      371b9b0e
    • Chandler Carruth's avatar
      Add a unit test for 'swap', and fix a pile of bugs in · 4de807a5
      Chandler Carruth authored
      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.
      
      llvm-svn: 158641
      4de807a5
    • Chandler Carruth's avatar
      Disable a particular assertion on MSVC... I'm deeply disturbed by its · d599a8c4
      Chandler Carruth authored
      implementation of the class layout for the V8 type.
      
      llvm-svn: 158640
      d599a8c4
    • Chandler Carruth's avatar
      Add tests for *DenesMap for both key and value types' construction and · a1be842f
      Chandler Carruth authored
      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.
      
      llvm-svn: 158639
      a1be842f
    • Chandler Carruth's avatar
      Introduce a SmallDenseMap container that re-uses the existing DenseMap · 20dd838a
      Chandler Carruth authored
      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. =]
      
      llvm-svn: 158638
      20dd838a
    • Chandler Carruth's avatar
      Add some somewhat exhaustive tests of sizeof properties of this horrible · a4d40753
      Chandler Carruth authored
      construct just for my sanity.
      
      llvm-svn: 158637
      a4d40753
  9. Jun 16, 2012
    • Benjamin Kramer's avatar
      Update CMake build. · aa1e8f3a
      Benjamin Kramer authored
      llvm-svn: 158601
      aa1e8f3a
    • Benjamin Kramer's avatar
      Merge the SmallBitVector and BitVector unit tests with gtest's typed test... · 34d6a9e5
      Benjamin Kramer authored
      Merge the SmallBitVector and BitVector unit tests with gtest's typed test magic and bring SmallBitVector up to date.
      
      llvm-svn: 158600
      34d6a9e5
    • Chandler Carruth's avatar
      Relax one assertion -- long double has strange alignments on lots of · 3bbbeebd
      Chandler Carruth authored
      platforms.
      
      Also, remove one assertion on MSVC because it produces a completely
      preposterous result, claiming something needs 12-byte alignment.
      
      llvm-svn: 158599
      3bbbeebd
    • Chandler Carruth's avatar
      Try to reduce the size of the array used for compile-time testing by · 8710d886
      Chandler Carruth authored
      making the bounds all '1', and chunking it a bit.
      
      llvm-svn: 158598
      8710d886
    • Chandler Carruth's avatar
      Add support to the alignment support header for conjuring a character · dea00d7c
      Chandler Carruth authored
      array of a suitable size and alignment for any of a number of different
      types to be stored into the character array.
      
      The mechanisms for producing an explicitly aligned type are fairly
      complex because this operation is poorly supported on all compilers.
      We've spent a fairly significant amount of time experimenting with
      different implementations inside of Google, and the one using explicitly
      expanded templates has been the most robust.
      
      Credit goes to Nick Lewycky for writing the first 20 versions or so of
      this logic we had inside of Google. I based this on the only one to
      actually survive. In case anyone is worried, yes we are both explicitly
      re-contributing and re-licensing it for LLVM. =]
      
      Once the issues with actually specifying the alignment are finished, it
      turns out that most compilers don't in turn align anything the way they
      are instructed. Testing of this logic against both Clang and GCC
      indicate that the alignment constraints are largely ignored by both
      compilers! I've come up with and used a work-around by wrapping each
      alignment-hinted type directly in a struct, and using that struct to
      align the character array through a union. This elaborate hackery is
      terrifying, but I've included testing that caught a terrifying number of
      bugs in every other technique I've tried.
      
      All of this in order to implement a poor C++98 programmers emulation of
      C++11 unrestricted unions in classes such as SmallDenseMap.
      
      llvm-svn: 158597
      dea00d7c
    • Chandler Carruth's avatar
      Work around a bug with MSVC 10 where it fails to recognize a valid use · a68dcb44
      Chandler Carruth authored
      of typename. GCC and Clang were fine with this, but MSVC won't accept
      it. Fortunately, it also doesn't need it. Yuck.
      
      Thanks to Nakamura for pointing this out in IRC.
      
      llvm-svn: 158593
      a68dcb44
    • Chandler Carruth's avatar
      Type parameterize the DenseMap unit tests. · 2b50c40e
      Chandler Carruth authored
      These were already trying to be type parameterized over different
      key/value pairs. I've realized this goal using GoogleTest's typed test
      functionality. This allows us to easily replicate the tests across
      different key/value combinations and soon different mapping templates.
      
      I've fixed a few bugs in the tests and extended them a bit in the
      process as many tests were only applying to the int->int mapping.
      
      llvm-svn: 158589
      2b50c40e
  10. Jun 06, 2012
  11. Jun 05, 2012
Loading