Line data Source code
1 : /*
2 : * Distributed under the OpenDDS License.
3 : * See: http://www.opendds.org/license.html
4 : */
5 :
6 : #ifndef OPENDDS_DCPS_DISJOINTSEQUENCE_H
7 : #define OPENDDS_DCPS_DISJOINTSEQUENCE_H
8 :
9 : #include "dcps_export.h"
10 : #include "Definitions.h"
11 : #include "SequenceNumber.h"
12 : #include "PoolAllocator.h"
13 :
14 : OPENDDS_BEGIN_VERSIONED_NAMESPACE_DECL
15 :
16 : namespace OpenDDS {
17 : namespace DCPS {
18 :
19 : /// Data structure for a set of SequenceNumbers.
20 : /// Sequence numbers can be inserted as single numbers, ranges,
21 : /// or RTPS-style bitmaps. The DisjointSequence can then be queried for
22 : /// contiguous ranges and internal gaps.
23 : class OpenDDS_Dcps_Export DisjointSequence {
24 : public:
25 :
26 : DisjointSequence();
27 : void reset();
28 :
29 : bool empty() const;
30 :
31 : /// Lowest SequenceNumber in the set.
32 : /// Precondition: !empty()
33 : SequenceNumber low() const;
34 :
35 : /// Highest SequenceNumber in the set.
36 : /// Precondition: !empty()
37 : SequenceNumber high() const;
38 :
39 : /// Gets the high end of the lowest contiguous range.
40 : /// Named after the use case of tracking received messages (which may be
41 : /// received out-of-order) and then determining the largest value that the
42 : /// receiver is allowed to acknowledge (under a cumulative-acking protocol).
43 : /// If empty(), returns SEQUENCENUMBER_UNKNOWN.
44 : SequenceNumber cumulative_ack() const;
45 :
46 : /// Gets the low end of the highest contiguous range, may be thought of as
47 : /// the inverse of cumulative_ack().
48 : /// If empty(), returns SEQUENCENUMBER_UNKNOWN.
49 : SequenceNumber last_ack() const;
50 :
51 : /// Objects with the disjoint() property have an internal gap in the inserted
52 : /// SequenceNumbers.
53 : bool disjoint() const;
54 :
55 : bool contains(SequenceNumber value) const;
56 :
57 : bool contains_any(const SequenceRange& range) const;
58 :
59 : /// All insert() methods return true upon modifying the set and false if
60 : /// the set already contained the SequenceNumber(s) that were to be inserted.
61 : /// This is the general form of insert() whereby the caller receives a list of
62 : /// sub-ranges of 'range' that were not already in the DisjointSequence.
63 : /// For example, given a DisjointSequence 'seq' containing (1, 2, 5, 9),
64 : /// calling seq.insert(SequenceRange(4, 12), v) returns true
65 : /// and yields v = [(4, 4), (6, 8), (10, 12)] and seq = (1, 2, 4, ..., 12).
66 : bool insert(const SequenceRange& range, OPENDDS_VECTOR(SequenceRange)& added);
67 :
68 : /// Insert all numbers between range.first and range.second (both inclusive).
69 : bool insert(const SequenceRange& range);
70 :
71 : /// Shorthand for "insert(SequenceRange(value, value))"
72 : bool insert(SequenceNumber value);
73 :
74 : void erase(SequenceNumber value);
75 :
76 : /// Insert using the RTPS compact representation of a set. The three
77 : /// parameters, taken together, describe a set with each 1 bit starting
78 : /// at the msb of bits[0] and extending through num_bits (which are located at
79 : /// the next least significant bits of bits[0] followed by the msb of bits[1],
80 : /// etc.) indicating presence of the number (value + bit_index) in the set.
81 : /// bit_index is 0-based.
82 : /// Precondition: the array 'bits' has at least ceil(num_bits / 32) entries.
83 : bool insert(SequenceNumber value,
84 : ACE_CDR::ULong num_bits,
85 : const ACE_CDR::Long bits[]);
86 :
87 : /// Insert the intersection of range and filter
88 : bool insert_filtered(const SequenceRange& range, const DisjointSequence& filter);
89 :
90 : /// Inverse of insert(value, num_bits, bits). Populates array of
91 : /// bitmap[length] with the bitmap of ranges above the cumulative_ack() value.
92 : /// Sets the number of significant (used) bits in num_bits. The 'base' of the
93 : /// bitmap is one larger than cumulative_ack(). Returns true if the entire
94 : /// DisjointSequence was able to fit in bitmap[]. Returning false is not an
95 : /// error, it's just that the higher-valued ranges didn't fit. If invert is
96 : /// true, the 1's in the bitmap represent the missing_sequence_ranges()
97 : /// instead of the present_sequence_ranges().
98 : /// Precondition: the array 'bits' has 'length' entries allocated.
99 : bool to_bitmap(ACE_CDR::Long bitmap[],
100 : ACE_CDR::ULong length,
101 : ACE_CDR::ULong& num_bits,
102 : ACE_CDR::ULong& cumulative_bits_added,
103 : bool invert = false) const;
104 :
105 : /// Returns missing ranges of SequenceNumbers (internal gaps in the sequence)
106 : OPENDDS_VECTOR(SequenceRange) missing_sequence_ranges() const;
107 :
108 : /// Returns a representation of the members of the sequence as a list of
109 : /// contiguous ranges (each Range is inclusive on both sides).
110 : OPENDDS_VECTOR(SequenceRange) present_sequence_ranges() const;
111 :
112 : void dump() const;
113 :
114 : /// Core data structure of DisjointSequence:
115 : /// Use a balanced binary tree (std::set) to store a list of ranges (std::pair of T).
116 : /// Maintain invariants (in addition to those from std::set):
117 : /// - For any element x of the set, x.second >= x.first
118 : /// - No adjacent or overlapping ranges. Given two elements ordered "x before y", y.first > x.second + 1
119 : /// Common non-mutating operations on the underlying set are public members of this class.
120 : /// Note that due to this design, size() is the number of contiguous ranges, not individual values.
121 : /// Some mutating operations on the underlying set that can't violate the invariants are also provided (like clear).
122 : /// Type T needs to support value-initialization, construction from int, copying,
123 : /// addition, subtraction, and comparison using == and <.
124 : template <typename T>
125 : class OrderedRanges {
126 : public:
127 : typedef std::pair<T, T> TPair;
128 : typedef bool (*Compare)(const TPair&, const TPair&);
129 : typedef OPENDDS_SET_CMP(TPair, Compare) Container;
130 : typedef typename Container::size_type size_type;
131 : typedef typename Container::const_iterator const_iterator;
132 : typedef const_iterator iterator;
133 : typedef typename Container::const_reverse_iterator const_reverse_iterator;
134 : typedef const_reverse_iterator reverse_iterator;
135 :
136 5743 : static bool range_less(const TPair& lhs, const TPair& rhs)
137 : {
138 5743 : return lhs.second < rhs.second;
139 : }
140 :
141 252 : OrderedRanges()
142 252 : : ranges_(range_less)
143 252 : {}
144 :
145 126 : const_iterator begin() const { return ranges_.begin(); }
146 : const_iterator cbegin() const { return ranges_.begin(); }
147 :
148 638 : const_iterator end() const { return ranges_.end(); }
149 : const_iterator cend() const { return ranges_.end(); }
150 :
151 31 : const_reverse_iterator rbegin() const { return ranges_.rbegin(); }
152 : const_reverse_iterator crbegin() const { return ranges_.rbegin(); }
153 :
154 : const_reverse_iterator rend() const { return ranges_.rend(); }
155 : const_reverse_iterator crend() const { return ranges_.rend(); }
156 :
157 141 : bool empty() const { return ranges_.empty(); }
158 74 : size_type size() const { return ranges_.size(); }
159 13 : void clear() { ranges_.clear(); }
160 :
161 200 : void add(T lower, T upper)
162 : {
163 200 : OPENDDS_ASSERT(upper >= lower);
164 200 : if (has(lower, upper)) {
165 0 : return;
166 : }
167 :
168 200 : const T above = upper + 1;
169 200 : for (typename Container::iterator i = lower_bound_i(lower - 1);
170 324 : i != ranges_.end() && (i->first <= above || i->second <= above);
171 : /* iterate in loop because of removal */) {
172 124 : lower = (std::min)(lower, i->first);
173 124 : upper = (std::max)(upper, i->second);
174 124 : ranges_.erase(i++);
175 : }
176 :
177 200 : ranges_.insert(TPair(lower, upper));
178 : }
179 :
180 196 : void add(T value)
181 : {
182 196 : add(value, value);
183 196 : }
184 :
185 1 : void remove(T value)
186 : {
187 1 : const typename Container::iterator iter = lower_bound_i(value);
188 1 : if (iter == end() || value < iter->first) {
189 0 : return;
190 : }
191 1 : remove_i(iter, value);
192 : }
193 :
194 2 : T pop_front()
195 : {
196 2 : const T value = begin()->first;
197 2 : remove_i(ranges_.begin(), value);
198 2 : return value;
199 : }
200 :
201 318 : bool has(T lower, T upper) const
202 : {
203 318 : const const_iterator iter = lower_bound(upper);
204 318 : return iter != end() && !(lower < iter->first);
205 : }
206 :
207 : bool has(const TPair& range) const
208 : {
209 : return has(range.first, range.second);
210 : }
211 :
212 115 : bool has(T value) const
213 : {
214 115 : return has(value, value);
215 : }
216 :
217 : bool has_any(T lower, T upper) const
218 : {
219 : const const_iterator iter = lower_bound(lower);
220 : return iter != end() && !(upper < iter->first);
221 : }
222 :
223 : bool has_any(const TPair& range) const
224 : {
225 : return has_any(range.first, range.second);
226 : }
227 :
228 : template <typename Type> friend
229 : bool operator==(const OrderedRanges<Type>& a, const OrderedRanges<Type>& b);
230 :
231 : private:
232 : const_iterator lower_bound(const TPair& p) const { return ranges_.lower_bound(p); }
233 :
234 318 : const_iterator lower_bound(T t) const
235 : {
236 318 : return ranges_.lower_bound(TPair(T() /*ignored*/, t));
237 : }
238 :
239 : // explicitly get a non-const iterator for use with methods like erase()
240 201 : typename Container::iterator lower_bound_i(T t)
241 : {
242 201 : return ranges_.lower_bound(TPair(T() /*ignored*/, t));
243 : }
244 :
245 : const_iterator upper_bound(const TPair& p) const { return ranges_.upper_bound(p); }
246 :
247 : const_iterator upper_bound(T t) const
248 : {
249 : return ranges_.upper_bound(TPair(T() /*ignored*/, t));
250 : }
251 :
252 : // 'iter' must be a valid iterator to a range that contains 'value'
253 3 : void remove_i(typename Container::iterator iter, T value)
254 : {
255 3 : const TPair orig = *iter;
256 3 : ranges_.erase(iter);
257 3 : if (value == orig.first) {
258 3 : if (value < orig.second) {
259 1 : ranges_.insert(TPair(value + T(1), orig.second));
260 : }
261 0 : } else if (value == orig.second) {
262 0 : ranges_.insert(TPair(orig.first, value - T(1)));
263 : } else {
264 0 : ranges_.insert(TPair(orig.first, value - T(1)));
265 0 : ranges_.insert(TPair(value + T(1), orig.second));
266 : }
267 3 : }
268 :
269 : friend class DisjointSequence;
270 : Container ranges_;
271 : };
272 :
273 : private:
274 : typedef OrderedRanges<SequenceNumber> RangeSet;
275 : RangeSet sequences_;
276 :
277 : // helper methods:
278 :
279 : bool insert_i(const SequenceRange& range,
280 : OPENDDS_VECTOR(SequenceRange)* gaps = 0);
281 :
282 : bool insert_bitmap_range(RangeSet::Container::iterator& iter, const SequenceRange& sr);
283 :
284 : public:
285 : /// Set the bits in range [low, high] in the bitmap, updating num_bits.
286 : static bool fill_bitmap_range(ACE_CDR::ULong low, ACE_CDR::ULong high,
287 : ACE_CDR::Long bitmap[], ACE_CDR::ULong length,
288 : ACE_CDR::ULong& num_bits, ACE_CDR::ULong& cumulative_bits_added);
289 :
290 : /// Return the number of CORBA::Longs required for the bitmap representation of
291 : /// sequence numbers between low and high, inclusive (maximum 8 longs).
292 : static ACE_CDR::ULong bitmap_num_longs(const SequenceNumber& low, const SequenceNumber& high);
293 : };
294 :
295 : template <typename T>
296 : bool operator==(
297 : const DisjointSequence::OrderedRanges<T>& a, const DisjointSequence::OrderedRanges<T>& b)
298 : {
299 : return a.ranges_ == b.ranges_;
300 : }
301 :
302 : } // namespace DCPS
303 : } // namespace OpenDDS
304 :
305 : OPENDDS_END_VERSIONED_NAMESPACE_DECL
306 :
307 : #ifdef __ACE_INLINE__
308 : # include "DisjointSequence.inl"
309 : #endif /* __ACE_INLINE__ */
310 :
311 : #endif /* DCPS_DISJOINTSEQUENCE_H */
|
