External/common/RingQueue/RingQueue.hpp

#ifndef RINGQUEUE_H
#define RINGQUEUE_H

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

/**
 * @brief 这里采用零公摊的方式，设置多大的空间，就有多大的空间可以使用
 *        1、如果队列是空，m_rear和m_front都设置为-1
 *        2、m_rear指向最新入队的元素的下一个位置
 *        3、m_front指向需要出队的第一个元素
 *        4、环形队列自带互斥锁
 *
 * 判断队列满：
 *        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 模版类型
 */

template<typename T>
class RingQueue
{

public:
    RingQueue();
    RingQueue(long size);
    ~RingQueue();

    /* 设置队列大小 */
    void setQueueSize(long size);
    /* 入队 */
    bool enQueue(const T& data);
    bool enQueue(T&& data);
    /* 阻塞入队 */
    void enQueueBlock(const T& data);
    /* 出队 */
    bool deQueue(T& data);
    /* 阻塞出队 */
    T& deQueueBlock();

    /* 获取队列中第一个值（下一个出队的元素），但是不出队，非阻塞 */
    bool front(T& t);
    T& frontBlock();
    /* 获取队列中即将入队的位置（这个函数用于存储指针的环形队列，获取内存地址） */
    T& backBlock();

    /* 获取队列大小，队列中有效值的大小 */
    long getQueueSize();
    /* 获取队列容量 */
    long getQueueCapacity();
    /* 判断队列是否为空 */
    bool isEmpty();
    /* 判断队列是否已满 */
    bool isFull();

private:
    std::mutex m_mutex;                     /* 互斥锁 */
    T* m_queue = nullptr;                   /* 队列 */
    long m_capacity = 0;     /* 队列容量 */
    long m_front = 0;        /* 队头 */
    long m_rear = 0;         /* 队尾 */
    std::condition_variable m_cond_NoFull;      /* 非空条件变量 */
    std::condition_variable m_cond_NoEmpty;     /* 非满条件变量 */
};


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

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

template<typename T>
RingQueue<T>::RingQueue(long capacicy) : m_capacity(capacicy)
{
    m_front = -1;
    m_rear = -1;
    m_queue = new T[m_capacity];
}

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

/**
 * @brief 设置队列大小
 *        注意：使用这个设置，如果队列中存储的是指针，指针的内存区域需要在调用这个函数之前释放，不然可能会造成
 *              内存泄漏
 * 
 * @tparam T 
 * @param size 
 */
template<typename T>
void RingQueue<T>::setQueueSize(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];
}


/* 入队 */
template<typename T>
bool RingQueue<T>::enQueue(const T& data)
{
    m_mutex.lock();
    /* 先检查队列是否还有剩余空间 */
    if(isFull())
    {
        return false;
    }
    else if(m_rear == -1)
    {
        m_front = 0;
        m_rear = 0;
    }

    /* 数据入队 */
    m_queue[m_rear] = data;
    m_rear = (m_rear + 1) % m_capacity;

    m_mutex.unlock();
    m_cond_NoEmpty.notify_all();
    return true;
}

/* 入队，传入右值 */
template<typename T>
bool RingQueue<T>::enQueue(T&& data)
{
    m_mutex.lock();
    /* 先检查队列是否还有剩余空间 */
    if(isFull())
    {
        return false;
    }
    else if(m_rear == -1)
    {
        m_front = 0;
        m_rear = 0;
    }

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

    m_mutex.unlock();
    m_cond_NoEmpty.notify_all();
    return true;
}

/* 阻塞入队 */
template<typename T>
void RingQueue<T>::enQueueBlock(const T& data)
{
    m_mutex.lock();
    m_cond_NoFull.wait(m_mutex, [this](){
        return !isFull();
    });

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

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

/* 出队 */
template<typename T>
bool RingQueue<T>::deQueue(T& data)
{
    m_mutex.lock();
    if(isEmpty())
    {
        return false;
    }
    data = 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_mutex.unlock();
    m_cond_NoFull.notify_all();
    return true;
}

/* 出队 */
template<typename T>
T& RingQueue<T>::deQueueBlock()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    m_cond_NoEmpty.wait(lock, [this](){
        return !isEmpty();
    });

    long tmp = 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 std::move(m_queue[tmp]);
}

/* 获取队列中第一个值（下一个出队的元素），但是不出队，非阻塞 */
template<typename T>
bool RingQueue<T>::front(T& t)
{
    std::lock_guard<std::mutex> lock(m_mutex);
    if(isEmpty())
    {
        return false;
    }
    t = m_queue[m_front];
    return true;
}

/* 阻塞获取队列中第一个数据，但是不出队 */
template<typename T>
T& RingQueue<T>::frontBlock()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    m_cond_NoEmpty.wait(lock, [this](){
        return !isEmpty();
    });
    return m_queue[m_front];
}

/**
 * @brief 获取队列中即将入队的位置（这个函数用于存储指针的环形队列，获取内存地址）
 *        这个函数不一定内存安全，谨慎使用
 * 
 * @tparam T 
 * @return T& 
 */
template<typename T>
T& RingQueue<T>::backBlock()
{
    std::lock_guard<std::mutex> lock(m_mutex);
    m_cond_NoFull.wait(lock, [this](){
        return !isFull();
    });

    return m_queue[m_rear];
}

/* 获取队列中有效值的大小 */
template<typename T>
long RingQueue<T>::getQueueSize()
{
    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>::getQueueCapacity()
{
    return m_capacity;
}

/**
 * @brief 判断队列是否为空
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template<typename T>
bool RingQueue<T>::isEmpty()
{
    if((m_front == m_rear) && (m_front == -1))
    {
        return true;
    }

    return false;
}

/**
 * @brief 判断队列是否已满，这里判断依赖入队和出队后的队头和队尾指针的位置
 *        1、队头和队尾指针相等，但是队尾指针不等于-1，表示队列已满
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template<typename T>
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 */