本文记录了 Lab 1: stitching substrings into a byte stream 的实验过程

Lab 材料：Lab 1: stitching substrings into a byte stream

目的：在 Lab 0 的基础上实现 TCPReceiver 的 StreamReassembler，它会将一个个小片段的 byte stream 已正确的方式重新组合成连续的字节流。

（1）由于网络是尽自己最大努力投递数据报，因此数据包可能会丢失，失序，重复，数据内容被更改等等。在这个实验中，我们需要解决以下问题：

  • 失序：数据到到达的顺序和发出的顺序不一致，例如：index = 4, "efgh"，index = 0, "abcd"
  • 重复：重复收到某个数据，例如：index = 0, "abcd"，index = 0, "abcd"
  • 重叠：收到数据中的某些字符已经在之前接收了，例如：index = 0, "abc"，index = 2, "cdefg"

（2）由于 StreamReassembler 是有容量限制的。因此，对于收到的数据，如果它的长度大于当前可以存储的最大容量，我们将丢弃超出的部分。

思路

一开始我是想用 std::map<uint64_t, std::string> 保存收到的数据，然后再进行合并数据。但是写着写着发现处理起来有点麻烦。于是就转换思路，使用 std::unordered_map<uint64_t, char> 存储单个 index 和它对应的字符。每接收到一个数据时，进行 merge 操作，然后循环处理是否可以将当前 received 的数据写入 ByteStream 中，最后判断是否结束。

1
2
3
4
5
6
7
std::unordered_map<uint64_t, char> _receiver;	// 保存收到的 data 以及 index
size_t _expect_index;		// 期望收到数据的 index
size_t _total_unassembled;	// 当前未组装的字符个数
bool _eof;                  // 如果传入的 eof = 1，则设置它为 true

// 处理失序、重复、重叠的数据
void merge(const std::string &data, const uint64_t index);

测试

1
2
make -j4
make check_lab1