Update contrib/libs/croaring to 4.5.0

commit_hash:541e42e55c2908c8e0ad09bdd3f12b2d7bb8cf09

8 files changed, 163 insertions, 154 deletions

diff --git a/contrib/libs/croaring/.yandex_meta/override.nix b/contrib/libs/croaring/.yandex_meta/override.nix
index 75344e401c0..71b6ee2a6b0 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.4.3";
+  version = "4.5.0";
 
   src = fetchFromGitHub {
     owner = "RoaringBitmap";
     repo = "CRoaring";
     rev = "v${version}";
-    hash = "sha256-1qR6uo/NYxwM99i7Ib9dSbD4k8fN2ZmrWh39pIQNJv4=";
+    hash = "sha256-hzEI/PJSE1B7pQLCUF4aRh+cTgX7wtJYI4QF07OlDoo=";
   };
 
   patches = [];
diff --git a/contrib/libs/croaring/include/roaring/containers/container_defs.h b/contrib/libs/croaring/include/roaring/containers/container_defs.h
index 402bad787d2..91f8e62c1ce 100644
--- a/contrib/libs/croaring/include/roaring/containers/container_defs.h
+++ b/contrib/libs/croaring/include/roaring/containers/container_defs.h
@@ -32,7 +32,6 @@ namespace internal {  // No extern "C" (contains template)
  * Then undefine the awkward macro so it's not used any more than it has to be.
  */
 typedef ROARING_CONTAINER_T container_t;
-#undef ROARING_CONTAINER_T
 
 /*
  * See ROARING_CONTAINER_T for notes on using container_t as a base class.
diff --git a/contrib/libs/croaring/include/roaring/containers/containers.h b/contrib/libs/croaring/include/roaring/containers/containers.h
index 5f7c789036f..a3afdc5c31a 100644
--- a/contrib/libs/croaring/include/roaring/containers/containers.h
+++ b/contrib/libs/croaring/include/roaring/containers/containers.h
@@ -2434,15 +2434,131 @@ roaring_container_iterator_t container_init_iterator_last(const container_t *c,
  * Moves the iterator to the next entry. Returns true and sets `value` if a
  * value is present.
  */
-bool container_iterator_next(const container_t *c, uint8_t typecode,
-                             roaring_container_iterator_t *it, uint16_t *value);
+inline bool container_iterator_next(const container_t *c, uint8_t typecode,
+                                    roaring_container_iterator_t *it,
+                                    uint16_t *value) {
+    switch (typecode) {
+        case BITSET_CONTAINER_TYPE: {
+            const bitset_container_t *bc = const_CAST_bitset(c);
+            it->index++;
+
+            uint32_t wordindex = it->index / 64;
+            if (wordindex >= BITSET_CONTAINER_SIZE_IN_WORDS) {
+                return false;
+            }
+
+            uint64_t word =
+                bc->words[wordindex] & (UINT64_MAX << (it->index % 64));
+            // next part could be optimized/simplified
+            while (word == 0 &&
+                   (wordindex + 1 < BITSET_CONTAINER_SIZE_IN_WORDS)) {
+                wordindex++;
+                word = bc->words[wordindex];
+            }
+            if (word != 0) {
+                it->index = wordindex * 64 + roaring_trailing_zeroes(word);
+                *value = it->index;
+                return true;
+            }
+            return false;
+        }
+        case ARRAY_CONTAINER_TYPE: {
+            const array_container_t *ac = const_CAST_array(c);
+            it->index++;
+            if (it->index < ac->cardinality) {
+                *value = ac->array[it->index];
+                return true;
+            }
+            return false;
+        }
+        case RUN_CONTAINER_TYPE: {
+            if (*value == UINT16_MAX) {  // Avoid overflow to zero
+                return false;
+            }
+
+            const run_container_t *rc = const_CAST_run(c);
+            uint32_t limit =
+                rc->runs[it->index].value + rc->runs[it->index].length;
+            if (*value < limit) {
+                (*value)++;
+                return true;
+            }
+
+            it->index++;
+            if (it->index < rc->n_runs) {
+                *value = rc->runs[it->index].value;
+                return true;
+            }
+            return false;
+        }
+        default:
+            assert(false);
+            roaring_unreachable;
+            return false;
+    }
+}
 
 /**
  * Moves the iterator to the previous entry. Returns true and sets `value` if a
  * value is present.
  */
-bool container_iterator_prev(const container_t *c, uint8_t typecode,
-                             roaring_container_iterator_t *it, uint16_t *value);
+inline bool container_iterator_prev(const container_t *c, uint8_t typecode,
+                                    roaring_container_iterator_t *it,
+                                    uint16_t *value) {
+    switch (typecode) {
+        case BITSET_CONTAINER_TYPE: {
+            if (--it->index < 0) {
+                return false;
+            }
+
+            const bitset_container_t *bc = const_CAST_bitset(c);
+            int32_t wordindex = it->index / 64;
+            uint64_t word =
+                bc->words[wordindex] & (UINT64_MAX >> (63 - (it->index % 64)));
+
+            while (word == 0 && --wordindex >= 0) {
+                word = bc->words[wordindex];
+            }
+            if (word == 0) {
+                return false;
+            }
+
+            it->index = (wordindex * 64) + (63 - roaring_leading_zeroes(word));
+            *value = it->index;
+            return true;
+        }
+        case ARRAY_CONTAINER_TYPE: {
+            if (--it->index < 0) {
+                return false;
+            }
+            const array_container_t *ac = const_CAST_array(c);
+            *value = ac->array[it->index];
+            return true;
+        }
+        case RUN_CONTAINER_TYPE: {
+            if (*value == 0) {
+                return false;
+            }
+
+            const run_container_t *rc = const_CAST_run(c);
+            (*value)--;
+            if (*value >= rc->runs[it->index].value) {
+                return true;
+            }
+
+            if (--it->index < 0) {
+                return false;
+            }
+
+            *value = rc->runs[it->index].value + rc->runs[it->index].length;
+            return true;
+        }
+        default:
+            assert(false);
+            roaring_unreachable;
+            return false;
+    }
+}
 
 /**
  * Moves the iterator to the smallest entry that is greater than or equal to
diff --git a/contrib/libs/croaring/include/roaring/roaring.h b/contrib/libs/croaring/include/roaring/roaring.h
index 9823a408b19..e3c718a88d5 100644
--- a/contrib/libs/croaring/include/roaring/roaring.h
+++ b/contrib/libs/croaring/include/roaring/roaring.h
@@ -13,8 +13,10 @@
 
 // Include other headers after roaring_types.h
 #include <roaring/bitset/bitset.h>
+#include <roaring/containers/containers.h>
 #include <roaring/memory.h>
 #include <roaring/portability.h>
+#include <roaring/roaring_array.h>
 #include <roaring/roaring_version.h>
 
 #ifdef __cplusplus
@@ -462,7 +464,27 @@ bool roaring_bitmap_remove_checked(roaring_bitmap_t *r, uint32_t x);
 /**
  * Check if value is present
  */
-bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val);
+inline bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) {
+    // For performance reasons, this function is inline and uses internal
+    // functions directly.
+#ifdef __cplusplus
+    using namespace ::roaring::internal;
+#endif
+    const uint16_t hb = val >> 16;
+    /*
+     * the next function call involves a binary search and lots of branching.
+     */
+    int32_t i = ra_get_index(&r->high_low_container, hb);
+    if (i < 0) return false;
+
+    uint8_t typecode;
+    // next call ought to be cheap
+    container_t *container = ra_get_container_at_index(&r->high_low_container,
+                                                       (uint16_t)i, &typecode);
+    // rest might be a tad expensive, possibly involving another round of binary
+    // search
+    return container_contains(container, val & 0xFFFF, typecode);
+}
 
 /**
  * Check whether a range of values from range_start (included)
@@ -1055,6 +1077,7 @@ while(i.has_value) {
   printf("value = %d\n", i.current_value);
   roaring_uint32_iterator_advance(&i);
 }
+roaring_uint32_iterator_free(&i);
 
 Obviously, if you modify the underlying bitmap, the iterator
 becomes invalid. So don't.
@@ -1107,7 +1130,7 @@ CROARING_DEPRECATED static inline void roaring_init_iterator_last(
 
 /**
  * Create an iterator object that can be used to iterate through the values.
- * Caller is responsible for calling `roaring_free_iterator()`.
+ * Caller is responsible for calling `roaring_uint32_iterator_free()`.
  *
  * The iterator is initialized (this function calls `roaring_iterator_init()`)
  * If there is a value, then this iterator points to the first value and
diff --git a/contrib/libs/croaring/include/roaring/roaring_version.h b/contrib/libs/croaring/include/roaring/roaring_version.h
index 98fd4fe827c..073bfb79847 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.4.3"
+#define ROARING_VERSION "4.5.0"
 enum {
     ROARING_VERSION_MAJOR = 4,
-    ROARING_VERSION_MINOR = 4,
-    ROARING_VERSION_REVISION = 3
+    ROARING_VERSION_MINOR = 5,
+    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/containers/containers.c b/contrib/libs/croaring/src/containers/containers.c
index 8a235ad38b2..0daa7ec81a2 100644
--- a/contrib/libs/croaring/src/containers/containers.c
+++ b/contrib/libs/croaring/src/containers/containers.c
@@ -1,4 +1,3 @@
-
 #include <roaring/containers/containers.h>
 #include <roaring/memory.h>
 
@@ -44,6 +43,14 @@ extern inline container_t *container_iandnot(container_t *c1, uint8_t type1,
                                              uint8_t type2,
                                              uint8_t *result_type);
 
+extern bool container_iterator_next(const container_t *c, uint8_t typecode,
+                                    roaring_container_iterator_t *it,
+                                    uint16_t *value);
+
+extern bool container_iterator_prev(const container_t *c, uint8_t typecode,
+                                    roaring_container_iterator_t *it,
+                                    uint16_t *value);
+
 void container_free(container_t *c, uint8_t type) {
     switch (type) {
         case BITSET_CONTAINER_TYPE:
@@ -370,128 +377,6 @@ roaring_container_iterator_t container_init_iterator_last(const container_t *c,
     }
 }
 
-bool container_iterator_next(const container_t *c, uint8_t typecode,
-                             roaring_container_iterator_t *it,
-                             uint16_t *value) {
-    switch (typecode) {
-        case BITSET_CONTAINER_TYPE: {
-            const bitset_container_t *bc = const_CAST_bitset(c);
-            it->index++;
-
-            uint32_t wordindex = it->index / 64;
-            if (wordindex >= BITSET_CONTAINER_SIZE_IN_WORDS) {
-                return false;
-            }
-
-            uint64_t word =
-                bc->words[wordindex] & (UINT64_MAX << (it->index % 64));
-            // next part could be optimized/simplified
-            while (word == 0 &&
-                   (wordindex + 1 < BITSET_CONTAINER_SIZE_IN_WORDS)) {
-                wordindex++;
-                word = bc->words[wordindex];
-            }
-            if (word != 0) {
-                it->index = wordindex * 64 + roaring_trailing_zeroes(word);
-                *value = it->index;
-                return true;
-            }
-            return false;
-        }
-        case ARRAY_CONTAINER_TYPE: {
-            const array_container_t *ac = const_CAST_array(c);
-            it->index++;
-            if (it->index < ac->cardinality) {
-                *value = ac->array[it->index];
-                return true;
-            }
-            return false;
-        }
-        case RUN_CONTAINER_TYPE: {
-            if (*value == UINT16_MAX) {  // Avoid overflow to zero
-                return false;
-            }
-
-            const run_container_t *rc = const_CAST_run(c);
-            uint32_t limit =
-                rc->runs[it->index].value + rc->runs[it->index].length;
-            if (*value < limit) {
-                (*value)++;
-                return true;
-            }
-
-            it->index++;
-            if (it->index < rc->n_runs) {
-                *value = rc->runs[it->index].value;
-                return true;
-            }
-            return false;
-        }
-        default:
-            assert(false);
-            roaring_unreachable;
-            return false;
-    }
-}
-
-bool container_iterator_prev(const container_t *c, uint8_t typecode,
-                             roaring_container_iterator_t *it,
-                             uint16_t *value) {
-    switch (typecode) {
-        case BITSET_CONTAINER_TYPE: {
-            if (--it->index < 0) {
-                return false;
-            }
-
-            const bitset_container_t *bc = const_CAST_bitset(c);
-            int32_t wordindex = it->index / 64;
-            uint64_t word =
-                bc->words[wordindex] & (UINT64_MAX >> (63 - (it->index % 64)));
-
-            while (word == 0 && --wordindex >= 0) {
-                word = bc->words[wordindex];
-            }
-            if (word == 0) {
-                return false;
-            }
-
-            it->index = (wordindex * 64) + (63 - roaring_leading_zeroes(word));
-            *value = it->index;
-            return true;
-        }
-        case ARRAY_CONTAINER_TYPE: {
-            if (--it->index < 0) {
-                return false;
-            }
-            const array_container_t *ac = const_CAST_array(c);
-            *value = ac->array[it->index];
-            return true;
-        }
-        case RUN_CONTAINER_TYPE: {
-            if (*value == 0) {
-                return false;
-            }
-
-            const run_container_t *rc = const_CAST_run(c);
-            (*value)--;
-            if (*value >= rc->runs[it->index].value) {
-                return true;
-            }
-
-            if (--it->index < 0) {
-                return false;
-            }
-
-            *value = rc->runs[it->index].value + rc->runs[it->index].length;
-            return true;
-        }
-        default:
-            assert(false);
-            roaring_unreachable;
-            return false;
-    }
-}
-
 bool container_iterator_lower_bound(const container_t *c, uint8_t typecode,
                                     roaring_container_iterator_t *it,
                                     uint16_t *value_out, uint16_t val) {
diff --git a/contrib/libs/croaring/src/roaring.c b/contrib/libs/croaring/src/roaring.c
index 0c220a29873..eae15498769 100644
--- a/contrib/libs/croaring/src/roaring.c
+++ b/contrib/libs/croaring/src/roaring.c
@@ -24,6 +24,8 @@ namespace api {
 
 #define CROARING_SERIALIZATION_ARRAY_UINT32 1
 #define CROARING_SERIALIZATION_CONTAINER 2
+extern inline bool roaring_bitmap_contains(const roaring_bitmap_t *r,
+                                           uint32_t val);
 extern inline int roaring_trailing_zeroes(unsigned long long input_num);
 extern inline int roaring_leading_zeroes(unsigned long long input_num);
 extern inline void roaring_bitmap_init_cleared(roaring_bitmap_t *r);
@@ -2915,23 +2917,6 @@ uint64_t roaring_bitmap_xor_cardinality(const roaring_bitmap_t *x1,
     return c1 + c2 - 2 * inter;
 }
 
-bool roaring_bitmap_contains(const roaring_bitmap_t *r, uint32_t val) {
-    const uint16_t hb = val >> 16;
-    /*
-     * the next function call involves a binary search and lots of branching.
-     */
-    int32_t i = ra_get_index(&r->high_low_container, hb);
-    if (i < 0) return false;
-
-    uint8_t typecode;
-    // next call ought to be cheap
-    container_t *container = ra_get_container_at_index(&r->high_low_container,
-                                                       (uint16_t)i, &typecode);
-    // rest might be a tad expensive, possibly involving another round of binary
-    // search
-    return container_contains(container, val & 0xFFFF, typecode);
-}
-
 /**
  * Check whether a range of values from range_start (included) to range_end
  * (excluded) is present
diff --git a/contrib/libs/croaring/ya.make b/contrib/libs/croaring/ya.make
index 94959dbbf5e..2ac165ee113 100644
--- a/contrib/libs/croaring/ya.make
+++ b/contrib/libs/croaring/ya.make
@@ -10,12 +10,13 @@ LICENSE(
 
 LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
 
-VERSION(4.4.3)
+VERSION(4.5.0)
 
-ORIGINAL_SOURCE(https://github.com/RoaringBitmap/CRoaring/archive/v4.4.3.tar.gz)
+ORIGINAL_SOURCE(https://github.com/RoaringBitmap/CRoaring/archive/v4.5.0.tar.gz)
 
 ADDINCL(
     GLOBAL contrib/libs/croaring/include
+    contrib/libs/croaring/src
 )
 
 NO_COMPILER_WARNINGS()