[boost] Re: Formal Review: Circular Buffer

From: Alberto Barbati (abarbati_at_[hidden])
Date: 2004-03-08 07:03:04

Pavel Vozenilek wrote:

> Discovered problems in code or in documentation,
> missing features, portability issues
> and finally opinion whether the library belongs
> to Boost is welcomed.

I believe this library is very useful and generally well-written. I 
found a few minor problems that I deem workable. My opinion is that the 
library should be accepted. The only things I would like to be discussed 
thouroughly are the "ctor/dtor vs. assignment" dispute (see specific 
thread) and the possibility to provide extension points that allows a 
(possibly future) implementation of a "notifying" container (ibid.).

About portability issues, these lines of code (file details.hpp, lines 
274-277) invoke undefined behaviour, according to 5.7/5:

     if (less(rhs, lhs) && lhs.m_it <= rhs.m_it)
         return lhs.m_it + m_buff->capacity() - rhs.m_it;
     if (less(lhs, rhs) && lhs.m_it >= rhs.m_it)
         return lhs.m_it - m_buff->capacity() - rhs.m_it;

that's because the expressions (lhs.m_it + m_buff->capacity()) and 
(lhs.m_it - m_buff->capacity()) might produce a pointer outside the 
allocated range. I suggest to replace those lines with:

     if (less(rhs, lhs) && lhs.m_it <= rhs.m_it)
         return lhs.m_it - rhs.m_it + m_buff->capacity();
     if (less(lhs, rhs) && lhs.m_it >= rhs.m_it)
         return lhs.m_it - rhs.m_it - m_buff->capacity();

or, even better, to avoid complaints from nasty compilers about mixed 
signed/unsigned usage:

     if (less(rhs, lhs) && lhs.m_it <= rhs.m_it)
         return (lhs.m_it - rhs.m_it) +
             static_cast<difference_type>(m_buff->capacity());
     if (less(lhs, rhs) && lhs.m_it >= rhs.m_it)
         return (lhs.m_it - rhs.m_it) -
             static_cast<difference_type>(m_buff->capacity());

To be extra paranoid, we should ensure that the static_cast doesn't 
overflow. This could be done by changing the defintion of max_size() in 
base.hpp from:

     size_type max_size() const { return m_alloc.max_size(); }

to

     size_type max_size() const {
         return std::min<size_type>(m_alloc.max_size(),
             (std::numeric_limits<difference_type>::max)()); }

I've seen this issue overlooked even in commercial standard library 
implementations. As c.end() - c.begin() == c.size() and c.end() - 
c.begin() must be representable as a positive quantity of type 
difference_type, this imply that c.size() <= c.max_size() <= 
numeric_limits<difference_type>::max().

On a side note, I think it should be good if the implementation of the 
iterator classes used the new Boost Iterators Library. I have uploaded 
in the Boost file area an implementation using boost::iterator_facade 
(filename is circular_buffer_new_iterators.zip). The implementation 
already include the fix above and also has a slightly more optimized 
version of the less() method, with fewer tests and without switches.
Problem is that there is something wrong with the implementation of 
operator[] in iterator_facade and the regression test does not compile 
anymore :-( However, if I hack iterator_facade::operator[] to avoid the 
use of the operator_brackets_proxy class, all regression tests pass. 
Maybe it would be good to discuss this problem of the iterator_facade in 
a different thread.

Alberto Barbati