williamr@2: #ifndef BOOST_DETAIL_QUICK_ALLOCATOR_HPP_INCLUDED
williamr@2: #define BOOST_DETAIL_QUICK_ALLOCATOR_HPP_INCLUDED
williamr@2: 
williamr@2: // MS compatible compilers support #pragma once
williamr@2: 
williamr@2: #if defined(_MSC_VER) && (_MSC_VER >= 1020)
williamr@2: # pragma once
williamr@2: #endif
williamr@2: 
williamr@2: //
williamr@2: //  detail/quick_allocator.hpp
williamr@2: //
williamr@2: //  Copyright (c) 2003 David Abrahams
williamr@2: //  Copyright (c) 2003 Peter Dimov
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //
williamr@2: 
williamr@2: #include <boost/config.hpp>
williamr@2: 
williamr@2: #include <boost/detail/lightweight_mutex.hpp>
williamr@2: #include <boost/type_traits/type_with_alignment.hpp>
williamr@2: #include <boost/type_traits/alignment_of.hpp>
williamr@2: 
williamr@2: #include <new>              // ::operator new, ::operator delete
williamr@2: #include <cstddef>          // std::size_t
williamr@2: 
williamr@2: namespace boost
williamr@2: {
williamr@2: 
williamr@2: namespace detail
williamr@2: {
williamr@2: 
williamr@2: template<unsigned size, unsigned align_> union freeblock
williamr@2: {
williamr@2:     typedef typename boost::type_with_alignment<align_>::type aligner_type;
williamr@2:     aligner_type aligner;
williamr@2:     char bytes[size];
williamr@2:     freeblock * next;
williamr@2: };
williamr@2: 
williamr@2: template<unsigned size, unsigned align_> struct allocator_impl
williamr@2: {
williamr@2:     typedef freeblock<size, align_> block;
williamr@2: 
williamr@2:     // It may seem odd to use such small pages.
williamr@2:     //
williamr@2:     // However, on a typical Windows implementation that uses
williamr@2:     // the OS allocator, "normal size" pages interact with the
williamr@2:     // "ordinary" operator new, slowing it down dramatically.
williamr@2:     //
williamr@2:     // 512 byte pages are handled by the small object allocator,
williamr@2:     // and don't interfere with ::new.
williamr@2:     //
williamr@2:     // The other alternative is to use much bigger pages (1M.)
williamr@2:     //
williamr@2:     // It is surprisingly easy to hit pathological behavior by
williamr@2:     // varying the page size. g++ 2.96 on Red Hat Linux 7.2,
williamr@2:     // for example, passionately dislikes 496. 512 seems OK.
williamr@2: 
williamr@2: #if defined(BOOST_QA_PAGE_SIZE)
williamr@2: 
williamr@2:     enum { items_per_page = BOOST_QA_PAGE_SIZE / size };
williamr@2: 
williamr@2: #else
williamr@2: 
williamr@2:     enum { items_per_page = 512 / size }; // 1048560 / size
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2: 
williamr@2:     static lightweight_mutex & mutex()
williamr@2:     {
williamr@2:         static lightweight_mutex m;
williamr@2:         return m;
williamr@2:     }
williamr@2: 
williamr@2:     static lightweight_mutex * mutex_init;
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2:     static block * free;
williamr@2:     static block * page;
williamr@2:     static unsigned last;
williamr@2: 
williamr@2:     static inline void * alloc()
williamr@2:     {
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2:         lightweight_mutex::scoped_lock lock( mutex() );
williamr@2: #endif
williamr@2:         if(block * x = free)
williamr@2:         {
williamr@2:             free = x->next;
williamr@2:             return x;
williamr@2:         }
williamr@2:         else
williamr@2:         {
williamr@2:             if(last == items_per_page)
williamr@2:             {
williamr@2:                 // "Listen to me carefully: there is no memory leak"
williamr@2:                 // -- Scott Meyers, Eff C++ 2nd Ed Item 10
williamr@2:                 page = ::new block[items_per_page];
williamr@2:                 last = 0;
williamr@2:             }
williamr@2: 
williamr@2:             return &page[last++];
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     static inline void * alloc(std::size_t n)
williamr@2:     {
williamr@2:         if(n != size) // class-specific new called for a derived object
williamr@2:         {
williamr@2:             return ::operator new(n);
williamr@2:         }
williamr@2:         else
williamr@2:         {
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2:             lightweight_mutex::scoped_lock lock( mutex() );
williamr@2: #endif
williamr@2:             if(block * x = free)
williamr@2:             {
williamr@2:                 free = x->next;
williamr@2:                 return x;
williamr@2:             }
williamr@2:             else
williamr@2:             {
williamr@2:                 if(last == items_per_page)
williamr@2:                 {
williamr@2:                     page = ::new block[items_per_page];
williamr@2:                     last = 0;
williamr@2:                 }
williamr@2: 
williamr@2:                 return &page[last++];
williamr@2:             }
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     static inline void dealloc(void * pv)
williamr@2:     {
williamr@2:         if(pv != 0) // 18.4.1.1/13
williamr@2:         {
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2:             lightweight_mutex::scoped_lock lock( mutex() );
williamr@2: #endif
williamr@2:             block * pb = static_cast<block *>(pv);
williamr@2:             pb->next = free;
williamr@2:             free = pb;
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     static inline void dealloc(void * pv, std::size_t n)
williamr@2:     {
williamr@2:         if(n != size) // class-specific delete called for a derived object
williamr@2:         {
williamr@2:             ::operator delete(pv);
williamr@2:         }
williamr@2:         else if(pv != 0) // 18.4.1.1/13
williamr@2:         {
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2:             lightweight_mutex::scoped_lock lock( mutex() );
williamr@2: #endif
williamr@2:             block * pb = static_cast<block *>(pv);
williamr@2:             pb->next = free;
williamr@2:             free = pb;
williamr@2:         }
williamr@2:     }
williamr@2: };
williamr@2: 
williamr@2: #ifdef BOOST_HAS_THREADS
williamr@2: 
williamr@2: template<unsigned size, unsigned align_>
williamr@2:   lightweight_mutex * allocator_impl<size, align_>::mutex_init = &allocator_impl<size, align_>::mutex();
williamr@2: 
williamr@2: #endif
williamr@2: 
williamr@2: template<unsigned size, unsigned align_>
williamr@2:   freeblock<size, align_> * allocator_impl<size, align_>::free = 0;
williamr@2: 
williamr@2: template<unsigned size, unsigned align_>
williamr@2:   freeblock<size, align_> * allocator_impl<size, align_>::page = 0;
williamr@2: 
williamr@2: template<unsigned size, unsigned align_>
williamr@2:   unsigned allocator_impl<size, align_>::last = allocator_impl<size, align_>::items_per_page;
williamr@2: 
williamr@2: template<class T>
williamr@2: struct quick_allocator: public allocator_impl< sizeof(T), boost::alignment_of<T>::value >
williamr@2: {
williamr@2: };
williamr@2: 
williamr@2: } // namespace detail
williamr@2: 
williamr@2: } // namespace boost
williamr@2: 
williamr@2: #endif  // #ifndef BOOST_DETAIL_QUICK_ALLOCATOR_HPP_INCLUDED