1 /** 2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef LIBPANDABASE_UTILS_RING_BUFFER_H 17 #define LIBPANDABASE_UTILS_RING_BUFFER_H 18 19 #include <array> 20 #include <limits> 21 22 #include "macros.h" 23 24 namespace panda { 25 template <class T, size_t N> 26 class RingBuffer; 27 28 template <class T, size_t N, bool is_const = false> 29 class RingBufferIterator { 30 public: 31 using iterator_category = std::bidirectional_iterator_tag; 32 using value_type = std::conditional_t<is_const, const T, T>; 33 using difference_type = ptrdiff_t; 34 using pointer = value_type *; 35 using reference = value_type &; 36 37 constexpr RingBufferIterator() noexcept = default; 38 constexpr RingBufferIterator(const RingBufferIterator &other) noexcept = default; 39 constexpr RingBufferIterator(RingBufferIterator &&other) noexcept = default; 40 41 constexpr RingBufferIterator &operator=(const RingBufferIterator &other) = default; 42 constexpr RingBufferIterator &operator=(RingBufferIterator &&other) = default; 43 44 ~RingBufferIterator() = default; 45 46 constexpr RingBufferIterator &operator++() noexcept 47 { 48 increment_index(); 49 return *this; 50 } 51 52 constexpr RingBufferIterator operator++(int) noexcept // NOLINT(cert-dcl21-cpp) 53 { 54 auto tmp = RingBufferIterator(*this); 55 increment_index(); 56 return tmp; 57 } 58 59 constexpr RingBufferIterator &operator--() noexcept 60 { 61 decrement_index(); 62 return *this; 63 } 64 65 constexpr RingBufferIterator operator--(int) noexcept // NOLINT(cert-dcl21-cpp) 66 { 67 auto tmp = RingBufferIterator(*this); 68 decrement_index(); 69 return tmp; 70 } 71 72 constexpr bool operator==(const RingBufferIterator &other) const noexcept 73 { 74 return index_ == other.index_; 75 } 76 77 constexpr bool operator!=(const RingBufferIterator &other) const noexcept 78 { 79 return index_ != other.index_; 80 } 81 82 constexpr reference operator*() const noexcept 83 { 84 return buffer_->operator[](index_); 85 } 86 87 constexpr pointer operator->() const noexcept 88 { 89 return static_cast<pointer>(&buffer_->operator[](index_)); 90 } 91 92 private: 93 using array_ptr = std::conditional_t<is_const, const std::array<T, N + 1> *, std::array<T, N + 1> *>; 94 RingBufferIterator(array_ptr buffer,size_t index)95 constexpr RingBufferIterator(array_ptr buffer, size_t index) : buffer_(buffer), index_(index) {} 96 increment_index()97 constexpr void increment_index() noexcept 98 { 99 index_ = (index_ == N) ? 0U : index_ + 1; 100 } 101 decrement_index()102 constexpr void decrement_index() noexcept 103 { 104 index_ = (index_ == 0U) ? N : index_ - 1; 105 } 106 107 friend class RingBuffer<T, N>; 108 109 array_ptr buffer_ = nullptr; 110 size_t index_ = 0U; 111 }; 112 113 /** 114 * Static circular buffer in STL-style 115 * @tparam T type of values in buffer 116 * @tparam N maximum count of elements in buffer 117 */ 118 template <class T, size_t N> 119 class RingBuffer { 120 public: 121 static_assert(N > 0U, "0 is invalid size for ring buffer"); 122 123 using value_type = T; 124 using pointer = value_type *; 125 using const_pointer = const value_type *; 126 using reference = value_type &; 127 using const_reference = const value_type &; 128 using size_type = size_t; 129 130 using iterator = RingBufferIterator<value_type, N>; 131 using const_iterator = RingBufferIterator<value_type, N, true>; 132 using reverse_iterator = std::reverse_iterator<iterator>; 133 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 134 135 constexpr RingBuffer() = default; 136 137 constexpr RingBuffer(const RingBuffer &other) = default; 138 constexpr RingBuffer(RingBuffer &&other) = default; 139 constexpr RingBuffer &operator=(const RingBuffer &other) = default; 140 constexpr RingBuffer &operator=(RingBuffer &&other) = default; 141 142 ~RingBuffer() = default; 143 144 /** 145 * Appends the given element value to the end of the ring buffer 146 * @param value the value of the element to append 147 */ push_back(const value_type & value)148 constexpr void push_back(const value_type &value) // NOLINT(readability-identifier-naming) 149 { 150 increment_tail(); 151 buffer_[tail_] = value; 152 } 153 154 /** 155 * Moves the given element value to the end of the ring buffer 156 * @param value the value of the element to append 157 */ push_back(value_type && value)158 constexpr void push_back(value_type &&value) // NOLINT(readability-identifier-naming) 159 { 160 emplace_back(std::move(value)); 161 } 162 163 /** 164 * Appends a new element to the end of the ring buffer 165 * 166 * @tparam Args arguments types for elemnt construction 167 * @param args arguments to forward to the constructor of the element 168 * @return a reference to the inserted element 169 */ 170 template <class... Args> emplace_back(Args...args)171 constexpr reference emplace_back(Args... args) // NOLINT(readability-identifier-naming) 172 { 173 increment_tail(); 174 buffer_[tail_] = value_type(std::forward<Args>(args)...); 175 return buffer_[tail_]; 176 } 177 178 /** 179 * Appends the given element value to the begin of the ring buffer 180 * @param value the value of the element to append 181 */ push_front(const value_type & value)182 constexpr void push_front(const value_type &value) // NOLINT(readability-identifier-naming) 183 { 184 decrement_head(); 185 buffer_[head_] = value; 186 } 187 188 /** 189 * Moves the given element value to the begin of the ring buffer 190 * @param value the value of the element to append 191 */ push_front(value_type && value)192 constexpr void push_front(value_type &&value) // NOLINT(readability-identifier-naming) 193 { 194 emplace_front(std::move(value)); 195 } 196 197 /** 198 * Appends a new element to the begin of the ring buffer 199 * 200 * @tparam Args arguments types for elemnt construction 201 * @param args arguments to forward to the constructor of the element 202 * @return a reference to the inserted element 203 */ 204 template <class... Args> emplace_front(Args...args)205 constexpr reference emplace_front(Args... args) // NOLINT(readability-identifier-naming) 206 { 207 decrement_head(); 208 buffer_[head_] = value_type(std::forward<Args>(args)...); 209 return buffer_[head_]; 210 } 211 212 /** 213 * Removes the last element of the ring buffer 214 */ pop_back()215 constexpr void pop_back() // NOLINT(readability-identifier-naming) 216 { 217 if constexpr (std::is_class_v<T>) { // NOLINT(readability-braces-around-statements) 218 buffer_[tail_].~value_type(); 219 } 220 decrement_buffer_index(tail_); 221 --current_size_; 222 } 223 224 /** 225 * Removes the first element of the ring buffer 226 */ pop_front()227 constexpr void pop_front() // NOLINT(readability-identifier-naming) 228 { 229 if constexpr (std::is_class_v<T>) { // NOLINT(readability-braces-around-statements) 230 buffer_[head_].~value_type(); 231 } 232 increment_buffer_index(head_); 233 --current_size_; 234 } 235 236 /** 237 * @return iterator to the first element 238 */ begin()239 constexpr iterator begin() noexcept // NOLINT(readability-identifier-naming) 240 { 241 return iterator(&buffer_, head_); 242 } 243 244 /** 245 * @return a reverse iterator to the first element of the revesred ring buffer 246 */ rbegin()247 constexpr reverse_iterator rbegin() noexcept // NOLINT(readability-identifier-naming) 248 { 249 return std::make_reverse_iterator(end()); 250 } 251 252 /** 253 * @return const context iterator to the first element 254 */ begin()255 constexpr const_iterator begin() const noexcept // NOLINT(readability-identifier-naming) 256 { 257 return const_iterator(&buffer_, head_); 258 } 259 260 /** 261 * @return a const context reverse iterator to the first element of the reversed ring buffer 262 */ rbegin()263 constexpr const_reverse_iterator rbegin() const noexcept // NOLINT(readability-identifier-naming) 264 { 265 return std::make_reverse_iterator(end()); 266 } 267 268 /** 269 * @return const iterator to the first element 270 */ cbegin()271 constexpr const_iterator cbegin() const noexcept // NOLINT(readability-identifier-naming) 272 { 273 return begin(); 274 } 275 276 /** 277 * @return a const reverse iterator to the first element of the reversed ring buffer 278 */ crbegin()279 constexpr const_reverse_iterator crbegin() const noexcept // NOLINT(readability-identifier-naming) 280 { 281 return rbegin(); 282 } 283 284 /** 285 * @return iterator to the element following the last element 286 */ end()287 constexpr iterator end() noexcept // NOLINT(readability-identifier-naming) 288 { 289 auto tmp = tail_; 290 increment_buffer_index(tmp); 291 return iterator(&buffer_, tmp); 292 } 293 294 /** 295 * @return a reverse iterator to the element following the last element of the reversed ring buffer 296 */ rend()297 constexpr reverse_iterator rend() noexcept // NOLINT(readability-identifier-naming) 298 { 299 return std::make_reverse_iterator(begin()); 300 } 301 302 /** 303 * @return const context iterator to the element following the last element 304 */ end()305 constexpr const_iterator end() const noexcept // NOLINT(readability-identifier-naming) 306 { 307 auto tmp = tail_; 308 increment_buffer_index(tmp); 309 return const_iterator(&buffer_, tmp); 310 } 311 312 /** 313 * @return a const context iterator to the element following the last element of the reversed ring buffer 314 */ rend()315 constexpr const_reverse_iterator rend() const noexcept // NOLINT(readability-identifier-naming) 316 { 317 return std::make_reverse_iterator(begin()); 318 } 319 320 /** 321 * @return const iterator to the element following the last element 322 */ cend()323 constexpr const_iterator cend() const noexcept // NOLINT(readability-identifier-naming) 324 { 325 return end(); 326 } 327 328 /** 329 * @return const iterator to the element following the last element of the reversed ring buffer 330 */ crend()331 constexpr const_reverse_iterator crend() const noexcept // NOLINT(readability-identifier-naming) 332 { 333 return rend(); 334 } 335 336 /** 337 * @return reference to first element in ring buffer 338 */ front()339 constexpr reference front() noexcept // NOLINT(readability-identifier-naming) 340 { 341 return buffer_[head_]; 342 } 343 344 /** 345 * @return const reference to first element in ring buffer 346 */ front()347 constexpr const_reference front() const noexcept // NOLINT(readability-identifier-naming) 348 { 349 return buffer_[head_]; 350 } 351 352 /** 353 * @return reference to last element in ring buffer 354 */ back()355 constexpr reference back() noexcept // NOLINT(readability-identifier-naming) 356 { 357 return buffer_[tail_]; 358 } 359 360 /** 361 * @return const reference to last element in ring buffer 362 */ back()363 constexpr const_reference back() const noexcept // NOLINT(readability-identifier-naming) 364 { 365 return buffer_[tail_]; 366 } 367 368 constexpr reference operator[](size_type index) noexcept 369 { 370 return buffer_[(head_ + index) % buffer_.size()]; 371 } 372 373 constexpr const_reference operator[](size_type index) const noexcept 374 { 375 return buffer_[(head_ + index) % buffer_.size()]; 376 } 377 378 /** 379 * @return true if buffer is empty and false otherwise 380 */ empty()381 [[nodiscard]] constexpr bool empty() const noexcept // NOLINT(readability-identifier-naming) 382 { 383 return size() == 0; 384 } 385 386 /** 387 * @return true if buffer is full (all buffer space is used) 388 */ full()389 [[nodiscard]] constexpr bool full() const noexcept // NOLINT(readability-identifier-naming) 390 { 391 return size() == capacity(); 392 } 393 394 /** 395 * @return current ring buffer size 396 */ size()397 constexpr size_type size() const noexcept // NOLINT(readability-identifier-naming) 398 { 399 return current_size_; 400 } 401 402 /** 403 * @return maximum ring buffer size 404 */ capacity()405 constexpr size_type capacity() const noexcept // NOLINT(readability-identifier-naming) 406 { 407 return N; 408 } 409 410 /** 411 * Erases all elements from the ring buffer. After this call, size() returns zero. 412 */ clear()413 constexpr void clear() noexcept // NOLINT(readability-identifier-naming) 414 { 415 if constexpr (std::is_class_v<T>) { // NOLINT(readability-braces-around-statements) 416 for (auto &element : *this) { 417 element.~value_type(); 418 } 419 } 420 head_ = 0; 421 tail_ = capacity(); 422 current_size_ = 0; 423 } 424 425 private: increment_tail()426 constexpr void increment_tail() noexcept 427 { 428 increment_buffer_index(tail_); 429 if (full()) { 430 increment_buffer_index(head_); 431 } else { 432 ++current_size_; 433 } 434 } 435 decrement_head()436 constexpr void decrement_head() noexcept 437 { 438 decrement_buffer_index(head_); 439 if (full()) { 440 decrement_buffer_index(tail_); 441 } else { 442 ++current_size_; 443 } 444 } 445 increment_buffer_index(size_type & index)446 constexpr void increment_buffer_index(size_type &index) const noexcept 447 { 448 index = (index + 1) % buffer_.size(); 449 } 450 decrement_buffer_index(size_type & index)451 constexpr void decrement_buffer_index(size_type &index) const noexcept 452 { 453 index = index == 0U ? N : index - 1; 454 } 455 456 std::array<T, N + 1> buffer_ = {}; 457 size_type head_ = 0U; 458 size_type tail_ = N; 459 size_type current_size_ = 0U; 460 }; 461 } // namespace panda 462 463 #endif // LIBPANDABASE_UTILS_RING_BUFFER_H 464