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:
- copy-constructible
- no-throw copy-constructible
- move-constructible
- 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):
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.
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
#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;
};