rust-managed
rust-managed copied to clipboard
Add slotvec, slotbkvec and slotdeque three containers
A slot vec SlotVec is a linear container similar to a vector but the indices are invalidated when the element is removed, and can not incidentally refer to a valid element again even if new elements are pushed. The slot vec implementation relies solely on the index of its elements to index data. In particular, the elements here are Option<T>, which means that Some/None can indicate whether the element is removed or not, respectively, without the need for dedicated slots to store this status information.
A slot bucket vec SlotBkVec is a double-layer liner container similar to a Vec<SlotVec> but the indices are invalidated when the element is removed. The outer layer represents the bucket of slotvec, and the inner layer is the vector that stores the actual element data. The index returned by the public API of a slot bucket vec is not directly the index generated by the internal SlotVec, but the generated index is masked, which causes the index to carry bucket/slot information. When getting an element, you don't need to specify the slot to get its element, but you must specify the bucket parameter when inserting an element. This is by design.
A slot deque SlotDeque is a liner container similar to a vector-deque (VecDeque) but the indices are invalidated when the element is removed. However, since the index of a std/alloc::VecDeque may become invalid due to certain operations (that is, the index assigned in the past will no longer point to the data inserted in the past in the future), we mainly solve this problem here so that we can use the assigned but not removed index to consistently access the elements at the time of insertion without worrying about the impact of push operations. It is simulated by SliceBkVec, which is essentially two SlotVecs, one for the front slice and the other for the back slice.
Thanks to the encapsulation of SlotVec, we can simply replace the current SocketSet in smoltcp and hide some details in SocketSet in SlotVec. I also plan to do something with SocketSet, because SocketSet is currently too simple to meet some of my specific needs. I hope that smoltcp can use user-defined Set to complete some complex scenarios. For example, we simply abstract SocketSet into a trait. This trait contains the necessary operations when smoltcp stack processes socket data. The rest of the operations are extended by the user, such as how to add a socket, because adding a socket and traversing the socket have an extremely subtle relationship, which determines the order of data processing or more to some extent. Of course, these are things to be discussed after this PR.
UPD: A PoC for replacing SocketSet: https://github.com/cavivie/smoltcp/commit/952aa020639b7628633ceffee0ec17cc647e2262