boost/libs/log/src/attribute_value_set.cpp - nest-cam/4320010/boost - Git at Google

 /*
  *          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_value_set.cpp
  * \author Andrey Semashev
  * \date   19.04.2007
  *
  * \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.
  */

 #include <new>
 #include <memory>
 #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_name.hpp>
 #include <boost/log/attributes/attribute_value.hpp>
 #include <boost/log/attributes/attribute_value_set.hpp>
 #include "alignment_gap_between.hpp"
 #include "attribute_set_impl.hpp"
 #include "stateless_allocator.hpp"
 #include <boost/log/detail/header.hpp>

 namespace boost {

 BOOST_LOG_OPEN_NAMESPACE

 BOOST_FORCEINLINE attribute_value_set::node_base::node_base() :
     m_pPrev(NULL),
     m_pNext(NULL)
 {
 }

 BOOST_FORCEINLINE attribute_value_set::node::node(key_type const& key, mapped_type& data, bool dynamic) :
     node_base(),
     m_Value(key, mapped_type()),
     m_DynamicallyAllocated(dynamic)
 {
     m_Value.second.swap(data);
 }

 //! Container implementation
 struct attribute_value_set::implementation
 {
 public:
     typedef key_type::id_type id_type;

 private:
     typedef attribute_set::implementation attribute_set_impl_type;
     typedef boost::log::aux::stateless_allocator< char > stateless_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;

     //! A container that provides iteration through elements of the container
     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;

     //! Element disposer
     struct disposer
     {
         typedef void result_type;
         void operator() (node* p) const BOOST_NOEXCEPT
         {
             if (!p->m_DynamicallyAllocated)
                 p->~node();
             else
                 delete p;
         }
     };

 private:
     //! Pointer to the source-specific attributes
     attribute_set_impl_type* m_pSourceAttributes;
     //! Pointer to the thread-specific attributes
     attribute_set_impl_type* m_pThreadAttributes;
     //! Pointer to the global attributes
     attribute_set_impl_type* m_pGlobalAttributes;

     //! The container with elements
     node_list m_Nodes;
     //! The pointer to the beginning of the storage of the elements
     node* m_pStorage;
     //! The pointer to the end of the allocated elements within the storage
     node* m_pEnd;
     //! The pointer to the end of storage
     node* m_pEOS;

     //! Hash table buckets
     buckets m_Buckets;

 private:
     //! Constructor
     implementation(
         node* storage,
         node* eos,
         attribute_set_impl_type* source_attrs,
         attribute_set_impl_type* thread_attrs,
         attribute_set_impl_type* global_attrs
     ) :
         m_pSourceAttributes(source_attrs),
         m_pThreadAttributes(thread_attrs),
         m_pGlobalAttributes(global_attrs),
         m_pStorage(storage),
         m_pEnd(storage),
         m_pEOS(eos)
     {
     }

     //! Destructor
     ~implementation()
     {
         m_Nodes.clear_and_dispose(disposer());
     }

     //! The function allocates memory and creates the object
     static implementation* create(
         size_type element_count,
         attribute_set_impl_type* source_attrs,
         attribute_set_impl_type* thread_attrs,
         attribute_set_impl_type* global_attrs)
     {
         // Calculate the buffer size
         const size_type header_size = sizeof(implementation) +
             aux::alignment_gap_between< implementation, node >::value;
         const size_type buffer_size = header_size + element_count * sizeof(node);

         implementation* p = reinterpret_cast< implementation* >(stateless_allocator().allocate(buffer_size));
         node* const storage = reinterpret_cast< node* >(reinterpret_cast< char* >(p) + header_size);
         new (p) implementation(storage, storage + element_count, source_attrs, thread_attrs, global_attrs);

         return p;
     }

 public:
     //! The function allocates memory and creates the object
     static implementation* create(
         attribute_set const& source_attrs,
         attribute_set const& thread_attrs,
         attribute_set const& global_attrs,
         size_type reserve_count)
     {
         return create(
             source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
             source_attrs.m_pImpl,
             thread_attrs.m_pImpl,
             global_attrs.m_pImpl);
     }

     //! The function allocates memory and creates the object
     static implementation* create(
         attribute_value_set const& source_attrs,
         attribute_set const& thread_attrs,
         attribute_set const& global_attrs,
         size_type reserve_count)
     {
         implementation* p = create(
             source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
             NULL,
             thread_attrs.m_pImpl,
             global_attrs.m_pImpl);
         p->copy_nodes_from(source_attrs.m_pImpl);
         return p;
     }

     //! The function allocates memory and creates the object
     static implementation* create(
         BOOST_RV_REF(attribute_value_set) source_attrs,
         attribute_set const& thread_attrs,
         attribute_set const& global_attrs,
         size_type reserve_count)
     {
         implementation* p = source_attrs.m_pImpl;
         source_attrs.m_pImpl = NULL;
         p->m_pThreadAttributes = thread_attrs.m_pImpl;
         p->m_pGlobalAttributes = global_attrs.m_pImpl;
         return p;
     }

     //! The function allocates memory and creates the object
     static implementation* create(size_type reserve_count)
     {
         return create(reserve_count, NULL, NULL, NULL);
     }

     //! Creates a copy of the object
     static implementation* copy(implementation* that)
     {
         // Create new object
         implementation* p = create(that->size(), NULL, NULL, NULL);

         // Copy all elements
         p->copy_nodes_from(that);

         return p;
     }

     //! Destroys the object and releases the memory
     static void destroy(implementation* p)
     {
         const size_type buffer_size = reinterpret_cast< char* >(p->m_pEOS) - reinterpret_cast< char* >(p);
         p->~implementation();
         stateless_allocator().deallocate(reinterpret_cast< stateless_allocator::pointer >(p), buffer_size);
     }

     //! Returns the pointer to the first element
     node_base* begin()
     {
         freeze();
         return m_Nodes.begin().pointed_node();
     }
     //! Returns the pointer after the last element
     node_base* end()
     {
         return m_Nodes.end().pointed_node();
     }

     //! Returns the number of elements in the container
     size_type size()
     {
         freeze();
         return m_Nodes.size();
     }

     //! Looks for the element with an equivalent key
     node_base* find(key_type key)
     {
         // First try to find an acquired element
         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 p;
         }

         // Element not found, try to acquire the value from attribute sets
         return freeze_node(key, b, p);
     }

     //! Freezes all elements of the container
     void freeze()
     {
         if (m_pSourceAttributes)
         {
             freeze_nodes_from(m_pSourceAttributes);
             m_pSourceAttributes = NULL;
         }
         if (m_pThreadAttributes)
         {
             freeze_nodes_from(m_pThreadAttributes);
             m_pThreadAttributes = NULL;
         }
         if (m_pGlobalAttributes)
         {
             freeze_nodes_from(m_pGlobalAttributes);
             m_pGlobalAttributes = NULL;
         }
     }

     //! Inserts an element
     std::pair< node*, bool > insert(key_type key, mapped_type const& mapped)
     {
         bucket& b = get_bucket(key.id());
         node* p = find_in_bucket(key, b);
         if (!p || p->m_Value.first != key)
         {
             p = insert_node(key, b, p, mapped);
             return std::pair< node*, bool >(p, true);
         }
         else
         {
             return std::pair< node*, bool >(p, false);
         }
     }

 private:
     //! 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;
     }

     //! Acquires the attribute value from the attribute sets
     node_base* freeze_node(key_type key, bucket& b, node* where)
     {
         attribute_set::iterator it;
         if (m_pSourceAttributes)
         {
             it = m_pSourceAttributes->find(key);
             if (it != m_pSourceAttributes->end())
             {
                 // The attribute is found, acquiring the value
                 return insert_node(key, b, where, it->second.get_value());
             }
         }

         if (m_pThreadAttributes)
         {
             it = m_pThreadAttributes->find(key);
             if (it != m_pThreadAttributes->end())
             {
                 // The attribute is found, acquiring the value
                 return insert_node(key, b, where, it->second.get_value());
             }
         }

         if (m_pGlobalAttributes)
         {
             it = m_pGlobalAttributes->find(key);
             if (it != m_pGlobalAttributes->end())
             {
                 // The attribute is found, acquiring the value
                 return insert_node(key, b, where, it->second.get_value());
             }
         }

         // The attribute is not found
         return m_Nodes.end().pointed_node();
     }

     //! The function inserts a node into the container
     node* insert_node(key_type key, bucket& b, node* where, mapped_type data)
     {
         node* p;
         if (m_pEnd != m_pEOS)
         {
             p = m_pEnd++;
             new (p) node(key, data, false);
         }
         else
         {
             p = new node(key, data, true);
         }

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

         m_Nodes.insert(it, *p);

         return p;
     }

     //! Acquires attribute values from the set of attributes
     void freeze_nodes_from(attribute_set_impl_type* attrs)
     {
         attribute_set::const_iterator it = attrs->begin(), end = attrs->end();
         for (; it != end; ++it)
         {
             key_type key = it->first;
             bucket& b = get_bucket(key.id());
             node* p = b.first;
             if (p)
             {
                 p = find_in_bucket(key, b);
                 if (p->m_Value.first == key)
                     continue; // the element is already frozen
             }

             insert_node(key, b, p, it->second.get_value());
         }
     }

     //! Copies nodes of the container
     void copy_nodes_from(implementation* from)
     {
         // Copy all elements
         node_list::iterator it = from->m_Nodes.begin(), end = from->m_Nodes.end();
         for (; it != end; ++it)
         {
             node* n = m_pEnd++;
             mapped_type data = it->m_Value.second;
             new (n) node(it->m_Value.first, data, false);
             m_Nodes.push_back(*n);

             // Since nodes within buckets are ordered, we can simply append the node to the end of the bucket
             bucket& b = get_bucket(n->m_Value.first.id());
             if (b.first == NULL)
                 b.first = b.last = n;
             else
                 b.last = n;
         }
     }
 };

 //! The constructor creates an empty set
 BOOST_LOG_API attribute_value_set::attribute_value_set(
     size_type reserve_count
 ) :
     m_pImpl(implementation::create(reserve_count))
 {
 }

 //! The constructor adopts three attribute sets to the set
 BOOST_LOG_API attribute_value_set::attribute_value_set(
     attribute_set const& source_attrs,
     attribute_set const& thread_attrs,
     attribute_set const& global_attrs,
     size_type reserve_count
 ) :
     m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
 {
 }

 //! The constructor adopts three attribute sets to the set
 BOOST_LOG_API attribute_value_set::attribute_value_set(
     attribute_value_set const& source_attrs,
     attribute_set const& thread_attrs,
     attribute_set const& global_attrs,
     size_type reserve_count
 ) :
     m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
 {
 }

 //! The constructor adopts three attribute sets to the set
 BOOST_LOG_API void attribute_value_set::construct(
     attribute_value_set& source_attrs,
     attribute_set const& thread_attrs,
     attribute_set const& global_attrs,
     size_type reserve_count
 )
 {
     m_pImpl = implementation::create(boost::move(source_attrs), thread_attrs, global_attrs, reserve_count);
 }

 //! Copy constructor
 BOOST_LOG_API attribute_value_set::attribute_value_set(attribute_value_set const& that)
 {
     if (that.m_pImpl)
         m_pImpl = implementation::copy(that.m_pImpl);
     else
         m_pImpl = NULL;
 }

 //! Destructor
 BOOST_LOG_API attribute_value_set::~attribute_value_set() BOOST_NOEXCEPT
 {
     if (m_pImpl)
     {
         implementation::destroy(m_pImpl);
         m_pImpl = NULL;
     }
 }

 //  Iterator generators
 BOOST_LOG_API attribute_value_set::const_iterator
 attribute_value_set::begin() const
 {
     return const_iterator(m_pImpl->begin(), const_cast< attribute_value_set* >(this));
 }

 BOOST_LOG_API attribute_value_set::const_iterator
 attribute_value_set::end() const
 {
     return const_iterator(m_pImpl->end(), const_cast< attribute_value_set* >(this));
 }

 //! The method returns number of elements in the container
 BOOST_LOG_API attribute_value_set::size_type
 attribute_value_set::size() const
 {
     return m_pImpl->size();
 }

 //! Internal lookup implementation
 BOOST_LOG_API attribute_value_set::const_iterator
 attribute_value_set::find(key_type key) const
 {
     return const_iterator(m_pImpl->find(key), const_cast< attribute_value_set* >(this));
 }

 //! The method acquires values of all adopted attributes. Users don't need to call it, since will always get an already frozen set.
 BOOST_LOG_API void attribute_value_set::freeze()
 {
     m_pImpl->freeze();
 }

 //! Inserts an element into the set
 BOOST_LOG_API std::pair< attribute_value_set::const_iterator, bool >
 attribute_value_set::insert(key_type key, mapped_type const& mapped)
 {
     std::pair< node*, bool > res = m_pImpl->insert(key, mapped);
     return std::pair< const_iterator, bool >(const_iterator(res.first, this), res.second);
 }

 BOOST_LOG_CLOSE_NAMESPACE // namespace log

 } // namespace boost

 #include <boost/log/detail/footer.hpp>
	/*
	* 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_value_set.cpp
	* \author Andrey Semashev
	* \date 19.04.2007
	*
	* \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.
	*/

	#include <new>
	#include <memory>
	#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_name.hpp>
	#include <boost/log/attributes/attribute_value.hpp>
	#include <boost/log/attributes/attribute_value_set.hpp>
	#include "alignment_gap_between.hpp"
	#include "attribute_set_impl.hpp"
	#include "stateless_allocator.hpp"
	#include <boost/log/detail/header.hpp>

	namespace boost {

	BOOST_LOG_OPEN_NAMESPACE

	BOOST_FORCEINLINE attribute_value_set::node_base::node_base() :
	m_pPrev(NULL),
	m_pNext(NULL)
	{
	}

	BOOST_FORCEINLINE attribute_value_set::node::node(key_type const& key, mapped_type& data, bool dynamic) :
	node_base(),
	m_Value(key, mapped_type()),
	m_DynamicallyAllocated(dynamic)
	{
	m_Value.second.swap(data);
	}

	//! Container implementation
	struct attribute_value_set::implementation
	{
	public:
	typedef key_type::id_type id_type;

	private:
	typedef attribute_set::implementation attribute_set_impl_type;
	typedef boost::log::aux::stateless_allocator< char > stateless_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;

	//! A container that provides iteration through elements of the container
	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;

	//! Element disposer
	struct disposer
	{
	typedef void result_type;
	void operator() (node* p) const BOOST_NOEXCEPT
	{
	if (!p->m_DynamicallyAllocated)
	p->~node();
	else
	delete p;
	}
	};

	private:
	//! Pointer to the source-specific attributes
	attribute_set_impl_type* m_pSourceAttributes;
	//! Pointer to the thread-specific attributes
	attribute_set_impl_type* m_pThreadAttributes;
	//! Pointer to the global attributes
	attribute_set_impl_type* m_pGlobalAttributes;

	//! The container with elements
	node_list m_Nodes;
	//! The pointer to the beginning of the storage of the elements
	node* m_pStorage;
	//! The pointer to the end of the allocated elements within the storage
	node* m_pEnd;
	//! The pointer to the end of storage
	node* m_pEOS;

	//! Hash table buckets
	buckets m_Buckets;

	private:
	//! Constructor
	implementation(
	node* storage,
	node* eos,
	attribute_set_impl_type* source_attrs,
	attribute_set_impl_type* thread_attrs,
	attribute_set_impl_type* global_attrs
	) :
	m_pSourceAttributes(source_attrs),
	m_pThreadAttributes(thread_attrs),
	m_pGlobalAttributes(global_attrs),
	m_pStorage(storage),
	m_pEnd(storage),
	m_pEOS(eos)
	{
	}

	//! Destructor
	~implementation()
	{
	m_Nodes.clear_and_dispose(disposer());
	}

	//! The function allocates memory and creates the object
	static implementation* create(
	size_type element_count,
	attribute_set_impl_type* source_attrs,
	attribute_set_impl_type* thread_attrs,
	attribute_set_impl_type* global_attrs)
	{
	// Calculate the buffer size
	const size_type header_size = sizeof(implementation) +
	aux::alignment_gap_between< implementation, node >::value;
	const size_type buffer_size = header_size + element_count * sizeof(node);

	implementation* p = reinterpret_cast< implementation* >(stateless_allocator().allocate(buffer_size));
	node* const storage = reinterpret_cast< node* >(reinterpret_cast< char* >(p) + header_size);
	new (p) implementation(storage, storage + element_count, source_attrs, thread_attrs, global_attrs);

	return p;
	}

	public:
	//! The function allocates memory and creates the object
	static implementation* create(
	attribute_set const& source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count)
	{
	return create(
	source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
	source_attrs.m_pImpl,
	thread_attrs.m_pImpl,
	global_attrs.m_pImpl);
	}

	//! The function allocates memory and creates the object
	static implementation* create(
	attribute_value_set const& source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count)
	{
	implementation* p = create(
	source_attrs.m_pImpl->size() + thread_attrs.m_pImpl->size() + global_attrs.m_pImpl->size() + reserve_count,
	NULL,
	thread_attrs.m_pImpl,
	global_attrs.m_pImpl);
	p->copy_nodes_from(source_attrs.m_pImpl);
	return p;
	}

	//! The function allocates memory and creates the object
	static implementation* create(
	BOOST_RV_REF(attribute_value_set) source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count)
	{
	implementation* p = source_attrs.m_pImpl;
	source_attrs.m_pImpl = NULL;
	p->m_pThreadAttributes = thread_attrs.m_pImpl;
	p->m_pGlobalAttributes = global_attrs.m_pImpl;
	return p;
	}

	//! The function allocates memory and creates the object
	static implementation* create(size_type reserve_count)
	{
	return create(reserve_count, NULL, NULL, NULL);
	}

	//! Creates a copy of the object
	static implementation* copy(implementation* that)
	{
	// Create new object
	implementation* p = create(that->size(), NULL, NULL, NULL);

	// Copy all elements
	p->copy_nodes_from(that);

	return p;
	}

	//! Destroys the object and releases the memory
	static void destroy(implementation* p)
	{
	const size_type buffer_size = reinterpret_cast< char* >(p->m_pEOS) - reinterpret_cast< char* >(p);
	p->~implementation();
	stateless_allocator().deallocate(reinterpret_cast< stateless_allocator::pointer >(p), buffer_size);
	}

	//! Returns the pointer to the first element
	node_base* begin()
	{
	freeze();
	return m_Nodes.begin().pointed_node();
	}
	//! Returns the pointer after the last element
	node_base* end()
	{
	return m_Nodes.end().pointed_node();
	}

	//! Returns the number of elements in the container
	size_type size()
	{
	freeze();
	return m_Nodes.size();
	}

	//! Looks for the element with an equivalent key
	node_base* find(key_type key)
	{
	// First try to find an acquired element
	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 p;
	}

	// Element not found, try to acquire the value from attribute sets
	return freeze_node(key, b, p);
	}

	//! Freezes all elements of the container
	void freeze()
	{
	if (m_pSourceAttributes)
	{
	freeze_nodes_from(m_pSourceAttributes);
	m_pSourceAttributes = NULL;
	}
	if (m_pThreadAttributes)
	{
	freeze_nodes_from(m_pThreadAttributes);
	m_pThreadAttributes = NULL;
	}
	if (m_pGlobalAttributes)
	{
	freeze_nodes_from(m_pGlobalAttributes);
	m_pGlobalAttributes = NULL;
	}
	}

	//! Inserts an element
	std::pair< node*, bool > insert(key_type key, mapped_type const& mapped)
	{
	bucket& b = get_bucket(key.id());
	node* p = find_in_bucket(key, b);
	if (!p \|\| p->m_Value.first != key)
	{
	p = insert_node(key, b, p, mapped);
	return std::pair< node*, bool >(p, true);
	}
	else
	{
	return std::pair< node*, bool >(p, false);
	}
	}

	private:
	//! 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;
	}

	//! Acquires the attribute value from the attribute sets
	node_base* freeze_node(key_type key, bucket& b, node* where)
	{
	attribute_set::iterator it;
	if (m_pSourceAttributes)
	{
	it = m_pSourceAttributes->find(key);
	if (it != m_pSourceAttributes->end())
	{
	// The attribute is found, acquiring the value
	return insert_node(key, b, where, it->second.get_value());
	}
	}

	if (m_pThreadAttributes)
	{
	it = m_pThreadAttributes->find(key);
	if (it != m_pThreadAttributes->end())
	{
	// The attribute is found, acquiring the value
	return insert_node(key, b, where, it->second.get_value());
	}
	}

	if (m_pGlobalAttributes)
	{
	it = m_pGlobalAttributes->find(key);
	if (it != m_pGlobalAttributes->end())
	{
	// The attribute is found, acquiring the value
	return insert_node(key, b, where, it->second.get_value());
	}
	}

	// The attribute is not found
	return m_Nodes.end().pointed_node();
	}

	//! The function inserts a node into the container
	node* insert_node(key_type key, bucket& b, node* where, mapped_type data)
	{
	node* p;
	if (m_pEnd != m_pEOS)
	{
	p = m_pEnd++;
	new (p) node(key, data, false);
	}
	else
	{
	p = new node(key, data, true);
	}

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

	m_Nodes.insert(it, *p);

	return p;
	}

	//! Acquires attribute values from the set of attributes
	void freeze_nodes_from(attribute_set_impl_type* attrs)
	{
	attribute_set::const_iterator it = attrs->begin(), end = attrs->end();
	for (; it != end; ++it)
	{
	key_type key = it->first;
	bucket& b = get_bucket(key.id());
	node* p = b.first;
	if (p)
	{
	p = find_in_bucket(key, b);
	if (p->m_Value.first == key)
	continue; // the element is already frozen
	}

	insert_node(key, b, p, it->second.get_value());
	}
	}

	//! Copies nodes of the container
	void copy_nodes_from(implementation* from)
	{
	// Copy all elements
	node_list::iterator it = from->m_Nodes.begin(), end = from->m_Nodes.end();
	for (; it != end; ++it)
	{
	node* n = m_pEnd++;
	mapped_type data = it->m_Value.second;
	new (n) node(it->m_Value.first, data, false);
	m_Nodes.push_back(*n);

	// Since nodes within buckets are ordered, we can simply append the node to the end of the bucket
	bucket& b = get_bucket(n->m_Value.first.id());
	if (b.first == NULL)
	b.first = b.last = n;
	else
	b.last = n;
	}
	}
	};

	//! The constructor creates an empty set
	BOOST_LOG_API attribute_value_set::attribute_value_set(
	size_type reserve_count
	) :
	m_pImpl(implementation::create(reserve_count))
	{
	}

	//! The constructor adopts three attribute sets to the set
	BOOST_LOG_API attribute_value_set::attribute_value_set(
	attribute_set const& source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count
	) :
	m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
	{
	}

	//! The constructor adopts three attribute sets to the set
	BOOST_LOG_API attribute_value_set::attribute_value_set(
	attribute_value_set const& source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count
	) :
	m_pImpl(implementation::create(source_attrs, thread_attrs, global_attrs, reserve_count))
	{
	}

	//! The constructor adopts three attribute sets to the set
	BOOST_LOG_API void attribute_value_set::construct(
	attribute_value_set& source_attrs,
	attribute_set const& thread_attrs,
	attribute_set const& global_attrs,
	size_type reserve_count
	)
	{
	m_pImpl = implementation::create(boost::move(source_attrs), thread_attrs, global_attrs, reserve_count);
	}

	//! Copy constructor
	BOOST_LOG_API attribute_value_set::attribute_value_set(attribute_value_set const& that)
	{
	if (that.m_pImpl)
	m_pImpl = implementation::copy(that.m_pImpl);
	else
	m_pImpl = NULL;
	}

	//! Destructor
	BOOST_LOG_API attribute_value_set::~attribute_value_set() BOOST_NOEXCEPT
	{
	if (m_pImpl)
	{
	implementation::destroy(m_pImpl);
	m_pImpl = NULL;
	}
	}

	// Iterator generators
	BOOST_LOG_API attribute_value_set::const_iterator
	attribute_value_set::begin() const
	{
	return const_iterator(m_pImpl->begin(), const_cast< attribute_value_set* >(this));
	}

	BOOST_LOG_API attribute_value_set::const_iterator
	attribute_value_set::end() const
	{
	return const_iterator(m_pImpl->end(), const_cast< attribute_value_set* >(this));
	}

	//! The method returns number of elements in the container
	BOOST_LOG_API attribute_value_set::size_type
	attribute_value_set::size() const
	{
	return m_pImpl->size();
	}

	//! Internal lookup implementation
	BOOST_LOG_API attribute_value_set::const_iterator
	attribute_value_set::find(key_type key) const
	{
	return const_iterator(m_pImpl->find(key), const_cast< attribute_value_set* >(this));
	}

	//! The method acquires values of all adopted attributes. Users don't need to call it, since will always get an already frozen set.
	BOOST_LOG_API void attribute_value_set::freeze()
	{
	m_pImpl->freeze();
	}

	//! Inserts an element into the set
	BOOST_LOG_API std::pair< attribute_value_set::const_iterator, bool >
	attribute_value_set::insert(key_type key, mapped_type const& mapped)
	{
	std::pair< node*, bool > res = m_pImpl->insert(key, mapped);
	return std::pair< const_iterator, bool >(const_iterator(res.first, this), res.second);
	}

	BOOST_LOG_CLOSE_NAMESPACE // namespace log

	} // namespace boost

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