Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-08-28 08:26:55

0001 // Licensed to the Apache Software Foundation (ASF) under one
0002 // or more contributor license agreements.  See the NOTICE file
0003 // distributed with this work for additional information
0004 // regarding copyright ownership.  The ASF licenses this file
0005 // to you under the Apache License, Version 2.0 (the
0006 // "License"); you may not use this file except in compliance
0007 // with the License.  You may obtain a copy of the License at
0008 //
0009 //   http://www.apache.org/licenses/LICENSE-2.0
0010 //
0011 // Unless required by applicable law or agreed to in writing,
0012 // software distributed under the License is distributed on an
0013 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0014 // KIND, either express or implied.  See the License for the
0015 // specific language governing permissions and limitations
0016 // under the License.
0017 
0018 #pragma once
0019 
0020 #include <cstdint>
0021 #include <limits>
0022 #include <memory>
0023 #include <utility>
0024 #include <vector>
0025 
0026 #include "arrow/array/array_nested.h"
0027 #include "arrow/array/builder_base.h"
0028 #include "arrow/array/data.h"
0029 #include "arrow/buffer.h"
0030 #include "arrow/buffer_builder.h"
0031 #include "arrow/status.h"
0032 #include "arrow/type.h"
0033 #include "arrow/util/macros.h"
0034 #include "arrow/util/visibility.h"
0035 
0036 namespace arrow {
0037 
0038 /// \addtogroup nested-builders
0039 ///
0040 /// @{
0041 
0042 // ----------------------------------------------------------------------
0043 // VarLengthListLikeBuilder
0044 
0045 template <typename TYPE>
0046 class VarLengthListLikeBuilder : public ArrayBuilder {
0047  public:
0048   using TypeClass = TYPE;
0049   using offset_type = typename TypeClass::offset_type;
0050 
0051   /// Use this constructor to incrementally build the value array along with offsets and
0052   /// null bitmap.
0053   VarLengthListLikeBuilder(MemoryPool* pool,
0054                            std::shared_ptr<ArrayBuilder> const& value_builder,
0055                            const std::shared_ptr<DataType>& type,
0056                            int64_t alignment = kDefaultBufferAlignment)
0057       : ArrayBuilder(pool, alignment),
0058         offsets_builder_(pool, alignment),
0059         value_builder_(value_builder),
0060         value_field_(type->field(0)->WithType(NULLPTR)) {}
0061 
0062   VarLengthListLikeBuilder(MemoryPool* pool,
0063                            std::shared_ptr<ArrayBuilder> const& value_builder,
0064                            int64_t alignment = kDefaultBufferAlignment)
0065       : VarLengthListLikeBuilder(pool, value_builder,
0066                                  std::make_shared<TYPE>(value_builder->type()),
0067                                  alignment) {}
0068 
0069   ~VarLengthListLikeBuilder() override = default;
0070 
0071   Status Resize(int64_t capacity) override {
0072     if (ARROW_PREDICT_FALSE(capacity > maximum_elements())) {
0073       return Status::CapacityError(type_name(),
0074                                    " array cannot reserve space for more than ",
0075                                    maximum_elements(), " got ", capacity);
0076     }
0077     ARROW_RETURN_NOT_OK(CheckCapacity(capacity));
0078 
0079     // One more than requested for list offsets
0080     const int64_t offsets_capacity =
0081         is_list_view(TYPE::type_id) ? capacity : capacity + 1;
0082     ARROW_RETURN_NOT_OK(offsets_builder_.Resize(offsets_capacity));
0083     return ArrayBuilder::Resize(capacity);
0084   }
0085 
0086   void Reset() override {
0087     ArrayBuilder::Reset();
0088     offsets_builder_.Reset();
0089     value_builder_->Reset();
0090   }
0091 
0092   /// \brief Start a new variable-length list slot
0093   ///
0094   /// This function should be called before appending elements to the
0095   /// value builder. Elements appended to the value builder before this function
0096   /// is called for the first time, will not be members of any list value.
0097   ///
0098   /// After this function is called, list_length elements SHOULD be appended to
0099   /// the values builder. If this contract is violated, the behavior is defined by
0100   /// the concrete builder implementation and SHOULD NOT be relied upon unless
0101   /// the caller is specifically building a [Large]List or [Large]ListView array.
0102   ///
0103   /// For [Large]List arrays, the list slot length will be the number of elements
0104   /// appended to the values builder before the next call to Append* or Finish. For
0105   /// [Large]ListView arrays, the list slot length will be exactly list_length, but if
0106   /// Append* is called before at least list_length elements are appended to the values
0107   /// builder, the current list slot will share elements with the next list
0108   /// slots or an invalid [Large]ListView array will be generated because there
0109   /// aren't enough elements in the values builder to fill the list slots.
0110   ///
0111   /// If you're building a [Large]List and don't need to be compatible
0112   /// with [Large]ListView, then `BaseListBuilder::Append(bool is_valid)`
0113   /// is a simpler API.
0114   ///
0115   /// \pre if is_valid is false, list_length MUST be 0
0116   /// \param is_valid Whether the new list slot is valid
0117   /// \param list_length The number of elements in the list
0118   Status Append(bool is_valid, int64_t list_length) {
0119     ARROW_RETURN_NOT_OK(Reserve(1));
0120     assert(is_valid || list_length == 0);
0121     UnsafeAppendToBitmap(is_valid);
0122     UnsafeAppendDimensions(/*offset=*/value_builder_->length(), /*size=*/list_length);
0123     return Status::OK();
0124   }
0125 
0126   Status AppendNull() final {
0127     // Append() a null list slot with list_length=0.
0128     //
0129     // When building [Large]List arrays, elements being appended to the values builder
0130     // before the next call to Append* or Finish will extend the list slot length, but
0131     // that is totally fine because list arrays admit non-empty null list slots.
0132     //
0133     // In the case of [Large]ListViews that's not a problem either because the
0134     // list slot length remains zero.
0135     return Append(false, 0);
0136   }
0137 
0138   Status AppendNulls(int64_t length) final {
0139     ARROW_RETURN_NOT_OK(Reserve(length));
0140     UnsafeAppendToBitmap(length, false);
0141     UnsafeAppendEmptyDimensions(/*num_values=*/length);
0142     return Status::OK();
0143   }
0144 
0145   /// \brief Append an empty list slot
0146   ///
0147   /// \post Another call to Append* or Finish should be made before appending to
0148   /// the values builder to ensure list slot remains empty
0149   Status AppendEmptyValue() final { return Append(true, 0); }
0150 
0151   /// \brief Append an empty list slot
0152   ///
0153   /// \post Another call to Append* or Finish should be made before appending to
0154   /// the values builder to ensure the last list slot remains empty
0155   Status AppendEmptyValues(int64_t length) final {
0156     ARROW_RETURN_NOT_OK(Reserve(length));
0157     UnsafeAppendToBitmap(length, true);
0158     UnsafeAppendEmptyDimensions(/*num_values=*/length);
0159     return Status::OK();
0160   }
0161 
0162   /// \brief Vector append
0163   ///
0164   /// For list-array builders, the sizes are inferred from the offsets.
0165   /// BaseListBuilder<T> provides an implementation that doesn't take sizes, but
0166   /// this virtual function allows dispatching calls to both list-array and
0167   /// list-view-array builders (which need the sizes)
0168   ///
0169   /// \param offsets The offsets of the variable-length lists
0170   /// \param sizes The sizes of the variable-length lists
0171   /// \param length The number of offsets, sizes, and validity bits to append
0172   /// \param valid_bytes If passed, valid_bytes is of equal length to values,
0173   /// and any zero byte will be considered as a null for that slot
0174   virtual Status AppendValues(const offset_type* offsets, const offset_type* sizes,
0175                               int64_t length, const uint8_t* valid_bytes) = 0;
0176 
0177   Status AppendArraySlice(const ArraySpan& array, int64_t offset,
0178                           int64_t length) override {
0179     const offset_type* offsets = array.GetValues<offset_type>(1);
0180     [[maybe_unused]] const offset_type* sizes = NULLPTR;
0181     if constexpr (is_list_view(TYPE::type_id)) {
0182       sizes = array.GetValues<offset_type>(2);
0183     }
0184     static_assert(internal::may_have_validity_bitmap(TYPE::type_id));
0185     const uint8_t* validity = array.MayHaveNulls() ? array.buffers[0].data : NULLPTR;
0186     ARROW_RETURN_NOT_OK(Reserve(length));
0187     for (int64_t row = offset; row < offset + length; row++) {
0188       const bool is_valid = !validity || bit_util::GetBit(validity, array.offset + row);
0189       int64_t size = 0;
0190       if (is_valid) {
0191         if constexpr (is_list_view(TYPE::type_id)) {
0192           size = sizes[row];
0193         } else {
0194           size = offsets[row + 1] - offsets[row];
0195         }
0196       }
0197       UnsafeAppendToBitmap(is_valid);
0198       UnsafeAppendDimensions(/*offset=*/value_builder_->length(), size);
0199       if (is_valid) {
0200         ARROW_RETURN_NOT_OK(
0201             value_builder_->AppendArraySlice(array.child_data[0], offsets[row], size));
0202       }
0203     }
0204     return Status::OK();
0205   }
0206 
0207   Status ValidateOverflow(int64_t new_elements) const {
0208     auto new_length = value_builder_->length() + new_elements;
0209     if (ARROW_PREDICT_FALSE(new_length > maximum_elements())) {
0210       return Status::CapacityError(type_name(), " array cannot contain more than ",
0211                                    maximum_elements(), " elements, have ", new_elements);
0212     } else {
0213       return Status::OK();
0214     }
0215   }
0216 
0217   ArrayBuilder* value_builder() const { return value_builder_.get(); }
0218 
0219   // Cannot make this a static attribute because of linking issues
0220   static constexpr int64_t maximum_elements() {
0221     return std::numeric_limits<offset_type>::max() - 1;
0222   }
0223 
0224   std::shared_ptr<DataType> type() const override {
0225     return std::make_shared<TYPE>(value_field_->WithType(value_builder_->type()));
0226   }
0227 
0228  private:
0229   static constexpr const char* type_name() {
0230     if constexpr (is_list_view(TYPE::type_id)) {
0231       return "ListView";
0232     } else {
0233       return "List";
0234     }
0235   }
0236 
0237  protected:
0238   /// \brief Append dimensions for num_values empty list slots.
0239   ///
0240   /// ListViewBuilder overrides this to also append the sizes.
0241   virtual void UnsafeAppendEmptyDimensions(int64_t num_values) {
0242     const int64_t offset = value_builder_->length();
0243     for (int64_t i = 0; i < num_values; ++i) {
0244       offsets_builder_.UnsafeAppend(static_cast<offset_type>(offset));
0245     }
0246   }
0247 
0248   /// \brief Append dimensions for a single list slot.
0249   ///
0250   /// ListViewBuilder overrides this to also append the size.
0251   virtual void UnsafeAppendDimensions(int64_t offset, int64_t ARROW_ARG_UNUSED(size)) {
0252     offsets_builder_.UnsafeAppend(static_cast<offset_type>(offset));
0253   }
0254 
0255   TypedBufferBuilder<offset_type> offsets_builder_;
0256   std::shared_ptr<ArrayBuilder> value_builder_;
0257   std::shared_ptr<Field> value_field_;
0258 };
0259 
0260 // ----------------------------------------------------------------------
0261 // ListBuilder / LargeListBuilder
0262 
0263 template <typename TYPE>
0264 class BaseListBuilder : public VarLengthListLikeBuilder<TYPE> {
0265  private:
0266   using BASE = VarLengthListLikeBuilder<TYPE>;
0267 
0268  public:
0269   using TypeClass = TYPE;
0270   using offset_type = typename BASE::offset_type;
0271 
0272   using BASE::BASE;
0273 
0274   using BASE::Append;
0275 
0276   ~BaseListBuilder() override = default;
0277 
0278   /// \brief Start a new variable-length list slot
0279   ///
0280   /// This function should be called before beginning to append elements to the
0281   /// value builder
0282   Status Append(bool is_valid = true) {
0283     // The value_length parameter to BASE::Append(bool, int64_t) is ignored when
0284     // building a list array, so we can pass 0 here.
0285     return BASE::Append(is_valid, 0);
0286   }
0287 
0288   /// \brief Vector append
0289   ///
0290   /// If passed, valid_bytes is of equal length to values, and any zero byte
0291   /// will be considered as a null for that slot
0292   Status AppendValues(const offset_type* offsets, int64_t length,
0293                       const uint8_t* valid_bytes = NULLPTR) {
0294     ARROW_RETURN_NOT_OK(this->Reserve(length));
0295     this->UnsafeAppendToBitmap(valid_bytes, length);
0296     this->offsets_builder_.UnsafeAppend(offsets, length);
0297     return Status::OK();
0298   }
0299 
0300   Status AppendValues(const offset_type* offsets, const offset_type* sizes,
0301                       int64_t length, const uint8_t* valid_bytes) final {
0302     // Offsets are assumed to be valid, but the first length-1 sizes have to be
0303     // consistent with the offsets to partially rule out the possibility that the
0304     // caller is passing sizes that could work if building a list-view, but don't
0305     // work on building a list that requires offsets to be non-decreasing.
0306     //
0307     // CAUTION: the last size element (`sizes[length - 1]`) is not
0308     // validated and could be inconsistent with the offsets given in a
0309     // subsequent call to AppendValues.
0310 #ifndef NDEBUG
0311     if (sizes) {
0312       for (int64_t i = 0; i < length - 1; ++i) {
0313         if (ARROW_PREDICT_FALSE(offsets[i] != offsets[i + 1] - sizes[i])) {
0314           if (!valid_bytes || valid_bytes[i]) {
0315             return Status::Invalid(
0316                 "BaseListBuilder: sizes are inconsistent with offsets provided");
0317           }
0318         }
0319       }
0320     }
0321 #endif
0322     return AppendValues(offsets, length, valid_bytes);
0323   }
0324 
0325   Status AppendValues(const offset_type* offsets, const offset_type* sizes,
0326                       int64_t length) {
0327     return AppendValues(offsets, sizes, length, /*valid_bytes=*/NULLPTR);
0328   }
0329 
0330   Status AppendNextOffset() {
0331     ARROW_RETURN_NOT_OK(this->ValidateOverflow(0));
0332     const int64_t num_values = this->value_builder_->length();
0333     return this->offsets_builder_.Append(static_cast<offset_type>(num_values));
0334   }
0335 
0336   Status FinishInternal(std::shared_ptr<ArrayData>* out) override {
0337     ARROW_RETURN_NOT_OK(AppendNextOffset());
0338 
0339     // Offset padding zeroed by BufferBuilder
0340     std::shared_ptr<Buffer> offsets;
0341     std::shared_ptr<Buffer> null_bitmap;
0342     ARROW_RETURN_NOT_OK(this->offsets_builder_.Finish(&offsets));
0343     ARROW_RETURN_NOT_OK(this->null_bitmap_builder_.Finish(&null_bitmap));
0344 
0345     if (this->value_builder_->length() == 0) {
0346       // Try to make sure we get a non-null values buffer (ARROW-2744)
0347       ARROW_RETURN_NOT_OK(this->value_builder_->Resize(0));
0348     }
0349 
0350     std::shared_ptr<ArrayData> items;
0351     ARROW_RETURN_NOT_OK(this->value_builder_->FinishInternal(&items));
0352 
0353     *out = ArrayData::Make(this->type(), this->length_,
0354                            {std::move(null_bitmap), std::move(offsets)},
0355                            {std::move(items)}, this->null_count_);
0356     this->Reset();
0357     return Status::OK();
0358   }
0359 };
0360 
0361 /// \class ListBuilder
0362 /// \brief Builder class for variable-length list array value types
0363 ///
0364 /// To use this class, you must append values to the child array builder and use
0365 /// the Append function to delimit each distinct list value (once the values
0366 /// have been appended to the child array) or use the bulk API to append
0367 /// a sequence of offsets and null values.
0368 ///
0369 /// A note on types.  Per arrow/type.h all types in the c++ implementation are
0370 /// logical so even though this class always builds list array, this can
0371 /// represent multiple different logical types.  If no logical type is provided
0372 /// at construction time, the class defaults to List<T> where t is taken from the
0373 /// value_builder/values that the object is constructed with.
0374 class ARROW_EXPORT ListBuilder : public BaseListBuilder<ListType> {
0375  public:
0376   using BaseListBuilder::BaseListBuilder;
0377 
0378   /// \cond FALSE
0379   using ArrayBuilder::Finish;
0380   /// \endcond
0381 
0382   Status Finish(std::shared_ptr<ListArray>* out) { return FinishTyped(out); }
0383 };
0384 
0385 /// \class LargeListBuilder
0386 /// \brief Builder class for large variable-length list array value types
0387 ///
0388 /// Like ListBuilder, but to create large list arrays (with 64-bit offsets).
0389 class ARROW_EXPORT LargeListBuilder : public BaseListBuilder<LargeListType> {
0390  public:
0391   using BaseListBuilder::BaseListBuilder;
0392 
0393   /// \cond FALSE
0394   using ArrayBuilder::Finish;
0395   /// \endcond
0396 
0397   Status Finish(std::shared_ptr<LargeListArray>* out) { return FinishTyped(out); }
0398 };
0399 
0400 // ----------------------------------------------------------------------
0401 // ListViewBuilder / LargeListViewBuilder
0402 
0403 template <typename TYPE>
0404 class BaseListViewBuilder : public VarLengthListLikeBuilder<TYPE> {
0405  private:
0406   using BASE = VarLengthListLikeBuilder<TYPE>;
0407 
0408  public:
0409   using TypeClass = TYPE;
0410   using offset_type = typename BASE::offset_type;
0411 
0412   using BASE::BASE;
0413 
0414   ~BaseListViewBuilder() override = default;
0415 
0416   Status Resize(int64_t capacity) override {
0417     ARROW_RETURN_NOT_OK(BASE::Resize(capacity));
0418     return sizes_builder_.Resize(capacity);
0419   }
0420 
0421   void Reset() override {
0422     BASE::Reset();
0423     sizes_builder_.Reset();
0424   }
0425 
0426   /// \brief Vector append
0427   ///
0428   /// If passed, valid_bytes is of equal length to values, and any zero byte
0429   /// will be considered as a null for that slot
0430   Status AppendValues(const offset_type* offsets, const offset_type* sizes,
0431                       int64_t length, const uint8_t* valid_bytes) final {
0432     ARROW_RETURN_NOT_OK(this->Reserve(length));
0433     this->UnsafeAppendToBitmap(valid_bytes, length);
0434     this->offsets_builder_.UnsafeAppend(offsets, length);
0435     this->sizes_builder_.UnsafeAppend(sizes, length);
0436     return Status::OK();
0437   }
0438 
0439   Status AppendValues(const offset_type* offsets, const offset_type* sizes,
0440                       int64_t length) {
0441     return AppendValues(offsets, sizes, length, /*valid_bytes=*/NULLPTR);
0442   }
0443 
0444   Status FinishInternal(std::shared_ptr<ArrayData>* out) override {
0445     // Offset and sizes padding zeroed by BufferBuilder
0446     std::shared_ptr<Buffer> null_bitmap;
0447     std::shared_ptr<Buffer> offsets;
0448     std::shared_ptr<Buffer> sizes;
0449     ARROW_RETURN_NOT_OK(this->null_bitmap_builder_.Finish(&null_bitmap));
0450     ARROW_RETURN_NOT_OK(this->offsets_builder_.Finish(&offsets));
0451     ARROW_RETURN_NOT_OK(this->sizes_builder_.Finish(&sizes));
0452 
0453     if (this->value_builder_->length() == 0) {
0454       // Try to make sure we get a non-null values buffer (ARROW-2744)
0455       ARROW_RETURN_NOT_OK(this->value_builder_->Resize(0));
0456     }
0457 
0458     std::shared_ptr<ArrayData> items;
0459     ARROW_RETURN_NOT_OK(this->value_builder_->FinishInternal(&items));
0460 
0461     *out = ArrayData::Make(this->type(), this->length_,
0462                            {std::move(null_bitmap), std::move(offsets), std::move(sizes)},
0463                            {std::move(items)}, this->null_count_);
0464     this->Reset();
0465     return Status::OK();
0466   }
0467 
0468  protected:
0469   void UnsafeAppendEmptyDimensions(int64_t num_values) override {
0470     for (int64_t i = 0; i < num_values; ++i) {
0471       this->offsets_builder_.UnsafeAppend(0);
0472     }
0473     for (int64_t i = 0; i < num_values; ++i) {
0474       this->sizes_builder_.UnsafeAppend(0);
0475     }
0476   }
0477 
0478   void UnsafeAppendDimensions(int64_t offset, int64_t size) override {
0479     this->offsets_builder_.UnsafeAppend(static_cast<offset_type>(offset));
0480     this->sizes_builder_.UnsafeAppend(static_cast<offset_type>(size));
0481   }
0482 
0483  private:
0484   TypedBufferBuilder<offset_type> sizes_builder_;
0485 };
0486 
0487 class ARROW_EXPORT ListViewBuilder final : public BaseListViewBuilder<ListViewType> {
0488  public:
0489   using BaseListViewBuilder::BaseListViewBuilder;
0490 
0491   /// \cond FALSE
0492   using ArrayBuilder::Finish;
0493   /// \endcond
0494 
0495   Status Finish(std::shared_ptr<ListViewArray>* out) { return FinishTyped(out); }
0496 };
0497 
0498 class ARROW_EXPORT LargeListViewBuilder final
0499     : public BaseListViewBuilder<LargeListViewType> {
0500  public:
0501   using BaseListViewBuilder::BaseListViewBuilder;
0502 
0503   /// \cond FALSE
0504   using ArrayBuilder::Finish;
0505   /// \endcond
0506 
0507   Status Finish(std::shared_ptr<LargeListViewArray>* out) { return FinishTyped(out); }
0508 };
0509 
0510 // ----------------------------------------------------------------------
0511 // Map builder
0512 
0513 /// \class MapBuilder
0514 /// \brief Builder class for arrays of variable-size maps
0515 ///
0516 /// To use this class, you must use the Append function to delimit each distinct
0517 /// map before appending values to the key and item array builders, or use the
0518 /// bulk API to append a sequence of offsets and null maps.
0519 ///
0520 /// Key uniqueness and ordering are not validated.
0521 class ARROW_EXPORT MapBuilder : public ArrayBuilder {
0522  public:
0523   /// Use this constructor to define the built array's type explicitly. If key_builder
0524   /// or item_builder has indeterminate type, this builder will also.
0525   MapBuilder(MemoryPool* pool, const std::shared_ptr<ArrayBuilder>& key_builder,
0526              const std::shared_ptr<ArrayBuilder>& item_builder,
0527              const std::shared_ptr<DataType>& type);
0528 
0529   /// Use this constructor to infer the built array's type. If key_builder or
0530   /// item_builder has indeterminate type, this builder will also.
0531   MapBuilder(MemoryPool* pool, const std::shared_ptr<ArrayBuilder>& key_builder,
0532              const std::shared_ptr<ArrayBuilder>& item_builder, bool keys_sorted = false);
0533 
0534   MapBuilder(MemoryPool* pool, const std::shared_ptr<ArrayBuilder>& item_builder,
0535              const std::shared_ptr<DataType>& type);
0536 
0537   Status Resize(int64_t capacity) override;
0538   void Reset() override;
0539   Status FinishInternal(std::shared_ptr<ArrayData>* out) override;
0540 
0541   /// \cond FALSE
0542   using ArrayBuilder::Finish;
0543   /// \endcond
0544 
0545   Status Finish(std::shared_ptr<MapArray>* out) { return FinishTyped(out); }
0546 
0547   /// \brief Vector append
0548   ///
0549   /// If passed, valid_bytes is of equal length to values, and any zero byte
0550   /// will be considered as a null for that slot
0551   Status AppendValues(const int32_t* offsets, int64_t length,
0552                       const uint8_t* valid_bytes = NULLPTR);
0553 
0554   /// \brief Start a new variable-length map slot
0555   ///
0556   /// This function should be called before beginning to append elements to the
0557   /// key and item builders
0558   Status Append();
0559 
0560   Status AppendNull() final;
0561 
0562   Status AppendNulls(int64_t length) final;
0563 
0564   Status AppendEmptyValue() final;
0565 
0566   Status AppendEmptyValues(int64_t length) final;
0567 
0568   Status AppendArraySlice(const ArraySpan& array, int64_t offset,
0569                           int64_t length) override {
0570     const auto* offsets = array.GetValues<int32_t>(1);
0571     static_assert(internal::may_have_validity_bitmap(MapType::type_id));
0572     const uint8_t* validity = array.MayHaveNulls() ? array.buffers[0].data : NULLPTR;
0573     for (int64_t row = offset; row < offset + length; row++) {
0574       const bool is_valid = !validity || bit_util::GetBit(validity, array.offset + row);
0575       if (is_valid) {
0576         ARROW_RETURN_NOT_OK(Append());
0577         const int64_t slot_length = offsets[row + 1] - offsets[row];
0578         // Add together the inner StructArray offset to the Map/List offset
0579         int64_t key_value_offset = array.child_data[0].offset + offsets[row];
0580         ARROW_RETURN_NOT_OK(key_builder_->AppendArraySlice(
0581             array.child_data[0].child_data[0], key_value_offset, slot_length));
0582         ARROW_RETURN_NOT_OK(item_builder_->AppendArraySlice(
0583             array.child_data[0].child_data[1], key_value_offset, slot_length));
0584       } else {
0585         ARROW_RETURN_NOT_OK(AppendNull());
0586       }
0587     }
0588     return Status::OK();
0589   }
0590 
0591   /// \brief Get builder to append keys.
0592   ///
0593   /// Append a key with this builder should be followed by appending
0594   /// an item or null value with item_builder().
0595   ArrayBuilder* key_builder() const { return key_builder_.get(); }
0596 
0597   /// \brief Get builder to append items
0598   ///
0599   /// Appending an item with this builder should have been preceded
0600   /// by appending a key with key_builder().
0601   ArrayBuilder* item_builder() const { return item_builder_.get(); }
0602 
0603   /// \brief Get builder to add Map entries as struct values.
0604   ///
0605   /// This is used instead of key_builder()/item_builder() and allows
0606   /// the Map to be built as a list of struct values.
0607   ArrayBuilder* value_builder() const { return list_builder_->value_builder(); }
0608 
0609   std::shared_ptr<DataType> type() const override {
0610     // Key and Item builder may update types, but they don't contain the field names,
0611     // so we need to reconstruct the type. (See ARROW-13735.)
0612     return std::make_shared<MapType>(
0613         field(entries_name_,
0614               struct_({field(key_name_, key_builder_->type(), false),
0615                        field(item_name_, item_builder_->type(), item_nullable_)}),
0616               false),
0617         keys_sorted_);
0618   }
0619 
0620   Status ValidateOverflow(int64_t new_elements) {
0621     return list_builder_->ValidateOverflow(new_elements);
0622   }
0623 
0624  protected:
0625   inline Status AdjustStructBuilderLength();
0626 
0627  protected:
0628   bool keys_sorted_ = false;
0629   bool item_nullable_ = false;
0630   std::string entries_name_;
0631   std::string key_name_;
0632   std::string item_name_;
0633   std::shared_ptr<ListBuilder> list_builder_;
0634   std::shared_ptr<ArrayBuilder> key_builder_;
0635   std::shared_ptr<ArrayBuilder> item_builder_;
0636 };
0637 
0638 // ----------------------------------------------------------------------
0639 // FixedSizeList builder
0640 
0641 /// \class FixedSizeListBuilder
0642 /// \brief Builder class for fixed-length list array value types
0643 class ARROW_EXPORT FixedSizeListBuilder : public ArrayBuilder {
0644  public:
0645   using TypeClass = FixedSizeListType;
0646 
0647   /// Use this constructor to define the built array's type explicitly. If value_builder
0648   /// has indeterminate type, this builder will also.
0649   FixedSizeListBuilder(MemoryPool* pool,
0650                        std::shared_ptr<ArrayBuilder> const& value_builder,
0651                        int32_t list_size);
0652 
0653   /// Use this constructor to infer the built array's type. If value_builder has
0654   /// indeterminate type, this builder will also.
0655   FixedSizeListBuilder(MemoryPool* pool,
0656                        std::shared_ptr<ArrayBuilder> const& value_builder,
0657                        const std::shared_ptr<DataType>& type);
0658 
0659   Status Resize(int64_t capacity) override;
0660   void Reset() override;
0661   Status FinishInternal(std::shared_ptr<ArrayData>* out) override;
0662 
0663   /// \cond FALSE
0664   using ArrayBuilder::Finish;
0665   /// \endcond
0666 
0667   Status Finish(std::shared_ptr<FixedSizeListArray>* out) { return FinishTyped(out); }
0668 
0669   /// \brief Append a valid fixed length list.
0670   ///
0671   /// This function affects only the validity bitmap; the child values must be appended
0672   /// using the child array builder.
0673   Status Append();
0674 
0675   /// \brief Vector append
0676   ///
0677   /// If passed, valid_bytes will be read and any zero byte
0678   /// will cause the corresponding slot to be null
0679   ///
0680   /// This function affects only the validity bitmap; the child values must be appended
0681   /// using the child array builder. This includes appending nulls for null lists.
0682   /// XXX this restriction is confusing, should this method be omitted?
0683   Status AppendValues(int64_t length, const uint8_t* valid_bytes = NULLPTR);
0684 
0685   /// \brief Append a null fixed length list.
0686   ///
0687   /// The child array builder will have the appropriate number of nulls appended
0688   /// automatically.
0689   Status AppendNull() final;
0690 
0691   /// \brief Append length null fixed length lists.
0692   ///
0693   /// The child array builder will have the appropriate number of nulls appended
0694   /// automatically.
0695   Status AppendNulls(int64_t length) final;
0696 
0697   Status ValidateOverflow(int64_t new_elements);
0698 
0699   Status AppendEmptyValue() final;
0700 
0701   Status AppendEmptyValues(int64_t length) final;
0702 
0703   Status AppendArraySlice(const ArraySpan& array, int64_t offset, int64_t length) final {
0704     const uint8_t* validity = array.MayHaveNulls() ? array.buffers[0].data : NULLPTR;
0705     for (int64_t row = offset; row < offset + length; row++) {
0706       if (!validity || bit_util::GetBit(validity, array.offset + row)) {
0707         ARROW_RETURN_NOT_OK(value_builder_->AppendArraySlice(
0708             array.child_data[0], list_size_ * (array.offset + row), list_size_));
0709         ARROW_RETURN_NOT_OK(Append());
0710       } else {
0711         ARROW_RETURN_NOT_OK(AppendNull());
0712       }
0713     }
0714     return Status::OK();
0715   }
0716 
0717   ArrayBuilder* value_builder() const { return value_builder_.get(); }
0718 
0719   std::shared_ptr<DataType> type() const override {
0720     return fixed_size_list(value_field_->WithType(value_builder_->type()), list_size_);
0721   }
0722 
0723   // Cannot make this a static attribute because of linking issues
0724   static constexpr int64_t maximum_elements() {
0725     return std::numeric_limits<FixedSizeListType::offset_type>::max() - 1;
0726   }
0727 
0728  protected:
0729   std::shared_ptr<Field> value_field_;
0730   const int32_t list_size_;
0731   std::shared_ptr<ArrayBuilder> value_builder_;
0732 };
0733 
0734 // ----------------------------------------------------------------------
0735 // Struct
0736 
0737 // ---------------------------------------------------------------------------------
0738 // StructArray builder
0739 /// Append, Resize and Reserve methods are acting on StructBuilder.
0740 /// Please make sure all these methods of all child-builders' are consistently
0741 /// called to maintain data-structure consistency.
0742 class ARROW_EXPORT StructBuilder : public ArrayBuilder {
0743  public:
0744   /// If any of field_builders has indeterminate type, this builder will also
0745   StructBuilder(const std::shared_ptr<DataType>& type, MemoryPool* pool,
0746                 std::vector<std::shared_ptr<ArrayBuilder>> field_builders);
0747 
0748   Status FinishInternal(std::shared_ptr<ArrayData>* out) override;
0749 
0750   /// \cond FALSE
0751   using ArrayBuilder::Finish;
0752   /// \endcond
0753 
0754   Status Finish(std::shared_ptr<StructArray>* out) { return FinishTyped(out); }
0755 
0756   /// Null bitmap is of equal length to every child field, and any zero byte
0757   /// will be considered as a null for that field, but users must using app-
0758   /// end methods or advance methods of the child builders' independently to
0759   /// insert data.
0760   Status AppendValues(int64_t length, const uint8_t* valid_bytes) {
0761     ARROW_RETURN_NOT_OK(Reserve(length));
0762     UnsafeAppendToBitmap(valid_bytes, length);
0763     return Status::OK();
0764   }
0765 
0766   /// Append an element to the Struct. All child-builders' Append method must
0767   /// be called independently to maintain data-structure consistency.
0768   Status Append(bool is_valid = true) {
0769     ARROW_RETURN_NOT_OK(Reserve(1));
0770     UnsafeAppendToBitmap(is_valid);
0771     return Status::OK();
0772   }
0773 
0774   /// \brief Append a null value. Automatically appends an empty value to each child
0775   /// builder.
0776   Status AppendNull() final {
0777     for (const auto& field : children_) {
0778       ARROW_RETURN_NOT_OK(field->AppendEmptyValue());
0779     }
0780     return Append(false);
0781   }
0782 
0783   /// \brief Append multiple null values. Automatically appends empty values to each
0784   /// child builder.
0785   Status AppendNulls(int64_t length) final {
0786     for (const auto& field : children_) {
0787       ARROW_RETURN_NOT_OK(field->AppendEmptyValues(length));
0788     }
0789     ARROW_RETURN_NOT_OK(Reserve(length));
0790     UnsafeAppendToBitmap(length, false);
0791     return Status::OK();
0792   }
0793 
0794   Status AppendEmptyValue() final {
0795     for (const auto& field : children_) {
0796       ARROW_RETURN_NOT_OK(field->AppendEmptyValue());
0797     }
0798     return Append(true);
0799   }
0800 
0801   Status AppendEmptyValues(int64_t length) final {
0802     for (const auto& field : children_) {
0803       ARROW_RETURN_NOT_OK(field->AppendEmptyValues(length));
0804     }
0805     ARROW_RETURN_NOT_OK(Reserve(length));
0806     UnsafeAppendToBitmap(length, true);
0807     return Status::OK();
0808   }
0809 
0810   Status AppendArraySlice(const ArraySpan& array, int64_t offset,
0811                           int64_t length) override {
0812     for (int i = 0; static_cast<size_t>(i) < children_.size(); i++) {
0813       ARROW_RETURN_NOT_OK(children_[i]->AppendArraySlice(array.child_data[i],
0814                                                          array.offset + offset, length));
0815     }
0816     const uint8_t* validity = array.MayHaveNulls() ? array.buffers[0].data : NULLPTR;
0817     ARROW_RETURN_NOT_OK(Reserve(length));
0818     UnsafeAppendToBitmap(validity, array.offset + offset, length);
0819     return Status::OK();
0820   }
0821 
0822   void Reset() override;
0823 
0824   ArrayBuilder* field_builder(int i) const { return children_[i].get(); }
0825 
0826   int num_fields() const { return static_cast<int>(children_.size()); }
0827 
0828   std::shared_ptr<DataType> type() const override;
0829 
0830  private:
0831   std::shared_ptr<DataType> type_;
0832 };
0833 
0834 /// @}
0835 
0836 }  // namespace arrow