当前位置: 首页 > news >正文

【斯坦福CS144】Lab1

一、实验目的

1.实现一个流重组器——一个将字节流的小块 (称为子串或段 )按正确顺序组装成连续的字节流的模块;

2.深入理解 TCP 协议的工作方式。

二、实验内容

编写一个名为"StreamReassembler"的数据结构,它负责重新组装数据。该结构将接收子串(由一串字节和大数据流中该串的第一个字节的索引组成),并提供一个名为"ByteStream"的输出,其中所有的数据都被正确排序。

三、实验过程

在minnow目录下,输入 git fetch 更新本地源仓库,此处显示更新失败是因为本次实验开始时源仓库已经最新,无需再次更新

输入git merge origin/check1-startercode获取Lab1

获取后输入cmake --build build来判断代码目前是否正常,结果为正常

用文本编辑器查看./src/reassembler.hh

修改代码,代码分析见注释

用文本编辑器查看./src/reassembler.cc

修改代码,代码分析见注释

保存并编译

输入make check1测试程序

全部通过

四、实验体会

1.下图完整地显示了CS144 这门实验的结构

ByteStream 是我们已经在 Lab0 中实现完成的。

我们在Lab1 中实现一个流重组器,一个将字节流的字串或者小段按照正确顺序来拼接回连续字节流的模块。

2.流重组器在 TCP 起到了相当重要的作用。迫于网络环境的限制,TCP 发送者会将数据切割成一个个小段的数据分批发送。但这就可能带来一些新的问题:数据在网络中传输时可能丢失、重排、多次重传等等。而TCP接收者就必须通过流重组器,将接收到的这些重排重传等等的数据包重新组装成新的连续字节流。

3.在调试的时候,所有的评测程序位于build/tests/中,进入此位置进行调试。

五、代码附录

reassembler.hh

#pragma once#include "byte_stream.hh"#include <string>
#include <list>
#include <tuple>class Reassembler
{bool had_last_ {};	// 是否已经插入了最后一个字符串uint64_t next_index_ {};	// 下一个要写入的字节的索引uint64_t buffer_size_ {};	// buffer_中的字节数std::list<std::tuple<uint64_t, uint64_t, std::string>> buffer_ {};/*** \breif 将data推入output流.*/void push_to_output(std::string data, Writer& output);/*** \brief 将data推入buffer暂存区.* \param first_index data的第一个字节的索引* \param last_index  data的最后一个字节的索引* \param data        待推入的字符串, 下标为[first_index, last_index]闭区间*/void buffer_push( uint64_t first_index, uint64_t last_index, std::string data );/*** 尝试将buffer中的串推入output流.*/void buffer_pop(Writer& output);public:/** Insert a new substring to be reassembled into a ByteStream.*   `first_index`: the index of the first byte of the substring*   `data`: the substring itself*   `is_last_substring`: this substring represents the end of the stream*   `output`: a mutable reference to the Writer** The Reassembler's job is to reassemble the indexed substrings (possibly out-of-order* and possibly overlapping) back into the original ByteStream. As soon as the Reassembler* learns the next byte in the stream, it should write it to the output.** If the Reassembler learns about bytes that fit within the stream's available capacity* but can't yet be written (because earlier bytes remain unknown), it should store them* internally until the gaps are filled in.** The Reassembler should discard any bytes that lie beyond the stream's available capacity* (i.e., bytes that couldn't be written even if earlier gaps get filled in).** The Reassembler should close the stream after writing the last byte.*/void insert( uint64_t first_index, std::string data, bool is_last_substring, Writer& output );// How many bytes are stored in the Reassembler itself?uint64_t bytes_pending() const;
};

reassembler.cc

#include "reassembler.hh"#include <ranges>
#include <algorithm>using namespace std;
void Reassembler::push_to_output( std::string data, Writer& output ) {next_index_ += data.size();output.push( move( data ) );
}void Reassembler::buffer_push( uint64_t first_index, uint64_t last_index, std::string data )
{// 合并区间auto l = first_index, r = last_index;auto beg = buffer_.begin(), end = buffer_.end();auto lef = lower_bound( beg, end, l, []( auto& a, auto& b ) { return get<1>( a ) < b; } );auto rig = upper_bound( lef, end, r, []( auto& b, auto& a ) { return get<0>( a ) > b; } );if (lef != end) l = min( l, get<0>( *lef ) );if (rig != beg) r = max( r, get<1>( *prev( rig ) ) );// 当data已在buffer_中时,直接返回if ( lef != end && get<0>( *lef ) == l && get<1>( *lef ) == r ) {return;}buffer_size_ += 1 + r - l;if ( data.size() == r - l + 1 && lef == rig ) { // 当buffer_中没有data重叠的部分buffer_.emplace( rig, l, r, move( data ) );return;}string s( 1 + r - l, 0 );for ( auto&& it : views::iota( lef, rig ) ) {auto& [a, b, c] = *it;buffer_size_ -= c.size();ranges::copy(c, s.begin() + a - l);}ranges::copy(data, s.begin() + first_index - l);buffer_.emplace( buffer_.erase( lef, rig ), l, r, move( s ) );
}void Reassembler::buffer_pop( Writer& output ) {while ( !buffer_.empty() && get<0>( buffer_.front() ) == next_index_ ) {auto& [a, b, c] = buffer_.front();buffer_size_ -= c.size();push_to_output( move( c ), output ); buffer_.pop_front();}if ( had_last_ && buffer_.empty() ) {output.close();}
}void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring, Writer& output )
{if ( data.empty() ) {if ( is_last_substring ) {output.close();}return;}auto end_index = first_index + data.size();                  // data: [first_index, end_index)auto last_index = next_index_ + output.available_capacity(); // 可用范围: [next_index_, last_index)if ( end_index < next_index_ || first_index >= last_index ) {return; // 不在可用范围内, 直接返回}// 调整data的范围if ( last_index < end_index ) {end_index = last_index;data.resize( end_index - first_index );is_last_substring = false;}if ( first_index < next_index_ ) {data = data.substr( next_index_ - first_index );first_index = next_index_;}// 若data可以直接写入output, 则直接写入if ( first_index == next_index_ && ( buffer_.empty() || end_index < get<1>( buffer_.front() ) + 2 ) ) {if ( buffer_.size() ) { // 若重叠, 则调整data的范围data.resize( min( end_index, get<0>( buffer_.front() ) ) - first_index );}push_to_output( move( data ), output );} else { // 否则, 将data插入buffer_buffer_push( first_index, end_index - 1, data );}had_last_ |= is_last_substring;// 尝试将buffer_中的数据写入outputbuffer_pop(output);
}uint64_t Reassembler::bytes_pending() const
{return buffer_size_;
}

相关文章:

【斯坦福CS144】Lab1

一、实验目的 1.实现一个流重组器——一个将字节流的小块 &#xff08;称为子串或段 &#xff09;按正确顺序组装成连续的字节流的模块&#xff1b; 2.深入理解 TCP 协议的工作方式。 二、实验内容 编写一个名为"StreamReassembler"的数据结构&#xff0c;它负责…...

药箱里的药及其常见药的作用

药箱里有常备药&#xff0c;经常买药&#xff0c;但是忘了自己有什么药。容易之间弄混&#xff0c;以此作为更新存储的媒介。 1、阿莫西林胶囊 处方药 是指需要由医师或者医疗人员开局处方才能购买的药物(常见的OTC是非处方药的意思)。 截止时间 2024 10/10 药品资料汇总&am…...

Android屏幕旋转流程(2)

&#xff08;1&#xff09;疑问 &#xff08;1&#xff09;settings put system user_rotation 1是什么意思&#xff1f; 答&#xff1a;设置用户期望的屏幕转向&#xff0c;0代表&#xff1a;Surface.ROTATION_0竖屏&#xff1b;1代表&#xff1a;Surface.ROTATION_90横屏&a…...

gaussdb hccdp认证模拟题(判断)

1.在事务ACID特性中&#xff0c;原子性指的是事务必须始终保持系统处于一致的状态。(1 分) 错。 2.某IT公司在开发软件时&#xff0c;需要使用GaussDB数据库&#xff0c;因此需要实现软件和数据的链接&#xff0c;而DBeaver是一个通用的数据库管理工具和 SQL 客户端&#xff…...

高效架构设计:JPA 实现单据管理,MyBatis 赋能报表查询的最佳实践

在现代企业应用开发中&#xff0c;数据持久层的设计与实现是至关重要的部分。开发者常常会面临选择如何合理地使用不同的数据访问框架&#xff0c;以最大限度地提升系统性能和开发效率。本文将讨论一种有效的搭配方案&#xff1a;使用 JPA 处理单据的增删改查操作&#xff0c;使…...

深入理解 CSS 浮动(Float):详尽指南

“批判他人总是想的太简单 剖析自己总是想的太困难” 文章目录 前言文章有误敬请斧正 不胜感恩&#xff01;目录1. 什么是 CSS 浮动&#xff1f;2. CSS 浮动的历史背景3. 基本用法float 属性值浮动元素的行为 4. 浮动对文档流的影响5. 清除浮动clear 属性清除浮动的技巧1. 使用…...

ElasticSearch学习笔记(三)Ubuntu 2204 server elasticsearch集群配置

如果你只是学习elasticsearch的增、删、改、查等相关操作&#xff0c;那么在windows上安装一个ES就可以了。但是你如果想在你的生产环境中使用Elasticsearch提供的强大的功能&#xff0c;那么还是建议你使用Linux操作系统。 本文以在Ubuntu 2204 server中安装elasticsearch 8.…...

基于STM32的简易交通灯proteus仿真设计(仿真+程序+设计报告+讲解视频)

基于STM32的简易交通灯proteus仿真设计(仿真程序设计报告讲解视频&#xff09; 仿真图proteus 8.9 程序编译器&#xff1a;keil 5 编程语言&#xff1a;C语言 设计编号&#xff1a;C0091 **1.**主要功能 功能说明&#xff1a; 以STM32单片机和数码管、LED灯设计简易交通…...

linux下新增加一块sata硬盘并使用

1&#xff09;确认新硬盘能被正确识别到 2&#xff09;对新硬盘进行分区 说明&#xff1a;fdisk指令中输入“m”&#xff0c;可以看到详细的指令含义。 3&#xff09;确认新创建的分区 5&#xff09;格式化新创建的分区 6&#xff09;挂载新分区并使用...

主从复制遇到的问题点

1.解决主从复制的配置问题 大致逻辑&#xff1a; 主库&#xff1a; 进入mysql的my.in文件&#xff0c;配置 server-id 1 log-bin mysql-bin log-bin D:/mysql/log binlog-do-db 数据库名 从库 进入mysql的my.in文件&#xff0c;配置 server-id 2 replicate-do-db 数据库名…...

Macbook ToDesk 无法连接网络

描述 网络连接的是 Wi-Fi&#xff0c;打开浏览器能跟正常浏览内容&#xff0c;说明 Wi-Fi 是正常的。 现象&#xff1a;显示网络连接失败&#xff0c;一直无法登陆&#xff01; 检查防火墙是没有阻止ToDesk 的任何连接&#xff0c;说明防火墙也是正常的。 解决 检查登录项&a…...

C++-容器适配器- stack、queue、priority_queue和仿函数

目录 1.什么是适配器 2.deque 1.简单了解结构 2.deque的缺陷 3.为什么选择deque作为stack和queue的底层默认容器 3.stack&#xff08;栈&#xff09; 4.queue&#xff08;队列&#xff09; 5.仿函数 6.priority_queue&#xff08;优先级队列&#xff09;&#xff08;堆…...

C++游戏开发指南

C游戏开发指南 引言 在这个数字娱乐时代&#xff0c;游戏行业炙手可热&#xff0c;你是否也憧憬着能亲自开发出一款独特的游戏呢&#xff1f;你是否想过&#xff0c;为什么越来越多的开发者选择C作为他们的开发语言&#xff1f;没错&#xff0c;C不仅是一种高效的编程语言&am…...

k8s的pod管理及优化

资源管理介绍 资源管理方式 命令式对象管理&#xff1a;直接用命令去操作kubernetes资源 命令式对象配置&#xff1a;通过命令配置和配置文件去操作kubernets资源 声明式对象配置&#xff1a;通过apply命令和配置文件去操作kubernets资源 命令式对象管理&#xff1a; 资源类…...

HTML 常用的块级元素和行内元素

1. 常用的块级元素 块级元素具有如下特点&#xff1a; 占据父容器的整行宽度。通常从新的一行开始。可以包含其他块级元素和行内元素。 常用的块级元素&#xff1a; div&#xff1a;通用的容器&#xff0c;用于布局和分块内容。 h1 到 h6&#xff1a;标题标签&#xff0c;定义…...

js短路求值

短路求值&#xff08;short-circuit evaluation&#xff09;是指在逻辑运算中&#xff0c;如果前面的表达式已经能够确定整个表达式的结果&#xff0c;后面的表达式就不会被执行。短路求值常见于逻辑运算符 &&&#xff08;与&#xff09;和 ||&#xff08;或&#xff0…...

react 知识点汇总(非常全面)

React 是一个用于构建用户界面的 JavaScript 库&#xff0c;由 Facebook 开发并维护。它的核心理念是“组件化”&#xff0c;即将用户界面拆分为可重用的组件。 React 的组件通常使用 JSX&#xff08;JavaScript XML&#xff09;。JSX 是一种 JavaScript 语法扩展&#xff0c;…...

如何加密重要U盘?U盘怎么加密保护?

在日常生活中&#xff0c;我们常常使用U盘来存储和传输重要文件。然而&#xff0c;U盘的便携性也意味着它容易丢失或被盗。为了保护U盘中的数据安全&#xff0c;我们需要对U盘进行加密。本文将为您介绍如何加密重要U盘&#xff0c;以及U盘加密保护的方法。 BitLocker BitLocke…...

js编写一个中奖程序

好的&#xff0c;以下是一个用JavaScript编写的抽奖程序&#xff0c;它根据给定的概率来决定奖项。我们将使用随机数生成器来模拟抽奖过程。 function drawPrize() {const prizes [{ name: 特等奖, probability: 0.00000001 },{ name: 一等奖, probability: 0.00000003 },{ n…...

Mybatis-plus的基础用法

文章目录 1. 核心功能1.1 配置与编写规则1.2 条件构造器1.3 自定义SQL1.4 IService接口1.4.1 Lambda方法1.4.2 批量新增 1.5 分页查询 2. 拓展功能2.1 代码生成器2.2 DB静态工具2.3 逻辑删除2.4 枚举处理器 参考 1. 核心功能 1.1 配置与编写规则 Maven依赖&#xff1a; <…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...