C++之STL心法#3-空间配置器stl

文中的代码摘自SGI版本的STL中的stl_alloc.h。本人在阅读源码的过程中对部分函数和代码作了注释，当然有部分中文注释是直接翻译原始的英文注释过来的。为了方便阅读，没有将代码分段展开描述，读者可以把代码复制到本地，一边看代码，一边看注释，可以帮助理解。后续会针对源代码中的部分内容单独展开进行讲解，感兴趣的读者可以关注后续发表的博文。

#ifndef __SGI_STL_INTERNAL_ALLOC_H
#define __SGI_STL_INTERNAL_ALLOC_H

#ifdef __SUNPRO_CC
#  define __PRIVATE public
   //额外的访问限制使我们无法真正将某些东西私有化。
#else
#  define __PRIVATE private
#endif

#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
#  define __USE_MALLOC
#endif




#if 0
#   include 
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include 
#   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endif

#ifndef __ALLOC
#   define __ALLOC alloc
#endif
#ifdef __STL_WIN32THREADS
#   include 
#endif

#include 
#include 
#include 
#include 
#ifndef __RESTRICT
#  define __RESTRICT
#endif

#if !defined(__STL_PTHREADS) && !defined(_NOTHREADS) 
 && !defined(__STL_SGI_THREADS) && !defined(__STL_WIN32THREADS)
#   define _NOTHREADS
#endif

# ifdef __STL_PTHREADS
    
#   include 
#   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
   
#   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 
# ifdef __STL_SGI_THREADS
    

    extern "C" {
      extern int __us_rsthread_malloc;
    }
	
	//上面的代码是从malloc.h中复制的。包含会更干净，但在某些标准一致性级别上会有问题。

#   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


#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
# ifdef __DECLARE_GLOBALS_HERE
    void (* __malloc_alloc_oom_handler)() = 0;
    //g++2.7.2不处理静态模板数据成员。
# else
    extern void (* __malloc_alloc_oom_handler)();
# endif
#endif


template 
class __malloc_alloc_template {

private:

static void *oom_malloc(size_t);//oom代表out of memory

static void *oom_realloc(void *, size_t);

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    static void (* __malloc_alloc_oom_handler)();//注意：g++2.7.2不处理静态模板数据成员。
#endif

public:

//调用c语言的malloc函数申请内存
static void * allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);//如果malloc申请内存失败，则调用oom_malloc再次申请内存
    return result;
}

//调用C语言的free函数，释放malloc申请的内存
static void deallocate(void *p, size_t )
{
    free(p);
}

//调用C语言库函数realloc，尝试重新调整之前调用malloc所分配的指针p所指向的内存块的大小。
static void * reallocate(void *p, size_t , size_t new_sz)
{
    void * result = realloc(p, new_sz);
    if (0 == result) result = oom_realloc(p, new_sz);//如果调整内存失败，则调用oom_realloc再次尝试调整内存
    return result;
}


static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;//将f赋值给此类的静态数据成员“__malloc_alloc_oom_handler”
    return(old);//返回赋值前__malloc_alloc_oom_handler的值
}

};//到这里，__malloc_alloc_template类的定义就结束了



// 下面是内存不足时的处理代码
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template 
void (* __malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;//给静态数据成员变量__malloc_alloc_oom_handler赋值为0
#endif


template 
void * __malloc_alloc_template::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 
void * __malloc_alloc_template::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;//给__malloc_alloc_template<0>取一个别名，叫malloc_alloc

template
class simple_alloc {

public:
    static T *allocate(size_t n)
                { return 0 == n? 0 : (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 (0 != 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.

template 
class debug_alloc {

private:

enum {extra = 8};       // 存储空间大小，请注意必须足够大才能保存对齐。

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

//给malloc_alloc取个别名;
typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;

# else



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

private:
	//实际上我们应该使用static const int x = N，而不是enum {x = N}，但很少有编译器接受前者。
	
# ifndef __SUNPRO_CC
    enum {__ALIGN = 8};
    enum {__MAX_BYTES = 128};
    enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//实际上__NFREELISTS=16
# endif

//将要申请的字节数bytes调整为__ALIGN即8的倍数
  static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  }
__PRIVATE:
  union obj {   //free_list的节点构造
        union obj * free_list_link;
        char client_data[1];    
  };
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]; //定义一个含有16个元素的列表
# endif

//根据bytes小决定使用第n号链表，n从1开始计数
  static  size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN-1)/__ALIGN - 1);//求空闲列表元素的下标
  }

  // 返回大小为n的对象，并可能加入大小为n的其它区块到free list。
  static void *refill(size_t n);
  
  //为nobjs分配一个大小为size的数据块，如果不方便申请所请求的数量的内存，则nobjs的值可能会减小
  static char *chunk_alloc(size_t size, int &nobjs);

  //块分配状态.
  static char *start_free;//内存池起始位置，只在chunk_alloc中变化
  static char *end_free;//内存池结束位置，只在chunk_alloc中变化
  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;//Linux互斥量，用于线程同步
# endif

# ifdef __STL_WIN32THREADS
    static CRITICAL_SECTION __node_allocator_lock;//Windows临界区，用于线程同步
    static bool __node_allocator_lock_initialized;

  public:
    __default_alloc_template() {
		//这里假设第一个构造函数是在线程启动之前调用的
        if (!__node_allocator_lock_initialized) {
            InitializeCriticalSection(&__node_allocator_lock);//调用Windows的API初始化一个临界资源对象
            __node_allocator_lock_initialized = true;
        }
    }
  private:
# endif

    class lock {
        public:
            lock() { __NODE_ALLOCATOR_LOCK; }//上锁，根据不同的宏定义调用不同平台的函数
            ~lock() { __NODE_ALLOCATOR_UNLOCK; }//解锁
    };
    friend class lock;//将lock类作为__default_alloc_template类的友元

public:

  
  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));//如果n大于128，则调用第一级内存配置器（allocate函数）申请内存
    }

	//如果n小于128，就检查对应的free_list
    my_free_list = free_list + FREELIST_INDEX(n);
    
#ifndef _NOTHREADS
	lock lock_instance;//通过调用构造函数获取锁，在析构时解除锁。
#endif

    result = *my_free_list;

	
    if (result == 0) {
        void *r = refill(ROUND_UP(n));
        return r;
    }

	//调整free_list
    *my_free_list = result->free_list_link;
    return (result);
  };

  
  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);//如果n大于128，则调用第一级配置器deallocate函数释放内存
        return;
    }

	//寻找对应的free_list
    my_free_list = free_list + FREELIST_INDEX(n);

# ifndef _NOTHREADS
    lock lock_instance;
#endif

	//调整free_list，回收区块
    q -> free_list_link = *my_free_list;
    *my_free_list = q;
  }

  static void * reallocate(void *p, size_t old_sz, size_t new_sz);

} ;

//重新生成两个类型alloc、single_client_alloc，第1个模板参数为true时表示在多线程中，false则意味着不使用多线程
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef __default_alloc_template single_client_alloc;



template 
char*
__default_alloc_template::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 = 2 * total_bytes + ROUND_UP(heap_size >> 4);
       
		//下面的代码，是试着让内存池中的剩余空间还有利用价值
        if (bytes_left > 0) { 
			
			//内存持重还有一点点剩余的空间，先分配给适当的freelist，首先要寻找适当的freelist
            obj * __VOLATILE * my_free_list =
                        free_list + FREELIST_INDEX(bytes_left);

			//调整freelist，将内存池中的残余空间编入
            ((obj *)start_free) -> free_list_link = *my_free_list;
            *my_free_list = (obj *)start_free;
        }

		//申请堆内存，用来扩充内存池
        start_free = (char *)malloc(bytes_to_get);
        if (0 == start_free) {//堆空间不足，内存申请失败
            int i;
            obj * __VOLATILE * my_free_list, *p;
			
			//
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) {
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return(chunk_alloc(size, nobjs));
                    //任何剩余的部分将最终使其成为正确的自由列表。
                }
            }
	    end_free = 0;	// 如有异常
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
            //这应该会抛出一个异常或纠正这种情况。因此，我们假定它成功了。
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return(chunk_alloc(size, nobjs));
    }
}



template 
void* __default_alloc_template::refill(size_t n)
{
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);//尝试取得nobjs个区块作为freelist的新节点，注意nobjs是引用类型的
    obj * __VOLATILE * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

	//如果只获得一个区块，就分配给调用者，freelist无新节点；否则准备调整freelist，加入新的节点
    if (1 == nobjs) return(chunk);
    my_free_list = free_list + FREELIST_INDEX(n);

    
      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 -> free_list_link = 0;
            break;
        } else {
            current_obj -> free_list_link = next_obj;
        }
      }
    return(result);
}

template 
void*
__default_alloc_template::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);
}

//__node_allocator_lock是一个静态数据成员，用于线程同步，下面的代码是在初始化它的值。
#ifdef __STL_PTHREADS
    template 
    pthread_mutex_t
    __default_alloc_template::__node_allocator_lock
        = PTHREAD_MUTEX_INITIALIZER;
#endif

#ifdef __STL_WIN32THREADS
    template  CRITICAL_SECTION
    __default_alloc_template::__node_allocator_lock;

    template  bool
    __default_alloc_template::__node_allocator_lock_initialized
	= false;
#endif

#ifdef __STL_SGI_THREADS
__STL_END_NAMESPACE
#include 
#include 
__STL_BEGIN_NAMESPACE


template 
volatile unsigned long
__default_alloc_template::__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 
void 
__default_alloc_template::__lock(volatile unsigned long *lock)
{
    const unsigned low_spin_max = 30;  // 如果我们怀疑是单处理器，则旋转周期
    const unsigned high_spin_max = 1000; // 多处理器的自旋周期
    static unsigned spin_max = low_spin_max;
    unsigned my_spin_max;
    static unsigned last_spins = 0;
    unsigned my_last_spins;
    static struct timespec ts = {0, 1000};
    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)) {
            
            last_spins = i;
            spin_max = high_spin_max;
            return;
        }
    }
    //我们可能会被安排在其他进程的日程上。睡眠。
    spin_max = low_spin_max;
    for (;;) {
        if (!__test_and_set((unsigned long *)lock, 1)) {
            return;
        }
        nanosleep(&ts, 0);
    }
}

template 
inline void
__default_alloc_template::__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;
        //这在许多多处理器上是不够的，因为写入受保护的变量和锁可能会被重新排序。
#   endif
}
#endif

//静态数据成员的定义及初始化
template 
char *__default_alloc_template::start_free = 0;

template 
char *__default_alloc_template::end_free = 0;

template 
size_t __default_alloc_template::heap_size = 0;

template 
__default_alloc_template::obj * __VOLATILE
__default_alloc_template ::free_list[
# ifdef __SUNPRO_CC
    __NFREELISTS
# else
    __default_alloc_template::__NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
//这16个0是使SunPro编译器的4.1版本满意所必需的。否则，它似乎为数组分配了太少的空间。

# ifdef __STL_WIN32THREADS
  //创建一个临界区初始化。每个文件只执行一次，但只有第一个构造函数可以执行任何操作。
  static alloc __node_allocator_dummy_instance;
# endif

#endif 

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif

__STL_END_NAMESPACE

#undef __PRIVATE

#endif 

// Local Variables:
// mode:C++
// End: