mirror of
https://review.haiku-os.org/haiku
synced 2024-11-23 07:18:40 +01:00
da82d38f42
all allocations, instead we now directly request the use of malloc/free in stl_config.h. This avoids warnings about 'arrays of size 0' when building any stl-code with -pedantic (like e.g. ICU does). Alternatively, we could active pthread-type threading support, but since in some small tests, I have not been able to see any advantage, I've just added a respective comment. git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@31609 a95241bf-73f2-0310-859d-f6bbb57e9c96
1062 lines
33 KiB
C++
1062 lines
33 KiB
C++
/*
|
|
* Copyright (c) 1996-1997
|
|
* Silicon Graphics Computer Systems, Inc.
|
|
*
|
|
* Permission to use, copy, modify, distribute and sell this software
|
|
* and its documentation for any purpose is hereby granted without fee,
|
|
* provided that the above copyright notice appear in all copies and
|
|
* that both that copyright notice and this permission notice appear
|
|
* in supporting documentation. Silicon Graphics makes no
|
|
* representations about the suitability of this software for any
|
|
* purpose. It is provided "as is" without express or implied warranty.
|
|
*/
|
|
|
|
/* NOTE: This is an internal header file, included by other STL headers.
|
|
* You should not attempt to use it directly.
|
|
*/
|
|
|
|
#ifndef __SGI_STL_INTERNAL_ALLOC_H
|
|
#define __SGI_STL_INTERNAL_ALLOC_H
|
|
|
|
#ifdef __SUNPRO_CC
|
|
# define __PRIVATE public
|
|
// Extra access restrictions prevent us from really making some things
|
|
// private.
|
|
#else
|
|
# define __PRIVATE private
|
|
#endif
|
|
|
|
#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
|
|
# define __USE_MALLOC
|
|
#endif
|
|
|
|
// This implements some standard node allocators. These are
|
|
// NOT the same as the allocators in the C++ draft standard or in
|
|
// in the original STL. They do not encapsulate different pointer
|
|
// types; indeed we assume that there is only one pointer type.
|
|
// The allocation primitives are intended to allocate individual objects,
|
|
// not larger arenas as with the original STL allocators.
|
|
|
|
#if 0
|
|
# include <new>
|
|
# define __THROW_BAD_ALLOC throw bad_alloc()
|
|
#elif !defined(__THROW_BAD_ALLOC)
|
|
#if (defined(__BEOS__) || defined(__HAIKU__))
|
|
# include <stdio.h>
|
|
# define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
|
|
#else
|
|
# include <iostream.h>
|
|
# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
|
|
#endif
|
|
#endif
|
|
|
|
#ifdef __STL_WIN32THREADS
|
|
# include <windows.h>
|
|
#endif
|
|
|
|
#include <stddef.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
#ifndef __RESTRICT
|
|
# define __RESTRICT
|
|
#endif
|
|
|
|
#if !defined(__STL_PTHREADS) && !defined(__STL_SOLTHREADS) \
|
|
&& !defined(_NOTHREADS) \
|
|
&& !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS)
|
|
# define _NOTHREADS
|
|
#endif
|
|
|
|
# ifdef __STL_PTHREADS
|
|
// POSIX Threads
|
|
// This is dubious, since this is likely to be a high contention
|
|
// lock. Performance may not be adequate.
|
|
# include <pthread.h>
|
|
# define __NODE_ALLOCATOR_LOCK \
|
|
if (threads) pthread_mutex_lock(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_UNLOCK \
|
|
if (threads) pthread_mutex_unlock(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_THREADS true
|
|
# define __VOLATILE volatile // Needed at -O3 on SGI
|
|
# endif
|
|
# ifdef __STL_SOLTHREADS
|
|
# include <thread.h>
|
|
# define __NODE_ALLOCATOR_LOCK \
|
|
if (threads) mutex_lock(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_UNLOCK \
|
|
if (threads) mutex_unlock(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_THREADS true
|
|
# define __VOLATILE
|
|
# endif
|
|
# ifdef __STL_WIN32THREADS
|
|
// The lock needs to be initialized by constructing an allocator
|
|
// objects of the right type. We do that here explicitly for alloc.
|
|
# define __NODE_ALLOCATOR_LOCK \
|
|
EnterCriticalSection(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_UNLOCK \
|
|
LeaveCriticalSection(&_S_node_allocator_lock)
|
|
# define __NODE_ALLOCATOR_THREADS true
|
|
# define __VOLATILE volatile // may not be needed
|
|
# endif /* WIN32THREADS */
|
|
# ifdef __STL_SGI_THREADS
|
|
// This should work without threads, with sproc threads, or with
|
|
// pthreads. It is suboptimal in all cases.
|
|
// It is unlikely to even compile on nonSGI machines.
|
|
|
|
extern "C" {
|
|
extern int __us_rsthread_malloc;
|
|
}
|
|
// The above is copied from malloc.h. Including <malloc.h>
|
|
// would be cleaner but fails with certain levels of standard
|
|
// conformance.
|
|
# define __NODE_ALLOCATOR_LOCK if (threads && __us_rsthread_malloc) \
|
|
{ _S_lock(&_S_node_allocator_lock); }
|
|
# define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
|
|
{ _S_unlock(&_S_node_allocator_lock); }
|
|
# define __NODE_ALLOCATOR_THREADS true
|
|
# define __VOLATILE volatile // Needed at -O3 on SGI
|
|
# endif
|
|
# ifdef _NOTHREADS
|
|
// Thread-unsafe
|
|
# define __NODE_ALLOCATOR_LOCK
|
|
# define __NODE_ALLOCATOR_UNLOCK
|
|
# define __NODE_ALLOCATOR_THREADS false
|
|
# define __VOLATILE
|
|
# endif
|
|
|
|
__STL_BEGIN_NAMESPACE
|
|
|
|
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
|
|
#pragma set woff 1174
|
|
#endif
|
|
|
|
// Malloc-based allocator. Typically slower than default alloc below.
|
|
// Typically thread-safe and more storage efficient.
|
|
#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
|
|
# ifdef __DECLARE_GLOBALS_HERE
|
|
void (* __malloc_alloc_oom_handler)() = 0;
|
|
// g++ 2.7.2 does not handle static template data members.
|
|
# else
|
|
extern void (* __malloc_alloc_oom_handler)();
|
|
# endif
|
|
#endif
|
|
|
|
template <int __inst>
|
|
class __malloc_alloc_template {
|
|
|
|
private:
|
|
|
|
static void* _S_oom_malloc(size_t);
|
|
static void* _S_oom_realloc(void*, size_t);
|
|
|
|
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
|
|
static void (* __malloc_alloc_oom_handler)();
|
|
#endif
|
|
|
|
public:
|
|
|
|
static void* allocate(size_t __n)
|
|
{
|
|
void* __result = malloc(__n);
|
|
if (0 == __result) __result = _S_oom_malloc(__n);
|
|
return __result;
|
|
}
|
|
|
|
static void deallocate(void* __p, size_t /* __n */)
|
|
{
|
|
free(__p);
|
|
}
|
|
|
|
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
|
|
{
|
|
void* __result = realloc(__p, __new_sz);
|
|
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
|
|
return __result;
|
|
}
|
|
|
|
static void (* __set_malloc_handler(void (*__f)()))()
|
|
{
|
|
void (* __old)() = __malloc_alloc_oom_handler;
|
|
__malloc_alloc_oom_handler = __f;
|
|
return(__old);
|
|
}
|
|
|
|
};
|
|
|
|
// malloc_alloc out-of-memory handling
|
|
|
|
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
|
|
template <int __inst>
|
|
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
|
|
#endif
|
|
|
|
template <int __inst>
|
|
void*
|
|
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
|
|
{
|
|
void (* __my_malloc_handler)();
|
|
void* __result;
|
|
|
|
for (;;) {
|
|
__my_malloc_handler = __malloc_alloc_oom_handler;
|
|
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
|
|
(*__my_malloc_handler)();
|
|
__result = malloc(__n);
|
|
if (__result) return(__result);
|
|
}
|
|
}
|
|
|
|
template <int __inst>
|
|
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
|
|
{
|
|
void (* __my_malloc_handler)();
|
|
void* __result;
|
|
|
|
for (;;) {
|
|
__my_malloc_handler = __malloc_alloc_oom_handler;
|
|
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
|
|
(*__my_malloc_handler)();
|
|
__result = realloc(__p, __n);
|
|
if (__result) return(__result);
|
|
}
|
|
}
|
|
|
|
typedef __malloc_alloc_template<0> malloc_alloc;
|
|
|
|
template<class _Tp, class _Alloc>
|
|
class simple_alloc {
|
|
|
|
public:
|
|
static _Tp* allocate(size_t __n)
|
|
{ return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
|
|
static _Tp* allocate(void)
|
|
{ return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
|
|
static void deallocate(_Tp* __p, size_t __n)
|
|
{ if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
|
|
static void deallocate(_Tp* __p)
|
|
{ _Alloc::deallocate(__p, sizeof (_Tp)); }
|
|
};
|
|
|
|
// Allocator adaptor to check size arguments for debugging.
|
|
// Reports errors using assert. Checking can be disabled with
|
|
// NDEBUG, but it's far better to just use the underlying allocator
|
|
// instead when no checking is desired.
|
|
// There is some evidence that this can confuse Purify.
|
|
template <class _Alloc>
|
|
class debug_alloc {
|
|
|
|
private:
|
|
|
|
enum {_S_extra = 8}; // Size of space used to store size. Note
|
|
// that this must be large enough to preserve
|
|
// alignment.
|
|
|
|
public:
|
|
|
|
static void* allocate(size_t __n)
|
|
{
|
|
char* __result = (char*)_Alloc::allocate(__n + _S_extra);
|
|
*(size_t*)__result = __n;
|
|
return __result + _S_extra;
|
|
}
|
|
|
|
static void deallocate(void* __p, size_t __n)
|
|
{
|
|
char* __real_p = (char*)__p - _S_extra;
|
|
assert(*(size_t*)__real_p == __n);
|
|
_Alloc::deallocate(__real_p, __n + _S_extra);
|
|
}
|
|
|
|
static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
|
|
{
|
|
char* __real_p = (char*)__p - _S_extra;
|
|
assert(*(size_t*)__real_p == __old_sz);
|
|
char* __result = (char*)
|
|
_Alloc::reallocate(__real_p, __old_sz + _S_extra, __new_sz + _S_extra);
|
|
*(size_t*)__result = __new_sz;
|
|
return __result + _S_extra;
|
|
}
|
|
|
|
};
|
|
|
|
|
|
# ifdef __USE_MALLOC
|
|
|
|
typedef malloc_alloc alloc;
|
|
typedef malloc_alloc single_client_alloc;
|
|
|
|
# else
|
|
|
|
|
|
// Default node allocator.
|
|
// With a reasonable compiler, this should be roughly as fast as the
|
|
// original STL class-specific allocators, but with less fragmentation.
|
|
// Default_alloc_template parameters are experimental and MAY
|
|
// DISAPPEAR in the future. Clients should just use alloc for now.
|
|
//
|
|
// Important implementation properties:
|
|
// 1. If the client request an object of size > _MAX_BYTES, the resulting
|
|
// object will be obtained directly from malloc.
|
|
// 2. In all other cases, we allocate an object of size exactly
|
|
// _S_round_up(requested_size). Thus the client has enough size
|
|
// information that we can return the object to the proper free list
|
|
// without permanently losing part of the object.
|
|
//
|
|
|
|
// The first template parameter specifies whether more than one thread
|
|
// may use this allocator. It is safe to allocate an object from
|
|
// one instance of a default_alloc and deallocate it with another
|
|
// one. This effectively transfers its ownership to the second one.
|
|
// This may have undesirable effects on reference locality.
|
|
// The second parameter is unreferenced and serves only to allow the
|
|
// creation of multiple default_alloc instances.
|
|
// Node that containers built on different allocator instances have
|
|
// different types, limiting the utility of this approach.
|
|
#ifdef __SUNPRO_CC
|
|
// breaks if we make these template class members:
|
|
enum {_ALIGN = 8};
|
|
enum {_MAX_BYTES = 128};
|
|
enum {_NFREELISTS = _MAX_BYTES/_ALIGN};
|
|
#endif
|
|
|
|
template <bool threads, int inst>
|
|
class __default_alloc_template {
|
|
|
|
private:
|
|
// Really we should use static const int x = N
|
|
// instead of enum { x = N }, but few compilers accept the former.
|
|
# ifndef __SUNPRO_CC
|
|
enum {_ALIGN = 8};
|
|
enum {_MAX_BYTES = 128};
|
|
enum {_NFREELISTS = _MAX_BYTES/_ALIGN};
|
|
# endif
|
|
static size_t
|
|
_S_round_up(size_t __bytes)
|
|
{ return (((__bytes) + _ALIGN-1) & ~(_ALIGN - 1)); }
|
|
|
|
__PRIVATE:
|
|
union _Obj {
|
|
union _Obj* _M_free_list_link;
|
|
char _M_client_data[1]; /* The client sees this. */
|
|
};
|
|
private:
|
|
# ifdef __SUNPRO_CC
|
|
static _Obj* __VOLATILE _S_free_list[];
|
|
// Specifying a size results in duplicate def for 4.1
|
|
# else
|
|
static _Obj* __VOLATILE _S_free_list[_NFREELISTS];
|
|
# endif
|
|
static size_t _S_freelist_index(size_t __bytes) {
|
|
return (((__bytes) + _ALIGN-1)/_ALIGN - 1);
|
|
}
|
|
|
|
// Returns an object of size __n, and optionally adds to size __n free list.
|
|
static void* _S_refill(size_t __n);
|
|
// Allocates a chunk for nobjs of size "size". nobjs may be reduced
|
|
// if it is inconvenient to allocate the requested number.
|
|
static char* _S_chunk_alloc(size_t __size, int& __nobjs);
|
|
|
|
// Chunk allocation state.
|
|
static char* _S_start_free;
|
|
static char* _S_end_free;
|
|
static size_t _S_heap_size;
|
|
|
|
# ifdef __STL_SGI_THREADS
|
|
static volatile unsigned long _S_node_allocator_lock;
|
|
static void _S_lock(volatile unsigned long*);
|
|
static inline void _S_unlock(volatile unsigned long*);
|
|
# endif
|
|
|
|
# ifdef __STL_PTHREADS
|
|
static pthread_mutex_t _S_node_allocator_lock;
|
|
# endif
|
|
|
|
# ifdef __STL_SOLTHREADS
|
|
static mutex_t _S_node_allocator_lock;
|
|
# endif
|
|
|
|
# ifdef __STL_WIN32THREADS
|
|
static CRITICAL_SECTION _S_node_allocator_lock;
|
|
static bool _S_node_allocator_lock_initialized;
|
|
|
|
public:
|
|
__default_alloc_template() {
|
|
// This assumes the first constructor is called before threads
|
|
// are started.
|
|
if (!_S_node_allocator_lock_initialized) {
|
|
InitializeCriticalSection(&_S_node_allocator_lock);
|
|
_S_node_allocator_lock_initialized = true;
|
|
}
|
|
}
|
|
private:
|
|
# endif
|
|
|
|
class _Lock {
|
|
public:
|
|
_Lock() { __NODE_ALLOCATOR_LOCK; }
|
|
~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
|
|
};
|
|
friend class _Lock;
|
|
|
|
public:
|
|
|
|
/* __n must be > 0 */
|
|
static void* allocate(size_t __n)
|
|
{
|
|
_Obj* __VOLATILE* __my_free_list;
|
|
_Obj* __RESTRICT __result;
|
|
|
|
if (__n > (size_t) _MAX_BYTES) {
|
|
return(malloc_alloc::allocate(__n));
|
|
}
|
|
__my_free_list = _S_free_list + _S_freelist_index(__n);
|
|
// Acquire the lock here with a constructor call.
|
|
// This ensures that it is released in exit or during stack
|
|
// unwinding.
|
|
# ifndef _NOTHREADS
|
|
/*REFERENCED*/
|
|
_Lock __lock_instance;
|
|
# endif
|
|
__result = *__my_free_list;
|
|
if (__result == 0) {
|
|
void* __r = _S_refill(_S_round_up(__n));
|
|
return __r;
|
|
}
|
|
*__my_free_list = __result -> _M_free_list_link;
|
|
return (__result);
|
|
};
|
|
|
|
/* __p may not be 0 */
|
|
static void deallocate(void* __p, size_t __n)
|
|
{
|
|
_Obj* __q = (_Obj*)__p;
|
|
_Obj* __VOLATILE* __my_free_list;
|
|
|
|
if (__n > (size_t) _MAX_BYTES) {
|
|
malloc_alloc::deallocate(__p, __n);
|
|
return;
|
|
}
|
|
__my_free_list = _S_free_list + _S_freelist_index(__n);
|
|
// acquire lock
|
|
# ifndef _NOTHREADS
|
|
/*REFERENCED*/
|
|
_Lock __lock_instance;
|
|
# endif /* _NOTHREADS */
|
|
__q -> _M_free_list_link = *__my_free_list;
|
|
*__my_free_list = __q;
|
|
// lock is released here
|
|
}
|
|
|
|
static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
|
|
|
|
} ;
|
|
|
|
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
|
|
typedef __default_alloc_template<false, 0> single_client_alloc;
|
|
|
|
|
|
|
|
/* We allocate memory in large chunks in order to avoid fragmenting */
|
|
/* the malloc heap too much. */
|
|
/* We assume that size is properly aligned. */
|
|
/* We hold the allocation lock. */
|
|
template <bool __threads, int __inst>
|
|
char*
|
|
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
|
|
int& __nobjs)
|
|
{
|
|
char* __result;
|
|
size_t __total_bytes = __size * __nobjs;
|
|
size_t __bytes_left = _S_end_free - _S_start_free;
|
|
|
|
if (__bytes_left >= __total_bytes) {
|
|
__result = _S_start_free;
|
|
_S_start_free += __total_bytes;
|
|
return(__result);
|
|
} else if (__bytes_left >= __size) {
|
|
__nobjs = (int)(__bytes_left/__size);
|
|
__total_bytes = __size * __nobjs;
|
|
__result = _S_start_free;
|
|
_S_start_free += __total_bytes;
|
|
return(__result);
|
|
} else {
|
|
size_t __bytes_to_get =
|
|
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
|
|
// Try to make use of the left-over piece.
|
|
if (__bytes_left > 0) {
|
|
_Obj* __VOLATILE* __my_free_list =
|
|
_S_free_list + _S_freelist_index(__bytes_left);
|
|
|
|
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
|
|
*__my_free_list = (_Obj*)_S_start_free;
|
|
}
|
|
_S_start_free = (char*)malloc(__bytes_to_get);
|
|
if (0 == _S_start_free) {
|
|
size_t __i;
|
|
_Obj* __VOLATILE* __my_free_list;
|
|
_Obj* __p;
|
|
// Try to make do with what we have. That can't
|
|
// hurt. We do not try smaller requests, since that tends
|
|
// to result in disaster on multi-process machines.
|
|
for (__i = __size; __i <= _MAX_BYTES; __i += _ALIGN) {
|
|
__my_free_list = _S_free_list + _S_freelist_index(__i);
|
|
__p = *__my_free_list;
|
|
if (0 != __p) {
|
|
*__my_free_list = __p -> _M_free_list_link;
|
|
_S_start_free = (char*)__p;
|
|
_S_end_free = _S_start_free + __i;
|
|
return(_S_chunk_alloc(__size, __nobjs));
|
|
// Any leftover piece will eventually make it to the
|
|
// right free list.
|
|
}
|
|
}
|
|
_S_end_free = 0; // In case of exception.
|
|
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
|
|
// This should either throw an
|
|
// exception or remedy the situation. Thus we assume it
|
|
// succeeded.
|
|
}
|
|
_S_heap_size += __bytes_to_get;
|
|
_S_end_free = _S_start_free + __bytes_to_get;
|
|
return(_S_chunk_alloc(__size, __nobjs));
|
|
}
|
|
}
|
|
|
|
|
|
/* Returns an object of size __n, and optionally adds to size __n free list.*/
|
|
/* We assume that __n is properly aligned. */
|
|
/* We hold the allocation lock. */
|
|
template <bool __threads, int __inst>
|
|
void*
|
|
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
|
|
{
|
|
int __nobjs = 20;
|
|
char* __chunk = _S_chunk_alloc(__n, __nobjs);
|
|
_Obj* __VOLATILE* __my_free_list;
|
|
_Obj* __result;
|
|
_Obj* __current_obj;
|
|
_Obj* __next_obj;
|
|
int __i;
|
|
|
|
if (1 == __nobjs) return(__chunk);
|
|
__my_free_list = _S_free_list + _S_freelist_index(__n);
|
|
|
|
/* Build free list in chunk */
|
|
__result = (_Obj*)__chunk;
|
|
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
|
|
for (__i = 1; ; __i++) {
|
|
__current_obj = __next_obj;
|
|
__next_obj = (_Obj*)((char*)__next_obj + __n);
|
|
if (__nobjs - 1 == __i) {
|
|
__current_obj -> _M_free_list_link = 0;
|
|
break;
|
|
} else {
|
|
__current_obj -> _M_free_list_link = __next_obj;
|
|
}
|
|
}
|
|
return(__result);
|
|
}
|
|
|
|
template <bool threads, int inst>
|
|
void*
|
|
__default_alloc_template<threads, inst>::reallocate(void* __p,
|
|
size_t __old_sz,
|
|
size_t __new_sz)
|
|
{
|
|
void* __result;
|
|
size_t __copy_sz;
|
|
|
|
if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
|
|
return(realloc(__p, __new_sz));
|
|
}
|
|
if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
|
|
__result = allocate(__new_sz);
|
|
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
|
|
memcpy(__result, __p, __copy_sz);
|
|
deallocate(__p, __old_sz);
|
|
return(__result);
|
|
}
|
|
|
|
#ifdef __STL_PTHREADS
|
|
template <bool __threads, int __inst>
|
|
pthread_mutex_t
|
|
__default_alloc_template<__threads, __inst>::_S_node_allocator_lock
|
|
= PTHREAD_MUTEX_INITIALIZER;
|
|
#endif
|
|
|
|
#ifdef __STL_SOLTHREADS
|
|
template <bool __threads, int __inst>
|
|
mutex_t
|
|
__default_alloc_template<__threads, __inst>::_S_node_allocator_lock
|
|
= DEFAULTMUTEX;
|
|
#endif
|
|
|
|
#ifdef __STL_WIN32THREADS
|
|
template <bool __threads, int __inst>
|
|
CRITICAL_SECTION
|
|
__default_alloc_template<__threads, __inst>::
|
|
_S_node_allocator_lock;
|
|
|
|
template <bool __threads, int __inst>
|
|
bool
|
|
__default_alloc_template<__threads, __inst>::
|
|
_S_node_allocator_lock_initialized
|
|
= false;
|
|
#endif
|
|
|
|
#ifdef __STL_SGI_THREADS
|
|
__STL_END_NAMESPACE
|
|
#include <mutex.h>
|
|
#include <time.h> /* XXX should use <ctime> */
|
|
__STL_BEGIN_NAMESPACE
|
|
// Somewhat generic lock implementations. We need only test-and-set
|
|
// and some way to sleep. These should work with both SGI pthreads
|
|
// and sproc threads. They may be useful on other systems.
|
|
template <bool __threads, int __inst>
|
|
volatile unsigned long
|
|
__default_alloc_template<__threads, __inst>::_S_node_allocator_lock = 0;
|
|
|
|
#if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) || defined(__GNUC__)
|
|
# define __test_and_set(l,v) test_and_set(l,v)
|
|
#endif
|
|
|
|
template <bool __threads, int __inst>
|
|
void
|
|
__default_alloc_template<__threads, __inst>::
|
|
_S_lock(volatile unsigned long* __lock)
|
|
{
|
|
const unsigned __low_spin_max = 30; // spins if we suspect uniprocessor
|
|
const unsigned __high_spin_max = 1000; // spins for multiprocessor
|
|
static unsigned __spin_max = __low_spin_max;
|
|
unsigned __my_spin_max;
|
|
static unsigned __last_spins = 0;
|
|
unsigned __my_last_spins;
|
|
unsigned __junk;
|
|
# define __ALLOC_PAUSE \
|
|
__junk *= __junk; __junk *= __junk; __junk *= __junk; __junk *= __junk
|
|
int __i;
|
|
|
|
if (!__test_and_set((unsigned long*)__lock, 1)) {
|
|
return;
|
|
}
|
|
__my_spin_max = __spin_max;
|
|
__my_last_spins = __last_spins;
|
|
for (__i = 0; __i < __my_spin_max; __i++) {
|
|
if (__i < __my_last_spins/2 || *__lock) {
|
|
__ALLOC_PAUSE;
|
|
continue;
|
|
}
|
|
if (!__test_and_set((unsigned long*)__lock, 1)) {
|
|
// got it!
|
|
// Spinning worked. Thus we're probably not being scheduled
|
|
// against the other process with which we were contending.
|
|
// Thus it makes sense to spin longer the next time.
|
|
__last_spins = __i;
|
|
__spin_max = __high_spin_max;
|
|
return;
|
|
}
|
|
}
|
|
// We are probably being scheduled against the other process. Sleep.
|
|
__spin_max = __low_spin_max;
|
|
for (__i = 0 ;; ++__i) {
|
|
struct timespec __ts;
|
|
int __log_nsec = __i + 6;
|
|
|
|
if (!__test_and_set((unsigned long *)__lock, 1)) {
|
|
return;
|
|
}
|
|
if (__log_nsec > 27) __log_nsec = 27;
|
|
/* Max sleep is 2**27nsec ~ 60msec */
|
|
__ts.tv_sec = 0;
|
|
__ts.tv_nsec = 1 << __log_nsec;
|
|
nanosleep(&__ts, 0);
|
|
}
|
|
}
|
|
|
|
template <bool __threads, int __inst>
|
|
inline void
|
|
__default_alloc_template<__threads, __inst>::_S_unlock(
|
|
volatile unsigned long* __lock)
|
|
{
|
|
# if defined(__GNUC__) && __mips >= 3
|
|
asm("sync");
|
|
*__lock = 0;
|
|
# elif __mips >= 3 && (defined (_ABIN32) || defined(_ABI64))
|
|
__lock_release(__lock);
|
|
# else
|
|
*__lock = 0;
|
|
// This is not sufficient on many multiprocessors, since
|
|
// writes to protected variables and the lock may be reordered.
|
|
# endif
|
|
}
|
|
#endif
|
|
|
|
template <bool __threads, int __inst>
|
|
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
|
|
|
|
template <bool __threads, int __inst>
|
|
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
|
|
|
|
template <bool __threads, int __inst>
|
|
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;
|
|
|
|
template <bool __threads, int __inst>
|
|
__default_alloc_template<__threads, __inst>::_Obj* __VOLATILE
|
|
__default_alloc_template<__threads, __inst> ::_S_free_list[
|
|
_NFREELISTS
|
|
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
|
|
// The 16 zeros are necessary to make version 4.1 of the SunPro
|
|
// compiler happy. Otherwise it appears to allocate too little
|
|
// space for the array.
|
|
|
|
# ifdef __STL_WIN32THREADS
|
|
// Create one to get critical section initialized.
|
|
// We do this onece per file, but only the first constructor
|
|
// does anything.
|
|
static alloc __node_allocator_dummy_instance;
|
|
# endif
|
|
|
|
#endif /* ! __USE_MALLOC */
|
|
|
|
// This implements allocators as specified in the C++ standard.
|
|
//
|
|
// Note that standard-conforming allocators use many language features
|
|
// that are not yet widely implemented. In particular, they rely on
|
|
// member templates, partial specialization, partial ordering of function
|
|
// templates, the typename keyword, and the use of the template keyword
|
|
// to refer to a template member of a dependent type.
|
|
|
|
#ifdef __STL_USE_STD_ALLOCATORS
|
|
|
|
template <class _Tp>
|
|
class allocator {
|
|
typedef alloc _Alloc; // The underlying allocator.
|
|
public:
|
|
typedef size_t size_type;
|
|
typedef ptrdiff_t difference_type;
|
|
typedef _Tp* pointer;
|
|
typedef const _Tp* const_pointer;
|
|
typedef _Tp& reference;
|
|
typedef const _Tp& const_reference;
|
|
typedef _Tp value_type;
|
|
|
|
template <class _Tp1> struct rebind {
|
|
typedef allocator<_Tp1> other;
|
|
};
|
|
|
|
allocator() __STL_NOTHROW {}
|
|
allocator(const allocator&) __STL_NOTHROW {}
|
|
template <class _Tp1> allocator(const allocator<_Tp1>&) __STL_NOTHROW {}
|
|
~allocator() __STL_NOTHROW {}
|
|
|
|
pointer address(reference __x) const { return &__x; }
|
|
const_pointer address(const_reference __x) const { return &__x; }
|
|
|
|
// __n is permitted to be 0. The C++ standard says nothing about what
|
|
// the return value is when __n == 0.
|
|
_Tp* allocate(size_type __n, const void* = 0) {
|
|
return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)))
|
|
: 0;
|
|
}
|
|
|
|
// __p is not permitted to be a null pointer.
|
|
void deallocate(pointer __p, size_type __n)
|
|
{ _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
|
|
|
|
size_type max_size() const __STL_NOTHROW
|
|
{ return size_t(-1) / sizeof(_Tp); }
|
|
|
|
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
|
|
void destroy(pointer __p) { __p->~_Tp(); }
|
|
};
|
|
|
|
template<>
|
|
class allocator<void> {
|
|
typedef size_t size_type;
|
|
typedef ptrdiff_t difference_type;
|
|
typedef void* pointer;
|
|
typedef const void* const_pointer;
|
|
typedef void value_type;
|
|
|
|
template <class _Tp1> struct rebind {
|
|
typedef allocator<_Tp1> other;
|
|
};
|
|
};
|
|
|
|
|
|
template <class _T1, class _T2>
|
|
inline bool operator==(const allocator<_T1>&, const allocator<_T2>&)
|
|
{
|
|
return true;
|
|
}
|
|
|
|
template <class _T1, class _T2>
|
|
inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&)
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// Allocator adaptor to turn an SGI-style allocator (e.g. alloc, malloc_alloc)
|
|
// into a standard-conforming allocator. Note that this adaptor does
|
|
// *not* assume that all objects of the underlying alloc class are
|
|
// identical, nor does it assume that all of the underlying alloc's
|
|
// member functions are static member functions. Note, also, that
|
|
// __allocator<_Tp, alloc> is essentially the same thing as allocator<_Tp>.
|
|
|
|
template <class _Tp, class _Alloc>
|
|
struct __allocator {
|
|
_Alloc __underlying_alloc;
|
|
|
|
typedef size_t size_type;
|
|
typedef ptrdiff_t difference_type;
|
|
typedef _Tp* pointer;
|
|
typedef const _Tp* const_pointer;
|
|
typedef _Tp& reference;
|
|
typedef const _Tp& const_reference;
|
|
typedef _Tp value_type;
|
|
|
|
template <class _Tp1> struct rebind {
|
|
typedef __allocator<_Tp1, _Alloc> other;
|
|
};
|
|
|
|
__allocator() __STL_NOTHROW {}
|
|
__allocator(const __allocator& __a) __STL_NOTHROW
|
|
: __underlying_alloc(__a.__underlying_alloc) {}
|
|
template <class _Tp1>
|
|
__allocator(const __allocator<_Tp1, _Alloc>& __a) __STL_NOTHROW
|
|
: __underlying_alloc(__a.__underlying_alloc) {}
|
|
~__allocator() __STL_NOTHROW {}
|
|
|
|
pointer address(reference __x) const { return &__x; }
|
|
const_pointer address(const_reference __x) const { return &__x; }
|
|
|
|
// __n is permitted to be 0.
|
|
_Tp* allocate(size_type __n, const void* = 0) {
|
|
return __n != 0
|
|
? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp)))
|
|
: 0;
|
|
}
|
|
|
|
// __p is not permitted to be a null pointer.
|
|
void deallocate(pointer __p, size_type __n)
|
|
{ __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }
|
|
|
|
size_type max_size() const __STL_NOTHROW
|
|
{ return size_t(-1) / sizeof(_Tp); }
|
|
|
|
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
|
|
void destroy(pointer __p) { __p->~_Tp(); }
|
|
};
|
|
|
|
template <class _Alloc>
|
|
class __allocator<void, _Alloc> {
|
|
typedef size_t size_type;
|
|
typedef ptrdiff_t difference_type;
|
|
typedef void* pointer;
|
|
typedef const void* const_pointer;
|
|
typedef void value_type;
|
|
|
|
template <class _Tp1> struct rebind {
|
|
typedef __allocator<_Tp1, _Alloc> other;
|
|
};
|
|
};
|
|
|
|
template <class _Tp, class _Alloc>
|
|
inline bool operator==(const __allocator<_Tp, _Alloc>& __a1,
|
|
const __allocator<_Tp, _Alloc>& __a2)
|
|
{
|
|
return __a1.__underlying_alloc == __a2.__underlying_alloc;
|
|
}
|
|
|
|
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
|
|
template <class _Tp, class _Alloc>
|
|
inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1,
|
|
const __allocator<_Tp, _Alloc>& __a2)
|
|
{
|
|
return __a1.__underlying_alloc != __a2.__underlying_alloc;
|
|
}
|
|
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
|
|
|
|
// Comparison operators for all of the predifined SGI-style allocators.
|
|
// This ensures that __allocator<malloc_alloc> (for example) will
|
|
// work correctly.
|
|
|
|
template <int inst>
|
|
inline bool operator==(const __malloc_alloc_template<inst>&,
|
|
const __malloc_alloc_template<inst>&)
|
|
{
|
|
return true;
|
|
}
|
|
|
|
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
|
|
template <int __inst>
|
|
inline bool operator!=(const __malloc_alloc_template<__inst>&,
|
|
const __malloc_alloc_template<__inst>&)
|
|
{
|
|
return false;
|
|
}
|
|
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
|
|
|
|
#ifndef __USE_MALLOC
|
|
template <bool __threads, int __inst>
|
|
inline bool operator==(const __default_alloc_template<__threads, __inst>&,
|
|
const __default_alloc_template<__threads, __inst>&)
|
|
{
|
|
return true;
|
|
}
|
|
|
|
# ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
|
|
template <bool __threads, int __inst>
|
|
inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
|
|
const __default_alloc_template<__threads, __inst>&)
|
|
{
|
|
return false;
|
|
}
|
|
# endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
|
|
#endif
|
|
|
|
template <class _Alloc>
|
|
inline bool operator==(const debug_alloc<_Alloc>&,
|
|
const debug_alloc<_Alloc>&) {
|
|
return true;
|
|
}
|
|
|
|
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
|
|
template <class _Alloc>
|
|
inline bool operator!=(const debug_alloc<_Alloc>&,
|
|
const debug_alloc<_Alloc>&) {
|
|
return false;
|
|
}
|
|
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
|
|
|
|
// Another allocator adaptor: _Alloc_traits. This serves two
|
|
// purposes. First, make it possible to write containers that can use
|
|
// either SGI-style allocators or standard-conforming allocator.
|
|
// Second, provide a mechanism so that containers can query whether or
|
|
// not the allocator has distinct instances. If not, the container
|
|
// can avoid wasting a word of memory to store an empty object.
|
|
|
|
// This adaptor uses partial specialization. The general case of
|
|
// _Alloc_traits<_Tp, _Alloc> assumes that _Alloc is a
|
|
// standard-conforming allocator, possibly with non-equal instances
|
|
// and non-static members. (It still behaves correctly even if _Alloc
|
|
// has static member and if all instances are equal. Refinements
|
|
// affect performance, not correctness.)
|
|
|
|
// There are always two members: allocator_type, which is a standard-
|
|
// conforming allocator type for allocating objects of type _Tp, and
|
|
// _S_instanceless, a static const member of type bool. If
|
|
// _S_instanceless is true, this means that there is no difference
|
|
// between any two instances of type allocator_type. Furthermore, if
|
|
// _S_instanceless is true, then _Alloc_traits has one additional
|
|
// member: _Alloc_type. This type encapsulates allocation and
|
|
// deallocation of objects of type _Tp through a static interface; it
|
|
// has two member functions, whose signatures are
|
|
// static _Tp* allocate(size_t)
|
|
// static void deallocate(_Tp*, size_t)
|
|
|
|
// The fully general version.
|
|
|
|
template <class _Tp, class _Allocator>
|
|
struct _Alloc_traits
|
|
{
|
|
static const bool _S_instanceless = false;
|
|
typedef typename _Allocator::__STL_TEMPLATE rebind<_Tp>::other
|
|
allocator_type;
|
|
};
|
|
|
|
template <class _Tp, class _Allocator>
|
|
const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;
|
|
|
|
// The version for the default allocator.
|
|
|
|
template <class _Tp, class _Tp1>
|
|
struct _Alloc_traits<_Tp, allocator<_Tp1> >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, alloc> _Alloc_type;
|
|
typedef allocator<_Tp> allocator_type;
|
|
};
|
|
|
|
// Versions for the predefined SGI-style allocators.
|
|
|
|
template <class _Tp, int __inst>
|
|
struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
|
|
typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
|
|
};
|
|
|
|
#ifndef __USE_MALLOC
|
|
template <class _Tp, bool __threads, int __inst>
|
|
struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, __default_alloc_template<__threads, __inst> >
|
|
_Alloc_type;
|
|
typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> >
|
|
allocator_type;
|
|
};
|
|
#endif
|
|
|
|
template <class _Tp, class _Alloc>
|
|
struct _Alloc_traits<_Tp, debug_alloc<_Alloc> >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
|
|
typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
|
|
};
|
|
|
|
// Versions for the __allocator adaptor used with the predefined
|
|
// SGI-style allocators.
|
|
|
|
template <class _Tp, class _Tp1, int __inst>
|
|
struct _Alloc_traits<_Tp,
|
|
__allocator<_Tp1, __malloc_alloc_template<__inst> > >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
|
|
typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
|
|
};
|
|
|
|
#ifndef __USE_MALLOC
|
|
template <class _Tp, class _Tp1, bool __thr, int __inst>
|
|
struct _Alloc_traits<_Tp,
|
|
__allocator<_Tp1,
|
|
__default_alloc_template<__thr, __inst> > >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, __default_alloc_template<__thr,__inst> >
|
|
_Alloc_type;
|
|
typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> >
|
|
allocator_type;
|
|
};
|
|
#endif
|
|
|
|
template <class _Tp, class _Tp1, class _Alloc>
|
|
struct _Alloc_traits<_Tp, __allocator<_Tp1, debug_alloc<_Alloc> > >
|
|
{
|
|
static const bool _S_instanceless = true;
|
|
typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
|
|
typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
|
|
};
|
|
|
|
|
|
#endif /* __STL_USE_STD_ALLOCATORS */
|
|
|
|
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
|
|
#pragma reset woff 1174
|
|
#endif
|
|
|
|
__STL_END_NAMESPACE
|
|
|
|
#undef __PRIVATE
|
|
|
|
#endif /* __SGI_STL_INTERNAL_ALLOC_H */
|
|
|
|
// Local Variables:
|
|
// mode:C++
|
|
// End:
|