CS144 Lab Checkpoint 1: stitching substrings into a byte stream

devtools/2025/3/6 19:24:39/

Putting substrings in sequence

TCP报文在发送方会被分成许多数据报文，传输中可能出现顺序的重排以及丢失和重发等现象，所以需要重装数据报文到原来字节流的顺序。

在本实验中，要实现的是重组器Reassembler，它接受子字符串和其中第一个字节的索引。流的每一个字节都有自己的索引，并从零开始计数。

What should the Reassembler store internally?

原则上，重组器必须处理三类知识：

流中的下一个字节。重组器一旦知道，立即将其推送到流。
在流的长度范围内但是暂时无法写入的字节。这些字节应该被存储在重组器中。
超出可用容量的字节。这些字节应该被丢弃。

在这里插入图片描述

本次要修改的文件是reassembler.hh和reassembler.cc，首先先在头文件中修改成员变量和构造函数如下

  size_t _capacity;                          std::vector<std::pair<char, bool>> _stream;size_t _cur_index;                          size_t _eof_index;                          size_t _unassembled_bytes_cnt;

然后修改构造函数如下

  explicit Reassembler( ByteStream&& output ): output_( std::move( output ) ), _capacity( output.writer().available_capacity() ), _stream( output.writer().available_capacity() ), _cur_index( 0 ), _eof_index( std::numeric_limits<uint64_t>::max() ), _unassembled_bytes_cnt( 0 ){}

这里需要注意的一点是，相比较之前的实验代码，新版代码将Reader和Writer分离，我们需要通过Writer的available_capacity()去访问ByteStream的容量。
然后在reassembler.cc中修改如下，这里参考了CS144 Lab：Lab1 – LRL52 的博客的博客的做法，他用vector存储pair对的方式，first元素存储字符，second元素存储是否被占用，这种处理方法很高效。

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{// Your code here.// 首先确认要写入重组器的首末位置 uint64_t start = max( _cur_index, first_index );uint64_t end= min( first_index + data.size(), min( _cur_index + output_.writer().available_capacity(), _eof_index ) );// 如果是最后的子串，就记录结束下标if ( is_last_substring ) {_eof_index = min( _eof_index, first_index + data.size() );}// 写入重组器中for ( uint64_t i = start, j = start - first_index; i < end; i++, j++ ) {auto& t = _stream[i % _capacity];//如果重复出现的子串，前后不一致则报错if ( t.second == true ) {if ( t.first != data[j] )throw __throw_runtime_error;}// 之前没有占用的位置就将data对应位置的元素放入，然后重组器内的元素个数自增else {t = make_pair( data[j], true );++_unassembled_bytes_cnt;}}string str;// 将重组器中从_cur_index开始的直到终止下标或者是无效下标的元素写入字符串str中while ( _cur_index < _eof_index && _stream[_cur_index % _capacity].second == true ) {str.push_back( _stream[_cur_index % _capacity].first );// 一旦写入，重组器对应位置就要清空_stream[_cur_index % _capacity] = { 0, false };--_unassembled_bytes_cnt;++_cur_index;}// str输出到writeroutput_.writer().push( str );if ( _cur_index == _eof_index )output_.writer().close();
}// 返回还有多少字节存储在Reassembler中
uint64_t Reassembler::bytes_pending() const
{// Your code here.return _unassembled_bytes_cnt;
}