varch/doc/list.md

介绍

list容器是对C语言的链表进行通用化的封装，list支持任意数据类型（int，char，struct等等），封装了链表常用的增删改查方法（这里的查是随机访问），可以直接当作普通的容器来使用，也可以在此基础上二次封装。

接口

创建和删除list对象

list_t list_create(int dsize);
void list_delete(list_t list);
#define list(type) // 为了更简便的使用，对list_create套一层宏定义
#define _list(list) // 对list_delete套一层宏定义，并在list删除后置为空

其中list_t为list的结构体，创建方法则会返回一个空的list对象，创建失败则返回NULL，其中dsize传入数据的大小。删除方法则是删除传入的list对象。创建方法和删除应该成对使用，创建出来在结束使用应该删除掉。

void test(void)
{
    list_t list = list(int); // 定义并创建一个int型的list
    _list(list); // 成对使用，用完即删除
}

list的插入和移除

void* list_insert(list_t list, int index, void* data);
int list_erase(list_t list, int index, int num);

list的巨大优势就是其插入和移除的效率，不用数据移位只需修改链表指向。
插入的方法是在指定索引的位置插入指定地址的数据（在其中，data传入NULL时则只是开辟空间，不进行赋值），插入成功后返回插入后的数据的地址，插入失败则是返回NULL。而移除则是移除指定索引的num个数据，返回实际移除了的个数。

void test(void)
{
    list_t list = list(int);  // 定义并创建一个int型的list
    int i = 0;
    void *data;

    /* 插入数据 */
    for (i = 0; i < 6; i++)
    {
        data = list_push_back(list, &i); // 尾插 0~5
        if (data) printf("insert %d\r\n", *(int*)data); // 插入后打印出来
    }

    _list(list); // 成对使用，用完即删除
}

结果：

insert 0
insert 1
insert 2
insert 3
insert 4
insert 5

通过插入和移除方法还延伸出了，以下的宏定义方法

#define list_push_front(list, data)
#define list_push_back(list, data)
#define list_pop_front(list)
#define list_pop_back(list)
#define list_clear(list)

list数据的读写

void* list_data(list_t list, int index);
#define list_at(list, type, i)

list_data方法就是根据索引来获取数据的地址，返回的则是指定的数据的地址，NULL则是失败。而list_at则是在list_data的基础上加多类型。
list的随机访问和连续地址的数组或者vector不太一样，数组是可以直接定位到指定索引的地址，而链表要进行随机访问，就得从表头开始通过链接指针一步步的指向到指定位置，而在此过程就会花费比较多的时间去一步步指向。varch的list增加了内置迭代器，可以记录当前访问的位置，当下次再访后面的位置时，就不必再从链表头开始指向了，而从当前位置开始指向到指定位置，如此有着很高的正向遍历效率。

void test(void)
{
    list_t list = list(int);
    int i = 0;

    for (i = 0; i < 6; i++)
    {
        list_push_back(list, &i);
    }

    for (i = 0; i < 6; i++) // 正向遍历
    {
        printf("list[%d] = %d\r\n", i, list_at(list, int, i));
    }

    _list(list);
}

结果：

list[0] = 0
list[1] = 1
list[2] = 2
list[3] = 3
list[4] = 4
list[5] = 5

list的大小和和数据大小

int list_size(list_t list);
int list_dsize(list_t list);

list的size很好理解，也就是像数组那样的大小，dsize也就是创建时候传入的数据的大小。

void test(void)
{
    list_t list = list(int);
    int i = 5;
    while (i--) list_push_back(list, NULL); // 尾插5个空数据，也就是只开辟空间，但不赋值
    printf("size = %d, data size = %d\r\n", list_size(list), list_dsize(list));
    _list(list);
}

结果：

size = 5, data size = 4

参考例子

typedef struct {
    char *name;
    int age;
} STUDENT;

void test(void)
{
    list_t list_int = list(int); // 定义并创建int型list
    list_t list_student = list(STUDENT); // 定义并创建结构体STUDENT型list
    char *name[3] = { // 定义三个名字
        "ZhangSan",
        "LiSi",
        "WangWu",
    };
    int i = 0;

    for (i = 0; i < 3; i++)
    {
        STUDENT s = {name[i], 18 + i};
        list_push_back(list_student, &s); // 插入三个STUDENT
        list_push_back(list_int, &i); // 依次插入 0 1 2
    }

    i= 1024; list_insert(list_int, 1, &i); // 在索引1的位置插入1024
    for (i = 0; i < list_size(list_int); i++)
    {
        printf("list_int[%d] = %d\r\n", i, list_at(list_int, int, i)); // 正向遍历
    }

    for (i = 0; i < list_size(list_student); i++)
    {
        printf("list_student[%d]: name=%s, age=%d\r\n", i, list_at(list_student, STUDENT, i).name, list_at(list_student, STUDENT, i).age); 
    }

    // 结束使用该list后就删除
    _list(list_int);
    _list(list_student);
}

结果：

list_int[0] = 0
list_int[1] = 1024
list_int[2] = 1
list_int[3] = 2
list_student[0]: name=ZhangSan, age=18
list_student[1]: name=LiSi, age=19
list_student[2]: name=WangWu, age=20

例子里面使用函数很多没有对返回值进行判断，实际应用需对返回值进行判断。

源码解析

list结构体

list容器的所有结构体都是隐式的，也就是不能直接访问到结构体成员的，这样子的方式保证了模块的独立与安全，防止外部调用修改结构体的成员导致list存储结构的破坏。所以list解析器只留了唯一一个list的声明在头文件，然后结构体的定义都在源文件。只能使用list容器提供的方法对list对象进行操作。
list类型声明

typedef struct LIST *list_t;

使用时候，只是用list_t即可。

/* type of list */
typedef struct LIST
{
	NODE* base;					/* address of base node */
	NODE* iterator;				/* iterator of list */
	int size;					/* size of list */
	int dsize;					/* data size */
	int index;					/* index of iterator */
} LIST;

LIST结构体中包含了5个成员，base（链式结构的基结点，也就是表头），iterator（当前指向的结点），size（list的大小，也就是list的长度），dsize（每个数据的大小），index（iterator所在的索引）。

/* type of list node */
typedef struct _NODE_
{
	struct _NODE_ *next; /* next node */
} NODE;
#define data(node) ((node)+1) /* data of node */

在NODE结构体当中，显式的成员也就只有next（指向下一个结点，形成链式结构），那数据存在哪里呢？这是varch的list的一个兼容所有数据结构的一个特性，因为每种数据类型的大小不太一致，如果规定结构体里面跟着的固定长度，那么就兼容不了不同长度的数据类型。然而，在这个NODE结构体当中，把实际的数据分配了在结构体末尾的空间，具体多长就由LIST的dsize来决定，然后把这个data成员称为隐式成员（不直接在结构体中体现）。那么要获取data成员的地址也很简单，就是在结点地址+1偏移NODE的size即可，如此，可以减少再一级指针指向data的指针空间了。
当创建int型list时候，NODE的数据可以理解为如下了：

typedef struct _NODE_
{
	struct _NODE_ *next; /* next node */
    char data[sizeof[int]];
} NODE;

迭代器的随机访问

前面说到list内置了迭代器，那这个迭代器是怎么回事呢？
看下源码：

static NODE* list_node(list_t list, int index) // 传入list和索引
{
	if (!list) return NULL;
	if (index < 0 || index >= list->size) return NULL;  // 判断索引有没有越界

    /*
    这个一步是重置迭代，也就是将迭代器定位回到链表首位
    满足其中3个条件之一都重置迭代器
    1、因为单向链表，不能反向指向，所以目标索引小于迭代器的索引时候，就要重置，然后从链表首位迭代到指定索引
    2、迭代器指针为空时，为空则没有指向具体的结点，当然得重置迭代，所以外部想重置迭代器，只需将迭代器指向置NULL即可
    3、目标索引index为0时，主动获取第0位，也就是首位
    */
	if (index < list->index || !list->iterator || index == 0)
	{
		list->index = 0;
		list->iterator = list->base;
	}

    /*
    循环将迭代器迭代到指定的索引位置
    单向链表索引正向递增，所以正向遍历时候时间复杂度O(n)，反向遍历还是O(n^2)
    */
	while (list->iterator && list->index < index)
	{
		list->iterator = list->iterator->next;
		list->index++;
	}

    /* 返回迭代器指向的结点 */
	return list->iterator;
}

在varch的list提供的所有api中，只要是传入索引的，都会调用上述访问进行链表的定位，所以在同一个索引操作时，是不需要重新进行指向定位的，而可以快速返回。