环形内存circular_buffer

boost中支持环形内存。该内存在一些地方还是蛮实用的。

简单看下具体使用及部分源码，使用和源码相对来说都还是比较简单，易于理解的

与STL接口基本一致

void CCircularBufferTest::TestCircularBuffer()
{
circular_buffer<CTest> aa(5); // 预先分配5个sizeof(CTest)的大小空间
aa.push_back(CTest(1)); // 插入元素
aa.push_back(CTest(2));
int isize = aa.size();
bool bfull = aa.full();

for (int i = 3; i <= 7; ++i)
{
aa.push_back(CTest(i)); // 再次插入会覆盖到最初进入的元素
}
CTest* pTest = aa.linearize(); // 转换为指针
CTest* pTest5 = pTest+4;
}

部分源码分析

构造函数

explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type())
: m_size(0), m_alloc(alloc) {
initialize_buffer(buffer_capacity);
m_first = m_last = m_buff;
}

保存能力，默认分配算法

里面有m_first,m_last,m_buffer保存着该环形内存的各个位置状态

初始化该能力的空间

//! Initialize the internal buffer.
void initialize_buffer(capacity_type buffer_capacity) {
m_buff = allocate(buffer_capacity);
m_end = m_buff + buffer_capacity;
}

继续往下调用allocate。再往下就是调用::operator new，没有调用C++的new，因为此处是分配原始内存，没有构造函数的

//! Allocate memory.
pointer allocate(size_type n) {
if (n > max_size())
throw_exception(std::length_error("circular_buffer"));
#if BOOST_CB_ENABLE_DEBUG
pointer p = (n == 0) ? 0 : m_alloc.allocate(n);
cb_details::do_fill_uninitialized_memory(p, sizeof(value_type) * n);
return p;
#else
return (n == 0) ? 0 : m_alloc.allocate(n);
#endif
}

这个里面有个比较有意思的地方do_fill_uninitialized_memory

const int UNINITIALIZED = 0xcc;

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);
}

是对这个地址空间memset为0xcc，就是我们经常看到的烫烫。。。，是为了方便我们一眼就看出这个内存是未初始化赋值的

构造后再看下push_back操作

template <class ValT>
void push_back_impl(ValT item) {
if (full()) {
if (empty())
return;
replace(m_last, static_cast<ValT>(item));
increment(m_last);
m_first = m_last;
} else {
boost::container::allocator_traits<Alloc>::construct(m_alloc, boost::addressof(*m_last), static_cast<ValT>(item));
increment(m_last);
++m_size;
}
}

如果空间未满，就会调用construct。实际上最后是调用到了

inline void *operator new(std::size_t, void *p, boost_container_new_t)

在p地址空间上调用了T的构造函数，我这里使用的是一个类CTest，最后会调用到CTest的拷贝构造函数中。

如果空间已经满了，则把最前面的进行覆盖，即上面的m_pLast,再看下last的赋值就知道为什么需要覆盖last了

void increment(Pointer& p) const {
if (++p == m_end)
p = m_buff;
}

当p的值到达m_pend时，会把m_buff(即首地址)赋给p，而p其实只是个参数，传入的就是m_last。就是满了的话，m_last就指向了最前面了

最主要的应该就是上面分析的这几个接口了。

可以看出环形内存在一开始就分配了固定大小的内存出来，有时或许会浪费空间，所以boost还提供了一个circular_buffer_space_optimized的优化型的缓冲区

先看下基本使用

void CCircularBufferTest::TestCircularBufferSpaceOptimized()
{
circular_buffer_space_optimized<CTest> cb(10);
for (int i = 0; i < 15; ++i)
{
cb.push_back(CTest(i));
}
int icbSize = cb.size();
int icbCapacity = cb.capacity();

TestCircularBufferSpaceOptimized();
}

接口基本一致，只是源码实现会略有不同

构造函数

explicit circular_buffer_space_optimized(capacity_type capacity_ctrl,
const allocator_type& alloc = allocator_type())
: circular_buffer<T, Alloc>(capacity_ctrl.min_capacity(), alloc)
, m_capacity_ctrl(capacity_ctrl) {}

里面会用到一个辅助类

template <class Size>
class capacity_control {

//! The capacity of the space-optimized circular buffer.
Size m_capacity;

//! The lowest guaranteed or minimum capacity of the adapted space-optimized circular buffer.
Size m_min_capacity;

public:

//! Constructor.
capacity_control(Size buffer_capacity, Size min_buffer_capacity = 0)
: m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity)
{ // Check for capacity lower than min_capacity.
BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity);
}

// Default copy constructor.

// Default assign operator.

//! Get the capacity of the space optimized circular buffer.
Size capacity() const { return m_capacity; }

//! Get the minimal capacity of the space optimized circular buffer.
Size min_capacity() const { return m_min_capacity; }

//! Size operator - returns the capacity of the space optimized circular buffer.
operator Size() const { return m_capacity; }
};

circular_buffer_space_optimized的容量是用该结构体在表示，它的构造只是赋了一些初始化值，而不会分配内存

再看下push_back的实现

void push_back(param_value_type item) {
check_low_capacity();
circular_buffer<T, Alloc>::push_back(item);
}

后面一句circular_buffer<T, Alloc>::push_back(item);与上面的circular_buffer一样。区别就在于check_low_capacity了

void check_low_capacity(size_type n = 1) {
size_type new_size = size() + n;
size_type new_capacity = circular_buffer<T, Alloc>::capacity();
if (new_size > new_capacity) {
if (new_capacity == 0)
new_capacity = 1;
for (; new_size > new_capacity; new_capacity *= 2) {}
circular_buffer<T, Alloc>::set_capacity(
ensure_reserve(new_capacity, new_size));
}
#if BOOST_CB_ENABLE_DEBUG
this->invalidate_iterators_except(end());
#endif
}

该接口会判断当前需要的大小，就是以前的大小加上n，因为push_back是插入一个元素，所以n用的默认值1，如果是insert多个元素，此处会传入有效的n

new_size>new_capacity，就表示空间不够了。需要新分配，新分配使用circular_buffer，会进行*2扩容分配( for (; new_size > new_capacity; new_capacity *= 2) {})。这样可以减少分配次数。当然扩容分配的容量也是在最初指定的能力之内的。此处有判断，如下
//! Ensure the reserve for possible growth up.
size_type ensure_reserve(size_type new_capacity, size_type buffer_size) const {
if (buffer_size + new_capacity / 5 >= new_capacity)
new_capacity *= 2; // ensure at least 20% reserve
if (new_capacity > m_capacity_ctrl)
return m_capacity_ctrl;
return new_capacity;
}

m_capacity_ctrl就是最初指定的值，如果*2扩容之后，不能保证空余20%，会再次*2扩容。空间扩展后，后续push_back就与前面一样了

另外它还有一个优化就是erase后，它会删除空间？？？？ erase源码分析

iterator erase(iterator pos) {
iterator it = circular_buffer<T, Alloc>::erase(pos);
size_type index = it - begin();
check_high_capacity();
return begin() + index;
}

circular_buffer<T, Alloc>::erase(pos);只是会调用对象的析构函数，不会释放空间

与书中讲解冲突的两个地方

1、优化后的环形内存分配足空间后是不会释放的

2、优化后的环形内存，在分配空间时会大于非优化的环形内存。比如我只需要500个2k的数据，用非优化的会分配1M的空间出来，但是用了优化个的circular_buffer_space_optimized会分配2M，看源码就能发现原因所在了。使用需要注意呀，罗剑锋的boost中有些地方讲解的不太对呀。