Re:Show HN: Revring, a circular buffer with zero memory waste
by rhaps0dy on Thursday June 18, 2015 @04:45PM
(#9741512)
You still have a buffer or size X that may store X-Y items. I fail to see the "zero memory waste" (not that it's a good tradeoff).
[ Parent
| on HN ]
Re:Show HN: Revring, a circular buffer with zero memory waste
by mungoman2 on Thursday June 18, 2015 @04:52PM
(#9741547)
No, the author can use all entries in the buffer. The space cost is hidden in that one of the pointers need to hold X+1 values, ie for 256 entries it is not enough with 8-bit indices.
An unfortunate effect of this implementation is that both indices are modified by the consumer. It's not safe to write/read dats from different contexts, something that would be very useful in a driver.
Re:Show HN: Revring, a circular buffer with zero memory waste
by codehero on Thursday June 18, 2015 @05:30PM
(#9741718)
Yeah your intuition is correct here. On an MSP430 (which is were I use it) the producer is in interrupt context but as a savvy redditor pointed out, I will need to enable/disable interrupts in the consumer function as well.
Re:Show HN: Revring, a circular buffer with zero memory waste
by rhaps0dy on Thursday June 18, 2015 @04:56PM
(#9741563)
Ah, thanks for explaining.
Now it makes sense.
Re:Show HN: Revring, a circular buffer with zero memory waste
by akkartik on Thursday June 18, 2015 @04:57PM
(#9741571)
If I understand correctly he's storing X items in a buffer of size X, but using an invalid value in the head pointer to indicate that the buffer is full.
It's easier to understand without the decrementing. Initialize head and tail to 0, keep incrementing and cycling through the end as usual. When removing an element check if head and tail are equal before removing. When adding an element check if head and tail are equal after adding, and set the head to a sentinel value, say MAX_INT. Now you can check for the sentinel before attempting to add an element.
Neat trick!