added test_ring_queue.cpp, modified RingQueue capacity() definition

[mihir-mihir]

726

Changes

1. 880ee1c
   • Wrote unit tests for RingQueue class
   • Changed the definition of capacity() in ring_queue.h
   • Before making this change, if an element was added when size == buff_len_ - 1, this caused begin_ and end_ to be identical, which resulted in size() incorrectly returning 0
   • It looks like in the current RingQueue implementation, where the end pointer points to one slot ahead of the end data element, one empty slot needs to be reserved to distinguish between:
     • the empty state (when begin_ and end_ are identical)
     • the full state (when the end pointer has "caught up" to one slot behind the begin pointer in the ring)
   • This means that the actual capacity of the RingQueue would be buff_len_ - 1 instead of buff_len_
   • The tests passed after changing capacity() to return buff_len_ - 1 instead of buff_len_
2. d3ef99f
   • Redefined is_full() for RingQueue to calculate the full condition by working with the pointers directly
   • Modified the RingQueue constructor definition to clarify that the actual capacity of the queue is max_len - 1

[github-actions[bot]]

:robot: Upon creation, pull request description does not have a link to an issue. If there is a related issue, please add it to the description using any of the supported formats.

[gavv]

Thanks for PR and for catching the bug!

I suggest a bit different fix for the issue. We can make that extra chunk an implementation detail - if user requested N chunks, visible capacity would be exactly N chunks, although internally we can allocate N+1 chunks.

So instead of fixing capacity(), we can fix constructor I guess, and allocate +1 chunk. Also, if EmbeddedCapacity is non-zero, we likely need to add +1 to it as well.

We'll also need to fix core::MovStats and use win_len instead of win_len + 1 there when initializing RingQueue.

Also would be nice to add one more test with for the boundary case when queue size is 1 element.

Thanks!

@baranovmv FYI

[mihir-mihir]

Sounds good, made these changes in 880cdd7. Also, do we want EmbeddedCapacity to represent (a), the max queue capacity that we allow for using data embedding (in this case the embedded buffer would contain one more element than the value of EmbeddedCapacity), or (b), the max number of buffer elements allowed when using data embedding? I read your comment as meaning (a), but let me know if you meant (b) and I can make the change.

[gavv]

Sounds good, made these changes in da43de9. Also, do we want EmbeddedCapacity to represent (a), the max queue capacity that we allow for using data embedding (in this case the embedded buffer would contain one more element than the value of EmbeddedCapacity), or (b), the max number of buffer elements allowed when using data embedding? I read your comment as meaning (a), but let me know if you meant (b) and I can make the change.

Yep, I meant (a). I think EmbeddedCapacity, max_len, and capacity() all should be consistent and have same semantics, since they're visible to user of RingQueue.

[gavv]

I guess we should do something like:

AlignedStorage<(EmbeddedCapacity != 0 ? EmbeddedCapacity+1 : 0) * sizeof(T)> embedded_data_;

?

[mihir-mihir]

I guess we should do something like:

AlignedStorage<(EmbeddedCapacity != 0 ? EmbeddedCapacity+1 : 0) * sizeof(T)> embedded_data_;

?

Got it, made that change thanks. I think everything should be covered in 880cdd7 now.