Make SparseBitVector::set actually work properly when sets are not in ascending or descending order.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42604 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 10 insertions, 4 deletions

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index a6df0acdc7..d1e9125068 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -334,9 +334,8 @@ class SparseBitVector {
         --ElementIter;
     } else {
       while (ElementIter != Elements.end() &&
-             ElementIter->index() <= ElementIndex)
+             ElementIter->index() < ElementIndex)
         ++ElementIter;
-      --ElementIter;
     }
     CurrElementIter = ElementIter;
     return ElementIter;
@@ -536,10 +535,17 @@ public:
       if (ElementIter == Elements.end() ||
           ElementIter->index() != ElementIndex) {
         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
-        // Insert does insert before, and lower bound gives the one before.
-        ElementIter = Elements.insert(++ElementIter, Element);
+        // We may have hit the beginning of our SparseBitVector, in which case,
+        // we may need to insert right after this element, which requires moving
+        // the current iterator forward one, because insert does insert before.
+        if (ElementIter->index() < ElementIndex)
+          ElementIter = Elements.insert(++ElementIter, Element);
+        else
+          ElementIter = Elements.insert(ElementIter, Element);
       }
     }
+    CurrElementIter = ElementIter;
+      
     ElementIter->set(Idx % ElementSize);
   }