Queue.h

Go to the documentation of this file.

#pragma once
 
 
#include "math/MathUtils.h"
#include "objects/containers/ArrayView.h"
#include <mm_malloc.h>
 
NAMESPACE_SPH_BEGIN
 
template <typename T, typename TCounter = Size>
class Queue : public Noncopyable {
private:
    using StorageType = typename WrapReferenceType<T>::Type;
 
    StorageType* data = nullptr;
 
    TCounter first = 0;
 
    TCounter last = 0;
 
    TCounter maxSize = 0;
 
public:
    Queue() = default;
 
    Queue(const TCounter size) {
        this->alloc(size, 0, 0);
        for (TCounter i = 0; i < maxSize; ++i) {
            new (data + i) StorageType();
        }
        last = maxSize;
    }
 
    Queue(std::initializer_list<StorageType> list) {
        this->alloc(list.size(), 0, 0);
        TCounter i = 0;
        for (auto& l : list) {
            new (data + i) StorageType(l);
            i++;
        }
        last = maxSize;
    }
 
    Queue(Queue&& other)
        : data(other.data)
        , first(other.first)
        , last(other.last)
        , maxSize(other.maxSize) {
        other.data = nullptr;
        other.first = other.last = other.maxSize = 0;
    }
 
    ~Queue() {
        for (TCounter i = first; i < last; ++i) {
            data[i].~StorageType();
        }
        if (data) {
            _mm_free(data);
            data = nullptr;
        }
    }
 
    Queue& operator=(Queue&& other) {
        std::swap(data, other.data);
        std::swap(first, other.first);
        std::swap(last, other.last);
        std::swap(maxSize, other.maxSize);
        return *this;
    }
 
    INLINE T& operator[](const TCounter idx) {
        SPH_ASSERT(idx < this->size());
        return data[first + idx];
    }
 
    INLINE const T& operator[](const TCounter idx) const {
        SPH_ASSERT(idx < this->size());
        return data[first + idx];
    }
 
    INLINE T& front() {
        SPH_ASSERT(!this->empty());
        return data[first];
    }
 
    INLINE const T& front() const {
        SPH_ASSERT(!this->empty());
        return data[first];
    }
 
    INLINE T& back() {
        SPH_ASSERT(!this->empty());
        return data[last - 1];
    }
 
    INLINE const T& back() const {
        SPH_ASSERT(!this->empty());
        return data[last - 1];
    }
 
    INLINE Size size() const {
        return last - first;
    }
 
    INLINE bool empty() const {
        return last == first;
    }
 
    void pushFront(const T& value) {
        if (first == 0) {
            // no place for new elements, needs to resize
            this->reserveFront(1);
        }
        SPH_ASSERT(first > 0);
        --first;
        new (data + first) StorageType();
        data[first] = value;
    }
 
    void pushBack(const T& value) {
        if (last == maxSize) {
            // no place for new elements, needs to resize
            this->reserveBack(1);
        }
        SPH_ASSERT(last < maxSize);
        ++last;
        new (data + last - 1) StorageType();
        data[last - 1] = value;
    }
 
    T popFront() {
        SPH_ASSERT(!this->empty());
        T value = this->front();
        data[first].~StorageType();
        ++first;
        return value;
    }
 
    T popBack() {
        SPH_ASSERT(!this->empty());
        T value = this->back();
        data[last - 1].~StorageType();
        --last;
        return value;
    }
 
    void clear() {
        for (TCounter i = first; i < last; ++i) {
            data[i].~StorageType();
        }
        last = first;
    }
 
    INLINE Iterator<StorageType> begin() {
        return Iterator<StorageType>(data + first, data + first, data + last);
    }
 
    INLINE Iterator<const StorageType> begin() const {
        return Iterator<const StorageType>(data + first, data + first, data + last);
    }
 
    INLINE Iterator<StorageType> end() {
        return Iterator<StorageType>(data + last, data + first, data + last);
    }
 
    INLINE Iterator<const StorageType> end() const {
        return Iterator<const StorageType>(data + last, data + first, data + last);
    }
 
    INLINE operator ArrayView<T, TCounter>() {
        return ArrayView<T, TCounter>(data + first, this->size());
    }
 
    INLINE operator ArrayView<const T, TCounter>() const {
        return ArrayView<const T, TCounter>(data + first, this->size());
    }
 
 
private:
    void alloc(const TCounter size, const TCounter extraFront, const TCounter extraBack) {
        maxSize = size + extraFront + extraBack;
        first = last = extraFront;
 
        data = (StorageType*)_mm_malloc(maxSize * sizeof(StorageType), alignof(StorageType));
    }
 
    void reserveFront(const TCounter num) {
        if (num > first) {
            Queue newQueue;
            newQueue.alloc(this->size(), max(num, this->size()), min(maxSize - last, this->size()));
            this->moveElements(std::move(newQueue));
        }
        SPH_ASSERT(num <= first);
    }
 
    void reserveBack(const TCounter num) {
        if (num > maxSize - last) {
            Queue newQueue;
            newQueue.alloc(this->size(), min(first, this->size()), max(num, this->size()));
            this->moveElements(std::move(newQueue));
        }
        SPH_ASSERT(num <= maxSize - last);
    }
 
    void moveElements(Queue&& newQueue) {
        newQueue.last = newQueue.first + this->size();
        SPH_ASSERT(newQueue.last <= newQueue.maxSize);
 
        // construct all element in the new queue using move constructor
        for (TCounter i = 0; i < this->size(); ++i) {
            new (newQueue.data + newQueue.first + i) StorageType(std::move(data[i + first]));
        }
        // replace queues
        *this = std::move(newQueue);
    }
};
 
NAMESPACE_SPH_END