Getting started
作为使用了版本管理的项目，开始新的开发，当然先要新建一个开发分支啦，可以用命令或者直接在IDE中GIT的图形控制界面操作，太简单就不细说。（我习惯命名：dev-lab1）
首先要从原始仓库合并Lab1的相关文件到本地仓库，接着在build目录下编译。执行下面的命令：
//你可能需要科学上网
git merge origin/lab1-startercode
//成功合并到本地仓库后，进入build目录
make -j4
等待编译完成，然后就可以在IDE界面的文件目录看到libsponge下多了两个文件：stream_reassembler.hh和stream_reassembler.cc
预备知识
首先来看项目提供的一副图片，如下：
这图完整展示项目的目的和架构（对TCP的抽象），lab0实现内层的ByteStream，lab1实现TCPReceiver(Lab2的目标)需要使用到的字节重组模块，lab3实现TCPSender，lab4实现TCPConnection(需要用到lab2和lab3的实现)。
Putting substring in sequence
根据PDF可知，要你实现一个StreamReassembler类，即流重组器，其接受一个完整的字节字符流或者该字符串首个字节index在后续字节流的子串，流的每一个字节都有唯一的index，从零开始向上增加。同时其拥有自己的ByteStream，一旦知道流的下一个字节，就将写入ByteStream中，ByteStream的所有者将可以随时读取和访问。
为什么这么做嘞？
TCP处理乱序和重复数据包的健壮性来自它能将字节流的任意摘录拼接会原始流的能力。在离散的可测试模块中实现这一功能使得处理传入段更加容易。
原始文件已经提供了完整的公共接口，你的任务是添加私有成员和成员函数，尽量不要修改公共接口
What’s the “capacity”?
注意，StreamReassembler是有内存使用限制的（不可能无限吧），所以对其设定容量（capacity），该容量由两部分组成：
-
重组后的ByteStream中字节数（下图绿色部分）
-
没有重组的子串的最大长度（下图红色部分）
注意： -
流的首个字节下标是从零开始的
-
包有重叠的，但不存在冲突的
-
尽快将接收到写入ByteStream，唯一不能写入该流的字节是其前一个字节没有被写入。即如果一个字节没有写入==_output==，那么前一个字节一定也没有被写入其中。如果存在下标为index的字节，那么[0,index-1]的字符存在，则[0,index]必须被写入==_output==（标号为零的存在一定也要被写入）
-
存在内容为空带有EOF标志的包
-
Lab1的时间花费测试应该小于半秒
首先针对流的下标，从零开始，那么就是无符号类型，结合 push_substring() 函数的参数可知，下标的上界应该是 UINT64_ 最大值
如何处理接收到的包（实际字节流片段）重叠？
对于重叠有两种情况：
- 容量的示意图中绿色部分的尾部超过接收到包的头部(如下图)
位于左侧绿色区域中的箭头表示接收到的包的index，绿色区域尾部的箭头是当前的位置的标记，所以可以在类中添加这个成员变量
- 绿色部分尾部标记小于接收到的流的index（如下图）
由于不存在冲突的情况，所以只用处理重叠，对于两种情况，从接收到的字节流的起始位置到结束位置写入ByteStream中分析就好做了。
对于起始位置的分析就两种情况，如果比当前标记小，那么就从当前标记开始写入，如果比当前标记大，就从该标记时写入
//index 是接收到流的头一个字节的标记，_cur_index是重组器类自己记录已经重组了末尾的标记
size_t st = max(index, _cur_index);
下边界已经出来了，再来分析上边界·······，对于上边界肯定有一个重组器自己设定的结束最大值标记，我们记为 _eof_index 其值初始化为uint64_最大值，然后对于接收到的流的index和其自身的长度data.size()之和，这两个数据谁小就是上边界。
等一下，是不是忘了什么？对，不知专门介绍了一遍重组器的容量嘛，用来管理内存占用，这个会不会对边界造成影响了？
先来分析一下，对于重组器本身设定的成员数据 _capacity，其是两部分之和，那么用容量减去绿色部分（重组器自身ByteStream的数据长度），就等于还可以写入的数据长度。这个数据长度是指从绿色部分的尾部开始的长度，所以加上_cur_index肯定也是一个边界。
综上，上边界就是在三个边界中选最小的那个，index+data.size()、_capacity - _output.buffer_size() + _cur_index、_eof_index
size_t ed = min(index + data.size(), mind(_cur_index + _capacity - _output.buffer_size(),_eof_index));
接着来分析，其标记末尾使用一个bool变量的EOF，那么就暗示，需要一个辅助的标记来判断每一个字节是否读取、是否是最后一个字符，这就想到和其一对一的bool数组，true表示还未读取，false表示已经读取或者到了末尾，所以可以用STL中的std::map，std::set直接模拟，但我自己用vector更熟练一些，同时还有pair<type,type>这个工具可以用，就想着能否用这个实现（vector可以用list，两者的底层实现还是不一样的，但支持的操作一样，后面检测一下）
push_substring()：
由于其传入是否为末尾的参数，所以函数内部首先需要判断是否为真，如果为真，则进一步判断 _eof_index 的值是否为64位无符号数最大值，如果是最大值，则更新_eof_index，使其等于接收到的流中头一个字节的标记和自身长度之和
if(eof){
if(_eof_index == numeric_limits<uint64_t>::max()){
_eof_index = index + data.size();
}
else if(_eof_index != index + data.size()){
throw runtime_error("StreamReassembler::push_string:: Inconsistent EOF index!\n");
}
}
然后再将接收到的流的每一个字节都用一个辅助bool标记
for(size_t i = st,j = st - index; i < ed; i++,j++){
std::pair<char,bool> &t = _stream[i % _capacity];
if(t.second){
if(t.first !=data[j]){
throw runtime_error("StreamReassembler::push_string:: Inconsistent substring!\n");
}
}
else{
t = make_pair(data[j],true);
_unreassembled_byte_count++;
}
}
将其写入重组器自身的ByteStream中（_output），需要一个临时的string
string str;
while (_cur_index < _eof_index && _stream[_cur_index % _capacity].second){
str.push_back(_stream[_cur_index % _capacity].first);
_stream[_cur_index % _capacity].second = false;
_unreassembled_byte_count--;
_cur_index++;
}
_output.write(str);
最后判断是否将此次的流写入完整了
if(_cur_index == _eof_index){
_output.end_input();
}
完整的头文件：
// Your code here -- add private members as necessary.
ByteStream _output; //!< The reassembled in-order byte stream
size_t _capacity; //!< The maximum number of bytes
std::vector<std::pair<char,bool>> _stream; //!< The current part of the unreassembled byte stream
uint64_t _cur_index; //!< The index of the first byte of the unreassembled byte stream
uint64_t _eof_index; //!< The index of the entire stream
size_t _unreassembled_byte_count; //!< The number of bytes that have not yet been reassembled
完整的源文件：
StreamReassembler::StreamReassembler(const size_t capacity) :
_output(capacity),
_capacity(capacity),
_stream(capacity),
_cur_index(0),
_eof_index(numeric_limits<uint64_t>::max()),
_unreassembled_byte_count(0){}
//! \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) {
size_t st = max(index,_cur_index);
size_t ed = min(index + data.size(),min(_cur_index + _capacity - _output.buffer_size(),_eof_index));
if(eof){
if(_eof_index == numeric_limits<uint64_t>::max()){
_eof_index = index + data.size();
}
else if(_eof_index != index + data.size()){
throw runtime_error("StreamReassembler::push_string:: Inconsistent EOF index!\n");
}
}
for(size_t i = st,j = st - index; i < ed; i++,j++){
std::pair<char,bool> &t = _stream[i % _capacity];
if(t.second){
if(t.first !=data[j]){
throw runtime_error("StreamReassembler::push_string:: Inconsistent substring!\n");
}
}
else{
t = make_pair(data[j],true);
_unreassembled_byte_count++;
}
}
string str;
while (_cur_index < _eof_index && _stream[_cur_index % _capacity].second){
str.push_back(_stream[_cur_index % _capacity].first);
_stream[_cur_index % _capacity].second = false;
_unreassembled_byte_count--;
_cur_index++;
}
_output.write(str);
if(_cur_index == _eof_index){
_output.end_input();
}
DUMMY_CODE(data, index, eof);
}
size_t StreamReassembler::unassembled_bytes() const { return _unreassembled_byte_count; }
bool StreamReassembler::empty() const { return _unreassembled_byte_count == 0; }
然后是结果：
文章来源：https://www.toymoban.com/news/detail-829219.html
emmmmm，这个速度貌似不合格呀，算了，暂时先这样，能跑起来再说，优化的事儿，后面搞文章来源地址https://www.toymoban.com/news/detail-829219.html
到了这里，关于CS144--Lab1笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
