wesm commented on a change in pull request #7442: URL: https://github.com/apache/arrow/pull/7442#discussion_r441661392
########## File path: cpp/src/arrow/compute/kernels/vector_selection.cc ########## @@ -0,0 +1,1816 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +#include <algorithm> +#include <cstring> +#include <limits> + +#include "arrow/array/array_base.h" +#include "arrow/array/array_binary.h" +#include "arrow/array/array_dict.h" +#include "arrow/array/array_nested.h" +#include "arrow/array/builder_primitive.h" +#include "arrow/array/concatenate.h" +#include "arrow/buffer_builder.h" +#include "arrow/compute/api_vector.h" +#include "arrow/compute/kernels/common.h" +#include "arrow/compute/kernels/util_internal.h" +#include "arrow/extension_type.h" +#include "arrow/record_batch.h" +#include "arrow/result.h" +#include "arrow/util/bit_block_counter.h" +#include "arrow/util/bit_util.h" +#include "arrow/util/bitmap_ops.h" +#include "arrow/util/bitmap_reader.h" +#include "arrow/util/int_util.h" + +namespace arrow { + +using internal::BinaryBitBlockCounter; +using internal::BitBlockCount; +using internal::BitBlockCounter; +using internal::BitmapReader; +using internal::CopyBitmap; +using internal::GetArrayView; +using internal::IndexBoundsCheck; +using internal::OptionalBitBlockCounter; +using internal::OptionalBitIndexer; + +namespace compute { +namespace internal { + +int64_t GetFilterOutputSize(const ArrayData& filter, + FilterOptions::NullSelectionBehavior null_selection) { + int64_t output_size = 0; + int64_t position = 0; + if (filter.GetNullCount() > 0) { + const uint8_t* filter_is_valid = filter.buffers[0]->data(); + BinaryBitBlockCounter bit_counter(filter.buffers[1]->data(), filter.offset, + filter_is_valid, filter.offset, filter.length); + if (null_selection == FilterOptions::EMIT_NULL) { + while (position < filter.length) { + BitBlockCount block = bit_counter.NextOrNotWord(); + output_size += block.popcount; + position += block.length; + } + } else { + while (position < filter.length) { + BitBlockCount block = bit_counter.NextAndWord(); + output_size += block.popcount; + position += block.length; + } + } + } else { + // The filter has no nulls, so we plow through its data as fast as + // possible. + BitBlockCounter bit_counter(filter.buffers[1]->data(), filter.offset, filter.length); + while (position < filter.length) { + BitBlockCount block = bit_counter.NextFourWords(); + output_size += block.popcount; + position += block.length; + } + } + return output_size; +} + +template <typename IndexType> +Result<std::shared_ptr<ArrayData>> GetTakeIndicesImpl( + const ArrayData& filter, FilterOptions::NullSelectionBehavior null_selection, + MemoryPool* memory_pool) { + using T = typename IndexType::c_type; + typename TypeTraits<IndexType>::BuilderType builder(memory_pool); + + const uint8_t* filter_data = filter.buffers[1]->data(); + BitBlockCounter data_counter(filter_data, filter.offset, filter.length); + + // The position relative to the start of the filter + T position = 0; + + // The current position taking the filter offset into account + int64_t position_with_offset = filter.offset; + if (filter.GetNullCount() > 0) { + // The filter has nulls, so we scan the validity bitmap and the filter data + // bitmap together, branching on the null selection type. + const uint8_t* filter_is_valid = filter.buffers[0]->data(); + + // To count blocks whether filter_data[i] || !filter_is_valid[i] + BinaryBitBlockCounter filter_counter(filter_data, filter.offset, filter_is_valid, + filter.offset, filter.length); + if (null_selection == FilterOptions::DROP) { + while (position < filter.length) { + BitBlockCount and_block = filter_counter.NextAndWord(); + RETURN_NOT_OK(builder.Reserve(and_block.popcount)); + if (and_block.AllSet()) { + // All the values are selected and non-null + for (int64_t i = 0; i < and_block.length; ++i) { + builder.UnsafeAppend(position++); + } + position_with_offset += and_block.length; + } else { + // Some of the values are false or null + for (int64_t i = 0; i < and_block.length; ++i) { + if (BitUtil::GetBit(filter_is_valid, position_with_offset) && + BitUtil::GetBit(filter_data, position_with_offset)) { + builder.UnsafeAppend(position); + } + ++position; + ++position_with_offset; + } + } + } + } else { + BitBlockCounter is_valid_counter(filter_is_valid, filter.offset, filter.length); + while (position < filter.length) { + // true OR NOT valid + BitBlockCount or_not_block = filter_counter.NextOrNotWord(); + RETURN_NOT_OK(builder.Reserve(or_not_block.popcount)); + + // If the values are all valid and the or_not_block is full, then we + // can infer that all the values are true and skip the bit checking + BitBlockCount is_valid_block = is_valid_counter.NextWord(); + + if (or_not_block.AllSet() && is_valid_block.AllSet()) { + // All the values are selected and non-null + for (int64_t i = 0; i < or_not_block.length; ++i) { + builder.UnsafeAppend(position++); + } + position_with_offset += or_not_block.length; + } else { + // Some of the values are false or null + for (int64_t i = 0; i < or_not_block.length; ++i) { + if (BitUtil::GetBit(filter_is_valid, position_with_offset)) { + if (BitUtil::GetBit(filter_data, position_with_offset)) { + builder.UnsafeAppend(position); + } + } else { + // Null slot, so append a null + builder.UnsafeAppendNull(); + } + ++position; + ++position_with_offset; + } + } + } + } + } else { + // The filter has no nulls, so we need only look for true values + BitBlockCount current_block = data_counter.NextWord(); + while (position < filter.length) { + if (current_block.AllSet()) { + int64_t run_length = 0; + + // If we've found a all-true block, then we scan forward until we find + // a block that has some false values (or we reach the end + while (current_block.length > 0 && current_block.AllSet()) { + run_length += current_block.length; + current_block = data_counter.NextWord(); + } + + // Append the consecutive run of indices + RETURN_NOT_OK(builder.Reserve(run_length)); + for (int64_t i = 0; i < run_length; ++i) { + builder.UnsafeAppend(position++); + } + position_with_offset += run_length; + } else { + // Must do bitchecking on the current block Review comment: fixed ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org
