src/qpid/RangeSet.h: generic set implementation using ranges.

 - no heap allocation for simple sets (<= 3 ranges)
 - binary searches for o(log(n)) performance in complex sets


git-svn-id: https://svn.apache.org/repos/asf/incubator/qpid/trunk@650198 13f79535-47bb-0310-9956-ffa450edef68

7 files changed, 512 insertions, 15 deletions

diff --git a/qpid/cpp/src/Makefile.am b/qpid/cpp/src/Makefile.am
index cf4630cdf0..2af40c3d86 100644
--- a/qpid/cpp/src/Makefile.am
+++ b/qpid/cpp/src/Makefile.am
@@ -297,6 +297,7 @@ nobase_include_HEADERS = \
   qpid/Options.h \
   qpid/Plugin.h \
   qpid/ptr_map.h \
+  qpid/RangeSet.h \
   qpid/RefCounted.h \
   qpid/SharedObject.h \
   qpid/Url.h \
diff --git a/qpid/cpp/src/qpid/InlineAllocator.h b/qpid/cpp/src/qpid/InlineAllocator.h
index 0bb30fa1a4..fd652aca03 100644
--- a/qpid/cpp/src/qpid/InlineAllocator.h
+++ b/qpid/cpp/src/qpid/InlineAllocator.h
@@ -23,6 +23,7 @@
  */
 
 #include <memory>
+#include <assert.h>
 
 namespace qpid {
 
@@ -49,7 +50,10 @@ class InlineAllocator : public BaseAllocator {
     }
 
     void deallocate(pointer p, size_type n) {
-        if (p == store) allocated=false;
+        if (p == store) {
+            assert(allocated);
+            allocated=false;
+        }
         else BaseAllocator::deallocate(p, n);
     }
 
diff --git a/qpid/cpp/src/qpid/RangeSet.h b/qpid/cpp/src/qpid/RangeSet.h
new file mode 100644
index 0000000000..2861337427
--- /dev/null
+++ b/qpid/cpp/src/qpid/RangeSet.h
@@ -0,0 +1,279 @@
+#ifndef QPID_RANGESET_H
+#define QPID_RANGESET_H
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ * 
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/InlineVector.h"
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/operators.hpp>
+#include <boost/bind.hpp>
+#include <algorithm>
+
+namespace qpid {
+
+/** A range of values, used in RangeSet */
+template <class T>
+class Range {
+  public:
+    Range() : begin_(), end_() {}
+    explicit Range(const T& t) : begin_(t), end_(t) { ++end_; }
+    Range(const T& b, const T& e) : begin_(b), end_(e) { assert(b <= e); }
+
+    T begin() const { return begin_; }
+    T end() const { return end_; }
+
+    void begin(const T& t) { begin_ = t; }
+    void end(const T& t) { end_ = t; }
+
+    bool empty() const { return begin_ == end_; }
+
+    bool contains(const T& x) const { return begin_ <= x && x < end_; }
+    bool contains(const Range& r) const { return begin_ <= r.begin_ && r.end_ <= end_; }
+
+    bool operator==(const Range& x) { return begin_ == x.begin_ && end_== x.end_; }
+
+    bool operator<(const T& t) const { return end_ < t; }
+
+    /** touching ranges can be merged into a single range. */
+    bool touching(const Range& r) const {
+        return std::max(begin_, r.begin_) <= std::min(end_, r.end_);
+    }
+
+    /** @pre touching */
+    void merge(const Range& r) {
+        assert(touching(r));
+        begin_ = std::min(begin_, r.begin_);
+        end_ = std::max(end_, r.end_);
+    }
+
+    operator bool() const { return !empty(); }
+        
+  private:
+    T begin_, end_;
+};
+
+
+/**
+ * A set implemented as a list of [begin, end) ranges.
+ * T must be LessThanComparable and Incrementable.
+ * RangeSet only provides const iterators.
+ */
+template <class T>
+class RangeSet
+    : boost::additive1<RangeSet<T>,
+                       boost::additive2<RangeSet<T>, Range<T>,
+                                        boost::additive2<RangeSet<T>, T> > >
+{
+    typedef qpid::Range<T> Range;
+    typedef InlineVector<Range, 3> Ranges; // TODO aconway 2008-04-21: what's the optimial inlined value?
+
+  public:
+    
+    class iterator : public boost::iterator_facade<
+        iterator,
+        const T,
+        boost::forward_traversal_tag>
+    {
+      public:
+        iterator() : ranges(), iter(), value() {}
+    
+      private:
+        typedef typename Ranges::const_iterator RangesIter;
+        iterator(const Ranges& r, const RangesIter& i, const T& t)
+            : ranges(&r), iter(i), value(t) {}
+        
+        void increment();
+        bool equal(const iterator& i) const;
+        const T& dereference() const { return value; }
+
+        const Ranges* ranges;
+        RangesIter iter;
+        T value;
+
+      friend class RangeSet<T>;
+      friend class boost::iterator_core_access;
+    };
+
+    typedef iterator const_iterator;
+    
+    RangeSet() {}
+    explicit RangeSet(const Range& r) { ranges.push_back(r); }
+    RangeSet(const T& a, const T& b) { ranges.push_back(Range(a,b)); }
+    
+    bool contiguous() const { return ranges.size() <= 1; }
+
+    bool contains(const T& t) const;
+    bool contains(const Range&) const;
+
+    /**@pre contiguous() */
+    Range toRange() const;
+
+    bool operator==(const RangeSet<T>&) const;
+
+    void removeRange (const Range&);
+    void removeSet (const RangeSet&);
+    
+    RangeSet& operator+=(const T& t) { return *this += Range(t); }
+    RangeSet& operator+=(const Range&);
+    RangeSet& operator+=(const RangeSet&) { return *this; };
+
+    RangeSet& operator-=(const T& t)  { return *this -= Range(t); }
+    RangeSet& operator-=(const Range& r) { removeRange(r); return *this; }
+    RangeSet& operator-=(const RangeSet& s) { removeSet(s); return *this; }
+
+    T front() const { return ranges.front().begin(); }
+    T back() const { return ranges.back().end(); }
+
+    iterator begin() const;
+    iterator end() const;
+    
+    bool empty() const { return ranges.empty(); }
+
+    /** Return the largest contiguous range containing x.
+     * Returns the empty range [x,x) if x is not in the set.
+     */
+    Range rangeContaining(const T&) const;
+
+ private:
+    Ranges ranges;
+
+  template <class U> friend std::ostream& operator<<(std::ostream& o, const RangeSet<U>& r);
+
+  friend class iterator;
+};
+
+template <class T>
+std::ostream& operator<<(std::ostream& o, const Range<T>& r) {
+    return o << "[" << r.begin() << "," << r.end() << ")";
+}
+
+template <class T>
+std::ostream& operator<<(std::ostream& o, const RangeSet<T>& rs) {
+    std::ostream_iterator<Range<T> > i(o, " ");
+    o << "{ ";
+    std::copy(rs.ranges.begin(), rs.ranges.end(), i);
+    return o << "}";
+}
+
+template <class T>
+bool RangeSet<T>::contains(const T& t) const {
+    typename Ranges::const_iterator i =
+        std::lower_bound(ranges.begin(), ranges.end(), t);
+    return i != ranges.end() && i->contains(t);
+}
+
+template <class T>
+bool RangeSet<T>::contains(const Range& r) const {
+    typename Ranges::const_iterator i =
+        std::lower_bound(ranges.begin(), ranges.end(), r.begin());
+    return i != ranges.end() && i->contains(r);
+}
+
+template <class T> RangeSet<T>& RangeSet<T>::operator+=(const Range& r) {
+    typename Ranges::iterator i =
+        std::lower_bound(ranges.begin(), ranges.end(), r.begin());
+    if (i != ranges.end() && i->touching(r)) {
+        i->merge(r);
+        typename Ranges::iterator j = i;
+        if (++j != ranges.end() && i->touching(*j)) {
+            i->merge(*j);
+            ranges.erase(j);
+        }
+    }
+    else
+        ranges.insert(i, r);
+    return *this;
+}
+
+template <class T> void RangeSet<T>::removeRange(const Range& r) {
+    typename Ranges::iterator i,j;
+    i = std::lower_bound(ranges.begin(), ranges.end(), r.begin());
+    if (i == ranges.end() || i->begin() >= r.end())
+        return;                 // Outside of set
+    if (*i == r)                // Erase i
+        ranges.erase(i);
+    else if (i->contains(r)) {  // Split i
+        Range i1(i->begin(), r.begin());
+        Range i2(r.end(), i->end());
+        *i = i2;
+        ranges.insert(i, i1);
+    } else {
+        if (i->begin() < r.begin()) { // Truncate i
+            i->end(r.begin());
+            ++i;
+        }
+        for (j = i; j != ranges.end() && r.contains(*j); ++j)
+            ;                   // Ranges to erase.
+        if (j != ranges.end() && j->end() > r.end())
+            j->begin(r.end());   // Truncate j
+        ranges.erase(i,j);
+    }
+}
+
+template <class T> void RangeSet<T>::removeSet(const RangeSet& r) {
+    std::for_each(
+        r.ranges.begin(), r.ranges.end(),
+        boost::bind(&RangeSet<T>::removeRange, this, _1));
+}
+
+template <class T> Range<T> RangeSet<T>::toRange() const {
+    assert(contiguous());
+    return empty() ? Range() :  ranges.front();
+}
+
+template <class T> void RangeSet<T>::iterator::increment() {
+    assert(ranges && iter != ranges->end());
+    if (!iter->contains(++value)) {
+        ++iter;
+        if (iter == ranges->end())
+            *this=iterator();   // end() iterator
+        else 
+            value=iter->begin();
+    }
+}
+
+template <class T> bool RangeSet<T>::operator==(const RangeSet<T>& r) const {
+    return ranges.size() == r.ranges.size() && std::equal(ranges.begin(), ranges.end(), r.ranges.begin());
+}
+
+template <class T> typename RangeSet<T>::iterator RangeSet<T>::begin() const {
+    return empty() ? end() : iterator(ranges, ranges.begin(), front());
+}
+
+template <class T> typename RangeSet<T>::iterator RangeSet<T>::end() const {
+    return iterator();
+}
+
+template <class T> bool RangeSet<T>::iterator::equal(const iterator& i) const {
+    return ranges==i.ranges && (ranges==0 || value==i.value);
+}
+
+template <class T> Range<T> RangeSet<T>::rangeContaining(const T& t) const {
+    typename Ranges::const_iterator i =
+        std::lower_bound(ranges.begin(), ranges.end(), t);
+    return (i != ranges.end() && i->contains(t)) ? *i : Range(t,t);
+}
+
+} // namespace qpid
+
+
+#endif  /*!QPID_RANGESET_H*/
diff --git a/qpid/cpp/src/tests/InlineAllocator.cpp b/qpid/cpp/src/tests/InlineAllocator.cpp
new file mode 100644
index 0000000000..fe6eaefaf4
--- /dev/null
+++ b/qpid/cpp/src/tests/InlineAllocator.cpp
@@ -0,0 +1,63 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ * 
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/InlineAllocator.h"
+#include "unit_test.h"
+
+QPID_AUTO_TEST_SUITE(InlineAllocatorTestSuite)
+
+using namespace qpid;
+using namespace std;
+
+QPID_AUTO_TEST_CASE(testAllocate) {
+    InlineAllocator<std::allocator<char>, 2> alloc;
+
+    char* p = alloc.allocate(1);
+    BOOST_CHECK(p == (char*)&alloc);
+    alloc.deallocate(p,1);
+
+    p = alloc.allocate(2);
+    BOOST_CHECK(p == (char*)&alloc);
+    alloc.deallocate(p,2);
+
+    p = alloc.allocate(3);
+    BOOST_CHECK(p != (char*)&alloc);
+    alloc.deallocate(p,3);
+}
+
+QPID_AUTO_TEST_CASE(testAllocateFull) {
+    InlineAllocator<std::allocator<char>, 1> alloc;
+
+    char* p = alloc.allocate(1);
+    BOOST_CHECK(p == (char*)&alloc);
+    
+    char* q = alloc.allocate(1);
+    BOOST_CHECK(q != (char*)&alloc);
+
+    alloc.deallocate(p,1);
+    p = alloc.allocate(1);
+    BOOST_CHECK(p == (char*)&alloc);
+    
+    alloc.deallocate(p,1);
+    alloc.deallocate(q,1);
+}
+
+QPID_AUTO_TEST_SUITE_END()
diff --git a/qpid/cpp/src/tests/InlineVector.cpp b/qpid/cpp/src/tests/InlineVector.cpp
index 5f1a08759f..7add920cb2 100644
--- a/qpid/cpp/src/tests/InlineVector.cpp
+++ b/qpid/cpp/src/tests/InlineVector.cpp
@@ -66,24 +66,54 @@ QPID_AUTO_TEST_CASE(testCtor) {
 }
 
 QPID_AUTO_TEST_CASE(testInsert) {
-    Vec v;
-    v.push_back(1);
-    BOOST_CHECK_EQUAL(v.size(), 1u);
-    BOOST_CHECK_EQUAL(v.back(), 1);
-    BOOST_CHECK(isInline(v));
+    {
+        Vec v;
+        v.push_back(1);
+        BOOST_CHECK_EQUAL(v.size(), 1u);
+        BOOST_CHECK_EQUAL(v.back(), 1);
+        BOOST_CHECK(isInline(v));
 
-    v.insert(v.begin(), 2);
-    BOOST_CHECK_EQUAL(v.size(), 2u);
-    BOOST_CHECK_EQUAL(v.back(), 1);
-    BOOST_CHECK(isInline(v));
+        v.insert(v.begin(), 2);
+        BOOST_CHECK_EQUAL(v.size(), 2u);
+        BOOST_CHECK_EQUAL(v.back(), 1);
+        BOOST_CHECK(isInline(v));
 
-    v.push_back(3);
-    BOOST_CHECK(isInline(v));
+        v.push_back(3);
+        BOOST_CHECK(isInline(v));
 
-    v.push_back(4);
-    BOOST_CHECK_EQUAL(v.size(), 4u);
+        v.push_back(4);
+
+        BOOST_CHECK(!isInline(v));
+    }
+    {
+        Vec v(3,42);
+        v.insert(v.begin(), 9);
+        BOOST_CHECK_EQUAL(v.size(), 4u);
+        BOOST_CHECK(!isInline(v));
+    }
+    {
+        Vec v(3,42);
+        v.insert(v.begin()+1, 9);
+        BOOST_CHECK(!isInline(v));
+        BOOST_CHECK_EQUAL(v.size(), 4u);
+    }
+}
+
+QPID_AUTO_TEST_CASE(testAssign) {
+    Vec v(3,42);
+    Vec u;
+    u = v;
+    BOOST_CHECK(isInline(u));
+    u.push_back(4);
+    BOOST_CHECK(!isInline(u));
+    v = u;
     BOOST_CHECK(!isInline(v));
 }
 
+QPID_AUTO_TEST_CASE(testResize) {
+    Vec v;
+    v.resize(5);
+    BOOST_CHECK(!isInline(v));    
+}
 
 QPID_AUTO_TEST_SUITE_END()
diff --git a/qpid/cpp/src/tests/Makefile.am b/qpid/cpp/src/tests/Makefile.am
index b7fe79f56c..a6750a427a 100644
--- a/qpid/cpp/src/tests/Makefile.am
+++ b/qpid/cpp/src/tests/Makefile.am
@@ -36,6 +36,7 @@ unit_test_SOURCES= unit_test.cpp unit_test.h \
 	SessionState.cpp Blob.cpp logging.cpp \
 	Url.cpp Uuid.cpp \
 	Shlib.cpp FieldValue.cpp FieldTable.cpp Array.cpp \
+	InlineAllocator.cpp \
 	InlineVector.cpp \
 	ISList.cpp IList.cpp \
 	ClientSessionTest.cpp \
@@ -45,7 +46,9 @@ unit_test_SOURCES= unit_test.cpp unit_test.h \
 	amqp_0_10/apply.cpp \
 	IncompleteMessageList.cpp \
 	amqp_0_10/Map.cpp \
-	amqp_0_10/handlers.cpp
+	amqp_0_10/handlers.cpp \
+	RangeSet.cpp
+
 
 check_LTLIBRARIES += libshlibtest.la
 libshlibtest_la_LDFLAGS = -module -rpath $(abs_builddir)
diff --git a/qpid/cpp/src/tests/RangeSet.cpp b/qpid/cpp/src/tests/RangeSet.cpp
new file mode 100644
index 0000000000..bc125ed4e2
--- /dev/null
+++ b/qpid/cpp/src/tests/RangeSet.cpp
@@ -0,0 +1,117 @@
+/*
+ *
+ * Copyright (c) 2006 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+
+#include "unit_test.h"
+#include "test_tools.h"
+#include "qpid/RangeSet.h"
+
+using namespace std;
+using namespace qpid;
+
+QPID_AUTO_TEST_SUITE(RangeSetTestSuite)
+
+typedef qpid::Range<int> Range;
+typedef qpid::RangeSet<int> RangeSet;
+
+QPID_AUTO_TEST_CASE(testEmptyRange) {
+    Range r;
+    BOOST_CHECK(r.empty());
+    BOOST_CHECK(!r.contains(0));
+    //    BOOST_CHECK(r.contiguous(0));
+}
+
+QPID_AUTO_TEST_CASE(testRangeSetAddPoint) {
+    RangeSet r;
+    BOOST_CHECK(r.empty());
+    r += 3;
+    BOOST_CHECK_MESSAGE(r.contains(3), r);
+    BOOST_CHECK_MESSAGE(r.contains(Range(3,4)), r);
+    BOOST_CHECK(!r.empty());
+    r += 5;
+    BOOST_CHECK_MESSAGE(r.contains(5), r);        
+    BOOST_CHECK_MESSAGE(r.contains(Range(5,6)), r);        
+    BOOST_CHECK_MESSAGE(!r.contains(Range(3,6)), r);
+    r += 4;
+    BOOST_CHECK_MESSAGE(r.contains(Range(3,6)), r);
+}
+
+QPID_AUTO_TEST_CASE(testRangeSetAddRange) {
+    RangeSet r;
+    r += Range(0,3);
+    BOOST_CHECK(r.contains(Range(0,3)));
+    r += Range(4,6);
+    BOOST_CHECK_MESSAGE(r.contains(Range(4,6)), r);
+    r += 3;
+    BOOST_CHECK_MESSAGE(r.contains(Range(0,6)), r);
+    BOOST_CHECK(r.front() == 0);
+    BOOST_CHECK(r.back() == 6);
+}
+
+QPID_AUTO_TEST_CASE(testRangeSetIterate) {
+    RangeSet r;
+    (((r += 1) += 10) += Range(4,7)) += 2;
+    BOOST_MESSAGE(r);
+    std::vector<int> actual;
+    std::copy(r.begin(), r.end(), std::back_inserter(actual));
+    std::vector<int> expect = boost::assign::list_of(1)(2)(4)(5)(6)(10);
+    BOOST_CHECK_EQUAL(expect, actual);
+}
+
+QPID_AUTO_TEST_CASE(testRangeSetRemove) {
+    BOOST_CHECK_EQUAL(RangeSet(0,5)-3, RangeSet(0,3)+Range(4,5));
+    BOOST_CHECK_EQUAL(RangeSet(1,5)-5, RangeSet(1,5));
+    BOOST_CHECK_EQUAL(RangeSet(1,5)-0, RangeSet(1,5));
+
+    RangeSet r(RangeSet(0,5)+Range(10,15)+Range(20,25));
+
+    BOOST_CHECK_EQUAL(r-Range(0,5), RangeSet(10,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(10,15), RangeSet(0,5)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(20,25), RangeSet(0,5)+Range(10,15));
+
+    BOOST_CHECK_EQUAL(r-Range(-5, 30), RangeSet());
+
+    BOOST_CHECK_EQUAL(r-Range(-5, 7), RangeSet(10,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(8,19), RangeSet(0,5)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(17,30), RangeSet(0,5)+Range(10,15));
+
+    BOOST_CHECK_EQUAL(r-Range(-5, 5), RangeSet(10,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(10,19), RangeSet(0,5)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(18,25), RangeSet(0,5)+Range(10,15));
+
+    BOOST_CHECK_EQUAL(r-Range(-3, 3), RangeSet(3,5)+Range(10,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(3, 7), RangeSet(0,2)+Range(10,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(3, 12), RangeSet(0,3)+Range(12,15)+Range(20,25));
+    BOOST_CHECK_EQUAL(r-Range(3, 22), RangeSet(12,15)+Range(22,25));
+    BOOST_CHECK_EQUAL(r-Range(12, 22), RangeSet(0,5)+Range(10,11)+Range(22,25));
+}
+
+QPID_AUTO_TEST_CASE(testRangeContaining) {
+    RangeSet r;
+    (((r += 1) += Range(3,5)) += 7);
+    BOOST_CHECK_EQUAL(r.rangeContaining(0), Range(0,0));
+    BOOST_CHECK_EQUAL(r.rangeContaining(1), Range(1,2));
+    BOOST_CHECK_EQUAL(r.rangeContaining(2), Range(2,2));
+    BOOST_CHECK_EQUAL(r.rangeContaining(3), Range(3,5));
+    BOOST_CHECK_EQUAL(r.rangeContaining(4), Range(3,5));
+    BOOST_CHECK_EQUAL(r.rangeContaining(5), Range(5,5));
+    BOOST_CHECK_EQUAL(r.rangeContaining(6), Range(6,6));
+    BOOST_CHECK_EQUAL(r.rangeContaining(7), Range(7,8));
+}
+
+QPID_AUTO_TEST_SUITE_END()