External/module/RingQueue/RingQueue.hpp

#ifndef RINGQUEUE_H
#define RINGQUEUE_H

#include <cstdlib>
#include <utility>
#include <mutex>
#include <condition_variable>
#include <atomic>

/**
 * @brief 这里采用零公摊的方式，设置多大的空间，就有多大的空间可以使用
 *        1、m_rear指向最新入队的元素的下一个位置，就是下个将要入队的元素位置
 *        2、m_front指向需要出队的第一个元素
 *        3、环形队列自带互斥锁
 *        
 * 注意：
 *      使用时要注意，不带NoBlock的都是阻塞函数
 *
 * 判断队列满：
 *        m_rear == m_front，并且此时都不等于 -1
 *
 * 判断队列空：
 *        m_rear == m_front，并且都等于 -1
 *
 * 获取队列大小：
 *       基本原则就是m_rear后面跟着的是有效值，m_front后面跟着的是已经出队的大小
 *       m_rear > m_front，返回 m_rear - m_front
 *       m_front > m_rear，返回 m_capacity - (m_front - m_rear)
 *       m_rear == m_front，且不等于-1，返回 m_capacity
 *       m_rear == m_front，且等于-1，返回 0
 * 
 * @tparam T 模版类型
 */

#define _DefaultValue (m_isUseDefaultValue.load() ? m_defaultValue : T{})

template<typename T>
class RingQueue
{
    RingQueue(const RingQueue<T>& queue) = delete;
    RingQueue<T> operator=(const RingQueue<T>& queue) = delete;
public:
    RingQueue();
    RingQueue(long size);
    RingQueue(long size, T defaultValue);
    ~RingQueue();

    /* 入队，默认是阻塞入队 */
    void push(const T& value);
    void push(T&& value);
    bool push_noBlock(const T& value);
    bool push_noBlock(T&& value);
    /* 入队，队列满就出队一个，非阻塞 */
    T push_pop(const T& value);

    /* 出队，删除队列的首个元素
     * 注意，如果存储的是指针，需要手动释放该指针指向的内存区域，不然会造成内存泄漏 */
    void pop();

    /* 获取队列中第一个值），但是不出队
     * 阻塞的方式获取，如果队列为空，会一直阻塞住，直到获取到数据为止 */
    T front();
    /* 非阻塞的方式获取，队列为空返回false */
    bool front_noBlock(T& t);
    /* 非阻塞方式获取第一个值，如果对列为空，则会返回设置的默认值 */
    T front_noBlock();

    /* 获取对立第一个数据，获取完立刻出队
     * 如果队列为空，会阻塞住，直到有数据为止
     * 如果删除了拷贝构造函数，使用会报错 */
    T front_pop();
    /* 非阻塞方式获取第一个值，并出队 */
    bool front_pop_noBlock(T& t);
    /* 非阻塞方式获取第一个值，并出队，如果队列为空，会返回设置的默认值 */
    T front_pop_noBlock();
    /* 通过移动语义获取数据，获取完成后队列中的数据只是个空壳了，因此直接就出队了 */
    bool front_pop_move(T& t);
    bool front_pop_move_noBlock(T& t);
    
    /* 设置队列大小 */
    void setQueueCapacity(long size);
    /* 设置默认值，给指针类型使用，如果是非阻塞获取，空的时候可以返回为设置的默认值（如nullptr） */
    void setDefaultValue(T defaultValue);
    /* 获取队列大小，队列中有效值的大小 */
    long QueueSize();
    /* 获取队列容量 */
    long QueueCapacity();
    /* 判断队列是否为空 */
    bool isEmpty();
    /* 判断队列是否已满 */
    bool isFull();
    /* 清空队列 */
    void clearQueue();
    /* 退出所有可能的阻塞函数 */
    void exit();

private:
    /* 判断是否空 */
    inline bool _isEmpty();
    /* 判断是否满 */
    inline bool _isFull();

private:
    std::atomic_bool m_isExit = false;      /* 是否退出，这个标识位是为了退出阻塞住的函数 */
    std::mutex m_mutex;                     /* 互斥锁 */
    T m_defaultValue;                       /* 默认值 */
    std::atomic_bool m_isUseDefaultValue = false; /* 是否使用默认值 */
    T* m_queue = nullptr;                   /* 队列 */
    long m_capacity = 0;                        /* 队列容量 */
    long m_front = -1;                          /* 队头 */
    long m_rear = -1;                           /* 队尾 */
    std::condition_variable m_cond_NoFull;      /* 非满条件变量 */
    std::condition_variable m_cond_NoEmpty;     /* 非空条件变量 */
};


/* =====================================================================
 * ***************************** 函数实现 *****************************
 * ===================================================================== */

/* 这个构造函数需要调用 setQueueSize 设置环形队列的大小 */
template<typename T>
RingQueue<T>::RingQueue() 
{
    
}

template<typename T>
RingQueue<T>::RingQueue(long capacity) 
{
    m_capacity = capacity;
    m_queue = new T[m_capacity] {};
}

/* 添加默认值 */
template<typename T>
RingQueue<T>::RingQueue(long capacity, T defaultValue)
{
    m_capacity = capacity;
    m_queue = new T[m_capacity] {};
    for(long i = 0; i < m_capacity; i++)
    {
        m_queue[i] = defaultValue;
    }
    m_defaultValue = defaultValue;
    m_isUseDefaultValue.store(true); // 设置使用默认值
}

template<typename T>
RingQueue<T>::~RingQueue()
{
    if(m_queue != nullptr)
    {
        delete[] m_queue;
        m_queue = nullptr;
    }
}


/* 清空队列 */
template<typename T>
void RingQueue<T>::clearQueue()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    if(m_queue != nullptr)
    {
        delete[] m_queue;
        m_queue = nullptr;
    }
    m_front = -1;
    m_rear = -1;
}


/*************** 入队 *******************/
template<typename T>
void RingQueue<T>::push(const T& value)
{
    {
        std::unique_lock<std::mutex> _lock(m_mutex);
        m_cond_NoFull.wait(_lock, [this]() {
            return (!_isFull() || m_isExit);
        });
        if(m_isExit)
        {
            return;
        }

        if(m_rear == -1)
        {
            m_front = 0;
            m_rear = 0;
        }

        m_queue[m_rear] = value;
        m_rear = (m_rear + 1) % m_capacity;
    }
    m_cond_NoEmpty.notify_all();
}

template<typename T>
void RingQueue<T>::push(T&& value)
{
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        m_cond_NoFull.wait(lock, [this](){
            return (!_isFull() || m_isExit);
        });
        if(m_isExit)
        {
            return;
        }

        if(m_rear == -1)
        {
            m_front = 0;
            m_rear = 0;
        }

        m_queue[m_rear] = std::move(value);
        m_rear = (m_rear + 1) % m_capacity;
    }

    m_cond_NoEmpty.notify_all();
}

/**
 * @brief 非阻塞的方式入队，如果队列已满，直接返回
 * 
 */
 template<typename T>
bool RingQueue<T>::push_noBlock(const T& value)
{
    {
        // std::unique_lock<std::mutex> lock(m_mutex, std::defer_lock);
        // if(!lock.try_lock())
        // {
        //     return false;
        // }
        std::lock_guard<std::mutex> lock(m_mutex);
        /* 先检查队列是否还有剩余空间 */
        if(_isFull())
        {
            return false;
        }
        else if(m_rear == -1)
        {
            m_front = 0;
            m_rear = 0;
        }

        m_queue[m_rear] = value;
        m_rear = (m_rear + 1) % m_capacity;
    }
    m_cond_NoEmpty.notify_all();
    return true;
}

template<typename T>
bool RingQueue<T>::push_noBlock(T&& value)
{
    {
        // std::unique_lock<std::mutex> lock(m_mutex, std::defer_lock);
        // if(!lock.try_lock())
        // {
        //     return false;
        // }
        std::lock_guard<std::mutex> lock(m_mutex);
        /* 先检查队列是否还有剩余空间 */
        if(_isFull())
        {
            return false;
        }
        else if(m_rear == -1)
        {
            m_front = 0;
            m_rear = 0;
        }

        m_queue[m_rear] = std::move(value);
        m_rear = (m_rear + 1) % m_capacity;
    }
    m_cond_NoEmpty.notify_all();
    return true;
}

/* 入队，队列满就出队一个，非阻塞 */
template<typename T>
T RingQueue<T>::push_pop(const T& value)
{
    T ret = _DefaultValue;
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        /* 如果队列已满，先出队一个元素 */
        if(_isFull())
        {
            ret = std::move(m_queue[m_front]);
            m_front = (m_front + 1) % m_capacity;
            if(m_front == m_rear)
            {
                m_front = -1;
                m_rear = -1;
            }
        }
        /* 入队新元素 */
        if(m_rear == -1)
        {
            m_front = 0;
            m_rear = 0;
        }
        m_queue[m_rear] = value;
        m_rear = (m_rear + 1) % m_capacity;
    }
    m_cond_NoEmpty.notify_all();
    return ret;
}


/**
 * @brief 出队，删除队列的首个元素
 *        注意，如果存储的是指针，需要手动释放该指针指向的内存区域，不然会造成内存泄漏
 * 
 * @tparam T 
 */
template<typename T>
void RingQueue<T>::pop()
{
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        if(_isEmpty())
        {
            return;
        }
        m_front = (m_front + 1) % m_capacity;
        if(m_front == m_rear)
        {
            m_front = -1;
            m_rear = -1;
        }
    }
    m_cond_NoFull.notify_all();
}


/* 获取队列中第一个值，但是不出队
 * 阻塞的方式获取，如果队列为空，会一直阻塞住，直到获取到数据为止 */
template<typename T>
T RingQueue<T>::front()
{
    
    std::unique_lock<std::mutex> lock(m_mutex);
    m_cond_NoEmpty.wait(lock, [this](){
        return (!isEmpty() || m_isExit);
    });
    if(m_isExit)
    {
        return _DefaultValue;
    }
    return m_queue[m_front];
    
}


/* 获取队列中第一个值，但是不出队，非阻塞的方式获取 */
template<typename T>
bool RingQueue<T>::front_noBlock(T& t)
{
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        if(_isEmpty())
        {
            return false;
        }
        t = m_queue[m_front];
    }
    return true;
}


/* 非阻塞方式获取第一个值，如果对列为空，则会返回设置的默认值 */
template<typename T>
T RingQueue<T>::front_noBlock()
{
    std::unique_lock<std::mutex> lock(m_mutex);
    if(_isEmpty())
    {
        return _DefaultValue;
    }
    return m_queue[m_front];
}

/* 获取对立第一个数据，获取完立刻出队
 * 如果队列为空，会阻塞住，直到有数据为止 */
template<typename T>
T RingQueue<T>::front_pop()
{
    // T ret = _DefaultValue;
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        m_cond_NoEmpty.wait(lock, [this](){
            return (!_isEmpty() || m_isExit);
        });
        /* 是否退出 */
        if(m_isExit)
        {
            return _DefaultValue;
        }
        /* 临时记录索引 */
        long front = m_front;
        m_front = (m_front + 1) % m_capacity;
        if(m_front == m_rear)
        {
            m_front = -1;
            m_rear = -1;
        }
        m_cond_NoFull.notify_all();
        return m_queue[front];
    }
}

/* 非阻塞方式获取第一个值，并出队 */
template<typename T>
bool RingQueue<T>::front_pop_noBlock(T& t)
{
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        if(_isEmpty())
        {
            return false;
        }
        t = std::move(m_queue[m_front]);
        m_front = (m_front + 1) % m_capacity;
        if(m_front == m_rear)
        {
            m_front = -1;
            m_rear = -1;
        }
    }
    m_cond_NoFull.notify_all();
    return true;
}

/* 非阻塞方式获取第一个值，并出队 */
template<typename T>
T RingQueue<T>::front_pop_noBlock()
{
    // T ret = _DefaultValue;
    {
        std::unique_lock<std::mutex> lock(m_mutex);
        // m_cond_NoEmpty.wait(lock, [this](){
        //     return (!_isEmpty() || m_isExit);
        // });
        if(_isEmpty())
        {
            return _DefaultValue;
        }
        /* 临时记录索引 */
        long front = m_front;
        
        m_front = (m_front + 1) % m_capacity;
        if(m_front == m_rear)
        {
            m_front = -1;
            m_rear = -1;
        }
        m_cond_NoFull.notify_all();
        return m_queue[front];
    }
}

/* 通过移动语义获取数据，获取完成后队列中的数据只是个空壳了，因此直接就出队了 */
template<typename T>
bool RingQueue<T>::front_pop_move(T& t)
{
    std::unique_lock<std::mutex> lock(m_mutex);
    m_cond_NoEmpty.wait(lock, [this]() {
        return (!_isEmpty() || m_isExit);
    });
    /* 是否退出 */
    if(m_isExit)
    {
        return false;
    }
    t = std::move(m_queue[m_front]); // 移动语义获取数据
    m_front = (m_front + 1) % m_capacity;
    if(m_front == m_rear)
    {
        m_front = -1;
        m_rear = -1;
    }
    
    m_cond_NoFull.notify_all();
    return true;
}

template<typename T>
bool RingQueue<T>::front_pop_move_noBlock(T& t)
{
    std::unique_lock<std::mutex> lock(m_mutex);
    // m_cond_NoEmpty.wait(lock, [this](){
    //     return (!_isEmpty() || m_isExit);
    // });
    if(_isEmpty())
    {
        return false;
    }
    t = std::move(m_queue[m_front]); // 移动语义获取数据
    
    m_front = (m_front + 1) % m_capacity;
    if(m_front == m_rear)
    {
        m_front = -1;
        m_rear = -1;
    }
    m_cond_NoFull.notify_all();

    return true;
}


/**
 * @brief 设置队列大小
 *        注意：使用这个设置，如果队列中存储的是指针，指针的内存区域需要在调用这个函数之前释放，不然可能会造成
 *              内存泄漏
 * 
 * @tparam T 
 * @param size 
 */
template<typename T>
void RingQueue<T>::setQueueCapacity(long size)
{
    if(m_queue != nullptr)
    {
        delete[] m_queue;
        m_queue = nullptr;
    }

    m_capacity = size;
    m_front = -1;
    m_rear = -1;
    m_queue = new T[m_capacity];
}


/* 设置默认值，给指针类型使用，如果是非阻塞获取，空的时候可以返回为设置的默认值（如nullptr） */
template<typename T>
void RingQueue<T>::setDefaultValue(T defaultValue)
{
    m_defaultValue = defaultValue;
    m_isUseDefaultValue.store(true); // 设置使用默认值
}

/* 获取队列中有效值的大小 */
template<typename T>
long RingQueue<T>::QueueSize()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    if(m_rear == -1)
    {
        return 0;
    }
    else if(m_rear > m_front)
    {
        return m_rear - m_front;
    }
    else if(m_rear < m_front)
    {
        return m_capacity - ( m_front - m_rear );
    }
    /* 这时候是队列满 */
    return m_capacity;
}

/* 获取队列容量 */
template<typename T>
long RingQueue<T>::QueueCapacity()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    return m_capacity;
}

/**
 * @brief 判断队列是否为空
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template<typename T>
bool RingQueue<T>::isEmpty()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    return _isEmpty();
}

/**
 * @brief 判断队列是否已满，这里判断依赖入队和出队后的队头和队尾指针的位置
 *        1、队头和队尾指针相等，但是队尾指针不等于-1，表示队列已满
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template<typename T>
bool RingQueue<T>::isFull()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    return _isFull();
}

/* 退出所有可能的阻塞函数 */
template<typename T>
void RingQueue<T>::exit()
{
    m_isExit = true;
    m_cond_NoFull.notify_all();
    m_cond_NoEmpty.notify_all();
}

/* 判断是否空 */
template<typename T>
bool RingQueue<T>::_isEmpty()
{
    if((m_front == m_rear) && (m_front == -1))
    {
        return true;
    }
    return false;
}

/* 判断是否满 */
template<typename T>
inline bool RingQueue<T>::_isFull()
{
    /* 如果m_rear或者m_front不等于-1，说明此时里面有内容
     * 同时m_front == m_rear，队列就满了 */
    if(m_front == m_rear && m_rear != -1)
    {
        return true;
    }
    return false;
}



#endif /* RINGQUEUE_H */