//----------------------------------------------------------------------------
/// @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 <ciso646>
#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 = static_cast <Value_t*> (std::malloc (NMAX * sizeof(Value_t)));
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::free(static_cast <void*> (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