OSDN Git Service

2011-05-28 Jonathan Wakely <jwakely.gcc@gmail.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / pool_allocator.h
1 // Allocators -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27  * Copyright (c) 1996-1997
28  * Silicon Graphics Computer Systems, Inc.
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation.  Silicon Graphics makes no
35  * representations about the suitability of this software for any
36  * purpose.  It is provided "as is" without express or implied warranty.
37  */
38
39 /** @file ext/pool_allocator.h
40  *  This file is a GNU extension to the Standard C++ Library.
41  */
42
43 #ifndef _POOL_ALLOCATOR_H
44 #define _POOL_ALLOCATOR_H 1
45
46 #include <bits/c++config.h>
47 #include <cstdlib>
48 #include <new>
49 #include <bits/functexcept.h>
50 #include <ext/atomicity.h>
51 #include <ext/concurrence.h>
52 #include <bits/move.h>
53
54 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
55 {
56 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57
58   using std::size_t;
59   using std::ptrdiff_t;
60
61   /**
62    *  @brief  Base class for __pool_alloc.
63    *
64    *  Uses various allocators to fulfill underlying requests (and makes as
65    *  few requests as possible when in default high-speed pool mode).
66    *
67    *  Important implementation properties:
68    *  0. If globally mandated, then allocate objects from new
69    *  1. If the clients request an object of size > _S_max_bytes, the resulting
70    *     object will be obtained directly from new
71    *  2. In all other cases, we allocate an object of size exactly
72    *     _S_round_up(requested_size).  Thus the client has enough size
73    *     information that we can return the object to the proper free list
74    *     without permanently losing part of the object.
75    */
76     class __pool_alloc_base
77     {
78     protected:
79
80       enum { _S_align = 8 };
81       enum { _S_max_bytes = 128 };
82       enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
83       
84       union _Obj
85       {
86         union _Obj* _M_free_list_link;
87         char        _M_client_data[1];    // The client sees this.
88       };
89       
90       static _Obj* volatile         _S_free_list[_S_free_list_size];
91
92       // Chunk allocation state.
93       static char*                  _S_start_free;
94       static char*                  _S_end_free;
95       static size_t                 _S_heap_size;     
96       
97       size_t
98       _M_round_up(size_t __bytes)
99       { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
100       
101       _GLIBCXX_CONST _Obj* volatile*
102       _M_get_free_list(size_t __bytes) throw ();
103     
104       __mutex&
105       _M_get_mutex() throw ();
106
107       // Returns an object of size __n, and optionally adds to size __n
108       // free list.
109       void*
110       _M_refill(size_t __n);
111       
112       // Allocates a chunk for nobjs of size size.  nobjs may be reduced
113       // if it is inconvenient to allocate the requested number.
114       char*
115       _M_allocate_chunk(size_t __n, int& __nobjs);
116     };
117
118
119   /**
120    * @brief  Allocator using a memory pool with a single lock.
121    * @ingroup allocators
122    */
123   template<typename _Tp>
124     class __pool_alloc : private __pool_alloc_base
125     {
126     private:
127       static _Atomic_word           _S_force_new;
128
129     public:
130       typedef size_t     size_type;
131       typedef ptrdiff_t  difference_type;
132       typedef _Tp*       pointer;
133       typedef const _Tp* const_pointer;
134       typedef _Tp&       reference;
135       typedef const _Tp& const_reference;
136       typedef _Tp        value_type;
137
138       template<typename _Tp1>
139         struct rebind
140         { typedef __pool_alloc<_Tp1> other; };
141
142       __pool_alloc() throw() { }
143
144       __pool_alloc(const __pool_alloc&) throw() { }
145
146       template<typename _Tp1>
147         __pool_alloc(const __pool_alloc<_Tp1>&) throw() { }
148
149       ~__pool_alloc() throw() { }
150
151       pointer
152       address(reference __x) const { return std::__addressof(__x); }
153
154       const_pointer
155       address(const_reference __x) const { return std::__addressof(__x); }
156
157       size_type
158       max_size() const throw() 
159       { return size_t(-1) / sizeof(_Tp); }
160
161 #ifdef __GXX_EXPERIMENTAL_CXX0X__
162       template<typename _Up, typename... _Args>
163         void
164         construct(_Up* __p, _Args&&... __args)
165         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
166
167       template<typename _Up>
168         void 
169         destroy(_Up* __p) { __p->~_Up(); }
170 #else
171       // _GLIBCXX_RESOLVE_LIB_DEFECTS
172       // 402. wrong new expression in [some_] allocator::construct
173       void 
174       construct(pointer __p, const _Tp& __val) 
175       { ::new((void *)__p) _Tp(__val); }
176
177       void 
178       destroy(pointer __p) { __p->~_Tp(); }
179 #endif
180
181       pointer
182       allocate(size_type __n, const void* = 0);
183
184       void
185       deallocate(pointer __p, size_type __n);      
186     };
187
188   template<typename _Tp>
189     inline bool
190     operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
191     { return true; }
192
193   template<typename _Tp>
194     inline bool
195     operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
196     { return false; }
197
198   template<typename _Tp>
199     _Atomic_word
200     __pool_alloc<_Tp>::_S_force_new;
201
202   template<typename _Tp>
203     _Tp*
204     __pool_alloc<_Tp>::allocate(size_type __n, const void*)
205     {
206       pointer __ret = 0;
207       if (__builtin_expect(__n != 0, true))
208         {
209           if (__n > this->max_size())
210             std::__throw_bad_alloc();
211
212           // If there is a race through here, assume answer from getenv
213           // will resolve in same direction.  Inspired by techniques
214           // to efficiently support threading found in basic_string.h.
215           if (_S_force_new == 0)
216             {
217               if (std::getenv("GLIBCXX_FORCE_NEW"))
218                 __atomic_add_dispatch(&_S_force_new, 1);
219               else
220                 __atomic_add_dispatch(&_S_force_new, -1);
221             }
222
223           const size_t __bytes = __n * sizeof(_Tp);           
224           if (__bytes > size_t(_S_max_bytes) || _S_force_new > 0)
225             __ret = static_cast<_Tp*>(::operator new(__bytes));
226           else
227             {
228               _Obj* volatile* __free_list = _M_get_free_list(__bytes);
229               
230               __scoped_lock sentry(_M_get_mutex());
231               _Obj* __restrict__ __result = *__free_list;
232               if (__builtin_expect(__result == 0, 0))
233                 __ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
234               else
235                 {
236                   *__free_list = __result->_M_free_list_link;
237                   __ret = reinterpret_cast<_Tp*>(__result);
238                 }
239               if (__ret == 0)
240                 std::__throw_bad_alloc();
241             }
242         }
243       return __ret;
244     }
245
246   template<typename _Tp>
247     void
248     __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)
249     {
250       if (__builtin_expect(__n != 0 && __p != 0, true))
251         {
252           const size_t __bytes = __n * sizeof(_Tp);
253           if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new > 0)
254             ::operator delete(__p);
255           else
256             {
257               _Obj* volatile* __free_list = _M_get_free_list(__bytes);
258               _Obj* __q = reinterpret_cast<_Obj*>(__p);
259
260               __scoped_lock sentry(_M_get_mutex());
261               __q ->_M_free_list_link = *__free_list;
262               *__free_list = __q;
263             }
264         }
265     }
266
267 _GLIBCXX_END_NAMESPACE_VERSION
268 } // namespace
269
270 #endif