/*
    Copyright 2005-2010 Intel Corporation.  All Rights Reserved.

    This file is part of Threading Building Blocks.

    Threading Building Blocks is free software; you can redistribute it
    and/or modify it under the terms of the GNU General Public License
    version 2 as published by the Free Software Foundation.

    Threading Building Blocks is distributed in the hope that it will be
    useful, but WITHOUT ANY WARRANTY; without even the implied warranty
    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Threading Building Blocks; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    As a special exception, you may use this file as part of a free software
    library without restriction.  Specifically, if other files instantiate
    templates or use macros or inline functions from this file, or you compile
    this file and link it with other files to produce an executable, this
    file does not by itself cause the resulting executable to be covered by
    the GNU General Public License.  This exception does not however
    invalidate any other reasons why the executable file might be covered by
    the GNU General Public License.
*/

#ifndef _TBB_intrusive_list_H
#define _TBB_intrusive_list_H

#include "tbb/tbb_stddef.h"

#if __TBB_ARENA_PER_MASTER

namespace tbb {
namespace internal {

//! Data structure to be inherited by the types that can form intrusive lists.
/** Intrusive list is formed by means of the member_intrusive_list<T> template class.
    Note that type T must derive from intrusive_list_node either publicly or 
    declare instantiation member_intrusive_list<T> as a friend.
    This class implements a limited subset of std::list interface. **/
struct intrusive_list_node {
    intrusive_list_node *my_prev_node,
                        *my_next_node;
#if TBB_USE_ASSERT
    intrusive_list_node () { my_prev_node = my_next_node = this; }
#endif /* TBB_USE_ASSERT */
};

//! List of element of type T, where T is derived from intrusive_list_node
/** The class is not thread safe. **/
template <class List, class T>
class intrusive_list_base {
    //! Pointer to the head node
    intrusive_list_node my_head;

    //! Number of list elements
    size_t my_size;

    static intrusive_list_node& node ( T& item ) { return List::node(item); }

    static T& item ( intrusive_list_node* node ) { return List::item(node); }

    template<class Iterator>
    class iterator_impl {
        Iterator& self () { return *static_cast<Iterator*>(this); }

        //! Pointer to the head of the list being iterated
        intrusive_list_node *my_list_head;

        //! Node the iterator points to at the moment
        intrusive_list_node *my_pos;

    protected:
        iterator_impl ( intrusive_list_node* head, intrusive_list_node* pos )
            : my_list_head(head), my_pos(pos)
        {}

        T& item () const {
            //return *reinterpret_cast<T*>((char*)my_pos - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
            return intrusive_list_base::item(my_pos);
        }

    public:
        iterator_impl () : my_list_head(NULL), my_pos(NULL) {}
        
        bool operator == ( const Iterator& it ) const {
            return my_pos == it.my_pos;
        }

        bool operator != ( const Iterator& it ) const {
            return my_pos != it.my_pos;
        }

        Iterator& operator++ () {
            my_pos = my_pos->my_next_node;
            return self();
        }

        Iterator& operator-- () {
            my_pos = my_pos->my_prev_node;
            return self();
        }

        Iterator operator++ ( int ) {
            Iterator result = self();
            ++(*this);
            return result;
        }

        Iterator operator-- ( int ) {
            Iterator result = self();
            --(*this);
            return result;
        }
    }; // intrusive_list_base::iterator_impl

    void assert_ok () const {
        __TBB_ASSERT( (my_head.my_prev_node == &my_head && !my_size) || 
                      (my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" );
#if TBB_USE_ASSERT >= 2
        size_t i = 0;
        for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node )
            ++i;
        __TBB_ASSERT( my_size == i, "Wrong size" );
#endif /* TBB_USE_ASSERT >= 2 */
    }

public:
    class iterator : public iterator_impl<iterator> {
        template <class U, class V> friend class intrusive_list_base;

        iterator ( intrusive_list_node* head, intrusive_list_node* pos )
            : iterator_impl<iterator>( head, pos )
        {}
    public:
        iterator () {}
        
        T* operator-> () const { return &this->item(); }

        T& operator* () const { return this->item(); }
    }; // class iterator

    class const_iterator : public iterator_impl<const_iterator> {
        template <class U, class V> friend class intrusive_list_base;

        const_iterator ( const intrusive_list_node* head, const intrusive_list_node* pos )
            : iterator_impl<const_iterator>( const_cast<intrusive_list_node*>(head), const_cast<intrusive_list_node*>(pos) )
        {}
    public:
        const_iterator () {}
        
        const T* operator-> () const { return &this->item(); }

        const T& operator* () const { return this->item(); }
    }; // class iterator

    intrusive_list_base () : my_size(0) {
        my_head.my_prev_node = &my_head;
        my_head.my_next_node = &my_head;
    }

    bool empty () const { return my_head.my_next_node == &my_head; }

    size_t size () const { return my_size; }

    iterator begin () { return iterator(&my_head, my_head.my_next_node); }

    iterator end () { return iterator(&my_head, &my_head); }

    const_iterator begin () const { return const_iterator(&my_head, my_head.my_next_node); }

    const_iterator end () const { return const_iterator(&my_head, &my_head); }

    void push_front ( T& val ) {
        __TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val), 
                    "Object with intrusive list node can be part of only one intrusive list simultaneously" );
        // An object can be part of only one intrusive list at the given moment via the given node member 
        node(val).my_prev_node = &my_head;
        node(val).my_next_node = my_head.my_next_node;
        my_head.my_next_node->my_prev_node = &node(val);
        my_head.my_next_node = &node(val);
        ++my_size;
        assert_ok();
    }

    void remove( T& val ) {
        __TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" );
        --my_size;
        node(val).my_next_node->my_prev_node = node(val).my_prev_node;
        node(val).my_prev_node->my_next_node = node(val).my_next_node;
#if TBB_USE_ASSERT
        node(val).my_prev_node = node(val).my_next_node = &node(val);
#endif
        assert_ok();
    }

    iterator erase ( iterator it ) {
        T& val = *it;
        ++it;
        remove( val );
        return it;
    }

}; // intrusive_list_base


//! Double linked list of items of type T containing a member of type intrusive_list_node.
/** NodePtr is a member pointer to the node data field. Class U is either T or 
    a base class of T containing the node member. Default values exist for the sake
    of a partial specialization working with inheritance case.

    The list does not have ownership of its items. Its purpose is to avoid dynamic 
    memory allocation when forming lists of existing objects.

    The class is not thread safe. **/
template <class T, class U, intrusive_list_node U::*NodePtr>
class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>
{
    friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>;

    static intrusive_list_node& node ( T& val ) { return val.*NodePtr; }

    static T& item ( intrusive_list_node* node ) {
        // Cannot use __TBB_offestof (and consequently __TBB_get_object_ref) macro 
        // with *NodePtr argument because gcc refuses to interpret pasted "->" and "*"
        // as member pointer dereferencing operator, and explicit usage of ## in 
        // __TBB_offestof implementation breaks operations with normal member names.
        return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
    }
}; // intrusive_list<T, U, NodePtr>

//! Double linked list of items of type T that is derived from intrusive_list_node class.
/** The list does not have ownership of its items. Its purpose is to avoid dynamic 
    memory allocation when forming lists of existing objects.

    The class is not thread safe. **/
template <class T>
class intrusive_list : public intrusive_list_base<intrusive_list<T>, T>
{
    friend class intrusive_list_base<intrusive_list<T>, T>;

    static intrusive_list_node& node ( T& val ) { return val; }

    static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); }
}; // intrusive_list<T>

} // namespace internal
} // namespace tbb

#endif /* __TBB_ARENA_PER_MASTER */

#endif /* _TBB_intrusive_list_H */