CS 144 Lab One -- 流重组器

//! \brief A class that assembles a series of excerpts from a byte stream
//! (possibly out of order, possibly overlapping) into an in-order byte stream.
class StreamReassembler {
  private:
    // Your code here -- add private members as necessary.
    struct Datum {
        char ch = 0;
        bool valid = false;
    };
    // 用于存放未按序达到的字节流
    std::vector<Datum> buffer_;  // buffer to store unassembled data.
    size_t buffer_header_;       // pointer to the begining of the unssembled bytes in
                                 // buffer.
    size_t unassembled_bytes_;
    size_t eof_byte_;
    bool is_eof_set_;    // true if read the eof
    // 存放按序到达的字节流,但是这部分字节流还没有被read
    ByteStream _output;  //!< The reassembled in-order byte stream
    size_t _capacity;    //!< The maximum number of bytes

  public:
    //! \brief Construct a `StreamReassembler` that will store up to
    //! `capacity` bytes. \note This capacity limits both the bytes that
    //! have been reassembled, and those that have not yet been
    //! reassembled.
    StreamReassembler(const size_t capacity);

    //! \brief Receive a substring and write any newly contiguous bytes
    //! into the stream.
    //!
    //! The StreamReassembler will stay within the memory limits of the
    //! `capacity`. Bytes that would exceed the capacity are silently
    //! discarded.
    //!
    //! \param data the substring
    //! \param index indicates the index (place in sequence) of the first
    //! byte in `data` \param eof the last byte of `data` will be the last
    //! byte in the entire stream
    void push_substring(const std::string &data, const uint64_t index, const bool eof);

    //! \name Access the reassembled byte stream
    //!@{
    const ByteStream &stream_out() const { return _output; }
    ByteStream &stream_out() { return _output; }
    //!@}

    //! The number of bytes in the substrings stored but not yet
    //! reassembled
    //!
    //! \note If the byte at a particular index has been pushed more than
    //! once, it should only be counted once for the purpose of this
    //! function.
    size_t unassembled_bytes() const;

    //! \brief Is the internal state empty (other than the output stream)?
    //! \returns `true` if no substrings are waiting to be assembled
    bool empty() const;
};

#include "stream_reassembler.hh"

#include <cassert>

// For Lab 1, please replace with a real implementation that passes the
// automated checks run by `make check_lab1`.

// You will need to add private members to the class declaration in
// `stream_reassembler.hh`

using namespace std;

StreamReassembler::StreamReassembler(const size_t capacity)
    : buffer_(capacity)
    , buffer_header_(0)
    , unassembled_bytes_(0)
    , eof_byte_(0)
    , is_eof_set_(false)
    , _output(capacity)
    , _capacity(capacity) {}

//! \details This function accepts a substring (aka a segment) of bytes,
//! possibly out-of-order, from the logical stream, and assembles any newly
//! contiguous substrings and writes them into the output stream in order.
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    if (_output.input_ended())
        return;
    const size_t max_byte = _output.bytes_read() + _capacity;
    const size_t index_start = std::max(_output.bytes_written(), index);
    size_t index_end = std::min(max_byte, index + data.length());
    // check for eof
    if (eof) {
        is_eof_set_ = true;
        eof_byte_ = index + data.length();
    }
    if (is_eof_set_)
        index_end = std::min(index_end, eof_byte_);

    // buffer the data
    for (size_t write_index = index_start; write_index < index_end; write_index++) {
        size_t cache_index = (buffer_header_ + write_index - _output.bytes_written()) % _capacity;
        assert(!(buffer_[cache_index].valid && buffer_[cache_index].ch != data[write_index - index]));
        if (!buffer_[cache_index].valid)
            unassembled_bytes_++;
        buffer_[cache_index].valid = true;
        buffer_[cache_index].ch = data[write_index - index];
    }

    // write the data.
    while (buffer_[buffer_header_].valid) {
        buffer_[buffer_header_].valid = false;
        _output.write_char(buffer_[buffer_header_].ch);
        unassembled_bytes_--;
        buffer_header_ = (buffer_header_ + 1) % _capacity;
    }
    if (is_eof_set_ && _output.bytes_written() >= eof_byte_)
        _output.end_input();
}

size_t StreamReassembler::unassembled_bytes() const { return unassembled_bytes_; }

bool StreamReassembler::empty() const { return unassembled_bytes_ == 0; }