`full()` returns `false` false-negatively when buffer wraps around

[lpirl]

When the buffer wraps around but slots at the beginning of the ring where popped already, full() false-negatively returns false. As a result push() etc. might return false false-negatively as well.

Reason seems to be that abs(tail - head) >= capacity does not work for the case where the buffer wraps around. This PR attempts to fix this by using used(): full = used(head, tail, capacity) == capacity.

Thanks for this nice package! :)

[elijahr]

@lpirl thank you for finding this and thank you for the contribution! This will need test coverage prior to merging. I can write the tests unless you would like to.

[lpirl]

Thanks for considering @elijahr . I'd be willing to contribute tests but maybe need your assistance.

My expectation would be that coverage doesn't change because no new functionality has been added. With this PR however, I see tests failing and I am not sure why. E.g.:

lockfreequeues/tests/t_ops.nim(266, 24): Check failed: full(0, 5, 4) == true
    full(0, 5, 4) was false

I understand the test but wondered how this got messed up by this PR. Since this PR makes full() build on used(), I checked the tests for used() and found, e.g.:

check(used(0, 6, 4) == 6)

Due to the doc "Determine how many slots are taken in storage", I would have expected used() to return 4 here. I see that head and tail are "virtually" moved between 0..2*capacity but storage is still of size capacity. So how can 6 out of 4 slots be taken? I probably don't understand the semantics of head, tail, and capacity, no?

[elijahr]

@lpirl I think the reason full() was implemented the way it was is for the multi-consumer and multi-producer implementations, where the head and tail values may show the queue as being "over full" due to caching. So the full() check needs to be >= capacity rather than == capacity.

Are you using the single-producer / single-consumer implementation or the multi implementations?

Do you have code to reproduce what you were seeing? That will help write a test and sort out what needs fixing. The existing tests may need some changes too.

[lpirl]

I see. I have used single-producer / single-consumer and haven't wrapped my head around the multi* use cases and implementations so far.

>= capacity is adapted.

Here is an example which triggers the defect I encountered:

import atomics
import src/lockfreequeues
var q = initSipsic[2, int]()
echo q.push 0
echo q.push 0
echo q.pop
echo q.pop
echo q.push 0
echo q.push 0
echo q.pop
assert not full(q.head.load, q.tail.load, q.capacity)