External/module/RingQueue/RingQueueManualMutex.hpp

#ifndef _RINGQUEUE_MANUAL_MUTEX_HPP_
#define _RINGQUEUE_MANUAL_MUTEX_HPP_

/**
 * @brief 这里采用零公摊的方式，设置多大的空间，就有多大的空间可以使用
 *        1、m_rear指向最新入队的元素的下一个位置，就是下个将要入队的元素位置
 *        2、m_front指向需要出队的第一个元素
 *        3、环形队列自带互斥锁，但是不会自动加锁，需要外部手动上锁
 *        
 * 使用说明:
 *      因为是外部手动上锁，所以这里所有的函数都是非阻塞函数
 *          1、入队时如果队列满，则会自动出队一个元素，入读函数的返回值则是出队的元素，
 *             如果队列中是指针，需要手动释放
 *          2、出队时如果队列为空，则会返回默认构建的元素值，尽量设置一个默认元素，会返
 *             回这个默认元素
 *
 * 判断队列满：
 *        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 模版类型
 */

#include <atomic>
#include <mutex>
#include <iostream>

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

template<typename T>
class RingQueueManualMutex
{
    RingQueueManualMutex(RingQueueManualMutex<T>&& queue) = delete;
    RingQueueManualMutex<T>& operator=(RingQueueManualMutex<T>&& queue) = delete;

public:
    RingQueueManualMutex();
    RingQueueManualMutex(long size);
    RingQueueManualMutex(long size, T defaultValue);
    /* 拷贝和赋值构造函数内部都不会自动上锁，需要在外部手动上锁
     * 如果存储的是指针，需要在外部手动拷贝，否则拷贝的是指针而已 */
    RingQueueManualMutex(const RingQueueManualMutex<T>& queue);
    RingQueueManualMutex<T> operator=(const RingQueueManualMutex<T>& queue);

    ~RingQueueManualMutex();



    /* 入队 */
    T push(const T& value);
    T push(T&& value);

    /* 获取队列中第一个值，但是不出队，
     * 非阻塞的方式获取，如果队列为空，会返回一个默认值 */
    T front();

    /* 获取对立第一个数据，获取完立刻出队
     * 如果删除了拷贝构造函数，使用会报错 */
    T front_pop();

    /* 获取最后一个值，最后一个值不会出队 */
    T back();
    bool back(T& value);

    /* 根据下标获取某个位置的元素，下标0就是下一个要出队的位置
     * 这里获取元素不会出队 */
    T operator[](long index);
    T at(long index) const;
    
    /* 设置队列大小 */
    void setQueueCapacity(long size);
    /* 设置默认值，给指针类型使用，如果是非阻塞获取，空的时候可以返回为设置的默认值（如nullptr） */
    void setDefaultValue(T defaultValue);
    /* 获取队列大小，队列中有效值的大小 */
    long QueueSize() const;
    /* 获取队列容量 */
    long QueueCapacity() const;
    /* 判断队列是否为空 */
    bool isEmpty() const;
    /* 判断队列是否已满 */
    bool isFull() const;
    /* 清空队列 */
    void clearQueue();

public:
    std::mutex mutex;                       /* 互斥锁 */
private:
    /* 判断是否空 */
    inline bool _isEmpty() const;
    /* 判断是否满 */
    inline bool _isFull() const;

private:    
    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;     /* 非空条件变量 */

public:
    /* 定义迭代器 */
    class Iterator
    {
    public:
        // Iterator(RingQueueManualMutex<T>* queue) : m_ptr(queue), m_index(m_ptr->m_front) {}
        Iterator(RingQueueManualMutex<T>* queue, long index) : m_ptr(queue), m_index(index) {}

        T& operator*() { 
            if(m_index == -1)
            {
                throw std::out_of_range("Iterator out of range");
            }
            return m_ptr->m_queue[m_index]; 
        }
        T* operator->() {
            if(m_index == -1)
            {
                throw std::out_of_range("Iterator out of range");
            }
            return &m_ptr->m_queue[m_index];
        }

        Iterator& operator++() {
            m_index = (m_index + 1) % m_ptr->m_capacity;
            if(m_index == m_ptr->m_rear)
            {
                m_index = -1; // 到达末尾
            }
            return *this;
        }
        Iterator operator++(int) {
            Iterator tmp = *this;  // 先保存旧值
            ++(*this);             // 复用前置 ++
            return tmp;            // 返回修改前的迭代器副本
        }
        /* 自减比较复杂，迭代器使用 -1 表示 end()，如果 end() 自减，则需要判断是空还是满
         */
        Iterator& operator--() {
            /* 等于 -1 说明是结尾，判断是空还是满 */
            if(m_index == -1)
            {
                if(m_ptr->isEmpty())
                {
                    /* 是空，返回自身 */
                    return *this;
                }
                else if(m_ptr->isFull())
                {
                    m_index = (m_ptr->m_rear - 1 + m_ptr->m_capacity) % m_ptr->m_capacity;
                }
            }else 
            {
                if(m_ptr->m_front == m_index)
                {
                    m_index = -1; // 到达开头前面
                } else
                {
                    m_index = (m_index - 1 + m_ptr->m_capacity) % m_ptr->m_capacity;
                }
            }
            return *this;
        }
        Iterator operator--(int) {
            Iterator tmp = *this;  // 先保存旧值
            --(*this);             // 复用前置 --
            return tmp;            // 返回修改前的迭代器副本
        }

        bool operator!=(const Iterator& other) const {
            if(m_ptr != other.m_ptr)
                return true;
            if(m_index == other.m_index)
                return false;
            return true;
        }
        bool operator==(const Iterator& other) const {
            if(m_ptr != other.m_ptr)
                return false;
            if(m_index != other.m_index)
                return false;
            return true;
        }

    private:
        RingQueueManualMutex<T>* m_ptr = nullptr;
        long m_index = -1;
    };

    Iterator begin() { return Iterator(this, m_front); }
    Iterator end() { return Iterator(this, -1); }
};


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

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

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

/* 添加默认值 */
template<typename T>
RingQueueManualMutex<T>::RingQueueManualMutex(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>
RingQueueManualMutex<T>::RingQueueManualMutex(const RingQueueManualMutex<T>& queue)
{
    m_capacity = queue.m_capacity;
    m_front = queue.m_front;
    m_rear = queue.m_rear;
    m_defaultValue = queue.m_defaultValue;
    m_isUseDefaultValue.store(queue.m_isUseDefaultValue.load());
    
    if(m_queue != nullptr)
    {
        delete[] m_queue;
        m_queue = nullptr;
    }
    
    if(m_capacity > 0)
    {
        m_queue = new T[m_capacity];
        for(long i = 0; i < m_capacity; i++)
        {
            m_queue[i] = queue.m_queue[i];
        }
    }
}

template<typename T>
RingQueueManualMutex<T> RingQueueManualMutex<T>::operator=(const RingQueueManualMutex<T>& queue)
{
    if(this == &queue)
    {
        return *this; // 防止自赋值
    }

    m_capacity = queue.m_capacity;
    m_front = queue.m_front;
    m_rear = queue.m_rear;
    m_defaultValue = queue.m_defaultValue;
    m_isUseDefaultValue.store(queue.m_isUseDefaultValue.load());

    if(m_queue != nullptr)
    {
        delete[] m_queue;
        m_queue = nullptr;
    }

    if(m_capacity > 0)
    {
        m_queue = new T[m_capacity];
        for(long i = 0; i < m_capacity; i++)
        {
            m_queue[i] = queue.m_queue[i];
        }
    }

    return *this;
}


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


/*************** 入队 *******************/
template<typename T>
T  RingQueueManualMutex<T>::push(const T& value)
{
    T ret = _DefaultValue;
    if(_isFull())
    {
        /* 队列已满，先出队一个元素 */
        ret = std::move(m_queue[m_front]);
        /* 出队后，前进一个位置 */
        m_front = (m_front + 1) % m_capacity;
    }
    // std::cout << "m_front: " << m_front << "  m_rear: " << m_rear << std::endl;
    if(m_rear == -1)
    {
        m_front = 0;
        m_rear = 0;
    }
    m_queue[m_rear] = value;
    m_rear = (m_rear + 1) % m_capacity;

    return std::move(ret);
}

template<typename T>
T  RingQueueManualMutex<T>::push(T&& value)
{
    T ret = _DefaultValue; // 默认值
    if(_isFull())
    {
        /* 队列已满，先出队一个元素 */
        ret = std::move(m_queue[m_front]);
        /* 出队后，前进一个位置 */
        m_front = (m_front + 1) % m_capacity;
    }
    if(m_rear == -1)
    {
        m_front = 0;
        m_rear = 0;
    }
    m_queue[m_rear] = std::move(value);
    m_rear = (m_rear + 1) % m_capacity;

    return std::move(ret);
}


/* 获取队列中第一个值，但是不出队
 * 阻塞的方式获取，如果队列为空，会一直阻塞住，直到获取到数据为止 */
template<typename T>
T RingQueueManualMutex<T>::front()
{
    if(_isEmpty())
    {
        return _DefaultValue; // 如果队列为空，返回默认值
    }
    return m_queue[m_front];
}



/* 获取对立第一个数据，获取完立刻出队 */
template<typename T>
T RingQueueManualMutex<T>::front_pop()
{
    if(_isEmpty())
    {
        return _DefaultValue; // 如果队列为空，返回默认值
    }
    // int ret = m_front;
    T 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;
    }

    return std::move(ret);
}

/* 获取最后一个值，最后一个值不会出队 */
template<typename T>
T RingQueueManualMutex<T>::back()
{
    if(_isEmpty())
    {
        return _DefaultValue; // 如果队列为空，返回默认值
    }
    return m_queue[(m_rear - 1 + m_capacity) % m_capacity];
}

template<typename T>
bool RingQueueManualMutex<T>::back(T& value)
{
    if(_isEmpty())
    {
        return false;
    }
    value = m_queue[(m_rear - 1 + m_capacity) % m_capacity];
    return true;
}

/* 根据下标获取某个位置的元素，下标0就是下一个要出队的位置
 * 这里获取元素不会出队 */
template<typename T>
T RingQueueManualMutex<T>::operator[](long index)
{
    if(_isEmpty())
    {
        return _DefaultValue; // 如果队列为空，返回默认值
    }
    if(index >= QueueSize() || index < -QueueSize())
    {
        return _DefaultValue;
    }
    if(index < 0)
    {
        index += m_capacity; // 处理负数索引
    }
    long realIndex = (index + m_front) % m_capacity;
    
    return m_queue[realIndex];
}


template<typename T>
T RingQueueManualMutex<T>::at(long index) const
{
    if(_isEmpty())
    {
        return _DefaultValue; // 如果队列为空，返回默认值
    }
    if(index >= QueueSize() || index < -QueueSize())
    {
        return _DefaultValue;
    }
    if(index < 0)
    {
        index += m_capacity; // 处理负数索引
    }
    long realIndex = (index + m_front) % m_capacity;
    
    return m_queue[realIndex];
}


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

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

/**
 * @brief 判断队列是否为空
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template<typename T>
bool RingQueueManualMutex<T>::isEmpty() const
{
    return _isEmpty();
}

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

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

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

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



#endif /* _RINGQUEUE_MANUAL_MUTEX_HPP_ */