注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

SGI STL源码文件,stl_alloc.h[注释]  

2011-02-17 01:50:38|  分类: c++学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

 

/ *

* 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.

// __PRIVATE 是为sun编译器对private限制过多而设

#else

#    define PRIVATE private

 

#endif

 

#ifdef STL_STATIC_TEMPLATE_MEMBER_BUG

#    define USE_MALLOC

//一个小bug就使得没有使用sgi stl的两级内存分配机制,囧

#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.

// 他们认为allocator不应该与存储内容的类型有关,是这样的,公共仓库看门的不应该因为

// 使用仓库的人不同而换人

 

#ifndef THROW_BAD_ALLOC

#    if defined( STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)

#    include <stdio.h>

#    include <stdlib.h>

#    define THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1

)

#    else / * Standard conforming out- of- memory handling */

#    include <new>

#    define THROW_BAD_ALLOC throw std::bad_alloc()

#    endif

#endif

 

#include <stddef.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

#ifndef RESTRICT

#    define RESTRICT

#endif

 

 

 

 

#ifdef STL_THREADS

# include <stl_threads.h>

# define NODE_ALLOCATOR_THREADS true

# ifdef STL_SGI_THREADS

/ / We test whether threads are in use before locking.

/ / Perhaps this should be moved into stl_threads.h, but that

/ / probably makes it harder to avoid the procedure call when

/ / it isn't needed.

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_node_allocator_lock._M_acquire_lock(); }

#    define NODE_ALLOCATOR_UNLOCK if (threads && us_rsthread_malloc)

\

{ _S_node_allocator_lock._M_release_lock(); }

# else / * !     STL_SGI_THREADS */

#    define NODE_ALLOCATOR_LOCK \

{ if (threads) _S_node_allocator_lock._M_acquire_lock(); }

#    define NODE_ALLOCATOR_UNLOCK \

{ if (threads) _S_node_allocator_lock._M_release_lock(); }

# endif

#else

/ /    Thread- unsafe

#    define NODE_ALLOCATOR_LOCK

#    define NODE_ALLOCATOR_UNLOCK

#    define NODE_ALLOCATOR_THREADS false

#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

//如果存在类模版静态常量bug,就使用全局常量__malloc_alloc_oom_handler

# 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 {

 

 

//__malloc_alloc_template为第一级内存分配机制,__inst的意思是instances,为多线程使用

 

//此一级内存分配工具使用C语言库的malloc calloc realloc free内存管理函数

 

//关于C库内存管理函数参见http://www.cplusplus.com/reference/clibrary/cstdlib/malloc/

private:

 

//内部使用的静态工具函数分别用于allocate与reallocate中

//__S_ 代表静态

 

 

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);

}

 

//此reallocate不是C++标准规定的函数

static void* reallocate(void*

new_sz)

{

 

__p, size_t / * old_sz */ , size_t

 

void* result = realloc( p, new_sz);

if (0 == result) result = _S_oom_realloc( p, new_sz);

return result;

}

    //最不想看到这种声明,此处意思是返回函数指针,接收函数指针为参数

    //以下是等效声明

    // typedef void (*return_void_param_void_func_ptr)();

    // static return_void_param_void_func_ptr __set_malloc_handler(\

    // return_void_param_void_func_ptr __f);

    // 接受新的handler,返回旧的handler,注意这个不是c++标准的要求函数

static void (* set_malloc_handler(void (* f)()))()

{

void (* old)() = malloc_alloc_oom_handler;

malloc_alloc_oom_handler = __f;

return( old);

}

 

} ? end malloc_alloc_template ? ;

 

/ / 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 (;;) {

        //此处设定内存不足处理函数指针,如果指针为空,则直接抛出异常

        //否则调用内存不足处理函数,此函数可能会做一些释放不用内足或是

        //提示用户释放内存之类的工作,之后再重新调用malloc申请内存,这说明

        //就算内存申请失败,还有另一次机会

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);

}

}

//这里定义第一级分配机制为malloc_alloc

//意为调用C库的malloc内存管理函数族

typedef malloc_alloc_template<0> malloc_alloc;

//无论第一级内存分配机制还是第二级内存分配机制,它们都不是标准的,SGI STL

//为此设计了一个simple_alloc接口,做为一个adaptor使一二级内存分配机制能

//符合C++标准

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:

    //多分配_S_extra个字节,把内存的长度保存在这个空间内

static void* allocate(size_t

{

 

 

 

__n)

 

char*

__result = (char*)_Alloc::allocate(__n + (int) _S_extra);

 

*(size_t*) result = n; //强制转换以保存内存大小

return result + (int) _S_extra;

}

 

 

static void deallocate(void*

{

 

__p, size_t

 

__n)

 

char* real_p = (char*) p - (int) _S_extra; //找到长度所在地址

assert(*(size_t*) real_p == __n); //长度检查

_Alloc::deallocate( real_p, __n + (int) _S_extra);

}

 

 

static void* reallocate(void*

{

 

__p, size_t

 

__old_sz, size_t

 

__new_sz)

 

char* real_p = (char*) p - (int) _S_extra;

assert(*(size_t*) real_p == __old_sz);

//长度检查无误后调用_Alloc::reallocate

char* result = (char*)

_Alloc::reallocate( real_p, __old_sz + (int) _S_extra,

__new_sz + (int) _S_extra);

*(size_t*) result = new_sz;

return result + (int) _S_extra;

}

 

} ? end debug_alloc ? ;

 

 

# 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.

// 上面是是对malloc_alloc的一个总结,请仔细阅读这一部分,我在最初实现一个

// 简单的sm_allocator,它使用了标准C++的::operator new和::operator delete管理

// 内存,但这里为什么不用这种机制而使用C标准库的malloc内存管理函数族呢?一个

// 原因如上面所述,C库内内管理函数族不是高度抽象的,与系统相关,这意味着它在

// 多种平台下可以高效工作,我说的高效不是速度,::operator new 致少和malloc一样快,

// 而是内存空间的使用,malloc函数

// 族与系统内核相联系,不同平台使用机制不同。比如Linux内核中内存的管理就是使用

// 扩展后的RBtree区间树管理内存,这种机制的内存分配并不是没有overhead的,比如你

// 调用malloc(n),系统分配的内存要比n大一些,多出的一些用于对此部分内存的管理,不

// free调用时它如何知道要释放多少内存呢。但是不同的系统这种类似的工作机制差异很大

// C++标准的::operator new不能利用这种机制,那么它管理内存就只能使用自己的管理

// 方法,这就是一个overhead上再次产生了overhead,于内存高效利用不利,SGI STL从最高效的

// 角度出发,选择使用C库内存管理函数族。

/ /

/ / 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.

 

#if defined( SUNPRO_CC) || defined(__GNUC__)

/ / breaks if we make these template class members:

enum {_ALIGN = 8};

enum {_MAX_BYTES = 128};

enum {_NFREELISTS = 16}; / / _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.

#if ! (defined( SUNPRO_CC) || defined( GNUC ))

enum {_ALIGN = 8};

enum {_MAX_BYTES = 128};

enum {_NFREELISTS = 16}; / / _MAX_BYTES/ _ALIGN

# endif

static size_t

 

_S_round_up(size_t

 

__bytes)

 

{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1))

; }

 

PRIVATE:

union _Obj {

union _Obj* _M_free_list_link;

char _M_client_data[1];    / * The client sees this.    */

};

private:

# if defined( SUNPRO_CC) || defined(__GNUC__) || defined( HP_aCC)

static _Obj* STL_VOLATILE _S_free_list[];

/ / Specifying a size results in duplicate def for 4.1

# else

static _Obj* STL_VOLATILE _S_free_list[_NFREELISTS];

# endif

 

 

static    size_t

_S_freelist_index(size_t

 

__bytes) {

 

return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_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_THREADS

static _STL_mutex_lock _S_node_allocator_lock;

# endif

 

/ / It would be nice to use _STL_auto_lock here. But we

/ / don't need the NULL check. And we do need a test whether

/ / threads have actually been started.

class _Lock;

friend class _Lock;

class _Lock {

public:

_Lock() { NODE_ALLOCATOR_LOCK; }

~_Lock() { NODE_ALLOCATOR_UNLOCK; }

};

 

public:

 

 

/ *     n must be > 0    */

static void* allocate(size_t

{

 

 

__n)

 

void* ret = 0;

 

if (__n > (size_t) _MAX_BYTES) {

ret = malloc_alloc::allocate( n);

}

else {

_Obj* STL_VOLATILE* 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

_Obj* RESTRICT result = *__my_free_list;

if ( result == 0)

ret = _S_refill(_S_round_up(__n));

else {

* my_free_list = result -> _M_free_list_link;

ret = result;

}

}

 

return ret;

} ? end allocate ? ;

 

 

/ *     p may not be 0 */

static void deallocate(void*

{

 

 

__p, size_t

 

 

__n)

 

if (__n > (size_t) _MAX_BYTES)

malloc_alloc::deallocate( p, n);

else {

_Obj* STL_VOLATILE*     my_free_list

= _S_free_list + _S_freelist_index( n);

_Obj* q = (_Obj*) p;

 

 

 

/ / 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)

 

 

} ? end default_alloc_template ?     ;

 

typedef default_alloc_template< NODE_ALLOCATOR_THREADS, 0> alloc;

typedef default_alloc_template<false, 0> single_client_alloc;

 

template <bool threads, int inst>

 

inline bool operator==(const

inst>&,

 

__default_alloc_template<__threads,

 

const default_alloc_template< threads, inst>

&)

{

return true;

}

 

# ifdef STL_FUNCTION_TMPL_PARTIAL_ORDER

template <bool threads, int inst>

 

inline bool operator! =(const

inst>&,

 

__default_alloc_template<__threads,

 

const default_alloc_template< threads, inst>

&)

{

return false;

}

# endif / *     STL_FUNCTION_TMPL_PARTIAL_ORDER */

 

 

 

 

/ * 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.    */

//下面这个函数较为复杂,配一张图在此

SGI STL源码文件,stl_alloc.h[注释] - saturnman - 一路

 

template <bool threads, int inst>

char*

default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t

size,

 

 

)

{

char* result;

size_t total_bytes = size * nobjs;

//想要申请的空间总数,最终不一定能满足这么多

size_t bytes_left = _S_end_free - _S_start_free;

int& nobjs

 

 

 

if ( bytes_left >= total_bytes) {

//尝试从二级池中分配,这个池的开口方向有点怪,至少和我感觉舒服的方向不对头

result = _S_start_free;

_S_start_free += total_bytes;

return( result);

} else if ( bytes_left >= size) {

//如果不能满足所要求的__nobjs,那就查查最大能满足多少。

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* STL_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) {

//申请失败,我们可以尝试看看原free list中是否有比这个__size大的块 ,如果这把这个块释放出来不也能满足这次申请要求吗

size_t i;

_Obj* STL_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 <= (size_t) _MAX_BYTES;

i += (size_t) _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.

//一直不明白前面为啥第一次用malloc,这一次要用malloc_alloc的一级内存配置器呢,原来是为了不成功时有异常抛出

} ? end if 0==_S_start_free ?

_S_heap_size += bytes_to_get;

 

_S_end_free = _S_start_free +

return(_S_chunk_alloc(__size,

//二级池有东西之后可以递归调用自己了

} ? end else ?

} ? end _S_chunk_alloc ?

__bytes_to_get;

__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;

//默认的申请元素个数,注意调用_S_refill意味着free_list中内存块大小是__n的自由表没有可用的块了

char* chunk = _S_chunk_alloc( n, __nobjs);

_Obj* STL_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);

} ? end _S_refill ?

 

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_THREADS

template <bool threads, int __inst>

_STL_mutex_lock

 

 

 

default_alloc_template< threads, __inst>::_S_node_allocator_lock

STL_MUTEX_INITIALIZER;

#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>

typename default_alloc_template<__threads, __inst>::_Obj*

STL_VOLATILE

default_alloc_template< threads, __inst> ::_S_free_list[

# if defined( SUNPRO_CC) || defined(__GNUC__) || defined( HP_aCC)

_NFREELISTS

# else

default_alloc_template< threads, __inst>::_NFREELISTS

# endif

] = {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.

 

#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

_Tp)))

 

}

__n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(

 

 

: 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

} ? end allocator ? ;

 

__p) {

 

__p->~_Tp(); }

 

 

template<>

class allocator<void> {

public:

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

return n != 0

 

 

__n, const void* = 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

} ? end allocator ? ;

 

template <class _Alloc>

 

__p) {

 

__p->~_Tp(); }

 

 

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>&,

 

 

{

return true;

}

const malloc_alloc_template<inst>&)

 

 

#ifdef STL_FUNCTION_TMPL_PARTIAL_ORDER

template <int inst>

 

 

 

 

inline bool operator! =(const

 

__malloc_alloc_template<__inst>&,

 

 

{

return false;

}

const malloc_alloc_template< inst>&)

 

#endif / *     STL_FUNCTION_TMPL_PARTIAL_ORDER */

 

 

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;

};

 

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;

};

 

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

struct _Alloc_traits<_Tp,

__inst>

 

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;

};

 

 

template <class _Tp, class _Tp1, bool

struct _Alloc_traits<_Tp,

__thr, int

__inst>

 

 

 

> > >

{

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;

};

 

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:

  评论这张
 
阅读(1930)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017