|
25 | 25 | #include <immintrin.h> |
26 | 26 | #endif |
27 | 27 | #include <algorithm> |
| 28 | +#include <array> |
28 | 29 | #include <cstddef> |
29 | 30 | #include <cstring> |
30 | 31 | #include <ostream> |
@@ -287,6 +288,82 @@ inline bool NewPlainTextLineReader::update_eof() { |
287 | 288 | return _eof; |
288 | 289 | } |
289 | 290 |
|
| 291 | +Status NewPlainTextLineReader::skip_split_prefix(size_t split_start, const std::string& delimiter, |
| 292 | + bool* eof, const io::IOContext* io_ctx, |
| 293 | + size_t* skipped_lines) { |
| 294 | + DCHECK_EQ(_total_read_bytes, 0); |
| 295 | + DCHECK_EQ(_output_buf_limit, 0); |
| 296 | + bool overlaps = false; |
| 297 | + if (delimiter.size() > 1) { |
| 298 | + // Compute the KMP prefix function once for this split in linear time. A nonempty |
| 299 | + // proper prefix that is also a suffix of the whole delimiter permits overlapping matches. |
| 300 | + std::vector<size_t> prefix_lengths(delimiter.size()); |
| 301 | + for (size_t i = 1, matched = 0; i < delimiter.size(); ++i) { |
| 302 | + while (matched > 0 && delimiter[i] != delimiter[matched]) { |
| 303 | + matched = prefix_lengths[matched - 1]; |
| 304 | + } |
| 305 | + if (delimiter[i] == delimiter[matched]) { |
| 306 | + ++matched; |
| 307 | + } |
| 308 | + prefix_lengths[i] = matched; |
| 309 | + } |
| 310 | + overlaps = prefix_lengths.back() > 0; |
| 311 | + } |
| 312 | + |
| 313 | + if (overlaps && _decompressor == nullptr) { |
| 314 | + // A fixed lookbehind can start in an overlapping delimiter chain (e.g. three newlines |
| 315 | + // with a two-newline delimiter). Find a byte that cannot belong to any delimiter, then |
| 316 | + // replay greedy matches from immediately after it. Keep scratch bounded even for long |
| 317 | + // delimiter runs; ordinary delimiters do not need this extra I/O. |
| 318 | + std::array<bool, 256> delimiter_bytes {}; |
| 319 | + for (unsigned char byte : delimiter) { |
| 320 | + delimiter_bytes[byte] = true; |
| 321 | + } |
| 322 | + constexpr size_t max_lookbehind_size = 64 * 1024; |
| 323 | + std::vector<char> buffer(1024); |
| 324 | + size_t sync_offset = _current_offset; |
| 325 | + bool synchronized = false; |
| 326 | + while (sync_offset > 0 && !synchronized) { |
| 327 | + const size_t length = std::min(sync_offset, buffer.size()); |
| 328 | + const size_t offset = sync_offset - length; |
| 329 | + size_t bytes_read = 0; |
| 330 | + RETURN_IF_ERROR(_file_reader->read_at(offset, Slice(buffer.data(), length), &bytes_read, |
| 331 | + io_ctx)); |
| 332 | + if (bytes_read != length) { |
| 333 | + return Status::IOError("Short read while aligning text split at offset {}", |
| 334 | + split_start); |
| 335 | + } |
| 336 | + sync_offset = offset; |
| 337 | + for (size_t i = length; i > 0; --i) { |
| 338 | + if (!delimiter_bytes[static_cast<unsigned char>(buffer[i - 1])]) { |
| 339 | + sync_offset = offset + i; |
| 340 | + synchronized = true; |
| 341 | + break; |
| 342 | + } |
| 343 | + } |
| 344 | + if (!synchronized && sync_offset > 0) { |
| 345 | + // Extend backward into new bytes; do not reread the already searched suffix. |
| 346 | + buffer.resize(std::min(buffer.size() * 2, max_lookbehind_size)); |
| 347 | + } |
| 348 | + } |
| 349 | + _min_length += _current_offset - sync_offset; |
| 350 | + _current_offset = sync_offset; |
| 351 | + } |
| 352 | + |
| 353 | + const size_t prefix_length = split_start - _current_offset; |
| 354 | + const uint8_t* line = nullptr; |
| 355 | + size_t size = 0; |
| 356 | + size_t skipped = 0; |
| 357 | + do { |
| 358 | + RETURN_IF_ERROR(read_line(&line, &size, eof, io_ctx)); |
| 359 | + skipped += !*eof; |
| 360 | + } while (!*eof && _total_read_bytes < prefix_length); |
| 361 | + if (skipped_lines != nullptr) { |
| 362 | + *skipped_lines = skipped; |
| 363 | + } |
| 364 | + return Status::OK(); |
| 365 | +} |
| 366 | + |
290 | 367 | // extend input buf if necessary only when _more_input_bytes > 0 |
291 | 368 | void NewPlainTextLineReader::extend_input_buf() { |
292 | 369 | DCHECK(_more_input_bytes > 0); |
|
0 commit comments