MCPcopy Create free account
hub / github.com/apache/arrow / FindInsertionChunked

Function FindInsertionChunked

cpp/src/arrow/compute/kernels/vector_search_sorted.cc:490–512  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

488/// Find the insertion point into a chunked array.
489template <typename ArrowType, typename Accessor>
490ChunkLocation FindInsertionChunked(const std::vector<Accessor>& chunks,
491 const SearchValue<ArrowType>& needle,
492 SearchSortedOptions::Side side,
493 NullPlacement null_placement) {
494 // A naive implementation would search directly in the chunked array,
495 // with each indexed access taking O(log n) time.
496 // It is much faster to first narrow down the search to a single chunk
497 // (by using a binary search among chunk boundaries, see FindInsertionChunk)
498 // and then do a dense binary search (FindInsertionDense).
499 DCHECK_GT(chunks.size(), 0);
500 int64_t chunk_index =
501 FindInsertionChunk<ArrowType>(chunks, needle, side, null_placement);
502 int64_t index_in_chunk;
503 if (chunk_index == static_cast<int64_t>(chunks.size())) {
504 // Inserting at the right of the last chunk
505 --chunk_index;
506 index_in_chunk = chunks.back().length();
507 } else {
508 index_in_chunk =
509 FindInsertionDense<ArrowType>(chunks[chunk_index], needle, side, null_placement);
510 }
511 return {chunk_index, chunks[chunk_index].LogicalInsertionIndex(index_in_chunk)};
512}
513
514template <typename ArrowType, typename Accessor>
515class ChunkedSearchSorted {

Callers

nothing calls this directly

Calls 4

backMethod · 0.80
sizeMethod · 0.45
lengthMethod · 0.45
LogicalInsertionIndexMethod · 0.45

Tested by

no test coverage detected