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