1 ////////////////////////////////////////////////////////////////////////////
3 // Copyright 2015 Realm Inc.
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
9 // http://www.apache.org/licenses/LICENSE-2.0
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
17 ////////////////////////////////////////////////////////////////////////////
19 #include "index_set.hpp"
21 #include <realm/util/assert.hpp>
25 using namespace realm;
26 using namespace realm::_impl;
28 const size_t IndexSet::npos;
31 void MutableChunkedRangeVectorIterator<T>::set(size_t front, size_t back)
33 this->m_outer->count -= this->m_inner->second - this->m_inner->first;
34 if (this->offset() == 0) {
35 this->m_outer->begin = front;
37 if (this->m_inner == &this->m_outer->data.back()) {
38 this->m_outer->end = back;
40 this->m_outer->count += back - front;
41 this->m_inner->first = front;
42 this->m_inner->second = back;
46 void MutableChunkedRangeVectorIterator<T>::adjust(ptrdiff_t front, ptrdiff_t back)
48 if (this->offset() == 0) {
49 this->m_outer->begin += front;
51 if (this->m_inner == &this->m_outer->data.back()) {
52 this->m_outer->end += back;
54 this->m_outer->count += -front + back;
55 this->m_inner->first += front;
56 this->m_inner->second += back;
60 void MutableChunkedRangeVectorIterator<T>::shift(ptrdiff_t distance)
62 if (this->offset() == 0) {
63 this->m_outer->begin += distance;
65 if (this->m_inner == &this->m_outer->data.back()) {
66 this->m_outer->end += distance;
68 this->m_inner->first += distance;
69 this->m_inner->second += distance;
72 void ChunkedRangeVector::push_back(value_type value)
74 if (!empty() && m_data.back().data.size() < max_size) {
75 auto& range = m_data.back();
76 REALM_ASSERT(range.end <= value.first);
78 range.data.push_back(value);
79 range.count += value.second - value.first;
80 range.end = value.second;
83 m_data.push_back({{value}, value.first, value.second, value.second - value.first});
88 ChunkedRangeVector::iterator ChunkedRangeVector::insert(iterator pos, value_type value)
90 if (pos.m_outer == m_data.end()) {
91 push_back(std::move(value));
92 return std::prev(end());
95 pos = ensure_space(pos);
96 auto& chunk = *pos.m_outer;
97 pos.m_inner = &*chunk.data.insert(pos.m_outer->data.begin() + pos.offset(), value);
98 chunk.count += value.second - value.first;
99 chunk.begin = std::min(chunk.begin, value.first);
100 chunk.end = std::max(chunk.end, value.second);
106 ChunkedRangeVector::iterator ChunkedRangeVector::ensure_space(iterator pos)
108 if (pos.m_outer->data.size() + 1 <= max_size)
111 auto offset = pos.offset();
113 // Split the chunk in half to make space for the new insertion
114 auto new_pos = m_data.insert(pos.m_outer + 1, Chunk{});
115 auto prev = new_pos - 1;
116 auto to_move = max_size / 2;
117 new_pos->data.reserve(to_move);
118 new_pos->data.assign(prev->data.end() - to_move, prev->data.end());
119 prev->data.resize(prev->data.size() - to_move);
121 size_t moved_count = 0;
122 for (auto range : new_pos->data)
123 moved_count += range.second - range.first;
125 prev->end = prev->data.back().second;
126 prev->count -= moved_count;
127 new_pos->begin = new_pos->data.front().first;
128 new_pos->end = new_pos->data.back().second;
129 new_pos->count = moved_count;
131 if (offset >= to_move) {
132 pos.m_outer = new_pos;
138 pos.m_end = m_data.end();
139 pos.m_inner = &pos.m_outer->data[offset];
144 ChunkedRangeVector::iterator ChunkedRangeVector::erase(iterator pos) noexcept
146 auto offset = pos.offset();
147 auto& chunk = *pos.m_outer;
148 chunk.count -= pos->second - pos->first;
149 chunk.data.erase(chunk.data.begin() + offset);
151 if (chunk.data.size() == 0) {
152 pos.m_outer = m_data.erase(pos.m_outer);
153 pos.m_end = m_data.end();
154 pos.m_inner = pos.m_outer == m_data.end() ? nullptr : &pos.m_outer->data.front();
159 chunk.begin = chunk.data.front().first;
160 chunk.end = chunk.data.back().second;
161 if (offset < chunk.data.size())
162 pos.m_inner = &chunk.data[offset];
165 pos.m_inner = pos.m_outer == pos.m_end ? nullptr : &pos.m_outer->data.front();
172 void ChunkedRangeVector::verify() const noexcept
175 size_t prev_end = -1;
176 for (auto range : *this) {
177 REALM_ASSERT(range.first < range.second);
178 REALM_ASSERT(prev_end == size_t(-1) || range.first > prev_end);
179 prev_end = range.second;
182 for (auto& chunk : m_data) {
183 REALM_ASSERT(!chunk.data.empty());
184 REALM_ASSERT(chunk.data.front().first == chunk.begin);
185 REALM_ASSERT(chunk.data.back().second == chunk.end);
186 REALM_ASSERT(chunk.count <= chunk.end - chunk.begin);
188 for (auto range : chunk.data)
189 count += range.second - range.first;
190 REALM_ASSERT(count == chunk.count);
196 class ChunkedRangeVectorBuilder {
198 using value_type = std::pair<size_t, size_t>;
200 ChunkedRangeVectorBuilder(ChunkedRangeVector const& expected);
201 void push_back(size_t index);
202 void push_back(std::pair<size_t, size_t> range);
203 std::vector<ChunkedRangeVector::Chunk> finalize();
205 std::vector<ChunkedRangeVector::Chunk> m_data;
206 size_t m_outer_pos = 0;
209 ChunkedRangeVectorBuilder::ChunkedRangeVectorBuilder(ChunkedRangeVector const& expected)
212 for (auto const& chunk : expected.m_data)
213 size += chunk.data.size();
214 m_data.resize(size / ChunkedRangeVector::max_size + 1);
215 for (size_t i = 0; i < m_data.size() - 1; ++i)
216 m_data[i].data.reserve(ChunkedRangeVector::max_size);
219 void ChunkedRangeVectorBuilder::push_back(size_t index)
221 push_back({index, index + 1});
224 void ChunkedRangeVectorBuilder::push_back(std::pair<size_t, size_t> range)
226 auto& chunk = m_data[m_outer_pos];
227 if (chunk.data.empty()) {
228 chunk.data.push_back(range);
229 chunk.count = range.second - range.first;
230 chunk.begin = range.first;
232 else if (range.first == chunk.data.back().second) {
233 chunk.data.back().second = range.second;
234 chunk.count += range.second - range.first;
236 else if (chunk.data.size() < ChunkedRangeVector::max_size) {
237 chunk.data.push_back(range);
238 chunk.count += range.second - range.first;
241 chunk.end = chunk.data.back().second;
243 if (m_outer_pos >= m_data.size())
244 m_data.push_back({{range}, range.first, 0, 1});
246 auto& chunk = m_data[m_outer_pos];
247 chunk.data.push_back(range);
248 chunk.begin = range.first;
249 chunk.count = range.second - range.first;
254 std::vector<ChunkedRangeVector::Chunk> ChunkedRangeVectorBuilder::finalize()
256 if (!m_data.empty()) {
257 m_data.resize(m_outer_pos + 1);
258 if (m_data.back().data.empty())
261 m_data.back().end = m_data.back().data.back().second;
263 return std::move(m_data);
267 IndexSet::IndexSet(std::initializer_list<size_t> values)
269 for (size_t v : values)
273 bool IndexSet::contains(size_t index) const noexcept
275 auto it = const_cast<IndexSet*>(this)->find(index);
276 return it != end() && it->first <= index;
279 size_t IndexSet::count(size_t start_index, size_t end_index) const noexcept
281 auto it = const_cast<IndexSet*>(this)->find(start_index);
282 const auto end = this->end();
283 if (it == end || it->first >= end_index) {
286 if (it->second >= end_index)
287 return std::min(it->second, end_index) - std::max(it->first, start_index);
291 if (start_index > it->first || it.offset() != 0) {
292 // Start index is in the middle of a chunk, so start by counting the
293 // rest of that chunk
294 ret = it->second - std::max(it->first, start_index);
295 for (++it; it != end && it->second < end_index && it.offset() != 0; ++it) {
296 ret += it->second - it->first;
298 if (it != end && it->first < end_index && it.offset() != 0)
299 ret += end_index - it->first;
300 if (it == end || it->second >= end_index)
304 // Now count all complete chunks that fall within the range
305 while (it != end && it.outer()->end <= end_index) {
306 REALM_ASSERT_DEBUG(it.offset() == 0);
307 ret += it.outer()->count;
311 // Cound all complete ranges within the last chunk
312 while (it != end && it->second <= end_index) {
313 ret += it->second - it->first;
317 // And finally add in the partial last range
318 if (it != end && it->first < end_index)
319 ret += end_index - it->first;
323 IndexSet::iterator IndexSet::find(size_t index) noexcept
325 return find(index, begin());
328 IndexSet::iterator IndexSet::find(size_t index, iterator begin) noexcept
330 auto it = std::find_if(begin.outer(), m_data.end(),
331 [&](auto const& lft) { return lft.end > index; });
332 if (it == m_data.end())
334 if (index < it->begin)
335 return iterator(it, m_data.end(), &it->data[0]);
336 auto inner_begin = it->data.begin();
337 if (it == begin.outer())
338 inner_begin += begin.offset();
339 auto inner = std::lower_bound(inner_begin, it->data.end(), index,
340 [&](auto const& lft, auto) { return lft.second <= index; });
341 REALM_ASSERT_DEBUG(inner != it->data.end());
343 return iterator(it, m_data.end(), &*inner);
346 void IndexSet::add(size_t index)
348 do_add(find(index), index);
351 void IndexSet::add(IndexSet const& other)
354 for (size_t index : other.as_indexes()) {
355 it = do_add(find(index, it), index);
359 size_t IndexSet::add_shifted(size_t index)
361 iterator it = begin(), end = this->end();
363 // Shift for any complete chunks before the target
364 for (; it != end && it.outer()->end <= index; it.next_chunk())
365 index += it.outer()->count;
367 // And any ranges within the last partial chunk
368 for (; it != end && it->first <= index; ++it)
369 index += it->second - it->first;
375 void IndexSet::add_shifted_by(IndexSet const& shifted_by, IndexSet const& values)
381 size_t expected = std::distance(as_indexes().begin(), as_indexes().end());
382 for (auto index : values.as_indexes()) {
383 if (!shifted_by.contains(index))
388 ChunkedRangeVectorBuilder builder(*this);
390 auto old_it = cbegin(), old_end = cend();
391 auto shift_it = shifted_by.cbegin(), shift_end = shifted_by.cend();
393 size_t skip_until = 0;
394 size_t old_shift = 0;
395 size_t new_shift = 0;
396 for (size_t index : values.as_indexes()) {
397 for (; shift_it != shift_end && shift_it->first <= index; ++shift_it) {
398 new_shift += shift_it->second - shift_it->first;
399 skip_until = shift_it->second;
401 if (index < skip_until)
404 for (; old_it != old_end && old_it->first <= index - new_shift + old_shift; ++old_it) {
405 for (size_t i = old_it->first; i < old_it->second; ++i)
406 builder.push_back(i);
407 old_shift += old_it->second - old_it->first;
410 REALM_ASSERT(index >= new_shift);
411 builder.push_back(index - new_shift + old_shift);
414 copy(old_it, old_end, std::back_inserter(builder));
415 m_data = builder.finalize();
418 REALM_ASSERT((size_t)std::distance(as_indexes().begin(), as_indexes().end()) == expected);
422 void IndexSet::set(size_t len)
430 void IndexSet::insert_at(size_t index, size_t count)
432 REALM_ASSERT(count > 0);
434 auto pos = find(index);
435 auto end = this->end();
436 bool in_existing = false;
438 if (pos->first <= index) {
440 pos.adjust(0, count);
445 for (auto it = std::next(pos); it != end; ++it)
449 for (size_t i = 0; i < count; ++i)
450 pos = std::next(do_add(pos, index + i));
456 void IndexSet::insert_at(IndexSet const& positions)
458 if (positions.empty())
465 IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
466 IndexIterator end1 = cend(), end2 = positions.cend();
468 ChunkedRangeVectorBuilder builder(*this);
470 while (begin1 != end1 && begin2 != end2) {
471 if (*begin1 + shift < *begin2) {
472 builder.push_back(*begin1++ + shift);
476 builder.push_back(*begin2++);
479 for (; begin1 != end1; ++begin1)
480 builder.push_back(*begin1 + shift);
481 for (; begin2 != end2; ++begin2)
482 builder.push_back(*begin2);
484 m_data = builder.finalize();
487 void IndexSet::shift_for_insert_at(size_t index, size_t count)
489 REALM_ASSERT(count > 0);
491 auto it = find(index);
495 for (auto pos = it, end = this->end(); pos != end; ++pos)
498 // If the range contained the insertion point, split the range and move
499 // the part of it before the insertion point back
500 if (it->first < index + count) {
501 auto old_second = it->second;
502 it.set(it->first - count, index);
503 insert(std::next(it), {index + count, old_second});
508 void IndexSet::shift_for_insert_at(realm::IndexSet const& values)
510 if (empty() || values.empty())
512 if (values.m_data.front().begin >= m_data.back().end)
515 IndexIterator begin1 = cbegin(), begin2 = values.cbegin();
516 IndexIterator end1 = cend(), end2 = values.cend();
518 ChunkedRangeVectorBuilder builder(*this);
520 while (begin1 != end1 && begin2 != end2) {
521 if (*begin1 + shift < *begin2) {
522 builder.push_back(*begin1++ + shift);
529 for (; begin1 != end1; ++begin1)
530 builder.push_back(*begin1 + shift);
532 m_data = builder.finalize();
535 void IndexSet::erase_at(size_t index)
537 auto it = find(index);
542 void IndexSet::erase_at(IndexSet const& positions)
544 if (empty() || positions.empty())
547 ChunkedRangeVectorBuilder builder(*this);
549 IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
550 IndexIterator end1 = cend(), end2 = positions.cend();
553 while (begin1 != end1 && begin2 != end2) {
554 if (*begin1 < *begin2) {
555 builder.push_back(*begin1++ - shift);
557 else if (*begin1 == *begin2) {
567 for (; begin1 != end1; ++begin1)
568 builder.push_back(*begin1 - shift);
570 m_data = builder.finalize();
573 size_t IndexSet::erase_or_unshift(size_t index)
575 auto shifted = index;
576 iterator it = begin(), end = this->end();
578 // Shift for any complete chunks before the target
579 for (; it != end && it.outer()->end <= index; it.next_chunk())
580 shifted -= it.outer()->count;
582 // And any ranges within the last partial chunk
583 for (; it != end && it->second <= index; ++it)
584 shifted -= it->second - it->first;
589 if (it->first <= index)
597 void IndexSet::do_erase(iterator it, size_t index)
599 if (it->first <= index) {
600 if (it->first + 1 == it->second) {
608 else if (it != begin() && std::prev(it)->second + 1 == it->first) {
609 std::prev(it).adjust(0, it->second - it->first);
613 for (; it != end(); ++it)
617 IndexSet::iterator IndexSet::do_remove(iterator it, size_t begin, size_t end)
619 for (it = find(begin, it); it != this->end() && it->first < end; it = find(begin, it)) {
620 // Trim off any part of the range to remove that's before the matching range
621 begin = std::max(it->first, begin);
623 // If the matching range extends to both sides of the range to remove,
624 // split it on the range to remove
625 if (it->first < begin && it->second > end) {
626 auto old_second = it->second;
627 it.set(it->first, begin);
628 it = std::prev(insert(std::next(it), {end, old_second}));
630 // Range to delete now coverages (at least) one end of the matching range
631 else if (begin == it->first && end >= it->second)
633 else if (begin == it->first)
634 it.set(end, it->second);
636 it.set(it->first, begin);
641 void IndexSet::remove(size_t index, size_t count)
643 do_remove(find(index), index, index + count);
646 void IndexSet::remove(realm::IndexSet const& values)
649 for (auto range : values) {
650 it = do_remove(it, range.first, range.second);
656 size_t IndexSet::shift(size_t index) const noexcept
659 for (auto range : *this) {
660 if (range.first > index)
662 index += range.second - range.first;
667 size_t IndexSet::unshift(size_t index) const noexcept
669 REALM_ASSERT_DEBUG(!contains(index));
670 return index - count(0, index);
673 void IndexSet::clear() noexcept
678 IndexSet::iterator IndexSet::do_add(iterator it, size_t index)
681 bool more_before = it != begin(), valid = it != end();
682 REALM_ASSERT(!more_before || index >= std::prev(it)->second);
683 if (valid && it->first <= index && it->second > index) {
684 // index is already in set
687 if (more_before && std::prev(it)->second == index) {
688 auto prev = std::prev(it);
689 // index is immediately after an existing range
692 if (valid && prev->second == it->first) {
693 // index joins two existing ranges
694 prev.adjust(0, it->second - it->first);
695 return std::prev(erase(it));
699 if (valid && it->first == index + 1) {
700 // index is immediately before an existing range
705 // index is not next to an existing range
706 return insert(it, {index, index + 1});