//----------------------------------------------------------------------------
|
/// @file circular_buffer.hpp
|
/// @brief This file contains the implementation of the circular buffer
|
///
|
/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
|
/// Distributed under the Boost Software License, Version 1.0.\n
|
/// ( See accompanyingfile LICENSE_1_0.txt or copy at
|
/// http://www.boost.org/LICENSE_1_0.txt )
|
/// @version 0.1
|
///
|
/// @remarks
|
//-----------------------------------------------------------------------------
|
#ifndef __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
|
#define __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
|
|
#include <memory>
|
#include <cassert>
|
#include <exception>
|
#include <boost/sort/common/util/algorithm.hpp>
|
#include <boost/sort/common/util/traits.hpp>
|
|
namespace boost
|
{
|
namespace sort
|
{
|
namespace common
|
{
|
namespace util
|
{
|
|
//---------------------------------------------------------------------------
|
/// @class circular_buffer
|
/// @brief This class implement a circular buffer
|
/// @remarks
|
//---------------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2 = 11>
|
struct circular_buffer
|
{
|
//------------------------------------------------------------------------
|
// STATIC CHECK
|
//------------------------------------------------------------------------
|
static_assert ( Power2 != 0, "Wrong Power2");
|
|
//------------------------------------------------------------------------
|
// DEFINITIONS
|
//------------------------------------------------------------------------
|
typedef Value_t value_t;
|
|
//------------------------------------------------------------------------
|
// VARIABLES
|
//------------------------------------------------------------------------
|
const size_t NMAX = (size_t) 1 << Power2;
|
const size_t MASK = (NMAX - 1);
|
const size_t BLOCK_SIZE = NMAX >> 1;
|
const size_t LOG_BLOCK = Power2 - 1;
|
Value_t * ptr = nullptr;
|
|
//------------------------------------------------------------------------
|
// first and last are the position of the first and last elements
|
// always are in the range [0, NMAX - 1]
|
//------------------------------------------------------------------------
|
size_t nelem, first_pos;
|
bool initialized;
|
|
//
|
//------------------------------------------------------------------------
|
// function : circular_buffer
|
/// @brief constructor of the class
|
//-----------------------------------------------------------------------
|
circular_buffer(void)
|
: ptr(nullptr), nelem(0), first_pos(0), initialized(false)
|
{
|
ptr = std::get_temporary_buffer < Value_t > (NMAX).first;
|
if (ptr == nullptr) throw std::bad_alloc();
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : ~circular_buffer
|
/// @brief destructor of the class
|
//-----------------------------------------------------------------------
|
~circular_buffer()
|
{
|
if (initialized)
|
{ for (size_t i = 0; i < NMAX; ++i) (ptr + i)->~Value_t();
|
initialized = false;
|
};
|
std::return_temporary_buffer(ptr);
|
}
|
;
|
//
|
//------------------------------------------------------------------------
|
// function : initialize
|
/// @brief : initialize the memory of the buffer from the uninitialize
|
// memory obtained from the temporary buffer
|
/// @param val : value used to initialize the memory
|
//-----------------------------------------------------------------------
|
void initialize(Value_t & val)
|
{
|
assert (initialized == false);
|
::new (static_cast<void*>(ptr)) Value_t(std::move(val));
|
for (size_t i = 1; i < NMAX; ++i)
|
::new (static_cast<void*>(ptr + i)) Value_t(std::move(ptr[i - 1]));
|
val = std::move(ptr[NMAX - 1]);
|
initialized = true;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : destroy_all
|
/// @brief : destroy all the objects in the internal memory
|
//-----------------------------------------------------------------------
|
void destroy_all(void) { destroy(ptr, ptr + NMAX); };
|
//
|
//------------------------------------------------------------------------
|
// function : get_buffer
|
/// @brief return the internal memory of the circular buffer
|
/// @return pointer to the internal memory of the buffer
|
//-----------------------------------------------------------------------
|
Value_t * get_buffer(void) { return ptr; };
|
//
|
//------------------------------------------------------------------------
|
// function : empty
|
/// @brief return if the buffer is empty
|
/// @return true : empty
|
//-----------------------------------------------------------------------
|
bool empty(void) const {return (nelem == 0); };
|
//
|
//------------------------------------------------------------------------
|
// function : full
|
/// @brief return if the buffer is full
|
/// @return true : full
|
//-----------------------------------------------------------------------
|
bool full(void) const { return (nelem == NMAX); };
|
//
|
//------------------------------------------------------------------------
|
// function : size
|
/// @brief return the number of elements stored in the buffer
|
/// @return number of elements stored
|
//-----------------------------------------------------------------------
|
size_t size(void) const { return nelem;};
|
//
|
//------------------------------------------------------------------------
|
// function : capacity
|
/// @brief : return the maximun capacity of the buffer
|
/// @return number of elements
|
//-----------------------------------------------------------------------
|
size_t capacity(void) const { return NMAX;};
|
//
|
//------------------------------------------------------------------------
|
// function : free_size
|
/// @brief return the free positions in the buffer
|
/// @return number of elements
|
//-----------------------------------------------------------------------
|
size_t free_size(void) const { return (NMAX - nelem); };
|
//
|
//------------------------------------------------------------------------
|
// function : clear
|
/// @brief clear the buffer
|
//-----------------------------------------------------------------------
|
void clear(void) { nelem = first_pos = 0; };
|
//
|
//------------------------------------------------------------------------
|
// function : front
|
/// @brief return the first element of the buffer
|
/// @return reference to the first value
|
//-----------------------------------------------------------------------
|
Value_t & front(void)
|
{
|
#ifdef __BS_DEBUG
|
assert (nelem > 0);
|
#endif
|
return (ptr[first_pos]);
|
};
|
//
|
//------------------------------------------------------------------------
|
// function :front
|
/// @brief return the first element of the buffer
|
/// @return const reference to the first value
|
//-----------------------------------------------------------------------
|
const Value_t & front(void) const
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
return (ptr[first_pos]);
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : back
|
/// @brief reference to the last value of the buffer
|
/// @return reference to the last value
|
//-----------------------------------------------------------------------
|
Value_t & back(void)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
return (ptr[(first_pos + nelem - 1) & MASK]);
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : back
|
/// @brief reference to the last value of the buffer
|
/// @return const reference to the last value
|
//-----------------------------------------------------------------------
|
const Value_t & back(void) const
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
return (ptr[(first_pos + nelem - 1) & MASK]);
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : operator []
|
/// @brief positional access to the elements
|
/// @param pos rquested
|
/// @return reference to the element
|
//-----------------------------------------------------------------------
|
Value_t & operator[](uint32_t pos)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
return ptr[(first_pos + pos) & MASK];
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : operator []
|
/// @brief positional access to the elements
|
/// @param pos rquested
|
/// @return const reference to the element
|
//-----------------------------------------------------------------------
|
const Value_t & operator[](uint32_t pos) const
|
{
|
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
return ptr[(first_pos + pos) & MASK];
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_front
|
/// @brief insert an element in the first position of the buffer
|
/// @param val : const value to insert
|
//-----------------------------------------------------------------------
|
void push_front(const Value_t & val)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem != NMAX);
|
#endif
|
++nelem;
|
first_pos = ((first_pos + MASK) & MASK);
|
ptr[first_pos] = val;
|
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_front
|
/// @brief insert an element in the first position of the buffer
|
/// @param val : rvalue to insert
|
//-----------------------------------------------------------------------
|
void push_front(Value_t && val)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem != NMAX);
|
#endif
|
++nelem;
|
first_pos = ((first_pos + MASK) & MASK);
|
ptr[first_pos] = val;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_back
|
/// @brief insert an element in the last position of the buffer
|
/// @param val : value to insert
|
//-----------------------------------------------------------------------
|
void push_back(const Value_t & val)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem != NMAX);
|
#endif
|
ptr[(first_pos + (nelem++)) & MASK] = val;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_back
|
/// @brief insert an element in the last position of the buffer
|
/// @param val : value to insert
|
//-----------------------------------------------------------------------
|
void push_back(Value_t && val)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem != NMAX);
|
#endif
|
ptr[(first_pos + (nelem++)) & MASK] = std::move(val);
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : pop_front
|
/// @brief remove the first element of the buffer
|
//-----------------------------------------------------------------------
|
void pop_front(void)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
--nelem;
|
(++first_pos) &= MASK;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : pop_back
|
/// @brief remove the last element of the buffer
|
//-----------------------------------------------------------------------
|
void pop_back(void)
|
{
|
#ifdef __BS_DEBUG
|
assert ( nelem > 0 );
|
#endif
|
--nelem;
|
};
|
|
template<class iter_t>
|
void pop_copy_front(iter_t it_dest, size_t num);
|
|
template<class iter_t>
|
void pop_move_front(iter_t it_dest, size_t num);
|
|
template<class iter_t>
|
void pop_copy_back(iter_t it_dest, size_t num);
|
|
template<class iter_t>
|
void pop_move_back(iter_t it_dest, size_t num);
|
|
template<class iter_t>
|
void push_copy_front(iter_t it_src, size_t num);
|
|
template<class iter_t>
|
void push_move_front(iter_t it_src, size_t num);
|
|
template<class iter_t>
|
void push_copy_back(iter_t it_src, size_t num);
|
|
template<class iter_t>
|
void push_move_back(iter_t it_src, size_t num);
|
|
//---------------------------------------------------------------------------
|
};// End of class circular_buffer
|
//---------------------------------------------------------------------------
|
//
|
//
|
//############################################################################
|
// ##
|
// N O N I N L I N E F U N C T I O N S ##
|
// ##
|
//############################################################################
|
//
|
//------------------------------------------------------------------------
|
// function : pop_copy_front
|
/// @brief copy and delete num elements from the front of the buffer
|
/// @param it_dest : iterator to the first position where copy the elements
|
/// @param num : number of elements to copy
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::pop_copy_front(iter_t it_dest, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( num <= nelem);
|
#endif
|
nelem -= num;
|
size_t pos = first_pos;
|
first_pos = (first_pos + num) & MASK;
|
for (size_t i = 0; i < num; ++i)
|
{
|
*(it_dest++) = ptr[pos++ & MASK];
|
};
|
first_pos &= MASK;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : pop_move_front
|
/// @brief move num elements from the front of the buffer to the place
|
// pointed by it_dest
|
/// @param it_dest : iterator to the first position where move the elements
|
/// @param num : number of elements to move
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
:: pop_move_front(iter_t it_dest, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( num <= nelem);
|
#endif
|
nelem -= num;
|
size_t pos = first_pos;
|
first_pos = (first_pos + num) & MASK;
|
for (size_t i = 0; i < num; ++i)
|
{
|
*(it_dest++) = std::move(ptr[pos++ & MASK]);
|
};
|
first_pos &= MASK;
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : pop_copy_back
|
/// @brief copy and delete num elements from the back of the buffer
|
/// @param p1 : iterator where begin to copy the elements
|
/// @param num : number of elements to copy
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::pop_copy_back(iter_t it_dest, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( num <= nelem);
|
#endif
|
nelem -= num;
|
size_t pos = (first_pos + nelem) & MASK;
|
for (size_t i = 0; i < num; ++i)
|
{
|
*(it_dest++) = ptr[pos++ & MASK];
|
};
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : pop_move_back
|
/// @brief move and delete num elements from the back of the buffer
|
/// @param p1 : iterator where begin to move the elements
|
/// @param num : number of elements to move
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::pop_move_back(iter_t it_dest, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( num <= nelem);
|
#endif
|
nelem -= num;
|
size_t pos = (first_pos + nelem) & MASK;
|
for (size_t i = 0; i < num; ++i)
|
{
|
*(it_dest++) = std::move(ptr[pos++ & MASK]);
|
};
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_copy_front
|
/// @brief copy num elements in the front of the buffer
|
/// @param it_src : iterator from where begin to copy the elements
|
/// @param mun : number of element to copy
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::push_copy_front(iter_t it_src, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( free_size() >= num);
|
#endif
|
nelem += num;
|
|
first_pos = (first_pos + NMAX - num) & MASK;
|
size_t pos = first_pos;
|
for (size_t i = 0; i < num; ++i)
|
{
|
ptr[(pos++) & MASK] = *(it_src++);
|
};
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_move_front
|
/// @brief move num elements in the front of the buffer
|
/// @param p1 : iterator from where begin to move the elements
|
/// @param mun : number of element to move
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::push_move_front(iter_t it_src, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( free_size() >= num);
|
#endif
|
nelem += num;
|
size_t pos = first_pos;
|
for (size_t i = 0; i < num; ++i)
|
{
|
ptr[(pos++) & MASK] = std::move(*(it_src++));
|
};
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_copy_back
|
/// @brief copy num elements in the back of the buffer
|
/// @param p1 : iterator from where begin to copy the elements
|
/// @param mun : number of element to copy
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::push_copy_back(iter_t it_src, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( free_size() >= num);
|
#endif
|
size_t pos = first_pos + nelem;
|
nelem += num;
|
for (size_t i = 0; i < num; ++i)
|
{
|
ptr[(pos++) & MASK] = *(it_src++);
|
};
|
};
|
//
|
//------------------------------------------------------------------------
|
// function : push_move_back
|
/// @brief move num elements in the back of the buffer
|
/// @param p1 : iterator from where begin to move the elements
|
/// @param mun : number of element to move
|
//-----------------------------------------------------------------------
|
template <class Value_t, uint32_t Power2>
|
template<class iter_t>
|
void circular_buffer<Value_t, Power2>
|
::push_move_back(iter_t it_src, size_t num)
|
{
|
static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
|
"Incompatible iterator");
|
if (num == 0) return;
|
#ifdef __BS_DEBUG
|
assert ( free_size() >= num);
|
#endif
|
size_t pos = first_pos + nelem;
|
nelem += num;
|
for (size_t i = 0; i < num; ++i)
|
{
|
ptr[(pos++) & MASK] = std::move(*(it_src++));
|
};
|
};
|
|
//****************************************************************************
|
};// End namespace util
|
};// End namespace common
|
};// End namespace sort
|
};// End namespace boost
|
//****************************************************************************
|
#endif
|
