自由链表（free list）——SGI STL的空间配置器（allocator）第二级配置器维护方法

参考：《STL源码剖析》 以及 STL空间配置器之第二级配置器的free-list详解

/*free list的节点*/
union obj{
	union obj * free_list_link; // 第一字段
	char client_data[1];  // 第二字段
};

/*16个free list的头指针存放于数组free_list[]*/
static obj * volatile free_list[16];

（1）链表头指针数组free_list[ ]

  自由链表free list包含了16个链表，每个链表都是由大小为x bytes的内存区块连接。x分别表示8、16、24、…112、120、128。而16个链表的头指针保存在数组free_list[ ]中。数组free_list[ ]的每个元素均为指向节点的指针。比如free_list[11]所指向的链表是由多个大小均为96bytes的内存区块组成。
  各种大小为x的内存区块在还没有被allocat出去用于保存数据时，它们都以链表的形式串联在一起。当调用allocat()方法被分配出去后，就从这个链表中去除了。因此16个链表中串起来的各个内存区块都是空闲的，一旦需要被使用，就会从链表中离开。

（2）free list 节点 obj

  每个自由链表都是由若干个大小相同的内存区块串联而成，而每个内存区块的开头部分都被一个union占据。union类似于struct，但其中的变量所占空间是重叠的，从不同的变量角度看就会被解释为不同含义。这里的union名字为obj，其中的两个变量free_list_link与client_data[ ]占据着同一块大小为4byte的内存空间，client_data[ ]指向头1byte。这4byte内存空间，从free_list_link的角度看，就被解释为free_list_link的值；从client_data[ ]的角度看，就被解释为client_data[0]的值。每个内存区块的开头4byte都归这个obj所有。
  这里定义char client_data[1]的做法其实非常巧妙。在一块内存的开头位置定义一个数组client_data[ ]，那么数组名client_data相当于指向这块区域首地址的一个常指针。而这个数组所存的内容client_data[0]其实不会被用到。整块内存区域在使用时都会被数据覆盖，而数组名client_data仍旧指向这块内存区域。因此既能将client_data当做一个存储该内存空间的指针变量，又不需要为这个指针变量分配空间来保存这个地址值从而节约了内存空间。
  free_list_link是一个指向obj的指针变量。当该内存区块空闲时，free_list_link指向下一个相同大小的内存区块，这4byte保存地址信息。而数组名client_data则指向当前内存区块。当该内存区块被用于保存数据而离开自由链表free list时，这4byte空间就被数据所覆盖。而此时由于离开了链表，也就无需指向下一个内存区块了。
  这里再啰嗦地总结一下：每个内存区块的头4byte在区块空闲时保存指针变量free_list_link的值，指向下一个区块串联起链表；而在用于保存数据时，这4byte被数据的一部分所覆盖。而数组client_data[ ]始终作为一个“并不占据内存的常指针”存在，只是形式上将头1byte划分给它，但它并不使用，它也无所谓这1byte内存里存的是什么。

（3）内存池管理函数chunk_alloc()

  内存池管理函数chunk_alloc(size_t size , int& nobjs)每次都从一个完整的内存区域中从顶部划出一整块连续的区域。这块区域小于等于所求的size*nobjs bytes。返回值为该内存区域的首地址。划分的方法简单来说就是将start_free指针返回，然后移动start_free到新的位置。
  不需要担心内存池出现碎片。一般来说，内存池从顶部划给free list的空间并不考虑收回来，当内存池中没有剩余空间时会重新malloc一块空间，带着整个内存池转移阵地。而只有整个heap空间都没有剩余空间时，内存池才会回收free list中整块连续的空闲区域。
  内存池并不负责free那些malloc获得的内存空间。

（4）自由链表重新填充函数refill()

  当16个链表中某一个链表串起来的内存区块都被用完时，其在数组free_list[ ]保存的头指针将变为0，即不指向任何内存空间。此时就需要重新串起一个链表。
  调用函数refill(size_t n)可以串起一个空闲的链表，将头指针保存在数组free_list[ ]对应位置，并返回一个内存区块以供保存数据使用（这个内存块不会进入链表而是直接被使用，只有调用deallocate()时才会回归链表）。

  指针变量chunk为内存池管理函数chunk_alloc()返回的整块内存空间首地址。函数refill()负责把这块内存划分成一个一个区块，将第一个区块返回给客端保存数据，剩下的区块进行串联后将头指针保存在数组free_list[ ]对应位置。

（5）空间配置函数allocate()

  当所求空间大于free list管理的最大区块128bytes时，调用第一级配置器直接分配内存空间。
  当所求空间小于128bytes时，将所求区块大小上调至8倍数边界。选择合适的一个链表，从其头部取一个区块出来保存数据，而将其后续区块的地址作为链表的新头指针保存到数组free_list[ ]对应位置。
  取出区块后，该区块的头4byte所保存的地址信息就被数据所覆盖。

（6）空间释放函数deallocate()

  释放的空间大于128bytes时，调用第一级配置器直接释放。
  空间小于128bytes时，该区块是之前从free list中分配出去的，大小是8的倍数。因此找到对应的链表，将该区块插至头部，并与后序区块串联。将自己的地址作为链表的新头指针保存到数组free_list[ ]对应位置。
  归还区块后，该区块的头4byte重新作为指针变量free_list_link保存后续区块的地址。