Back to the queue class from previous posts (here and here)… I realized things can be done better: I want the queue to work with move-constructible and move-assignable types as well as copyable types, and do so automatically. This way the
push and
pop methods can use
std::move to insert and remove elements from the queue. I also want it to work with no-throw constructible and assignable types; this way the
push and
pop methods can take a more optimized path that does not deal with exceptions. So I realized that I need four versions of
push and
pop methods: 1) copy-constructible, 2) no-throw copy-constructible, 3) move-constructible, 4) no-throw move-constructible. All fine and dandy, but how do we select the right version at compile time based on type
T that the queue holds?
In C++20 we will get template concepts that will allow us to do just that sort of selection at compile time. In the meantime we have to make do with
std::enable_if (see here) and other type traits.
Finally, for completeness of interface, I want to add a
pop method that returns an item rather than taking an output reference parameter, and declares proper
noexcept value depending on type
T.
Below is the no-throw-movable pop method; it’s declared noexcept and lacks exception handling code (possibly making it faster at runtime):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template<typename Q = T> typename std::enable_if< std::is_move_assignable<Q>::value and std::is_nothrow_move_assignable<Q>::value, void>::type pop(T& item) noexcept { m_fullSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); item = std::move(m_data[m_popIndex]); m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; --m_count; } m_openSlots.post(); } |
And here is the new pop method; notice its noexcept value is dependent on which version of pop it uses, and it is deduced at compile time 🙂
|
1 2 3 4 5 6 |
T pop() noexcept(std::is_nothrow_invocable_r<void, decltype(&blocking_queue<T>::pop<T>), T&>::value) { T item; pop(item); return item; } |
Complete listing:
|
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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 |
#pragma once #include <mutex> #include <utility> #include <type_traits> #include "semaphore.h" template<typename T> class blocking_queue { public: blocking_queue(unsigned int size) : m_size(size), m_pushIndex(0), m_popIndex(0), m_count(0), m_data((T*)operator new(size * sizeof(T))), m_openSlots(size), m_fullSlots(0) {} blocking_queue(const blocking_queue&) = delete; blocking_queue(blocking_queue&&) = delete; blocking_queue& operator = (const blocking_queue&) = delete; blocking_queue& operator = (blocking_queue&&) = delete; ~blocking_queue() noexcept { while (m_count--) { m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; } operator delete(m_data); } template<typename Q = T> typename std::enable_if< std::is_copy_constructible<Q>::value and std::is_nothrow_copy_constructible<Q>::value, void>::type push(const T& item) noexcept { m_openSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); new (m_data + m_pushIndex) T (item); m_pushIndex = ++m_pushIndex % m_size; ++m_count; } m_fullSlots.post(); } template<typename Q = T> typename std::enable_if< std::is_copy_constructible<Q>::value and not std::is_nothrow_copy_constructible<Q>::value, void>::type push(const T& item) { m_openSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); try { new (m_data + m_pushIndex) T (item); } catch (...) { m_openSlots.post(); throw; } m_pushIndex = ++m_pushIndex % m_size; ++m_count; } m_fullSlots.post(); } template<typename Q = T> typename std::enable_if< std::is_move_constructible<Q>::value and std::is_nothrow_move_constructible<Q>::value, void>::type push(T&& item) noexcept { m_openSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); new (m_data + m_pushIndex) T (std::move(item)); m_pushIndex = ++m_pushIndex % m_size; ++m_count; } m_fullSlots.post(); } template<typename Q = T> typename std::enable_if< std::is_move_constructible<Q>::value and not std::is_nothrow_move_constructible<Q>::value, void>::type push(T&& item) { m_openSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); try { new (m_data + m_pushIndex) T (std::move(item)); } catch (...) { m_openSlots.post(); throw; } m_pushIndex = ++m_pushIndex % m_size; ++m_count; } m_fullSlots.post(); } template<typename Q = T> typename std::enable_if< not std::is_move_assignable<Q>::value and std::is_nothrow_copy_assignable<Q>::value, void>::type pop(T& item) noexcept { m_fullSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); item = m_data[m_popIndex]; m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; --m_count; } m_openSlots.post(); } template<typename Q = T> typename std::enable_if< not std::is_move_assignable<Q>::value and not std::is_nothrow_copy_assignable<Q>::value, void>::type pop(T& item) { m_fullSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); try { item = m_data[m_popIndex]; } catch (...) { m_fullSlots.post(); throw; } m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; --m_count; } m_openSlots.post(); } template<typename Q = T> typename std::enable_if< std::is_move_assignable<Q>::value and std::is_nothrow_move_assignable<Q>::value, void>::type pop(T& item) noexcept { m_fullSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); item = std::move(m_data[m_popIndex]); m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; --m_count; } m_openSlots.post(); } template<typename Q = T> typename std::enable_if< std::is_move_assignable<Q>::value and not std::is_nothrow_move_assignable<Q>::value, void>::type pop(T& item) { m_fullSlots.wait(); { std::lock_guard<std::mutex> lock(m_cs); try { item = std::move(m_data[m_popIndex]); } catch (...) { m_fullSlots.post(); throw; } m_data[m_popIndex].~T(); m_popIndex = ++m_popIndex % m_size; --m_count; } m_openSlots.post(); } T pop() noexcept(std::is_nothrow_invocable_r<void, decltype(&blocking_queue<T>::pop<T>), T&>::value) { T item; pop(item); return item; } bool empty() const noexcept { std::lock_guard<std::mutex> lock(m_cs); return m_count == 0; } bool size() const noexcept { std::lock_guard<std::mutex> lock(m_cs); return m_count; } unsigned int max_size() const noexcept { return m_size; } private: const unsigned int m_size; unsigned int m_pushIndex; unsigned int m_popIndex; unsigned int m_count; T* m_data; fast_semaphore m_openSlots; fast_semaphore m_fullSlots; std::mutex m_cs; }; |
Dear Martin, thanks a lot for your blog! Very thorough and clear explanations!
I suppose there is a typo at line 209 – returned type should be unsigned int.
you’re right about line 209, thank you! must have been a copy-paste error 😉
In fact I think the return type should be auto 🙂
Thank you very much, Martin!:)