Structure and Design

这里主要就是需要维护一个区间，来表示每一次插入的时候插入的data是什么以及有效的 first_index 和 last_index 所以首先有一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class section
{
private:
  uint64_t first_index;
  uint64_t last_index;

public:
  string data;

public:
  section( uint64_t first_index_, uint64_t last_index_, string& data_ )
    : first_index( first_index_ ), last_index( last_index_ ), data( std::move( data_ ) ) {};
  uint64_t get_first_index() const { return first_index; };
  uint64_t get_last_index() const { return last_index; };
  uint64_t get_size() const { return last_index - first_index + 1; };
  void set_first_index( uint64_t first_index_ ) { this->first_index = first_index_; };
  void set_last_index( uint64_t last_index_ ) { this->last_index = last_index_; };
  bool operator<( const section& sec ) const { return this->first_index < sec.first_index; };
  bool operator>( const section& sec ) const { return this->first_index > sec.first_index; };
};

有了这个类之后，使用一个 std::set<section> sections 来按照第一个字母排序，维护一个有序的集合，这样每次新加入一段的时候，其前后的 index 只有

  1. 小于 section.first_index
  2. 大于等于 section.first_index 且小于等于 section.last_index
  3. 大于 section.last_index
    那么根据首位 index 的这三种情况组合起来，一共有 9 种，但是其中某些不可能出现，于是处理的框架就是：
    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
    void Reassembler::dummy_insert( uint64_t first_index, std::string& data, bool is_last_substring )
    {
      uint64_t last_index = first_index + data.size() - 1;
      bool is_inserted = false;
      for ( auto it = sections.begin(); it != sections.end(); it++ ) {
        uint64_t first = it->get_first_index();
        uint64_t last = it->get_last_index();
        int relative_position_first = get_relative_position( first, last, first_index );
        int relative_position_last = get_relative_position( first, last, last_index );
        std::pair<int, int> cases( relative_position_first, relative_position_last );
        if ( cases == make_pair( 1, 1 ) ) {
          section new_section( first_index, last_index, data );
          sections.insert( new_section );
          bytes_pending_ += new_section.get_size();
          is_inserted = true;
          break;
        } else if ( cases == make_pair( 1, 2 ) ) {
          string push_data = data.substr( 0, first - first_index );
          section new_section( first_index, first - 1, push_data );
          sections.insert( new_section );
          bytes_pending_ += new_section.get_size();
          is_inserted = true;
          break;
        } else if ( cases == make_pair( 1, 3 ) ) {
          string push_data = data.substr( 0, first - first_index );
          string remaining_data = data.substr( last - first_index + 1 );
          section new_section( first_index, first - 1, push_data );
          bytes_pending_ += new_section.get_size();
          sections.insert( new_section );
          dummy_insert( last + 1, remaining_data, is_last_substring );
          is_inserted = true;
          break;
        } else if ( cases == make_pair( 2, 2 ) ) {
          return;
        } else if ( cases == make_pair( 2, 3 ) ) {
          string remaining_data = data.substr( last - first_index + 1 );
          dummy_insert( last + 1, remaining_data, is_last_substring );
          is_inserted = true;
          break;
        } else if ( cases == make_pair( 3, 3 ) ) {
          continue;
        } else {
          __throw_logic_error( "should not reach here" );
        }
      }
      if ( !is_inserted ) {
        section new_section( first_index, last_index, data );
        sections.insert( new_section );
        bytes_pending_ += new_section.get_size();
      }
    }
    其中所有以 3 结尾的情况，都需要考虑多出来的一段与后面的情况，为了省事这里直接采用递归的方式，递归插入剩下多的情况

    Hint:这里应该并非最佳实践，首先这里的set是可以用lower_bound直接查询第一个插入的位置的，但是因为我不会用遂作罢，第二是，这里的带1的情况我没有直接合并进去，因为set是不能修改的，所以应该用map更好

最后每次插入结束都尝试进行一次push，即

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
void Reassembler::try_push()
{
  for ( auto it = sections.begin(); it != sections.end(); ) {
    if ( it->get_first_index() <= first_pushing_index ) {
      if ( it->get_last_index() < first_pushing_index ) {
      } else {
        string push_data = it->data.substr( first_pushing_index - it->get_first_index(),
                                            it->get_last_index() - first_pushing_index + 1 );
        bytes_pending_ -= push_data.size();
        if ( output_.writer().available_capacity() >= push_data.size() ) {
          first_pushing_index = it->get_last_index() + 1;
        } else {
          first_pushing_index += output_.writer().available_capacity();
        }
        output_.writer().push( push_data );
      }
      it = sections.erase( it );
    } else {
      break;
    }
  }
  if ( final_index != UINT64_MAX - 1 ) {
    if ( first_pushing_index == final_index + 1 || final_index == UINT64_MAX ) {
      output_.writer().close();
    }
  }
}

Implementation Challenges

第一个问题是，这里不允许用指针自己造链表，所以第一次我写了三天的链表过不了编译，遂作罢，摆烂用set了

第二是：

这里一开始忘了迭代器删除之后再++是ub，我以为会自动更新，忘了手动更新过不了测速

Experimental results and performance.


最后测速在 10.07Gbit/s 左右，还有优化空间