I made a #![no_std] circular buffer using const generics

As a learning exercise, and with the recent stabilization of const generics, I implemented a circular buffer using const generics to have the whole buffer in the structure directly instead of using Box or raw pointers.

There is a lot of unsafe, mainly because the entire buffer contains MaybeUninitalized values. The nightly compiler is required because many APIs of MaybeUninit are still unstable.

It is my first time dealing with unsafe Rust so there are likely a few things I missed, I'd be glad if someone could take a look.

The repository is here on gitlab.

The end result looks like this:

let mut buf = CircularBuffer::<usize, 10>::new();
for i in 0..10 {
    assert!(buf.push_back(i).is_none());
}

for i in 0..10 {
    assert_eq!(i, buf[i as isize]);
}

for i in 0..10 {
    assert_eq!(Some(9 - i), buf.pop_back());
}

assert!(buf.pop_back().is_none());

Thanks!

1 Like

Haven’t looked at it for very long but here’s two things.

The eremc seems like you could try to use isize::rem_euclid. I think that you can easily just drop support for the case of N > isize::MAX (presumably with an assert just to be sure). This isn’t much of a loss since (unless maybe for zero-sized T, I’m not 100% sure there) the compiler will disallow this size of allocation anyway. In this case, converting N into isize and passing the result to isize::rem_euclid should work fine.

You should also take into consideration that (on 32bit platforms), your start and end indices can overflow which will probably (AFAICT) lead to memory unsafety in your current implementation as the wrong element could be accessed / returned.

2 Likes

My only suggestion would be to make the public API use usize rather than isize. That seems like an implementation detail that would be best hidden from the users. And using usize for lengths and indices is more common. This lowers the friction, for instance, if a user wants to use with_capacity on a std collection to drain the buffer into.

4 Likes

Thanks,

I left isize in the public API because it allows negative indexes. Currently, if after initializing the buffer you use push_front, the element you added will be at index -1 it is done that way so that a given element stays at the same index its whole lifetime.

I think that I will add a wrapper that provides a similar API but take usize as an index. That way both are available.

The eremc seems like you could try to use isize::rem_euclid

Yes and no, the issue is that I also want to convert the result to usize to be able to use it to index in the buffer. For the record, ermec stands for "euclid reminder convert".

I think that you can easily just drop support for the case of N > isize::MAX (presumably with an assert just to be sure).

Yes it's done in the CircularBuffer::new function. The assert also verifies that N is not zero.

You should also take into consideration that (on 32bit platforms), your start and end indices can overflow which will probably (AFAICT) lead to memory unsafety in your current implementation as the wrong element could be accessed / returned.

Good catch. I'm not sure how to deal with it. Maybe if I restrict N to be smaller than a quarter of isize::MAX there might be some way of detecting overflow and still making it work correctly. The fact that N is not necessarily a multiple of the point of overflow might make it a bit harder, but there are likely some implementations that already deal with that kind of issues.

I was curious so I tried.

Turns out the behaviour is quite weird. Basically, with N = isize::MAX + 1 and a zero sized type it doesn't compile if the debugging symbols are enabled due to this compiler bug, but it compiles smoothly (and panics due to the assert) in release mode.

I thought of eremc(left, right) becoming left.rem_euclid(right as isize) as usize which should work perfectly fine as long as right <= isize::MAX, I think.

Edit: Perhaps it doesn’t work for left == isize::MIN.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.