| 488 | /// Find the insertion point into a chunked array. |
| 489 | template <typename ArrowType, typename Accessor> |
| 490 | ChunkLocation 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 | |
| 514 | template <typename ArrowType, typename Accessor> |
| 515 | class ChunkedSearchSorted { |
nothing calls this directly
no test coverage detected