频道栏目
首页 > 程序开发 > 移动开发 > 其他 > 正文
游戏引擎Mojoc解析:C实现泛型ArrayList
2017-12-04 09:49:35      个评论    来源:scott.cgi  
收藏   我要投稿

泛型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)」

点击复制链接 与好友分享!回本站首页
上一篇:移动开发soci开发环境搭建教程
下一篇:Hibernate编程开发入门教程:单表操作总结
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站