## 参考
https://doraemonzzz.com/2022/01/30/2022-1-30-CS144-Lab1%E7%BF%BB%E8%AF%91/
## 目标
TCP发送方将其字节流分为短段（每个子串不超过1,460字节），以便它们各自在一个数据报中。但网络可能会对这些数据报进行重新排序，或丢弃它们，或多次传送它们。接收方必须将这些片段重新组合成它们开始时的连续的字节流。
## 直观理解
### 故事背景：组装书页
想象有一家图书装订厂，需要把一堆**散页**的书页（很可能"乱序"地送到厂里）**组合**成一本**有序**的书。每一页都有自己的**页码**（类似我们的 `index`），我们最终要把它们**按页码顺序**排列好，然后**装订**成一本完整的书（类似输出 `ByteStream`）。
在这个故事中：
1. **散页** = 分段的字节数据（`push_substring` 传入的 `data`）。
2. **页码** = 数据对应的逻辑下标（参数 `index`）。
3. **装订好的书** = 最终输出流（`_output`）。
4. **装订厂的工作台** = `StreamReassembler` 的内部缓冲区（`buffer` + `bitmap`）。
5. **最大可工作台容量** = 代码里的 `capacity`。
---
### 缓冲区（buffer + bitmap）就是一本"占位"的大本子
- 你可以把 `StreamReassembler` 内部的 `buffer` 想象成一个**摆满空白插槽的大本子**：它有固定的"页数"（对应 `capacity`），这些页面现在都是空白（或填着 `'\0'`），等待我们把真正的书页插入进来。
- 为了标记哪些页面已经插好了"真正的内容"，哪些页面还是空的，`bitmap` 里存了**是否有效**的标识位（真 / 假）。当我们把一页（一个字节）插进去以后，就把对应位置的标识位设为 `true`；还没插入的地方则是 `false`。
---
### 收到新散页：如何"插入"到工作台上
#### 1. 确定散页对应的位置（index 与 offset）
- 当我们收到一个新的散页（字符串 `data`），还带着它在整本书中的起始页码 `index`，先要判断：
- 如果 `index` 在我们当前需要的下标（`unass_base`）**之后**，说明这是**更后面的书页**，需要放到工作台上相应的"插槽"处（要计算和 `unass_base` 的偏移量 `offset`）。
- 如果 `index` 比当前需要的下标要早，但它的末尾部分仍然延伸到我们需要的区域，那么就只取它还没被我们"组装走"的那部分插入工作台。
#### 2. 不能装就丢吗？——容量检查
- `capacity` 相当于工作台能放下的插槽总数，但是**并不是**我们实时可用的容量，还要考虑已经写到 `_output` 但仍旧占着"坑"的缓冲区。如果没有空间了，多出的那部分就等于"溢出"（实际代码里你可能会直接忽略或截断，不会放进来）。
#### 3. 真正插入
- 我们拿着散页 `data` 的内容，一字节一字节去对应到 `buffer[i + offset]` 中，同时把 `bitmap[i + offset]` 设为 `true` 表示这里已经有了有效数据。
- `unass_size` 就相当于我们"已经拿到但还没正式装订"的散页字节总数。
---
### check_contiguous()：能装订多少就装订多少
- 每当插入新的散页后，可能会触发"已经可以连续组合起来"的部分（就像书页1、2、3 已经都到位了，那就可以马上把它们**装订**进书中）。
- `check_contiguous()` 就是干这件事的：
1. 它会从 `buffer` 的最前面（对应我们要找的 `unass_base` 下标起），**如果数据是连着的**（`bitmap.front()` 为 `true`），就把这一部分字节拿出来连成 `tmp`。
2. 一直拿到遇到"空"的位置（`false`）或者到 `buffer` 尾部，就停止。
3. 然后把这串连续有效的内容（`tmp`）一次性写入 `_output`（相当于把这几页纸装订到书里去了）。
4. 同时，我们也要把 `unass_base` 和 `unass_size` 更新：因为这部分数据已经变成**正式装订**的页面了，不能再占着 `buffer` 里了。
- 在代码里，你能看到会 `pop_front()` 一些元素，并把 `unass_base` 往后挪、把 `unass_size` 减少，就是做了"已经装订好就剥离工作台"的工作。
---
### eof 与结束判断
- 当我们收到一个标识 `eof = true` 时，就说明这是我们期望的最后一批散页，但不代表我们**马上**结束。只有当**全部**需要的字节（`unass_size == 0`）都装订进书里了，才可以**正式收尾** (`_output.end_input()`)。
---
### 小结
1. **buffer + bitmap**：就像一个"临时存放散页"的工作台。
- `buffer[i]` 存某字节。
- `bitmap[i]` 标记那个字节是否有效。
2. **unass_base**：表示我已经装订好的最末端下标（下一页要找的书页页码）。
3. **push_substring(...)**：想办法把新到的散页放到工作台合适的位置，同时避免溢出。
4. **check_contiguous()**：检查是不是可以拿一些**连续的**书页，装订到书中 `_output`。
5. **unassembled_bytes()**：告诉你工作台上还有多少散页没被正式装订。
6. **eof**：当标记最后一批散页到了，但若工作台上还有欠缺的页面，就还不能结束。等到全部装订完才 end。
---
你可以把这段逻辑与书的装订过程联系起来，就会发现"收到乱序页 -> 暂存到工作台相应位置 -> 连续的部分一次装订 -> 直到最后"整个流程十分自然。这样，你对代码里 `bytestream`、`buffer`、`bitmap` 以及 `unass_base`、`check_contiguous()` 做的事情就有更直观的把握了。祝学习愉快！
在这个 StreamReassembler 中，buffer 和 bitmap 是用来处理乱序数据的两个关键数据结构：
1. buffer（缓冲区）
```cpp
std::deque<char> buffer; //!< The unassembled strings
```
- 存储还未能按序重组的数据内容
- 使用 deque 是因为需要在两端进行操作（前端取出数据，后端添加数据）
- 大小为 capacity，未使用的位置用 '\0' 填充
1. bitmap（位图）
```cpp
std::deque<bool> bitmap; //!< buffer bitmap
```
- 标记 buffer 中对应位置是否已经存储了有效数据
- true 表示该位置已有数据
- false 表示该位置尚未收到数据
- 与 buffer 一一对应
工作原理：
1. 当收到新数据片段时：
```cpp
buffer[i + offset] = data[i]; // 存储数据
bitmap[i + offset] = true; // 标记该位置已有数据
```
1. 检查连续数据时（check_contiguous）：
```cpp
while (bitmap.front()) { // 如果第一个位置有数据
tmp += buffer.front(); // 取出数据
buffer.pop_front(); // 移除已处理数据
bitmap.pop_front(); // 移除对应标记
// 在末尾补充空位
buffer.push_back('\0');
bitmap.push_back(false);
}
```
这样设计的好处：
1. 可以处理乱序到达的数据片段
2. 避免重复处理相同位置的数据
3. 能够快速判断哪些位置的数据已经到达
4. 方便检查是否有连续的数据可以输出
例如，假设收到以下片段：
```Java
index: 5, data: "def"
index: 0, data: "abc"
```
buffer和bitmap会帮助正确组装成"abcdef"。
## 新数据在 unass 点后
让我用 ASCII 图解释 `min(len, _capacity - _output.buffer_size() - offset)` 这个计算：
```Java
【整体视图】
capacity = 10 (总容量)
假设收到新数据："HELLO" (len=5)，从位置8开始 (offset=2)：
|<-------------- capacity=10 ------------>|
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | D | E | F | | | H | E | 新数据位置示意
+---+---+---+---+---+---+---+---+---+---+
|<--- buffer_size=6 --->|
|offset|
|-可用空间-|
计算可用空间：
_capacity = 10 (总容量)
_output.buffer_size() = 6 (已使用空间)
offset = 2 (新数据的偏移量)
可用空间 = 10 - 6 - 2 = 2 (只能放入 "HE"，"LLO" 放不下)
real_len = min(len=5, 可用空间=2) = 2
```
再举个例子：
```Java
情况1：缓冲区较空
capacity = 10
+---+---+---+---+---+---+---+---+---+---+
| A | B | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+
|<->| buffer_size=2
|->| offset=1
|<---- 可用空间=7 ---->|
len = 5 ("HELLO")
real_len = min(5, 7) = 5 // 全部数据都能放入
情况2：缓冲区较满
capacity = 10
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | D | E | F | G | H | | |
+---+---+---+---+---+---+---+---+---+---+
|<-------- buffer_size=8 -------->|
|->| offset=1
|->| 可用空间=1
len = 5 ("HELLO")
real_len = min(5, 1) = 1 // 只能放入一个字符
```
这个计算就像是在玩俄罗斯方块：
1. `capacity` 是游戏屏幕的总高度
2. `buffer_size` 是已经堆积的方块高度
3. `offset` 是新方块要放的位置到顶部的距离
4. `real_len` 是实际能放下的新方块数量
这样可以确保：
1. 不会超过总容量
2. 考虑了已使用空间
3. 考虑了新数据的位置
4. 取最小值保证安全
### 新数据与 unass 有部分重叠的情况
```Java
假设当前状态：
unass_base = 5 (从位置5开始未重组)
收到数据："WORLD" (len=5) 从位置3开始 (index=3)
【初始状态】
index=3
↓
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | W | O | R | L | D | | | 新数据
+---+---+---+---+---+---+---+---+---+---+
|<----- data="WORLD" ----->|
↑
unass_base=5
offset = unass_base - index = 5 - 3 = 2
意味着要跳过 "WO"，只处理 "RLD"
【计算实际可用长度】
len = 5 (WORLD的长度)
len - offset = 3 (要处理的实际长度，即"RLD")
real_len = min(3, capacity - buffer_size)
【处理后】
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | D | E | R | L | D | | |
+---+---+---+---+---+---+---+---+---+---+
buffer: 数据内容
bitmap:
1 1 1 1 1 1 1 1 0 0
↑ ↑ ↑
新存储的数据
```
再举个更复杂的例子：
```Java
【情况1：部分重叠，部分超出容量】
capacity = 10
unass_base = 5
收到："HELLOWORLD" (index=3)
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | H | E | L | L | O | W | O | 当前缓冲区
+---+---+---+---+---+---+---+---+---+---+
|<------ 新数据 "HELLOWORLD" ------>|
↑
unass_base=5
offset = 5 - 3 = 2 (跳过"HE")
len - offset = 8 (要处理"LLOWORLD")
real_len = min(8, 剩余容量)
【情况2：有重叠且有已存在数据】
+---+---+---+---+---+---+---+---+---+---+
| A | B | C | D | E | x | x | O | W | O | 当前缓冲区
+---+---+---+---+---+---+---+---+---+---+
bitmap: 1 1 1 1 1 0 0 1 1 1
↑ ↑ ↑
要填充的空位
```
代码逻辑解释：
```cpp
// 1. 计算偏移量
offset = unass_base - index; // 跳过重叠部分
// 2. 计算实际可处理长度
real_len = min(len - offset, _capacity - _output.buffer_size());
// 3. 如果无法完全存储，取消 EOF 标记
if (real_len < len - offset) {
_eof = false;
}
// 4. 存储数据，但跳过已有数据
for (size_t i = 0; i < real_len; i++) {
if (bitmap[i]) continue; // 跳过已有数据
buffer[i] = data[i + offset]; // 存储新数据
bitmap[i] = true; // 标记为已使用
unass_size++; // 更新未重组数据大小
}
```
这就像拼拼图：
1. 找到新片段应该放的位置
2. 跳过已经有的部分
3. 把新的部分放进去
4. 标记哪些位置已经填好了