boost/lockfree/ringbuffer.hpp

   1 //  lock-free single-producer/single-consumer ringbuffer
   2 //  this algorithm is implemented in various projects (jack, portaudio, supercollider)
   3 //
   4 //  implementation for c++
   5 //
   6 //  Copyright (C) 2009 Tim Blechmann
   7 //
   8 //  Distributed under the Boost Software License, Version 1.0. (See
   9 //  accompanying file LICENSE_1_0.txt or copy at
  10 //  http://www.boost.org/LICENSE_1_0.txt)
  11
  12 //  Disclaimer: Not a Boost library.
  13
  14 #ifndef BOOST_LOCKFREE_RINGBUFFER_HPP_INCLUDED
  15 #define BOOST_LOCKFREE_RINGBUFFER_HPP_INCLUDED
  16
  17 #include <boost/atomic.hpp>
  18 #include <boost/array.hpp>
  19 #include <boost/noncopyable.hpp>
  20 #include <boost/smart_ptr/scoped_array.hpp>
  21
  22 #include "detail/branch_hints.hpp"
  23 #include "detail/prefix.hpp"
  24
  25 namespace boost
  26 {
  27 namespace lockfree
  28 {
  29
  30 namespace detail
  31 {
  32
  33 template <typename T>
  34 class ringbuffer_internal:
  35     boost::noncopyable
  36 {
  37     static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(size_t);
  38     atomic<size_t> write_index_;
  39     char padding1[padding_size]; /* force read_index and write_index to different cache lines */
  40     atomic<size_t> read_index_;
  41
  42 protected:
  43     ringbuffer_internal(void):
  44         write_index_(0), read_index_(0)
  45     {}
  46
  47     static size_t next_index(size_t arg, size_t max_size)
  48     {
  49         size_t ret = arg + 1;
  50         while (unlikely(ret >= max_size))
  51             ret -= max_size;
  52         return ret;
  53     }
  54
  55     bool enqueue(T const & t, T * buffer, size_t max_size)
  56     {
  57         size_t next = next_index(write_index_.load(memory_order_acquire), max_size);
  58
  59         if (next == read_index_.load(memory_order_acquire))
  60             return false; /* ringbuffer is full */
  61
  62         buffer[next] = t;
  63
  64         write_index_.store(next, memory_order_release);
  65
  66         return true;
  67     }
  68
  69     bool dequeue (T * ret, T * buffer, size_t max_size)
  70     {
  71         if (empty())
  72             return false;
  73
  74         size_t next = next_index(read_index_.load(memory_order_acquire), max_size);
  75         *ret = buffer[next];
  76         read_index_.store(next, memory_order_release);
  77         return true;
  78     }
  79
  80 public:
  81     void reset(void)
  82     {
  83         write_index_.store(0, memory_order_relaxed);
  84         read_index_.store(0, memory_order_release);
  85     }
  86
  87     bool empty(void)
  88     {
  89         return write_index_.load(memory_order_relaxed) == read_index_.load(memory_order_relaxed);
  90     }
  91
  92 };
  93
  94 } /* namespace detail */
  95
  96 template <typename T, size_t max_size>
  97 class ringbuffer:
  98     public detail::ringbuffer_internal<T>
  99 {
 100     boost::array<T, max_size> array_;
 101
 102 public:
 103     bool enqueue(T const & t)
 104     {
 105         return detail::ringbuffer_internal<T>::enqueue(t, array_.c_array(), max_size);
 106     }
 107
 108     bool dequeue(T * ret)
 109     {
 110         return detail::ringbuffer_internal<T>::dequeue(ret, array_.c_array(), max_size);
 111     }
 112 };
 113
 114 template <typename T>
 115 class ringbuffer<T, 0>:
 116     public detail::ringbuffer_internal<T>
 117 {
 118     size_t max_size_;
 119     scoped_array<T> array_;
 120
 121 public:
 122     ringbuffer(size_t max_size):
 123         max_size_(max_size), array_(new T[max_size])
 124     {}
 125
 126     bool enqueue(T const & t)
 127     {
 128         return detail::ringbuffer_internal<T>::enqueue(t, array_.get(), max_size_);
 129     }
 130
 131     bool dequeue(T * ret)
 132     {
 133         return detail::ringbuffer_internal<T>::dequeue(ret, array_.get(), max_size_);
 134     }
 135 };
 136
 137
 138 } /* namespace lockfree */
 139 } /* namespace boost */
 140
 141
 142 #endif /* BOOST_LOCKFREE_RINGBUFFER_HPP_INCLUDED */