Intermediate changes

commit_hash:b4d87cdddfb809ce2f3c9dfd1142cf6e92a83cb7

12 files changed, 315 insertions, 147 deletions

diff --git a/contrib/libs/croaring/.yandex_meta/override.nix b/contrib/libs/croaring/.yandex_meta/override.nix
index 1a2152ff69..fa1cd2b260 100644
--- a/contrib/libs/croaring/.yandex_meta/override.nix
+++ b/contrib/libs/croaring/.yandex_meta/override.nix
@@ -1,12 +1,12 @@
 pkgs: attrs: with pkgs; with attrs; rec {
   pname = "croaring";
-  version = "4.1.7";
+  version = "4.2.0";
 
   src = fetchFromGitHub {
     owner = "RoaringBitmap";
     repo = "CRoaring";
     rev = "v${version}";
-    hash = "sha256-vven8MrN0GRI3lz4zgquPE+5nBYxVaeY9SalKweux90=";
+    hash = "sha256-PzwtQDAsnRGIjeb3Ax6qqXtdEqtwaCWsj6g46J3Oqm0=";
   };
 
   patches = [];
diff --git a/contrib/libs/croaring/cpp/roaring.hh b/contrib/libs/croaring/cpp/roaring.hh
index 231dc5bd4f..8a3b8b6892 100644
--- a/contrib/libs/croaring/cpp/roaring.hh
+++ b/contrib/libs/croaring/cpp/roaring.hh
@@ -7,6 +7,7 @@ A C++ header for Roaring Bitmaps.
 #include <algorithm>
 #include <cstdarg>
 #include <initializer_list>
+#include <limits>
 #include <new>
 #include <stdexcept>
 #include <string>
@@ -39,7 +40,10 @@ A C++ header for Roaring Bitmaps.
 
 namespace roaring {
 
-class RoaringSetBitForwardIterator;
+class RoaringSetBitBiDirectionalIterator;
+
+/** DEPRECATED, use `RoaringSetBitBiDirectionalIterator`. */
+using RoaringSetBitForwardIterator = RoaringSetBitBiDirectionalIterator;
 
 /**
  * A bit of context usable with `*Bulk()` functions.
@@ -92,6 +96,16 @@ class Roaring {
     }
 
     /**
+     * Construct a roaring object by taking control of a malloc()'d C struct.
+     *
+     * Passing a NULL pointer is unsafe.
+     * The pointer to the C struct will be invalid after the call.
+     */
+    explicit Roaring(roaring_bitmap_t *s) noexcept : roaring(*s) {
+        roaring_free(s);  // deallocate the passed-in pointer
+    }
+
+    /**
      * Copy constructor.
      * It may throw std::runtime_error if there is insufficient memory.
      */
@@ -119,16 +133,6 @@ class Roaring {
     }
 
     /**
-     * Construct a roaring object by taking control of a malloc()'d C struct.
-     *
-     * Passing a NULL pointer is unsafe.
-     * The pointer to the C struct will be invalid after the call.
-     */
-    explicit Roaring(roaring_bitmap_t *s) noexcept : roaring(*s) {
-        roaring_free(s);  // deallocate the passed-in pointer
-    }
-
-    /**
      * Construct a bitmap from a list of uint32_t values.
      */
     static Roaring bitmapOf(size_t n, ...) {
@@ -143,6 +147,44 @@ class Roaring {
     }
 
     /**
+     * Copies the content of the provided bitmap, and
+     * discard the current content.
+     * It may throw std::runtime_error if there is insufficient memory.
+     */
+    Roaring &operator=(const Roaring &r) {
+        if (!api::roaring_bitmap_overwrite(&roaring, &r.roaring)) {
+            ROARING_TERMINATE("failed memory alloc in assignment");
+        }
+        api::roaring_bitmap_set_copy_on_write(
+            &roaring, api::roaring_bitmap_get_copy_on_write(&r.roaring));
+        return *this;
+    }
+
+    /**
+     * Moves the content of the provided bitmap, and
+     * discard the current content.
+     */
+    Roaring &operator=(Roaring &&r) noexcept {
+        api::roaring_bitmap_clear(&roaring);  // free this class's allocations
+
+        // !!! See notes in the Move Constructor regarding roaring_bitmap_move()
+        //
+        roaring = r.roaring;
+        api::roaring_bitmap_init_cleared(&r.roaring);
+
+        return *this;
+    }
+
+    /**
+     * Assignment from an initializer list.
+     */
+    Roaring &operator=(std::initializer_list<uint32_t> l) {
+        // Delegate to move assignment operator
+        *this = Roaring(l);
+        return *this;
+    }
+
+    /**
      * Construct a bitmap from a list of uint32_t values.
      * E.g., bitmapOfList({1,2,3}).
      */
@@ -243,6 +285,11 @@ class Roaring {
     }
 
     /**
+     * Clears the bitmap.
+     */
+    void clear() { api::roaring_bitmap_clear(&roaring); }
+
+    /**
      * Return the largest value (if not empty)
      */
     uint32_t maximum() const noexcept {
@@ -270,63 +317,9 @@ class Roaring {
         return api::roaring_bitmap_contains_range(&roaring, x, y);
     }
 
-    /**
-     * Destructor.  By contract, calling roaring_bitmap_clear() is enough to
-     * release all auxiliary memory used by the structure.
-     */
-    ~Roaring() {
-        if (!(roaring.high_low_container.flags & ROARING_FLAG_FROZEN)) {
-            api::roaring_bitmap_clear(&roaring);
-        } else {
-            // The roaring member variable copies the `roaring_bitmap_t` and
-            // nested `roaring_array_t` structures by value and is freed in the
-            // constructor, however the underlying memory arena used for the
-            // container data is not freed with it. Here we derive the arena
-            // pointer from the second arena allocation in
-            // `roaring_bitmap_frozen_view` and free it as well.
-            roaring_bitmap_free(
-                (roaring_bitmap_t *)((char *)
-                                         roaring.high_low_container.containers -
-                                     sizeof(roaring_bitmap_t)));
-        }
-    }
-
-    /**
-     * Copies the content of the provided bitmap, and
-     * discard the current content.
-     * It may throw std::runtime_error if there is insufficient memory.
-     */
-    Roaring &operator=(const Roaring &r) {
-        if (!api::roaring_bitmap_overwrite(&roaring, &r.roaring)) {
-            ROARING_TERMINATE("failed memory alloc in assignment");
-        }
-        api::roaring_bitmap_set_copy_on_write(
-            &roaring, api::roaring_bitmap_get_copy_on_write(&r.roaring));
-        return *this;
-    }
-
-    /**
-     * Moves the content of the provided bitmap, and
-     * discard the current content.
-     */
-    Roaring &operator=(Roaring &&r) noexcept {
-        api::roaring_bitmap_clear(&roaring);  // free this class's allocations
-
-        // !!! See notes in the Move Constructor regarding roaring_bitmap_move()
-        //
-        roaring = r.roaring;
-        api::roaring_bitmap_init_cleared(&r.roaring);
-
-        return *this;
-    }
-
-    /**
-     * Assignment from an initializer list.
-     */
-    Roaring &operator=(std::initializer_list<uint32_t> l) {
-        // Delegate to move assignment operator
-        *this = Roaring(l);
-        return *this;
+    bool containsRangeClosed(const uint32_t x,
+                             const uint32_t y) const noexcept {
+        return api::roaring_bitmap_contains_range_closed(&roaring, x, y);
     }
 
     /**
@@ -394,6 +387,16 @@ class Roaring {
     }
 
     /**
+     * Returns true if the bitmap is full (cardinality is uint32_t max + 1).
+     * we put std::numeric_limits<>::max/min in parentheses
+     * to avoid a clash with the Windows.h header under Windows.
+     */
+    bool isFull() const noexcept {
+        return api::roaring_bitmap_get_cardinality(&roaring) ==
+               ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1;
+    }
+
+    /**
      * Returns true if the bitmap is subset of the other.
      */
     bool isSubset(const Roaring &r) const noexcept {
@@ -443,8 +446,8 @@ class Roaring {
      * [range_start, range_end]. Areas outside the interval are unchanged.
      */
     void flipClosed(uint32_t range_start, uint32_t range_end) noexcept {
-        api::roaring_bitmap_flip_inplace(&roaring, range_start,
-                                         uint64_t(range_end) + 1);
+        api::roaring_bitmap_flip_inplace_closed(&roaring, range_start,
+                                                range_end);
     }
 
     /**
@@ -868,7 +871,30 @@ class Roaring {
         return ans;
     }
 
-    typedef RoaringSetBitForwardIterator const_iterator;
+    /**
+     * Destructor.  By contract, calling roaring_bitmap_clear() is enough to
+     * release all auxiliary memory used by the structure.
+     */
+    ~Roaring() {
+        if (!(roaring.high_low_container.flags & ROARING_FLAG_FROZEN)) {
+            api::roaring_bitmap_clear(&roaring);
+        } else {
+            // The roaring member variable copies the `roaring_bitmap_t` and
+            // nested `roaring_array_t` structures by value and is freed in the
+            // constructor, however the underlying memory arena used for the
+            // container data is not freed with it. Here we derive the arena
+            // pointer from the second arena allocation in
+            // `roaring_bitmap_frozen_view` and free it as well.
+            roaring_bitmap_free(
+                (roaring_bitmap_t *)((char *)
+                                         roaring.high_low_container.containers -
+                                     sizeof(roaring_bitmap_t)));
+        }
+    }
+
+    friend class RoaringSetBitBiDirectionalIterator;
+    typedef RoaringSetBitBiDirectionalIterator const_iterator;
+    typedef RoaringSetBitBiDirectionalIterator const_bidirectional_iterator;
 
     /**
      * Returns an iterator that can be used to access the position of the set
@@ -893,14 +919,26 @@ class Roaring {
 /**
  * Used to go through the set bits. Not optimally fast, but convenient.
  */
-class RoaringSetBitForwardIterator final {
+class RoaringSetBitBiDirectionalIterator final {
    public:
-    typedef std::forward_iterator_tag iterator_category;
+    typedef std::bidirectional_iterator_tag iterator_category;
     typedef uint32_t *pointer;
     typedef uint32_t &reference_type;
     typedef uint32_t value_type;
     typedef int32_t difference_type;
-    typedef RoaringSetBitForwardIterator type_of_iterator;
+    typedef RoaringSetBitBiDirectionalIterator type_of_iterator;
+
+    explicit RoaringSetBitBiDirectionalIterator(const Roaring &parent,
+                                                bool exhausted = false) {
+        if (exhausted) {
+            i.parent = &parent.roaring;
+            i.container_index = INT32_MAX;
+            i.has_value = false;
+            i.current_value = UINT32_MAX;
+        } else {
+            api::roaring_iterator_init(&parent.roaring, &i);
+        }
+    }
 
     /**
      * Provides the location of the set bit.
@@ -931,66 +969,60 @@ class RoaringSetBitForwardIterator final {
         return i.current_value >= *o;
     }
 
-    /**
-     * Move the iterator to the first value >= val.
-     */
-    void equalorlarger(uint32_t val) {
-        api::roaring_uint32_iterator_move_equalorlarger(&i, val);
-    }
-
     type_of_iterator &operator++() {  // ++i, must returned inc. value
         api::roaring_uint32_iterator_advance(&i);
         return *this;
     }
 
     type_of_iterator operator++(int) {  // i++, must return orig. value
-        RoaringSetBitForwardIterator orig(*this);
+        RoaringSetBitBiDirectionalIterator orig(*this);
         api::roaring_uint32_iterator_advance(&i);
         return orig;
     }
 
+    /**
+     * Move the iterator to the first value >= val.
+     * Return true if there is such a value.
+     */
+    bool move_equalorlarger(value_type val) {
+        return api::roaring_uint32_iterator_move_equalorlarger(&i, val);
+    }
+
+    /** DEPRECATED, use `move_equalorlarger`.*/
+    CROARING_DEPRECATED void equalorlarger(uint32_t val) {
+        api::roaring_uint32_iterator_move_equalorlarger(&i, val);
+    }
+
     type_of_iterator &operator--() {  // prefix --
         api::roaring_uint32_iterator_previous(&i);
         return *this;
     }
 
     type_of_iterator operator--(int) {  // postfix --
-        RoaringSetBitForwardIterator orig(*this);
+        RoaringSetBitBiDirectionalIterator orig(*this);
         api::roaring_uint32_iterator_previous(&i);
         return orig;
     }
 
-    bool operator==(const RoaringSetBitForwardIterator &o) const {
+    bool operator==(const RoaringSetBitBiDirectionalIterator &o) const {
         return i.current_value == *o && i.has_value == o.i.has_value;
     }
 
-    bool operator!=(const RoaringSetBitForwardIterator &o) const {
+    bool operator!=(const RoaringSetBitBiDirectionalIterator &o) const {
         return i.current_value != *o || i.has_value != o.i.has_value;
     }
 
-    explicit RoaringSetBitForwardIterator(const Roaring &parent,
-                                          bool exhausted = false) {
-        if (exhausted) {
-            i.parent = &parent.roaring;
-            i.container_index = INT32_MAX;
-            i.has_value = false;
-            i.current_value = UINT32_MAX;
-        } else {
-            api::roaring_iterator_init(&parent.roaring, &i);
-        }
-    }
-
     api::roaring_uint32_iterator_t
         i{};  // The empty constructor silences warnings from pedantic static
               // analyzers.
 };
 
-inline RoaringSetBitForwardIterator Roaring::begin() const {
-    return RoaringSetBitForwardIterator(*this);
+inline RoaringSetBitBiDirectionalIterator Roaring::begin() const {
+    return RoaringSetBitBiDirectionalIterator(*this);
 }
 
-inline RoaringSetBitForwardIterator &Roaring::end() const {
-    static RoaringSetBitForwardIterator e(*this, true);
+inline RoaringSetBitBiDirectionalIterator &Roaring::end() const {
+    static RoaringSetBitBiDirectionalIterator e(*this, true);
     return e;
 }
 
diff --git a/contrib/libs/croaring/cpp/roaring64map.hh b/contrib/libs/croaring/cpp/roaring64map.hh
index 46e726a2d9..7de53cbd45 100644
--- a/contrib/libs/croaring/cpp/roaring64map.hh
+++ b/contrib/libs/croaring/cpp/roaring64map.hh
@@ -493,6 +493,8 @@ class Roaring64Map {
         return iter->second.contains(lowBytes(x));
     }
 
+    // TODO: implement `containsRange`
+
     /**
      * Compute the intersection of the current bitmap and the provided bitmap,
      * writing the result in the current bitmap. The provided bitmap is not
@@ -785,17 +787,11 @@ class Roaring64Map {
         // to avoid a clash with the Windows.h header under Windows
         return roarings.size() ==
                        ((uint64_t)(std::numeric_limits<uint32_t>::max)()) + 1
-                   ? std::all_of(
-                         roarings.cbegin(), roarings.cend(),
-                         [](const std::pair<const uint32_t, Roaring>
-                                &roaring_map_entry) {
-                             // roarings within map are saturated if cardinality
-                             // is uint32_t max + 1
-                             return roaring_map_entry.second.cardinality() ==
-                                    ((uint64_t)(std::numeric_limits<
-                                                uint32_t>::max)()) +
-                                        1;
-                         })
+                   ? std::all_of(roarings.cbegin(), roarings.cend(),
+                                 [](const std::pair<const uint32_t, Roaring>
+                                        &roaring_map_entry) {
+                                     return roaring_map_entry.second.isFull();
+                                 })
                    : false;
     }
 
@@ -1712,6 +1708,8 @@ class Roaring64Map {
 
 /**
  * Used to go through the set bits. Not optimally fast, but convenient.
+ *
+ * Recommend to explicitly construct this iterator.
  */
 class Roaring64MapSetBitBiDirectionalIterator {
    public:
@@ -1790,7 +1788,11 @@ class Roaring64MapSetBitBiDirectionalIterator {
         return orig;
     }
 
-    bool move(const value_type &x) {
+    /**
+     * Move the iterator to the first value >= val.
+     * Return true if there is such a value.
+     */
+    bool move_equalorlarger(const value_type &x) {
         map_iter = p->lower_bound(Roaring64Map::highBytes(x));
         if (map_iter != p->cend()) {
             roaring_iterator_init(&map_iter->second.roaring, &i);
@@ -1807,6 +1809,11 @@ class Roaring64MapSetBitBiDirectionalIterator {
         return false;
     }
 
+    /** DEPRECATED, use `move_equalorlarger`. */
+    CROARING_DEPRECATED bool move(const value_type &x) {
+        return move_equalorlarger(x);
+    }
+
     type_of_iterator &operator--() {  //  --i, must return dec.value
         if (map_iter == p->cend()) {
             --map_iter;
diff --git a/contrib/libs/croaring/include/roaring/bitset/bitset.h b/contrib/libs/croaring/include/roaring/bitset/bitset.h
index c57d73d108..38ed39e806 100644
--- a/contrib/libs/croaring/include/roaring/bitset/bitset.h
+++ b/contrib/libs/croaring/include/roaring/bitset/bitset.h
@@ -131,7 +131,10 @@ inline bool bitset_get(const bitset_t *bitset, size_t i) {
 /* Count number of bits set.  */
 size_t bitset_count(const bitset_t *bitset);
 
-/* Find the index of the first bit set. Or zero if the bitset is empty.  */
+/* Returns true if no bit is set.  */
+bool bitset_empty(const bitset_t *bitset);
+
+/* Find the index of the first bit set. Or SIZE_MAX if the bitset is empty.  */
 size_t bitset_minimum(const bitset_t *bitset);
 
 /* Find the index of the last bit set. Or zero if the bitset is empty.  */
diff --git a/contrib/libs/croaring/include/roaring/roaring.h b/contrib/libs/croaring/include/roaring/roaring.h
index 4256ad0ca5..7880e3f3d9 100644
--- a/contrib/libs/croaring/include/roaring/roaring.h
+++ b/contrib/libs/croaring/include/roaring/roaring.h
@@ -387,7 +387,9 @@ void roaring_bitmap_add_range_closed(roaring_bitmap_t *r, uint32_t min,
  */
 inline void roaring_bitmap_add_range(roaring_bitmap_t *r, uint64_t min,
                                      uint64_t max) {
-    if (max <= min) return;
+    if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
+        return;
+    }
     roaring_bitmap_add_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
 }
 
@@ -407,7 +409,9 @@ void roaring_bitmap_remove_range_closed(roaring_bitmap_t *r, uint32_t min,
  */
 inline void roaring_bitmap_remove_range(roaring_bitmap_t *r, uint64_t min,
                                         uint64_t max) {
-    if (max <= min) return;
+    if (max <= min || min > (uint64_t)UINT32_MAX + 1) {
+        return;
+    }
     roaring_bitmap_remove_range_closed(r, (uint32_t)min, (uint32_t)(max - 1));
 }
 
@@ -436,6 +440,14 @@ bool roaring_bitmap_contains_range(const roaring_bitmap_t *r,
                                    uint64_t range_start, uint64_t range_end);
 
 /**
+ * Check whether a range of values from range_start (included)
+ * to range_end (included) is present
+ */
+bool roaring_bitmap_contains_range_closed(const roaring_bitmap_t *r,
+                                          uint32_t range_start,
+                                          uint32_t range_end);
+
+/**
  * Check if an items is present, using context from a previous insert or search
  * for speed optimization.
  *
@@ -467,6 +479,12 @@ uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r,
                                           uint64_t range_end);
 
 /**
+ * Returns the number of elements in the range [range_start, range_end].
+ */
+uint64_t roaring_bitmap_range_cardinality_closed(const roaring_bitmap_t *r,
+                                                 uint32_t range_start,
+                                                 uint32_t range_end);
+/**
  * Returns true if the bitmap is empty (cardinality is zero).
  */
 bool roaring_bitmap_is_empty(const roaring_bitmap_t *r);
@@ -868,6 +886,14 @@ roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *r1,
                                       uint64_t range_start, uint64_t range_end);
 
 /**
+ * Compute the negation of the bitmap in the interval [range_start, range_end].
+ * The number of negated values is range_end - range_start + 1.
+ * Areas outside the range are passed through unchanged.
+ */
+roaring_bitmap_t *roaring_bitmap_flip_closed(const roaring_bitmap_t *x1,
+                                             uint32_t range_start,
+                                             uint32_t range_end);
+/**
  * compute (in place) the negation of the roaring bitmap within a specified
  * interval: [range_start, range_end). The number of negated values is
  * range_end - range_start.
@@ -877,6 +903,16 @@ void roaring_bitmap_flip_inplace(roaring_bitmap_t *r1, uint64_t range_start,
                                  uint64_t range_end);
 
 /**
+ * compute (in place) the negation of the roaring bitmap within a specified
+ * interval: [range_start, range_end]. The number of negated values is
+ * range_end - range_start + 1.
+ * Areas outside the range are passed through unchanged.
+ */
+void roaring_bitmap_flip_inplace_closed(roaring_bitmap_t *r1,
+                                        uint32_t range_start,
+                                        uint32_t range_end);
+
+/**
  * Selects the element at index 'rank' where the smallest element is at index 0.
  * If the size of the roaring bitmap is strictly greater than rank, then this
  * function returns true and sets element to the element of given rank.
diff --git a/contrib/libs/croaring/include/roaring/roaring_version.h b/contrib/libs/croaring/include/roaring/roaring_version.h
index f211339f45..33926a2102 100644
--- a/contrib/libs/croaring/include/roaring/roaring_version.h
+++ b/contrib/libs/croaring/include/roaring/roaring_version.h
@@ -2,11 +2,11 @@
 // /include/roaring/roaring_version.h automatically generated by release.py, do not change by hand
 #ifndef ROARING_INCLUDE_ROARING_VERSION
 #define ROARING_INCLUDE_ROARING_VERSION
-#define ROARING_VERSION "4.1.7"
+#define ROARING_VERSION "4.2.0"
 enum {
     ROARING_VERSION_MAJOR = 4,
-    ROARING_VERSION_MINOR = 1,
-    ROARING_VERSION_REVISION = 7
+    ROARING_VERSION_MINOR = 2,
+    ROARING_VERSION_REVISION = 0
 };
 #endif // ROARING_INCLUDE_ROARING_VERSION
 // clang-format on
\ No newline at end of file
diff --git a/contrib/libs/croaring/src/bitset.c b/contrib/libs/croaring/src/bitset.c
index 5d23af1e7b..96fee905ce 100644
--- a/contrib/libs/croaring/src/bitset.c
+++ b/contrib/libs/croaring/src/bitset.c
@@ -216,6 +216,15 @@ bool bitset_inplace_union(bitset_t *CROARING_CBITSET_RESTRICT b1,
     return true;
 }
 
+bool bitset_empty(const bitset_t *bitset) {
+    for (size_t k = 0; k < bitset->arraysize; k++) {
+        if (bitset->array[k] != 0) {
+            return false;
+        }
+    }
+    return true;
+}
+
 size_t bitset_minimum(const bitset_t *bitset) {
     for (size_t k = 0; k < bitset->arraysize; k++) {
         uint64_t w = bitset->array[k];
@@ -223,7 +232,7 @@ size_t bitset_minimum(const bitset_t *bitset) {
             return roaring_trailing_zeroes(w) + k * 64;
         }
     }
-    return 0;
+    return SIZE_MAX;
 }
 
 bool bitset_grow(bitset_t *bitset, size_t newarraysize) {
diff --git a/contrib/libs/croaring/src/roaring.c b/contrib/libs/croaring/src/roaring.c
index 5a71fd39c3..8f6b5a4f37 100644
--- a/contrib/libs/croaring/src/roaring.c
+++ b/contrib/libs/croaring/src/roaring.c
@@ -1,5 +1,6 @@
 #include <assert.h>
 #include <inttypes.h>
+#include <limits.h>
 #include <stdarg.h>
 #include <stdint.h>
 #include <stdio.h>
@@ -1330,15 +1331,22 @@ uint64_t roaring_bitmap_get_cardinality(const roaring_bitmap_t *r) {
 uint64_t roaring_bitmap_range_cardinality(const roaring_bitmap_t *r,
                                           uint64_t range_start,
                                           uint64_t range_end) {
+    if (range_start >= range_end || range_start > (uint64_t)UINT32_MAX + 1) {
+        return 0;
+    }
+    return roaring_bitmap_range_cardinality_closed(r, (uint32_t)range_start,
+                                                   (uint32_t)(range_end - 1));
+}
+
+uint64_t roaring_bitmap_range_cardinality_closed(const roaring_bitmap_t *r,
+                                                 uint32_t range_start,
+                                                 uint32_t range_end) {
     const roaring_array_t *ra = &r->high_low_container;
 
-    if (range_end > UINT32_MAX) {
-        range_end = UINT32_MAX + UINT64_C(1);
-    }
-    if (range_start >= range_end) {
+    if (range_start > range_end) {
         return 0;
     }
-    range_end--;  // make range_end inclusive
+
     // now we have: 0 <= range_start <= range_end <= UINT32_MAX
 
     uint16_t minhb = (uint16_t)(range_start >> 16);
@@ -2005,11 +2013,18 @@ static void inplace_fully_flip_container(roaring_array_t *x1_arr, uint16_t hb) {
 roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *x1,
                                       uint64_t range_start,
                                       uint64_t range_end) {
-    if (range_start >= range_end) {
+    if (range_start >= range_end || range_start > (uint64_t)UINT32_MAX + 1) {
         return roaring_bitmap_copy(x1);
     }
-    if (range_end >= UINT64_C(0x100000000)) {
-        range_end = UINT64_C(0x100000000);
+    return roaring_bitmap_flip_closed(x1, (uint32_t)range_start,
+                                      (uint32_t)(range_end - 1));
+}
+
+roaring_bitmap_t *roaring_bitmap_flip_closed(const roaring_bitmap_t *x1,
+                                             uint32_t range_start,
+                                             uint32_t range_end) {
+    if (range_start > range_end) {
+        return roaring_bitmap_copy(x1);
     }
 
     roaring_bitmap_t *ans = roaring_bitmap_create();
@@ -2017,8 +2032,8 @@ roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *x1,
 
     uint16_t hb_start = (uint16_t)(range_start >> 16);
     const uint16_t lb_start = (uint16_t)range_start;  // & 0xFFFF;
-    uint16_t hb_end = (uint16_t)((range_end - 1) >> 16);
-    const uint16_t lb_end = (uint16_t)(range_end - 1);  // & 0xFFFF;
+    uint16_t hb_end = (uint16_t)(range_end >> 16);
+    const uint16_t lb_end = (uint16_t)range_end;  // & 0xFFFF;
 
     ra_append_copies_until(&ans->high_low_container, &x1->high_low_container,
                            hb_start, is_cow(x1));
@@ -2059,17 +2074,24 @@ roaring_bitmap_t *roaring_bitmap_flip(const roaring_bitmap_t *x1,
 
 void roaring_bitmap_flip_inplace(roaring_bitmap_t *x1, uint64_t range_start,
                                  uint64_t range_end) {
-    if (range_start >= range_end) {
-        return;  // empty range
+    if (range_start >= range_end || range_start > (uint64_t)UINT32_MAX + 1) {
+        return;
     }
-    if (range_end >= UINT64_C(0x100000000)) {
-        range_end = UINT64_C(0x100000000);
+    roaring_bitmap_flip_inplace_closed(x1, (uint32_t)range_start,
+                                       (uint32_t)(range_end - 1));
+}
+
+void roaring_bitmap_flip_inplace_closed(roaring_bitmap_t *x1,
+                                        uint32_t range_start,
+                                        uint32_t range_end) {
+    if (range_start > range_end) {
+        return;  // empty range
     }
 
     uint16_t hb_start = (uint16_t)(range_start >> 16);
     const uint16_t lb_start = (uint16_t)range_start;
-    uint16_t hb_end = (uint16_t)((range_end - 1) >> 16);
-    const uint16_t lb_end = (uint16_t)(range_end - 1);
+    uint16_t hb_end = (uint16_t)(range_end >> 16);
+    const uint16_t lb_end = (uint16_t)range_end;
 
     if (hb_start == hb_end) {
         inplace_flip_container(&x1->high_low_container, hb_start, lb_start,
@@ -2827,15 +2849,28 @@ bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) {
  */
 bool roaring_bitmap_contains_range(const roaring_bitmap_t *r,
                                    uint64_t range_start, uint64_t range_end) {
-    if (range_end >= UINT64_C(0x100000000)) {
-        range_end = UINT64_C(0x100000000);
+    if (range_start >= range_end || range_start > (uint64_t)UINT32_MAX + 1) {
+        return true;
     }
-    if (range_start >= range_end)
-        return true;  // empty range are always contained!
-    if (range_end - range_start == 1)
+    return roaring_bitmap_contains_range_closed(r, (uint32_t)range_start,
+                                                (uint32_t)(range_end - 1));
+}
+
+/**
+ * Check whether a range of values from range_start (included) to range_end
+ * (included) is present
+ */
+bool roaring_bitmap_contains_range_closed(const roaring_bitmap_t *r,
+                                          uint32_t range_start,
+                                          uint32_t range_end) {
+    if (range_start > range_end) {
+        return true;
+    }  // empty range are always contained!
+    if (range_end == range_start) {
         return roaring_bitmap_contains(r, (uint32_t)range_start);
+    }
     uint16_t hb_rs = (uint16_t)(range_start >> 16);
-    uint16_t hb_re = (uint16_t)((range_end - 1) >> 16);
+    uint16_t hb_re = (uint16_t)(range_end >> 16);
     const int32_t span = hb_re - hb_rs;
     const int32_t hlc_sz = ra_get_size(&r->high_low_container);
     if (hlc_sz < span + 1) {
@@ -2847,7 +2882,7 @@ bool roaring_bitmap_contains_range(const roaring_bitmap_t *r,
         return false;
     }
     const uint32_t lb_rs = range_start & 0xFFFF;
-    const uint32_t lb_re = ((range_end - 1) & 0xFFFF) + 1;
+    const uint32_t lb_re = (range_end & 0xFFFF) + 1;
     uint8_t type;
     container_t *c =
         ra_get_container_at_index(&r->high_low_container, (uint16_t)is, &type);
diff --git a/contrib/libs/croaring/ya.make b/contrib/libs/croaring/ya.make
index 03863f4f54..78b8b40c9d 100644
--- a/contrib/libs/croaring/ya.make
+++ b/contrib/libs/croaring/ya.make
@@ -10,9 +10,9 @@ LICENSE(
 
 LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
 
-VERSION(4.1.7)
+VERSION(4.2.0)
 
-ORIGINAL_SOURCE(https://github.com/RoaringBitmap/CRoaring/archive/v4.1.7.tar.gz)
+ORIGINAL_SOURCE(https://github.com/RoaringBitmap/CRoaring/archive/v4.2.0.tar.gz)
 
 ADDINCL(
     GLOBAL contrib/libs/croaring/include
diff --git a/contrib/libs/llvm16/include/llvm/Config/llvm-config-linux-aarch64.h b/contrib/libs/llvm16/include/llvm/Config/llvm-config-linux-aarch64.h
new file mode 100644
index 0000000000..708cd9addd
--- /dev/null
+++ b/contrib/libs/llvm16/include/llvm/Config/llvm-config-linux-aarch64.h
@@ -0,0 +1,35 @@
+#pragma once
+
+#include "llvm-config-linux.h"
+
+/* Host triple LLVM will be executed on */
+#undef LLVM_HOST_TRIPLE
+#define LLVM_HOST_TRIPLE "aarch64-unknown-linux-gnu"
+
+/* LLVM architecture name for the native architecture, if available */
+#undef LLVM_NATIVE_ARCH
+#define LLVM_NATIVE_ARCH AArch64
+
+/* LLVM name for the native AsmParser init function, if available */
+#undef LLVM_NATIVE_ASMPARSER
+#define LLVM_NATIVE_ASMPARSER LLVMInitializeAArch64AsmParser
+
+/* LLVM name for the native AsmPrinter init function, if available */
+#undef LLVM_NATIVE_ASMPRINTER
+#define LLVM_NATIVE_ASMPRINTER LLVMInitializeAArch64AsmPrinter
+
+/* LLVM name for the native Disassembler init function, if available */
+#undef LLVM_NATIVE_DISASSEMBLER
+#define LLVM_NATIVE_DISASSEMBLER LLVMInitializeAArch64Disassembler
+
+/* LLVM name for the native Target init function, if available */
+#undef LLVM_NATIVE_TARGET
+#define LLVM_NATIVE_TARGET LLVMInitializeAArch64Target
+
+/* LLVM name for the native TargetInfo init function, if available */
+#undef LLVM_NATIVE_TARGETINFO
+#define LLVM_NATIVE_TARGETINFO LLVMInitializeAArch64TargetInfo
+
+/* LLVM name for the native target MC init function, if available */
+#undef LLVM_NATIVE_TARGETMC
+#define LLVM_NATIVE_TARGETMC LLVMInitializeAArch64TargetMC
diff --git a/contrib/libs/llvm16/include/llvm/Config/llvm-config.h b/contrib/libs/llvm16/include/llvm/Config/llvm-config.h
index 0ab964dcd1..06f9c57d27 100644
--- a/contrib/libs/llvm16/include/llvm/Config/llvm-config.h
+++ b/contrib/libs/llvm16/include/llvm/Config/llvm-config.h
@@ -4,6 +4,8 @@
 #   include "llvm-config-osx.h"
 #elif defined(_MSC_VER)
 #   include "llvm-config-win.h"
+#elif defined(__linux__) && (defined(__aarch64__) || defined(_M_ARM64))
+#   include "llvm-config-linux-aarch64.h"
 #else
 #   include "llvm-config-linux.h"
 #endif
diff --git a/contrib/libs/llvm16/tools/lli/ya.make b/contrib/libs/llvm16/tools/lli/ya.make
index 3f2bcc8143..e172246e8b 100644
--- a/contrib/libs/llvm16/tools/lli/ya.make
+++ b/contrib/libs/llvm16/tools/lli/ya.make
@@ -76,6 +76,15 @@ IF (OS_LINUX)
     )
 ENDIF()
 
+IF (ARCH_AARCH64)
+    PEERDIR(
+        contrib/libs/llvm16/lib/Target/AArch64
+        contrib/libs/llvm16/lib/Target/AArch64/AsmParser
+        contrib/libs/llvm16/lib/Target/AArch64/MCTargetDesc
+        contrib/libs/llvm16/lib/Target/AArch64/TargetInfo
+    )
+ENDIF()
+
 ADDINCL(
     contrib/libs/llvm16/tools/lli
 )