Since we'll soon accept overlapping stream data (#408), we might need to think again about the best data structure to use here. However, I think #408 superseeds this issue. Closing.

Reopening.

It would be nice if the same data structure could also be used in the sentPacketHandler for keeping track of sent packets.
A requirement for this use case is that the tree supports modification while iterating (we might need to remove M out of N sent packets, and we don't want want to incur a M*log(N) cost for that.

Unfortunately, the only (?) popular generic tree data structure around is Google's Btree, which 1. has a horrible iterator interface and 2. doesn't support modifications while iterating.

It would be nice to find a 3rd party package that's widely used (let's say at least 100 imports, as reported by godoc), and actively maintained. While there are a few repos around, none of them even makes it to 10 imports, so I don't feel very comfortable relying on their code.

Can we use a concurrent skip[list,set,map] for this?

@zllovesuki Do you have a specific one in mind?
Would we create our own implementation, or is there a 3rd party library we can build on?

@marten-seemann was thinking about https://github.com/zhangyunhao116/skip[set,map] implementation, purely because I did something similar to frameSorter in Java with ConcurrentSkipListSet.

As for import counts, let's just say that private repository imports don't show up

There exists a lock-free RBT paper but I don't think there's an implementation yet: http://www.cs.umanitoba.ca/%7Ehacamero/Research/RBTreesKim.pdf

This probably doesn't directly apply to the stream frame sorter, but here's a proposal for an efficient way to track sent packets and handle ACKs: #3836