Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Is there a bug in circular_q::size()? #2820

Closed
SaltedReed opened this issue Jul 15, 2023 · 2 comments
Closed

Is there a bug in circular_q::size()? #2820

SaltedReed opened this issue Jul 15, 2023 · 2 comments

Comments

@SaltedReed
Copy link

Now circular_q::size() is implemented as:

    // Return number of elements actually stored
    size_t size() const
    {
        if (tail_ >= head_)
        {
            return tail_ - head_;
        }
        else
        {
            return max_items_ - (head_ - tail_); // is it wrong?
        }
    }

At where I commented, is it supposed to be "return max_items_ - 1 - (head_ - tail_);"?

An example is, when users call the following constructor to create a circular queue with max_items=3:

explicit circular_q(size_t max_items)
        : max_items_(max_items + 1) // one item is reserved as marker for full q
        , v_(max_items_)
    {}

max_items_=4. So If the circular queue looks like this:
index:             0   1   2
has element: no no yes
                    tail_     head_
then size() is supposed to return 1. But with current implementation, the return value is 4-(2-0)=2. I think the marker for full q should be minused here, which isn't yet.

@tt4g
Copy link
Contributor

tt4g commented Jul 16, 2023

It has been changed in this commit (bad7284), but maybe missed the max_items_ = max_items + 1 in the constructor.
There is no test, so I think it is most likely a bug.

@gabime
Copy link
Owner

gabime commented Jul 16, 2023

Good catch @SaltedReed . PR to fix is welcome.
@tt4g You are right, we need to add some tests for it.

@gabime gabime closed this as completed in d8d23a6 Jul 20, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants