iOS/Pods/Realm/Realm/ObjectStore/src/index_set.cpp

   1 ////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2015 Realm Inc.
   4 //
   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
   8 //
   9 // http://www.apache.org/licenses/LICENSE-2.0
  10 //
  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.
  16 //
  17 ////////////////////////////////////////////////////////////////////////////
  18
  19 #include "index_set.hpp"
  20
  21 #include <realm/util/assert.hpp>
  22
  23 #include <algorithm>
  24
  25 using namespace realm;
  26 using namespace realm::_impl;
  27
  28 const size_t IndexSet::npos;
  29
  30 template<typename T>
  31 void MutableChunkedRangeVectorIterator<T>::set(size_t front, size_t back)
  32 {
  33     this->m_outer->count -= this->m_inner->second - this->m_inner->first;
  34     if (this->offset() == 0) {
  35         this->m_outer->begin = front;
  36     }
  37     if (this->m_inner == &this->m_outer->data.back()) {
  38         this->m_outer->end = back;
  39     }
  40     this->m_outer->count += back - front;
  41     this->m_inner->first = front;
  42     this->m_inner->second = back;
  43 }
  44
  45 template<typename T>
  46 void MutableChunkedRangeVectorIterator<T>::adjust(ptrdiff_t front, ptrdiff_t back)
  47 {
  48     if (this->offset() == 0) {
  49         this->m_outer->begin += front;
  50     }
  51     if (this->m_inner == &this->m_outer->data.back()) {
  52         this->m_outer->end += back;
  53     }
  54     this->m_outer->count += -front + back;
  55     this->m_inner->first += front;
  56     this->m_inner->second += back;
  57 }
  58
  59 template<typename T>
  60 void MutableChunkedRangeVectorIterator<T>::shift(ptrdiff_t distance)
  61 {
  62     if (this->offset() == 0) {
  63         this->m_outer->begin += distance;
  64     }
  65     if (this->m_inner == &this->m_outer->data.back()) {
  66         this->m_outer->end += distance;
  67     }
  68     this->m_inner->first += distance;
  69     this->m_inner->second += distance;
  70 }
  71
  72 void ChunkedRangeVector::push_back(value_type value)
  73 {
  74     if (!empty() && m_data.back().data.size() < max_size) {
  75         auto& range = m_data.back();
  76         REALM_ASSERT(range.end <= value.first);
  77
  78         range.data.push_back(value);
  79         range.count += value.second - value.first;
  80         range.end = value.second;
  81     }
  82     else {
  83         m_data.push_back({{value}, value.first, value.second, value.second - value.first});
  84     }
  85     verify();
  86 }
  87
  88 ChunkedRangeVector::iterator ChunkedRangeVector::insert(iterator pos, value_type value)
  89 {
  90     if (pos.m_outer == m_data.end()) {
  91         push_back(std::move(value));
  92         return std::prev(end());
  93     }
  94
  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);
 101
 102     verify();
 103     return pos;
 104 }
 105
 106 ChunkedRangeVector::iterator ChunkedRangeVector::ensure_space(iterator pos)
 107 {
 108     if (pos.m_outer->data.size() + 1 <= max_size)
 109         return pos;
 110
 111     auto offset = pos.offset();
 112
 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);
 120
 121     size_t moved_count = 0;
 122     for (auto range : new_pos->data)
 123         moved_count += range.second - range.first;
 124
 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;
 130
 131     if (offset >= to_move) {
 132         pos.m_outer = new_pos;
 133         offset -= to_move;
 134     }
 135     else {
 136         pos.m_outer = prev;
 137     }
 138     pos.m_end = m_data.end();
 139     pos.m_inner = &pos.m_outer->data[offset];
 140     verify();
 141     return pos;
 142 }
 143
 144 ChunkedRangeVector::iterator ChunkedRangeVector::erase(iterator pos) noexcept
 145 {
 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);
 150
 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();
 155         verify();
 156         return pos;
 157     }
 158
 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];
 163     else {
 164         ++pos.m_outer;
 165         pos.m_inner = pos.m_outer == pos.m_end ? nullptr : &pos.m_outer->data.front();
 166     }
 167
 168     verify();
 169     return pos;
 170 }
 171
 172 void ChunkedRangeVector::verify() const noexcept
 173 {
 174 #ifdef REALM_DEBUG
 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;
 180     }
 181
 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);
 187         size_t count = 0;
 188         for (auto range : chunk.data)
 189             count += range.second - range.first;
 190         REALM_ASSERT(count == chunk.count);
 191     }
 192 #endif
 193 }
 194
 195 namespace {
 196 class ChunkedRangeVectorBuilder {
 197 public:
 198     using value_type = std::pair<size_t, size_t>;
 199
 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();
 204 private:
 205     std::vector<ChunkedRangeVector::Chunk> m_data;
 206     size_t m_outer_pos = 0;
 207 };
 208
 209 ChunkedRangeVectorBuilder::ChunkedRangeVectorBuilder(ChunkedRangeVector const& expected)
 210 {
 211     size_t size = 0;
 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);
 217 }
 218
 219 void ChunkedRangeVectorBuilder::push_back(size_t index)
 220 {
 221     push_back({index, index + 1});
 222 }
 223
 224 void ChunkedRangeVectorBuilder::push_back(std::pair<size_t, size_t> range)
 225 {
 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;
 231     }
 232     else if (range.first == chunk.data.back().second) {
 233         chunk.data.back().second = range.second;
 234         chunk.count += range.second - range.first;
 235     }
 236     else if (chunk.data.size() < ChunkedRangeVector::max_size) {
 237         chunk.data.push_back(range);
 238         chunk.count += range.second - range.first;
 239     }
 240     else {
 241         chunk.end = chunk.data.back().second;
 242         ++m_outer_pos;
 243         if (m_outer_pos >= m_data.size())
 244             m_data.push_back({{range}, range.first, 0, 1});
 245         else {
 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;
 250         }
 251     }
 252 }
 253
 254 std::vector<ChunkedRangeVector::Chunk> ChunkedRangeVectorBuilder::finalize()
 255 {
 256     if (!m_data.empty()) {
 257         m_data.resize(m_outer_pos + 1);
 258         if (m_data.back().data.empty())
 259             m_data.pop_back();
 260         else
 261             m_data.back().end = m_data.back().data.back().second;
 262     }
 263     return std::move(m_data);
 264 }
 265 }
 266
 267 IndexSet::IndexSet(std::initializer_list<size_t> values)
 268 {
 269     for (size_t v : values)
 270         add(v);
 271 }
 272
 273 bool IndexSet::contains(size_t index) const noexcept
 274 {
 275     auto it = const_cast<IndexSet*>(this)->find(index);
 276     return it != end() && it->first <= index;
 277 }
 278
 279 size_t IndexSet::count(size_t start_index, size_t end_index) const noexcept
 280 {
 281     auto it = const_cast<IndexSet*>(this)->find(start_index);
 282     const auto end = this->end();
 283     if (it == end || it->first >= end_index) {
 284         return 0;
 285     }
 286     if (it->second >= end_index)
 287         return std::min(it->second, end_index) - std::max(it->first, start_index);
 288
 289     size_t ret = 0;
 290
 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;
 297         }
 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)
 301             return ret;
 302     }
 303
 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;
 308         it.next_chunk();
 309     }
 310
 311     // Cound all complete ranges within the last chunk
 312     while (it != end && it->second <= end_index) {
 313         ret += it->second - it->first;
 314         ++it;
 315     }
 316
 317     // And finally add in the partial last range
 318     if (it != end && it->first < end_index)
 319         ret += end_index - it->first;
 320     return ret;
 321 }
 322
 323 IndexSet::iterator IndexSet::find(size_t index) noexcept
 324 {
 325     return find(index, begin());
 326 }
 327
 328 IndexSet::iterator IndexSet::find(size_t index, iterator begin) noexcept
 329 {
 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())
 333         return 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());
 342
 343     return iterator(it, m_data.end(), &*inner);
 344 }
 345
 346 void IndexSet::add(size_t index)
 347 {
 348     do_add(find(index), index);
 349 }
 350
 351 void IndexSet::add(IndexSet const& other)
 352 {
 353     auto it = begin();
 354     for (size_t index : other.as_indexes()) {
 355         it = do_add(find(index, it), index);
 356     }
 357 }
 358
 359 size_t IndexSet::add_shifted(size_t index)
 360 {
 361     iterator it = begin(), end = this->end();
 362
 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;
 366
 367     // And any ranges within the last partial chunk
 368     for (; it != end && it->first <= index; ++it)
 369         index += it->second - it->first;
 370
 371     do_add(it, index);
 372     return index;
 373 }
 374
 375 void IndexSet::add_shifted_by(IndexSet const& shifted_by, IndexSet const& values)
 376 {
 377     if (values.empty())
 378         return;
 379
 380 #ifdef REALM_DEBUG
 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))
 384             ++expected;
 385     }
 386 #endif
 387
 388     ChunkedRangeVectorBuilder builder(*this);
 389
 390     auto old_it = cbegin(), old_end = cend();
 391     auto shift_it = shifted_by.cbegin(), shift_end = shifted_by.cend();
 392
 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;
 400         }
 401         if (index < skip_until)
 402             continue;
 403
 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;
 408         }
 409
 410         REALM_ASSERT(index >= new_shift);
 411         builder.push_back(index - new_shift + old_shift);
 412     }
 413
 414     copy(old_it, old_end, std::back_inserter(builder));
 415     m_data = builder.finalize();
 416
 417 #ifdef REALM_DEBUG
 418     REALM_ASSERT((size_t)std::distance(as_indexes().begin(), as_indexes().end()) == expected);
 419 #endif
 420 }
 421
 422 void IndexSet::set(size_t len)
 423 {
 424     clear();
 425     if (len) {
 426         push_back({0, len});
 427     }
 428 }
 429
 430 void IndexSet::insert_at(size_t index, size_t count)
 431 {
 432     REALM_ASSERT(count > 0);
 433
 434     auto pos = find(index);
 435     auto end = this->end();
 436     bool in_existing = false;
 437     if (pos != end) {
 438         if (pos->first <= index) {
 439             in_existing = true;
 440             pos.adjust(0, count);
 441         }
 442         else {
 443             pos.shift(count);
 444         }
 445         for (auto it = std::next(pos); it != end; ++it)
 446             it.shift(count);
 447     }
 448     if (!in_existing) {
 449         for (size_t i = 0; i < count; ++i)
 450             pos = std::next(do_add(pos, index + i));
 451     }
 452
 453     verify();
 454 }
 455
 456 void IndexSet::insert_at(IndexSet const& positions)
 457 {
 458     if (positions.empty())
 459         return;
 460     if (empty()) {
 461         *this = positions;
 462         return;
 463     }
 464
 465     IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
 466     IndexIterator end1 = cend(), end2 = positions.cend();
 467
 468     ChunkedRangeVectorBuilder builder(*this);
 469     size_t shift = 0;
 470     while (begin1 != end1 && begin2 != end2) {
 471         if (*begin1 + shift < *begin2) {
 472             builder.push_back(*begin1++ + shift);
 473         }
 474         else {
 475             ++shift;
 476             builder.push_back(*begin2++);
 477         }
 478     }
 479     for (; begin1 != end1; ++begin1)
 480         builder.push_back(*begin1 + shift);
 481     for (; begin2 != end2; ++begin2)
 482         builder.push_back(*begin2);
 483
 484     m_data = builder.finalize();
 485 }
 486
 487 void IndexSet::shift_for_insert_at(size_t index, size_t count)
 488 {
 489     REALM_ASSERT(count > 0);
 490
 491     auto it = find(index);
 492     if (it == end())
 493         return;
 494
 495     for (auto pos = it, end = this->end(); pos != end; ++pos)
 496         pos.shift(count);
 497
 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});
 504     }
 505     verify();
 506 }
 507
 508 void IndexSet::shift_for_insert_at(realm::IndexSet const& values)
 509 {
 510     if (empty() || values.empty())
 511         return;
 512     if (values.m_data.front().begin >= m_data.back().end)
 513         return;
 514
 515     IndexIterator begin1 = cbegin(), begin2 = values.cbegin();
 516     IndexIterator end1 = cend(), end2 = values.cend();
 517
 518     ChunkedRangeVectorBuilder builder(*this);
 519     size_t shift = 0;
 520     while (begin1 != end1 && begin2 != end2) {
 521         if (*begin1 + shift < *begin2) {
 522             builder.push_back(*begin1++ + shift);
 523         }
 524         else {
 525             ++shift;
 526             begin2++;
 527         }
 528     }
 529     for (; begin1 != end1; ++begin1)
 530         builder.push_back(*begin1 + shift);
 531
 532     m_data = builder.finalize();
 533 }
 534
 535 void IndexSet::erase_at(size_t index)
 536 {
 537     auto it = find(index);
 538     if (it != end())
 539         do_erase(it, index);
 540 }
 541
 542 void IndexSet::erase_at(IndexSet const& positions)
 543 {
 544     if (empty() || positions.empty())
 545         return;
 546
 547     ChunkedRangeVectorBuilder builder(*this);
 548
 549     IndexIterator begin1 = cbegin(), begin2 = positions.cbegin();
 550     IndexIterator end1 = cend(), end2 = positions.cend();
 551
 552     size_t shift = 0;
 553     while (begin1 != end1 && begin2 != end2) {
 554         if (*begin1 < *begin2) {
 555             builder.push_back(*begin1++ - shift);
 556         }
 557         else if (*begin1 == *begin2) {
 558             ++shift;
 559             ++begin1;
 560             ++begin2;
 561         }
 562         else {
 563             ++shift;
 564             ++begin2;
 565         }
 566     }
 567     for (; begin1 != end1; ++begin1)
 568         builder.push_back(*begin1 - shift);
 569
 570     m_data = builder.finalize();
 571 }
 572
 573 size_t IndexSet::erase_or_unshift(size_t index)
 574 {
 575     auto shifted = index;
 576     iterator it = begin(), end = this->end();
 577
 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;
 581
 582     // And any ranges within the last partial chunk
 583     for (; it != end && it->second <= index; ++it)
 584         shifted -= it->second - it->first;
 585
 586     if (it == end)
 587         return shifted;
 588
 589     if (it->first <= index)
 590         shifted = npos;
 591
 592     do_erase(it, index);
 593
 594     return shifted;
 595 }
 596
 597 void IndexSet::do_erase(iterator it, size_t index)
 598 {
 599     if (it->first <= index) {
 600         if (it->first + 1 == it->second) {
 601             it = erase(it);
 602         }
 603         else {
 604             it.adjust(0, -1);
 605             ++it;
 606         }
 607     }
 608     else if (it != begin() && std::prev(it)->second + 1 == it->first) {
 609         std::prev(it).adjust(0, it->second - it->first);
 610         it = erase(it);
 611     }
 612
 613     for (; it != end(); ++it)
 614         it.shift(-1);
 615 }
 616
 617 IndexSet::iterator IndexSet::do_remove(iterator it, size_t begin, size_t end)
 618 {
 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);
 622
 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}));
 629         }
 630         // Range to delete now coverages (at least) one end of the matching range
 631         else if (begin == it->first && end >= it->second)
 632             it = erase(it);
 633         else if (begin == it->first)
 634             it.set(end, it->second);
 635         else
 636             it.set(it->first, begin);
 637     }
 638     return it;
 639 }
 640
 641 void IndexSet::remove(size_t index, size_t count)
 642 {
 643     do_remove(find(index), index, index + count);
 644 }
 645
 646 void IndexSet::remove(realm::IndexSet const& values)
 647 {
 648     auto it = begin();
 649     for (auto range : values) {
 650         it = do_remove(it, range.first, range.second);
 651         if (it == end())
 652             return;
 653     }
 654 }
 655
 656 size_t IndexSet::shift(size_t index) const noexcept
 657 {
 658     // FIXME: optimize
 659     for (auto range : *this) {
 660         if (range.first > index)
 661             break;
 662         index += range.second - range.first;
 663     }
 664     return index;
 665 }
 666
 667 size_t IndexSet::unshift(size_t index) const noexcept
 668 {
 669     REALM_ASSERT_DEBUG(!contains(index));
 670     return index - count(0, index);
 671 }
 672
 673 void IndexSet::clear() noexcept
 674 {
 675     m_data.clear();
 676 }
 677
 678 IndexSet::iterator IndexSet::do_add(iterator it, size_t index)
 679 {
 680     verify();
 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
 685         return it;
 686     }
 687     if (more_before && std::prev(it)->second == index) {
 688         auto prev = std::prev(it);
 689         // index is immediately after an existing range
 690         prev.adjust(0, 1);
 691
 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));
 696         }
 697         return prev;
 698     }
 699     if (valid && it->first == index + 1) {
 700         // index is immediately before an existing range
 701         it.adjust(-1, 0);
 702         return it;
 703     }
 704
 705     // index is not next to an existing range
 706     return insert(it, {index, index + 1});
 707 }