Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C++

Template Concepts, Sort Of

0.00/5 (No votes)
15 Mar 2019MIT1 min read 3.4K  
Template concepts, sort of

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):

C++
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. 🙂

C++
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

C++
#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;
};

License

This article, along with any associated source code and files, is licensed under The MIT License