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