CS144 Lab Checkpoint 1: stitching substrings into a byte stream

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输出到writer
  output_.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;
}