空间配置器.md

第一次看有点看不懂（完全看不懂）

allocator被称为空间配置器而不是内存配置器的原因：空间不一定是内存，空间也可以是磁盘或者辅助存储介质（存在面向磁盘的配置器）

STL标准规格告诉我们：配置器定义与之中，SGI内有以下两个文件：
<stl_alloc.h> // 负责空间的配置与释放
<stl_construct.h> // 负责内容的构造与析构

• 空间配置器设置的接口（暂时不记录）
• 配置器中的construct和destroy函数：
  construct和destroy为构造和析构的基本工具，在于<stl_construct.h>文件中被定义和书写。
  construct的功能比较简单，就是泛化地使用placement new （必须包含<new.h>文件），实例化一个类并且返回其指针。
  destroy的第一版功能是接受一个指针并且调用指针所指向的对象的析构函数，第二版允许接受范围[first,last)的迭代器，若对象的析构函数不是trivial destructor(不重要的析构函数)就一个个地进行销毁，否则不做处理（不理解这里为什么不做处理）
  SGI 的空间的配置和释放的设计哲学：
• 向system heap要求空间
• 考虑多线程的状态
• 考虑内存不足时的应变措施
• 考虑过多“小型区块”可能造成的内存碎片问题
  c++的内存配置的基本操作是::operator new()，内存释放的基本操作是::operator delete()。这两个全局函数相当于c的malloc和free函数。仔细来讲，会在一个for循环里不断尝试释放、配置、再释放、再配置，直到内存被分配好为止，除非客端没有设定”内存不足处理例程“。
  考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层级配置器：
  第一级配置器：

1. allocate()直接使用malloc()
2. deallocate()直接使用free()
3. reallocate()直接调用realloc()
4. 模拟c++的set_new_handler()来处理内存不足的情况：c++的new handler机制时可以要求系统在内存配置无法被满足时调用一个自己指定的函数 第二级配置器：（会主动将任何内存需求上调至8的倍数
5. 维护16个自由链表负责16个小型区块的次配置能力（具体实现？）

   union obj{
   	union obj * free_list_link;
   	char client_data[1]; 
   }

   这个数据结构非常的精髓：通常自由链表为了维护下一个链表的指针会再定义一个指针，但是，这个指针是占用内存空间的！为了减少这种额外负担这里使用union进行定义，一物二用，这个指针既指向该链表的区块又指向下一个可以使用的链表。
6. 如果需求区块大于128bytes就调用第一级配置器
   二级配置器涉及的内容挺多的：
7. 二级配置器的基本构造：数据结构构造、ROUND_UP()函数、FREELIST_INDEX(size_t bytes)函数等基本组件的具体实现，还有负责实际内存分配的allocate()、deallocate()、reallocate()成员函数和内存池的起始位置地址、结束位置地址和堆的大小等成员变量和最精髓的chunk_alloc()函数和refill()函数
8. 空间配置函数allocate()：bytes大于128就调用第一级配置器，否则寻找16个freelist种适当的一个，找不到就通过refill重新填充freelist，找到了就调整freelist（类似于链表中砍掉一个节点）然后返回区块给客端
9. 空间释放函数deallocate()：与allocate()类似，但是不需要重新填充freelist，找到块之后直接进行回收就好（与链表增添一个节点类似）
10. 重新填充freelist：从内存池取得nobj个新区块（但是不一定能取到这么多，因为有可能内存池空间不够了）。如果只取到一个区块就直接返回给客端，否则调整freelist纳入新结点（类似链表的头插法，但是具体的实现很tricky）
11. 内存池 （chunk_alloc()函数的实现）：有以下几种情况：
    1. 内存池剩余空间完全满足需求量：直接分配后返回起始位置
    2. 内存池剩余空间不能完全满足需求量但是能至少供应一个以上的区块：重新更改需要的总字节数后把内存池能够提供的区块返回给freelist
    3. 内存池剩余空间连一个区块的大小都无法提供：先把内存池中的剩余零头配给适当的freelist，然后配置heap空间来补充内存池：先调用malloc函数尝试直接从堆中获得内存（新的大小为需求量的两倍加上一个随着配置次数越来越大的附加量），如果失败则尝试在freelist中检查有没有可以使用的区块，如果有则更改内存池的起始和结束位置为freelist中相应的位置，并且递归调用自己来修正nobj；如果没有就调用第一级配置器的out-of-memory机制尝试能不能释放一些其它内存来获得空间；总是递归调用自己来修正堆的大小和nobj。
       内存基本处理工具：（STL将以下三个函数实际定义于<stl_uninitalized>）
       uninitialized_copy(first,last,result)：将内存的配置与对象的构造行为分离开来
       uninitialized_fill(first,last,x)：同样地将内存的配置与对象的构造行为分离开来，能够在一定范围内进行初值填充
       uninitialized_fil_n(first,n,x)：同样地将内存的配置与对象的构造行为分离开来，能够在初始地址加上一个固定偏移量的范围内设定初值
       以上的三个函数都具有*”commit or roll back”*的语意，即成功提交或者回滚，在某个地址的位置上若不能成功进行元素的构造则析构掉已经构造的所有元素