ceph/src/seastar/include/seastar/core/circular_buffer.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) 2014 Cloudius Systems, Ltd.
  20  */
  21
  22 #pragma once
  23
  24 #include <seastar/core/transfer.hh>
  25 #include <seastar/core/bitops.hh>
  26 #include <memory>
  27 #include <algorithm>
  28
  29 namespace seastar {
  30
  31 /// A growable double-ended queue container that can be efficiently
  32 /// extended (and shrunk) from both ends. Implementation is a single
  33 /// storage vector.
  34 ///
  35 /// Similar to libstdc++'s std::deque, except that it uses a single
  36 /// level store, and so is more efficient for simple stored items.
  37 /// Similar to boost::circular_buffer_space_optimized, except it uses
  38 /// uninitialized storage for unoccupied elements (and thus move/copy
  39 /// constructors instead of move/copy assignments, which are less
  40 /// efficient).
  41 ///
  42 /// The storage of the circular_buffer is expanded automatically in
  43 /// exponential increments.
  44 /// When adding new elements:
  45 /// * if size + 1 > capacity: all iterators and references are
  46 ///     invalidated,
  47 /// * otherwise only the begin() or end() iterator is invalidated:
  48 ///     * push_front() and emplace_front() will invalidate begin() and
  49 ///     * push_back() and emplace_back() will invalidate end().
  50 ///
  51 /// Removing elements never invalidates any references and only
  52 /// invalidates begin() or end() iterators:
  53 ///     * pop_front() will invalidate begin() and
  54 ///     * pop_back() will invalidate end().
  55 ///
  56 /// reserve() may also invalidate all iterators and references.
  57 template <typename T, typename Alloc = std::allocator<T>>
  58 class circular_buffer {
  59     struct impl : Alloc {
  60         T* storage = nullptr;
  61         // begin, end interpreted (mod capacity)
  62         size_t begin = 0;
  63         size_t end = 0;
  64         size_t capacity = 0;
  65     };
  66     impl _impl;
  67 public:
  68     using value_type = T;
  69     using size_type = size_t;
  70     using reference = T&;
  71     using pointer = T*;
  72     using const_reference = const T&;
  73     using const_pointer = const T*;
  74 public:
  75     circular_buffer() = default;
  76     circular_buffer(circular_buffer&& X) noexcept;
  77     circular_buffer(const circular_buffer& X) = delete;
  78     ~circular_buffer();
  79     circular_buffer& operator=(const circular_buffer&) = delete;
  80     circular_buffer& operator=(circular_buffer&& b) noexcept;
  81     void push_front(const T& data);
  82     void push_front(T&& data);
  83     template <typename... A>
  84     void emplace_front(A&&... args);
  85     void push_back(const T& data);
  86     void push_back(T&& data);
  87     template <typename... A>
  88     void emplace_back(A&&... args);
  89     T& front();
  90     const T& front() const;
  91     T& back();
  92     const T& back() const;
  93     void pop_front();
  94     void pop_back();
  95     bool empty() const;
  96     size_t size() const;
  97     size_t capacity() const;
  98     void reserve(size_t);
  99     void clear();
 100     T& operator[](size_t idx);
 101     const T& operator[](size_t idx) const;
 102     template <typename Func>
 103     void for_each(Func func);
 104     // access an element, may return wrong or destroyed element
 105     // only useful if you do not rely on data accuracy (e.g. prefetch)
 106     T& access_element_unsafe(size_t idx);
 107 private:
 108     void expand();
 109     void expand(size_t);
 110     void maybe_expand(size_t nr = 1);
 111     size_t mask(size_t idx) const;
 112
 113     template<typename CB, typename ValueType>
 114     struct cbiterator : std::iterator<std::random_access_iterator_tag, ValueType> {
 115         typedef std::iterator<std::random_access_iterator_tag, ValueType> super_t;
 116
 117         ValueType& operator*() const { return cb->_impl.storage[cb->mask(idx)]; }
 118         ValueType* operator->() const { return &cb->_impl.storage[cb->mask(idx)]; }
 119         // prefix
 120         cbiterator<CB, ValueType>& operator++() {
 121             idx++;
 122             return *this;
 123         }
 124         // postfix
 125         cbiterator<CB, ValueType> operator++(int unused) {
 126             auto v = *this;
 127             idx++;
 128             return v;
 129         }
 130         // prefix
 131         cbiterator<CB, ValueType>& operator--() {
 132             idx--;
 133             return *this;
 134         }
 135         // postfix
 136         cbiterator<CB, ValueType> operator--(int unused) {
 137             auto v = *this;
 138             idx--;
 139             return v;
 140         }
 141         cbiterator<CB, ValueType> operator+(typename super_t::difference_type n) const {
 142             return cbiterator<CB, ValueType>(cb, idx + n);
 143         }
 144         cbiterator<CB, ValueType> operator-(typename super_t::difference_type n) const {
 145             return cbiterator<CB, ValueType>(cb, idx - n);
 146         }
 147         cbiterator<CB, ValueType>& operator+=(typename super_t::difference_type n) {
 148             idx += n;
 149             return *this;
 150         }
 151         cbiterator<CB, ValueType>& operator-=(typename super_t::difference_type n) {
 152             idx -= n;
 153             return *this;
 154         }
 155         bool operator==(const cbiterator<CB, ValueType>& rhs) const {
 156             return idx == rhs.idx;
 157         }
 158         bool operator!=(const cbiterator<CB, ValueType>& rhs) const {
 159             return idx != rhs.idx;
 160         }
 161         bool operator<(const cbiterator<CB, ValueType>& rhs) const {
 162             return idx < rhs.idx;
 163         }
 164         bool operator>(const cbiterator<CB, ValueType>& rhs) const {
 165             return idx > rhs.idx;
 166         }
 167         bool operator>=(const cbiterator<CB, ValueType>& rhs) const {
 168             return idx >= rhs.idx;
 169         }
 170         bool operator<=(const cbiterator<CB, ValueType>& rhs) const {
 171             return idx <= rhs.idx;
 172         }
 173        typename super_t::difference_type operator-(const cbiterator<CB, ValueType>& rhs) const {
 174             return idx - rhs.idx;
 175         }
 176     private:
 177         CB* cb;
 178         size_t idx;
 179         cbiterator<CB, ValueType>(CB* b, size_t i) : cb(b), idx(i) {}
 180         friend class circular_buffer;
 181     };
 182     friend class iterator;
 183
 184 public:
 185     typedef cbiterator<circular_buffer, T> iterator;
 186     typedef cbiterator<const circular_buffer, const T> const_iterator;
 187
 188     iterator begin() {
 189         return iterator(this, _impl.begin);
 190     }
 191     const_iterator begin() const {
 192         return const_iterator(this, _impl.begin);
 193     }
 194     iterator end() {
 195         return iterator(this, _impl.end);
 196     }
 197     const_iterator end() const {
 198         return const_iterator(this, _impl.end);
 199     }
 200     const_iterator cbegin() const {
 201         return const_iterator(this, _impl.begin);
 202     }
 203     const_iterator cend() const {
 204         return const_iterator(this, _impl.end);
 205     }
 206     iterator erase(iterator first, iterator last);
 207 };
 208
 209 template <typename T, typename Alloc>
 210 inline
 211 size_t
 212 circular_buffer<T, Alloc>::mask(size_t idx) const {
 213     return idx & (_impl.capacity - 1);
 214 }
 215
 216 template <typename T, typename Alloc>
 217 inline
 218 bool
 219 circular_buffer<T, Alloc>::empty() const {
 220     return _impl.begin == _impl.end;
 221 }
 222
 223 template <typename T, typename Alloc>
 224 inline
 225 size_t
 226 circular_buffer<T, Alloc>::size() const {
 227     return _impl.end - _impl.begin;
 228 }
 229
 230 template <typename T, typename Alloc>
 231 inline
 232 size_t
 233 circular_buffer<T, Alloc>::capacity() const {
 234     return _impl.capacity;
 235 }
 236
 237 template <typename T, typename Alloc>
 238 inline
 239 void
 240 circular_buffer<T, Alloc>::reserve(size_t size) {
 241     if (capacity() < size) {
 242         // Make sure that the new capacity is a power of two.
 243         expand(size_t(1) << log2ceil(size));
 244     }
 245 }
 246
 247 template <typename T, typename Alloc>
 248 inline
 249 void
 250 circular_buffer<T, Alloc>::clear() {
 251     erase(begin(), end());
 252 }
 253
 254 template <typename T, typename Alloc>
 255 inline
 256 circular_buffer<T, Alloc>::circular_buffer(circular_buffer&& x) noexcept
 257     : _impl(std::move(x._impl)) {
 258     x._impl = {};
 259 }
 260
 261 template <typename T, typename Alloc>
 262 inline
 263 circular_buffer<T, Alloc>& circular_buffer<T, Alloc>::operator=(circular_buffer&& x) noexcept {
 264     if (this != &x) {
 265         this->~circular_buffer();
 266         new (this) circular_buffer(std::move(x));
 267     }
 268     return *this;
 269 }
 270
 271 template <typename T, typename Alloc>
 272 template <typename Func>
 273 inline
 274 void
 275 circular_buffer<T, Alloc>::for_each(Func func) {
 276     auto s = _impl.storage;
 277     auto m = _impl.capacity - 1;
 278     for (auto i = _impl.begin; i != _impl.end; ++i) {
 279         func(s[i & m]);
 280     }
 281 }
 282
 283 template <typename T, typename Alloc>
 284 inline
 285 circular_buffer<T, Alloc>::~circular_buffer() {
 286     for_each([this] (T& obj) {
 287         _impl.destroy(&obj);
 288     });
 289     _impl.deallocate(_impl.storage, _impl.capacity);
 290 }
 291
 292 template <typename T, typename Alloc>
 293 void
 294 circular_buffer<T, Alloc>::expand() {
 295     expand(std::max<size_t>(_impl.capacity * 2, 1));
 296 }
 297
 298 template <typename T, typename Alloc>
 299 void
 300 circular_buffer<T, Alloc>::expand(size_t new_cap) {
 301     auto new_storage = _impl.allocate(new_cap);
 302     auto p = new_storage;
 303     try {
 304         for_each([this, &p] (T& obj) {
 305             transfer_pass1(_impl, &obj, p);
 306             p++;
 307         });
 308     } catch (...) {
 309         while (p != new_storage) {
 310             _impl.destroy(--p);
 311         }
 312         _impl.deallocate(new_storage, new_cap);
 313         throw;
 314     }
 315     p = new_storage;
 316     for_each([this, &p] (T& obj) {
 317         transfer_pass2(_impl, &obj, p++);
 318     });
 319     std::swap(_impl.storage, new_storage);
 320     std::swap(_impl.capacity, new_cap);
 321     _impl.begin = 0;
 322     _impl.end = p - _impl.storage;
 323     _impl.deallocate(new_storage, new_cap);
 324 }
 325
 326 template <typename T, typename Alloc>
 327 inline
 328 void
 329 circular_buffer<T, Alloc>::maybe_expand(size_t nr) {
 330     if (_impl.end - _impl.begin + nr > _impl.capacity) {
 331         expand();
 332     }
 333 }
 334
 335 template <typename T, typename Alloc>
 336 inline
 337 void
 338 circular_buffer<T, Alloc>::push_front(const T& data) {
 339     maybe_expand();
 340     auto p = &_impl.storage[mask(_impl.begin - 1)];
 341     _impl.construct(p, data);
 342     --_impl.begin;
 343 }
 344
 345 template <typename T, typename Alloc>
 346 inline
 347 void
 348 circular_buffer<T, Alloc>::push_front(T&& data) {
 349     maybe_expand();
 350     auto p = &_impl.storage[mask(_impl.begin - 1)];
 351     _impl.construct(p, std::move(data));
 352     --_impl.begin;
 353 }
 354
 355 template <typename T, typename Alloc>
 356 template <typename... Args>
 357 inline
 358 void
 359 circular_buffer<T, Alloc>::emplace_front(Args&&... args) {
 360     maybe_expand();
 361     auto p = &_impl.storage[mask(_impl.begin - 1)];
 362     _impl.construct(p, std::forward<Args>(args)...);
 363     --_impl.begin;
 364 }
 365
 366 template <typename T, typename Alloc>
 367 inline
 368 void
 369 circular_buffer<T, Alloc>::push_back(const T& data) {
 370     maybe_expand();
 371     auto p = &_impl.storage[mask(_impl.end)];
 372     _impl.construct(p, data);
 373     ++_impl.end;
 374 }
 375
 376 template <typename T, typename Alloc>
 377 inline
 378 void
 379 circular_buffer<T, Alloc>::push_back(T&& data) {
 380     maybe_expand();
 381     auto p = &_impl.storage[mask(_impl.end)];
 382     _impl.construct(p, std::move(data));
 383     ++_impl.end;
 384 }
 385
 386 template <typename T, typename Alloc>
 387 template <typename... Args>
 388 inline
 389 void
 390 circular_buffer<T, Alloc>::emplace_back(Args&&... args) {
 391     maybe_expand();
 392     auto p = &_impl.storage[mask(_impl.end)];
 393     _impl.construct(p, std::forward<Args>(args)...);
 394     ++_impl.end;
 395 }
 396
 397 template <typename T, typename Alloc>
 398 inline
 399 T&
 400 circular_buffer<T, Alloc>::front() {
 401     return _impl.storage[mask(_impl.begin)];
 402 }
 403
 404 template <typename T, typename Alloc>
 405 inline
 406 const T&
 407 circular_buffer<T, Alloc>::front() const {
 408     return _impl.storage[mask(_impl.begin)];
 409 }
 410
 411 template <typename T, typename Alloc>
 412 inline
 413 T&
 414 circular_buffer<T, Alloc>::back() {
 415     return _impl.storage[mask(_impl.end - 1)];
 416 }
 417
 418 template <typename T, typename Alloc>
 419 inline
 420 const T&
 421 circular_buffer<T, Alloc>::back() const {
 422     return _impl.storage[mask(_impl.end - 1)];
 423 }
 424
 425 template <typename T, typename Alloc>
 426 inline
 427 void
 428 circular_buffer<T, Alloc>::pop_front() {
 429     _impl.destroy(&front());
 430     ++_impl.begin;
 431 }
 432
 433 template <typename T, typename Alloc>
 434 inline
 435 void
 436 circular_buffer<T, Alloc>::pop_back() {
 437     _impl.destroy(&back());
 438     --_impl.end;
 439 }
 440
 441 template <typename T, typename Alloc>
 442 inline
 443 T&
 444 circular_buffer<T, Alloc>::operator[](size_t idx) {
 445     return _impl.storage[mask(_impl.begin + idx)];
 446 }
 447
 448 template <typename T, typename Alloc>
 449 inline
 450 const T&
 451 circular_buffer<T, Alloc>::operator[](size_t idx) const {
 452     return _impl.storage[mask(_impl.begin + idx)];
 453 }
 454
 455 template <typename T, typename Alloc>
 456 inline
 457 T&
 458 circular_buffer<T, Alloc>::access_element_unsafe(size_t idx) {
 459     return _impl.storage[mask(_impl.begin + idx)];
 460 }
 461
 462 template <typename T, typename Alloc>
 463 inline
 464 typename circular_buffer<T, Alloc>::iterator
 465 circular_buffer<T, Alloc>::erase(iterator first, iterator last) {
 466     static_assert(std::is_nothrow_move_assignable<T>::value, "erase() assumes move assignment does not throw");
 467     if (first == last) {
 468         return last;
 469     }
 470     // Move to the left or right depending on which would result in least amount of moves.
 471     // This also guarantees that iterators will be stable when removing from either front or back.
 472     if (std::distance(begin(), first) < std::distance(last, end())) {
 473         auto new_start = std::move_backward(begin(), first, last);
 474         auto i = begin();
 475         while (i < new_start) {
 476             _impl.destroy(&*i++);
 477         }
 478         _impl.begin = new_start.idx;
 479         return last;
 480     } else {
 481         auto new_end = std::move(last, end(), first);
 482         auto i = new_end;
 483         auto e = end();
 484         while (i < e) {
 485             _impl.destroy(&*i++);
 486         }
 487         _impl.end = new_end.idx;
 488         return first;
 489     }
 490 }
 491
 492 }