TCP managed to produce a pair of reliable in-order byte streams (one from you to the server, and one in the opposite direction), even though the underlying network only delivers “best-effort” datagrams.
You also implemented the byte-stream abstraction yourself, in memory within one computer.
Over the next four weeks, you’ll implement TCP, to provide the byte-stream abstraction between a pair of computers separated by an unreliable datagram network.
size_t left = index, right = index + data.length(); // 初始化左右区间 size_t o_left = left, o_right = right; // keep the original value node tmp = {0, 0, ""};
if (right < left_bound) return; // must be duplicated left = left < left_bound ? left_bound : left; // 左边已经接受过的数据就不要了 string res = data.substr(left - o_left, right - left);// 掐头
/* 开始区间合并。需要扫描两次 */ // 第一次 for (auto it = buffer.begin(); it != buffer.end(); it++) { if (left >= it->left && left <= it->right) { // 区间重叠 size_t r = right,l = left; // 更新左右端点 right = max(right, it->right); left = min(left, it->left); if (r <= it->right) // 如果目标区间被包裹在it内 // res需要更新为it头+data掐头后的全长+it尾，也即将it中间重叠部分用data替换 res = it->data.substr(0, l - it->left) + data.substr(l - o_left) + it->data.substr(r - it->left, it->right - r); else res = it->data.substr(0, l - it->left) + data.substr(l - o_left); // 删除原来的结点 buffer.erase(it); break; } }
// 第二次 for (auto it = buffer.begin(); it != buffer.end(); it++) { if (it->left >= left && it->left <= right) { if (it->right <= right);// it这个区间被包含在目标区间内，则什么也不做 else { // 需要加上it的尾 res += it->data.substr(right - it->left, it->right - right); // 更新右端点 right = it->right; } // 删除 buffer.erase(it); } } // 将维护区间插入区间集合 tmp = {left, right, res}; buffer.insert(tmp);
classStreamReassembler { private: // Your code here -- add private members as necessary. structnode { size_t left; // 当前data位于总体的左index（闭） size_t right; // 右index（开） string data; booloperator<(const node &b) const { return left < b.left; } }; bool is_eof; // 文件的末尾是否接收成功 size_t left_bound; // 当前已经成功接收到left_bound之前的数据 set<node> buffer; // 存储结构
ByteStream _output; //!< The reassembled in-order byte stream size_t _capacity; //!< The maximum number of bytes public: // ... // used by the TCPReceiver voidset_is_eof(){ is_eof = false; } }
size_t left = index, right = index + data.length(); // 初始化左右区间 size_t o_left = left, o_right = right; // keep the original value auto iterator = buffer.begin(); // 这些变量在这里声明是为了防止后面goto报错 node tmp = {0, 0, ""};
if (right < left_bound) return; // must be duplicated left = left < left_bound ? left_bound : left; // 左边已经接受过的数据就不要了 right = right <= left_bound + _capacity ? right : left_bound + _capacity; // 右边越界的也不要 o_right = right; string res = data.substr(left - o_left, right - left);
size_t start = left; // the begin of the unused data-zone of variable data if (data.compare("") == 0 || res.compare("") == 0) goto end; // 如果data是空串也直接不要 if (o_left >= left_bound + _capacity) goto end; // 越界的不要
// 开始区间合并。需要扫描两次 for (auto it = buffer.begin(); it != buffer.end(); it++) { if (left >= it->left && left <= it->right) { size_t r = right; size_t l = left; right = max(right, it->right); left = min(left, it->left); if (right == it->right) { start = o_right; } else { start = it->right; } if (r <= it->right) { res = it->data.substr(0, l - it->left) + data.substr(l - o_left) + it->data.substr(r - it->left, it->right - r); } else { res = it->data.substr(0, l - it->left) + data.substr(l - o_left); } // 删除这一步很关键。 buffer.erase(it); break; } }
// 第二次 for (auto it = buffer.begin(); it != buffer.end(); it++) { if (it->left >= left && it->left <= right) { // 此时空间不够，先尝试下能不能写入一部分到_output中 if (it->left > start && remaining < it->left - start) { if (left == left_bound) { size_t out_mem = _output.remaining_capacity(); if (out_mem > 0) { // out的区域本身就很充足 if (out_mem >= it->left - start) { // 写入ByteStream _output.write(res.substr(0, it->left - start)); // 更新 res = res.substr(it->left - start); left_bound = it->left - start + left; left = left_bound; remaining += it->left - start; // out剩下的空位会在最后写入 goto ok; } else { // 光是out不够的话，那就先能腾多少空间腾多少 _output.write(res.substr(0, out_mem)); res = res.substr(out_mem); left_bound = out_mem + left; left = left_bound; remaining += out_mem; // 如果腾出空间加上原来空间足够，那就非常ok if (it->left > start && remaining >= it->left - start) { goto ok; } // 否则进入错误处理代码 } } } tmp = {left, start + remaining, res.substr(0, start - left + remaining)}; remaining = 0; if (eof == 1) is_eof = false; buffer.insert(tmp); goto end; } ok: remaining -= it->left - start; start = it->right; if (it->right > right){ res += it->data.substr(right - it->left, it->right - right); right = it->right; } buffer.erase(it); } } if (start < o_right && remaining < o_right - start) { right = start + remaining; if (eof == 1) is_eof = false; } tmp = {left, right, res}; if (left < right) buffer.insert(tmp);
