llvm-gcc-4.0/libstdc++-v3/src/mt_allocator.cc - llvm-archive - Git at Google

 // Allocator details.

 // Copyright (C) 2004 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Librarbooly.  This library is free
 // software; you can redistribute it and/or modify it under the
 // terms of the GNU General Public License as published by the
 // Free Software Foundation; either version 2, or (at your option)
 // any later version.

 // This library 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 this library; see the file COPYING.  If not, write to the Free
 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 // 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.

 //
 // ISO C++ 14882:
 //

 #include <bits/c++config.h>
 #include <bits/concurrence.h>
 #include <ext/mt_allocator.h>

 namespace __gnu_internal
 {
   __glibcxx_mutex_define_initialized(freelist_mutex);

 #ifdef __GTHREADS
   __gthread_key_t freelist_key;
 #endif
 }

 namespace __gnu_cxx
 {
   void
   __pool<false>::_M_destroy() throw()
   {
     if (_M_init && !_M_options._M_force_new)
       {
 	for (size_t __n = 0; __n < _M_bin_size; ++__n)
 	  {
 	    _Bin_record& __bin = _M_bin[__n];
 	    while (__bin._M_address)
 	      {
 		_Block_address* __tmp = __bin._M_address->_M_next;
 		::operator delete(__bin._M_address->_M_initial);
 		__bin._M_address = __tmp;
 	      }
 	    ::operator delete(__bin._M_first);
 	  }
 	::operator delete(_M_bin);
 	::operator delete(_M_binmap);
       }
   }

   void
   __pool<false>::_M_reclaim_block(char* __p, size_t __bytes)
   {
     // Round up to power of 2 and figure out which bin to use.
     const size_t __which = _M_binmap[__bytes];
     _Bin_record& __bin = _M_bin[__which];

     char* __c = __p - _M_get_align();
     _Block_record* __block = reinterpret_cast<_Block_record*>(__c);

     // Single threaded application - return to global pool.
     __block->_M_next = __bin._M_first[0];
     __bin._M_first[0] = __block;
   }

   char*
   __pool<false>::_M_reserve_block(size_t __bytes, const size_t __thread_id)
   {
     // Round up to power of 2 and figure out which bin to use.
     const size_t __which = _M_binmap[__bytes];
     _Bin_record& __bin = _M_bin[__which];
     const _Tune& __options = _M_get_options();
     const size_t __bin_size = (__options._M_min_bin << __which)
 			       + __options._M_align;
     size_t __block_count = __options._M_chunk_size - sizeof(_Block_address);
     __block_count /= __bin_size;

     // Get a new block dynamically, set it up for use.
     void* __v = ::operator new(__options._M_chunk_size);
     _Block_address* __address = static_cast<_Block_address*>(__v);
     __address->_M_initial = __v;
     __address->_M_next = __bin._M_address;
     __bin._M_address = __address;

     char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
     _Block_record* __block = reinterpret_cast<_Block_record*>(__c);
     __bin._M_first[__thread_id] = __block;
     while (--__block_count > 0)
       {
 	__c += __bin_size;
 	__block->_M_next = reinterpret_cast<_Block_record*>(__c);
 	__block = __block->_M_next;
       }
     __block->_M_next = NULL;

     __block = __bin._M_first[__thread_id];
     __bin._M_first[__thread_id] = __block->_M_next;

     // NB: For alignment reasons, we can't use the first _M_align
     // bytes, even when sizeof(_Block_record) < _M_align.
     return reinterpret_cast<char*>(__block) + __options._M_align;
   }

   void
   __pool<false>::_M_initialize()
   {
     // _M_force_new must not change after the first allocate(), which
     // in turn calls this method, so if it's false, it's false forever
     // and we don't need to return here ever again.
     if (_M_options._M_force_new)
       {
 	_M_init = true;
 	return;
       }

     // Create the bins.
     // Calculate the number of bins required based on _M_max_bytes.
     // _M_bin_size is statically-initialized to one.
     size_t __bin_size = _M_options._M_min_bin;
     while (_M_options._M_max_bytes > __bin_size)
       {
 	__bin_size <<= 1;
 	++_M_bin_size;
       }

     // Setup the bin map for quick lookup of the relevant bin.
     const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type);
     _M_binmap = static_cast<_Binmap_type*>(::operator new(__j));
     _Binmap_type* __bp = _M_binmap;
     _Binmap_type __bin_max = _M_options._M_min_bin;
     _Binmap_type __bint = 0;
     for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct)
       {
 	if (__ct > __bin_max)
 	  {
 	    __bin_max <<= 1;
 	    ++__bint;
 	  }
 	*__bp++ = __bint;
       }

     // Initialize _M_bin and its members.
     void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size);
     _M_bin = static_cast<_Bin_record*>(__v);
     for (size_t __n = 0; __n < _M_bin_size; ++__n)
       {
 	_Bin_record& __bin = _M_bin[__n];
 	__v = ::operator new(sizeof(_Block_record*));
 	__bin._M_first = static_cast<_Block_record**>(__v);
 	__bin._M_first[0] = NULL;
 	__bin._M_address = NULL;
       }
     _M_init = true;
   }

 #ifdef __GTHREADS
   void
   __pool<true>::_M_destroy() throw()
   {
     if (_M_init && !_M_options._M_force_new)
       {
 	if (__gthread_active_p())
 	  {
 	    for (size_t __n = 0; __n < _M_bin_size; ++__n)
 	      {
 		_Bin_record& __bin = _M_bin[__n];
 		while (__bin._M_address)
 		  {
 		    _Block_address* __tmp = __bin._M_address->_M_next;
 		    ::operator delete(__bin._M_address->_M_initial);
 		    __bin._M_address = __tmp;
 		  }
 		::operator delete(__bin._M_first);
 		::operator delete(__bin._M_free);
 		::operator delete(__bin._M_used);
 		::operator delete(__bin._M_mutex);
 	      }
 	    ::operator delete(_M_thread_freelist_initial);
 	  }
 	else
 	  {
 	    for (size_t __n = 0; __n < _M_bin_size; ++__n)
 	      {
 		_Bin_record& __bin = _M_bin[__n];
 		while (__bin._M_address)
 		  {
 		    _Block_address* __tmp = __bin._M_address->_M_next;
 		    ::operator delete(__bin._M_address->_M_initial);
 		    __bin._M_address = __tmp;
 		  }
 		::operator delete(__bin._M_first);
 	      }
 	  }
 	::operator delete(_M_bin);
 	::operator delete(_M_binmap);
       }
   }

   void
   __pool<true>::_M_reclaim_block(char* __p, size_t __bytes)
   {
     // Round up to power of 2 and figure out which bin to use.
     const size_t __which = _M_binmap[__bytes];
     const _Bin_record& __bin = _M_bin[__which];

     // Know __p not null, assume valid block.
     char* __c = __p - _M_get_align();
     _Block_record* __block = reinterpret_cast<_Block_record*>(__c);
     if (__gthread_active_p())
       {
 	// Calculate the number of records to remove from our freelist:
 	// in order to avoid too much contention we wait until the
 	// number of records is "high enough".
 	const size_t __thread_id = _M_get_thread_id();
 	const _Tune& __options = _M_get_options();
 	const unsigned long __limit = 100 * (_M_bin_size - __which)
 		                      * __options._M_freelist_headroom;

 	unsigned long __remove = __bin._M_free[__thread_id];
 	__remove *= __options._M_freelist_headroom;
 	if (__remove >= __bin._M_used[__thread_id])
 	  __remove -= __bin._M_used[__thread_id];
 	else
 	  __remove = 0;
 	if (__remove > __limit && __remove > __bin._M_free[__thread_id])
 	  {
 	    _Block_record* __first = __bin._M_first[__thread_id];
 	    _Block_record* __tmp = __first;
 	    __remove /= __options._M_freelist_headroom;
 	    const unsigned long __removed = __remove;
 	    while (--__remove > 0)
 	      __tmp = __tmp->_M_next;
 	    __bin._M_first[__thread_id] = __tmp->_M_next;
 	    __bin._M_free[__thread_id] -= __removed;

 	    __gthread_mutex_lock(__bin._M_mutex);
 	    __tmp->_M_next = __bin._M_first[0];
 	    __bin._M_first[0] = __first;
 	    __bin._M_free[0] += __removed;
 	    __gthread_mutex_unlock(__bin._M_mutex);
 	  }

 	// Return this block to our list and update counters and
 	// owner id as needed.
 	--__bin._M_used[__block->_M_thread_id];

 	__block->_M_next = __bin._M_first[__thread_id];
 	__bin._M_first[__thread_id] = __block;

 	++__bin._M_free[__thread_id];
       }
     else
       {
 	// Not using threads, so single threaded application - return
 	// to global pool.
 	__block->_M_next = __bin._M_first[0];
 	__bin._M_first[0] = __block;
       }
   }

   char*
   __pool<true>::_M_reserve_block(size_t __bytes, const size_t __thread_id)
   {
     // Round up to power of 2 and figure out which bin to use.
     const size_t __which = _M_binmap[__bytes];
     const _Tune& __options = _M_get_options();
     const size_t __bin_size = ((__options._M_min_bin << __which)
 			       + __options._M_align);
     size_t __block_count = __options._M_chunk_size - sizeof(_Block_address);
     __block_count /= __bin_size;

     // Are we using threads?
     // - Yes, check if there are free blocks on the global
     //   list. If so, grab up to __block_count blocks in one
     //   lock and change ownership. If the global list is
     //   empty, we allocate a new chunk and add those blocks
     //   directly to our own freelist (with us as owner).
     // - No, all operations are made directly to global pool 0
     //   no need to lock or change ownership but check for free
     //   blocks on global list (and if not add new ones) and
     //   get the first one.
     _Bin_record& __bin = _M_bin[__which];
     _Block_record* __block = NULL;
     if (__gthread_active_p())
       {
 	__gthread_mutex_lock(__bin._M_mutex);
 	if (__bin._M_first[0] == NULL)
 	  {
 	    void* __v = ::operator new(__options._M_chunk_size);
 	    _Block_address* __address = static_cast<_Block_address*>(__v);
 	    __address->_M_initial = __v;
 	    __address->_M_next = __bin._M_address;
 	    __bin._M_address = __address;
 	    __gthread_mutex_unlock(__bin._M_mutex);

 	    // No need to hold the lock when we are adding a whole
 	    // chunk to our own list.
 	    char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
 	    __block = reinterpret_cast<_Block_record*>(__c);
 	    __bin._M_free[__thread_id] = __block_count;
 	    __bin._M_first[__thread_id] = __block;
 	    while (--__block_count > 0)
 	      {
 		__c += __bin_size;
 		__block->_M_next = reinterpret_cast<_Block_record*>(__c);
 		__block = __block->_M_next;
 	      }
 	    __block->_M_next = NULL;
 	  }
 	else
 	  {
 	    // Is the number of required blocks greater than or equal
 	    // to the number that can be provided by the global free
 	    // list?
 	    __bin._M_first[__thread_id] = __bin._M_first[0];
 	    if (__block_count >= __bin._M_free[0])
 	      {
 		__bin._M_free[__thread_id] = __bin._M_free[0];
 		__bin._M_free[0] = 0;
 		__bin._M_first[0] = NULL;
 	      }
 	    else
 	      {
 		__bin._M_free[__thread_id] = __block_count;
 		__bin._M_free[0] -= __block_count;
 		__block = __bin._M_first[0];
 		while (--__block_count > 0)
 		  __block = __block->_M_next;
 		__bin._M_first[0] = __block->_M_next;
 		__block->_M_next = NULL;
 	      }
 	    __gthread_mutex_unlock(__bin._M_mutex);
 	  }
       }
     else
       {
 	void* __v = ::operator new(__options._M_chunk_size);
 	_Block_address* __address = static_cast<_Block_address*>(__v);
 	__address->_M_initial = __v;
 	__address->_M_next = __bin._M_address;
 	__bin._M_address = __address;

 	char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
 	_Block_record* __block = reinterpret_cast<_Block_record*>(__c);
  	__bin._M_first[0] = __block;
 	while (--__block_count > 0)
 	  {
 	    __c += __bin_size;
 	    __block->_M_next = reinterpret_cast<_Block_record*>(__c);
 	    __block = __block->_M_next;
 	  }
 	__block->_M_next = NULL;
       }

     __block = __bin._M_first[__thread_id];
     __bin._M_first[__thread_id] = __block->_M_next;

     if (__gthread_active_p())
       {
 	__block->_M_thread_id = __thread_id;
 	--__bin._M_free[__thread_id];
 	++__bin._M_used[__thread_id];
       }

     // NB: For alignment reasons, we can't use the first _M_align
     // bytes, even when sizeof(_Block_record) < _M_align.
     return reinterpret_cast<char*>(__block) + __options._M_align;
   }

  void
   __pool<true>::_M_initialize(__destroy_handler __d)
   {
     // _M_force_new must not change after the first allocate(),
     // which in turn calls this method, so if it's false, it's false
     // forever and we don't need to return here ever again.
     if (_M_options._M_force_new)
       {
 	_M_init = true;
 	return;
       }

     // Create the bins.
     // Calculate the number of bins required based on _M_max_bytes.
     // _M_bin_size is statically-initialized to one.
     size_t __bin_size = _M_options._M_min_bin;
     while (_M_options._M_max_bytes > __bin_size)
       {
 	__bin_size <<= 1;
 	++_M_bin_size;
       }

     // Setup the bin map for quick lookup of the relevant bin.
     const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type);
     _M_binmap = static_cast<_Binmap_type*>(::operator new(__j));
     _Binmap_type* __bp = _M_binmap;
     _Binmap_type __bin_max = _M_options._M_min_bin;
     _Binmap_type __bint = 0;
     for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct)
       {
 	if (__ct > __bin_max)
 	  {
 	    __bin_max <<= 1;
 	    ++__bint;
 	  }
 	*__bp++ = __bint;
       }

     // Initialize _M_bin and its members.
     void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size);
     _M_bin = static_cast<_Bin_record*>(__v);

     // If __gthread_active_p() create and initialize the list of
     // free thread ids. Single threaded applications use thread id 0
     // directly and have no need for this.
     if (__gthread_active_p())
       {
 	const size_t __k = sizeof(_Thread_record) * _M_options._M_max_threads;
 	__v = ::operator new(__k);
 	_M_thread_freelist = static_cast<_Thread_record*>(__v);
 	_M_thread_freelist_initial = __v;

 	// NOTE! The first assignable thread id is 1 since the
 	// global pool uses id 0
 	size_t __i;
 	for (__i = 1; __i < _M_options._M_max_threads; ++__i)
 	  {
 	    _Thread_record& __tr = _M_thread_freelist[__i - 1];
 	    __tr._M_next = &_M_thread_freelist[__i];
 	    __tr._M_id = __i;
 	  }

 	// Set last record.
 	_M_thread_freelist[__i - 1]._M_next = NULL;
 	_M_thread_freelist[__i - 1]._M_id = __i;

 	// Initialize per thread key to hold pointer to
 	// _M_thread_freelist.
 	__gthread_key_create(&__gnu_internal::freelist_key, __d);

 	const size_t __max_threads = _M_options._M_max_threads + 1;
 	for (size_t __n = 0; __n < _M_bin_size; ++__n)
 	  {
 	    _Bin_record& __bin = _M_bin[__n];
 	    __v = ::operator new(sizeof(_Block_record*) * __max_threads);
 	    __bin._M_first = static_cast<_Block_record**>(__v);

 	    __bin._M_address = NULL;

 	    __v = ::operator new(sizeof(size_t) * __max_threads);
 	    __bin._M_free = static_cast<size_t*>(__v);

 	    __v = ::operator new(sizeof(size_t) * __max_threads);
 	    __bin._M_used = static_cast<size_t*>(__v);

 	    __v = ::operator new(sizeof(__gthread_mutex_t));
 	    __bin._M_mutex = static_cast<__gthread_mutex_t*>(__v);

 #ifdef __GTHREAD_MUTEX_INIT
 	    {
 	      // Do not copy a POSIX/gthr mutex once in use.
 	      __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
 	      *__bin._M_mutex = __tmp;
 	    }
 #else
 	    { __GTHREAD_MUTEX_INIT_FUNCTION(__bin._M_mutex); }
 #endif
 	    for (size_t __threadn = 0; __threadn < __max_threads; ++__threadn)
 	      {
 		__bin._M_first[__threadn] = NULL;
 		__bin._M_free[__threadn] = 0;
 		__bin._M_used[__threadn] = 0;
 	      }
 	  }
       }
     else
       {
 	for (size_t __n = 0; __n < _M_bin_size; ++__n)
 	  {
 	    _Bin_record& __bin = _M_bin[__n];
 	    __v = ::operator new(sizeof(_Block_record*));
 	    __bin._M_first = static_cast<_Block_record**>(__v);
 	    __bin._M_first[0] = NULL;
 	    __bin._M_address = NULL;
 	  }
       }
     _M_init = true;
   }

   size_t
   __pool<true>::_M_get_thread_id()
   {
     // If we have thread support and it's active we check the thread
     // key value and return its id or if it's not set we take the
     // first record from _M_thread_freelist and sets the key and
     // returns it's id.
     if (__gthread_active_p())
       {
 	void* v = __gthread_getspecific(__gnu_internal::freelist_key);
 	_Thread_record* __freelist_pos = static_cast<_Thread_record*>(v);
 	if (__freelist_pos == NULL)
 	  {
 	    // Since _M_options._M_max_threads must be larger than
 	    // the theoretical max number of threads of the OS the
 	    // list can never be empty.
 	    {
 	      __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex);
 	      __freelist_pos = _M_thread_freelist;
 	      _M_thread_freelist = _M_thread_freelist->_M_next;
 	    }

 	    __gthread_setspecific(__gnu_internal::freelist_key,
 				  static_cast<void*>(__freelist_pos));
 	  }
 	return __freelist_pos->_M_id;
       }

     // Otherwise (no thread support or inactive) all requests are
     // served from the global pool 0.
     return 0;
   }

   void
   __pool<true>::_M_destroy_thread_key(void* __freelist_pos)
   {
     // Return this thread id record to front of thread_freelist.
     __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex);
     _Thread_record* __tr = static_cast<_Thread_record*>(__freelist_pos);
     __tr->_M_next = _M_thread_freelist;
     _M_thread_freelist = __tr;
   }
 #endif

   // Instantiations.
   template class __mt_alloc<char>;
   template class __mt_alloc<wchar_t>;
 } // namespace __gnu_cxx
	// Allocator details.

	// Copyright (C) 2004 Free Software Foundation, Inc.
	//
	// This file is part of the GNU ISO C++ Librarbooly. This library is free
	// software; you can redistribute it and/or modify it under the
	// terms of the GNU General Public License as published by the
	// Free Software Foundation; either version 2, or (at your option)
	// any later version.

	// This library 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 this library; see the file COPYING. If not, write to the Free
	// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
	// 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.

	//
	// ISO C++ 14882:
	//

	#include <bits/c++config.h>
	#include <bits/concurrence.h>
	#include <ext/mt_allocator.h>

	namespace __gnu_internal
	{
	__glibcxx_mutex_define_initialized(freelist_mutex);

	#ifdef __GTHREADS
	__gthread_key_t freelist_key;
	#endif
	}

	namespace __gnu_cxx
	{
	void
	__pool<false>::_M_destroy() throw()
	{
	if (_M_init && !_M_options._M_force_new)
	{
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	while (__bin._M_address)
	{
	_Block_address* __tmp = __bin._M_address->_M_next;
	::operator delete(__bin._M_address->_M_initial);
	__bin._M_address = __tmp;
	}
	::operator delete(__bin._M_first);
	}
	::operator delete(_M_bin);
	::operator delete(_M_binmap);
	}
	}

	void
	__pool<false>::_M_reclaim_block(char* __p, size_t __bytes)
	{
	// Round up to power of 2 and figure out which bin to use.
	const size_t __which = _M_binmap[__bytes];
	_Bin_record& __bin = _M_bin[__which];

	char* __c = __p - _M_get_align();
	_Block_record* __block = reinterpret_cast<_Block_record*>(__c);

	// Single threaded application - return to global pool.
	__block->_M_next = __bin._M_first[0];
	__bin._M_first[0] = __block;
	}

	char*
	__pool<false>::_M_reserve_block(size_t __bytes, const size_t __thread_id)
	{
	// Round up to power of 2 and figure out which bin to use.
	const size_t __which = _M_binmap[__bytes];
	_Bin_record& __bin = _M_bin[__which];
	const _Tune& __options = _M_get_options();
	const size_t __bin_size = (__options._M_min_bin << __which)
	+ __options._M_align;
	size_t __block_count = __options._M_chunk_size - sizeof(_Block_address);
	__block_count /= __bin_size;

	// Get a new block dynamically, set it up for use.
	void* __v = ::operator new(__options._M_chunk_size);
	_Block_address* __address = static_cast<_Block_address*>(__v);
	__address->_M_initial = __v;
	__address->_M_next = __bin._M_address;
	__bin._M_address = __address;

	char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
	_Block_record* __block = reinterpret_cast<_Block_record*>(__c);
	__bin._M_first[__thread_id] = __block;
	while (--__block_count > 0)
	{
	__c += __bin_size;
	__block->_M_next = reinterpret_cast<_Block_record*>(__c);
	__block = __block->_M_next;
	}
	__block->_M_next = NULL;

	__block = __bin._M_first[__thread_id];
	__bin._M_first[__thread_id] = __block->_M_next;

	// NB: For alignment reasons, we can't use the first _M_align
	// bytes, even when sizeof(_Block_record) < _M_align.
	return reinterpret_cast<char*>(__block) + __options._M_align;
	}

	void
	__pool<false>::_M_initialize()
	{
	// _M_force_new must not change after the first allocate(), which
	// in turn calls this method, so if it's false, it's false forever
	// and we don't need to return here ever again.
	if (_M_options._M_force_new)
	{
	_M_init = true;
	return;
	}

	// Create the bins.
	// Calculate the number of bins required based on _M_max_bytes.
	// _M_bin_size is statically-initialized to one.
	size_t __bin_size = _M_options._M_min_bin;
	while (_M_options._M_max_bytes > __bin_size)
	{
	__bin_size <<= 1;
	++_M_bin_size;
	}

	// Setup the bin map for quick lookup of the relevant bin.
	const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type);
	_M_binmap = static_cast<_Binmap_type*>(::operator new(__j));
	_Binmap_type* __bp = _M_binmap;
	_Binmap_type __bin_max = _M_options._M_min_bin;
	_Binmap_type __bint = 0;
	for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct)
	{
	if (__ct > __bin_max)
	{
	__bin_max <<= 1;
	++__bint;
	}
	*__bp++ = __bint;
	}

	// Initialize _M_bin and its members.
	void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size);
	_M_bin = static_cast<_Bin_record*>(__v);
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	__v = ::operator new(sizeof(_Block_record*));
	__bin._M_first = static_cast<_Block_record**>(__v);
	__bin._M_first[0] = NULL;
	__bin._M_address = NULL;
	}
	_M_init = true;
	}

	#ifdef __GTHREADS
	void
	__pool<true>::_M_destroy() throw()
	{
	if (_M_init && !_M_options._M_force_new)
	{
	if (__gthread_active_p())
	{
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	while (__bin._M_address)
	{
	_Block_address* __tmp = __bin._M_address->_M_next;
	::operator delete(__bin._M_address->_M_initial);
	__bin._M_address = __tmp;
	}
	::operator delete(__bin._M_first);
	::operator delete(__bin._M_free);
	::operator delete(__bin._M_used);
	::operator delete(__bin._M_mutex);
	}
	::operator delete(_M_thread_freelist_initial);
	}
	else
	{
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	while (__bin._M_address)
	{
	_Block_address* __tmp = __bin._M_address->_M_next;
	::operator delete(__bin._M_address->_M_initial);
	__bin._M_address = __tmp;
	}
	::operator delete(__bin._M_first);
	}
	}
	::operator delete(_M_bin);
	::operator delete(_M_binmap);
	}
	}

	void
	__pool<true>::_M_reclaim_block(char* __p, size_t __bytes)
	{
	// Round up to power of 2 and figure out which bin to use.
	const size_t __which = _M_binmap[__bytes];
	const _Bin_record& __bin = _M_bin[__which];

	// Know __p not null, assume valid block.
	char* __c = __p - _M_get_align();
	_Block_record* __block = reinterpret_cast<_Block_record*>(__c);
	if (__gthread_active_p())
	{
	// Calculate the number of records to remove from our freelist:
	// in order to avoid too much contention we wait until the
	// number of records is "high enough".
	const size_t __thread_id = _M_get_thread_id();
	const _Tune& __options = _M_get_options();
	const unsigned long __limit = 100 * (_M_bin_size - __which)
	* __options._M_freelist_headroom;

	unsigned long __remove = __bin._M_free[__thread_id];
	__remove *= __options._M_freelist_headroom;
	if (__remove >= __bin._M_used[__thread_id])
	__remove -= __bin._M_used[__thread_id];
	else
	__remove = 0;
	if (__remove > __limit && __remove > __bin._M_free[__thread_id])
	{
	_Block_record* __first = __bin._M_first[__thread_id];
	_Block_record* __tmp = __first;
	__remove /= __options._M_freelist_headroom;
	const unsigned long __removed = __remove;
	while (--__remove > 0)
	__tmp = __tmp->_M_next;
	__bin._M_first[__thread_id] = __tmp->_M_next;
	__bin._M_free[__thread_id] -= __removed;

	__gthread_mutex_lock(__bin._M_mutex);
	__tmp->_M_next = __bin._M_first[0];
	__bin._M_first[0] = __first;
	__bin._M_free[0] += __removed;
	__gthread_mutex_unlock(__bin._M_mutex);
	}

	// Return this block to our list and update counters and
	// owner id as needed.
	--__bin._M_used[__block->_M_thread_id];

	__block->_M_next = __bin._M_first[__thread_id];
	__bin._M_first[__thread_id] = __block;

	++__bin._M_free[__thread_id];
	}
	else
	{
	// Not using threads, so single threaded application - return
	// to global pool.
	__block->_M_next = __bin._M_first[0];
	__bin._M_first[0] = __block;
	}
	}

	char*
	__pool<true>::_M_reserve_block(size_t __bytes, const size_t __thread_id)
	{
	// Round up to power of 2 and figure out which bin to use.
	const size_t __which = _M_binmap[__bytes];
	const _Tune& __options = _M_get_options();
	const size_t __bin_size = ((__options._M_min_bin << __which)
	+ __options._M_align);
	size_t __block_count = __options._M_chunk_size - sizeof(_Block_address);
	__block_count /= __bin_size;

	// Are we using threads?
	// - Yes, check if there are free blocks on the global
	// list. If so, grab up to __block_count blocks in one
	// lock and change ownership. If the global list is
	// empty, we allocate a new chunk and add those blocks
	// directly to our own freelist (with us as owner).
	// - No, all operations are made directly to global pool 0
	// no need to lock or change ownership but check for free
	// blocks on global list (and if not add new ones) and
	// get the first one.
	_Bin_record& __bin = _M_bin[__which];
	_Block_record* __block = NULL;
	if (__gthread_active_p())
	{
	__gthread_mutex_lock(__bin._M_mutex);
	if (__bin._M_first[0] == NULL)
	{
	void* __v = ::operator new(__options._M_chunk_size);
	_Block_address* __address = static_cast<_Block_address*>(__v);
	__address->_M_initial = __v;
	__address->_M_next = __bin._M_address;
	__bin._M_address = __address;
	__gthread_mutex_unlock(__bin._M_mutex);

	// No need to hold the lock when we are adding a whole
	// chunk to our own list.
	char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
	__block = reinterpret_cast<_Block_record*>(__c);
	__bin._M_free[__thread_id] = __block_count;
	__bin._M_first[__thread_id] = __block;
	while (--__block_count > 0)
	{
	__c += __bin_size;
	__block->_M_next = reinterpret_cast<_Block_record*>(__c);
	__block = __block->_M_next;
	}
	__block->_M_next = NULL;
	}
	else
	{
	// Is the number of required blocks greater than or equal
	// to the number that can be provided by the global free
	// list?
	__bin._M_first[__thread_id] = __bin._M_first[0];
	if (__block_count >= __bin._M_free[0])
	{
	__bin._M_free[__thread_id] = __bin._M_free[0];
	__bin._M_free[0] = 0;
	__bin._M_first[0] = NULL;
	}
	else
	{
	__bin._M_free[__thread_id] = __block_count;
	__bin._M_free[0] -= __block_count;
	__block = __bin._M_first[0];
	while (--__block_count > 0)
	__block = __block->_M_next;
	__bin._M_first[0] = __block->_M_next;
	__block->_M_next = NULL;
	}
	__gthread_mutex_unlock(__bin._M_mutex);
	}
	}
	else
	{
	void* __v = ::operator new(__options._M_chunk_size);
	_Block_address* __address = static_cast<_Block_address*>(__v);
	__address->_M_initial = __v;
	__address->_M_next = __bin._M_address;
	__bin._M_address = __address;

	char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
	_Block_record* __block = reinterpret_cast<_Block_record*>(__c);
	__bin._M_first[0] = __block;
	while (--__block_count > 0)
	{
	__c += __bin_size;
	__block->_M_next = reinterpret_cast<_Block_record*>(__c);
	__block = __block->_M_next;
	}
	__block->_M_next = NULL;
	}

	__block = __bin._M_first[__thread_id];
	__bin._M_first[__thread_id] = __block->_M_next;

	if (__gthread_active_p())
	{
	__block->_M_thread_id = __thread_id;
	--__bin._M_free[__thread_id];
	++__bin._M_used[__thread_id];
	}

	// NB: For alignment reasons, we can't use the first _M_align
	// bytes, even when sizeof(_Block_record) < _M_align.
	return reinterpret_cast<char*>(__block) + __options._M_align;
	}

	void
	__pool<true>::_M_initialize(__destroy_handler __d)
	{
	// _M_force_new must not change after the first allocate(),
	// which in turn calls this method, so if it's false, it's false
	// forever and we don't need to return here ever again.
	if (_M_options._M_force_new)
	{
	_M_init = true;
	return;
	}

	// Create the bins.
	// Calculate the number of bins required based on _M_max_bytes.
	// _M_bin_size is statically-initialized to one.
	size_t __bin_size = _M_options._M_min_bin;
	while (_M_options._M_max_bytes > __bin_size)
	{
	__bin_size <<= 1;
	++_M_bin_size;
	}

	// Setup the bin map for quick lookup of the relevant bin.
	const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type);
	_M_binmap = static_cast<_Binmap_type*>(::operator new(__j));
	_Binmap_type* __bp = _M_binmap;
	_Binmap_type __bin_max = _M_options._M_min_bin;
	_Binmap_type __bint = 0;
	for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct)
	{
	if (__ct > __bin_max)
	{
	__bin_max <<= 1;
	++__bint;
	}
	*__bp++ = __bint;
	}

	// Initialize _M_bin and its members.
	void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size);
	_M_bin = static_cast<_Bin_record*>(__v);

	// If __gthread_active_p() create and initialize the list of
	// free thread ids. Single threaded applications use thread id 0
	// directly and have no need for this.
	if (__gthread_active_p())
	{
	const size_t __k = sizeof(_Thread_record) * _M_options._M_max_threads;
	__v = ::operator new(__k);
	_M_thread_freelist = static_cast<_Thread_record*>(__v);
	_M_thread_freelist_initial = __v;

	// NOTE! The first assignable thread id is 1 since the
	// global pool uses id 0
	size_t __i;
	for (__i = 1; __i < _M_options._M_max_threads; ++__i)
	{
	_Thread_record& __tr = _M_thread_freelist[__i - 1];
	__tr._M_next = &_M_thread_freelist[__i];
	__tr._M_id = __i;
	}

	// Set last record.
	_M_thread_freelist[__i - 1]._M_next = NULL;
	_M_thread_freelist[__i - 1]._M_id = __i;

	// Initialize per thread key to hold pointer to
	// _M_thread_freelist.
	__gthread_key_create(&__gnu_internal::freelist_key, __d);

	const size_t __max_threads = _M_options._M_max_threads + 1;
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	__v = ::operator new(sizeof(_Block_record) __max_threads);
	__bin._M_first = static_cast<_Block_record**>(__v);

	__bin._M_address = NULL;

	__v = ::operator new(sizeof(size_t) * __max_threads);
	__bin._M_free = static_cast<size_t*>(__v);

	__v = ::operator new(sizeof(size_t) * __max_threads);
	__bin._M_used = static_cast<size_t*>(__v);

	__v = ::operator new(sizeof(__gthread_mutex_t));
	__bin._M_mutex = static_cast<__gthread_mutex_t*>(__v);

	#ifdef __GTHREAD_MUTEX_INIT
	{
	// Do not copy a POSIX/gthr mutex once in use.
	__gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
	*__bin._M_mutex = __tmp;
	}
	#else
	{ __GTHREAD_MUTEX_INIT_FUNCTION(__bin._M_mutex); }
	#endif
	for (size_t __threadn = 0; __threadn < __max_threads; ++__threadn)
	{
	__bin._M_first[__threadn] = NULL;
	__bin._M_free[__threadn] = 0;
	__bin._M_used[__threadn] = 0;
	}
	}
	}
	else
	{
	for (size_t __n = 0; __n < _M_bin_size; ++__n)
	{
	_Bin_record& __bin = _M_bin[__n];
	__v = ::operator new(sizeof(_Block_record*));
	__bin._M_first = static_cast<_Block_record**>(__v);
	__bin._M_first[0] = NULL;
	__bin._M_address = NULL;
	}
	}
	_M_init = true;
	}

	size_t
	__pool<true>::_M_get_thread_id()
	{
	// If we have thread support and it's active we check the thread
	// key value and return its id or if it's not set we take the
	// first record from _M_thread_freelist and sets the key and
	// returns it's id.
	if (__gthread_active_p())
	{
	void* v = __gthread_getspecific(__gnu_internal::freelist_key);
	_Thread_record* __freelist_pos = static_cast<_Thread_record*>(v);
	if (__freelist_pos == NULL)
	{
	// Since _M_options._M_max_threads must be larger than
	// the theoretical max number of threads of the OS the
	// list can never be empty.
	{
	__gnu_cxx::lock sentry(__gnu_internal::freelist_mutex);
	__freelist_pos = _M_thread_freelist;
	_M_thread_freelist = _M_thread_freelist->_M_next;
	}

	__gthread_setspecific(__gnu_internal::freelist_key,
	static_cast<void*>(__freelist_pos));
	}
	return __freelist_pos->_M_id;
	}

	// Otherwise (no thread support or inactive) all requests are
	// served from the global pool 0.
	return 0;
	}

	void
	__pool<true>::_M_destroy_thread_key(void* __freelist_pos)
	{
	// Return this thread id record to front of thread_freelist.
	__gnu_cxx::lock sentry(__gnu_internal::freelist_mutex);
	_Thread_record* __tr = static_cast<_Thread_record*>(__freelist_pos);
	__tr->_M_next = _M_thread_freelist;
	_M_thread_freelist = __tr;
	}
	#endif

	// Instantiations.
	template class __mt_alloc<char>;
	template class __mt_alloc<wchar_t>;
	} // namespace __gnu_cxx