boostorg / circular_buffer Goto Github PK

Does it make sense to add .cbegin() and .cend() to boost::circular_buffer?

It currently is not provided:

../boost/boost/math/statistics/univariate_statistics.hpp:82:19: error: ‘const class boost::circular_buffer<double>’ has no member named ‘cbegin’; did you mean ‘begin’?
     return mean(v.cbegin(), v.cend());
                 ~~^~~~~~
                 begin

For possible implementation and benchmarking please see here.

this should be trivial to do. In fact, I might give implementing it a shot...

Hello,

Would it be possible to improve complexity of circular_buffer<T>::resize(new_size, item) in the case where T is scalar ?

Currently, complexity is always linear.

It would be nice to have constant complexity when T is a scalar type and no reallocation happens (ie. new_size <= capacity()).

When we want to reduce size of buffer (ie. new_size < size()), you could call erase_end(n) internally which already implements an optimization for scalar types.

When we want to increase size of buffer, you could optimize for scalar types by calling std::memset() at most 2 times.

Hi,
I have created a boost::circular_buffer<my_class_type> using the default ctor.
Then I call set_capacity(100) and then I push_back() a thousand elements: the size() of the circular buffer is reported as 99 and thus the function full() always return false.

I think this is very misleading: my belief is that instead of having:

bool full() const BOOST_NOEXCEPT { return capacity() == size(); }

we should have:

bool full() const BOOST_NOEXCEPT { return capacity()-1 == size(); }

What am I missing?

Thanks,
Francesco

The fix in the 'develop' branch is for the Embarcadero C++ clang-based compilers.

Having a compile-time size of a circular buffer is often useful:

boost::circular_array<double, 7> v;

Will attempt to provide this in a forthcoming PR if everyone thinks it's a good idea.

UBSan complains on presumably valid code:

#include <boost/circular_buffer.hpp>
#include <vector>

int main(int argc, const char * argv[]) {
    boost::circular_buffer<uint8_t> cbuff(99);
    std::vector<uint8_t> blah = { 'b', 'l', 'a', 'h', '\0'};
    
    // Wrap around
    for(unsigned i = 0; i < 99999; ++i) {
        cbuff.insert(cbuff.end(), blah.begin(), blah.end());
    }
    return 0;
}

Build and run:

$ clang++ -std=c++11 -fsanitize=undefined t.cpp -o t.exe
$ ./t.exe
/usr/local/include/boost/circular_buffer/base.hpp:2358:18: runtime error: addition of unsigned offset to 0x7fa96dc02b6f overflowed to 0x7fa96dc02b11

The complaint is on boost/circular_buffer/base.hpp:2358, where:

2358:         return p + (n < (m_end - p) ? n : n - capacity());

With:

(lldb) p/x (void*)p
(void *) $1 = 0x0000000100f0024f
(lldb) p/x (void*)n
(void *) $2 = 0x0000000000000005
(lldb) p/x (void*)m_end
(void *) $3 = 0x0000000100f00253

So m_end - p = 4, n = 5, the condition is false, and we are adding p + n - capacity(), and the p+n part is overflowing m_end.

As can be seen in https://godbolt.org/z/5aabcr99d, boost/circular_buffer/space_optimized.hpp is not self-contained and including (only) it causes a compilation error.

Hi,

I am trying to integrate boost into an android application for use with the Android NDK. I am trying to integrate boost 1.70.

I have tried two different configurations (both on Android):

Configuration 1
Android Gradle Plugin version: 3.4.1
Gradle version: 5.1.1
CMake version: 3.14.4
Android NDK version: 19.2.5345600

Configuration 2
I upgraded to the latest beta versions of all the above, so 3.5.+, etc.

Both are using Clang compilers. I built the boost library in two different ways... Using the following two repositories:
https://github.com/Orphis/boost-cmake
https://github.com/moritz-wundke/Boost-for-Android

In all cases (both configurations and both build types), I was able to successfully generate the boost files and import them into my project.

The only boost class that I require is boost::circular_buffer (and it's corresponding classes it references).

Basically, boost itself seems to be missing includes that it needs.

In the file boost/circular_buffer/base.hpp, I have the following issues

• Missing include for details.hpp, otherwise it cannot find "cb_details::const_traits"
• "BOOST_CB_ASSERT" and ".is_valid( ... )" all seem to be missing imports, etc.

Note: other issues exist in other files, as well. I tried manually adding the 'recommended' imports, but that just caused a chain reaction of missing imports that I couldn't resolve.

I tried using the tagged 1.70 version so I expected it to be stable.

Thanks for your help!

circular_buffer/test/common.ipp is calling std::allocator::max_size, which is removed in C++20.

Need to make change to common.ipp so that it can conform to C++20 standard.

Is there any interest in PRs that would turn this into a standalone (but c++14 - maybe 11 only) library?

I was using circular buffer in a side project of mine and as it was the only direct boost dependency I was curious if I could remove the boost dependency completely without rewriting the library.

Turns out that it is fairly easy to do this via a couple of search&replace transformations and 2-3 internalizations, because what few boost types are used have mostly been merged into the standard library.

I didn't need compatibility with any compiler that doesn't have full c++14 support, but if there is interest in this at all, I can check if c++11 would be sufficient (available type traits might be a limitation).

This is what most standard containers are doing today.

By replacing std::deque with boost::circular, I got a few compilation errors...

Prior to C++11, the guideline was to prefer iterator because of some STL API defect in regard to const_iterator but this got fixed in C++11

References:
Effective STL book
item 26: Prefer iterator to const_iterator, reverse_iterator, and const_reverse_iterator

Effective Modern C++ book
Item 13: Prefer const_iterators to iterators

Using gcc 9.1 with -fsanitize=undefined and -DBOOST_CB_ENABLE_DEBUG=1, the following code results in a ubsan error: "boost/circular_buffer/debug.hpp:37:16: runtime error: null pointer passed as argument 1, which is declared to never be null".

using Q = boost::circular_buffer<int>;  
Q q;    
const Q q2(q);

The ubsan error is a result of the following code in circular_buffer/debug.h:

template <class T>
inline void do_fill_uninitialized_memory(T* data, std::size_t size_in_bytes) BOOST_NOEXCEPT {
    std::memset(static_cast<void*>(data), UNINITIALIZED, size_in_bytes);
}

During copy construction, the function gets called with data == nullptr and size_in_bytes == 0. I believe that passing a null pointer to memset is technically undefined behavior even if the size is 0.

Changing the above function as follows avoids the ubsan error:

template <class T>
inline void do_fill_uninitialized_memory(T* data, std::size_t size_in_bytes) BOOST_NOEXCEPT {
    if (size_in_bytes != 0u) {
        std::memset(static_cast<void*>(data), UNINITIALIZED, size_in_bytes);
    }
}

I had originally written it to check for data != nullptr, but since this is debug code I thought it seemed desirable to know if the function is ever called with data == null and size_in_bytes != 0. In any case, either way will prevent the ubsan error.

I would like to use circular_buffer with Asio. And I'm not the only one -> https://stackoverflow.com/questions/19859833/read-data-into-a-circular-buffer

I could do something like

beast::buffers_cat(
asio::buffer(array_one().first, array_one().second),
asio::buffer(array_two().first, array_two().second)
)

to inform asio's async_read() of where it can write the received data to.
async_read would tell me how many bytes it has actually written into the circular_buffer.... and here I hit the wall. I need an API in circular_buffer where I can tell it "advance the pointer X elements because, even if push_back has not been called, the data is there".

Saw this in a build locally, thought I would report it... I haven't done any analysis on it.

../boost/circular_buffer/allocators.hpp:81:9: warning: destructor called on non-final 'Dummy' that has virtual functions but non-virtual destructor [-Wdelete-non-virtual-dtor]
        ptr->~U();
        ^
../boost/circular_buffer/details.hpp:473:38: note: in instantiation of function template specialization 'boost::cb_details::allocator_traits<std::allocator<Dummy> >::destroy<Dummy>' requested here
            allocator_traits<Alloc>::destroy(alloc, boost::to_address(next));
                                     ^
../boost/circular_buffer/base.hpp:2500:25: note: in instantiation of function template specialization 'boost::cb_details::uninitialized_fill_n_with_alloc<Dummy *, unsigned long, Dummy, std::allocator<Dummy> >' requested here
            cb_details::uninitialized_fill_n_with_alloc(m_buff, size(), item, alloc());
                        ^
../boost/circular_buffer/base.hpp:1056:9: note: in instantiation of member function 'boost::circular_buffer<Dummy, std::allocator<Dummy> >::initialize_buffer' requested here
        initialize_buffer(n, item);
        ^
../libs/circular_buffer/test/base_test.cpp:37:28: note: in instantiation of member function 'boost::circular_buffer<Dummy, std::allocator<Dummy> >::circular_buffer' requested here
    circular_buffer<Dummy> cb(3, Dummy());
                           ^
../boost/circular_buffer/allocators.hpp:81:15: note: qualify call to silence this warning
        ptr->~U();
              ^
              Dummy::
1 warning generated.

Boost >=1.69 implementation of max_size() calls this function which does NOT take into account the maximum size of the allocator.

Boost <= 1.68 implementation of max_size() was calling this function from boost::container which does take into account the maximum size of the allocator.

The relevant commit is ca3d667 @glenfe

As a result, when using a custom allocator with limited size MY_MAX_SIZE, previous calls to max_size() would return MY_MAX_SIZE, but they will now return (std::numeric_limits<size_type>::max)() / sizeof(value_type)

With Boost 1.69.0 beta 1 compilation of an application that uses a circular buffer fails with the following error:
boost/circular_buffer/allocators.hpp(38): error C2589: '(': illegal token on right side of '::'
because max is defined as a macro in Windows.h.

This can be fixed by preventing macro expansion by adding parentheses:
return (std::numeric_limits<size_type>::max)() / sizeof(value_type);

Example code:

#include <windows.h>
#include <boost/circular_buffer.hpp>

int main(int /*argc*/, char* /*argv*/[])
{
	boost::circular_buffer<int> cb(3);
	return 0;
}