deque.h

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

        swap(copy);
        return *this;
    }

    template<typename T>
    inline void Deque<T>::destroyAll()
    {
        if (m_start <= m_end)
            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
        else {
            TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
            TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
        }
    }

    template<typename T>
    inline Deque<T>::~Deque()
    {
        checkValidity();
        invalidateIterators();
        destroyAll();
    }

    template<typename T>
    inline void Deque<T>::swap(Deque<T>& other)
    {
        checkValidity();
        other.checkValidity();
        invalidateIterators();
        std::swap(m_start, other.m_start);
        std::swap(m_end, other.m_end);
        m_buffer.swap(other.m_buffer);
        checkValidity();
        other.checkValidity();
    }

    template<typename T>
    inline void Deque<T>::clear()
    {
        checkValidity();
        invalidateIterators();
        destroyAll();
        m_start = 0;
        m_end = 0;
        checkValidity();
    }

    template<typename T>
    template<typename Predicate>
    inline DequeIterator<T> Deque<T>::findIf(Predicate& predicate)
    {
        iterator end_iterator = end();
        for (iterator it = begin(); it != end_iterator; ++it) {
            if (predicate(*it))
                return it;
        }
        return end_iterator;
    }

    template<typename T>
    inline void Deque<T>::expandCapacityIfNeeded()
    {
        if (m_start) {
            if (m_end + 1 != m_start)
                return;
        } else if (m_end) {
            if (m_end != m_buffer.capacity() - 1)
                return;
        } else if (m_buffer.capacity())
            return;

        expandCapacity();
    }

    template<typename T>
    void Deque<T>::expandCapacity()
    {
        checkValidity();
        size_t oldCapacity = m_buffer.capacity();
        size_t newCapacity = max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
        T* oldBuffer = m_buffer.buffer();
        m_buffer.allocateBuffer(newCapacity);
        if (m_start <= m_end)
            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
        else {
            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
            size_t newStart = newCapacity - (oldCapacity - m_start);
            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
            m_start = newStart;
        }
        m_buffer.deallocateBuffer(oldBuffer);
        checkValidity();
    }

    template<typename T> template<typename U>
    inline void Deque<T>::append(const U& value)
    {
        checkValidity();
        expandCapacityIfNeeded();
        new (&m_buffer.buffer()[m_end]) T(value);
        if (m_end == m_buffer.capacity() - 1)
            m_end = 0;
        else
            ++m_end;
        checkValidity();
    }

    template<typename T> template<typename U>
    inline void Deque<T>::prepend(const U& value)
    {
        checkValidity();
        expandCapacityIfNeeded();
        if (!m_start)
            m_start = m_buffer.capacity() - 1;
        else
            --m_start;
        new (&m_buffer.buffer()[m_start]) T(value);
        checkValidity();
    }

    template<typename T>
    inline void Deque<T>::removeFirst()
    {
        checkValidity();
        invalidateIterators();
        ASSERT(!isEmpty());
        TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
        if (m_start == m_buffer.capacity() - 1)
            m_start = 0;
        else
            ++m_start;
        checkValidity();
    }

    template<typename T>
    inline void Deque<T>::remove(iterator& it)
    {
        it.checkValidity();
        remove(it.m_index);
    }

    template<typename T>
    inline void Deque<T>::remove(const_iterator& it)
    {
        it.checkValidity();
        remove(it.m_index);
    }

    template<typename T>
    inline void Deque<T>::remove(size_t position)
    {
        if (position == m_end)
            return;

        checkValidity();
        invalidateIterators();

        T* buffer = m_buffer.buffer();
        TypeOperations::destruct(&buffer[position], &buffer[position + 1]);

        // Find which segment of the circular buffer contained the remove element, and only move elements in that part.
        if (position >= m_start) {
            TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
            m_start = (m_start + 1) % m_buffer.capacity();
        } else {
            TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
            m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
        }
        checkValidity();
    }

#ifdef NDEBUG
    template<typename T> inline void DequeIteratorBase<T>::checkValidity() const { }
    template<typename T> inline void DequeIteratorBase<T>::checkValidity(const DequeIteratorBase<T>&) const { }
    template<typename T> inline void DequeIteratorBase<T>::addToIteratorsList() { }
    template<typename T> inline void DequeIteratorBase<T>::removeFromIteratorsList() { }
#else
    template<typename T>
    void DequeIteratorBase<T>::checkValidity() const
    {
        ASSERT(m_deque);
        m_deque->checkIndexValidity(m_index);
    }

    template<typename T>
    void DequeIteratorBase<T>::checkValidity(const Base& other) const
    {
        checkValidity();
        other.checkValidity();
        ASSERT(m_deque == other.m_deque);
    }

    template<typename T>
    void DequeIteratorBase<T>::addToIteratorsList()
    {
        if (!m_deque)
            m_next = 0;
        else {
            m_next = m_deque->m_iterators;
            m_deque->m_iterators = this;
            if (m_next)
                m_next->m_previous = this;
        }
        m_previous = 0;
    }

    template<typename T>
    void DequeIteratorBase<T>::removeFromIteratorsList()
    {
        if (!m_deque) {
            ASSERT(!m_next);
            ASSERT(!m_previous);
        } else {
            if (m_next) {
                ASSERT(m_next->m_previous == this);
                m_next->m_previous = m_previous;
            }
            if (m_previous) {
                ASSERT(m_deque->m_iterators != this);
                ASSERT(m_previous->m_next == this);
                m_previous->m_next = m_next;
            } else {
                ASSERT(m_deque->m_iterators == this);
                m_deque->m_iterators = m_next;
            }
        }
        m_next = 0;
        m_previous = 0;
    }
#endif

    template<typename T>
    inline DequeIteratorBase<T>::DequeIteratorBase()
        : m_deque(0)
    {
    }

    template<typename T>
    inline DequeIteratorBase<T>::DequeIteratorBase(const Deque<T>* deque, size_t index)
        : m_deque(const_cast<Deque<T>*>(deque))
        , m_index(index)
    {
        addToIteratorsList();
        checkValidity();
    }

    template<typename T>
    inline DequeIteratorBase<T>::DequeIteratorBase(const Base& other)
        : m_deque(other.m_deque)
        , m_index(other.m_index)
    {
        addToIteratorsList();
        checkValidity();
    }

    template<typename T>
    inline DequeIteratorBase<T>& DequeIteratorBase<T>::operator=(const Base& other)
    {
        checkValidity();
        other.checkValidity();
        removeFromIteratorsList();

        m_deque = other.m_deque;
        m_index = other.m_index;
        addToIteratorsList();
        checkValidity();
        return *this;
    }

    template<typename T>
    inline DequeIteratorBase<T>::~DequeIteratorBase()
    {
#ifndef NDEBUG
        removeFromIteratorsList();
        m_deque = 0;
#endif
    }

    template<typename T>
    inline bool DequeIteratorBase<T>::isEqual(const Base& other) const
    {
        checkValidity(other);
        return m_index == other.m_index;
    }

    template<typename T>
    inline void DequeIteratorBase<T>::increment()
    {
        checkValidity();
        ASSERT(m_index != m_deque->m_end);
        ASSERT(m_deque->m_buffer.capacity());
        if (m_index == m_deque->m_buffer.capacity() - 1)
            m_index = 0;
        else
            ++m_index;
        checkValidity();
    }

    template<typename T>
    inline void DequeIteratorBase<T>::decrement()
    {
        checkValidity();
        ASSERT(m_index != m_deque->m_start);
        ASSERT(m_deque->m_buffer.capacity());
        if (!m_index)
            m_index = m_deque->m_buffer.capacity() - 1;
        else
            --m_index;
        checkValidity();
    }

    template<typename T>
    inline T* DequeIteratorBase<T>::after() const
    {
        checkValidity();
        ASSERT(m_index != m_deque->m_end);
        return &m_deque->m_buffer.buffer()[m_index];
    }

    template<typename T>
    inline T* DequeIteratorBase<T>::before() const
    {
        checkValidity();
        ASSERT(m_index != m_deque->m_start);
        if (!m_index)
            return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
        return &m_deque->m_buffer.buffer()[m_index - 1];
    }

} // namespace WTF

using WTF::Deque;

#endif // WTF_Deque_h