/*
 *          Copyright Andrey Semashev 2007 - 2015.
 * Distributed under the Boost Software License, Version 1.0.
 *    (See accompanying file LICENSE_1_0.txt or copy at
 *          http://www.boost.org/LICENSE_1_0.txt)
 */
/*!
 * \file   attribute_set_impl.hpp
 * \author Andrey Semashev
 * \date   03.07.2010
 *
 * \brief  This header is the Boost.Log library implementation, see the library documentation
 *         at http://www.boost.org/doc/libs/release/libs/log/doc/html/index.html.
 */

#ifndef BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_
#define BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_

#include <new>
#include <memory>
#include <limits>
#include <utility>
#include <algorithm>
#include <cstddef>
#include <boost/assert.hpp>
#include <boost/array.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/intrusive/list.hpp>
#include <boost/intrusive/link_mode.hpp>
#include <boost/intrusive/derivation_value_traits.hpp>
#include <boost/log/attributes/attribute_set.hpp>
#include <boost/log/detail/header.hpp>

#ifndef BOOST_LOG_HASH_TABLE_SIZE_LOG
// Hash table size will be 2 ^ this value
#define BOOST_LOG_HASH_TABLE_SIZE_LOG 4
#endif

#ifndef BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE
// Maximum pool size that each attribute set maintains
#define BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE 8
#endif

namespace boost {

BOOST_LOG_OPEN_NAMESPACE

//! A simple pooling allocator
template< typename T >
class pool_allocator :
    public std::allocator< T >
{
public:
    template< typename U >
    struct rebind
    {
        typedef pool_allocator< U > other;
    };

    typedef std::allocator< T > base_type;

#if BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE > 0

    typedef typename base_type::value_type value_type;
    typedef typename base_type::size_type size_type;
    typedef typename base_type::difference_type difference_type;
    typedef typename base_type::pointer pointer;
    typedef typename base_type::const_pointer const_pointer;
    typedef typename base_type::reference reference;
    typedef typename base_type::const_reference const_reference;

private:
    array< pointer, BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE > m_Pool;
    size_type m_PooledCount;

public:
    pool_allocator() : m_PooledCount(0)
    {
    }

    pool_allocator(pool_allocator const& that) :
        base_type(static_cast< base_type const& >(that)),
        m_PooledCount(0)
    {
    }

    template< typename U >
    pool_allocator(pool_allocator< U > const& that) :
        base_type(static_cast< typename pool_allocator< U >::base_type const& >(that)),
        m_PooledCount(0)
    {
    }

    ~pool_allocator()
    {
        for (size_type i = 0; i < m_PooledCount; ++i)
        {
            base_type::deallocate(m_Pool[i], 1);
        }
    }

    pool_allocator& operator= (pool_allocator const& that)
    {
        base_type::operator= (static_cast< base_type const& >(that));
        return *this;
    }

    template< typename U >
    pool_allocator& operator= (pool_allocator< U > const& that)
    {
        base_type::operator= (
            static_cast< typename pool_allocator< U >::base_type const& >(that));
        return *this;
    }

    pointer allocate(size_type n, const void* hint = NULL)
    {
        if (m_PooledCount > 0)
        {
            --m_PooledCount;
            return m_Pool[m_PooledCount];
        }
        else
            return base_type::allocate(n, hint);
    }

    void deallocate(pointer p, size_type n)
    {
        if (m_PooledCount < m_Pool.size())
        {
            m_Pool[m_PooledCount] = p;
            ++m_PooledCount;
        }
        else
            base_type::deallocate(p, n);
    }

#else

    template< typename U >
    pool_allocator(pool_allocator< U > const& that) :
        base_type(static_cast< typename pool_allocator< U >::base_type const& >(that))
    {
    }

#endif // BOOST_LOG_ATTRIBUTE_SET_MAX_POOL_SIZE > 0
};

//! Attribute set implementation
struct attribute_set::implementation
{
public:
    //! Attribute name identifier type
    typedef key_type::id_type id_type;

    //! Allocator type
    typedef pool_allocator< node > node_allocator;

    //! Node base class traits for the intrusive list
    struct node_traits
    {
        typedef node_base node;
        typedef node* node_ptr;
        typedef node const* const_node_ptr;
        static node* get_next(const node* n) { return n->m_pNext; }
        static void set_next(node* n, node* next) { n->m_pNext = next; }
        static node* get_previous(const node* n) { return n->m_pPrev; }
        static void set_previous(node* n, node* prev) { n->m_pPrev = prev; }
    };

    //! Contained node traits for the intrusive list
    typedef intrusive::derivation_value_traits<
        node,
        node_traits,
        intrusive::normal_link
    > value_traits;

    //! The container that allows to iterate through elements
    typedef intrusive::list<
        node,
        intrusive::value_traits< value_traits >,
        intrusive::constant_time_size< true >
    > node_list;

    //! A hash table bucket
    struct bucket
    {
        //! Points to the first element in the bucket
        node* first;
        //! Points to the last element in the bucket (not the one after the last!)
        node* last;

        bucket() : first(NULL), last(NULL) {}
    };

    //! A list of buckets
    typedef boost::array< bucket, 1U << BOOST_LOG_HASH_TABLE_SIZE_LOG > buckets;

    //! Cleanup function object used to erase elements from the container
    struct disposer
    {
        typedef void result_type;

        explicit disposer(node_allocator& alloc) : m_Allocator(alloc)
        {
        }
        void operator() (node* p) const
        {
            p->~node();
            m_Allocator.deallocate(p, 1);
        }

    private:
        node_allocator& m_Allocator;
    };

private:
    //! List of nodes
    node_list m_Nodes;
    //! Node allocator
    node_allocator m_Allocator;
    //! Hash table buckets
    buckets m_Buckets;

public:
    implementation()
    {
    }

    implementation(implementation const& that) : m_Allocator(that.m_Allocator)
    {
        node_list::const_iterator it = that.m_Nodes.begin(), end = that.m_Nodes.end();
        for (; it != end; ++it)
        {
            node* const n = m_Allocator.allocate(1, NULL);
            new (n) node(it->m_Value.first, it->m_Value.second);
            m_Nodes.push_back(*n);

            bucket& b = get_bucket(it->m_Value.first.id());
            if (b.first == NULL)
                b.first = b.last = n;
            else
                b.last = n;
        }
    }

    ~implementation()
    {
        m_Nodes.clear_and_dispose(disposer(m_Allocator));
    }

    size_type size() const { return m_Nodes.size(); }
    iterator begin() { return iterator(m_Nodes.begin().pointed_node()); }
    iterator end() { return iterator(m_Nodes.end().pointed_node()); }

    void clear()
    {
        m_Nodes.clear_and_dispose(disposer(m_Allocator));
        std::fill_n(m_Buckets.begin(), m_Buckets.size(), bucket());
    }

    std::pair< iterator, bool > insert(key_type key, mapped_type const& data)
    {
        BOOST_ASSERT(!!key);

        bucket& b = get_bucket(key.id());
        node* p = b.first;
        if (p)
        {
            // The bucket is not empty, search among the elements
            p = find_in_bucket(key, b);
            if (p->m_Value.first == key)
                return std::make_pair(iterator(p), false);
        }

        node* const n = m_Allocator.allocate(1, NULL);
        new (n) node(key, data);

        node_list::iterator it;
        if (b.first == NULL)
        {
            // The bucket is empty
            b.first = b.last = n;
            it = m_Nodes.end();
        }
        else if (p == b.last && key.id() > p->m_Value.first.id())
        {
            // The new element should become the last element of the bucket
            it = m_Nodes.iterator_to(*p);
            ++it;
            b.last = n;
        }
        else if (p == b.first)
        {
            // The new element should become the first element of the bucket
            it = m_Nodes.iterator_to(*p);
            b.first = n;
        }
        else
        {
            // The new element should be within the bucket
            it = m_Nodes.iterator_to(*p);
        }

        m_Nodes.insert(it, *n);

        return std::make_pair(iterator(n), true);
    }

    void erase(iterator it)
    {
        typedef node_list::node_traits node_traits;
        typedef node_list::value_traits value_traits;

        node* p = static_cast< node* >(it.base());

        // Adjust bucket boundaries, if needed
        bucket& b = get_bucket(it->first.id());
        if (p == b.first)
        {
            if (p == b.last)
            {
                // The erased element is the only one in the bucket
                b.first = b.last = NULL;
            }
            else
            {
                // The erased element is the first one in the bucket
                b.first = value_traits::to_value_ptr(node_traits::get_next(b.first));
            }
        }
        else if (p == b.last)
        {
            // The erased element is the last one in the bucket
            b.last = value_traits::to_value_ptr(node_traits::get_previous(b.last));
        }

        m_Nodes.erase_and_dispose(m_Nodes.iterator_to(*p), disposer(m_Allocator));
    }

    iterator find(key_type key)
    {
        bucket& b = get_bucket(key.id());
        node* p = b.first;
        if (p)
        {
            // The bucket is not empty, search among the elements
            p = find_in_bucket(key, b);
            if (p->m_Value.first == key)
                return iterator(p);
        }

        return end();
    }

private:
    implementation& operator= (implementation const&);

    //! The function returns a bucket for the specified element
    bucket& get_bucket(id_type id)
    {
        return m_Buckets[id & (buckets::static_size - 1)];
    }

    //! Attempts to find an element with the specified key in the bucket
    node* find_in_bucket(key_type key, bucket const& b)
    {
        typedef node_list::node_traits node_traits;
        typedef node_list::value_traits value_traits;

        // All elements within the bucket are sorted to speedup the search.
        node* p = b.first;
        while (p != b.last && p->m_Value.first.id() < key.id())
        {
            p = value_traits::to_value_ptr(node_traits::get_next(p));
        }

        return p;
    }
};

BOOST_LOG_CLOSE_NAMESPACE // namespace log

} // namespace boost

#include <boost/log/detail/footer.hpp>

#endif // BOOST_LOG_ATTRIBUTE_SET_IMPL_HPP_INCLUDED_