summaryrefslogtreecommitdiff
path: root/boost/sort/common/util/circular_buffer.hpp
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2019-12-05 15:12:59 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2019-12-05 15:12:59 +0900
commitb8cf34c691623e4ec329053cbbf68522a855882d (patch)
tree34da08632a99677f6b79ecb65e5b655a5b69a67f /boost/sort/common/util/circular_buffer.hpp
parent3fdc3e5ee96dca5b11d1694975a65200787eab86 (diff)
downloadboost-b8cf34c691623e4ec329053cbbf68522a855882d.tar.gz
boost-b8cf34c691623e4ec329053cbbf68522a855882d.tar.bz2
boost-b8cf34c691623e4ec329053cbbf68522a855882d.zip
Imported Upstream version 1.67.0upstream/1.67.0
Diffstat (limited to 'boost/sort/common/util/circular_buffer.hpp')
-rw-r--r--boost/sort/common/util/circular_buffer.hpp572
1 files changed, 572 insertions, 0 deletions
diff --git a/boost/sort/common/util/circular_buffer.hpp b/boost/sort/common/util/circular_buffer.hpp
new file mode 100644
index 0000000000..2fc7e973e1
--- /dev/null
+++ b/boost/sort/common/util/circular_buffer.hpp
@@ -0,0 +1,572 @@
+//----------------------------------------------------------------------------
+/// @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