CS144 lab1

[TOC]

先放一张经典的图… Do you see the lab1 work ?

The work

我们需要去实现一个流重载器，因为在进行数据的接收时都是无序的，需要进行重新的组合得到一个有序的数据。

The requirement

The keypoint is the capacity. 这也是TCP实现限流的一个重要的手段

capacity 意味着从被读入到没有被组合的位置的长度不能大于capcaity，所以我们需要去定义额外的数据结果去保存我们的未被组装的数据。

The implement

实现思想是使用map去记录未被编码进入的数据，保存 index和string 和数据

每次加入一个新的数据时，先使用二分查找去在未被编码的数据中查找合适的数据集合，对这些有重合/可连接的数据进行操作

  1. 连接，直接前面相连或者后面相连
  2. 重合，将重合的部分去掉，合并为一个未被编码的数据

随后尝试将第一个数据加入到ouput中

  1. 小于等于_next，将合理数据加入进去
  2. 大于_next, 直接返回

然后判断结束情况

  1. 有eof标识，设置结束index
  2. 如果结束index已经设置，判断是否已经完全加入，直接结束ouput

1. 添加新的成员变量

1
2
3
4
5
6
7
8
9
10
class StreamReassembler {
  private:
    // 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::map<size_t, std::string>_unassembled_bytes;
    size_t unassembled_bytes_num;
    size_t _next_index;
    size_t _eof_index;

2. 实现函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {
    size_t start = index;
    size_t end = index + data.length() - 1;
    string new_data = data;
    auto start_iter = _unassembled_bytes.lower_bound(start);
    if (data.empty())
        goto assemble_from;

    if (end < _next_index) return;

    if (start_iter != _unassembled_bytes.begin()) start_iter--;
    if (!_unassembled_bytes.empty()&& start_iter->first <= start && start_iter->first + start_iter->second.length() -1 >= end)
        goto assemble_from;

    for (auto i = start_iter; i != _unassembled_bytes.end();) {
        size_t now_start = i->first;
        size_t now_end = i->first + i->second.length() - 1;
        if (now_start < start && now_end >= start - 1) {
            size_t len = start - now_start;
            new_data = i->second.substr(0, len) + new_data;
            start = now_start;
            unassembled_bytes_num -= i->second.length();
            i = _unassembled_bytes.erase(i);

        } else if (now_start >= start&& now_end <= end) {         // If it is fully coverd
            unassembled_bytes_num -= i->second.length();
            i = _unassembled_bytes.erase(i);
//            unassembled_bytes_num -= i->second.length();

        }
        else if (now_start > end + 1)
            break ;
        else if (now_start <= end + 1 && now_end > end) {
            size_t len = now_end - end;
            try {
                new_data += i->second.substr(i->second.length() - len, len);
            }
            catch (std::exception &e) {
                printf("errrr %s",e.what());
            }
            unassembled_bytes_num -= i->second.length();

            i = _unassembled_bytes.erase(i);
        } else if (now_end < start - 1) i++;

        else {
            break ;
        }

    }
    _unassembled_bytes.insert(make_pair(start, new_data));
    unassembled_bytes_num += new_data.length();
assemble_from:

    if (!_unassembled_bytes.empty()) {

        auto i = _unassembled_bytes.begin();
        size_t remaining_capacity = _output.remaining_capacity();
//        if (i->first + i->second.length() <= _next_index)
//            break;
        if (i->first <= _next_index) {
            size_t now_start = i->first;
            string now_data = i->second;
            size_t all_has =  _next_index - now_start;
            try {
                now_data = now_data.substr(all_has, now_data.length() - all_has);
            } catch (std::exception &e) {
                printf("errrr %s",e.what());
            }
            size_t can_input = min(now_data.length(), remaining_capacity);
            _next_index += can_input;
            string  read_data = now_data.substr(0, can_input);
            string un_data;
                try {
                un_data = now_data.substr(can_input, now_data.length() - can_input);
            }
            catch (std::exception &e) {
                printf("errrr %s",e.what());
            }
            _output.write(read_data);
            unassembled_bytes_num -= read_data.length();
            _unassembled_bytes.erase(i);

            if (!un_data.empty())
                _unassembled_bytes.insert(make_pair(_next_index, un_data));
        }
    }

    if (eof) {
        _eof_index = index + data.size();
    }
    if (_eof_index <= _next_index)
        _output.end_input();
}

size_t StreamReassembler::unassembled_bytes() const { return unassembled_bytes_num; }

bool StreamReassembler::empty() const { return _unassembled_bytes.empty(); }

The test

最终测试结果基本在0.33s左右，自信)