Line data    Source code

       1             : // Copyright (c) 2023-2024 The Dash Core developers
       2             : // Distributed under the MIT software license, see the accompanying
       3             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4             : 
       5             : #include <util/ranges_set.h>
       6             : 
       7          12 : CRangesSet::Range::Range() : CRangesSet::Range::Range(0, 0) {}
       8             : 
       9     3117698 : CRangesSet::Range::Range(uint64_t begin, uint64_t end) :
      10     1558849 :     begin(begin),
      11     1558849 :     end(end)
      12     1558849 : {
      13     3117698 : }
      14             : 
      15      163458 : bool CRangesSet::Add(uint64_t value)
      16             : {
      17      163458 :     if (Contains(value)) return false;
      18             : 
      19             :     // If element is not in CRangesSet, we need to add a new range [value, value + 1)
      20             :     // But this operation can cause 2 operation of merge (total 3 cases):
      21             :     // - if there're exist ranges [x, value) and [value + 1, y) than
      22             :     //   all 3 of them should be merged in one range [x, y)
      23             :     // - if there's exist a range [x, value) - we need to replace it to new range [x, value + 1)
      24             :     // - if there's exist a range [value + 1, y) - we need to replace it to new range [value, y)
      25      163458 :     Range new_range{value, value + 1};
      26      163458 :     auto it = ranges.lower_bound({value, value});
      27      163458 :     if (it != ranges.begin()) {
      28      163318 :         auto prev = it;
      29      163318 :         --prev;
      30             : 
      31      163318 :         if (prev->end == value) {
      32       57125 :             new_range.begin = prev->begin;
      33       57125 :             it = ranges.erase(prev);
      34       57125 :         }
      35      163318 :     }
      36      163458 :     const auto next = it;
      37      163458 :     if (next != ranges.end()) {
      38      163208 :         if (next->begin == value + 1) {
      39       57814 :             new_range.end = next->end;
      40       57814 :             ranges.erase(next);
      41       57814 :         }
      42      163208 :     }
      43      163458 :     const auto ret = ranges.insert(new_range);
      44      163458 :     assert(ret.second);
      45      163458 :     return true;
      46      163458 : }
      47             : 
      48       98838 : bool CRangesSet::Remove(uint64_t value)
      49             : {
      50       98838 :     if (!Contains(value)) return false;
      51             : 
      52             :     // If element is in CRangesSet, there's possible 2 cases:
      53             :     // - value in the range that is lower-bound (if begin of that range equals to `value`)
      54             :     // - value in the previous range (otherwise)
      55       98838 :     auto it = ranges.lower_bound({value, value});
      56             : 
      57       98838 :     if (it == ranges.end() || it->begin != value) {
      58       41765 :         assert(it != ranges.begin());
      59       41765 :         --it;
      60       41765 :     }
      61             : 
      62       98838 :     const Range current_range = *it;
      63       98838 :     ranges.erase(it);
      64       98838 :     if (current_range.begin != value) {
      65       41765 :         const auto ret = ranges.insert({current_range.begin, value});
      66       41765 :         assert(ret.second);
      67       41765 :     }
      68       98838 :     if (value + 1 != current_range.end) {
      69       41400 :         const auto ret = ranges.insert({value + 1, current_range.end});
      70       41400 :         assert(ret.second);
      71       41400 :     }
      72       98838 :     return true;
      73       98838 : }
      74             : 
      75           0 : bool CRangesSet::IsEmpty() const noexcept
      76             : {
      77           0 :     return ranges.empty();
      78             : }
      79             : 
      80      262154 : size_t CRangesSet::Size() const noexcept
      81             : {
      82      262154 :     size_t result{0};
      83  2509992705 :     for (auto i : ranges) {
      84  2509730551 :         result += i.end - i.begin;
      85             :     }
      86      262154 :     return result;
      87             : }
      88             : 
      89     1049918 : bool CRangesSet::Contains(uint64_t value) const noexcept
      90             : {
      91     1049918 :     const auto it = ranges.lower_bound({value, value});
      92     1049918 :     if (it != ranges.end() && it->begin == value) return true;
      93      772450 :     if (it == ranges.begin()) return false;
      94      771953 :     auto prev = it;
      95      771953 :     --prev;
      96      771953 :     return prev->begin <= value && prev->end > value;
      97     1049918 : }
      98             :