Author: aconway
Date: Mon Apr 21 09:36:08 2008
New Revision: 650198
URL: http://svn.apache.org/viewvc?rev=650198&view=rev
Log:
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
Added:
incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h (with props)
incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp (with props)
incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp (with props)
Modified:
incubator/qpid/trunk/qpid/cpp/src/Makefile.am
incubator/qpid/trunk/qpid/cpp/src/qpid/InlineAllocator.h
incubator/qpid/trunk/qpid/cpp/src/tests/InlineVector.cpp
incubator/qpid/trunk/qpid/cpp/src/tests/Makefile.am
Modified: incubator/qpid/trunk/qpid/cpp/src/Makefile.am
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/Makefile.am?rev=650198&r1=650197&r2=650198&view=diff
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/Makefile.am (original)
+++ incubator/qpid/trunk/qpid/cpp/src/Makefile.am Mon Apr 21 09:36:08 2008
@@ -297,6 +297,7 @@
qpid/Options.h \
qpid/Plugin.h \
qpid/ptr_map.h \
+ qpid/RangeSet.h \
qpid/RefCounted.h \
qpid/SharedObject.h \
qpid/Url.h \
Modified: incubator/qpid/trunk/qpid/cpp/src/qpid/InlineAllocator.h
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/qpid/InlineAllocator.h?rev=650198&r1=650197&r2=650198&view=diff
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/qpid/InlineAllocator.h (original)
+++ incubator/qpid/trunk/qpid/cpp/src/qpid/InlineAllocator.h Mon Apr 21
09:36:08 2008
@@ -23,6 +23,7 @@
*/
#include <memory>
+#include <assert.h>
namespace qpid {
@@ -49,7 +50,10 @@
}
void deallocate(pointer p, size_type n) {
- if (p == store) allocated=false;
+ if (p == store) {
+ assert(allocated);
+ allocated=false;
+ }
else BaseAllocator::deallocate(p, n);
}
Added: incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h?rev=650198&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h (added)
+++ incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h Mon Apr 21 09:36:08 2008
@@ -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;
+
+ /[EMAIL PROTECTED] 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*/
Propchange: incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/qpid/trunk/qpid/cpp/src/qpid/RangeSet.h
------------------------------------------------------------------------------
svn:keywords = Rev Date
Added: incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp?rev=650198&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp (added)
+++ incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp Mon Apr 21
09:36:08 2008
@@ -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()
Propchange: incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/qpid/trunk/qpid/cpp/src/tests/InlineAllocator.cpp
------------------------------------------------------------------------------
svn:keywords = Rev Date
Modified: incubator/qpid/trunk/qpid/cpp/src/tests/InlineVector.cpp
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/tests/InlineVector.cpp?rev=650198&r1=650197&r2=650198&view=diff
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/tests/InlineVector.cpp (original)
+++ incubator/qpid/trunk/qpid/cpp/src/tests/InlineVector.cpp Mon Apr 21
09:36:08 2008
@@ -66,24 +66,54 @@
}
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));
-
- v.insert(v.begin(), 2);
- BOOST_CHECK_EQUAL(v.size(), 2u);
- 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.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()
Modified: incubator/qpid/trunk/qpid/cpp/src/tests/Makefile.am
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/tests/Makefile.am?rev=650198&r1=650197&r2=650198&view=diff
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/tests/Makefile.am (original)
+++ incubator/qpid/trunk/qpid/cpp/src/tests/Makefile.am Mon Apr 21 09:36:08 2008
@@ -36,6 +36,7 @@
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 @@
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)
Added: incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp
URL:
http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp?rev=650198&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp (added)
+++ incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp Mon Apr 21 09:36:08
2008
@@ -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()
Propchange: incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: incubator/qpid/trunk/qpid/cpp/src/tests/RangeSet.cpp
------------------------------------------------------------------------------
svn:keywords = Rev Date
