1//----------------------------------------------------------------------------
2/// @file circular_buffer.hpp
3/// @brief This file contains the implementation of the circular buffer
4///
5/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
6/// Distributed under the Boost Software License, Version 1.0.\n
7/// ( See accompanyingfile LICENSE_1_0.txt or copy at
8/// http://www.boost.org/LICENSE_1_0.txt )
9/// @version 0.1
10///
11/// @remarks
12//-----------------------------------------------------------------------------
13#ifndef __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
14#define __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
15
16#include <ciso646>
17#include <memory>
18#include <cassert>
19#include <exception>
20#include <boost/sort/common/util/algorithm.hpp>
21#include <boost/sort/common/util/traits.hpp>
22
23namespace boost
24{
25namespace sort
26{
27namespace common
28{
29namespace util
30{
31
32//---------------------------------------------------------------------------
33/// @class circular_buffer
34/// @brief This class implement a circular buffer
35/// @remarks
36//---------------------------------------------------------------------------
37template <class Value_t, uint32_t Power2 = 11>
38struct circular_buffer
39{
40 //------------------------------------------------------------------------
41 // STATIC CHECK
42 //------------------------------------------------------------------------
43 static_assert ( Power2 != 0, "Wrong Power2");
44
45 //------------------------------------------------------------------------
46 // DEFINITIONS
47 //------------------------------------------------------------------------
48 typedef Value_t value_t;
49
50 //------------------------------------------------------------------------
51 // VARIABLES
52 //------------------------------------------------------------------------
53 const size_t NMAX = (size_t) 1 << Power2;
54 const size_t MASK = (NMAX - 1);
55 const size_t BLOCK_SIZE = NMAX >> 1;
56 const size_t LOG_BLOCK = Power2 - 1;
57 Value_t * ptr = nullptr;
58
59 //------------------------------------------------------------------------
60 // first and last are the position of the first and last elements
61 // always are in the range [0, NMAX - 1]
62 //------------------------------------------------------------------------
63 size_t nelem, first_pos;
64 bool initialized;
65
66 //
67 //------------------------------------------------------------------------
68 // function : circular_buffer
69 /// @brief constructor of the class
70 //-----------------------------------------------------------------------
71 circular_buffer(void)
72 : ptr(nullptr), nelem(0), first_pos(0), initialized(false)
73 {
74 ptr = static_cast <Value_t*> (std::malloc (size: NMAX * sizeof(Value_t)));
75 if (ptr == nullptr) throw std::bad_alloc();
76 };
77 //
78 //------------------------------------------------------------------------
79 // function : ~circular_buffer
80 /// @brief destructor of the class
81 //-----------------------------------------------------------------------
82 ~circular_buffer()
83 {
84 if (initialized)
85 { for (size_t i = 0; i < NMAX; ++i) (ptr + i)->~Value_t();
86 initialized = false;
87 };
88 std::free(ptr: static_cast <void*> (ptr));
89 }
90 ;
91 //
92 //------------------------------------------------------------------------
93 // function : initialize
94 /// @brief : initialize the memory of the buffer from the uninitialize
95 // memory obtained from the temporary buffer
96 /// @param val : value used to initialize the memory
97 //-----------------------------------------------------------------------
98 void initialize(Value_t & val)
99 {
100 assert (initialized == false);
101 ::new (static_cast<void*>(ptr)) Value_t(std::move(val));
102 for (size_t i = 1; i < NMAX; ++i)
103 ::new (static_cast<void*>(ptr + i)) Value_t(std::move(ptr[i - 1]));
104 val = std::move(ptr[NMAX - 1]);
105 initialized = true;
106 };
107 //
108 //------------------------------------------------------------------------
109 // function : destroy_all
110 /// @brief : destroy all the objects in the internal memory
111 //-----------------------------------------------------------------------
112 void destroy_all(void) { destroy(ptr, ptr + NMAX); };
113 //
114 //------------------------------------------------------------------------
115 // function : get_buffer
116 /// @brief return the internal memory of the circular buffer
117 /// @return pointer to the internal memory of the buffer
118 //-----------------------------------------------------------------------
119 Value_t * get_buffer(void) { return ptr; };
120 //
121 //------------------------------------------------------------------------
122 // function : empty
123 /// @brief return if the buffer is empty
124 /// @return true : empty
125 //-----------------------------------------------------------------------
126 bool empty(void) const {return (nelem == 0); };
127 //
128 //------------------------------------------------------------------------
129 // function : full
130 /// @brief return if the buffer is full
131 /// @return true : full
132 //-----------------------------------------------------------------------
133 bool full(void) const { return (nelem == NMAX); };
134 //
135 //------------------------------------------------------------------------
136 // function : size
137 /// @brief return the number of elements stored in the buffer
138 /// @return number of elements stored
139 //-----------------------------------------------------------------------
140 size_t size(void) const { return nelem;};
141 //
142 //------------------------------------------------------------------------
143 // function : capacity
144 /// @brief : return the maximun capacity of the buffer
145 /// @return number of elements
146 //-----------------------------------------------------------------------
147 size_t capacity(void) const { return NMAX;};
148 //
149 //------------------------------------------------------------------------
150 // function : free_size
151 /// @brief return the free positions in the buffer
152 /// @return number of elements
153 //-----------------------------------------------------------------------
154 size_t free_size(void) const { return (NMAX - nelem); };
155 //
156 //------------------------------------------------------------------------
157 // function : clear
158 /// @brief clear the buffer
159 //-----------------------------------------------------------------------
160 void clear(void) { nelem = first_pos = 0; };
161 //
162 //------------------------------------------------------------------------
163 // function : front
164 /// @brief return the first element of the buffer
165 /// @return reference to the first value
166 //-----------------------------------------------------------------------
167 Value_t & front(void)
168 {
169#ifdef __BS_DEBUG
170 assert (nelem > 0);
171#endif
172 return (ptr[first_pos]);
173 };
174 //
175 //------------------------------------------------------------------------
176 // function :front
177 /// @brief return the first element of the buffer
178 /// @return const reference to the first value
179 //-----------------------------------------------------------------------
180 const Value_t & front(void) const
181 {
182#ifdef __BS_DEBUG
183 assert ( nelem > 0 );
184#endif
185 return (ptr[first_pos]);
186 };
187 //
188 //------------------------------------------------------------------------
189 // function : back
190 /// @brief reference to the last value of the buffer
191 /// @return reference to the last value
192 //-----------------------------------------------------------------------
193 Value_t & back(void)
194 {
195#ifdef __BS_DEBUG
196 assert ( nelem > 0 );
197#endif
198 return (ptr[(first_pos + nelem - 1) & MASK]);
199 };
200 //
201 //------------------------------------------------------------------------
202 // function : back
203 /// @brief reference to the last value of the buffer
204 /// @return const reference to the last value
205 //-----------------------------------------------------------------------
206 const Value_t & back(void) const
207 {
208#ifdef __BS_DEBUG
209 assert ( nelem > 0 );
210#endif
211 return (ptr[(first_pos + nelem - 1) & MASK]);
212 };
213 //
214 //------------------------------------------------------------------------
215 // function : operator []
216 /// @brief positional access to the elements
217 /// @param pos rquested
218 /// @return reference to the element
219 //-----------------------------------------------------------------------
220 Value_t & operator[](uint32_t pos)
221 {
222#ifdef __BS_DEBUG
223 assert ( nelem > 0 );
224#endif
225 return ptr[(first_pos + pos) & MASK];
226 };
227 //
228 //------------------------------------------------------------------------
229 // function : operator []
230 /// @brief positional access to the elements
231 /// @param pos rquested
232 /// @return const reference to the element
233 //-----------------------------------------------------------------------
234 const Value_t & operator[](uint32_t pos) const
235 {
236
237#ifdef __BS_DEBUG
238 assert ( nelem > 0 );
239#endif
240 return ptr[(first_pos + pos) & MASK];
241 };
242 //
243 //------------------------------------------------------------------------
244 // function : push_front
245 /// @brief insert an element in the first position of the buffer
246 /// @param val : const value to insert
247 //-----------------------------------------------------------------------
248 void push_front(const Value_t & val)
249 {
250#ifdef __BS_DEBUG
251 assert ( nelem != NMAX);
252#endif
253 ++nelem;
254 first_pos = ((first_pos + MASK) & MASK);
255 ptr[first_pos] = val;
256
257 };
258 //
259 //------------------------------------------------------------------------
260 // function : push_front
261 /// @brief insert an element in the first position of the buffer
262 /// @param val : rvalue to insert
263 //-----------------------------------------------------------------------
264 void push_front(Value_t && val)
265 {
266#ifdef __BS_DEBUG
267 assert ( nelem != NMAX);
268#endif
269 ++nelem;
270 first_pos = ((first_pos + MASK) & MASK);
271 ptr[first_pos] = val;
272 };
273 //
274 //------------------------------------------------------------------------
275 // function : push_back
276 /// @brief insert an element in the last position of the buffer
277 /// @param val : value to insert
278 //-----------------------------------------------------------------------
279 void push_back(const Value_t & val)
280 {
281#ifdef __BS_DEBUG
282 assert ( nelem != NMAX);
283#endif
284 ptr[(first_pos + (nelem++)) & MASK] = val;
285 };
286 //
287 //------------------------------------------------------------------------
288 // function : push_back
289 /// @brief insert an element in the last position of the buffer
290 /// @param val : value to insert
291 //-----------------------------------------------------------------------
292 void push_back(Value_t && val)
293 {
294#ifdef __BS_DEBUG
295 assert ( nelem != NMAX);
296#endif
297 ptr[(first_pos + (nelem++)) & MASK] = std::move(val);
298 };
299 //
300 //------------------------------------------------------------------------
301 // function : pop_front
302 /// @brief remove the first element of the buffer
303 //-----------------------------------------------------------------------
304 void pop_front(void)
305 {
306#ifdef __BS_DEBUG
307 assert ( nelem > 0 );
308#endif
309 --nelem;
310 (++first_pos) &= MASK;
311 };
312 //
313 //------------------------------------------------------------------------
314 // function : pop_back
315 /// @brief remove the last element of the buffer
316 //-----------------------------------------------------------------------
317 void pop_back(void)
318 {
319#ifdef __BS_DEBUG
320 assert ( nelem > 0 );
321#endif
322 --nelem;
323 };
324
325 template<class iter_t>
326 void pop_copy_front(iter_t it_dest, size_t num);
327
328 template<class iter_t>
329 void pop_move_front(iter_t it_dest, size_t num);
330
331 template<class iter_t>
332 void pop_copy_back(iter_t it_dest, size_t num);
333
334 template<class iter_t>
335 void pop_move_back(iter_t it_dest, size_t num);
336
337 template<class iter_t>
338 void push_copy_front(iter_t it_src, size_t num);
339
340 template<class iter_t>
341 void push_move_front(iter_t it_src, size_t num);
342
343 template<class iter_t>
344 void push_copy_back(iter_t it_src, size_t num);
345
346 template<class iter_t>
347 void push_move_back(iter_t it_src, size_t num);
348
349//---------------------------------------------------------------------------
350};// End of class circular_buffer
351//---------------------------------------------------------------------------
352//
353//
354//############################################################################
355// ##
356// N O N I N L I N E F U N C T I O N S ##
357// ##
358//############################################################################
359//
360//------------------------------------------------------------------------
361// function : pop_copy_front
362/// @brief copy and delete num elements from the front of the buffer
363/// @param it_dest : iterator to the first position where copy the elements
364/// @param num : number of elements to copy
365//-----------------------------------------------------------------------
366template <class Value_t, uint32_t Power2>
367template<class iter_t>
368void circular_buffer<Value_t, Power2>
369::pop_copy_front(iter_t it_dest, size_t num)
370{
371 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
372 "Incompatible iterator");
373 if (num == 0) return;
374#ifdef __BS_DEBUG
375 assert ( num <= nelem);
376#endif
377 nelem -= num;
378 size_t pos = first_pos;
379 first_pos = (first_pos + num) & MASK;
380 for (size_t i = 0; i < num; ++i)
381 {
382 *(it_dest++) = ptr[pos++ & MASK];
383 };
384 first_pos &= MASK;
385};
386//
387//------------------------------------------------------------------------
388// function : pop_move_front
389/// @brief move num elements from the front of the buffer to the place
390// pointed by it_dest
391/// @param it_dest : iterator to the first position where move the elements
392/// @param num : number of elements to move
393//-----------------------------------------------------------------------
394template <class Value_t, uint32_t Power2>
395template<class iter_t>
396void circular_buffer<Value_t, Power2>
397:: pop_move_front(iter_t it_dest, size_t num)
398{
399 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
400 "Incompatible iterator");
401 if (num == 0) return;
402#ifdef __BS_DEBUG
403 assert ( num <= nelem);
404#endif
405 nelem -= num;
406 size_t pos = first_pos;
407 first_pos = (first_pos + num) & MASK;
408 for (size_t i = 0; i < num; ++i)
409 {
410 *(it_dest++) = std::move(ptr[pos++ & MASK]);
411 };
412 first_pos &= MASK;
413};
414//
415//------------------------------------------------------------------------
416// function : pop_copy_back
417/// @brief copy and delete num elements from the back of the buffer
418/// @param p1 : iterator where begin to copy the elements
419/// @param num : number of elements to copy
420//-----------------------------------------------------------------------
421template <class Value_t, uint32_t Power2>
422template<class iter_t>
423void circular_buffer<Value_t, Power2>
424::pop_copy_back(iter_t it_dest, size_t num)
425{
426 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
427 "Incompatible iterator");
428 if (num == 0) return;
429#ifdef __BS_DEBUG
430 assert ( num <= nelem);
431#endif
432 nelem -= num;
433 size_t pos = (first_pos + nelem) & MASK;
434 for (size_t i = 0; i < num; ++i)
435 {
436 *(it_dest++) = ptr[pos++ & MASK];
437 };
438};
439//
440//------------------------------------------------------------------------
441// function : pop_move_back
442/// @brief move and delete num elements from the back of the buffer
443/// @param p1 : iterator where begin to move the elements
444/// @param num : number of elements to move
445//-----------------------------------------------------------------------
446template <class Value_t, uint32_t Power2>
447template<class iter_t>
448void circular_buffer<Value_t, Power2>
449::pop_move_back(iter_t it_dest, size_t num)
450{
451 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
452 "Incompatible iterator");
453 if (num == 0) return;
454#ifdef __BS_DEBUG
455 assert ( num <= nelem);
456#endif
457 nelem -= num;
458 size_t pos = (first_pos + nelem) & MASK;
459 for (size_t i = 0; i < num; ++i)
460 {
461 *(it_dest++) = std::move(ptr[pos++ & MASK]);
462 };
463};
464//
465//------------------------------------------------------------------------
466// function : push_copy_front
467/// @brief copy num elements in the front of the buffer
468/// @param it_src : iterator from where begin to copy the elements
469/// @param mun : number of element to copy
470//-----------------------------------------------------------------------
471template <class Value_t, uint32_t Power2>
472template<class iter_t>
473void circular_buffer<Value_t, Power2>
474::push_copy_front(iter_t it_src, size_t num)
475{
476 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
477 "Incompatible iterator");
478 if (num == 0) return;
479#ifdef __BS_DEBUG
480 assert ( free_size() >= num);
481#endif
482 nelem += num;
483
484 first_pos = (first_pos + NMAX - num) & MASK;
485 size_t pos = first_pos;
486 for (size_t i = 0; i < num; ++i)
487 {
488 ptr[(pos++) & MASK] = *(it_src++);
489 };
490};
491//
492//------------------------------------------------------------------------
493// function : push_move_front
494/// @brief move num elements in the front of the buffer
495/// @param p1 : iterator from where begin to move the elements
496/// @param mun : number of element to move
497//-----------------------------------------------------------------------
498template <class Value_t, uint32_t Power2>
499template<class iter_t>
500void circular_buffer<Value_t, Power2>
501::push_move_front(iter_t it_src, size_t num)
502{
503 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
504 "Incompatible iterator");
505 if (num == 0) return;
506#ifdef __BS_DEBUG
507 assert ( free_size() >= num);
508#endif
509 nelem += num;
510 size_t pos = first_pos;
511 for (size_t i = 0; i < num; ++i)
512 {
513 ptr[(pos++) & MASK] = std::move(*(it_src++));
514 };
515};
516//
517//------------------------------------------------------------------------
518// function : push_copy_back
519/// @brief copy num elements in the back of the buffer
520/// @param p1 : iterator from where begin to copy the elements
521/// @param mun : number of element to copy
522//-----------------------------------------------------------------------
523template <class Value_t, uint32_t Power2>
524template<class iter_t>
525void circular_buffer<Value_t, Power2>
526::push_copy_back(iter_t it_src, size_t num)
527{
528 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
529 "Incompatible iterator");
530 if (num == 0) return;
531#ifdef __BS_DEBUG
532 assert ( free_size() >= num);
533#endif
534 size_t pos = first_pos + nelem;
535 nelem += num;
536 for (size_t i = 0; i < num; ++i)
537 {
538 ptr[(pos++) & MASK] = *(it_src++);
539 };
540};
541//
542//------------------------------------------------------------------------
543// function : push_move_back
544/// @brief move num elements in the back of the buffer
545/// @param p1 : iterator from where begin to move the elements
546/// @param mun : number of element to move
547//-----------------------------------------------------------------------
548template <class Value_t, uint32_t Power2>
549template<class iter_t>
550void circular_buffer<Value_t, Power2>
551::push_move_back(iter_t it_src, size_t num)
552{
553 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
554 "Incompatible iterator");
555 if (num == 0) return;
556#ifdef __BS_DEBUG
557 assert ( free_size() >= num);
558#endif
559 size_t pos = first_pos + nelem;
560 nelem += num;
561 for (size_t i = 0; i < num; ++i)
562 {
563 ptr[(pos++) & MASK] = std::move(*(it_src++));
564 };
565};
566
567//****************************************************************************
568};// End namespace util
569};// End namespace common
570};// End namespace sort
571};// End namespace boost
572//****************************************************************************
573#endif
574

source code of boost/libs/sort/include/boost/sort/common/util/circular_buffer.hpp