剖析SGI STL空间配置器（allocate内存分配函数）

要理解allocate函数是如何分配内存，就要先知道他是怎么管理内存的。
allocate函数的定义如下：

  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
      
      _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;
  };

参数__n是要申请内存的大小，如果大于128字节，就不受二级空间配置器管理，直接通过malloc申请，但不是简单的只做malloc，对其进行了一层封装，在malloc失败时会有异常处理，具体怎么处理后面介绍。
而如果申请的内存大小 小于128字节，就会到二级空间配置器来处理了。二级空间配置器的结构如下图：

自由链表_S_free_list的结点存放一条链表，链表的的起始地址表示一块大小为（下标+1）8的内存，要在二级空间配置器上申请一块内存，需要获取对应大小内存在自由链表的下标，_Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n);这句的代码就是用来定位的，需要注意是用一个二级指针接收的，如果__my_free_list为空，表示没有对应大小的内存块，这时候就需要调用_S_refill函数取填充了，具体怎么填充后面介绍。如果不为空表示有对应大小的内存块，直接把链表的第一个结点返回给用户，再更新链表头节点即可。

#     ifndef _NOTHREADS
      
      _Lock __lock_instance;
#     endif

在多线程环境下，因为自由链表定义在数据段，自由链表需要互斥的访问，在C++STL的设计完全没有考虑多线程，而SGI STL是线程安全的。