ceph/src/msg/async/dpdk/circular_buffer.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 /*
   3  * This file is open source software, licensed to you under the terms
   4  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   5  * distributed with this work for additional information regarding copyright
   6  * ownership.  You may not use this file except in compliance with the License.
   7  *
   8  * You may obtain a copy of the License at
   9  *
  10  *   http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing,
  13  * software distributed under the License is distributed on an
  14  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  15  * KIND, either express or implied.  See the License for the
  16  * specific language governing permissions and limitations
  17  * under the License.
  18  */
  19 /*
  20  * Copyright (C) 2014 Cloudius Systems, Ltd.
  21  */
  22
  23 #ifndef CEPH_CIRCULAR_BUFFER_HH_
  24 #define CEPH_CIRCULAR_BUFFER_HH_
  25
  26 // A growable double-ended queue container that can be efficiently
  27 // extended (and shrunk) from both ends.  Implementation is a single
  28 // storage vector.
  29 //
  30 // Similar to libstdc++'s std::deque, except that it uses a single level
  31 // store, and so is more efficient for simple stored items.
  32 // Similar to boost::circular_buffer_space_optimized, except it uses
  33 // uninitialized storage for unoccupied elements (and thus move/copy
  34 // constructors instead of move/copy assignments, which are less efficient).
  35
  36 #include <memory>
  37 #include <algorithm>
  38
  39 #include "transfer.h"
  40
  41 template <typename T, typename Alloc = std::allocator<T>>
  42 class circular_buffer {
  43   struct impl : Alloc {
  44     T* storage = nullptr;
  45     // begin, end interpreted (mod capacity)
  46     size_t begin = 0;
  47     size_t end = 0;
  48     size_t capacity = 0;
  49   };
  50   impl _impl;
  51  public:
  52   using value_type = T;
  53   using size_type = size_t;
  54   using reference = T&;
  55   using pointer = T*;
  56   using const_reference = const T&;
  57   using const_pointer = const T*;
  58  public:
  59   circular_buffer() = default;
  60   circular_buffer(circular_buffer&& X);
  61   circular_buffer(const circular_buffer& X) = delete;
  62   ~circular_buffer();
  63   circular_buffer& operator=(const circular_buffer&) = delete;
  64   circular_buffer& operator=(circular_buffer&&) = delete;
  65   void push_front(const T& data);
  66   void push_front(T&& data);
  67   template <typename... A>
  68   void emplace_front(A&&... args);
  69   void push_back(const T& data);
  70   void push_back(T&& data);
  71   template <typename... A>
  72   void emplace_back(A&&... args);
  73   T& front();
  74   T& back();
  75   void pop_front();
  76   void pop_back();
  77   bool empty() const;
  78   size_t size() const;
  79   size_t capacity() const;
  80   T& operator[](size_t idx);
  81   template <typename Func>
  82   void for_each(Func func);
  83   // access an element, may return wrong or destroyed element
  84   // only useful if you do not rely on data accuracy (e.g. prefetch)
  85   T& access_element_unsafe(size_t idx);
  86  private:
  87   void expand();
  88   void maybe_expand(size_t nr = 1);
  89   size_t mask(size_t idx) const;
  90
  91   template<typename CB, typename ValueType>
  92   struct cbiterator : std::iterator<std::random_access_iterator_tag, ValueType> {
  93     typedef std::iterator<std::random_access_iterator_tag, ValueType> super_t;
  94
  95     ValueType& operator*() const { return cb->_impl.storage[cb->mask(idx)]; }
  96     ValueType* operator->() const { return &cb->_impl.storage[cb->mask(idx)]; }
  97     // prefix
  98     cbiterator<CB, ValueType>& operator++() {
  99       idx++;
 100       return *this;
 101     }
 102     // postfix
 103     cbiterator<CB, ValueType> operator++(int unused) {
 104       auto v = *this;
 105       idx++;
 106       return v;
 107     }
 108     // prefix
 109     cbiterator<CB, ValueType>& operator--() {
 110       idx--;
 111       return *this;
 112     }
 113     // postfix
 114     cbiterator<CB, ValueType> operator--(int unused) {
 115       auto v = *this;
 116       idx--;
 117       return v;
 118     }
 119     cbiterator<CB, ValueType> operator+(typename super_t::difference_type n) const {
 120       return cbiterator<CB, ValueType>(cb, idx + n);
 121     }
 122     cbiterator<CB, ValueType> operator-(typename super_t::difference_type n) const {
 123       return cbiterator<CB, ValueType>(cb, idx - n);
 124     }
 125     cbiterator<CB, ValueType>& operator+=(typename super_t::difference_type n) {
 126       idx += n;
 127       return *this;
 128     }
 129     cbiterator<CB, ValueType>& operator-=(typename super_t::difference_type n) {
 130       idx -= n;
 131       return *this;
 132     }
 133     bool operator==(const cbiterator<CB, ValueType>& rhs) const {
 134       return idx == rhs.idx;
 135     }
 136     bool operator!=(const cbiterator<CB, ValueType>& rhs) const {
 137       return idx != rhs.idx;
 138     }
 139     bool operator<(const cbiterator<CB, ValueType>& rhs) const {
 140       return idx < rhs.idx;
 141     }
 142     bool operator>(const cbiterator<CB, ValueType>& rhs) const {
 143       return idx > rhs.idx;
 144     }
 145     bool operator>=(const cbiterator<CB, ValueType>& rhs) const {
 146       return idx >= rhs.idx;
 147     }
 148     bool operator<=(const cbiterator<CB, ValueType>& rhs) const {
 149       return idx <= rhs.idx;
 150     }
 151     typename super_t::difference_type operator-(const cbiterator<CB, ValueType>& rhs) const {
 152       return idx - rhs.idx;
 153     }
 154    private:
 155     CB* cb;
 156     size_t idx;
 157     cbiterator<CB, ValueType>(CB* b, size_t i) : cb(b), idx(i) {}
 158     friend class circular_buffer;
 159   };
 160   friend class iterator;
 161
 162  public:
 163   typedef cbiterator<circular_buffer, T> iterator;
 164   typedef cbiterator<const circular_buffer, const T> const_iterator;
 165
 166   iterator begin() {
 167     return iterator(this, _impl.begin);
 168   }
 169   const_iterator begin() const {
 170     return const_iterator(this, _impl.begin);
 171   }
 172   iterator end() {
 173     return iterator(this, _impl.end);
 174   }
 175   const_iterator end() const {
 176     return const_iterator(this, _impl.end);
 177   }
 178   const_iterator cbegin() const {
 179     return const_iterator(this, _impl.begin);
 180   }
 181   const_iterator cend() const {
 182     return const_iterator(this, _impl.end);
 183   }
 184 };
 185
 186 template <typename T, typename Alloc>
 187 inline size_t circular_buffer<T, Alloc>::mask(size_t idx) const {
 188   return idx & (_impl.capacity - 1);
 189 }
 190
 191 template <typename T, typename Alloc>
 192 inline bool circular_buffer<T, Alloc>::empty() const {
 193   return _impl.begin == _impl.end;
 194 }
 195
 196 template <typename T, typename Alloc>
 197 inline size_t circular_buffer<T, Alloc>::size() const {
 198   return _impl.end - _impl.begin;
 199 }
 200
 201 template <typename T, typename Alloc>
 202 inline size_t circular_buffer<T, Alloc>::capacity() const {
 203   return _impl.capacity;
 204 }
 205
 206 template <typename T, typename Alloc>
 207 inline circular_buffer<T, Alloc>::circular_buffer(circular_buffer&& x)
 208     : _impl(std::move(x._impl)) {
 209   x._impl = {};
 210 }
 211
 212 template <typename T, typename Alloc>
 213 template <typename Func>
 214 inline void circular_buffer<T, Alloc>::for_each(Func func) {
 215   auto s = _impl.storage;
 216   auto m = _impl.capacity - 1;
 217   for (auto i = _impl.begin; i != _impl.end; ++i) {
 218     func(s[i & m]);
 219   }
 220 }
 221
 222 template <typename T, typename Alloc>
 223 inline circular_buffer<T, Alloc>::~circular_buffer() {
 224   for_each([this] (T& obj) {
 225     _impl.destroy(&obj);
 226   });
 227   _impl.deallocate(_impl.storage, _impl.capacity);
 228 }
 229
 230 template <typename T, typename Alloc>
 231 void circular_buffer<T, Alloc>::expand() {
 232   auto new_cap = std::max<size_t>(_impl.capacity * 2, 1);
 233   auto new_storage = _impl.allocate(new_cap);
 234   auto p = new_storage;
 235   try {
 236     for_each([this, &p] (T& obj) {
 237       transfer_pass1(_impl, &obj, p);
 238       p++;
 239     });
 240   } catch (...) {
 241     while (p != new_storage) {
 242       _impl.destroy(--p);
 243     }
 244     _impl.deallocate(new_storage, new_cap);
 245     throw;
 246   }
 247   p = new_storage;
 248   for_each([this, &p] (T& obj) {
 249     transfer_pass2(_impl, &obj, p++);
 250   });
 251   std::swap(_impl.storage, new_storage);
 252   std::swap(_impl.capacity, new_cap);
 253   _impl.begin = 0;
 254   _impl.end = p - _impl.storage;
 255   _impl.deallocate(new_storage, new_cap);
 256 }
 257
 258 template <typename T, typename Alloc>
 259 inline void circular_buffer<T, Alloc>::maybe_expand(size_t nr) {
 260   if (_impl.end - _impl.begin + nr > _impl.capacity) {
 261     expand();
 262   }
 263 }
 264
 265 template <typename T, typename Alloc>
 266 inline void circular_buffer<T, Alloc>::push_front(const T& data) {
 267   maybe_expand();
 268   auto p = &_impl.storage[mask(_impl.begin - 1)];
 269   _impl.construct(p, data);
 270   --_impl.begin;
 271 }
 272
 273 template <typename T, typename Alloc>
 274 inline void circular_buffer<T, Alloc>::push_front(T&& data) {
 275   maybe_expand();
 276   auto p = &_impl.storage[mask(_impl.begin - 1)];
 277   _impl.construct(p, std::move(data));
 278   --_impl.begin;
 279 }
 280
 281 template <typename T, typename Alloc>
 282 template <typename... Args>
 283 inline void circular_buffer<T, Alloc>::emplace_front(Args&&... args) {
 284   maybe_expand();
 285   auto p = &_impl.storage[mask(_impl.begin - 1)];
 286   _impl.construct(p, std::forward<Args>(args)...);
 287   --_impl.begin;
 288 }
 289
 290 template <typename T, typename Alloc>
 291 inline void circular_buffer<T, Alloc>::push_back(const T& data) {
 292   maybe_expand();
 293   auto p = &_impl.storage[mask(_impl.end)];
 294   _impl.construct(p, data);
 295   ++_impl.end;
 296 }
 297
 298 template <typename T, typename Alloc>
 299 inline void circular_buffer<T, Alloc>::push_back(T&& data) {
 300   maybe_expand();
 301   auto p = &_impl.storage[mask(_impl.end)];
 302   _impl.construct(p, std::move(data));
 303   ++_impl.end;
 304 }
 305
 306 template <typename T, typename Alloc>
 307 template <typename... Args>
 308 inline void circular_buffer<T, Alloc>::emplace_back(Args&&... args) {
 309   maybe_expand();
 310   auto p = &_impl.storage[mask(_impl.end)];
 311   _impl.construct(p, std::forward<Args>(args)...);
 312   ++_impl.end;
 313 }
 314
 315 template <typename T, typename Alloc>
 316 inline T& circular_buffer<T, Alloc>::front() {
 317   return _impl.storage[mask(_impl.begin)];
 318 }
 319
 320 template <typename T, typename Alloc>
 321 inline T& circular_buffer<T, Alloc>::back() {
 322   return _impl.storage[mask(_impl.end - 1)];
 323 }
 324
 325 template <typename T, typename Alloc>
 326 inline void circular_buffer<T, Alloc>::pop_front() {
 327   _impl.destroy(&front());
 328   ++_impl.begin;
 329 }
 330
 331 template <typename T, typename Alloc>
 332 inline void circular_buffer<T, Alloc>::pop_back() {
 333   _impl.destroy(&back());
 334   --_impl.end;
 335 }
 336
 337 template <typename T, typename Alloc>
 338 inline T& circular_buffer<T, Alloc>::operator[](size_t idx) {
 339   return _impl.storage[mask(_impl.begin + idx)];
 340 }
 341
 342 template <typename T, typename Alloc>
 343 inline T& circular_buffer<T, Alloc>::access_element_unsafe(size_t idx) {
 344   return _impl.storage[mask(_impl.begin + idx)];
 345 }
 346
 347 #endif /* CEPH_CIRCULAR_BUFFER_HH_ */