Stanford-CS144-Sponge 笔记 - Lab 1: Stitching Substrings Into A Byte Stream

第一个实验要求实现一个流重组器（stream reassembler），可以将带索引的字节流碎片重组成有序的字节流。

1. OverView

如上图所示，这是我们要实现的TCP的各个部分。

在Lab0中，我们实现的是ByteStram。
在Lab1中，我们将实现一个流重组器（stream reassembler），用于将从字节流中提取到的各个片段按照正确的顺序重组成有序的字节流。
在Lab2中，我们将实现接收端，即TCPReveiver。
在Lab3中，我们将实现发送端，即TCPSender。
在Lab4中，我们将之前实现的各个部分组合而成一个TCPConnection。

2. Putting substrings in sequence

在本实验中，你将实现一个流重组器，他将接受各个片段，并根据序号将其组成一个完整的信息。流中的每个字都有自己的唯一的ID。该流重组器拥有一个ByteStream对象用于输出，每当该重组器得到一段排序好的数据后，就将其传递给ByteStream。

2.1 What’s the “capacity”?

push substring方法需要忽略任何超出capacity的数据，即避免占用过大的内存。这能够保证其不会无限的占用内存。capacity包含大小的说明如下：

2.2 FAQs

Q：在每个流中首个数据包的ID是什么？
A：0
Q：我的实现应该达到怎样的性能？
A：请不要将此视为构建一个空间或时间效率非常低的数据结构的挑战——该数据结构将是您的TCP实现的基础。一个大致的预期是，每个新的Lab 1测试可以在不到半秒的时间内完成。
Q：不一致的substring应该如何处理？
A：你可以假设它们不存在。也就是说，您可以假设存在一个唯一的底层字节流，并且所有子字符串都是它的(准确的)片段。
Q：我可以使用什么？
A：你可以使用标准库中任何你觉得有用的部分。特别是，我们希望您至少使用一种数据结构。
Q：什么时候应该将字节写入流？
A：尽快，除非它前面的字节还没有被push。
Q：push_substring方法中被提供的substrings可能重复吗？
A：可能。
Q：我需要添加私有成员到StreamReassembler吗？
A：是的。子字符串可以以任何顺序到达，所以你的数据结构必须“记住”子字符串，直到它们准备好放入流中——也就是说，直到它们之前的所有索引都被写入。
Q：我们重新组装的数据结构可以存储重叠的子字符串吗？
A：不。实现一个存储重叠子字符串的“接口正确”重装程序是可能的。但是允许重新组装者这样做会削弱“容量”作为内存限制的概念。

解决方案
我们需要增加一些成员变量：

// libsponge\stream_reassembler.hh
   ByteStream output_;  //!< The reassembled in-order byte stream
   size_t capacity_;    //!< The maximum number of bytes
   size_t unassembled_bytes_; // 未发送至output_的数据大小
   std::string datas_; // 数据
   std::unordered_set<uint64_t> write_flag_; // 该数据位是否已经写入
   size_t next_index_; // 下一个要写入的index
   bool is_eof_; // 是否收到eof位

然后主要需要实现push_substring方法，其中对于datas_需要动态扩容，因为收到的数据可能是乱序的，导致空间不够：

// libsponge\stream_reassembler.cc
StreamReassembler::StreamReassembler(const size_t capacity)
   : output_(capacity)
   , capacity_(capacity)
   , unassembled_bytes_(0)
   , datas_(capacity, '\0')
   , write_flag_(capacity)
   , next_index_(0)
   , is_eof_(false) {}

//! \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 (index >= next_index_ + output_.remaining_capacity()) {
       return;
   }
   // 设置eof标志
   if (eof && index + data.size() <= next_index_ + output_.remaining_capacity()) {
       is_eof_ = true;
   }
   // 如果所有数据都已经保存过了，那就跳过
   if (index + data.size() > next_index_) {
       // 将数据保存到datas_中，从index和next_index_中更大的一方开始，避免无用循环
       for (size_t i = (index > next_index_? index: next_index_); i < next_index_ + output_.remaining_capacity() && i < index + data.size(); i++) {
           if (write_flag_.count(i) == 0) {
               // 动态扩容
               if (datas_.capacity() <= i) {
                   datas_.reserve(i * 2);
               }
               datas_[i] = data[i - index];
               write_flag_.insert(i);
               unassembled_bytes_++;
           }
       }
       // 将已经有序的数据发送到字节流中
       while (write_flag_.count(next_index_) > 0) {
           output_.write(datas_[next_index_]);
           write_flag_.erase(next_index_);
           next_index_++;
           unassembled_bytes_--;
       }
   }
   // 如果输入结束且所有数据都发送了，则结束字节流
   if (is_eof_ && empty()) {
       output_.end_input();
   }
}

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

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

在上个实验的ByteStream中，我选择重写write方法，提供一次放入一个字符的功能：

// libsponge\byte_stream.cc
size_t ByteStream::write(const char data) {
   // 获取数据大小
   if (remaining_capacity() <= 0)
       return 0;
   // 保存数据并更新信息
   buffer_ += data;
   used_++;
   total_write_++;
   return 1;
}