queue/array_lock_free_queue.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.h
  29 /// @brief Definition of a circular array based lock-free queue
  30 ///
  31 /// @author Faustino Frechilla
  32 /// @history
  33 /// Ref  Who                 When         What
  34 ///      Faustino Frechilla  11-Jul-2010  Original development
  35 /// @endhistory
  36 ///
  37 // ============================================================================
  38
  39 #ifndef __ARRAY_LOCK_FREE_QUEUE_H__
  40 #define __ARRAY_LOCK_FREE_QUEUE_H__
  41
  42 #include <stdint.h>     // uint32_t
  43 #include "atomic_ops.h" // atomic operations wrappers
  44
  45 #define ARRAY_LOCK_FREE_Q_DEFAULT_SIZE 65535 // (2^16)
  46
  47 // define this variable if calls to "size" must return the real size of the
  48 // queue. If it is undefined  that function will try to take a snapshot of
  49 // the queue, but returned value might be bogus
  50 #undef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
  51 //#define ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE 1
  52
  53
  54 /// @brief Lock-free queue based on a circular array
  55 /// No allocation of extra memory for the nodes handling is needed, but it has to add
  56 /// extra overhead (extra CAS operation) when inserting to ensure the thread-safety of the queue
  57 /// ELEM_T     represents the type of elementes pushed and popped from the queue
  58 /// TOTAL_SIZE size of the queue. It should be a power of 2 to ensure
  59 ///            indexes in the circular queue keep stable when the uint32_t
  60 ///            variable that holds the current position rolls over from FFFFFFFF
  61 ///            to 0. For instance
  62 ///            2    -> 0x02
  63 ///            4    -> 0x04
  64 ///            8    -> 0x08
  65 ///            16   -> 0x10
  66 ///            (...)
  67 ///            1024 -> 0x400
  68 ///            2048 -> 0x800
  69 ///
  70 ///            if queue size is not defined as requested, let's say, for
  71 ///            instance 100, when current position is FFFFFFFF (4,294,967,295)
  72 ///            index in the circular array is 4,294,967,295 % 100 = 95.
  73 ///            When that value is incremented it will be set to 0, that is the
  74 ///            last 4 elements of the queue are not used when the counter rolls
  75 ///            over to 0
  76 template <typename ELEM_T, uint32_t Q_SIZE = ARRAY_LOCK_FREE_Q_DEFAULT_SIZE>
  77 class ArrayLockFreeQueue
  78 {
  79 public:
  80     /// @brief constructor of the class
  81     ArrayLockFreeQueue();
  82     virtual ~ArrayLockFreeQueue();
  83
  84     /// @brief returns the current number of items in the queue
  85     /// It tries to take a snapshot of the size of the queue, but in busy environments
  86     /// this function might return bogus values.
  87     ///
  88     /// If a reliable queue size must be kept you might want to have a look at
  89     /// the preprocessor variable in this header file called 'ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE'
  90     /// it enables a reliable size though it hits overall performance of the queue
  91     /// (when the reliable size variable is on it's got an impact of about 20% in time)
  92     uint32_t size();
  93
  94     /// @brief push an element at the tail of the queue
  95     /// @param the element to insert in the queue
  96     /// Note that the element is not a pointer or a reference, so if you are using large data
  97     /// structures to be inserted in the queue you should think of instantiate the template
  98     /// of the queue as a pointer to that large structure
  99     /// @returns true if the element was inserted in the queue. False if the queue was full
 100     bool push(const ELEM_T &a_data);
 101
 102     /// @brief pop the element at the head of the queue
 103     /// @param a reference where the element in the head of the queue will be saved to
 104     /// Note that the a_data parameter might contain rubbish if the function returns false
 105     /// @returns true if the element was successfully extracted from the queue. False if the queue was empty
 106     bool pop(ELEM_T &a_data);
 107
 108 private:
 109     /// @brief array to keep the elements
 110     ELEM_T m_theQueue[Q_SIZE];
 111
 112 #ifdef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
 113     /// @brief number of elements in the queue
 114     volatile uint32_t m_count;
 115 #endif
 116
 117     /// @brief where a new element will be inserted
 118     volatile uint32_t m_writeIndex;
 119
 120     /// @brief where the next element where be extracted from
 121     volatile uint32_t m_readIndex;
 122
 123     /// @brief maximum read index for multiple producer queues
 124     /// If it's not the same as m_writeIndex it means
 125     /// there are writes pending to be "committed" to the queue, that means,
 126     /// the place for the data was reserved (the index in the array) but
 127     /// data is still not in the queue, so the thread trying to read will have
 128     /// to wait for those other threads to save the data into the queue
 129     ///
 130     /// note this index is only used for MultipleProducerThread queues
 131     volatile uint32_t m_maximumReadIndex;
 132
 133     /// @brief calculate the index in the circular array that corresponds
 134     /// to a particular "count" value
 135     inline uint32_t countToIndex(uint32_t a_count);
 136 };
 137
 138 // include the implementation file
 139 #include "array_lock_free_queue_impl.h"
 140
 141 #endif // __ARRAY_LOCK_FREE_QUEUE_H__