3 * Copyright (c) 1996,1997
4 * Silicon Graphics Computer Systems, Inc.
7 * Moscow Center for SPARC Technology
12 * This material is provided "as is", with absolutely no warranty expressed
13 * or implied. Any use is at your own risk.
15 * Permission to use or copy this software for any purpose is hereby granted
16 * without fee, provided the above notices are retained on all copies.
17 * Permission to modify the code and to distribute modified code is granted,
18 * provided the above notices are retained, and a notice that the code was
19 * modified is included with the above copyright notice.
23 /* NOTE: This is an internal header file, included by other STL headers.
24 * You should not attempt to use it directly.
27 #ifndef _STLP_INTERNAL_ALLOC_H
28 #define _STLP_INTERNAL_ALLOC_H
30 # ifndef _STLP_CSTDDEF
34 #if !defined (_STLP_DEBUG_H) && (defined (_STLP_DEBUG) || defined (_STLP_ASSERTIONS))
35 # include <stl/debug/_debug.h>
38 # ifndef _STLP_CSTDLIB
41 # ifndef _STLP_CSTRING
45 # ifndef __THROW_BAD_ALLOC
46 # if !defined(_STLP_USE_EXCEPTIONS)
47 # if !defined (_STLP_CSTDIO)
50 # if !defined (_STLP_CSTDLIB)
53 # define __THROW_BAD_ALLOC puts("out of memory\n"); exit(1)
54 # else /* !defined(_STLP_USE_EXCEPTIONS) */
55 # define __THROW_BAD_ALLOC throw _STLP_STD::bad_alloc()
56 # endif /* !defined(_STLP_USE_EXCEPTIONS) */
57 # endif /* __THROW_BAD_ALLOC */
59 # ifndef _STLP_INTERNAL_NEW_HEADER
60 # include <stl/_new.h>
63 // #if ! defined (__SYMBIAN32__)
64 #if /* defined (_STLP_THREADS) && */ ! defined (_STLP_INTERNAL_THREADS_H)
65 # include <stl/_threads.h>
69 #ifndef _STLP_INTERNAL_CONSTRUCT_H
70 # include <stl/_construct.h>
74 # define __ALLOC __sgi_alloc
81 #if defined (_STLP_THREADS) || (defined(_STLP_OWN_IOSTREAMS) && ! defined (_STLP_NO_THREADS) && ! defined (_NOTHREADS) )
82 # define _STLP_NODE_ALLOCATOR_THREADS true
84 # define _STLP_NODE_ALLOCATOR_THREADS false
89 # if defined (_STLP_USE_RAW_SGI_ALLOCATORS)
90 template <class _Tp, class _Alloc> struct __allocator;
93 #ifndef _STLP_NO_NODE_ALLOC
95 // Malloc-based allocator. Typically slower than default alloc below.
96 // Typically thread-safe and more storage efficient.
98 typedef void (* __oom_handler_type)();
100 template <int __inst>
101 class __malloc_alloc {
103 static void* _STLP_CALL _S_oom_malloc(size_t);
104 static __oom_handler_type __oom_handler;
106 // this one is needed for proper simple_alloc wrapping
107 typedef char value_type;
108 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES) && defined (_STLP_USE_RAW_SGI_ALLOCATORS)
109 template <class _Tp1> struct rebind {
110 typedef __allocator<_Tp1, __malloc_alloc<__inst> > other;
113 static void* _STLP_CALL allocate(size_t __n) {
114 void* __result = malloc(__n);
115 if (0 == __result) __result = _S_oom_malloc(__n);
118 static void _STLP_CALL deallocate(void* __p, size_t /* __n */) { free((char*)__p); }
119 static __oom_handler_type _STLP_CALL set_malloc_handler(__oom_handler_type __f) {
120 __oom_handler_type __old = __oom_handler;
128 // New-based allocator. Typically slower than default alloc below.
129 // Typically thread-safe and more storage efficient.
130 class _STLP_CLASS_DECLSPEC __new_alloc {
132 // this one is needed for proper simple_alloc wrapping
133 typedef char value_type;
134 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES) && defined(_STLP_USE_RAW_SGI_ALLOCATORS)
135 template <class _Tp1> struct rebind {
136 typedef __allocator<_Tp1, __new_alloc > other;
139 static void* _STLP_CALL allocate(size_t __n) {
140 return __stl_new(__n);
142 static void _STLP_CALL deallocate(void* __p, size_t) { __stl_delete(__p); }
146 // Allocator adaptor to check size arguments for debugging.
147 // Reports errors using assert. Checking can be disabled with
148 // NDEBUG, but it's far better to just use the underlying allocator
149 // instead when no checking is desired.
150 // There is some evidence that this can confuse Purify.
151 // This adaptor can only be applied to raw allocators
153 template <class _Alloc>
154 class __debug_alloc : public _Alloc {
156 typedef _Alloc __allocator_type;
157 typedef typename _Alloc::value_type value_type;
159 struct __alloc_header {
161 size_t __type_size:16;
162 _STLP_UINT32_T _M_size;
163 }; // that is 8 bytes for sure
164 // Sunpro CC has bug on enums, so extra_before/after set explicitly
165 enum { __pad=8, __magic=0xdeba, __deleted_magic = 0xdebd,
166 __shred_byte= _STLP_SHRED_BYTE
169 enum { __extra_before = 16, __extra_after = 8 };
170 // Size of space used to store size. Note
171 // that this must be large enough to preserve
173 static size_t _STLP_CALL __extra_before_chunk() {
174 return (long)__extra_before/sizeof(value_type)+
175 (size_t)((long)__extra_before%sizeof(value_type)>0);
177 static size_t _STLP_CALL __extra_after_chunk() {
178 return (long)__extra_after/sizeof(value_type)+
179 (size_t)((long)__extra_after%sizeof(value_type)>0);
182 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES) && defined (_STLP_USE_RAW_SGI_ALLOCATORS)
183 template <class _Tp1> struct rebind {
184 typedef __allocator< _Tp1, __debug_alloc<_Alloc> > other;
189 static void * _STLP_CALL allocate(size_t);
190 static void _STLP_CALL deallocate(void *, size_t);
193 # if defined(__OS400__)
194 enum {_ALIGN = 16, _ALIGN_SHIFT=4, _MAX_BYTES = 256};
195 # define _STLP_NFREELISTS 16
197 enum {_ALIGN = 8, _ALIGN_SHIFT=3, _MAX_BYTES = 128};
198 # define _STLP_NFREELISTS 16
199 # endif /* __OS400__ */
201 #ifndef _STLP_NO_NODE_ALLOC
203 // Default node allocator.
204 // With a reasonable compiler, this should be roughly as fast as the
205 // original STL class-specific allocators, but with less fragmentation.
206 // Default_alloc_template parameters are experimental and MAY
207 // DISAPPEAR in the future. Clients should just use alloc for now.
209 // Important implementation properties:
210 // 1. If the client request an object of size > _MAX_BYTES, the resulting
211 // object will be obtained directly from malloc.
212 // 2. In all other cases, we allocate an object of size exactly
213 // _S_round_up(requested_size). Thus the client has enough size
214 // information that we can return the object to the proper free list
215 // without permanently losing part of the object.
218 // The first template parameter specifies whether more than one thread
219 // may use this allocator. It is safe to allocate an object from
220 // one instance of a default_alloc and deallocate it with another
221 // one. This effectively transfers its ownership to the second one.
222 // This may have undesirable effects on reference locality.
223 // The second parameter is unreferenced and serves only to allow the
224 // creation of multiple default_alloc instances.
226 class _STLP_CLASS_DECLSPEC _Node_alloc_obj {
228 _Node_alloc_obj * _M_free_list_link;
231 template <bool __threads, int __inst>
234 static inline size_t _STLP_CALL _S_round_up(size_t __bytes) { return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); }
235 typedef _Node_alloc_obj _Obj;
237 // Returns an object of size __n, and optionally adds to size __n free list.
238 static void* _STLP_CALL _S_refill(size_t __n);
239 // Allocates a chunk for nobjs of size size. nobjs may be reduced
240 // if it is inconvenient to allocate the requested number.
241 static char* _STLP_CALL _S_chunk_alloc(size_t __p_size, int& __nobjs);
242 // Chunk allocation state.
243 static _Node_alloc_obj * _STLP_VOLATILE _S_free_list[_STLP_NFREELISTS];
244 static char* _S_start_free;
245 static char* _S_end_free;
246 static size_t _S_heap_size;
247 static void * _STLP_CALL _M_allocate(size_t __n);
248 /* __p may not be 0 */
249 static void _STLP_CALL _M_deallocate(void *__p, size_t __n);
251 // this one is needed for proper simple_alloc wrapping
252 typedef char value_type;
253 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES) && defined (_STLP_USE_RAW_SGI_ALLOCATORS)
254 template <class _Tp1> struct rebind {
255 typedef __allocator<_Tp1, __node_alloc<__threads, __inst> > other;
258 /* __n must be > 0 */
259 static void * _STLP_CALL allocate(size_t __n) {
260 return (__n > (size_t)_MAX_BYTES) ? __stl_new(__n) : _M_allocate(__n); }
261 /* __p may not be 0 */
262 static void _STLP_CALL deallocate(void *__p, size_t __n) {
263 if (__n > (size_t)_MAX_BYTES) __stl_delete(__p); else _M_deallocate(__p, __n); }
266 # if defined (_STLP_USE_TEMPLATE_EXPORT)
267 _STLP_EXPORT_TEMPLATE_CLASS __malloc_alloc<0>;
268 _STLP_EXPORT_TEMPLATE_CLASS __node_alloc<_STLP_NODE_ALLOCATOR_THREADS, 0>;
269 # endif /* _STLP_USE_TEMPLATE_EXPORT */
270 typedef __node_alloc<_STLP_NODE_ALLOCATOR_THREADS, 0> _Node_alloc;
271 # if defined (_STLP_USE_TEMPLATE_EXPORT)
272 _STLP_EXPORT_TEMPLATE_CLASS __debug_alloc<_Node_alloc>;
273 _STLP_EXPORT_TEMPLATE_CLASS __debug_alloc<__new_alloc>;
274 _STLP_EXPORT_TEMPLATE_CLASS __debug_alloc<__malloc_alloc<0> >;
279 # if defined (_STLP_USE_PERTHREAD_ALLOC)
282 // include additional header here
283 # include <stl/_pthread_alloc.h>
284 _STLP_BEGIN_NAMESPACE
286 # if defined ( _STLP_DEBUG_ALLOC )
287 typedef __debug_alloc<__pthread_alloc> __sgi_alloc;
289 typedef __pthread_alloc __sgi_alloc;
290 # endif /* _STLP_DEBUG_ALLOC */
292 typedef __pthread_alloc __single_client_alloc;
293 typedef __pthread_alloc __multithreaded_alloc;
297 # if defined ( _STLP_USE_NEWALLOC )
299 # if defined ( _STLP_DEBUG_ALLOC )
300 typedef __debug_alloc<__new_alloc> __sgi_alloc;
302 typedef __new_alloc __sgi_alloc;
303 # endif /* _STLP_DEBUG_ALLOC */
305 typedef __new_alloc __single_client_alloc;
306 typedef __new_alloc __multithreaded_alloc;
308 # elif defined (_STLP_USE_MALLOC)
310 # if defined ( _STLP_DEBUG_ALLOC )
311 typedef __debug_alloc<__malloc_alloc<0> > __sgi_alloc;
313 typedef __malloc_alloc<0> __sgi_alloc;
314 # endif /* _STLP_DEBUG_ALLOC */
316 typedef __malloc_alloc<0> __single_client_alloc;
317 typedef __malloc_alloc<0> __multithreaded_alloc;
321 # if defined ( _STLP_DEBUG_ALLOC )
322 typedef __debug_alloc<_Node_alloc> __sgi_alloc;
324 typedef _Node_alloc __sgi_alloc;
327 typedef __node_alloc<false, 0> __single_client_alloc;
328 typedef __node_alloc<true, 0> __multithreaded_alloc;
330 # endif /* _STLP_USE_NEWALLOC */
331 # endif /* PTHREAD_ALLOC */
333 // This implements allocators as specified in the C++ standard.
335 // Note that standard-conforming allocators use many language features
336 // that are not yet widely implemented. In particular, they rely on
337 // member templates, partial specialization, partial ordering of function
338 // templates, the typename keyword, and the use of the template keyword
339 // to refer to a template member of a dependent type.
345 typedef _Tp value_type;
346 typedef value_type * pointer;
347 typedef const _Tp* const_pointer;
348 typedef _Tp& reference;
349 typedef const _Tp& const_reference;
350 typedef size_t size_type;
351 typedef ptrdiff_t difference_type;
352 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES)
353 template <class _Tp1> struct rebind {
354 typedef allocator<_Tp1> other;
357 allocator() _STLP_NOTHROW {}
358 # if defined (_STLP_MEMBER_TEMPLATES)
359 template <class _Tp1> allocator(const allocator<_Tp1>&) _STLP_NOTHROW {}
361 allocator(const allocator<_Tp>&) _STLP_NOTHROW {}
362 ~allocator() _STLP_NOTHROW {}
363 pointer address(reference __x) const { return &__x; }
364 const_pointer address(const_reference __x) const { return &__x; }
365 // __n is permitted to be 0. The C++ standard says nothing about what the return value is when __n == 0.
366 _Tp* allocate(size_type __n, const void* = 0) {
367 return __n != 0 ? __REINTERPRET_CAST(value_type*,__sgi_alloc::allocate(__n * sizeof(value_type))) : 0;
369 // __p is permitted to be a null pointer, only if n==0.
370 void deallocate(pointer __p, size_type __n) {
371 _STLP_ASSERT( (__p == 0) == (__n == 0) )
372 if (__p != 0) __sgi_alloc::deallocate((void*)__p, __n * sizeof(value_type));
374 // backwards compatibility
375 void deallocate(pointer __p) const { if (__p != 0) __sgi_alloc::deallocate((void*)__p, sizeof(value_type)); }
376 size_type max_size() const _STLP_NOTHROW { return size_t(-1) / sizeof(value_type); }
377 void construct(pointer __p, const _Tp& __val) { _STLP_STD::_Construct(__p, __val); }
378 void destroy(pointer __p) { _STLP_STD::_Destroy(__p); }
379 # if defined(__MRC__)||(defined(__SC__) && !defined(__DMC__))
380 template <class _T2> bool operator==(const allocator<_T2>&) const _STLP_NOTHROW { return true; }
381 template <class _T2> bool operator!=(const allocator<_T2>&) const _STLP_NOTHROW { return false; }
386 class _STLP_CLASS_DECLSPEC allocator<void> {
388 typedef size_t size_type;
389 typedef ptrdiff_t difference_type;
390 typedef void* pointer;
391 typedef const void* const_pointer;
392 # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
393 typedef void value_type;
395 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES)
396 template <class _Tp1> struct rebind {
397 typedef allocator<_Tp1> other;
400 # if defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)) //*ty 03/24/2001 - MPW compilers get confused on these operator definitions
401 template <class _T2> bool operator==(const allocator<_T2>&) const _STLP_NOTHROW { return true; }
402 template <class _T2> bool operator!=(const allocator<_T2>&) const _STLP_NOTHROW { return false; }
406 #if !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__))) //*ty 03/24/2001 - MPW compilers get confused on these operator definitions
407 template <class _T1, class _T2> inline bool _STLP_CALL operator==(const allocator<_T1>&, const allocator<_T2>&) _STLP_NOTHROW { return true; }
408 template <class _T1, class _T2> inline bool _STLP_CALL operator!=(const allocator<_T1>&, const allocator<_T2>&) _STLP_NOTHROW { return false; }
411 # if defined (_STLP_USE_TEMPLATE_EXPORT)
412 _STLP_EXPORT_TEMPLATE_CLASS allocator<char>;
413 # if defined (_STLP_HAS_WCHAR_T)
414 _STLP_EXPORT_TEMPLATE_CLASS allocator<wchar_t>;
416 # endif /* _STLP_USE_TEMPLATE_EXPORT */
418 // Another allocator adaptor: _Alloc_traits. This serves two
419 // purposes. First, make it possible to write containers that can use
420 // either SGI-style allocators or standard-conforming allocator.
422 // The fully general version.
423 template <class _Tp, class _Allocator>
426 typedef _Allocator _Orig;
427 # if defined (_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM)
428 typedef typename _Allocator::_STLP_TEMPLATE rebind<_Tp> _Rebind_type;
429 typedef typename _Rebind_type::other allocator_type;
430 static allocator_type create_allocator(const _Orig& __a) { return allocator_type(__a); }
432 // this is not actually true, used only to pass this type through
433 // to dynamic overload selection in _STLP_alloc_proxy methods
434 typedef _Allocator allocator_type;
435 # endif /* _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM */
438 #ifndef _STLP_FORCE_ALLOCATORS
439 #define _STLP_FORCE_ALLOCATORS(a,y)
442 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && ! defined (_STLP_MEMBER_TEMPLATE_CLASSES)
443 // The version for the default allocator, for rare occasion when we have partial spec w/o member template classes
444 template <class _Tp, class _Tp1>
445 struct _Alloc_traits<_Tp, allocator<_Tp1> > {
446 typedef allocator<_Tp1> _Orig;
447 typedef allocator<_Tp> allocator_type;
448 static allocator_type create_allocator(const allocator<_Tp1 >& __a) { return allocator_type(__a); }
450 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
452 /* macro to convert the allocator for initialization
453 * not using MEMBER_TEMPLATE_CLASSES as it should work given template constructor */
454 #if defined (_STLP_MEMBER_TEMPLATES) || ! defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
455 /* if _STLP_NO_TEMPLATE_CONVERSIONS is set, the member template constructor is
456 * not used implicitly to convert allocator parameter, so let us do it explicitly */
457 # if defined (_STLP_MEMBER_TEMPLATE_CLASSES) && defined (_STLP_NO_TEMPLATE_CONVERSIONS)
458 # define _STLP_CONVERT_ALLOCATOR(__a, _Tp) __stl_alloc_create(__a,(_Tp*)0)
460 # define _STLP_CONVERT_ALLOCATOR(__a, _Tp) __a
462 /* else convert, but only if partial specialization works, since else
463 * Container::allocator_type won't be different */
465 # define _STLP_CONVERT_ALLOCATOR(__a, _Tp) __stl_alloc_create(__a,(_Tp*)0)
468 # if defined (_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM)
469 template <class _Tp, class _Alloc>
470 inline _STLP_TYPENAME_ON_RETURN_TYPE _Alloc_traits<_Tp, _Alloc>::allocator_type _STLP_CALL
471 __stl_alloc_create(const _Alloc& __a, const _Tp*) {
472 typedef typename _Alloc::_STLP_TEMPLATE rebind<_Tp>::other _Rebound_type;
473 return _Rebound_type(__a);
476 // If custom allocators are being used without member template classes support :
477 // user (on purpose) is forced to define rebind/get operations !!!
478 template <class _Tp1, class _Tp2>
479 inline allocator<_Tp2>& _STLP_CALL
480 __stl_alloc_rebind(allocator<_Tp1>& __a, const _Tp2*) { return (allocator<_Tp2>&)(__a); }
481 template <class _Tp1, class _Tp2>
482 inline allocator<_Tp2> _STLP_CALL
483 __stl_alloc_create(const allocator<_Tp1>&, const _Tp2*) { return allocator<_Tp2>(); }
484 #endif /* _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM */
486 # ifdef _STLP_USE_RAW_SGI_ALLOCATORS
487 // move obsolete stuff out of the way
488 # include <stl/_alloc_old.h>
491 // inheritance is being used for EBO optimization
492 template <class _Value, class _Tp, class _MaybeReboundAlloc>
493 class _STLP_alloc_proxy : public _MaybeReboundAlloc {
495 typedef _MaybeReboundAlloc _Base;
496 typedef _STLP_alloc_proxy<_Value, _Tp, _MaybeReboundAlloc> _Self;
499 inline _STLP_alloc_proxy(const _MaybeReboundAlloc& __a, _Value __p) : _MaybeReboundAlloc(__a), _M_data(__p) {}
502 inline _STLP_alloc_proxy(const _Self& __x) : _MaybeReboundAlloc(__x), _M_data(__x._M_data) {}
503 // construction/destruction
504 inline _Self& operator = (const _Self& __x) {
505 *(_MaybeReboundAlloc*)this = *(_MaybeReboundAlloc*)__x;
506 _M_data = __x._M_data; return *this;
508 inline _Self& operator = (const _Base& __x) { ((_Base&)*this) = __x; return *this; }
510 // Unified interface to perform allocate()/deallocate() with limited
512 #if ! defined (_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM)
513 // else it is rebound already, and allocate() member is accessible
514 inline _Tp* allocate(size_t __n) {
515 return __stl_alloc_rebind(__STATIC_CAST(_Base&,*this),(_Tp*)0).allocate(__n,0);
517 inline void deallocate(_Tp* __p, size_t __n) {
518 __stl_alloc_rebind(__STATIC_CAST(_Base&, *this),(_Tp*)0).deallocate(__p, __n);
520 #endif /* !_STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM */
523 # if defined (_STLP_USE_TEMPLATE_EXPORT)
524 _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<char *,char,allocator<char> >;
525 # if defined (_STLP_HAS_WCHAR_T)
526 _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<wchar_t *,wchar_t,allocator<wchar_t> >;
528 # endif /* _STLP_USE_TEMPLATE_EXPORT */
530 # undef _STLP_NODE_ALLOCATOR_THREADS
534 # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) && !defined (_STLP_LINK_TIME_INSTANTIATION)
535 # include <stl/_alloc.c>
538 #endif /* _STLP_INTERNAL_ALLOC_H */