cs144 LAB1 基于滑动窗口的碎片字节流重组器

2024-06-19 17:52

本文主要是介绍cs144 LAB1 基于滑动窗口的碎片字节流重组器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.StreamReassembler.capacity 的意义

StreamReassembler._capacity 的含义:

capacity

  • ByteStream 的空间上限是 capacity
  • StreamReassembler 用于暂存未重组字符串片段的缓冲区空间 StreamReassembler.buffer 上限也是 capacity
  • 蓝色部分代表了已经被上层应用读取的已重组数据
  • 绿色部分代表了 ByteStream 中已经重组并写入但还未被读取的字节流所占据的空间大小
  • 红色部分代表了 StreamReassembler 中已经缓存但未经重组的若干字符串片段所占据的空间大小
  • 同时绿色和红色两部分加起来的空间总占用大小不会超过 capacity(事实上会一直小于它)

从代码层面来看:

  • first unread 的索引等于 ByteStream 的 bytes_read() 函数的返回值(我们一般不关注这个值)
  • first unassembled 的索引等于 ByteStream 的 bytes_write() 函数的返回值(起始就是下一个期望的字节在流中的序号)
  • first unacceptable 的索引等于 ByteStream 的 bytes_read() 加上 capacity 的和(已超过 ByteStream 的 buffer 限制)
  • first unread 和 first unacceptable 这两个边界是动态变化的,每次重组结束都需要更新。

最后,有个很重要点,ByteStream 和 StreamReassembler 的总容量有固定的限制,多余的数据需要丢弃(此需要对端重传数据,这就引出了重传等知识点)

二.滑动窗口碎片重组算法 

        每次收到的data数据由于网络传输不可靠的原因会产生乱序,重叠。需要对每次收到的碎片序列进行重组。可以定义装配器的窗口大小为capacity,范围为[_first_unassembled,_first_unassembled + _capacity]。超出此范围的字节将被丢弃(实验要求,之后会引出重传)。窗口会随着第一个期望的字节序号进行移动即_first_unassembled。每次计算缓冲区第一个期望字节序号,并保障每个字节碎片都在窗口范围内,这需要对碎片进行裁剪,裁剪过后的碎片可以直接加入缓存区。

        可分为下面几个步骤完成:

1.计算重组器窗口起始位置,结束位置。

2.判断碎片是否合法,不合法则直接丢弃。

3.裁剪碎片,使其满足缓冲区要求。

4.碎片加入缓存区。

5.缓存区写入流。(如果缓冲区头部有元素的话)

6.判断EOF。

        需要注意EOF这里有几个大坑,首先是EOF可能会提早到来,这时不能直接结束流写入需要进行判断。第二是EOF可能与其他流重叠,故而可以记录EOF的合法结束字节位置来判断是否真正需要停止流写入。

#ifndef SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
#define SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH#include "byte_stream.hh"#include <cstdint>
#include <string>
#include <deque>//! \brief A class that assembles a series of excerpts from a byte stream (possibly out of order,
//! possibly overlapping) into an in-order byte stream.
class StreamReassembler {private:// Your code here -- add private members as necessary.std::deque<std::string::value_type> _reassembler_buffer;  //重组器缓冲区std::deque<bool> _bytes_flag; //重组器字节标志位std::size_t _unassembaled_bytes = 0;  //未被装配的字节bool _is_eof = false; //判断子序列是否含有EOFstd::size_t _eof_index = 0; //记录EOF段最后一个字节的位置ByteStream _output;  //!< The reassembled in-order byte streamsize_t _capacity;    //!< The maximum number of bytespublic://! \brief Construct a `StreamReassembler` that will store up to `capacity` bytes.//! \note This capacity limits both the bytes that have been reassembled,//! and those that have not yet been reassembled.StreamReassembler(const size_t capacity);//! \brief Receive a substring and write any newly contiguous bytes into the stream.//!//! The StreamReassembler will stay within the memory limits of the `capacity`.//! Bytes that would exceed the capacity are silently discarded.//!//! \param data the substring//! \param index indicates the index (place in sequence) of the first byte in `data`//! \param eof the last byte of `data` will be the last byte in the entire streamvoid push_substring(const std::string &data, const uint64_t index, const bool eof);//! \name Access the reassembled byte stream//!@{const ByteStream &stream_out() const { return _output; }ByteStream &stream_out() { return _output; }//!@}//! The number of bytes in the substrings stored but not yet reassembled//!//! \note If the byte at a particular index has been pushed more than once, it//! should only be counted once for the purpose of this function.size_t unassembled_bytes() const;//! \brief Is the internal state empty (other than the output stream)?//! \returns `true` if no substrings are waiting to be assembledbool empty() const;
};#endif  // SPONGE_LIBSPONGE_STREAM_REASSEMBLER_HH
#include "stream_reassembler.hh"// Dummy implementation of a stream reassembler.// For Lab 1, please replace with a real implementation that passes the
// automated checks run by `make check_lab1`.// You will need to add private members to the class declaration in `stream_reassembler.hh`template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}using namespace std;StreamReassembler::StreamReassembler(const size_t capacity) : 
_reassembler_buffer(capacity, '\0'),
_bytes_flag(capacity, false),
_output(capacity),
_capacity(capacity) {}//! \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) {//判断index是否合法std::size_t _first_unassembled = _output.bytes_written();   //每次计算期望的字节序号std::size_t _first_unacceptable = _first_unassembled + _capacity;   //第一个不允许装配的字节序号if(index >= _first_unacceptable || index + data.length() < _first_unassembled)return;//滑动窗口位于[_first_unassembled,_first_unassembled + _capacity]之间只有其中元素可以入队,对data进行裁剪std::size_t new_index = index;std::size_t new_end = index + data.length();if(new_index < _first_unassembled)new_index = _first_unassembled;if(new_end >= _first_unacceptable)new_end = _first_unacceptable;//裁剪完成后data的起始位置符合滑动窗口要求,入队for(std::size_t i = new_index; i < new_end; ++i){if(!_bytes_flag[i - _first_unassembled]){_reassembler_buffer[i - _first_unassembled] = data[i - index];   //入队_bytes_flag[i - _first_unassembled] = true;  //相应标志位置位++_unassembaled_bytes;  //缓冲区计数增加}}//写入流操作(当装配缓冲区头部有元素那么一定是顺序的直接写入流)string wait_to_write{};while(_bytes_flag.front()){wait_to_write += _reassembler_buffer.front();_bytes_flag.pop_front();_reassembler_buffer.pop_front();_bytes_flag.emplace_back(false);        //维护缓冲区大小_reassembler_buffer.emplace_back('\0'); //维护缓冲区大小}if(wait_to_write.size() > 0){int out_bytes = _output.write(std::move(wait_to_write));_unassembaled_bytes -= out_bytes;}//检查eofif(eof){_is_eof = true;_eof_index = new_end;}if(_is_eof && _eof_index == _output.bytes_written())_output.end_input();
}size_t StreamReassembler::unassembled_bytes() const { return _unassembaled_bytes; }bool StreamReassembler::empty() const { return _unassembaled_bytes == 0; }

 

这篇关于cs144 LAB1 基于滑动窗口的碎片字节流重组器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075727

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

为什么现在很多人愿意选择做债务重组?债重组真的就这么好吗?

债务重组,起初作为面向优质企业客户的定制化大额融资策略,以其高效周期著称,一个月便显成效。然而,随着时代的车轮滚滚向前,它已悄然转变为负债累累、深陷网贷泥潭者的救赎之道。在此路径下,个人可先借助专业机构暂代月供,经一段时间养护征信之后,转向银行获取低成本贷款,用以替换高昂网贷,实现利息减负与成本优化的双重目标。 尽管债务重组的代价不菲,远超传统贷款成本,但其吸引力依旧强劲,背后逻辑深刻。其一

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

主窗口的设计与开发(二)

主窗口的设计与开发(二) 前言         在上一集当中,我们完成了主窗口的初始化,主窗口包括了左中右三个区域。我们还完成了对左窗口的初始化,左窗口包括了用户头像、会话标签页按钮、好友标签页按钮以及好友申请标签页按钮。对于切换每个标签页,我们还做了初始化信号槽的内容。最后我们将整个MainWidget类设置为单例模式。         那么这一集我们将继续完成主窗口的设计与开发,这一集我

QtC++截图支持窗口获取

介绍 在截图工具中你会发现,接触到窗口后会自动圈出目标窗口,个别强大一点的还能进行元素识别可以自动圈出元素,那么今天简单分析一下QTc++如何获取窗口并圈出当前鼠标下的窗口。 介绍1.如何获取所有窗口2.比较函数3.实现窗口判断 结尾 1.如何获取所有窗口 1.我们需要调用windows接口EnumWindowsProc回调函数来获取所有顶级窗口,需要包含windows.

JVM - 字节码文件详解

文章目录 目录 文章目录 1. 无关性基石 2. Class类文件结构 magic- 魔数 主副版本号 常量池 访问标志 类索引,父类索引与接口索引集合 字段 方法 属性 3. 类加载机制 类的生命周期 类加载过程 加载 连接 验证 准备 解析 初始化 4. 类加载器 类与类加载器 类加载器的分类 启动类加载器  扩展类加载器 应用程序类加

运行.bat文件,如何在Dos窗口里面得到该文件的路径

把java代码打包成.jar文件,编写一个.bat文件,执行该文件,编译.jar包;(.bat,.jar放在同一个文件夹下) 运行.bat文件,如何在Dos窗口里面得到该文件的路径,并运行.jar文件: echo 当前盘符:%~d0 echo 当前路径:%cd% echo 当前执行命令行:%0 echo 当前bat文件路径:%~dp0 echo 当前bat文件短路径:%~sdp0 nc

类codepen的实现可拖拽窗口demo

首先说下思想 flex或者其他布局方式,实现左右分割布局,主盒子宽度100%,左右布局中包含一个分割条(可在布局容器中,也可以单独定义)为分隔条绑定鼠标点击事件,为document绑定鼠标移动事件和鼠标放开事件,通过监听鼠标移动事件和上一个状态保存下来的鼠标位置作对比,判断当前鼠标移动方向(往左还是往右)然后计算当前鼠标位置和鼠标点击位置的距离,来计算左右容器的变化,然后通过dom的方式设置宽度