webkitgtk-2.16.5HEADwebkitgtk-2.16.5master

1 files changed, 195 insertions, 0 deletions

diff --git a/Source/WTF/wtf/RangeSet.h b/Source/WTF/wtf/RangeSet.h
new file mode 100644
index 000000000..75471ad7d
--- /dev/null
+++ b/Source/WTF/wtf/RangeSet.h
@@ -0,0 +1,195 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef WTF_RangeSet_h
+#define WTF_RangeSet_h
+
+#include <wtf/ListDump.h>
+#include <wtf/MathExtras.h>
+#include <wtf/StdLibExtras.h>
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// A RangeSet is a set of numerical ranges. A value belongs to the set if it is within any of the
+// ranges. A range belongs to the set if every value in the range belongs to the set. A range overlaps
+// the set if any value in the range belongs to the set. You can add ranges and query range
+// membership. The internal representation is a list of ranges that gets periodically compacted. This
+// representation is optimal so long as the number of distinct ranges tends to be small, and the
+// number of range sets tends to be small as well. This works reasonably well in a bunch of compiler
+// algorithms, where the top range ends up being used a lot.
+//
+// The initial user of this is JSC::B3::HeapRange, which is used to perform alias analysis. You can
+// model new users on that class. Basically, you need to define:
+//
+// T::Type - the type of the members of the range. HeapRange uses unsigned.
+// T(T::Type begin, T::Type end) - construct a new range.
+// T::Type T::begin() const - instance method giving the inclusive beginning of the range.
+// T::Type T::end() const - instance method giving the exclusive end of the range.
+// void T::dump(PrintStream&) const - some kind of dumping.
+
+template<typename RangeType>
+class RangeSet {
+public:
+    typedef RangeType Range;
+    typedef typename Range::Type Type;
+
+    RangeSet()
+    {
+    }
+
+    ~RangeSet()
+    {
+    }
+
+    void add(const Range& range)
+    {
+        if (range.begin() == range.end())
+            return;
+        
+        // We expect the range set to become top in a lot of cases. We also expect the same range to
+        // be added repeatedly. That's why this is here.
+        if (!m_ranges.isEmpty() && subsumesNonEmpty(m_ranges.last(), range))
+            return;
+
+        m_isCompact = false;
+
+        // We append without compacting only if doing so is guaranteed not to resize the vector.
+        if (m_ranges.size() + 1 < m_ranges.capacity()) {
+            m_ranges.append(range);
+            return;
+        }
+
+        m_ranges.append(range);
+        compact();
+    }
+
+    bool contains(const Range& range) const
+    {
+        if (range.begin() == range.end())
+            return false;
+        
+        unsigned index = findRange(range);
+        if (index != UINT_MAX)
+            return subsumesNonEmpty(m_ranges[index], range);
+        return false;
+    }
+
+    bool overlaps(const Range& range) const
+    {
+        if (range.begin() == range.end())
+            return false;
+        
+        return findRange(range) != UINT_MAX;
+    }
+
+    void clear()
+    {
+        m_ranges.clear();
+        m_isCompact = true;
+    }
+
+    void dump(PrintStream& out) const
+    {
+        const_cast<RangeSet*>(this)->compact();
+        out.print(listDump(m_ranges));
+    }
+
+    void dumpRaw(PrintStream& out) const
+    {
+        out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
+    }
+
+private:
+    void compact()
+    {
+        if (m_isCompact)
+            return;
+
+        if (m_ranges.isEmpty()) {
+            m_isCompact = true;
+            return;
+        }
+
+        std::sort(
+            m_ranges.begin(), m_ranges.end(),
+            [&] (const Range& a, const Range& b) -> bool {
+                return a.begin() < b.begin();
+            });
+
+        unsigned srcIndex = 1;
+        unsigned dstIndex = 1;
+        Range* lastRange = &m_ranges[0];
+        while (srcIndex < m_ranges.size()) {
+            Range range = m_ranges[srcIndex++];
+            ASSERT(range.begin() >= lastRange->begin());
+            if (range.end() <= lastRange->end())
+                continue;
+            if (range.begin() <= lastRange->end()) {
+                *lastRange = Range(lastRange->begin(), range.end());
+                continue;
+            }
+            ASSERT(!overlapsNonEmpty(*lastRange, range));
+            lastRange = &m_ranges[dstIndex++];
+            *lastRange = range;
+        }
+        m_ranges.resize(dstIndex);
+
+        m_isCompact = true;
+    }
+    
+    static bool overlapsNonEmpty(const Range& a, const Range& b)
+    {
+        return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
+    }
+
+    static bool subsumesNonEmpty(const Range& a, const Range& b)
+    {
+        return a.begin() <= b.begin() && a.end() >= b.end();
+    }
+
+    unsigned findRange(const Range& range) const
+    {
+        const_cast<RangeSet*>(this)->compact();
+
+        // 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;
+    bool m_isCompact { true };
+};
+
+} // namespace WTF
+
+using WTF::RangeSet;
+
+#endif // WTF_RangeSet_h
+