Line data    Source code

       1             : // Copyright (c) 2023 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             : #ifndef BITCOIN_UTIL_RANGES_SET_H
       6             : #define BITCOIN_UTIL_RANGES_SET_H
       7             : 
       8             : #include <hash.h>
       9             : #include <saltedhasher.h>
      10             : #include <serialize.h>
      11             : 
      12             : #include <set>
      13             : 
      14             : /**
      15             :  * The CRangesSet is a datastructure that keeps efficiently numbers as set of
      16             :  * continuous ranges of numbers.
      17             :  * CRangesSet let's to keep elements with gaps of any size while CSkipList has
      18             :  * limited capacity (total size of all gaps)
      19             :  *
      20             :  * The CRangesSet provides transaction guarantees: element can be added or
      21             :  * removed and data structure will be consistent. For case if any of these
      22             :  * operation failed (out-memory for example), the `assert` will be called to
      23             :  * terminate program.
      24             :  */
      25             : class CRangesSet
      26             : {
      27             :     // internal datastructure, doesn't have a reason to be publicly available
      28             :     struct Range
      29             :     {
      30             :         uint64_t begin;
      31             :         uint64_t end;
      32             :         Range();
      33             :         Range(uint64_t begin, uint64_t end);
      34    21946338 :         bool operator<(const Range& other) const
      35             :         {
      36    21946338 :             if (begin != other.begin) return begin < other.begin;
      37      334523 :             return end < other.end;
      38    21946338 :         }
      39             : 
      40           0 :         SERIALIZE_METHODS(Range, obj)
      41             :         {
      42           0 :             READWRITE(obj.begin);
      43           0 :             READWRITE(obj.end);
      44           0 :         }
      45             :     };
      46             : 
      47             :     std::set<Range> ranges;
      48             : 
      49             : public:
      50             :     /**
      51             :      * this function adds `value` to the datastructure.
      52             :      * it returns true if `add` succeed
      53             :      */
      54             :     [[nodiscard]] bool Add(uint64_t value);
      55             : 
      56             :     /**
      57             :      * this function returns true if `value` exists in the datastructure
      58             :      */
      59             :     [[nodiscard]] bool Contains(uint64_t value) const noexcept;
      60             : 
      61             :     /**
      62             :      * this function removes `value` from the datastructure.
      63             :      * it returns `false` if element didn't existed or removing failed by any reason
      64             :      */
      65             :     [[nodiscard]] bool Remove(uint64_t value);
      66             : 
      67             :     /**
      68             :      * Size() works with complexity O(N) times, avoid calling it without a good reason
      69             :      * Instead prefer to use IsEmpty()
      70             :      */
      71             :     [[nodiscard]] size_t Size() const noexcept;
      72             : 
      73             :     /**
      74             :      * IsEmpty() returns true if there's no any elements added
      75             :      */
      76             :     [[nodiscard]] bool IsEmpty() const noexcept;
      77             : 
      78          48 :     SERIALIZE_METHODS(CRangesSet, obj)
      79             :     {
      80          16 :         READWRITE(obj.ranges);
      81          16 :     }
      82             : };
      83             : 
      84             : #endif // BITCOIN_UTIL_RANGES_SET_H