2 * Copyright (c) 1996-1997
3 * Silicon Graphics Computer Systems, Inc.
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation. Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose. It is provided "as is" without express or implied warranty.
14 /* NOTE: This is an internal header file, included by other STL headers.
15 * You should not attempt to use it directly.
18 #ifndef __SGI_STL_INTERNAL_ALLOC_H
19 #define __SGI_STL_INTERNAL_ALLOC_H
22 # define __PRIVATE public
23 // Extra access restrictions prevent us from really making some things
26 # define __PRIVATE private
29 #ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
34 // This implements some standard node allocators. These are
35 // NOT the same as the allocators in the C++ draft standard or in
36 // in the original STL. They do not encapsulate different pointer
37 // types; indeed we assume that there is only one pointer type.
38 // The allocation primitives are intended to allocate individual objects,
39 // not larger arenas as with the original STL allocators.
43 # define __THROW_BAD_ALLOC throw bad_alloc()
44 #elif !defined(__THROW_BAD_ALLOC)
45 # include <iostream.h>
46 # define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
49 #ifdef __STL_WIN32THREADS
61 #if !defined(__STL_PTHREADS) && !defined(__STL_SOLTHREADS) \
62 && !defined(_NOTHREADS) \
63 && !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS)
67 # ifdef __STL_PTHREADS
69 // This is dubious, since this is likely to be a high contention
70 // lock. Performance may not be adequate.
72 # define __NODE_ALLOCATOR_LOCK \
73 if (threads) pthread_mutex_lock(&_S_node_allocator_lock)
74 # define __NODE_ALLOCATOR_UNLOCK \
75 if (threads) pthread_mutex_unlock(&_S_node_allocator_lock)
76 # define __NODE_ALLOCATOR_THREADS true
77 # define __VOLATILE volatile // Needed at -O3 on SGI
79 # ifdef __STL_SOLTHREADS
81 # define __NODE_ALLOCATOR_LOCK \
82 if (threads) mutex_lock(&_S_node_allocator_lock)
83 # define __NODE_ALLOCATOR_UNLOCK \
84 if (threads) mutex_unlock(&_S_node_allocator_lock)
85 # define __NODE_ALLOCATOR_THREADS true
88 # ifdef __STL_WIN32THREADS
89 // The lock needs to be initialized by constructing an allocator
90 // objects of the right type. We do that here explicitly for alloc.
91 # define __NODE_ALLOCATOR_LOCK \
92 EnterCriticalSection(&_S_node_allocator_lock)
93 # define __NODE_ALLOCATOR_UNLOCK \
94 LeaveCriticalSection(&_S_node_allocator_lock)
95 # define __NODE_ALLOCATOR_THREADS true
96 # define __VOLATILE volatile // may not be needed
97 # endif /* WIN32THREADS */
98 # ifdef __STL_SGI_THREADS
99 // This should work without threads, with sproc threads, or with
100 // pthreads. It is suboptimal in all cases.
101 // It is unlikely to even compile on nonSGI machines.
104 extern int __us_rsthread_malloc
;
106 // The above is copied from malloc.h. Including <malloc.h>
107 // would be cleaner but fails with certain levels of standard
109 # define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
110 { _S_lock(&_S_node_allocator_lock); }
111 # define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
112 { _S_unlock(&_S_node_allocator_lock); }
113 # define __NODE_ALLOCATOR_THREADS true
114 # define __VOLATILE volatile // Needed at -O3 on SGI
118 # define __NODE_ALLOCATOR_LOCK
119 # define __NODE_ALLOCATOR_UNLOCK
120 # define __NODE_ALLOCATOR_THREADS false
124 __STL_BEGIN_NAMESPACE
126 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
127 #pragma set woff 1174
130 // Malloc-based allocator. Typically slower than default alloc below.
131 // Typically thread-safe and more storage efficient.
132 #ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
133 # ifdef __DECLARE_GLOBALS_HERE
134 void (* __malloc_alloc_oom_handler
)() = 0;
135 // g++ 2.7.2 does not handle static template data members.
137 extern void (* __malloc_alloc_oom_handler
)();
141 template <int __inst
>
142 class __malloc_alloc_template
{
146 static void* _S_oom_malloc(size_t);
147 static void* _S_oom_realloc(void*, size_t);
149 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
150 static void (* __malloc_alloc_oom_handler
)();
155 static void* allocate(size_t __n
)
157 void* __result
= malloc(__n
);
158 if (0 == __result
) __result
= _S_oom_malloc(__n
);
162 static void deallocate(void* __p
, size_t /* __n */)
167 static void* reallocate(void* __p
, size_t /* old_sz */, size_t __new_sz
)
169 void* __result
= realloc(__p
, __new_sz
);
170 if (0 == __result
) __result
= _S_oom_realloc(__p
, __new_sz
);
174 static void (* __set_malloc_handler(void (*__f
)()))()
176 void (* __old
)() = __malloc_alloc_oom_handler
;
177 __malloc_alloc_oom_handler
= __f
;
183 // malloc_alloc out-of-memory handling
185 #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
186 template <int __inst
>
187 void (* __malloc_alloc_template
<__inst
>::__malloc_alloc_oom_handler
)() = 0;
190 template <int __inst
>
192 __malloc_alloc_template
<__inst
>::_S_oom_malloc(size_t __n
)
194 void (* __my_malloc_handler
)();
198 __my_malloc_handler
= __malloc_alloc_oom_handler
;
199 if (0 == __my_malloc_handler
) { __THROW_BAD_ALLOC
; }
200 (*__my_malloc_handler
)();
201 __result
= malloc(__n
);
202 if (__result
) return(__result
);
206 template <int __inst
>
207 void* __malloc_alloc_template
<__inst
>::_S_oom_realloc(void* __p
, size_t __n
)
209 void (* __my_malloc_handler
)();
213 __my_malloc_handler
= __malloc_alloc_oom_handler
;
214 if (0 == __my_malloc_handler
) { __THROW_BAD_ALLOC
; }
215 (*__my_malloc_handler
)();
216 __result
= realloc(__p
, __n
);
217 if (__result
) return(__result
);
221 typedef __malloc_alloc_template
<0> malloc_alloc
;
223 template<class _Tp
, class _Alloc
>
227 static _Tp
* allocate(size_t __n
)
228 { return 0 == __n
? 0 : (_Tp
*) _Alloc::allocate(__n
* sizeof (_Tp
)); }
229 static _Tp
* allocate(void)
230 { return (_Tp
*) _Alloc::allocate(sizeof (_Tp
)); }
231 static void deallocate(_Tp
* __p
, size_t __n
)
232 { if (0 != __n
) _Alloc::deallocate(__p
, __n
* sizeof (_Tp
)); }
233 static void deallocate(_Tp
* __p
)
234 { _Alloc::deallocate(__p
, sizeof (_Tp
)); }
237 // Allocator adaptor to check size arguments for debugging.
238 // Reports errors using assert. Checking can be disabled with
239 // NDEBUG, but it's far better to just use the underlying allocator
240 // instead when no checking is desired.
241 // There is some evidence that this can confuse Purify.
242 template <class _Alloc
>
247 enum {_S_extra
= 8}; // Size of space used to store size. Note
248 // that this must be large enough to preserve
253 static void* allocate(size_t __n
)
255 char* __result
= (char*)_Alloc::allocate(__n
+ _S_extra
);
256 *(size_t*)__result
= __n
;
257 return __result
+ _S_extra
;
260 static void deallocate(void* __p
, size_t __n
)
262 char* __real_p
= (char*)__p
- _S_extra
;
263 assert(*(size_t*)__real_p
== __n
);
264 _Alloc::deallocate(__real_p
, __n
+ _S_extra
);
267 static void* reallocate(void* __p
, size_t __old_sz
, size_t __new_sz
)
269 char* __real_p
= (char*)__p
- _S_extra
;
270 assert(*(size_t*)__real_p
== __old_sz
);
271 char* __result
= (char*)
272 _Alloc::reallocate(__real_p
, __old_sz
+ _S_extra
, __new_sz
+ _S_extra
);
273 *(size_t*)__result
= __new_sz
;
274 return __result
+ _S_extra
;
282 typedef malloc_alloc alloc
;
283 typedef malloc_alloc single_client_alloc
;
288 // Default node allocator.
289 // With a reasonable compiler, this should be roughly as fast as the
290 // original STL class-specific allocators, but with less fragmentation.
291 // Default_alloc_template parameters are experimental and MAY
292 // DISAPPEAR in the future. Clients should just use alloc for now.
294 // Important implementation properties:
295 // 1. If the client request an object of size > _MAX_BYTES, the resulting
296 // object will be obtained directly from malloc.
297 // 2. In all other cases, we allocate an object of size exactly
298 // _S_round_up(requested_size). Thus the client has enough size
299 // information that we can return the object to the proper free list
300 // without permanently losing part of the object.
303 // The first template parameter specifies whether more than one thread
304 // may use this allocator. It is safe to allocate an object from
305 // one instance of a default_alloc and deallocate it with another
306 // one. This effectively transfers its ownership to the second one.
307 // This may have undesirable effects on reference locality.
308 // The second parameter is unreferenced and serves only to allow the
309 // creation of multiple default_alloc instances.
310 // Node that containers built on different allocator instances have
311 // different types, limiting the utility of this approach.
313 // breaks if we make these template class members:
315 enum {_MAX_BYTES
= 128};
316 enum {_NFREELISTS
= _MAX_BYTES
/_ALIGN
};
319 template <bool threads
, int inst
>
320 class __default_alloc_template
{
323 // Really we should use static const int x = N
324 // instead of enum { x = N }, but few compilers accept the former.
327 enum {_MAX_BYTES
= 128};
328 enum {_NFREELISTS
= _MAX_BYTES
/_ALIGN
};
331 _S_round_up(size_t __bytes
)
332 { return (((__bytes
) + _ALIGN
-1) & ~(_ALIGN
- 1)); }
336 union _Obj
* _M_free_list_link
;
337 char _M_client_data
[1]; /* The client sees this. */
341 static _Obj
* __VOLATILE _S_free_list
[];
342 // Specifying a size results in duplicate def for 4.1
344 static _Obj
* __VOLATILE _S_free_list
[_NFREELISTS
];
346 static size_t _S_freelist_index(size_t __bytes
) {
347 return (((__bytes
) + _ALIGN
-1)/_ALIGN
- 1);
350 // Returns an object of size __n, and optionally adds to size __n free list.
351 static void* _S_refill(size_t __n
);
352 // Allocates a chunk for nobjs of size "size". nobjs may be reduced
353 // if it is inconvenient to allocate the requested number.
354 static char* _S_chunk_alloc(size_t __size
, int& __nobjs
);
356 // Chunk allocation state.
357 static char* _S_start_free
;
358 static char* _S_end_free
;
359 static size_t _S_heap_size
;
361 # ifdef __STL_SGI_THREADS
362 static volatile unsigned long _S_node_allocator_lock
;
363 static void _S_lock(volatile unsigned long*);
364 static inline void _S_unlock(volatile unsigned long*);
367 # ifdef __STL_PTHREADS
368 static pthread_mutex_t _S_node_allocator_lock
;
371 # ifdef __STL_SOLTHREADS
372 static mutex_t _S_node_allocator_lock
;
375 # ifdef __STL_WIN32THREADS
376 static CRITICAL_SECTION _S_node_allocator_lock
;
377 static bool _S_node_allocator_lock_initialized
;
380 __default_alloc_template() {
381 // This assumes the first constructor is called before threads
383 if (!_S_node_allocator_lock_initialized
) {
384 InitializeCriticalSection(&_S_node_allocator_lock
);
385 _S_node_allocator_lock_initialized
= true;
393 _Lock() { __NODE_ALLOCATOR_LOCK
; }
394 ~_Lock() { __NODE_ALLOCATOR_UNLOCK
; }
400 /* __n must be > 0 */
401 static void* allocate(size_t __n
)
403 _Obj
* __VOLATILE
* __my_free_list
;
404 _Obj
* __RESTRICT __result
;
406 if (__n
> (size_t) _MAX_BYTES
) {
407 return(malloc_alloc::allocate(__n
));
409 __my_free_list
= _S_free_list
+ _S_freelist_index(__n
);
410 // Acquire the lock here with a constructor call.
411 // This ensures that it is released in exit or during stack
415 _Lock __lock_instance
;
417 __result
= *__my_free_list
;
419 void* __r
= _S_refill(_S_round_up(__n
));
422 *__my_free_list
= __result
-> _M_free_list_link
;
426 /* __p may not be 0 */
427 static void deallocate(void* __p
, size_t __n
)
429 _Obj
* __q
= (_Obj
*)__p
;
430 _Obj
* __VOLATILE
* __my_free_list
;
432 if (__n
> (size_t) _MAX_BYTES
) {
433 malloc_alloc::deallocate(__p
, __n
);
436 __my_free_list
= _S_free_list
+ _S_freelist_index(__n
);
440 _Lock __lock_instance
;
441 # endif /* _NOTHREADS */
442 __q
-> _M_free_list_link
= *__my_free_list
;
443 *__my_free_list
= __q
;
444 // lock is released here
447 static void* reallocate(void* __p
, size_t __old_sz
, size_t __new_sz
);
451 typedef __default_alloc_template
<__NODE_ALLOCATOR_THREADS
, 0> alloc
;
452 typedef __default_alloc_template
<false, 0> single_client_alloc
;
456 /* We allocate memory in large chunks in order to avoid fragmenting */
457 /* the malloc heap too much. */
458 /* We assume that size is properly aligned. */
459 /* We hold the allocation lock. */
460 template <bool __threads
, int __inst
>
462 __default_alloc_template
<__threads
, __inst
>::_S_chunk_alloc(size_t __size
,
466 size_t __total_bytes
= __size
* __nobjs
;
467 size_t __bytes_left
= _S_end_free
- _S_start_free
;
469 if (__bytes_left
>= __total_bytes
) {
470 __result
= _S_start_free
;
471 _S_start_free
+= __total_bytes
;
473 } else if (__bytes_left
>= __size
) {
474 __nobjs
= (int)(__bytes_left
/__size
);
475 __total_bytes
= __size
* __nobjs
;
476 __result
= _S_start_free
;
477 _S_start_free
+= __total_bytes
;
480 size_t __bytes_to_get
=
481 2 * __total_bytes
+ _S_round_up(_S_heap_size
>> 4);
482 // Try to make use of the left-over piece.
483 if (__bytes_left
> 0) {
484 _Obj
* __VOLATILE
* __my_free_list
=
485 _S_free_list
+ _S_freelist_index(__bytes_left
);
487 ((_Obj
*)_S_start_free
) -> _M_free_list_link
= *__my_free_list
;
488 *__my_free_list
= (_Obj
*)_S_start_free
;
490 _S_start_free
= (char*)malloc(__bytes_to_get
);
491 if (0 == _S_start_free
) {
493 _Obj
* __VOLATILE
* __my_free_list
;
495 // Try to make do with what we have. That can't
496 // hurt. We do not try smaller requests, since that tends
497 // to result in disaster on multi-process machines.
498 for (__i
= __size
; __i
<= _MAX_BYTES
; __i
+= _ALIGN
) {
499 __my_free_list
= _S_free_list
+ _S_freelist_index(__i
);
500 __p
= *__my_free_list
;
502 *__my_free_list
= __p
-> _M_free_list_link
;
503 _S_start_free
= (char*)__p
;
504 _S_end_free
= _S_start_free
+ __i
;
505 return(_S_chunk_alloc(__size
, __nobjs
));
506 // Any leftover piece will eventually make it to the
510 _S_end_free
= 0; // In case of exception.
511 _S_start_free
= (char*)malloc_alloc::allocate(__bytes_to_get
);
512 // This should either throw an
513 // exception or remedy the situation. Thus we assume it
516 _S_heap_size
+= __bytes_to_get
;
517 _S_end_free
= _S_start_free
+ __bytes_to_get
;
518 return(_S_chunk_alloc(__size
, __nobjs
));
523 /* Returns an object of size __n, and optionally adds to size __n free list.*/
524 /* We assume that __n is properly aligned. */
525 /* We hold the allocation lock. */
526 template <bool __threads
, int __inst
>
528 __default_alloc_template
<__threads
, __inst
>::_S_refill(size_t __n
)
531 char* __chunk
= _S_chunk_alloc(__n
, __nobjs
);
532 _Obj
* __VOLATILE
* __my_free_list
;
538 if (1 == __nobjs
) return(__chunk
);
539 __my_free_list
= _S_free_list
+ _S_freelist_index(__n
);
541 /* Build free list in chunk */
542 __result
= (_Obj
*)__chunk
;
543 *__my_free_list
= __next_obj
= (_Obj
*)(__chunk
+ __n
);
544 for (__i
= 1; ; __i
++) {
545 __current_obj
= __next_obj
;
546 __next_obj
= (_Obj
*)((char*)__next_obj
+ __n
);
547 if (__nobjs
- 1 == __i
) {
548 __current_obj
-> _M_free_list_link
= 0;
551 __current_obj
-> _M_free_list_link
= __next_obj
;
557 template <bool threads
, int inst
>
559 __default_alloc_template
<threads
, inst
>::reallocate(void* __p
,
566 if (__old_sz
> (size_t) _MAX_BYTES
&& __new_sz
> (size_t) _MAX_BYTES
) {
567 return(realloc(__p
, __new_sz
));
569 if (_S_round_up(__old_sz
) == _S_round_up(__new_sz
)) return(__p
);
570 __result
= allocate(__new_sz
);
571 __copy_sz
= __new_sz
> __old_sz
? __old_sz
: __new_sz
;
572 memcpy(__result
, __p
, __copy_sz
);
573 deallocate(__p
, __old_sz
);
577 #ifdef __STL_PTHREADS
578 template <bool __threads
, int __inst
>
580 __default_alloc_template
<__threads
, __inst
>::_S_node_allocator_lock
581 = PTHREAD_MUTEX_INITIALIZER
;
584 #ifdef __STL_SOLTHREADS
585 template <bool __threads
, int __inst
>
587 __default_alloc_template
<__threads
, __inst
>::_S_node_allocator_lock
591 #ifdef __STL_WIN32THREADS
592 template <bool __threads
, int __inst
>
594 __default_alloc_template
<__threads
, __inst
>::
595 _S_node_allocator_lock
;
597 template <bool __threads
, int __inst
>
599 __default_alloc_template
<__threads
, __inst
>::
600 _S_node_allocator_lock_initialized
604 #ifdef __STL_SGI_THREADS
607 #include <time.h> /* XXX should use <ctime> */
608 __STL_BEGIN_NAMESPACE
609 // Somewhat generic lock implementations. We need only test-and-set
610 // and some way to sleep. These should work with both SGI pthreads
611 // and sproc threads. They may be useful on other systems.
612 template <bool __threads
, int __inst
>
613 volatile unsigned long
614 __default_alloc_template
<__threads
, __inst
>::_S_node_allocator_lock
= 0;
616 #if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__)
617 # define __test_and_set(l,v) test_and_set(l,v)
620 template <bool __threads
, int __inst
>
622 __default_alloc_template
<__threads
, __inst
>::
623 _S_lock(volatile unsigned long* __lock
)
625 const unsigned __low_spin_max
= 30; // spins if we suspect uniprocessor
626 const unsigned __high_spin_max
= 1000; // spins for multiprocessor
627 static unsigned __spin_max
= __low_spin_max
;
628 unsigned __my_spin_max
;
629 static unsigned __last_spins
= 0;
630 unsigned __my_last_spins
;
632 # define __ALLOC_PAUSE \
633 __junk *= __junk; __junk *= __junk; __junk *= __junk; __junk *= __junk
636 if (!__test_and_set((unsigned long*)__lock
, 1)) {
639 __my_spin_max
= __spin_max
;
640 __my_last_spins
= __last_spins
;
641 for (__i
= 0; __i
< __my_spin_max
; __i
++) {
642 if (__i
< __my_last_spins
/2 || *__lock
) {
646 if (!__test_and_set((unsigned long*)__lock
, 1)) {
648 // Spinning worked. Thus we're probably not being scheduled
649 // against the other process with which we were contending.
650 // Thus it makes sense to spin longer the next time.
652 __spin_max
= __high_spin_max
;
656 // We are probably being scheduled against the other process. Sleep.
657 __spin_max
= __low_spin_max
;
658 for (__i
= 0 ;; ++__i
) {
659 struct timespec __ts
;
660 int __log_nsec
= __i
+ 6;
662 if (!__test_and_set((unsigned long *)__lock
, 1)) {
665 if (__log_nsec
> 27) __log_nsec
= 27;
666 /* Max sleep is 2**27nsec ~ 60msec */
668 __ts
.tv_nsec
= 1 << __log_nsec
;
673 template <bool __threads
, int __inst
>
675 __default_alloc_template
<__threads
, __inst
>::_S_unlock(
676 volatile unsigned long* __lock
)
678 # if defined(__GNUC__) && __mips >= 3
681 # elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64))
682 __lock_release(__lock
);
685 // This is not sufficient on many multiprocessors, since
686 // writes to protected variables and the lock may be reordered.
691 template <bool __threads
, int __inst
>
692 char* __default_alloc_template
<__threads
, __inst
>::_S_start_free
= 0;
694 template <bool __threads
, int __inst
>
695 char* __default_alloc_template
<__threads
, __inst
>::_S_end_free
= 0;
697 template <bool __threads
, int __inst
>
698 size_t __default_alloc_template
<__threads
, __inst
>::_S_heap_size
= 0;
700 template <bool __threads
, int __inst
>
701 __default_alloc_template
<__threads
, __inst
>::_Obj
* __VOLATILE
702 __default_alloc_template
<__threads
, __inst
> ::_S_free_list
[
704 ] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
705 // The 16 zeros are necessary to make version 4.1 of the SunPro
706 // compiler happy. Otherwise it appears to allocate too little
707 // space for the array.
709 # ifdef __STL_WIN32THREADS
710 // Create one to get critical section initialized.
711 // We do this onece per file, but only the first constructor
713 static alloc __node_allocator_dummy_instance
;
716 #endif /* ! __USE_MALLOC */
718 // This implements allocators as specified in the C++ standard.
720 // Note that standard-conforming allocators use many language features
721 // that are not yet widely implemented. In particular, they rely on
722 // member templates, partial specialization, partial ordering of function
723 // templates, the typename keyword, and the use of the template keyword
724 // to refer to a template member of a dependent type.
726 #ifdef __STL_USE_STD_ALLOCATORS
730 typedef alloc _Alloc
; // The underlying allocator.
732 typedef size_t size_type
;
733 typedef ptrdiff_t difference_type
;
734 typedef _Tp
* pointer
;
735 typedef const _Tp
* const_pointer
;
736 typedef _Tp
& reference
;
737 typedef const _Tp
& const_reference
;
738 typedef _Tp value_type
;
740 template <class _Tp1
> struct rebind
{
741 typedef allocator
<_Tp1
> other
;
744 allocator() __STL_NOTHROW
{}
745 allocator(const allocator
&) __STL_NOTHROW
{}
746 template <class _Tp1
> allocator(const allocator
<_Tp1
>&) __STL_NOTHROW
{}
747 ~allocator() __STL_NOTHROW
{}
749 pointer
address(reference __x
) const { return &__x
; }
750 const_pointer
address(const_reference __x
) const { return &__x
; }
752 // __n is permitted to be 0. The C++ standard says nothing about what
753 // the return value is when __n == 0.
754 _Tp
* allocate(size_type __n
, const void* = 0) {
755 return __n
!= 0 ? static_cast<_Tp
*>(_Alloc::allocate(__n
* sizeof(_Tp
)))
759 // __p is not permitted to be a null pointer.
760 void deallocate(pointer __p
, size_type __n
)
761 { _Alloc::deallocate(__p
, __n
* sizeof(_Tp
)); }
763 size_type
max_size() const __STL_NOTHROW
764 { return size_t(-1) / sizeof(_Tp
); }
766 void construct(pointer __p
, const _Tp
& __val
) { new(__p
) _Tp(__val
); }
767 void destroy(pointer __p
) { __p
->~_Tp(); }
771 class allocator
<void> {
772 typedef size_t size_type
;
773 typedef ptrdiff_t difference_type
;
774 typedef void* pointer
;
775 typedef const void* const_pointer
;
776 typedef void value_type
;
778 template <class _Tp1
> struct rebind
{
779 typedef allocator
<_Tp1
> other
;
784 template <class _T1
, class _T2
>
785 inline bool operator==(const allocator
<_T1
>&, const allocator
<_T2
>&)
790 template <class _T1
, class _T2
>
791 inline bool operator!=(const allocator
<_T1
>&, const allocator
<_T2
>&)
796 // Allocator adaptor to turn an SGI-style allocator (e.g. alloc, malloc_alloc)
797 // into a standard-conforming allocator. Note that this adaptor does
798 // *not* assume that all objects of the underlying alloc class are
799 // identical, nor does it assume that all of the underlying alloc's
800 // member functions are static member functions. Note, also, that
801 // __allocator<_Tp, alloc> is essentially the same thing as allocator<_Tp>.
803 template <class _Tp
, class _Alloc
>
805 _Alloc __underlying_alloc
;
807 typedef size_t size_type
;
808 typedef ptrdiff_t difference_type
;
809 typedef _Tp
* pointer
;
810 typedef const _Tp
* const_pointer
;
811 typedef _Tp
& reference
;
812 typedef const _Tp
& const_reference
;
813 typedef _Tp value_type
;
815 template <class _Tp1
> struct rebind
{
816 typedef __allocator
<_Tp1
, _Alloc
> other
;
819 __allocator() __STL_NOTHROW
{}
820 __allocator(const __allocator
& __a
) __STL_NOTHROW
821 : __underlying_alloc(__a
.__underlying_alloc
) {}
822 template <class _Tp1
>
823 __allocator(const __allocator
<_Tp1
, _Alloc
>& __a
) __STL_NOTHROW
824 : __underlying_alloc(__a
.__underlying_alloc
) {}
825 ~__allocator() __STL_NOTHROW
{}
827 pointer
address(reference __x
) const { return &__x
; }
828 const_pointer
address(const_reference __x
) const { return &__x
; }
830 // __n is permitted to be 0.
831 _Tp
* allocate(size_type __n
, const void* = 0) {
833 ? static_cast<_Tp
*>(__underlying_alloc
.allocate(__n
* sizeof(_Tp
)))
837 // __p is not permitted to be a null pointer.
838 void deallocate(pointer __p
, size_type __n
)
839 { __underlying_alloc
.deallocate(__p
, __n
* sizeof(_Tp
)); }
841 size_type
max_size() const __STL_NOTHROW
842 { return size_t(-1) / sizeof(_Tp
); }
844 void construct(pointer __p
, const _Tp
& __val
) { new(__p
) _Tp(__val
); }
845 void destroy(pointer __p
) { __p
->~_Tp(); }
848 template <class _Alloc
>
849 class __allocator
<void, _Alloc
> {
850 typedef size_t size_type
;
851 typedef ptrdiff_t difference_type
;
852 typedef void* pointer
;
853 typedef const void* const_pointer
;
854 typedef void value_type
;
856 template <class _Tp1
> struct rebind
{
857 typedef __allocator
<_Tp1
, _Alloc
> other
;
861 template <class _Tp
, class _Alloc
>
862 inline bool operator==(const __allocator
<_Tp
, _Alloc
>& __a1
,
863 const __allocator
<_Tp
, _Alloc
>& __a2
)
865 return __a1
.__underlying_alloc
== __a2
.__underlying_alloc
;
868 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
869 template <class _Tp
, class _Alloc
>
870 inline bool operator!=(const __allocator
<_Tp
, _Alloc
>& __a1
,
871 const __allocator
<_Tp
, _Alloc
>& __a2
)
873 return __a1
.__underlying_alloc
!= __a2
.__underlying_alloc
;
875 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
877 // Comparison operators for all of the predifined SGI-style allocators.
878 // This ensures that __allocator<malloc_alloc> (for example) will
882 inline bool operator==(const __malloc_alloc_template
<inst
>&,
883 const __malloc_alloc_template
<inst
>&)
888 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
889 template <int __inst
>
890 inline bool operator!=(const __malloc_alloc_template
<__inst
>&,
891 const __malloc_alloc_template
<__inst
>&)
895 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
898 template <bool __threads
, int __inst
>
899 inline bool operator==(const __default_alloc_template
<__threads
, __inst
>&,
900 const __default_alloc_template
<__threads
, __inst
>&)
905 # ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
906 template <bool __threads
, int __inst
>
907 inline bool operator!=(const __default_alloc_template
<__threads
, __inst
>&,
908 const __default_alloc_template
<__threads
, __inst
>&)
912 # endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
915 template <class _Alloc
>
916 inline bool operator==(const debug_alloc
<_Alloc
>&,
917 const debug_alloc
<_Alloc
>&) {
921 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
922 template <class _Alloc
>
923 inline bool operator!=(const debug_alloc
<_Alloc
>&,
924 const debug_alloc
<_Alloc
>&) {
927 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
929 // Another allocator adaptor: _Alloc_traits. This serves two
930 // purposes. First, make it possible to write containers that can use
931 // either SGI-style allocators or standard-conforming allocator.
932 // Second, provide a mechanism so that containers can query whether or
933 // not the allocator has distinct instances. If not, the container
934 // can avoid wasting a word of memory to store an empty object.
936 // This adaptor uses partial specialization. The general case of
937 // _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
938 // standard-conforming allocator, possibly with non-equal instances
939 // and non-static members. (It still behaves correctly even if _Alloc
940 // has static member and if all instances are equal. Refinements
941 // affect performance, not correctness.)
943 // There are always two members: allocator_type, which is a standard-
944 // conforming allocator type for allocating objects of type _Tp, and
945 // _S_instanceless, a static const member of type bool. If
946 // _S_instanceless is true, this means that there is no difference
947 // between any two instances of type allocator_type. Furthermore, if
948 // _S_instanceless is true, then _Alloc_traits has one additional
949 // member: _Alloc_type. This type encapsulates allocation and
950 // deallocation of objects of type _Tp through a static interface; it
951 // has two member functions, whose signatures are
952 // static _Tp* allocate(size_t)
953 // static void deallocate(_Tp*, size_t)
955 // The fully general version.
957 template <class _Tp
, class _Allocator
>
960 static const bool _S_instanceless
= false;
961 typedef typename
_Allocator::__STL_TEMPLATE rebind
<_Tp
>::other
965 template <class _Tp
, class _Allocator
>
966 const bool _Alloc_traits
<_Tp
, _Allocator
>::_S_instanceless
;
968 // The version for the default allocator.
970 template <class _Tp
, class _Tp1
>
971 struct _Alloc_traits
<_Tp
, allocator
<_Tp1
> >
973 static const bool _S_instanceless
= true;
974 typedef simple_alloc
<_Tp
, alloc
> _Alloc_type
;
975 typedef allocator
<_Tp
> allocator_type
;
978 // Versions for the predefined SGI-style allocators.
980 template <class _Tp
, int __inst
>
981 struct _Alloc_traits
<_Tp
, __malloc_alloc_template
<__inst
> >
983 static const bool _S_instanceless
= true;
984 typedef simple_alloc
<_Tp
, __malloc_alloc_template
<__inst
> > _Alloc_type
;
985 typedef __allocator
<_Tp
, __malloc_alloc_template
<__inst
> > allocator_type
;
989 template <class _Tp
, bool __threads
, int __inst
>
990 struct _Alloc_traits
<_Tp
, __default_alloc_template
<__threads
, __inst
> >
992 static const bool _S_instanceless
= true;
993 typedef simple_alloc
<_Tp
, __default_alloc_template
<__threads
, __inst
> >
995 typedef __allocator
<_Tp
, __default_alloc_template
<__threads
, __inst
> >
1000 template <class _Tp
, class _Alloc
>
1001 struct _Alloc_traits
<_Tp
, debug_alloc
<_Alloc
> >
1003 static const bool _S_instanceless
= true;
1004 typedef simple_alloc
<_Tp
, debug_alloc
<_Alloc
> > _Alloc_type
;
1005 typedef __allocator
<_Tp
, debug_alloc
<_Alloc
> > allocator_type
;
1008 // Versions for the __allocator adaptor used with the predefined
1009 // SGI-style allocators.
1011 template <class _Tp
, class _Tp1
, int __inst
>
1012 struct _Alloc_traits
<_Tp
,
1013 __allocator
<_Tp1
, __malloc_alloc_template
<__inst
> > >
1015 static const bool _S_instanceless
= true;
1016 typedef simple_alloc
<_Tp
, __malloc_alloc_template
<__inst
> > _Alloc_type
;
1017 typedef __allocator
<_Tp
, __malloc_alloc_template
<__inst
> > allocator_type
;
1020 #ifndef __USE_MALLOC
1021 template <class _Tp
, class _Tp1
, bool __thr
, int __inst
>
1022 struct _Alloc_traits
<_Tp
,
1024 __default_alloc_template
<__thr
, __inst
> > >
1026 static const bool _S_instanceless
= true;
1027 typedef simple_alloc
<_Tp
, __default_alloc_template
<__thr
,__inst
> >
1029 typedef __allocator
<_Tp
, __default_alloc_template
<__thr
,__inst
> >
1034 template <class _Tp
, class _Tp1
, class _Alloc
>
1035 struct _Alloc_traits
<_Tp
, __allocator
<_Tp1
, debug_alloc
<_Alloc
> > >
1037 static const bool _S_instanceless
= true;
1038 typedef simple_alloc
<_Tp
, debug_alloc
<_Alloc
> > _Alloc_type
;
1039 typedef __allocator
<_Tp
, debug_alloc
<_Alloc
> > allocator_type
;
1043 #endif /* __STL_USE_STD_ALLOCATORS */
1045 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
1046 #pragma reset woff 1174
1053 #endif /* __SGI_STL_INTERNAL_ALLOC_H */