(arrow-nanoarrow) branch main updated: feat: add ArrowResolveChunk16 (#934)

[paleolimbot]

This is an automated email from the ASF dual-hosted git repository.

paleolimbot pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-nanoarrow.git


The following commit(s) were added to refs/heads/main by this push:
     new da7e96fa feat: add ArrowResolveChunk16 (#934)
da7e96fa is described below

commit da7e96fae9e586e339aea6bbe5e5143f31450c49
Author: Rusty Conover <ru...@conover.me>
AuthorDate: Sat Sep 5 23:11:03 2026 -0400

    feat: add ArrowResolveChunk16 (#934)
    
    Adds the int16 counterpart to ArrowResolveChunk32 and
    ArrowResolveChunk64.
    
    This follows up on the run-end encoded array review in #930, where int16
    run ends currently require a linear scan. The helper uses the same
    binary-search semantics as the existing resolvers and includes
    boundary-parity tests.
    
    Validation:
    - 270/270 C/C++ tests passed
    - clang-format and git diff checks passed
---
 src/nanoarrow/common/inline_buffer.h | 21 +++++++++++++++++++++
 src/nanoarrow/common/utils_test.cc   | 12 ++++++++++++
 2 files changed, 33 insertions(+)

diff --git a/src/nanoarrow/common/inline_buffer.h 
b/src/nanoarrow/common/inline_buffer.h
index c9a78602..e3d48547 100644
--- a/src/nanoarrow/common/inline_buffer.h
+++ b/src/nanoarrow/common/inline_buffer.h
@@ -71,6 +71,27 @@ static inline int64_t ArrowResolveChunk32(int32_t index, 
const int32_t* offsets,
   return lo;
 }
 
+static inline int64_t ArrowResolveChunk16(int16_t index, const int16_t* 
offsets,
+                                          int16_t lo, int16_t hi) {
+  // Similar to std::upper_bound(), but slightly different as our offsets
+  // array always starts with 0.
+  int16_t n = hi - lo;
+  // First iteration does not need to check for n > 1
+  // (lo < hi is guaranteed by the precondition).
+  NANOARROW_DCHECK(n > 1);
+  do {
+    const int16_t m = n >> 1;
+    const int16_t mid = lo + m;
+    if (index >= offsets[mid]) {
+      lo = mid;
+      n -= m;
+    } else {
+      n = m;
+    }
+  } while (n > 1);
+  return lo;
+}
+
 static inline int64_t _ArrowGrowByFactor(int64_t current_capacity, int64_t 
new_capacity) {
   int64_t doubled_capacity = current_capacity * 2;
   if (doubled_capacity > new_capacity) {
diff --git a/src/nanoarrow/common/utils_test.cc 
b/src/nanoarrow/common/utils_test.cc
index 0f8b0218..d4e43ad5 100644
--- a/src/nanoarrow/common/utils_test.cc
+++ b/src/nanoarrow/common/utils_test.cc
@@ -783,6 +783,18 @@ TEST(UtilsTest, ArrowResolveChunk32Test) {
   EXPECT_EQ(ArrowResolveChunk32(5, offsets, 0, n_offsets), 2);
 }
 
+TEST(UtilsTest, ArrowResolveChunk16Test) {
+  int16_t offsets[] = {0, 2, 3, 6};
+  int16_t n_offsets = 4;
+
+  EXPECT_EQ(ArrowResolveChunk16(0, offsets, 0, n_offsets), 0);
+  EXPECT_EQ(ArrowResolveChunk16(1, offsets, 0, n_offsets), 0);
+  EXPECT_EQ(ArrowResolveChunk16(2, offsets, 0, n_offsets), 1);
+  EXPECT_EQ(ArrowResolveChunk16(3, offsets, 0, n_offsets), 2);
+  EXPECT_EQ(ArrowResolveChunk16(4, offsets, 0, n_offsets), 2);
+  EXPECT_EQ(ArrowResolveChunk16(5, offsets, 0, n_offsets), 2);
+}
+
 TEST(MaybeTest, ConstructionAndConversion) {
   using nanoarrow::NA;
   using nanoarrow::internal::Maybe;