queue/array_lock_free_queue_single_producer.h

   1 // ============================================================================
   2 // Copyright (c) 2010 Faustino Frechilla
   3 // All rights reserved.
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are met:
   7 //
   8 //  1. Redistributions of source code must retain the above copyright notice,
   9 //     this list of conditions and the following disclaimer.
  10 //  2. Redistributions in binary form must reproduce the above copyright
  11 //     notice, this list of conditions and the following disclaimer in the
  12 //     documentation and/or other materials provided with the distribution.
  13 //  3. The name of the author may not be used to endorse or promote products
  14 //     derived from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26 // POSSIBILITY OF SUCH DAMAGE.
  27 //
  28 /// @file array_lock_free_queue_single_producer.h
  29 /// @brief Definition of a circular array based lock-free queue
  30 ///
  31 /// WARNING: This queue is not thread safe when several threads try to insert
  32 ///          elements into the queue. It is allowed to use as many consumers
  33 ///          as needed though.
  34 ///
  35 /// @author Faustino Frechilla
  36 /// @history
  37 /// Ref  Who                 When         What
  38 ///      Faustino Frechilla  11-Jul-2010  Original development
  39 /// @endhistory
  40 ///
  41 // ============================================================================
  42
  43 #ifndef __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__
  44 #define __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__
  45
  46 #include <stdint.h>     // uint32_t
  47 #include "atomic_ops.h" // atomic operations wrappers
  48
  49 #define ARRAY_LOCK_FREE_Q_DEFAULT_SIZE 65536 // 2^16 = 65,536 elements by default
  50
  51 // define this variable if calls to "size" must return the real size of the
  52 // queue. If it is undefined  that function will try to take a snapshot of
  53 // the queue, but returned value might be bogus
  54 #undef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
  55 //#define ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE 1
  56
  57
  58 /// @brief especialisation of the ArrayLockFreeQueue to be used when there is
  59 ///        only one producer thread
  60 /// No allocation of extra memory for the nodes handling is needed
  61 /// WARNING: This queue is not thread safe when several threads try to insert elements
  62 /// into the queue
  63 /// ELEM_T     represents the type of elementes pushed and popped from the queue
  64 /// TOTAL_SIZE size of the queue. It should be a power of 2 to ensure
  65 ///            indexes in the circular queue keep stable when the uint32_t
  66 ///            variable that holds the current position rolls over from FFFFFFFF
  67 ///            to 0. For instance
  68 ///            2    -> 0x02
  69 ///            4    -> 0x04
  70 ///            8    -> 0x08
  71 ///            16   -> 0x10
  72 ///            (...)
  73 ///            1024 -> 0x400
  74 ///            2048 -> 0x800
  75 ///
  76 ///            if queue size is not defined as requested, let's say, for
  77 ///            instance 100, when current position is FFFFFFFF (4,294,967,295)
  78 ///            index in the circular array is 4,294,967,295 % 100 = 95.
  79 ///            When that value is incremented it will be set to 0, that is the
  80 ///            last 4 elements of the queue are not used when the counter rolls
  81 ///            over to 0
  82 template <typename ELEM_T, uint32_t Q_SIZE = ARRAY_LOCK_FREE_Q_DEFAULT_SIZE>
  83 class ArrayLockFreeQueueSingleProducer
  84 {
  85 public:
  86     /// @brief constructor of the class
  87     ArrayLockFreeQueueSingleProducer();
  88     virtual ~ArrayLockFreeQueueSingleProducer();
  89
  90     /// @brief returns the current number of items in the queue
  91     /// It tries to take a snapshot of the size of the queue, but in busy environments
  92     /// this function might return bogus values.
  93     ///
  94     /// If a reliable queue size must be kept you might want to have a look at
  95     /// the preprocessor variable in this header file called 'ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE'
  96     /// it enables a reliable size though it hits overall performance of the queue
  97     /// (when the reliable size variable is on it's got an impact of about 20% in time)
  98     uint32_t size();
  99
 100     /// @brief push an element at the tail of the queue
 101     /// @param the element to insert in the queue
 102     /// Note that the element is not a pointer or a reference, so if you are using large data
 103     /// structures to be inserted in the queue you should think of instantiate the template
 104     /// of the queue as a pointer to that large structure
 105     /// @returns true if the element was inserted in the queue. False if the queue was full
 106     bool push(const ELEM_T &a_data);
 107
 108     /// @brief pop the element at the head of the queue
 109     /// @param a reference where the element in the head of the queue will be saved to
 110     /// Note that the a_data parameter might contain rubbish if the function returns false
 111     /// @returns true if the element was successfully extracted from the queue. False if the queue was empty
 112     bool pop(ELEM_T &a_data);
 113
 114 private:
 115     /// @brief array to keep the elements
 116     ELEM_T m_theQueue[Q_SIZE];
 117
 118 #ifdef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
 119     /// @brief number of elements in the queue
 120     volatile uint32_t m_count;
 121 #endif
 122
 123     /// @brief where a new element will be inserted
 124     volatile uint32_t m_writeIndex;
 125
 126     /// @brief where the next element where be extracted from
 127     volatile uint32_t m_readIndex;
 128
 129     /// @brief calculate the index in the circular array that corresponds
 130     /// to a particular "count" value
 131     inline uint32_t countToIndex(uint32_t a_count);
 132 };
 133
 134 // include the implementation file
 135 #include "array_lock_free_queue_single_producer_impl.h"
 136
 137 #endif // __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__