Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / RangeSet.h
index 56ecf4b..9db10fc 100644 (file)
@@ -56,6 +56,8 @@ public:
     typedef RangeType Range;
     typedef typename Range::Type Type;
 
+    typedef Vector<Range, 8> VectorType;
+    
     RangeSet()
     {
     }
@@ -77,6 +79,10 @@ public:
         m_isCompact = false;
 
         // We append without compacting only if doing so is guaranteed not to resize the vector.
+        // FIXME: This heuristic is almost certainly wrong, because we don't control the capacity. I
+        // think that this means that we will sometimes be rage-compacting when we are just shy of the
+        // capacity.
+        // https://bugs.webkit.org/show_bug.cgi?id=170308
         if (m_ranges.size() + 1 < m_ranges.capacity()) {
             m_ranges.append(range);
             return;
@@ -92,15 +98,8 @@ public:
             return false;
         
         unsigned index = findRange(range);
-        if (index + 1 < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index + 1], range))
-            return true;
-        if (index < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index], range))
-            return true;
-        if (static_cast<unsigned>(index - 1) < m_ranges.size()
-            && subsumesNonEmpty(m_ranges[index - 1], range))
-            return true;
+        if (index != UINT_MAX)
+            return subsumesNonEmpty(m_ranges[index], range);
         return false;
     }
 
@@ -109,17 +108,7 @@ public:
         if (range.begin() == range.end())
             return false;
         
-        unsigned index = findRange(range);
-        if (index + 1 < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index + 1], range))
-            return true;
-        if (index < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index], range))
-            return true;
-        if (static_cast<unsigned>(index - 1) < m_ranges.size()
-            && overlapsNonEmpty(m_ranges[index - 1], range))
-            return true;
-        return false;
+        return findRange(range) != UINT_MAX;
     }
 
     void clear()
@@ -138,8 +127,23 @@ public:
     {
         out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
     }
+    
+    typename VectorType::const_iterator begin() const
+    {
+        return m_ranges.begin();
+    }
+    
+    typename VectorType::const_iterator end() const
+    {
+        return m_ranges.end();
+    }
+    
+    void addAll(const RangeSet& other)
+    {
+        for (Range range : other)
+            add(range);
+    }
 
-private:
     void compact()
     {
         if (m_isCompact)
@@ -172,11 +176,12 @@ private:
             lastRange = &m_ranges[dstIndex++];
             *lastRange = range;
         }
-        m_ranges.resize(dstIndex);
+        m_ranges.shrink(dstIndex);
 
         m_isCompact = true;
     }
     
+private:
     static bool overlapsNonEmpty(const Range& a, const Range& b)
     {
         return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
@@ -191,17 +196,16 @@ private:
     {
         const_cast<RangeSet*>(this)->compact();
 
-        const Range* found = approximateBinarySearch<const Range, Type>(
-            m_ranges, m_ranges.size(), range.begin(), [&] (const Range* range) -> Type {
-                return range->begin();
-            });
-        if (!found)
-            return UINT_MAX;
-
-        return found - m_ranges.begin();
+        // FIXME: Once we start using this in anger, we will want this to be a binary search.
+        for (unsigned i = 0; i < m_ranges.size(); ++i) {
+            if (overlapsNonEmpty(m_ranges[i], range))
+                return i;
+        }
+        
+        return UINT_MAX;
     }
     
-    Vector<Range, 8> m_ranges;
+    VectorType m_ranges;
     bool m_isCompact { true };
 };