pool_allocator.h

Go to the documentation of this file.
00001 // Allocators -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  * Copyright (c) 1996-1997
00033  * Silicon Graphics Computer Systems, Inc.
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Silicon Graphics makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  */
00043 
00044 /** @file ext/pool_allocator.h
00045  *  This file is a GNU extension to the Standard C++ Library.
00046  */
00047 
00048 #ifndef _POOL_ALLOCATOR_H
00049 #define _POOL_ALLOCATOR_H 1
00050 
00051 #include <bits/c++config.h>
00052 #include <cstdlib>
00053 #include <new>
00054 #include <bits/functexcept.h>
00055 #include <ext/atomicity.h>
00056 #include <ext/concurrence.h>
00057 
00058 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00059 
00060   using std::size_t;
00061   using std::ptrdiff_t;
00062 
00063   /**
00064    *  @brief  Base class for __pool_alloc.
00065    *
00066    *  @if maint
00067    *  Uses various allocators to fulfill underlying requests (and makes as
00068    *  few requests as possible when in default high-speed pool mode).
00069    *
00070    *  Important implementation properties:
00071    *  0. If globally mandated, then allocate objects from new
00072    *  1. If the clients request an object of size > _S_max_bytes, the resulting
00073    *     object will be obtained directly from new
00074    *  2. In all other cases, we allocate an object of size exactly
00075    *     _S_round_up(requested_size).  Thus the client has enough size
00076    *     information that we can return the object to the proper free list
00077    *     without permanently losing part of the object.
00078    *
00079    *  @endif
00080    */
00081     class __pool_alloc_base
00082     {
00083     protected:
00084 
00085       enum { _S_align = 8 };
00086       enum { _S_max_bytes = 128 };
00087       enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
00088       
00089       union _Obj
00090       {
00091     union _Obj* _M_free_list_link;
00092     char        _M_client_data[1];    // The client sees this.
00093       };
00094       
00095       static _Obj* volatile         _S_free_list[_S_free_list_size];
00096 
00097       // Chunk allocation state.
00098       static char*                  _S_start_free;
00099       static char*                  _S_end_free;
00100       static size_t                 _S_heap_size;     
00101       
00102       size_t
00103       _M_round_up(size_t __bytes)
00104       { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
00105       
00106       _Obj* volatile*
00107       _M_get_free_list(size_t __bytes);
00108     
00109       __mutex&
00110       _M_get_mutex();
00111 
00112       // Returns an object of size __n, and optionally adds to size __n
00113       // free list.
00114       void*
00115       _M_refill(size_t __n);
00116       
00117       // Allocates a chunk for nobjs of size size.  nobjs may be reduced
00118       // if it is inconvenient to allocate the requested number.
00119       char*
00120       _M_allocate_chunk(size_t __n, int& __nobjs);
00121     };
00122 
00123 
00124   /// @brief  class __pool_alloc.
00125   template<typename _Tp>
00126     class __pool_alloc : private __pool_alloc_base
00127     {
00128     private:
00129       static _Atomic_word       _S_force_new;
00130 
00131     public:
00132       typedef size_t     size_type;
00133       typedef ptrdiff_t  difference_type;
00134       typedef _Tp*       pointer;
00135       typedef const _Tp* const_pointer;
00136       typedef _Tp&       reference;
00137       typedef const _Tp& const_reference;
00138       typedef _Tp        value_type;
00139 
00140       template<typename _Tp1>
00141         struct rebind
00142         { typedef __pool_alloc<_Tp1> other; };
00143 
00144       __pool_alloc() throw() { }
00145 
00146       __pool_alloc(const __pool_alloc&) throw() { }
00147 
00148       template<typename _Tp1>
00149         __pool_alloc(const __pool_alloc<_Tp1>&) throw() { }
00150 
00151       ~__pool_alloc() throw() { }
00152 
00153       pointer
00154       address(reference __x) const { return &__x; }
00155 
00156       const_pointer
00157       address(const_reference __x) const { return &__x; }
00158 
00159       size_type
00160       max_size() const throw() 
00161       { return size_t(-1) / sizeof(_Tp); }
00162 
00163       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00164       // 402. wrong new expression in [some_] allocator::construct
00165       void 
00166       construct(pointer __p, const _Tp& __val) 
00167       { ::new(__p) _Tp(__val); }
00168 
00169       void 
00170       destroy(pointer __p) { __p->~_Tp(); }
00171 
00172       pointer
00173       allocate(size_type __n, const void* = 0);
00174 
00175       void
00176       deallocate(pointer __p, size_type __n);      
00177     };
00178 
00179   template<typename _Tp>
00180     inline bool
00181     operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
00182     { return true; }
00183 
00184   template<typename _Tp>
00185     inline bool
00186     operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
00187     { return false; }
00188 
00189   template<typename _Tp>
00190     _Atomic_word
00191     __pool_alloc<_Tp>::_S_force_new;
00192 
00193   template<typename _Tp>
00194     _Tp*
00195     __pool_alloc<_Tp>::allocate(size_type __n, const void*)
00196     {
00197       pointer __ret = 0;
00198       if (__builtin_expect(__n != 0, true))
00199     {
00200       if (__builtin_expect(__n > this->max_size(), false))
00201         std::__throw_bad_alloc();
00202 
00203       // If there is a race through here, assume answer from getenv
00204       // will resolve in same direction.  Inspired by techniques
00205       // to efficiently support threading found in basic_string.h.
00206       if (_S_force_new == 0)
00207         {
00208           if (std::getenv("GLIBCXX_FORCE_NEW"))
00209         __atomic_add_dispatch(&_S_force_new, 1);
00210           else
00211         __atomic_add_dispatch(&_S_force_new, -1);
00212         }
00213 
00214       const size_t __bytes = __n * sizeof(_Tp);       
00215       if (__bytes > size_t(_S_max_bytes) || _S_force_new == 1)
00216         __ret = static_cast<_Tp*>(::operator new(__bytes));
00217       else
00218         {
00219           _Obj* volatile* __free_list = _M_get_free_list(__bytes);
00220           
00221           __scoped_lock sentry(_M_get_mutex());
00222           _Obj* __restrict__ __result = *__free_list;
00223           if (__builtin_expect(__result == 0, 0))
00224         __ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
00225           else
00226         {
00227           *__free_list = __result->_M_free_list_link;
00228           __ret = reinterpret_cast<_Tp*>(__result);
00229         }
00230           if (__builtin_expect(__ret == 0, 0))
00231         std::__throw_bad_alloc();
00232         }
00233     }
00234       return __ret;
00235     }
00236 
00237   template<typename _Tp>
00238     void
00239     __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)
00240     {
00241       if (__builtin_expect(__n != 0 && __p != 0, true))
00242     {
00243       const size_t __bytes = __n * sizeof(_Tp);
00244       if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new == 1)
00245         ::operator delete(__p);
00246       else
00247         {
00248           _Obj* volatile* __free_list = _M_get_free_list(__bytes);
00249           _Obj* __q = reinterpret_cast<_Obj*>(__p);
00250 
00251           __scoped_lock sentry(_M_get_mutex());
00252           __q ->_M_free_list_link = *__free_list;
00253           *__free_list = __q;
00254         }
00255     }
00256     }
00257 
00258 _GLIBCXX_END_NAMESPACE
00259 
00260 #endif

Generated on Thu Nov 1 13:12:19 2007 for libstdc++ by  doxygen 1.5.1