[boost] Re: circular_buffer ver. 3.3 [long]

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2003-08-24 15:32:23

Hello Jano,

From: "Jan Gaspar" <jga_at_[hidden]>
Subject: circular_buffer ver. 3.3
>
> Another beast was born. You can find it at
> http://groups.yahoo.com/group/boost/files/circular_buffer.zip

This circular_buffer works on MSVC 6.5 and Intel C++ 7 and also compiles on
BC++B 6.4.

Few notes to latest source:

1. circular_buffer_adaptor.html: the link in

   "The circular_buffer_space_optimized is defined in
    the file boost/circular_buffer.hpp."

   points to wrong source file.

2. circular_buffer_adaptor.hpp should include
   circular_buffer_base.hpp, someone might
   use only this header.

3. It would be helpful (for MSVC) to put this into
   headers circular_buffer_fwd.hpp and
   circular_buffer.hpp:

#if _MSC_VER >= 1020
#pragma once
#endif

4. Borland C++ Builder 6.4 requires to specify template parameters
   for cb_iterator:

a. in operator-():
   cb_iterator operator - (difference_type n) const { return
cb_iterator<Buff, Traits>(*this) -= n; }

b. in operator+():
    cb_iterator operator + (difference_type n) const { return
cb_iterator<Buff, Traits>(*this) += n; }

5. Borland C++ Builder 6.4 doesn't allow to bring
   operator[] via using.

This is workaround in circular_buffer_adaptor.hpp:

#include <boost/detail/workaround.hpp>

...

#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564) )
    reference operator [] (difference_type n) { circular_buffer<T,
Alloc>::operator[](n); }
    const reference operator [] (difference_type n) const {
circular_buffer<T, Alloc>::operator[](n); }
#else
    using circular_buffer<T, Alloc>::operator[];
#endif

6. circular_buffer_adapter.hpp: member m_final_capacity
   may be named m_max_capacity.

7. Maybe there should be low treshold to capacity as well as high.
   Actual capacity may vary between these. This would avoid
   unnecessary reallocations when there are only few items.

min_capacity <= size <= current_capacity <= max_capacity

min_capacity is allowed to be 0.

Grow algorithm can be:
a. if new_size >= current_capacity then current_capacity =
std::min(max_capacity, current_size * 2)
b. avoid reallocating for only few items
  if new_size + new_size / 2 >= max_capacity then current_capacity =
max_capacity

The two check_low_capacity() functions can be merged into one
void check_low_capacity(size_type n = 1);

Also the "<< 1" and ">> 1" can be in this case safely replaced by * 2 and /
2
(it is unsigned).

Shrink algorithm can be:
a. allow hysteresis when shrinking
   if new_size < current_capacity / 3 then shrink_to(std::max(min_capacity,
current_capacity / 2))
b. if new_size < min_capacity then shrink_to(min_capacity)
c. if new_size == 0 && min_capacity == 0 then shrink_to(0)

The constructors and set_capacity() would need one more paramerer or
overload,
capacity() could return pair<>. clear() would need change.

8. circular_buffer_space_optimized<> constructor with circular_buffer<>
   parameter can be provided, similarly operators <, >, ==, !=,
   and possibly swap() (swaping only items).

   I don't know how much needed in practice this would be though.

9. circular_buffer_base.hpp and circular_buffer_adaptor.hpp:
   instead of check

#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)

is enough to use

#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)

(it is defined for MSVC).

10. cb_iterator::operator->() should also have asserts inside.

11. cb_iterator::operator+=() and operator-=(): the asserts should
    be moved at the beginning of these functions.

12. cb_iterator::operator--() should have assert:
    BOOST_ASSERT(m_it != m_buff.m_first); // is not begin()

13. cb_iterator::operator+=() should have assert:
    BOOST_ASSERT(distance(m_it - m_buff.begin()) + n <= size());

    Similarly in operator-=() and operator[].

   cb_iterator functions may also check if their m_it pointer is
   in valid range <begin(), end()).

14. Btw, isn't cb_iterator::operator[]() added by mistake?
    I have never seen such an operation for iterator.

15. circular_buffer::front(), back(), pop_front() and
    pop_back() can have asserts for empty buffer.

    insert()/rinsert()/erase() can check position iterator
    validity too.

16. RAII vs try blocks:

> > 1. IMO the macro based exception handling isn't needed, it is better
> >     to use RAII, like:
> > ...
> >
> > can be replaced by:
> >
> > void set_capacity(size_type new_capacity) {
> >   if (new_capacity == capacity()) return;
> >   pointer buff = allocate(new_capacity);
> >
> >   struct deleter_t {
> >     pointer data;
> >    size_type capacity;
> >     deleter_t(pointer p, size_type s) : data(p), capacity(s) {}
> >     ~deleter_t() { deallocate(data, capacity); }
> >   };
> >   deleter_t guard(buff, new_capacity);
> >
> >   size_type new_size = new_capacity < size() ? new_capacity : size();
> >   std::uninitialized_copy(end() - new_size, end(), buff);
> >   destroy();
> >   m_size = new_size;
> >   m_buff = m_first = buff;
> >   m_end = m_buff + new_capacity;
> >    m_last = full() ? m_buff : m_buff + size();
> >    guard.data = 0;
> > }
> >
> I think this is not a good idea because
> - it won't work -  the ~deleter_t() destructor does not have access to
> the deallocate() method
> - the original macros are more explanatory (it is easier to understand)
> - every STL implementation is using such macros
>
It may be possible to pass member function pointer or make deleter friend.

(Another possibility would be to use Alexandrescu's ScopeGuard.)

There's one good reason to avoid catch(...): on Win32 it interferes with
system exceptions handling. If someone uses __try/__catch/__finally,
these won't be called after throw; and also it won't be possible
to fix and continue system exception.

If I remember right, Digital Unix compiler had similar option for signals.

16. circular_buffer.html: the sentence
    "The rules for iterator invalidation" should be:
    "The rules for iterator (and result of data()) invalidation".

17. Maybe function data() should return 0 if buffer is empty instead
    of pointer pointing to garbage. It would at least make app behavior
    predictable.

18. documentation: "allocates memory continuously" should be replaced
    by "allocates memory as needed (growing and shrinking)".

19. circular_buffer_adaptor.html: is the first rule for invalidation of
    iterators valid? Shouldn't there be "MAY invalidate all iterators
    when buffer grows/shrinks, the rules from circular_buffer<> apply as
well"?

    Second rule here is the same as for circular_buffer<>.

20. Documentation: at the beginning of circular_buffer.html can be picture
    to give quick clue to people who do not read documentation throroughly
;-)

    Something like attached PNG. The circular_buffer_space_optimized can
have
    something too.

21. Documentation: <hr> between sections would make reading easier.

22. The code can use static_asserts to check if InputIterator::value_type
    is convertible to T (using type traits, many places).

    This would make errors easier to spot.

23. Something to catch errors better: could function destroy() set all
    internal pointers to 0? (at least in debug mode). This would lead
    to predictable behavior with orphaned iterators.

    Similarly, circular_buffer_space_optimized can (before deallocating,
    in debug mode) fill old buffer with 0xCC or so.

24. Question: do you plan to add Mojo to circular_buffer?

/Pavel