It might have helped to explain the principle of a ringbuffer in the beginning. The idea would be if the index we are going to read is the current write index the buffer is empty. If the index we are going to write to next is the read index then we are full. This implicitly makes the capacity len()-1. In the context of a vec [0, 1, 2, 3] if the read index is 0 and the write index is 0 we are empty. However if the read index is 3 and the write index is currently 2 we are full. We haven't written to 2 but to respect the invariants we cannot write to 2 otherwise it would be difficult to check whether we are full. Think of the case where read index is 0 and write index is 3. We cannot possibly check whether write is less than read because it isn't. However write +1 == read which means we are full. The C implementation is correct.
10:34 Something else you could have done is use `let vec = Vec::::with_capacity(capacity)` which would allow you to remove the Option wrapper and the restriction on T to be Clone. The length is zero however so indexing now would panic, but you can use `vec.set_len(capacity)` to fix that. This will allow you to index possible garbage data, but as long as you implement the ring buffer correctly it is safe to use. One last thing is that after you have allocated the underlying array you don't really need the Vec anymore since the array should now be fixed length, so lastly you can call `vec.into_boxed_slice()` to convert to a Box and use that as storage instead of Vec. 🙂
Another thing, the C implementation is not wrong. I would recommend renaming `read_index` and `write_index` to `start` and `end` in your code. This way it is easier to see that in new() you initialise start to be after end (start > end), which seems to be your main problem. Hopefully this also makes it more clear why we only update the write_idx (end) on push, since the read_idx (start) doesn't move.
Determining full vs empty in ring buffer is a common issue. Whenever head == tail, the ring buffer can be either full or empty. You need extra logic to tell them apart. A simple approach is to use a bool flag to mean full (i.e. you see the flag to true whenever number of items == capacity) and make empty be head == tail && !full
@@vei_bean This assumes that you have initialized the memory in the first place and that you actually set the value back to None after you have read from it. Neither is true. The simplist solution is to check whether the next index that would be written to is the read index. In the case where you are resetting the value after each read you are leaving performance on the table since you are having to initialize the object at the index on every single operation. When you are using a ringbuffer you are generally worried about performance. You could always just be using a linked list which would be simpler to implement(well at least in most languages...)
@@Jeanpierrec19 when creating the ring buffer we fill it with None variant of Option, the memory is initialized it's just empty Options (None). checking the next index isn't necessarily the simplest solution, checking for Some is just .is_some(), seems pretty simple to me. I'm not too sure whether or not it is more or less intensive as some math and and comparison. my logic on checking is_some is that once we get Some at the write index it would have to mean we have looped back to the starting write index if you dont reset the value and if you do reset the value would mean you write faster than you read, both of which i interpret as a full buffer. if you consider already read data empty when not reseting the value, well that would require more overhead. really just a tupple of (Option, bool) if you want that. again i dont really know how efficient option is but from what i understand about rust, they put alot of effort to make sure it is as efficient as possible in the standard lib. I made my own ring buffer implementation if you want to look at that: codeberg.org/Vulpesx/ring_buffer
To check if full just check if write index is some, could do this in java aswell since it has options too. Options solve the issue of checking capacity
Rust itself has a ring buffer in std::collections::vec_deque, it's not perfect 1 to 1 with your implementation as it is not fixed size but I imagine it might be worthwhile to look at the source in that for a more idiomatic ring buffer if you cant make a vec_deque work for yourself or impl something on top of a vec_deque
Note: Pull fn needs to use readidx not writeidx. For C implementation, the wiki says to add a counter. Also set readidx to 0 when using it in pull fn. In the Java implementation, the write and read sequences continue to grow. Which is why you can use them as way to check if empty or full. So this would require the rust code to track the sequences and evaluate the index on pull/push. I prefer the first option.
@@timClicks love you work. I couldn’t fall asleep so this was good exercise before bed. I think Someone in comments had the idea to mark the read items as None. Is_full fn could then just check if next item is Some. I’m not sure how to check if_empty in option. Edit: You can add a back_idx fn and check if idxs are same and back_idx(readidx) is none. Maybe I haven't tested that out yet
Hai Tim. In the tutorial you had mentioned the push(write) operation is mutable and pull(read) is by reference or immutable. Is that the right way of doing?. We cant hold a mutable and immutable reference to a same thing same time. The underlying Data structure need to move the elements to new memory location in heap every time. This may cause a mismatch of element referenced in a memory location. Please correct me if I am wrong.
BTW I loved watching this as the ring buffer is a favorite data structure of mine and I've been keen to try implementing it in rust in various ways. Thanks for making this!
