本系列博客是由扭曲45原创，欢迎转载，转载时注明出处，http://blog.csdn.net/cg0206/article/details/8258166
SOA,全称small object allocator,中文意思是小对象分配器。box2d虽然是用c++写的，但是并没有使用c++自带的new/delete实现内存管理，而是使用在c的malloc/free做法的基础上封装了类b2BlockAllocator进行内存管理，使得分配和使内存变得更加高效、快速。其中b2BlockAllocator就是一个SOA，下面我们就对源码进行分析。
一、b2BlockAllocator类的头文件
首先我们对头文件b2BlockAllocator.h进行大致的了解一遍。不多说，上代码：
//一次分配内存大小
const int32 b2_chunkSize = 16 * 1024;
//块子节点大小的最大值
const int32 b2_maxBlockSize = 640;
//可以申请块子节点大小的类型总数
const int32 b2_blockSizes = 14;
//块空间增量
const int32 b2_chunkArrayIncrement = 128;
//块子节点结构体[链表实现]声明
struct b2Block;
//块结构体声明
struct b2Chunk;
//这是一个小型的对象分配器，用于一次分配多个小对象
class b2BlockAllocator
{
public:
b2BlockAllocator();
~b2BlockAllocator();
//分配内存，当size>b2_maxBlockSize则直接用b2Alloc分配
void* Allocate(int32 size);
//释放内存，当size>b2_maxBlockSize则直接用b2Free释放
void Free(void* p, int32 size);
//清空内存
void Clear();
private:
//当前块的头指针
b2Chunk* m_chunks;
//当前已使用的块空间节点总数
int32 m_chunkCount;
//当前已申请的块空间节点总数
int32 m_chunkSpace;
//未被使用的内存块链表类型数组，保存了其不同类型链表的头指针
b2Block* m_freeLists[b2_blockSizes];
//申请的块大小类型数组
static int32 s_blockSizes[b2_blockSizes];
//根据要申请块的大小获取其类型索引的数组
static uint8 s_blockSizeLookup[b2_maxBlockSize + 1];
//是否已初始化s_blockSizeLookup数组，标志变量
static bool s_blockSizeLookupInitialized;
};
上面文字是对相关字段及方法的注释，我们就不对其进行讲解了。
二、b2BlockAllocator的.c文件
下面我们看该类的具体实现，看b2BlockAllocator.c文件，
1、变量的定义
映入我们眼帘的是一些变量或结构的定义，如下代码：
int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] =
{
16, // 0
32, // 1
64, // 2
96, // 3
128, // 4
160, // 5
192, // 6
224, // 7
256, // 8
320, // 9
384, // 10
448, // 11
512, // 12
640, // 13
};
uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
bool b2BlockAllocator::s_blockSizeLookupInitialized;
struct b2Chunk
{
int32 blockSize;
b2Block* blocks;
};
struct b2Block
{
b2Block* next;
};
s_blockSizes ：是申请的块子节点大小类型数组，主要负责将相应大小的子节点分类；
blockSizeLookup：是根据要申请的子节点size获取s_blockSizes数组的索引，并保持到该数组中；
s_blockSizeLookupInitialized：是否已初始化s_blockSizeLookup数组，标志变量，用于只需要初始化很少次数的变量，可以人为控制【但是最好还是不要那么做】，默认值是false，也许大家感到奇怪，这个变量在哪初始化的，大家可以猜猜看。
b2Chunk是块结构体，其中blockSize表示块子节点大小，blocks表示块头指针；
b2Block表示块子节点结构体，next表示下一个块头指针，如果你感觉到很熟悉的话，那就对了，这是典型的链表定义，将会用链表将子节点链接起来。
2、函数的实现
1)、构造函数和析构函数
接下来就是该类的构造函数和析构函数了，同样我们也看代码。
b2BlockAllocator::b2BlockAllocator()
{
b2Assert(b2_blockSizes < UCHAR_MAX);
m_chunkSpace = b2_chunkArrayIncrement;
m_chunkCount = 0;
m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
memset(m_freeLists, 0, sizeof(m_freeLists));
if (s_blockSizeLookupInitialized == false)
{
int32 j = 0;
for (int32 i = 1; i <= b2_maxBlockSize; ++i)
{
b2Assert(j < b2_blockSizes);
if (i <= s_blockSizes[j])
{
s_blockSizeLookup[i] = (uint8)j;
}
else
{
++j;
s_blockSizeLookup[i] = (uint8)j;
}
}
s_blockSizeLookupInitialized = true;
}
}
b2BlockAllocator::~b2BlockAllocator()
{
for (int32 i = 0; i < m_chunkCount; ++i)
{
b2Free(m_chunks[i].blocks);
}
b2Free(m_chunks);
}
在构造函数b2BlockAllocator()中我们初始化相关变量，例如一开始我们就判断b2_blockSizes的有效性，接着为m_chunkSpace、m_chunkCount、m_chuns、m_freeLists、和s_blockSizeLookup的初始化。我们主要说说s_blockSizeLookup的初始化是怎样完成的。
a)、用s_blockSizeLookupInitialized判断s_blockSizeLookup是否已初始化，若没有则进入。大家猜到绿色部分的疑问了没，如果你的答案是编译器，那就恭喜你了。
b)、里面的for循环主要是根据块的大小，将块分类成以上14中类型，并设置索引值，保存到s_blockSizeLookup数组中，j保存的是s_blockSizes数组的索引值。
c)、接着判断j的有效性，这里用的是assert断言，关于assert断言的又不懂的童鞋可以参照维基百科上面的解释http://zh.wikipedia.org/wiki/Assert.h
d)、if/else中i不大于j索引对应的块大小类型的数组,则将j索引的值赋给类型索引数组，例如，j = 0时，i的值可以是 1-16。否则i>j索引对应的块大小类型的数组，则将j索引自增，赋值。上面代码可以简化成：
if(i > s_blockSizes[j])
{
++j;
}
s_blockSizeLookup[i] = (uint8)j;
虽然效率差了点:-D，但这样更易于理解。
e)、将标志变量置s_blockSizeLookupInitialized为true，表示已经初始化在析构函数~b2BlockAllocator()我们释放了当前块的每个子节点，和整个块。
2)、内存管理函数内存管理函数分为三个：Allocate分配函数；Free释放函数；Clear清理内存函数
关于Allocate函数，代码如下：
void* b2BlockAllocator::Allocate(int32 size)
{
if (size == 0)
return NULL;
//验证size的有效性
b2Assert(0 < size);
//申请的空间大于规定的最大值，
//直接申请，不放到块的链表中去【即m_chunks】
if (size > b2_maxBlockSize)
{
return b2Alloc(size);
}
//根据要申请的内存大小获取内存类型索引值，并判断有效性
int32 index = s_blockSizeLookup[size];
b2Assert(0 <= index && index < b2_blockSizes);
//查看是否有同类型的未被使用的内存块
if (m_freeLists[index])
{
b2Block* block = m_freeLists[index];
m_freeLists[index] = block->next;
return block;
}
else
{
//已使用的大小与已申请的块大小相等
//重新申请空间
if (m_chunkCount == m_chunkSpace)
{
//获取原来的块头，并保存到oldChunks中
b2Chunk* oldChunks = m_chunks;
//扩充块空间的大小
m_chunkSpace += b2_chunkArrayIncrement;
//申请空间，并重新赋值给m_chunks变量
m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));
//拷贝内存到m_chunks中
memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
//将最新申请的内存的最后b2_chunkArrayIncrement置，防止程序中读取脏数据
//个人感觉如下写法更易于理解，只是效率要慢一点点啦
///memset(m_chunks , 0,m_chunkSpace * sizeof(b2Chunk));
///memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));
memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));
//释放原来的块空间
b2Free(oldChunks);
}
//获取已使用块空间的尾指针
b2Chunk* chunk = m_chunks + m_chunkCount;
//申请n个块子节点内存
//并将地址赋值给块头指针
//这样的好处是不需要频繁的去内存中申请空间，不必每个节点都去申请，提高了效率
chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);
//用于调试，正式版本中将关闭_DEBUG宏，故不存在相关代码，以后我们遇到相关代码块也将忽略
#if defined(_DEBUG)
memset(chunk->blocks, 0xcd, b2_chunkSize);
#endif
//获取根据索引块大小，并赋值给块的大小
int32 blockSize = s_blockSizes[index];
chunk->blockSize = blockSize;
//获取子节点个数
//并防止转换时出现错误【个人猜测，有待考证】
int32 blockCount = b2_chunkSize / blockSize;
b2Assert(blockCount * blockSize <= b2_chunkSize);
//将子节点用链表的方式串起来
//有人不禁疑惑，这不是刚刚申请的一个连续的内存块吗？
//用头指针可以直接访问呀？干嘛要串起来？
//好处：
//可以自由的操作每个子节点，例如、释放、访问、其它方式链接等，在后面我们将看见
for (int32 i = 0; i < blockCount - 1; ++i)
{
b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);
b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));
block->next = next;
}
//获取最后一个内存块的子节点
//并将子节点的下一个节点置空
b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));
last->next = NULL;
//将申请且未使用的指针保存到m_freeLists对应类型的数组中
m_freeLists[index] = chunk->blocks->next;
//当前已使用的块空间节点总数
++m_chunkCount;
//返回块的头指针
return chunk->blocks;
}
代码的解释如上述，在此就不啰嗦了，不过我们总体分析一下，它的逻辑是:
a)、将内存按大小分为16，32，64，96，128，160，192，224，256...640等b2_blockSizes【即14】类，并按照顺序保存到数组s_blockSizes中。
b)、通过申请size的大小，判断是否大于b2_maxBlockSize，如果大于则直接分配。
c)、否则通过size，传递给s_blockSizeLookup数组找到所需要申请的类型index，将index的值在传递给链表数组m_freelists[index]，查找是否有子节点，有则直接返回子节点。
d)、否则将判断m_chunks指向的动态数组是否已用完，若用完则扩充块空间大小加b2_chunkArrayIncrement，重新申请空间，并将空间的内存拷贝到现在的空间中，并释放原内存空间。
e)、通过m_chunks+m_chunkCount获取块空间的m_chunks动态数组的未被使用的空间元素，申请大小为b2_chunkSize的内存，并将其分成对应类型的n块空间，并将这n个子节点串链起来，形成链表。将链表的下一个指针保存到对应类型的m_freeLists数组中，同时返回头指针作为申请的内存地址。
关于Free函数，代码和注释如下：
void b2BlockAllocator::Free(void* p, int32 size)
{
//判断检测size是否有效
//并作相应的处理
if (size == 0)
{
return;
}
b2Assert(0 < size);
if (size > b2_maxBlockSize)
{
b2Free(p);
return;
}
//根据内存大小获取索引值，并判断是否有效
int32 index = s_blockSizeLookup[size];
b2Assert(0 <= index && index < b2_blockSizes);
#ifdef _DEBUG
// Verify the memory address and size is valid.
int32 blockSize = s_blockSizes[index];
bool found = false;
for (int32 i = 0; i < m_chunkCount; ++i)
{
b2Chunk* chunk = m_chunks + i;
if (chunk->blockSize != blockSize)
{
b2Assert( (int8*)p + blockSize <= (int8*)chunk->blocks ||
(int8*)chunk->blocks + b2_chunkSize <= (int8*)p);
}
else
{
if ((int8*)chunk->blocks <= (int8*)p && (int8*)p + blockSize <= (int8*)chunk->blocks + b2_chunkSize)
{
found = true;
}
}
}
b2Assert(found);
memset(p, 0xfd, blockSize);
#endif
//获取块的块的头指针并插入到相应的空闲链表的头部【注意是子节点从链表头部插入】，并保存相应的头指针到m_freeLists中去
b2Block* block = (b2Block*)p;
block->next = m_freeLists[index];
m_freeLists[index] = block;
}
同样，_DEBUG宏类的我们不做讨论。这里说明一下，若内存小于等于b2_maxBlockSize时，此时内存空间并没有释放，而是将链接到相应类型的空闲链表中，并且是从链表头部插入此节点的，对此这也是很容易做到的，这也是刚刚申请空间将连续的空间分割，再次链接成链表的原因。
再看Clear函数
void b2BlockAllocator::Clear()
{
//释放当前已使用的块空间大小
for (int32 i = 0; i < m_chunkCount; ++i)
{
b2Free(m_chunks[i].blocks);
}
m_chunkCount = 0;
//清空块
memset(m_chunks, 0, m_chunkSpace * sizeof(b2Chunk));
//清空未被使用的内存块链表类型数组
memset(m_freeLists, 0, sizeof(m_freeLists));
}
只是释放了形成链表的块内存，m_chunks和m_freeLists也只是清空其内容，真正释放它们是在上面说的类的析构函数中。
ok,不多说了，有什么错误、不妥之处，希望大家能多多指正。也希望和大家多多交流。