CS144_lab01

Putting substrings in sequence

问题

输入的数据格式为：一个字符串，该字符串在整个数据的起始位置index，该字符串是不是最后一个的标识。

目标：把这些无序的字符整理为有序数据。

思维

数据结构

std::deque<char> _buffer  // 缓存区
std::deque<bool> bitmap;    // 与缓存区对应，判断bit是否可以发送。
size_t _index  // 有序字符的下一个存储在缓存中的下标
bool _eof;    // 数据流结束标识
size_t unass_size;    // 未重组的个数

1、index大于_index，导致[_index, index)区间出现空白。这就要等待该空白区域填满了之后，才能发送该片段。

2、index小于_index，就会出现重复的数据。根据index和_index求出偏移，就可以解决。

注意：只要数据是有序的，就把它交付出去。

3、最后一个数据段可能提前到了

实现

### push_substring
void StreamReassembler::push_substring(const string &data, const size_t index, const bool eof) {

    if(eof) {
        _eof = eof;
    }

    size_t len = data.length();
    if(len == 0 && _eof && unass_size == 0) {
        _output.end_input();
        return;
    }
    // 忽略无效下标
    if(index >= _index + _capacity) return;

    if(index >= _index) {
        size_t offset = index - _index;     // 计算偏移
        size_t real_len = min(len, _capacity - _output.buffer_size() - offset);
        if(real_len < len) {    // 数据还没有传输完
            _eof = false;
        }
        for(size_t i = 0; i < real_len; ++i) {
            // 跳过重复数据([_index, A)一直为空白区，但是后面也有多种情况
            if(bitmap[i + offset]) continue;  
            // _buffer和bitmap 一一对应  
            _buffer[i + offset] = data[i];
            bitmap[i + offset] = true;
            unass_size++;   // 统计未重组的字符
        }
    } else if(index + len > _index) {   // 计算与已经传输的字符重复了，去重。
        size_t offset = _index - index;
        // 不能超过缓存区
        size_t real_len = min(len - offset, _capacity - _output.buffer_size());
        if(real_len < len - offset) {
            _eof = false;
        }
        for(size_t i = 0; i < real_len; ++i) {
            if(bitmap[i]) continue;
            _buffer[i] = data[i + offset];  // i + offset未重叠的部分
            bitmap[i] = true;
            unass_size++;
        }
    }
    check_contiguous();
    if(_eof && unass_size == 0) {
        _output.end_input();
    }

}

check_contiguous

void StreamReassembler::check_contiguous() {
    string msg = "";
    while(bitmap.front()) {
        msg += _buffer.front();
        _buffer.pop_front();
        bitmap.pop_front();
        // 保证缓存区大小固定
        _buffer.push_back('\0');
        bitmap.push_back(false);
    }

    if(msg.length() > 0) {
        _output.write(msg);
        unass_size -= msg.length();
        _index += msg.length();
    }
}