fc_queue.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
// vim:tabstop=4:shiftwidth=4:expandtab:

/*
 * Copyright (C) 2009-2016 Wu Yongwei <adah at users dot sourceforge dot net>
 *
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any
 * damages arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute
 * it freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must
 *    not claim that you wrote the original software.  If you use this
 *    software in a product, an acknowledgement in the product
 *    documentation would be appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must
 *    not be misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source
 *    distribution.
 *
 * This file is part of Stones of Nvwa:
 *      http://sourceforge.net/projects/nvwa
 *
 */

#ifndef NVWA_FC_QUEUE_H
#define NVWA_FC_QUEUE_H

#include <assert.h>             // assert
#include <stddef.h>             // ptrdiff_t/size_t/NULL
#include <memory>               // std::allocator
#include <new>                  // placement new
#include "_nvwa.h"              // NVWA_NAMESPACE_*
#include "c++11.h"              // _NOEXCEPT/_NOEXCEPT_/_NULLPTR
#include "type_traits.h"        // nvwa::is_trivially_destructible

#if NVWA_CXX11_MODE
#include <utility>              // std::swap/std::declval
#else
#include <algorithm>            // std::swap
#endif

NVWA_NAMESPACE_BEGIN

template <class _Tp, class _Alloc = std::allocator<_Tp> >
class fc_queue
{
public:
    typedef _Tp                 value_type;
    typedef _Alloc              allocator_type;
    typedef size_t              size_type;
    typedef value_type*         pointer;
    typedef const value_type*   const_pointer;
    typedef value_type&         reference;
    typedef const value_type&   const_reference;

    explicit fc_queue(size_type max_size,
                      const allocator_type& alloc = allocator_type())
        : _M_alloc(alloc)
    {
        assert(max_size != 0);
        if (max_size + 1 == 0)
            throw std::bad_alloc();
        _M_begin = _M_alloc.allocate(max_size + 1);
        _M_end = _M_begin + max_size + 1;
        _M_head = _M_tail = _M_begin;
    }

    fc_queue(const fc_queue& rhs);

    ~fc_queue()
    {
        while (_M_head != _M_tail)
        {
            destroy(_M_head);
            _M_head = increment(_M_head);
        }
        if (_M_begin)
            _M_alloc.deallocate(_M_begin, _M_end - _M_begin);
    }

    fc_queue& operator=(const fc_queue& rhs)
    {
        fc_queue temp(rhs);
        swap(temp);
        return *this;
    }

    bool empty() const _NOEXCEPT
    {
        return _M_head == _M_tail;
    }

    bool full() const _NOEXCEPT
    {
        return _M_head == increment(_M_tail);
    }

    size_type capacity() const _NOEXCEPT
    {
        return _M_end - _M_begin - 1;
    }

    size_type size() const _NOEXCEPT
    {
        ptrdiff_t dist = _M_tail - _M_head;
        if (dist < 0)
            dist += _M_end - _M_begin;
        return dist;
    }

    reference front()
    {
        assert(!empty());
        return *_M_head;
    }

    const_reference front() const
    {
        assert(!empty());
        return *_M_head;
    }

    reference back()
    {
        assert(!empty());
        return *decrement(_M_tail);
    }

    const_reference back() const
    {
        assert(!empty());
        return *decrement(_M_tail);
    };

    void push(const value_type& value)
    {
        construct(_M_tail, value);
        if (full())
            pop();
        _M_tail = increment(_M_tail);
    }

    void pop()
    {
        assert(!empty());
        destroy(_M_head);
        _M_head = increment(_M_head);
    }

    bool contains(const value_type& value) const
    {
        pointer ptr = _M_head;
        while (ptr != _M_tail)
        {
            if (*ptr == value)
                return true;
            ptr = increment(ptr);
        }
        return false;
    }

    void swap(fc_queue& rhs)
        _NOEXCEPT_(noexcept(std::swap(std::declval<allocator_type&>(),
                                      std::declval<allocator_type&>())))
    {
        using std::swap;
        swap(_M_alloc, rhs._M_alloc);
        swap(_M_head,  rhs._M_head);
        swap(_M_tail,  rhs._M_tail);
        swap(_M_begin, rhs._M_begin);
        swap(_M_end,   rhs._M_end);
    }

    allocator_type get_allocator() const
    {
        return _M_alloc;
    }

protected:
    pointer         _M_head;
    pointer         _M_tail;
    pointer         _M_begin;
    pointer         _M_end;
    allocator_type  _M_alloc;

protected:
    pointer increment(pointer ptr) const _NOEXCEPT
    {
        ++ptr;
        if (ptr == _M_end)
            ptr = _M_begin;
        return ptr;
    }
    pointer decrement(pointer ptr) const _NOEXCEPT
    {
        if (ptr == _M_begin)
            ptr = _M_end;
        return --ptr;
    }
    void construct(void* ptr, const _Tp& value)
    {
        new (ptr) _Tp(value);
    }
    void destroy(void* ptr) _NOEXCEPT_(noexcept(std::declval<_Tp*>()->~_Tp()))
    {
        _M_destroy(ptr, is_trivially_destructible<_Tp>());
    }

private:
    void _M_destroy(void*, true_type)
    {}
    void _M_destroy(void* ptr, false_type)
    {
        ((_Tp*)ptr)->~_Tp();
    }
};

template <class _Tp, class _Alloc>
fc_queue<_Tp, _Alloc>::fc_queue(const fc_queue& rhs)
    : _M_head(_NULLPTR), _M_tail(_NULLPTR), _M_begin(_NULLPTR)
{
    fc_queue temp(rhs.capacity(), rhs.get_allocator());
    pointer ptr = rhs._M_head;
    while (ptr != rhs._M_tail)
    {
        temp.push(*ptr);
        ptr = rhs.increment(ptr);
    }
    swap(temp);
}

template <class _Tp, class _Alloc>
void swap(fc_queue<_Tp, _Alloc>& lhs, fc_queue<_Tp, _Alloc>& rhs)
    _NOEXCEPT_(noexcept(lhs.swap(rhs)))
{
    lhs.swap(rhs);
}

NVWA_NAMESPACE_END

#endif // NVWA_FC_QUEUE_H