| 454 | |
| 455 | struct ReadRangeCombiner { |
| 456 | Result<std::vector<ReadRange>> Coalesce(std::vector<ReadRange> ranges) { |
| 457 | if (ranges.empty()) { |
| 458 | return ranges; |
| 459 | } |
| 460 | |
| 461 | // Remove zero-sized ranges |
| 462 | auto end = std::remove_if(ranges.begin(), ranges.end(), |
| 463 | [](const ReadRange& range) { return range.length == 0; }); |
| 464 | // Sort in position order |
| 465 | std::sort(ranges.begin(), end, |
| 466 | [](const ReadRange& a, const ReadRange& b) { return a.offset < b.offset; }); |
| 467 | // Remove ranges that overlap 100% |
| 468 | end = std::unique(ranges.begin(), end, |
| 469 | [](const ReadRange& left, const ReadRange& right) { |
| 470 | return right.offset >= left.offset && |
| 471 | right.offset + right.length <= left.offset + left.length; |
| 472 | }); |
| 473 | ranges.resize(end - ranges.begin()); |
| 474 | |
| 475 | // Skip further processing if ranges is empty after removing zero-sized ranges. |
| 476 | if (ranges.empty()) { |
| 477 | return ranges; |
| 478 | } |
| 479 | |
| 480 | #ifndef NDEBUG |
| 481 | for (size_t i = 0; i < ranges.size() - 1; ++i) { |
| 482 | const auto& left = ranges[i]; |
| 483 | const auto& right = ranges[i + 1]; |
| 484 | DCHECK_LE(left.offset, right.offset); |
| 485 | if (left.offset + left.length > right.offset) { |
| 486 | return Status::IOError("Some read ranges overlap"); |
| 487 | } |
| 488 | } |
| 489 | #endif |
| 490 | |
| 491 | std::vector<ReadRange> coalesced; |
| 492 | |
| 493 | auto itr = ranges.begin(); |
| 494 | // Ensure ranges is not empty. |
| 495 | DCHECK_LE(itr, ranges.end()); |
| 496 | // Start of the current coalesced range and end (exclusive) of previous range. |
| 497 | // Both are initialized with the start of first range which is a placeholder value. |
| 498 | int64_t coalesced_start = itr->offset; |
| 499 | int64_t prev_range_end = coalesced_start; |
| 500 | |
| 501 | for (; itr < ranges.end(); ++itr) { |
| 502 | const int64_t current_range_start = itr->offset; |
| 503 | const int64_t current_range_end = current_range_start + itr->length; |
| 504 | // We don't expect to have 0 sized ranges. |
| 505 | DCHECK_LT(current_range_start, current_range_end); |
| 506 | |
| 507 | // At this point, the coalesced range is [coalesced_start, prev_range_end). |
| 508 | // Stop coalescing if: |
| 509 | // - coalesced range is too large, or |
| 510 | // - distance (hole/gap) between consecutive ranges is too large. |
| 511 | if (current_range_end - coalesced_start > range_size_limit_ || |
| 512 | current_range_start - prev_range_end > hole_size_limit_) { |
| 513 | DCHECK_LE(coalesced_start, prev_range_end); |