EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:46
0001 //---------------------------------------------------------------------------- 0002 /// @file circular_buffer.hpp 0003 /// @brief This file contains the implementation of the circular buffer 0004 /// 0005 /// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n 0006 /// Distributed under the Boost Software License, Version 1.0.\n 0007 /// ( See accompanyingfile LICENSE_1_0.txt or copy at 0008 /// http://www.boost.org/LICENSE_1_0.txt ) 0009 /// @version 0.1 0010 /// 0011 /// @remarks 0012 //----------------------------------------------------------------------------- 0013 #ifndef __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP 0014 #define __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP 0015 0016 #include <ciso646> 0017 #include <memory> 0018 #include <cassert> 0019 #include <exception> 0020 #include <boost/sort/common/util/algorithm.hpp> 0021 #include <boost/sort/common/util/traits.hpp> 0022 0023 namespace boost 0024 { 0025 namespace sort 0026 { 0027 namespace common 0028 { 0029 namespace util 0030 { 0031 0032 //--------------------------------------------------------------------------- 0033 /// @class circular_buffer 0034 /// @brief This class implement a circular buffer 0035 /// @remarks 0036 //--------------------------------------------------------------------------- 0037 template <class Value_t, uint32_t Power2 = 11> 0038 struct circular_buffer 0039 { 0040 //------------------------------------------------------------------------ 0041 // STATIC CHECK 0042 //------------------------------------------------------------------------ 0043 static_assert ( Power2 != 0, "Wrong Power2"); 0044 0045 //------------------------------------------------------------------------ 0046 // DEFINITIONS 0047 //------------------------------------------------------------------------ 0048 typedef Value_t value_t; 0049 0050 //------------------------------------------------------------------------ 0051 // VARIABLES 0052 //------------------------------------------------------------------------ 0053 const size_t NMAX = (size_t) 1 << Power2; 0054 const size_t MASK = (NMAX - 1); 0055 const size_t BLOCK_SIZE = NMAX >> 1; 0056 const size_t LOG_BLOCK = Power2 - 1; 0057 Value_t * ptr = nullptr; 0058 0059 //------------------------------------------------------------------------ 0060 // first and last are the position of the first and last elements 0061 // always are in the range [0, NMAX - 1] 0062 //------------------------------------------------------------------------ 0063 size_t nelem, first_pos; 0064 bool initialized; 0065 0066 // 0067 //------------------------------------------------------------------------ 0068 // function : circular_buffer 0069 /// @brief constructor of the class 0070 //----------------------------------------------------------------------- 0071 circular_buffer(void) 0072 : ptr(nullptr), nelem(0), first_pos(0), initialized(false) 0073 { 0074 ptr = static_cast <Value_t*> (std::malloc (NMAX * sizeof(Value_t))); 0075 if (ptr == nullptr) throw std::bad_alloc(); 0076 }; 0077 // 0078 //------------------------------------------------------------------------ 0079 // function : ~circular_buffer 0080 /// @brief destructor of the class 0081 //----------------------------------------------------------------------- 0082 ~circular_buffer() 0083 { 0084 if (initialized) 0085 { for (size_t i = 0; i < NMAX; ++i) (ptr + i)->~Value_t(); 0086 initialized = false; 0087 }; 0088 std::free(static_cast <void*> (ptr)); 0089 } 0090 ; 0091 // 0092 //------------------------------------------------------------------------ 0093 // function : initialize 0094 /// @brief : initialize the memory of the buffer from the uninitialize 0095 // memory obtained from the temporary buffer 0096 /// @param val : value used to initialize the memory 0097 //----------------------------------------------------------------------- 0098 void initialize(Value_t & val) 0099 { 0100 assert (initialized == false); 0101 ::new (static_cast<void*>(ptr)) Value_t(std::move(val)); 0102 for (size_t i = 1; i < NMAX; ++i) 0103 ::new (static_cast<void*>(ptr + i)) Value_t(std::move(ptr[i - 1])); 0104 val = std::move(ptr[NMAX - 1]); 0105 initialized = true; 0106 }; 0107 // 0108 //------------------------------------------------------------------------ 0109 // function : destroy_all 0110 /// @brief : destroy all the objects in the internal memory 0111 //----------------------------------------------------------------------- 0112 void destroy_all(void) { destroy(ptr, ptr + NMAX); }; 0113 // 0114 //------------------------------------------------------------------------ 0115 // function : get_buffer 0116 /// @brief return the internal memory of the circular buffer 0117 /// @return pointer to the internal memory of the buffer 0118 //----------------------------------------------------------------------- 0119 Value_t * get_buffer(void) { return ptr; }; 0120 // 0121 //------------------------------------------------------------------------ 0122 // function : empty 0123 /// @brief return if the buffer is empty 0124 /// @return true : empty 0125 //----------------------------------------------------------------------- 0126 bool empty(void) const {return (nelem == 0); }; 0127 // 0128 //------------------------------------------------------------------------ 0129 // function : full 0130 /// @brief return if the buffer is full 0131 /// @return true : full 0132 //----------------------------------------------------------------------- 0133 bool full(void) const { return (nelem == NMAX); }; 0134 // 0135 //------------------------------------------------------------------------ 0136 // function : size 0137 /// @brief return the number of elements stored in the buffer 0138 /// @return number of elements stored 0139 //----------------------------------------------------------------------- 0140 size_t size(void) const { return nelem;}; 0141 // 0142 //------------------------------------------------------------------------ 0143 // function : capacity 0144 /// @brief : return the maximun capacity of the buffer 0145 /// @return number of elements 0146 //----------------------------------------------------------------------- 0147 size_t capacity(void) const { return NMAX;}; 0148 // 0149 //------------------------------------------------------------------------ 0150 // function : free_size 0151 /// @brief return the free positions in the buffer 0152 /// @return number of elements 0153 //----------------------------------------------------------------------- 0154 size_t free_size(void) const { return (NMAX - nelem); }; 0155 // 0156 //------------------------------------------------------------------------ 0157 // function : clear 0158 /// @brief clear the buffer 0159 //----------------------------------------------------------------------- 0160 void clear(void) { nelem = first_pos = 0; }; 0161 // 0162 //------------------------------------------------------------------------ 0163 // function : front 0164 /// @brief return the first element of the buffer 0165 /// @return reference to the first value 0166 //----------------------------------------------------------------------- 0167 Value_t & front(void) 0168 { 0169 #ifdef __BS_DEBUG 0170 assert (nelem > 0); 0171 #endif 0172 return (ptr[first_pos]); 0173 }; 0174 // 0175 //------------------------------------------------------------------------ 0176 // function :front 0177 /// @brief return the first element of the buffer 0178 /// @return const reference to the first value 0179 //----------------------------------------------------------------------- 0180 const Value_t & front(void) const 0181 { 0182 #ifdef __BS_DEBUG 0183 assert ( nelem > 0 ); 0184 #endif 0185 return (ptr[first_pos]); 0186 }; 0187 // 0188 //------------------------------------------------------------------------ 0189 // function : back 0190 /// @brief reference to the last value of the buffer 0191 /// @return reference to the last value 0192 //----------------------------------------------------------------------- 0193 Value_t & back(void) 0194 { 0195 #ifdef __BS_DEBUG 0196 assert ( nelem > 0 ); 0197 #endif 0198 return (ptr[(first_pos + nelem - 1) & MASK]); 0199 }; 0200 // 0201 //------------------------------------------------------------------------ 0202 // function : back 0203 /// @brief reference to the last value of the buffer 0204 /// @return const reference to the last value 0205 //----------------------------------------------------------------------- 0206 const Value_t & back(void) const 0207 { 0208 #ifdef __BS_DEBUG 0209 assert ( nelem > 0 ); 0210 #endif 0211 return (ptr[(first_pos + nelem - 1) & MASK]); 0212 }; 0213 // 0214 //------------------------------------------------------------------------ 0215 // function : operator [] 0216 /// @brief positional access to the elements 0217 /// @param pos rquested 0218 /// @return reference to the element 0219 //----------------------------------------------------------------------- 0220 Value_t & operator[](uint32_t pos) 0221 { 0222 #ifdef __BS_DEBUG 0223 assert ( nelem > 0 ); 0224 #endif 0225 return ptr[(first_pos + pos) & MASK]; 0226 }; 0227 // 0228 //------------------------------------------------------------------------ 0229 // function : operator [] 0230 /// @brief positional access to the elements 0231 /// @param pos rquested 0232 /// @return const reference to the element 0233 //----------------------------------------------------------------------- 0234 const Value_t & operator[](uint32_t pos) const 0235 { 0236 0237 #ifdef __BS_DEBUG 0238 assert ( nelem > 0 ); 0239 #endif 0240 return ptr[(first_pos + pos) & MASK]; 0241 }; 0242 // 0243 //------------------------------------------------------------------------ 0244 // function : push_front 0245 /// @brief insert an element in the first position of the buffer 0246 /// @param val : const value to insert 0247 //----------------------------------------------------------------------- 0248 void push_front(const Value_t & val) 0249 { 0250 #ifdef __BS_DEBUG 0251 assert ( nelem != NMAX); 0252 #endif 0253 ++nelem; 0254 first_pos = ((first_pos + MASK) & MASK); 0255 ptr[first_pos] = val; 0256 0257 }; 0258 // 0259 //------------------------------------------------------------------------ 0260 // function : push_front 0261 /// @brief insert an element in the first position of the buffer 0262 /// @param val : rvalue to insert 0263 //----------------------------------------------------------------------- 0264 void push_front(Value_t && val) 0265 { 0266 #ifdef __BS_DEBUG 0267 assert ( nelem != NMAX); 0268 #endif 0269 ++nelem; 0270 first_pos = ((first_pos + MASK) & MASK); 0271 ptr[first_pos] = val; 0272 }; 0273 // 0274 //------------------------------------------------------------------------ 0275 // function : push_back 0276 /// @brief insert an element in the last position of the buffer 0277 /// @param val : value to insert 0278 //----------------------------------------------------------------------- 0279 void push_back(const Value_t & val) 0280 { 0281 #ifdef __BS_DEBUG 0282 assert ( nelem != NMAX); 0283 #endif 0284 ptr[(first_pos + (nelem++)) & MASK] = val; 0285 }; 0286 // 0287 //------------------------------------------------------------------------ 0288 // function : push_back 0289 /// @brief insert an element in the last position of the buffer 0290 /// @param val : value to insert 0291 //----------------------------------------------------------------------- 0292 void push_back(Value_t && val) 0293 { 0294 #ifdef __BS_DEBUG 0295 assert ( nelem != NMAX); 0296 #endif 0297 ptr[(first_pos + (nelem++)) & MASK] = std::move(val); 0298 }; 0299 // 0300 //------------------------------------------------------------------------ 0301 // function : pop_front 0302 /// @brief remove the first element of the buffer 0303 //----------------------------------------------------------------------- 0304 void pop_front(void) 0305 { 0306 #ifdef __BS_DEBUG 0307 assert ( nelem > 0 ); 0308 #endif 0309 --nelem; 0310 (++first_pos) &= MASK; 0311 }; 0312 // 0313 //------------------------------------------------------------------------ 0314 // function : pop_back 0315 /// @brief remove the last element of the buffer 0316 //----------------------------------------------------------------------- 0317 void pop_back(void) 0318 { 0319 #ifdef __BS_DEBUG 0320 assert ( nelem > 0 ); 0321 #endif 0322 --nelem; 0323 }; 0324 0325 template<class iter_t> 0326 void pop_copy_front(iter_t it_dest, size_t num); 0327 0328 template<class iter_t> 0329 void pop_move_front(iter_t it_dest, size_t num); 0330 0331 template<class iter_t> 0332 void pop_copy_back(iter_t it_dest, size_t num); 0333 0334 template<class iter_t> 0335 void pop_move_back(iter_t it_dest, size_t num); 0336 0337 template<class iter_t> 0338 void push_copy_front(iter_t it_src, size_t num); 0339 0340 template<class iter_t> 0341 void push_move_front(iter_t it_src, size_t num); 0342 0343 template<class iter_t> 0344 void push_copy_back(iter_t it_src, size_t num); 0345 0346 template<class iter_t> 0347 void push_move_back(iter_t it_src, size_t num); 0348 0349 //--------------------------------------------------------------------------- 0350 };// End of class circular_buffer 0351 //--------------------------------------------------------------------------- 0352 // 0353 // 0354 //############################################################################ 0355 // ## 0356 // N O N I N L I N E F U N C T I O N S ## 0357 // ## 0358 //############################################################################ 0359 // 0360 //------------------------------------------------------------------------ 0361 // function : pop_copy_front 0362 /// @brief copy and delete num elements from the front of the buffer 0363 /// @param it_dest : iterator to the first position where copy the elements 0364 /// @param num : number of elements to copy 0365 //----------------------------------------------------------------------- 0366 template <class Value_t, uint32_t Power2> 0367 template<class iter_t> 0368 void circular_buffer<Value_t, Power2> 0369 ::pop_copy_front(iter_t it_dest, size_t num) 0370 { 0371 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0372 "Incompatible iterator"); 0373 if (num == 0) return; 0374 #ifdef __BS_DEBUG 0375 assert ( num <= nelem); 0376 #endif 0377 nelem -= num; 0378 size_t pos = first_pos; 0379 first_pos = (first_pos + num) & MASK; 0380 for (size_t i = 0; i < num; ++i) 0381 { 0382 *(it_dest++) = ptr[pos++ & MASK]; 0383 }; 0384 first_pos &= MASK; 0385 }; 0386 // 0387 //------------------------------------------------------------------------ 0388 // function : pop_move_front 0389 /// @brief move num elements from the front of the buffer to the place 0390 // pointed by it_dest 0391 /// @param it_dest : iterator to the first position where move the elements 0392 /// @param num : number of elements to move 0393 //----------------------------------------------------------------------- 0394 template <class Value_t, uint32_t Power2> 0395 template<class iter_t> 0396 void circular_buffer<Value_t, Power2> 0397 :: pop_move_front(iter_t it_dest, size_t num) 0398 { 0399 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0400 "Incompatible iterator"); 0401 if (num == 0) return; 0402 #ifdef __BS_DEBUG 0403 assert ( num <= nelem); 0404 #endif 0405 nelem -= num; 0406 size_t pos = first_pos; 0407 first_pos = (first_pos + num) & MASK; 0408 for (size_t i = 0; i < num; ++i) 0409 { 0410 *(it_dest++) = std::move(ptr[pos++ & MASK]); 0411 }; 0412 first_pos &= MASK; 0413 }; 0414 // 0415 //------------------------------------------------------------------------ 0416 // function : pop_copy_back 0417 /// @brief copy and delete num elements from the back of the buffer 0418 /// @param p1 : iterator where begin to copy the elements 0419 /// @param num : number of elements to copy 0420 //----------------------------------------------------------------------- 0421 template <class Value_t, uint32_t Power2> 0422 template<class iter_t> 0423 void circular_buffer<Value_t, Power2> 0424 ::pop_copy_back(iter_t it_dest, size_t num) 0425 { 0426 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0427 "Incompatible iterator"); 0428 if (num == 0) return; 0429 #ifdef __BS_DEBUG 0430 assert ( num <= nelem); 0431 #endif 0432 nelem -= num; 0433 size_t pos = (first_pos + nelem) & MASK; 0434 for (size_t i = 0; i < num; ++i) 0435 { 0436 *(it_dest++) = ptr[pos++ & MASK]; 0437 }; 0438 }; 0439 // 0440 //------------------------------------------------------------------------ 0441 // function : pop_move_back 0442 /// @brief move and delete num elements from the back of the buffer 0443 /// @param p1 : iterator where begin to move the elements 0444 /// @param num : number of elements to move 0445 //----------------------------------------------------------------------- 0446 template <class Value_t, uint32_t Power2> 0447 template<class iter_t> 0448 void circular_buffer<Value_t, Power2> 0449 ::pop_move_back(iter_t it_dest, size_t num) 0450 { 0451 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0452 "Incompatible iterator"); 0453 if (num == 0) return; 0454 #ifdef __BS_DEBUG 0455 assert ( num <= nelem); 0456 #endif 0457 nelem -= num; 0458 size_t pos = (first_pos + nelem) & MASK; 0459 for (size_t i = 0; i < num; ++i) 0460 { 0461 *(it_dest++) = std::move(ptr[pos++ & MASK]); 0462 }; 0463 }; 0464 // 0465 //------------------------------------------------------------------------ 0466 // function : push_copy_front 0467 /// @brief copy num elements in the front of the buffer 0468 /// @param it_src : iterator from where begin to copy the elements 0469 /// @param mun : number of element to copy 0470 //----------------------------------------------------------------------- 0471 template <class Value_t, uint32_t Power2> 0472 template<class iter_t> 0473 void circular_buffer<Value_t, Power2> 0474 ::push_copy_front(iter_t it_src, size_t num) 0475 { 0476 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0477 "Incompatible iterator"); 0478 if (num == 0) return; 0479 #ifdef __BS_DEBUG 0480 assert ( free_size() >= num); 0481 #endif 0482 nelem += num; 0483 0484 first_pos = (first_pos + NMAX - num) & MASK; 0485 size_t pos = first_pos; 0486 for (size_t i = 0; i < num; ++i) 0487 { 0488 ptr[(pos++) & MASK] = *(it_src++); 0489 }; 0490 }; 0491 // 0492 //------------------------------------------------------------------------ 0493 // function : push_move_front 0494 /// @brief move num elements in the front of the buffer 0495 /// @param p1 : iterator from where begin to move the elements 0496 /// @param mun : number of element to move 0497 //----------------------------------------------------------------------- 0498 template <class Value_t, uint32_t Power2> 0499 template<class iter_t> 0500 void circular_buffer<Value_t, Power2> 0501 ::push_move_front(iter_t it_src, size_t num) 0502 { 0503 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0504 "Incompatible iterator"); 0505 if (num == 0) return; 0506 #ifdef __BS_DEBUG 0507 assert ( free_size() >= num); 0508 #endif 0509 nelem += num; 0510 size_t pos = first_pos; 0511 for (size_t i = 0; i < num; ++i) 0512 { 0513 ptr[(pos++) & MASK] = std::move(*(it_src++)); 0514 }; 0515 }; 0516 // 0517 //------------------------------------------------------------------------ 0518 // function : push_copy_back 0519 /// @brief copy num elements in the back of the buffer 0520 /// @param p1 : iterator from where begin to copy the elements 0521 /// @param mun : number of element to copy 0522 //----------------------------------------------------------------------- 0523 template <class Value_t, uint32_t Power2> 0524 template<class iter_t> 0525 void circular_buffer<Value_t, Power2> 0526 ::push_copy_back(iter_t it_src, size_t num) 0527 { 0528 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0529 "Incompatible iterator"); 0530 if (num == 0) return; 0531 #ifdef __BS_DEBUG 0532 assert ( free_size() >= num); 0533 #endif 0534 size_t pos = first_pos + nelem; 0535 nelem += num; 0536 for (size_t i = 0; i < num; ++i) 0537 { 0538 ptr[(pos++) & MASK] = *(it_src++); 0539 }; 0540 }; 0541 // 0542 //------------------------------------------------------------------------ 0543 // function : push_move_back 0544 /// @brief move num elements in the back of the buffer 0545 /// @param p1 : iterator from where begin to move the elements 0546 /// @param mun : number of element to move 0547 //----------------------------------------------------------------------- 0548 template <class Value_t, uint32_t Power2> 0549 template<class iter_t> 0550 void circular_buffer<Value_t, Power2> 0551 ::push_move_back(iter_t it_src, size_t num) 0552 { 0553 static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value, 0554 "Incompatible iterator"); 0555 if (num == 0) return; 0556 #ifdef __BS_DEBUG 0557 assert ( free_size() >= num); 0558 #endif 0559 size_t pos = first_pos + nelem; 0560 nelem += num; 0561 for (size_t i = 0; i < num; ++i) 0562 { 0563 ptr[(pos++) & MASK] = std::move(*(it_src++)); 0564 }; 0565 }; 0566 0567 //**************************************************************************** 0568 };// End namespace util 0569 };// End namespace common 0570 };// End namespace sort 0571 };// End namespace boost 0572 //**************************************************************************** 0573 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|