stl_alloc.h
2024-09-09 16:34:03
/*
* 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 //这个实现一些标准结点的内存分配管理器。这些配置器与C++标准草稿所描述的或与原始的STL所描述的都不相同。
//它们并没有封装不同的指针类型，实际上，我们假设仅存在一种指针类型。
//一些基本的函式意在分配那些不大于原始STL配置器所能分配的最大空间的个别对象独立对象。 #if 0
# include <new>
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include <iostream.h>
# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit()
#endif #ifndef __ALLOC
# define __ALLOC alloc
#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(_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(&__node_allocator_lock)
# define __NODE_ALLOCATOR_UNLOCK \
if (threads) pthread_mutex_unlock(&__node_allocator_lock)
# define __NODE_ALLOCATOR_THREADS true
# define __VOLATILE volatile // Needed at -O3 on SGI
# 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(&__node_allocator_lock)
# define __NODE_ALLOCATOR_UNLOCK \
LeaveCriticalSection(&__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) \
{ __lock(&__node_allocator_lock); }
# define __NODE_ALLOCATOR_UNLOCK if (threads && __us_rsthread_malloc) \
{ __unlock(&__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的分配器通常比稍後介紹的 default alloc 速度慢，
// 一般而言是线程安全的，並且對於空間的運用比較高效。 #ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
# ifdef __DECLARE_GLOBALS_HERE
void (* __malloc_alloc_oom_handler)() = ;
// g++ 2.7.2 does not handle static template data members.
# else
extern void (* __malloc_alloc_oom_handler)();
# endif
#endif // 以下是第一级配置器。注意，没有[template型别参数]。因为inst完全没有派上用场。
template <int inst>
class __malloc_alloc_template { private:
// 内存分配失败处理函数，利用循环
static void *oom_malloc(size_t); static void *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);// 第一级配置器直接使用malloc系统调用
if ( == result) result = oom_malloc(n);//内存分配失败，调用oom_malloc处理函数
return result;
} static void deallocate(void *p, size_t /* n */)
{
free(p);//第一级配置器直接使用free系统调用
} static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result = realloc(p, new_sz);//第一级配置器直接使用realloc系统调用
if ( == result) result = oom_realloc(p, new_sz);//内存分配失败，调用oom_realloc处理函数
return result;
} // 以下類似 C++ 的 set_new_handler().
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)() = ;
#endif // 内存分配失败处理函数定义
// 原理：不断尝试释放、配置、再释放、再配置…
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
void (* my_malloc_handler)();
void *result; for (;;) {
my_malloc_handler = __malloc_alloc_oom_handler;
if ( == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)(); //调用函数指针指向的处理函数，企图释放记忆内存
result = malloc(n); //第一级配置器直接使用malloc系统调用
if (result) return(result);//直到分配内存成功
}
} template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
void (* my_malloc_handler)();
void *result; for (;;) {
my_malloc_handler = __malloc_alloc_oom_handler;
if ( == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)();
result = realloc(p, n); //第一级配置器直接使用realloc系统调用
if (result) return(result);//直到分配内存成功
}
} typedef __malloc_alloc_template<> malloc_alloc; //简单的内存配置器，调用Alloc类型的方法进行内存申请与释放
template<class T, class Alloc>
class simple_alloc { public:
static T *allocate(size_t n)
{ return == n? : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
static void deallocate(T *p, size_t n)
{ if ( != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
}; // 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 {extra = }; // 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 + extra);
*(size_t *)result = n;
return result + extra;
} static void deallocate(void *p, size_t n)
{
char * real_p = (char *)p - extra;
assert(*(size_t *)real_p == n);
Alloc::deallocate(real_p, n + extra);
} static void * reallocate(void *p, size_t old_sz, size_t new_sz)
{
char * real_p = (char *)p - extra;
assert(*(size_t *)real_p == old_sz);
char * result = (char *)
Alloc::reallocate(real_p, old_sz + extra, new_sz + extra);
*(size_t *)result = new_sz;
return result + 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
// 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 = };
enum {__MAX_BYTES = };
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 = };
enum {__MAX_BYTES = };
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};
# endif
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-) & ~(__ALIGN - ));
}
__PRIVATE:
union obj {
union obj * free_list_link;
char client_data[]; /* The client sees this. */
};
private:
# ifdef __SUNPRO_CC
static obj * __VOLATILE free_list[];
// Specifying a size results in duplicate def for 4.1
# else
static obj * __VOLATILE free_list[__NFREELISTS];
# endif
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-)/__ALIGN - );
} // Returns an object of size n, and optionally adds to size n free list.
static void *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 *chunk_alloc(size_t size, int &nobjs); // Chunk allocation state.
static char *start_free;
static char *end_free;
static size_t heap_size; # ifdef __STL_SGI_THREADS
static volatile unsigned long __node_allocator_lock;
static void __lock(volatile unsigned long *);
static inline void __unlock(volatile unsigned long *);
# endif # ifdef __STL_PTHREADS
static pthread_mutex_t __node_allocator_lock;
# endif # ifdef __STL_WIN32THREADS
static CRITICAL_SECTION __node_allocator_lock;
static bool __node_allocator_lock_initialized; public:
__default_alloc_template() {
// This assumes the first constructor is called before threads
// are started.
if (!__node_allocator_lock_initialized) {
InitializeCriticalSection(&__node_allocator_lock);
__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 = free_list + 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 == ) {
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result -> 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 = free_list + FREELIST_INDEX(n);
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
lock lock_instance;
# endif /* _NOTHREADS */
q -> 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, > alloc;
typedef __default_alloc_template<false, > 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>::chunk_alloc(size_t size, int& nobjs)
{
char * result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; if (bytes_left >= total_bytes) {
result = start_free;
start_free += total_bytes;
return(result);
} else if (bytes_left >= size) {
nobjs = bytes_left/size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
} else {
size_t bytes_to_get = * total_bytes + ROUND_UP(heap_size >> );
// Try to make use of the left-over piece.
if (bytes_left > ) {
obj * __VOLATILE * my_free_list =
free_list + FREELIST_INDEX(bytes_left); ((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get);
if ( == start_free) {
int i;
obj * __VOLATILE * my_free_list, *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 = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if ( != p) {
*my_free_list = p -> free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return(chunk_alloc(size, nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
end_free = ; // In case of exception.
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return(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>::refill(size_t n)
{
int nobjs = ;
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i; if ( == nobjs) return(chunk);
my_free_list = free_list + FREELIST_INDEX(n); /* Build free list in chunk */
result = (obj *)chunk;
*my_free_list = next_obj = (obj *)(chunk + n);
for (i = ; ; i++) {
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - == i) {
current_obj -> free_list_link = ;
break;
} else {
current_obj -> 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 (ROUND_UP(old_sz) == 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>::__node_allocator_lock
= PTHREAD_MUTEX_INITIALIZER;
#endif #ifdef __STL_WIN32THREADS
template <bool threads, int inst> CRITICAL_SECTION
__default_alloc_template<threads, inst>::__node_allocator_lock; template <bool threads, int inst> bool
__default_alloc_template<threads, inst>::__node_allocator_lock_initialized
= false;
#endif #ifdef __STL_SGI_THREADS
__STL_END_NAMESPACE
#include <mutex.h>
#include <time.h>
__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>::__node_allocator_lock = ; #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>::__lock(volatile unsigned long *lock)
{
const unsigned low_spin_max = ; // spin cycles if we suspect uniprocessor
const unsigned high_spin_max = ; // spin cycles for multiprocessor
static unsigned spin_max = low_spin_max;
unsigned my_spin_max;
static unsigned last_spins = ;
unsigned my_last_spins;
static struct timespec ts = {, };
unsigned junk;
# define __ALLOC_PAUSE junk *= junk; junk *= junk; junk *= junk; junk *= junk
int i; if (!__test_and_set((unsigned long *)lock, )) {
return;
}
my_spin_max = spin_max;
my_last_spins = last_spins;
for (i = ; i < my_spin_max; i++) {
if (i < my_last_spins/ || *lock) {
__ALLOC_PAUSE;
continue;
}
if (!__test_and_set((unsigned long *)lock, )) {
// 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 (;;) {
if (!__test_and_set((unsigned long *)lock, )) {
return;
}
nanosleep(&ts, );
}
} template <bool threads, int inst>
inline void
__default_alloc_template<threads, inst>::__unlock(volatile unsigned long *lock)
{
# if defined(__GNUC__) && __mips >=
asm("sync");
*lock = ;
# elif __mips >= && (defined (_ABIN32) || defined(_ABI64))
__lock_release(lock);
# else
*lock = ;
// 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>::start_free = ; template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = ; template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = ; template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj * __VOLATILE
__default_alloc_template<threads, inst> ::free_list[
# ifdef __SUNPRO_CC
__NFREELISTS
# else
__default_alloc_template<threads, inst>::__NFREELISTS
# endif
] = {, , , , , , , , , , , , , , , , };
// 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 */ #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:
最新文章
- centos 6x系统下源码安装mysql操作记录
- Linux学习之路—Linux文件权限
- Sqlserver 如何获取每组中的第一条记录
- [Linux] LD_LIBRARY_PATH
- Linux常用命令_（安装包管理）
- 浅谈KL散度
- Gartner2014年魔力象限(商业智能和分析平台)
- c++ deque 双端队列
- hdu 5497 Inversion 树状数组 逆序对，单点修改
- 转战WebApp: 最适合Android开发者的WebApp框架
- 解决从源码编译ncurses6.0编译lib_gen.c报错的问题
- 关于Set Nocount ON的性能 |c#调用存储过程的返回值总是-1
- OpenStack dashboard界面操作 实现登陆虚拟机并通信
- 面试题：使用LinkedList来模拟一个堆栈或者队列数据结构
- Linux文件权限命令及配置
- 架构师技能图谱 V1.2
- 01、Spar内核架构原理
- 函数和常用模块【day05】：装饰器高潮（三）
- 【转】在Win7的IIS上搭建FTP服务及用户授权
- 【SQL】from a,b。表a 和b之间是什么关系？