| 419 | |
| 420 | struct ReadRangeCombiner { |
| 421 | Result<std::vector<ReadRange>> Coalesce(std::vector<ReadRange> ranges) { |
| 422 | if (ranges.empty()) { |
| 423 | return ranges; |
| 424 | } |
| 425 | |
| 426 | // Remove zero-sized ranges |
| 427 | auto end = std::remove_if(ranges.begin(), ranges.end(), |
| 428 | [](const ReadRange& range) { return range.length == 0; }); |
| 429 | // Sort in position order |
| 430 | std::sort(ranges.begin(), end, |
| 431 | [](const ReadRange& a, const ReadRange& b) { return a.offset < b.offset; }); |
| 432 | // Remove ranges that overlap 100% |
| 433 | end = std::unique(ranges.begin(), end, |
| 434 | [](const ReadRange& left, const ReadRange& right) { |
| 435 | return right.offset >= left.offset && |
| 436 | right.offset + right.length <= left.offset + left.length; |
| 437 | }); |
| 438 | ranges.resize(end - ranges.begin()); |
| 439 | |
| 440 | // Skip further processing if ranges is empty after removing zero-sized ranges. |
| 441 | if (ranges.empty()) { |
| 442 | return ranges; |
| 443 | } |
| 444 | |
| 445 | #ifndef NDEBUG |
| 446 | for (size_t i = 0; i < ranges.size() - 1; ++i) { |
| 447 | const auto& left = ranges[i]; |
| 448 | const auto& right = ranges[i + 1]; |
| 449 | DCHECK_LE(left.offset, right.offset); |
| 450 | if (left.offset + left.length > right.offset) { |
| 451 | return Status::IOError("Some read ranges overlap"); |
| 452 | } |
| 453 | } |
| 454 | #endif |
| 455 | |
| 456 | std::vector<ReadRange> coalesced; |
| 457 | |
| 458 | auto itr = ranges.begin(); |
| 459 | // Ensure ranges is not empty. |
| 460 | DCHECK_LE(itr, ranges.end()); |
| 461 | // Start of the current coalesced range and end (exclusive) of previous range. |
| 462 | // Both are initialized with the start of first range which is a placeholder value. |
| 463 | int64_t coalesced_start = itr->offset; |
| 464 | int64_t prev_range_end = coalesced_start; |
| 465 | |
| 466 | for (; itr < ranges.end(); ++itr) { |
| 467 | const int64_t current_range_start = itr->offset; |
| 468 | const int64_t current_range_end = current_range_start + itr->length; |
| 469 | // We don't expect to have 0 sized ranges. |
| 470 | DCHECK_LT(current_range_start, current_range_end); |
| 471 | |
| 472 | // At this point, the coalesced range is [coalesced_start, prev_range_end). |
| 473 | // Stop coalescing if: |
| 474 | // - coalesced range is too large, or |
| 475 | // - distance (hole/gap) between consecutive ranges is too large. |
| 476 | if (current_range_end - coalesced_start > range_size_limit_ || |
| 477 | current_range_start - prev_range_end > hole_size_limit_) { |
| 478 | DCHECK_LE(coalesced_start, prev_range_end); |