“拖了好几个月终于想起来给它完成了”
起因是自己想要复习巩固一下自己网络方面的知识，于是在Stanford CS144: Computer Network - CS自学指南 (csdiy.wiki)找到了这门课，看了一下课程实验设计的非常不错，需要自己实现一套 TCP 协议栈，而且还是用 C++ 实现，刚好最近在学C++，正好拿来练手，这门课B站上有录播，不过我主要是冲着实验去的所以没有看。还有一点需要注意，目前网上 2021spring 版的资料比较多，之后课程实验进行了一次较大的更新，代码框架全部重写，参考网上评论，新版本代码删去了较难的实验且部分实验不再需要写代码，出于学习的考虑，我还是选择 2021 spring进行学习。
实验要求
- 实现一个流重组器
- 需要拼接的子串是连续的，即子串内不存在空洞
- 子串之间可能交叉或者完全重叠
- 子串可能是一个只包含EOF标志的空串 上面列出来的是一些大致的要求，实际写代码的时候还有很多细化的问题：
- 判断容量是否满不是看你自己内部实现的缓冲区是否真的满了，而是进来的子串的 index 是否超过了容量
- 除非是在容量满的情况下带着 eof，否则你需要保存 eof 状态，随着子串的不断到来判断是否真的结束
我的思路
一开始我是想用链表之类的来实现，但是写着写着发现复杂度有点高，给自己心态写崩了，遂放弃。然后尝试使用一个类似大数组+对应标志位的方式实现，但是具体实现上出了问题，我出于性能考虑希望在进行子串合并到大数组的时候进行相应的裁剪之类的操作，结果发现要考虑的情况太多，代码变成了一堆 if-else，不好排查问题所以也放弃了，最终我选择了一个思路和实现都较为简单的方案，下面进行具体描述。
整体思路依旧是大数组+对应标志位，采用 deque实现，因为 deque 可以方便的进行前后插入；实现上我不在进行类似子串的部分合并的操作，具体来说：当子串需要合并进缓冲区时，不进行是否重叠之类的判断，而是直接将缓冲区扩充到可以容纳子串，然后直接将子串覆盖进相应的区域，这样省去了不少实现上的心智负担，就是性能可能差一些。
![[CS144lab1.png]] 上面是其中一种情况的示意图，要注意的是 buffer 中的内容并不一定是连续的，这里我省略了标志位buffer，用于标识 buffer 中每一个元素是否有内容。
代码实现
下面是具体的代码实现，部分简单的函数没有贴上： 这里解释下为什么合并后还需要判断是否输出 buffer 中的部分内容，这是因为有可能某个 substring 刚好接上了然后直接输出了，导致已重组但还未读的尾部超过了 buffer 的头部，所以需要再次检查。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class StreamReassembler {
private:
ByteStream _output; //!< The reassembled in-order byte stream
size_t _capacity; //!< The maximum number of bytes
size_t _first_unassemble = 0; // _output.wirtten()
size_t _next_assemble = 0; // 实际上就是 buffer 的开头
bool has_eof = false;
std::deque<char> _buffer = {};
std::deque<bool> _wflags = {};
};
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
size_t len = data.length();
// 容量满了，跳过
if (index > _capacity + _output.bytes_read())
return;
if (eof)
has_eof = eof;
if (_buffer.empty() && data.empty() && has_eof) {
_output.end_input();
return;
}
// substring 整个已经输出过了，跳过
if (index + len <= _first_unassemble)
return;
// 部分substring或刚好接上，直接输出
if (index <= _first_unassemble) {
size_t ret = _output.write(data.substr(_first_unassemble - index));
_first_unassemble += ret;
}
if (index > _first_unassemble) {
// 1. 计算合并后的 buffer 应该多大
size_t min_index = min(index, _next_assemble);
size_t max_index = max(index + len, _next_assemble + _buffer.size());
// 2. 将 buffer 向两边延展
if (min_index < _next_assemble) {
// 向左扩充
for (size_t i = 0; i < _next_assemble - min_index; i++) {
_buffer.push_front(0);
_wflags.push_front(false);
}
}
if (_next_assemble + _buffer.size() < max_index) {
// 向右扩充
size_t r_limit = max_index - _next_assemble - _buffer.size();
for (size_t i = 0; i < r_limit; i++) {
_buffer.push_back(0);
_wflags.push_back(false);
}
}
// 3. 用 subring 的内容覆盖 延展后的 buffer
size_t offset = index - min_index;
for (size_t i = 0; i < len; i++) {
if (_wflags[i + offset])
continue;
_buffer[i + offset] = data[i];
_wflags[i + offset] = true;
}
// 4. 更新 _next_assemble
_next_assemble = min_index;
}
// 判断是否输出 _buffer 中的部分内容
// a. buffer 不需要输出，返回
if (_next_assemble > _first_unassemble)
return;
// b. buffer 中有数据且开头输出过了
if (_buffer.size() && _next_assemble < _first_unassemble) {
// 去掉输出过的部分
size_t offset = _first_unassemble - _next_assemble;
for (size_t i = 0; i < offset; i++) {
_buffer.pop_front();
_wflags.pop_front();
_next_assemble++;
}
if (!_buffer.empty()) {
// 后面的内容需要输出
while (!_wflags.empty() && _wflags.front()) {
_output.write_char(_buffer.front());
_buffer.pop_front();
_wflags.pop_front();
_next_assemble++;
_first_unassemble++;
}
}
}
if (has_eof && _buffer.empty()) {
_output.end_input();
}
}
代码调试
**你一定会用到** 参考 【计算机网络】Stanford CS144 Lab Assignments 学习笔记 - 康宇PL - 博客园 (cnblogs.com)中调试方法论一节