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_single_producer.h
29 /// @brief Definition of a circular array based lock-free queue
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
35 /// @author Faustino Frechilla
38 /// Faustino Frechilla 11-Jul-2010 Original development
41 // ============================================================================
43 #ifndef __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__
44 #define __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__
46 #include <stdint.h> // uint32_t
47 #include "atomic_ops.h" // atomic operations wrappers
49 #define ARRAY_LOCK_FREE_Q_DEFAULT_SIZE 65536 // 2^16 = 65,536 elements by default
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
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
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
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
82 template <typename ELEM_T, uint32_t Q_SIZE = ARRAY_LOCK_FREE_Q_DEFAULT_SIZE>
83 class ArrayLockFreeQueueSingleProducer
86 /// @brief constructor of the class
87 ArrayLockFreeQueueSingleProducer();
88 virtual ~ArrayLockFreeQueueSingleProducer();
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.
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)
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);
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);
115 /// @brief array to keep the elements
116 ELEM_T m_theQueue[Q_SIZE];
118 #ifdef ARRAY_LOCK_FREE_Q_KEEP_REAL_SIZE
119 /// @brief number of elements in the queue
120 volatile uint32_t m_count;
123 /// @brief where a new element will be inserted
124 volatile uint32_t m_writeIndex;
126 /// @brief where the next element where be extracted from
127 volatile uint32_t m_readIndex;
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);
134 // include the implementation file
135 #include "array_lock_free_queue_single_producer_impl.h"
137 #endif // __ARRAY_LOCK_FREE_QUEUE_SINGLE_PRODUCER_H__