ceph/src/seastar/include/seastar/core/circular_buffer_fixed_capacity.hh

   1 /*
   2  * This file is open source software, licensed to you under the terms
   3  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   4  * distributed with this work for additional information regarding copyright
   5  * ownership.  You may not use this file except in compliance with the License.
   6  *
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing,
  12  * software distributed under the License is distributed on an
  13  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14  * KIND, either express or implied.  See the License for the
  15  * specific language governing permissions and limitations
  16  * under the License.
  17  */
  18 /*
  19  * Copyright (C) 2017 ScyllaDB
  20  */
  21
  22 #pragma once
  23
  24 // A fixed capacity double-ended queue container that can be efficiently
  25 // extended (and shrunk) from both ends.  Implementation is a single
  26 // storage vector.
  27 //
  28 // Similar to libstdc++'s std::deque, except that it uses a single level
  29 // store, and so is more efficient for simple stored items.
  30
  31 #include <type_traits>
  32 #include <cstddef>
  33 #include <iterator>
  34 #include <utility>
  35
  36
  37 /// \file
  38
  39 namespace seastar {
  40
  41 /// A fixed-capacity container (like boost::static_vector) that can insert
  42 /// and remove at both ends (like std::deque). Does not allocate.
  43 ///
  44 /// Does not perform overflow checking when size exceeds capacity.
  45 ///
  46 /// \tparam T type of objects stored in the container; must be noexcept move enabled
  47 /// \tparam Capacity maximum number of objects that can be stored in the container; must be a power of 2
  48 template <typename T, size_t Capacity>
  49 class circular_buffer_fixed_capacity {
  50     size_t _begin = 0;
  51     size_t _end = 0;
  52     union maybe_storage {
  53         T data;
  54         maybe_storage() noexcept {}
  55         ~maybe_storage() {}
  56     };
  57     maybe_storage _storage[Capacity];
  58 private:
  59     static size_t mask(size_t idx) { return idx % Capacity; }
  60     T* obj(size_t idx) { return &_storage[mask(idx)].data; }
  61     const T* obj(size_t idx) const { return &_storage[mask(idx)].data; }
  62 public:
  63     static_assert((Capacity & (Capacity - 1)) == 0, "capacity must be a power of two");
  64     static_assert(std::is_nothrow_move_constructible<T>::value && std::is_nothrow_move_assignable<T>::value,
  65             "circular_buffer_fixed_capacity only supports nothrow-move value types");
  66     using value_type = T;
  67     using size_type = size_t;
  68     using reference = T&;
  69     using pointer = T*;
  70     using const_reference = const T&;
  71     using const_pointer = const T*;
  72     using difference_type = ssize_t;
  73 public:
  74     template <typename ValueType>
  75     class cbiterator {
  76         using holder = std::conditional_t<std::is_const<ValueType>::value, const maybe_storage, maybe_storage>;
  77         holder* _start;
  78         size_t _idx;
  79     private:
  80         cbiterator(holder* start, size_t idx) noexcept : _start(start), _idx(idx) {}
  81     public:
  82         using iterator_category = std::random_access_iterator_tag;
  83         using value_type = ValueType;
  84         using difference_type = ssize_t;
  85         using pointer = ValueType*;
  86         using reference = ValueType&;
  87     public:
  88         cbiterator();
  89         ValueType& operator*() const { return _start[mask(_idx)].data; }
  90         ValueType* operator->() const { return &operator*(); }
  91         // prefix
  92         cbiterator& operator++() {
  93             ++_idx;
  94             return *this;
  95         }
  96         // postfix
  97         cbiterator operator++(int) {
  98             auto v = *this;
  99             ++_idx;
 100             return v;
 101         }
 102         // prefix
 103         cbiterator& operator--() {
 104             --_idx;
 105             return *this;
 106         }
 107         // postfix
 108         cbiterator operator--(int) {
 109             auto v = *this;
 110             --_idx;
 111             return v;
 112         }
 113         cbiterator operator+(difference_type n) const {
 114             return cbiterator{_start, _idx + n};
 115         }
 116         friend cbiterator operator+(difference_type n, cbiterator i) {
 117             return i + n;
 118         }
 119         cbiterator operator-(difference_type n) const {
 120             return cbiterator{_start, _idx - n};
 121         }
 122         cbiterator& operator+=(difference_type n) {
 123             _idx += n;
 124             return *this;
 125         }
 126         cbiterator& operator-=(difference_type n) {
 127             _idx -= n;
 128             return *this;
 129         }
 130         bool operator==(const cbiterator& rhs) const {
 131             return _idx == rhs._idx;
 132         }
 133         bool operator!=(const cbiterator& rhs) const {
 134             return _idx != rhs._idx;
 135         }
 136         bool operator<(const cbiterator& rhs) const {
 137             return ssize_t(_idx - rhs._idx) < 0;
 138         }
 139         bool operator>(const cbiterator& rhs) const {
 140             return ssize_t(_idx - rhs._idx) > 0;
 141         }
 142         bool operator<=(const cbiterator& rhs) const {
 143             return ssize_t(_idx - rhs._idx) <= 0;
 144         }
 145         bool operator>=(const cbiterator& rhs) const {
 146             return ssize_t(_idx - rhs._idx) >= 0;
 147         }
 148         difference_type operator-(const cbiterator& rhs) const {
 149             return _idx - rhs._idx;
 150         }
 151         friend class circular_buffer_fixed_capacity;
 152     };
 153 public:
 154     using iterator = cbiterator<T>;
 155     using const_iterator = cbiterator<const T>;
 156 public:
 157     circular_buffer_fixed_capacity() = default;
 158     circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept;
 159     ~circular_buffer_fixed_capacity();
 160     circular_buffer_fixed_capacity& operator=(circular_buffer_fixed_capacity&& x) noexcept;
 161     void push_front(const T& data);
 162     void push_front(T&& data);
 163     template <typename... A>
 164     T& emplace_front(A&&... args);
 165     void push_back(const T& data);
 166     void push_back(T&& data);
 167     template <typename... A>
 168     T& emplace_back(A&&... args);
 169     T& front();
 170     T& back();
 171     void pop_front();
 172     void pop_back();
 173     bool empty() const;
 174     size_t size() const;
 175     size_t capacity() const;
 176     T& operator[](size_t idx);
 177     void clear();
 178     iterator begin() {
 179         return iterator(_storage, _begin);
 180     }
 181     const_iterator begin() const {
 182         return const_iterator(_storage, _begin);
 183     }
 184     iterator end() {
 185         return iterator(_storage, _end);
 186     }
 187     const_iterator end() const {
 188         return const_iterator(_storage, _end);
 189     }
 190     const_iterator cbegin() const {
 191         return const_iterator(_storage, _begin);
 192     }
 193     const_iterator cend() const {
 194         return const_iterator(_storage, _end);
 195     }
 196     iterator erase(iterator first, iterator last);
 197 };
 198
 199 template <typename T, size_t Capacity>
 200 inline
 201 bool
 202 circular_buffer_fixed_capacity<T, Capacity>::empty() const {
 203     return _begin == _end;
 204 }
 205
 206 template <typename T, size_t Capacity>
 207 inline
 208 size_t
 209 circular_buffer_fixed_capacity<T, Capacity>::size() const {
 210     return _end - _begin;
 211 }
 212
 213 template <typename T, size_t Capacity>
 214 inline
 215 size_t
 216 circular_buffer_fixed_capacity<T, Capacity>::capacity() const {
 217     return Capacity;
 218 }
 219
 220 template <typename T, size_t Capacity>
 221 inline
 222 circular_buffer_fixed_capacity<T, Capacity>::circular_buffer_fixed_capacity(circular_buffer_fixed_capacity&& x) noexcept
 223         : _begin(std::exchange(x._begin, 0)), _end(std::exchange(x._end, 0)) {
 224     for (auto i = _begin; i != _end; ++i) {
 225         new (&_storage[i].data) T(std::move(x._storage[i].data));
 226     }
 227 }
 228
 229 template <typename T, size_t Capacity>
 230 inline
 231 circular_buffer_fixed_capacity<T, Capacity>&
 232 circular_buffer_fixed_capacity<T, Capacity>::operator=(circular_buffer_fixed_capacity&& x) noexcept {
 233     if (this != &x) {
 234         this->~circular_buffer_fixed_capacity();
 235         new (this) circular_buffer_fixed_capacity(std::move(x));
 236     }
 237     return *this;
 238 }
 239
 240 template <typename T, size_t Capacity>
 241 inline
 242 circular_buffer_fixed_capacity<T, Capacity>::~circular_buffer_fixed_capacity() {
 243     for (auto i = _begin; i != _end; ++i) {
 244         _storage[i].data.~T();
 245     }
 246 }
 247
 248 template <typename T, size_t Capacity>
 249 inline
 250 void
 251 circular_buffer_fixed_capacity<T, Capacity>::push_front(const T& data) {
 252     new (obj(_begin - 1)) T(data);
 253     --_begin;
 254 }
 255
 256 template <typename T, size_t Capacity>
 257 inline
 258 void
 259 circular_buffer_fixed_capacity<T, Capacity>::push_front(T&& data) {
 260     new (obj(_begin - 1)) T(std::move(data));
 261     --_begin;
 262 }
 263
 264 template <typename T, size_t Capacity>
 265 template <typename... Args>
 266 inline
 267 T&
 268 circular_buffer_fixed_capacity<T, Capacity>::emplace_front(Args&&... args) {
 269     auto p = new (obj(_begin - 1)) T(std::forward<Args>(args)...);
 270     --_begin;
 271     return *p;
 272 }
 273
 274 template <typename T, size_t Capacity>
 275 inline
 276 void
 277 circular_buffer_fixed_capacity<T, Capacity>::push_back(const T& data) {
 278     new (obj(_end)) T(data);
 279     ++_end;
 280 }
 281
 282 template <typename T, size_t Capacity>
 283 inline
 284 void
 285 circular_buffer_fixed_capacity<T, Capacity>::push_back(T&& data) {
 286     new (obj(_end)) T(std::move(data));
 287     ++_end;
 288 }
 289
 290 template <typename T, size_t Capacity>
 291 template <typename... Args>
 292 inline
 293 T&
 294 circular_buffer_fixed_capacity<T, Capacity>::emplace_back(Args&&... args) {
 295     auto p = new (obj(_end)) T(std::forward<Args>(args)...);
 296     ++_end;
 297     return *p;
 298 }
 299
 300 template <typename T, size_t Capacity>
 301 inline
 302 T&
 303 circular_buffer_fixed_capacity<T, Capacity>::front() {
 304     return *obj(_begin);
 305 }
 306
 307 template <typename T, size_t Capacity>
 308 inline
 309 T&
 310 circular_buffer_fixed_capacity<T, Capacity>::back() {
 311     return *obj(_end - 1);
 312 }
 313
 314 template <typename T, size_t Capacity>
 315 inline
 316 void
 317 circular_buffer_fixed_capacity<T, Capacity>::pop_front() {
 318     obj(_begin)->~T();
 319     ++_begin;
 320 }
 321
 322 template <typename T, size_t Capacity>
 323 inline
 324 void
 325 circular_buffer_fixed_capacity<T, Capacity>::pop_back() {
 326     obj(_end - 1)->~T();
 327     --_end;
 328 }
 329
 330 template <typename T, size_t Capacity>
 331 inline
 332 T&
 333 circular_buffer_fixed_capacity<T, Capacity>::operator[](size_t idx) {
 334     return *obj(_begin + idx);
 335 }
 336
 337 template <typename T, size_t Capacity>
 338 inline
 339 typename circular_buffer_fixed_capacity<T, Capacity>::iterator
 340 circular_buffer_fixed_capacity<T, Capacity>::erase(iterator first, iterator last) {
 341     static_assert(std::is_nothrow_move_assignable<T>::value, "erase() assumes move assignment does not throw");
 342     if (first == last) {
 343         return last;
 344     }
 345     // Move to the left or right depending on which would result in least amount of moves.
 346     // This also guarantees that iterators will be stable when removing from either front or back.
 347     if (std::distance(begin(), first) < std::distance(last, end())) {
 348         auto new_start = std::move_backward(begin(), first, last);
 349         auto i = begin();
 350         while (i < new_start) {
 351             *i++.~T();
 352         }
 353         _begin = new_start.idx;
 354         return last;
 355     } else {
 356         auto new_end = std::move(last, end(), first);
 357         auto i = new_end;
 358         auto e = end();
 359         while (i < e) {
 360             *i++.~T();
 361         }
 362         _end = new_end.idx;
 363         return first;
 364     }
 365 }
 366
 367 template <typename T, size_t Capacity>
 368 inline
 369 void
 370 circular_buffer_fixed_capacity<T, Capacity>::clear() {
 371     for (auto i = _begin; i != _end; ++i) {
 372         obj(i)->~T();
 373     }
 374     _begin = _end = 0;
 375 }
 376
 377 }
 378