1 // ============================================================================
2 // Copyright (c) 2010 Faustino Frechilla
3 // All rights reserved.
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are met:
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.
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.
28 /// @file array_lock_free_queue.h
29 /// @brief Definition of a circular array based lock-free queue
31 /// @author Faustino Frechilla
34 /// Faustino Frechilla 11-Jul-2010 Original development
37 // ============================================================================
39 #ifndef __ARRAY_LOCK_FREE_QUEUE_H__
40 #define __ARRAY_LOCK_FREE_QUEUE_H__
42 #include <stdint.h> // uint32_t
43 #include "atomic_ops.h" // atomic operations wrappers
45 #define ARRAY_LOCK_FREE_Q_DEFAULT_SIZE 65535 // (2^16)
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
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
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
76 template <typename ELEM_T, uint32_t Q_SIZE = ARRAY_LOCK_FREE_Q_DEFAULT_SIZE>
77 class ArrayLockFreeQueue
80 /// @brief constructor of the class
82 virtual ~ArrayLockFreeQueue();
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.
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)
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);
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);
109 /// @brief array to keep the elements
110 ELEM_T m_theQueue[Q_SIZE];
112 #ifdef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
113 /// @brief number of elements in the queue
114 volatile uint32_t m_count;
117 /// @brief where a new element will be inserted
118 volatile uint32_t m_writeIndex;
120 /// @brief where the next element where be extracted from
121 volatile uint32_t m_readIndex;
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
130 /// note this index is only used for MultipleProducerThread queues
131 volatile uint32_t m_maximumReadIndex;
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);
138 // include the implementation file
139 #include "array_lock_free_queue_impl.h"
141 #endif // __ARRAY_LOCK_FREE_QUEUE_H__