forked from scylladb/scylladb
-
Notifications
You must be signed in to change notification settings - Fork 0
/
clustering_interval_set.hh
131 lines (126 loc) · 5.29 KB
/
clustering_interval_set.hh
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
/*
* Copyright (C) 2020-present ScyllaDB
*/
/*
* SPDX-License-Identifier: AGPL-3.0-or-later
*/
#pragma once
#include "schema/schema_fwd.hh"
#include "mutation/position_in_partition.hh"
#include <boost/icl/interval_set.hpp>
// Represents a non-contiguous subset of clustering_key domain of a particular schema.
// Can be treated like an ordered and non-overlapping sequence of position_range:s.
class clustering_interval_set {
// Needed to make position_in_partition comparable, required by boost::icl::interval_set.
class position_in_partition_with_schema {
schema_ptr _schema;
position_in_partition _pos;
public:
position_in_partition_with_schema()
: _pos(position_in_partition::for_static_row())
{ }
position_in_partition_with_schema(schema_ptr s, position_in_partition pos)
: _schema(std::move(s))
, _pos(std::move(pos))
{ }
bool operator<(const position_in_partition_with_schema& other) const {
return position_in_partition::less_compare(*_schema)(_pos, other._pos);
}
bool operator==(const position_in_partition_with_schema& other) const {
return position_in_partition::equal_compare(*_schema)(_pos, other._pos);
}
const position_in_partition& position() const { return _pos; }
};
private:
// We want to represent intervals of clustering keys, not position_in_partitions,
// but clustering_key domain is not enough to represent all kinds of clustering ranges.
// All intervals in this set are of the form [x, y).
using set_type = boost::icl::interval_set<position_in_partition_with_schema>;
using interval = boost::icl::interval<position_in_partition_with_schema>;
set_type _set;
public:
clustering_interval_set() = default;
// Constructs from legacy clustering_row_ranges
clustering_interval_set(const schema& s, const query::clustering_row_ranges& ranges) {
for (auto&& r : ranges) {
add(s, position_range::from_range(r));
}
}
query::clustering_row_ranges to_clustering_row_ranges() const {
query::clustering_row_ranges result;
for (position_range r : *this) {
result.push_back(query::clustering_range::make(
{r.start().key(), r.start()._bound_weight != bound_weight::after_all_prefixed},
{r.end().key(), r.end()._bound_weight == bound_weight::after_all_prefixed}));
}
return result;
}
class position_range_iterator {
public:
using iterator_category = std::input_iterator_tag;
using value_type = const position_range;
using difference_type = std::ptrdiff_t;
using pointer = const position_range*;
using reference = const position_range&;
private:
set_type::iterator _i;
public:
position_range_iterator(set_type::iterator i) : _i(i) {}
position_range operator*() const {
// FIXME: Produce position_range view. Not performance critical yet.
const interval::interval_type& iv = *_i;
return position_range{iv.lower().position(), iv.upper().position()};
}
bool operator==(const position_range_iterator& other) const = default;
position_range_iterator& operator++() {
++_i;
return *this;
}
position_range_iterator operator++(int) {
auto tmp = *this;
++_i;
return tmp;
}
};
static interval::type make_interval(const schema& s, const position_range& r) {
assert(r.start().has_clustering_key());
assert(r.end().has_clustering_key());
return interval::right_open(
position_in_partition_with_schema(s.shared_from_this(), r.start()),
position_in_partition_with_schema(s.shared_from_this(), r.end()));
}
public:
bool equals(const schema& s, const clustering_interval_set& other) const {
return boost::equal(_set, other._set);
}
bool contains(const schema& s, position_in_partition_view pos) const {
// FIXME: Avoid copy
return _set.find(position_in_partition_with_schema(s.shared_from_this(), position_in_partition(pos))) != _set.end();
}
// Returns true iff this set is fully contained in the other set.
bool contained_in(clustering_interval_set& other) const {
return boost::icl::within(_set, other._set);
}
bool overlaps(const schema& s, const position_range& range) const {
// FIXME: Avoid copy
auto r = _set.equal_range(make_interval(s, range));
return r.first != r.second;
}
// Adds given clustering range to this interval set.
// The range may overlap with this set.
void add(const schema& s, const position_range& r) {
_set += make_interval(s, r);
}
void add(const schema& s, const clustering_interval_set& other) {
for (auto&& r : other) {
add(s, r);
}
}
position_range_iterator begin() const { return {_set.begin()}; }
position_range_iterator end() const { return {_set.end()}; }
};
template <> struct fmt::formatter<clustering_interval_set> : fmt::formatter<string_view> {
auto format(const clustering_interval_set& set, fmt::format_context& ctx) const {
return fmt::format_to(ctx.out(), "{{{}}}", fmt::join(set, ",\n "));
}
};