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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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 */
46
47#ifndef _POOL_ALLOCATOR_H
48#define _POOL_ALLOCATOR_H 1
49
50#include <bits/c++config.h>
51#include <cstdlib>
52#include <new>
53#include <bits/functexcept.h>
54#include <bits/atomicity.h>
55#include <bits/concurrence.h>
56
57namespace __gnu_cxx
58{
59  /**
60   *  @brief  Base class for __pool_alloc.
61   *
62   *  @if maint
63   *  Uses various allocators to fulfill underlying requests (and makes as
64   *  few requests as possible when in default high-speed pool mode).
65   *
66   *  Important implementation properties:
67   *  0. If globally mandated, then allocate objects from new
68   *  1. If the clients request an object of size > _S_max_bytes, the resulting
69   *     object will be obtained directly from new
70   *  2. In all other cases, we allocate an object of size exactly
71   *     _S_round_up(requested_size).  Thus the client has enough size
72   *     information that we can return the object to the proper free list
73   *     without permanently losing part of the object.
74   *
75   *  @endif
76   */
77    class __pool_alloc_base
78    {
79    protected:
80
81      enum { _S_align = 8 };
82      enum { _S_max_bytes = 128 };
83      enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
84
85      union _Obj
86      {
87	union _Obj* _M_free_list_link;
88	char        _M_client_data[1];    // The client sees this.
89      };
90
91      static _Obj* volatile         _S_free_list[_S_free_list_size];
92
93      // Chunk allocation state.
94      static char*                  _S_start_free;
95      static char*                  _S_end_free;
96      static size_t                 _S_heap_size;
97
98      size_t
99      _M_round_up(size_t __bytes)
100      { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
101
102      _Obj* volatile*
103      _M_get_free_list(size_t __bytes);
104
105      mutex_type&
106      _M_get_mutex();
107
108      // Returns an object of size __n, and optionally adds to size __n
109      // free list.
110      void*
111      _M_refill(size_t __n);
112
113      // Allocates a chunk for nobjs of size size.  nobjs may be reduced
114      // if it is inconvenient to allocate the requested number.
115      char*
116      _M_allocate_chunk(size_t __n, int& __nobjs);
117    };
118
119
120  /// @brief  class __pool_alloc.
121  template<typename _Tp>
122    class __pool_alloc : private __pool_alloc_base
123    {
124    private:
125      static _Atomic_word	    _S_force_new;
126
127    public:
128      typedef size_t     size_type;
129      typedef ptrdiff_t  difference_type;
130      typedef _Tp*       pointer;
131      typedef const _Tp* const_pointer;
132      typedef _Tp&       reference;
133      typedef const _Tp& const_reference;
134      typedef _Tp        value_type;
135
136      template<typename _Tp1>
137        struct rebind
138        { typedef __pool_alloc<_Tp1> other; };
139
140      __pool_alloc() throw() { }
141
142      __pool_alloc(const __pool_alloc&) throw() { }
143
144      template<typename _Tp1>
145        __pool_alloc(const __pool_alloc<_Tp1>&) throw() { }
146
147      ~__pool_alloc() throw() { }
148
149      pointer
150      address(reference __x) const { return &__x; }
151
152      const_pointer
153      address(const_reference __x) const { return &__x; }
154
155      size_type
156      max_size() const throw()
157      { return size_t(-1) / sizeof(_Tp); }
158
159      // _GLIBCXX_RESOLVE_LIB_DEFECTS
160      // 402. wrong new expression in [some_] allocator::construct
161      void
162      construct(pointer __p, const _Tp& __val)
163      { ::new(__p) _Tp(__val); }
164
165      void
166      destroy(pointer __p) { __p->~_Tp(); }
167
168      pointer
169      allocate(size_type __n, const void* = 0);
170
171      void
172      deallocate(pointer __p, size_type __n);
173    };
174
175  template<typename _Tp>
176    inline bool
177    operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
178    { return true; }
179
180  template<typename _Tp>
181    inline bool
182    operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
183    { return false; }
184
185  template<typename _Tp>
186    _Atomic_word
187    __pool_alloc<_Tp>::_S_force_new;
188
189  template<typename _Tp>
190    _Tp*
191    __pool_alloc<_Tp>::allocate(size_type __n, const void*)
192    {
193      pointer __ret = 0;
194      if (__builtin_expect(__n != 0, true))
195	{
196	  if (__builtin_expect(__n > this->max_size(), false))
197	    std::__throw_bad_alloc();
198
199	  // If there is a race through here, assume answer from getenv
200	  // will resolve in same direction.  Inspired by techniques
201	  // to efficiently support threading found in basic_string.h.
202	  if (_S_force_new == 0)
203	    {
204	      if (getenv("GLIBCXX_FORCE_NEW"))
205		__atomic_add(&_S_force_new, 1);
206	      else
207		__atomic_add(&_S_force_new, -1);
208	    }
209
210	  const size_t __bytes = __n * sizeof(_Tp);
211	  if (__bytes > size_t(_S_max_bytes) || _S_force_new == 1)
212	    __ret = static_cast<_Tp*>(::operator new(__bytes));
213	  else
214	    {
215	      _Obj* volatile* __free_list = _M_get_free_list(__bytes);
216
217	      lock sentry(_M_get_mutex());
218	      _Obj* __restrict__ __result = *__free_list;
219	      if (__builtin_expect(__result == 0, 0))
220		__ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
221	      else
222		{
223		  *__free_list = __result->_M_free_list_link;
224		  __ret = reinterpret_cast<_Tp*>(__result);
225		}
226	      if (__builtin_expect(__ret == 0, 0))
227		std::__throw_bad_alloc();
228	    }
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 (__builtin_expect(__n != 0 && __p != 0, true))
238	{
239	  const size_t __bytes = __n * sizeof(_Tp);
240	  if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new == 1)
241	    ::operator delete(__p);
242	  else
243	    {
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;
249	      *__free_list = __q;
250	    }
251	}
252    }
253} // namespace __gnu_cxx
254
255#endif
256