This file is indexed.

/usr/include/qpid/RangeSet.h is in libqpidcommon2-dev 0.16-9ubuntu2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
#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>
#include <numeric>

namespace qpid {

/** A range of values, used in RangeSet.
 * Range(begin, end) includes begin but excludes end.
 * Range::makeClosed(first,last) includes both first and last.
 */
template <class T>
class Range {
  public:
    static Range makeClosed(const T& first, T last) { return Range(first, ++last); }

    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_; }
    /** End of _open_ range, i.e. !contains(end()) */
    T end() const { return end_; }

    T first() const { assert(!empty()); return begin_; }
    /** Last in closed range, i.e. contains(end()) */
    T last() const { assert(!empty()); T ret=end_; return --ret; }

    void begin(const T& t) { begin_ = t; }
    void end(const T& t) { end_ = t; }
    size_t size() const { return end_ - begin_; }
    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 strictContains(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; }
    bool operator<(const Range<T>& r) const { return end_ < r.begin_; }

    /** 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(); }

    template <class S> void serialize(S& s) { s(begin_)(end_); }

  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 InlineVector<Range<T>, 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<T>& r) { *this += r; }
    RangeSet(const T& a, const T& b) { *this += Range<T>(a,b); }

    bool contiguous() const { return ranges.size() <= 1; }

    bool contains(const T& t) const;
    bool contains(const Range<T>&) const;

    /**@pre contiguous() */
    Range<T> toRange() const;

    bool operator==(const RangeSet<T>&) const;

    void addRange (const Range<T>&);
    void addSet (const RangeSet<T>&);

    RangeSet<T>& operator+=(const T& t) { return *this += Range<T>(t); }
    RangeSet<T>& operator+=(const Range<T>& r) { addRange(r); return *this; }
    RangeSet<T>& operator+=(const RangeSet<T>& s) { addSet(s); return *this; }

    void removeRange (const Range<T>&);
    void removeSet (const RangeSet<T>&);

    RangeSet<T>& operator-=(const T& t)  { return *this -= Range<T>(t); }
    RangeSet<T>& operator-=(const Range<T>& r) { removeRange(r); return *this; }
    RangeSet<T>& operator-=(const RangeSet<T>& s) { removeSet(s); return *this; }

    T front() const { return ranges.front().begin(); }
    T back() const { return ranges.back().end(); }

    // Iterate over elements in the set.
    iterator begin() const;
    iterator end() const;

    // Iterate over ranges in the set.
    typedef typename Ranges::const_iterator RangeIterator;
    RangeIterator rangesBegin() const { return ranges.begin(); }
    RangeIterator rangesEnd() const { return ranges.end(); }
    size_t rangesSize() const { return ranges.size(); }

    // The difference between the start and end of this range set
    uint32_t span() const;

    size_t size() const;
    bool empty() const { return ranges.empty(); }
    void clear() { ranges.clear(); }

    /** Return the largest contiguous range containing x.
     * Returns the empty range [x,x) if x is not in the set.
     */
    Range<T> rangeContaining(const T&) const;

    template <class S> void serialize(S& s) { s.split(*this); s(ranges.begin(), ranges.end()); }
    template <class S> void encode(S& s) const { s(uint16_t(ranges.size()*sizeof(Range<T>))); }
    template <class S> void decode(S& s) { uint16_t sz; s(sz); ranges.resize(sz/sizeof(Range<T>)); }

 private:
    static size_t accumulateSize(size_t s, const Range<T>& r) { return s+r.size(); }
    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(), Range<T>(t));
    return i != ranges.end() && i->contains(t);
}

template <class T>
bool RangeSet<T>::contains(const Range<T>& r) const {
    typename Ranges::const_iterator i =
        std::lower_bound(ranges.begin(), ranges.end(), r);
    return i != ranges.end() && i->contains(r);
}

template <class T> void RangeSet<T>::addRange(const Range<T>& r) {
    if (r.empty()) return;
    typename Ranges::iterator i =
        std::lower_bound(ranges.begin(), ranges.end(), r);
    if (i == ranges.end() || !i->touching(r))
        ranges.insert(i, r);
    else {
        i->merge(r);
        typename Ranges::iterator j = i;
        if (++j != ranges.end() && i->touching(*j)) {
            i->merge(*j);
            ranges.erase(j);
        }
    }
}


template <class T> void RangeSet<T>::addSet(const RangeSet<T>& s) {
    typedef RangeSet<T>& (RangeSet<T>::*RangeSetRangeOp)(const Range<T>&);
    std::for_each(s.ranges.begin(), s.ranges.end(),
                  boost::bind((RangeSetRangeOp)&RangeSet<T>::operator+=, this, _1));
}

template <class T> void RangeSet<T>::removeRange(const Range<T>& r) {
    if (r.empty()) return;
    typename Ranges::iterator i,j;
    i = std::lower_bound(ranges.begin(), ranges.end(), r);
    if (i == ranges.end() || i->begin() >= r.end())
        return;                 // Outside of set
    if (*i == r)                // Erase i
        ranges.erase(i);
    else if (i->strictContains(r)) {  // Split i
        Range<T> i1(i->begin(), r.begin());
        Range<T> 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() && r.end() > j->begin())
            j->begin(r.end()); // Truncate j
        ranges.erase(i,j);
    }
}

template <class T> void RangeSet<T>::removeSet(const RangeSet<T>& 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<T>() :  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(), Range<T>(t));
    return (i != ranges.end() && i->contains(t)) ? *i : Range<T>(t,t);
}

template <class T> uint32_t RangeSet<T>::span() const {
    if (ranges.empty()) return 0;
    return ranges.back().last() - ranges.front().first();
}

template <class T> size_t RangeSet<T>::size() const {
    return std::accumulate(rangesBegin(), rangesEnd(), 0, &RangeSet<T>::accumulateSize);
}

} // namespace qpid


#endif  /*!QPID_RANGESET_H*/