lock_free_mpmc_queue.h 6.05 KB
Newer Older
1
/*
2
 * Copyright (c) 2014-2015, Siemens AG. All rights reserved.
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef EMBB_CONTAINERS_LOCK_FREE_MPMC_QUEUE_H_
#define EMBB_CONTAINERS_LOCK_FREE_MPMC_QUEUE_H_

#include <embb/base/atomic.h>
#include <embb/base/function.h>

#include <embb/containers/lock_free_tree_value_pool.h>
#include <embb/containers/object_pool.h>
#include <embb/containers/internal/hazard_pointer.h>

#include <limits>
#include <stdexcept>

namespace embb {
namespace containers {
namespace internal {
/**
 * Queue node
 *
 * Single linked lists, contains the element (\c element) and a pointer to the
 * next node (\c next).
 *
49
 * \tparam Type Element type
50
 */
51
  template< typename Type >
52 53 54 55 56
class LockFreeMPMCQueueNode {
 private:
  /**
   * Pointer to the next node
   */
57
  embb::base::Atomic< LockFreeMPMCQueueNode< Type >* > next;
58 59 60 61

  /**
   * The stored element
   */
62
  Type element;
63 64 65 66 67 68 69 70 71 72 73 74 75

 public:
  /**
   * Creates a queue node
   *
   * Explicitly allow uninitialized \c element, used for dummy node
   */
  LockFreeMPMCQueueNode();

  /**
   * Creates a queue node
   */
  LockFreeMPMCQueueNode(
76
    Type const& element
77
    /**< [IN] The element of this queue node */);
78 79 80 81 82 83

  /**
   * Returns the next pointer
   *
   * \return The next pointer
   */
84
  embb::base::Atomic< LockFreeMPMCQueueNode< Type >* > & GetNext();
85 86 87 88

  /**
   * Returns the element held by this node
   */
89
  Type GetElement();
90 91 92 93 94 95 96 97 98 99 100 101
};
} // namespace internal

/**
 * Lock-free queue for multiple producers and multiple consumers
 *
 * \concept{CPP_CONCEPTS_QUEUE}
 *
 * \ingroup CPP_CONTAINERS_QUEUES
 *
 * \see WaitFreeSPSCQueue
 *
102
 * \tparam Type Type of the queue elements
103 104 105
 * \tparam ValuePool Type of the value pool used as basis for the ObjectPool
 *         which stores the elements.
 */
106
template< typename Type,
107
  typename ValuePool = embb::containers::LockFreeTreeValuePool < bool, false >
108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
>
class LockFreeMPMCQueue {
 private:
  /**
   * The capacity of the queue. It is guaranteed that the queue can hold at
   * least as many elements, maybe more.
   */
  size_t capacity;
  // Do not change the ordering of class local variables.
  // Important for initialization.

  /**
   * Callback to the method that is called by hazard pointers if a pointer is
   * not hazardous anymore, i.e., can safely be reused.
   */
123
  embb::base::Function < void, internal::LockFreeMPMCQueueNode<Type>* >
124 125 126 127 128
    delete_pointer_callback;

  /**
   * The hazard pointer object, used for memory management.
   */
129
  embb::containers::internal::HazardPointer
130
    < internal::LockFreeMPMCQueueNode<Type>* > hazardPointer;
131 132 133 134

  /**
   * The object pool, used for lock-free memory allocation.
   */
135
  ObjectPool< internal::LockFreeMPMCQueueNode<Type>, ValuePool > objectPool;
136 137 138 139

  /**
   * Atomic pointer to the head node of the queue
   */
140
  embb::base::Atomic< internal::LockFreeMPMCQueueNode<Type>* > head;
141 142 143 144

  /**
   * Atomic pointer to the tail node of the queue
   */
145
  embb::base::Atomic< internal::LockFreeMPMCQueueNode<Type>* > tail;
146 147 148 149 150

  /**
   * The callback function, used to cleanup non-hazardous pointers.
   * \see delete_pointer_callback
   */
151
  void DeletePointerCallback(internal::LockFreeMPMCQueueNode<Type>* to_delete);
152 153 154 155 156 157 158 159

 public:
  /**
   * Creates a queue with the specified capacity.
   *
   * \memory
   * Let \c t be the maximum number of threads and \c x be <tt>2.5*t+1</tt>.
   * Then, <tt>x*(3*t+1)</tt> elements of size <tt>sizeof(void*)</tt>, \c x
160 161
   * elements of size <tt>sizeof(Type)</tt>, and \c capacity+1 elements of size
   * <tt>sizeof(Type)</tt> are allocated.
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
   *
   * \notthreadsafe
   *
   * \see CPP_CONCEPTS_QUEUE
   */
  LockFreeMPMCQueue(
    size_t capacity
    /**< [IN] Capacity of the queue */);

  /**
   * Destroys the queue.
   *
   * \notthreadsafe
   */
  ~LockFreeMPMCQueue();

  /**
   * Returns the capacity of the queue.
   *
   * \return Number of elements the queue can hold.
   *
   * \waitfree
   */
  size_t GetCapacity();

  /**
   * Tries to enqueue an element into the queue.
   *
   * \return \c true if the element could be enqueued, \c false if the queue is
   * full.
   *
   * \lockfree
   *
   * \note It might be possible to enqueue more elements into the queue than its
   * capacity permits.
   *
   * \see CPP_CONCEPTS_QUEUE
   */
  bool TryEnqueue(
201
    Type const& element
202
    /**< [IN] Const reference to the element that shall be enqueued */);
203 204 205 206 207 208 209 210 211 212 213 214

  /**
   * Tries to dequeue an element from the queue.
   *
   * \return \c true if an element could be dequeued, \c false if the queue is
   * empty.
   *
   * \lockfree
   *
   * \see CPP_CONCEPTS_QUEUE
   */
  bool TryDequeue(
215
    Type & element
216 217 218
    /**< [IN, OUT] Reference to the dequeued element.
                   Unchanged, if the operation
                   was not successful. */);
219 220 221 222 223 224 225
};
} // namespace containers
} // namespace embb

#include <embb/containers/internal/lock_free_mpmc_queue-inl.h>

#endif  // EMBB_CONTAINERS_LOCK_FREE_MPMC_QUEUE_H_