Size and other calculation bugs in RingQueue

[vgough]

Size returns an invalid size (larger than the buffer) in some cases.

Due to #27 , I created a new Ring queue implementation: https://github.com/arg0net/collections

As part of it, I added a Fuzzing test to look for edge cases that I might not have considered. I tried running the fuzzer on Logdy's RingQueue out of curiosity since I was seeing strange behavior. What it found is that the RingQueue Size function is incorrect and can report a size greater than the size of the ring. Since Size is called from other functions, those functions are also incorrect.

Reproduction case:

• create RingQueue of size N
• queue N elements into it. The ring is now full.
• Pop one element. now start is 1, and end is 0.
• Size returns N+1, when it should return N-1.

Here's my hacked fix

func (r *RingQueue[T]) Size() int {
    res := r.end - r.start
    if res < 0 {
        res = len(r.data) + res
    } else if res == 0 && r.isFull {
        return len(r.data)
    }

    return res
}

After fixing that, the fuzzer next found a bug in PeekIdx. There's an off-by-one error which causes it to return a value for an empty ring. Since the ring values are not cleared, it is returning a previously used value from the queue. I believe the problem is that it isn't taking into account the isFull flag if start == end. I patched in a fix for that as well as the Size issue and then the fuzzer was still finding problems, so I've given up. I suggest implementing fuzzing to help track down the issues, or else consider importing the implementation I created. I'm happy to add additional methods if you need Scan or other methods.

FWIW, I also ran the benchmark on the arg0net and lodgy versions and found the arg0net is also 8x faster for repeating push/pops on a desktop server. I'm guessing that this is because there's no need to do modular arithmetic or the extra step of memory indexing (one is built into the array accessor) to determine an index.

Hope that helps!

[PeterOsinski]

thanks, I'll look into that!