「游戏引擎Mojoc」(8)C实现泛型ArrayList
泛型ArrayList是基础的数据结构，然而在C的标准库里并没有提供，所以需要自己手动实现一个。Mojoc的ArrayList实现经过了实践的测试，达到了稳定和高效的状态，源码ArrayList.h。
本文主要介绍实现思路和一些特性，Mojoc的泛型ArrayList主要完成了以下几个功能：
- 存取放任意数据类型。
- 动态内存扩展。
- 针对栈数据与堆数据不同的存储策略。
- 一组简洁的数据操作接口。
- 利用宏进行了接口简化和特殊调用。
- 一些高效优化的数据操作策略。
ArrayList的数据
typedef struct
{
/**
* 手动设置内存扩展策略
*/
int increase;
/**
* 数组元素类型大小
*/
int elementTypeSize;
/**
* 元素个数
*/
int size;
/**
* 元素数据内存，使用Array结构存储
*/
Array(elementType) elementArray[1];
}
ArrayList;
typedef struct
{
/**
* 内存指针
*/
void* data;
/**
* 元素个数
*/
int length;
}
Array;ArrayList 使用 Array结构来存放数据的内存。所以，Array的Length其实是Capacity，而ArrayList的Size是元素的个数。
实现泛型的策略是保存元素类型的大小elementTypeSize，这样在遍历的时候，就可以根据不同类型，进行数据的检索。
elementArray负责存储数据。
使用了realloc来进行内存的扩充，所以elementArray的data指针是会变化的。increase是扩展内存的大小，这里并没有用一般百分比扩容的策略。
ArrayList的构建
// 堆上创建
ArrayList* (*Create)(int elementTypeSize);
// 栈初始化
void (*Init)(int elementTypeSize, ArrayList* outArrayList);
// 堆上创建，带有元素个数
ArrayList* (*CreateWithSize)(int elementTypeSize, int size);
// 栈上初始化，带有元素个数
void (*InitWithSize)(int elementTypeSize, int size, ArrayList* outArrayList);
// 堆上创建，带有容量
ArrayList* (*CreateWithCapacity)(int elementTypeSize, int capacity);
// 栈上初始化，带有容量
void (*InitWithCapacity)(int elementTypeSize, int capacity, ArrayList* outArrayList);这里提供了3种策略，2种形式的构建。其中，堆上创建就是malloc内存数据，栈上初始化在于ArrayList是栈对象，比如
ArrayList list[1];这样的构造形式。或是初始化在其它struct类型中的嵌入ArrayList。Init前缀的函数提过了初始化的功能。elementTypeSize就是泛型中的类型，比如
sizeof(int), sizeof(struct)等等。
ArrayList的泛型形式
#define ArrayList(elementType) ArrayList这个简单的宏定义，在实践中却有不可思议的效果，对于明确泛型使用提供了直觉上的便利性和可读性。elementType是一个形式，被替换为不存在，这样就模拟了泛型语法中<>的可读性。
// 栈上 int 类型
ArrayList(int) list[1]; Init(sizeof(int), list);
// 堆上 int 类型
ArrayList(int)* list = Create(sizeof(int));
struct Obj
{
ArrayList(float) list[1];
ArrayList(float)* otherList;
};ArrayList的数据操作
// 添加元素空间，并返回元素地址
void* (*GetAdd)(ArrayList* arrayList);
// 插入元素空间，并返回元素地址
void* (*GetInsert)(ArrayList* arrayList, int index);
// 拷贝元素，并返回元素地址
void* (*Add)(ArrayList* arrayList, void* elementPtr);
//插入元素，并返回地址
void* (*Insert)(ArrayList* arrayList, int index, void* elementPtr);
...一旦确定了elementTypeSize，所有的操作都会基于elementTypeSize。从而实现了不同类型，一套数据类型的操作。当然，也会提供一套宏，来简化API的调用。
#define AArrayList_GetAdd(arrayList, elementType) \
(*(elementType*) AArrayList->GetAdd(arrayList))
#define AArrayList_GetInsert(arrayList, index, elementType) \
(*(elementType*) AArrayList->GetInsert(arrayList, index))
#define AArrayList_Add(arrayList, element) \
AArrayList->Add(arrayList, &(element))
#define AArrayList_Insert(arrayList, index, element) \
AArrayList->Insert(arrayList, index, &(element))
...ArrayList的一些特别的操作
// 弹出一个元素，实现高效的模拟了Stack
void* (*Pop)(ArrayList* arrayList, void* defaultElementPtr);
// 高效的删除一个范围的元素
void (*RemoveRange)(ArrayList* arrayList, int fromIndex, int toIndex);
// 删除一个元素，并用最后一个元素填充。避免了元素移动，但会打乱元素次序
void (*RemoveByLast)(ArrayList* arrayList, int index);
// 利用realloc的特点，释放动态增长的多余空间
void (*Shrink)(ArrayList* arrayList);
// 初始化常量ArrayList
#define AArrayList_Init(elementType, increase) \
{ \
increase, \
sizeof(elementType), \
0, \
{ \
NULL, \
0, \
}, \
}
/**
* 构建一个固定容量的ArrayList
*/
#define AArayList_InitFix(elementType, capacity, size, ...) \
{ \
0, \
sizeof(elementType), \
size, \
AArray_Init(elementType, capacity, __VA_ARGS__), \
}还有很多就不一一列举了，很多API的设定，都是在实践中需求的，为了效率，为了优化，为了提高性能特别增加的。
ArrayList的实现
源码的实现，ArrayList.c，可以看到原理很简单，实现清晰明确，这是工程实践的结果。如果曾经手动实现过泛型ArrayList，在来看这份代码实现，就能感受到简洁的力量，没有多余的直接完成目的。
如果用这个代码去写些功能，用的过程中就会发现，所有想要的功能尽在其中，而边界检查效率稳定性都面面俱到。
ArrayList的删除操作
关于删除操作，需要多说一些。删除，需要移动元素。但有一个小技巧，就是倒序遍历删除。
for (int i = arrayList.size - 1; i > -1; i--)
{
// 删完继续往前走，其它不用操心。
Remove(arrayList[i]);
}但这里还有一个更高效的函数，如果不在意元素顺序的话。
for (int i = arrayList.size - 1; i > -1; i--)
{
// 这里会删掉元素，使用最后一个元素填充，无需移动其它元素
RemoveByLast(arrayList, i);
}最后
Mojoc的泛型ArrayList的实现，只使用了C语言的标准库，可以拿出来独立使用。更多的使用示例请看scottcgi/Mojoc的源代码，全局搜索ArrayList。
「ArrayList(T)」