文档中心

TD开发平台_基础

02.常用数据结构

tdCore开发平台定义了一系列基本的数据类型便于整个平台的移植。 Tuint8,Tunt16,Tuint8,Tint8,Tint16,Tint32分别表示 8位、16位、32位无符号整数和有符号整数; Tuint,Tint分别表示符合硬件体系结构的,能和指针类型互相无损转换的无符号整数和有符号整数。宏 TINT_MIN和 TINT_MAX分别表示最小和最大整数。 Tbool表示布尔量(定义为 Tint8)。char字符和 void *指针类型也仍然使用。 NULL表示空指针 (void *)0。TFloat表示浮点数类型,定义为 double,也可以根据具体硬件平台修改为 float。

1)队列( TQueue)
队列是一个链表容器,其特点是可以快速插入删除节点,访问指定序号的节点前必须遍历。另提供数据结构 TQueue来方便管理队列,下面是如何使用 TQueue:
1、初始化队列
void TQueueInit(TQueue *queue, Tint data_size, Tint free_max_num,
Tint queue_max_num);
例子:
typedef struct {
      Tint my_data;
      ... ...
} my_node;
TQueue my_queue;
TQueueInit(&my_queue, sizeof(my_node), 10, TINT_MAX);
定义一个 TQueue的变量,调用 TQueueInit函数初始化该队列,函数参数 data_size表示链表上每个节点中要容纳的开发人员数据大小(字节);参数 free_max_num表示当开发人员释放一个链表节点时,不立即释放内存而是保持起来的最大空闲节点数;参数 queue_max_num表示该队列上可以分配的最大节点数(不包括空闲节点)。
2、分配和释放队列节点
void *TQueueMalloc(TQueue *queue, Tbool if_head_or_tail);
void TQueueFree(TQueue *queue, void *data);
例子:
my_node *pnode1 = TQueueMalloc(&my_queue, TRUE);
TQueueFree(&my_queue, pnode1);
上例中在链表头插入了一个节点,返回节点中存储开发人员数据的内存首地址给 pnode1;开发人员数据的内存已经被清0了。当节点的内存分配失败或队列中的节点数会超过queue_max_num时,返回 NULL。如果要在链表尾插入一个节点,那么 TQueueMalloc的参数 if_head_or_tail为 FALSE。
摘除并释放节点调用 TQueueFree,该函数内部可能并没有释放这个节点的内存,而是把它挂在一个 free链表上,这样当以后开发人员调用 TQueueMalloc时就可以直接从 free
链表上拿过来用,避免频繁分配和释放内存。
3、遍历队列
void *TQueueSeek(TQueue *queue, void *data, Tbool
if_next_or_prev);
例子:
my_node *phead = TQueueSeek(&my_queue, NULL, TRUE);
my_node *ptail = TQueueSeek(&my_queue, NULL, FALSE);
my_node *pnext = TQueueSeek(&my_queue, phead, TRUE);
my_node *pprev = TQueueSeek(&my_queue, pnext, FALSE);

TQueueSeek函数返回指定节点(参数 data)的后一个(参数 if_next_or_prev为 TRUE)或前一节点(参数 if_next_or_prev为 FALSE),当不指定节点( data为 NULL),就表示得到头节点或尾节点。如果后续没有节点了就返回 NULL。连续调用该函数就可以遍历整个链表:

my_node *phead = TQueueSeek(&my_queue, NULL, TRUE);
while(phead) {
    ... ...
    /*访问phead 节点,但是不能删除它*/
    phead = TQueueSeek(&my_queue, phead, TRUE);
}
或:
my_node *phead = TQueueSeek(&my_queue, NULL, TRUE);
while(phead) {
    my_node *pnext = TQueueSeek(&my_queue, phead, TRUE);
    ... ...
    /*访问phead 节点,甚至可以删除它*/
    phead = pnext;
}

还有下面两个常用函数:

void TQueueFreeAll(TQueue *queue); /*释放所有节点,加入到free 中*/
void TQueueReset(TQueue *queue); /*将一个队列重置为初始化状态,释放所有分配的节点内存,包括free 的*/
2)数组( TArray)
数组的特点是所有的节点在内存中连续存放,这样可以快速的访问指定序号的节点,但是数组的缺点就是插入删除节点可能需要移动其他节点来保持内存的连续性。提供了数据结构 TArray来方便管理数组。下面是如何使用数组容器 TArray:
1、初始化数组
void TArrayInit(TArray *parray, Tint size);
例子:
typedef struct {
    Tint my_data;
    ... ...
} my_node;
TArray my_array;
TArrayInit(&my_array, sizeof(my_node));
首先定义一个 TArray的变量,然后调用 TArrayInit函数初始化该数组,函数参数 size表示数组里的每个节点中要容纳的开发人员数据大小(字节);
2、分配和释放数组元素
void *TArrayAdd(TArray *parray, Tint i, Tint n);
void TArrayDelete(TArray *parray, Tint i, Tint n);
例如:
my_node *pnode = TArrayAdd(&my_array, 0, 5);
my_node *pnode2 = TArrayAdd(&my_array, -1, 2);
TArrayDelete(&my_array, 0, 2);
TArrayDelete(&my_array, -1, 1);

TArrayAdd函数在数组的第 i个位置增加 n个元素,返回增加元素的首地址。 i的范围是[0,数组中元素个数 ],如果 i等于 -1就表示在尾部增加 n个元素。新增加的元素内存已经被清 0。增加数组元素可能导致 TArray在内部调用 realloc()扩大内存。并且每次分配内存都会多分配一部分,防止频繁调用 TArrayAdd增加元素时每次都realloc内存。
TArrayDelete函数用于在数组的第 i个位置删除 n个元素,i的范围是 [0,数组元素个数-1],如果 i等于 -1就表示删除尾部 n个元素。删除元素也不是每次都会调 realloc收缩内存,只有当多余内存到达一个限度时才 realloc收缩内存。最多删除 n个元素。

3、访问数组

void *TArrayGet(TArray *parray, Tint i); /*得到数组第i 个元素的首地址。i的范围是[0, 数组元素个数-1],没有返回NULL*/
例子:
my_node *pnode = TArrayGet(&my_array, 0);

4、其他常用的操作

void TArrayClear(TArray *parray, Tint i, Tint n);
void *TArraySet(TArray *parray, Tint n);
void TArrayReset(TArray *parray);
宏:TARRAY_LENGTH(my_array)
宏:TARRAY_HEAD(my_array)

TArrayClear用于从数组第 i个位置开始的 n个元素内存清 0,i的范围是 [0,到数组元素个数 -1],i等于 -1表示清除尾部的 n个元素;最多清除 n个元素。
TArraySet用于直接设置数组的元素个数并只分配需要的内存,并且返回第一个元素的内存地址。如果 n等于 -1就等于数组里的元素个数,这时就仅仅相当于收缩内存。
TArrayReset用于将数组重置为初始化状态,释放所有分配的内存。
宏 TARRAY_LENGTH()用于获得数组中的元素个数。
宏 TARRAY_HEAD()用于获得数组中第一个元素的内存地址。

3)字符串 ID(T_ID)
在后续的数据结构和模块中,经常要用字符串来作为标识,例如用字符串 "click"来标识点击事件类型;用 "window"来标识一种对象类型;用 "width"来标识对象的宽度属性;用"get_volume"来标识一种远程方法调用;用 "volume_change"来标识一种远程消息类型等等。但是在实际编程中字符串的传递和比较操作复杂和耗时,如果把一个字符串转换成一个唯一的整数 id,整数的操作就比较简单。用类型 T_ID来表示这个整数类型。平台提供了下面两个函数:
typedef Tuint T_ID;
T_ID TStringGetID(const char *string, Tint len);
const char * TIDGetString(T_ID id, int *len);

TStringGetID得到字符串 string的整数 id,len表示这个字符串的长度,如果 len等于 -1,就表示该字符串是以 '\0'结束的,内部将用 strlen()取得字符串长度。该函数不会返回None(即整数 0),除非 string为 NULL或 len小于等于 0。TStringGetID函数只保证在同一个进程中,相同的字符串得到相同的整数 id,不同的字符串得到不同的整数 id。这里要注意以下两点:
a、在不同的进程中,相同的字符串得到的整数 id不一定相同;
b、同一个程序的多次运行,相同的字符串得到的整数 id不一定相同;
TStringGetID函数的时间复杂度为 O(log(n))。
TIDGetString函数用于反向查找整数 id对应的字符串,时间复杂度为 O(1)。
并且定义了下面的一个宏来方便获取字符串 ID:

#define TStringID(string) TStringGetID(string, -1)
例如:
T_ID event_id = TStringID(“change”); 等同于:
T_ID event_id = TStringGetID("change", -1);

用一个特殊值 None(等于 0)来表示空的字符串 ID,没有字符串的 id为 None。

4)表( TTable)
表 TTable是最重要的数据结构。可以把 TTable看做为一个两列多行的表格,每一行表示 TTable的一个节点,每个节点都是一个( id, value)二元对。其中 id的类型是 T_ID,是通过 TStringGetID函数得到的一个字符串 id;value表示这个节点的值,值的类型可以是整数( Tint)、字符串、指针( void *)、浮点数( TFloat)和表( TTable)(即表是可以嵌套的,没有层次限制,但是不能循环)。一个 TTable中的所有节点 id都不重复,除了 id等于 None,即允许存在多个 id等于 None的节点。下面是一个 TTable的例子:
TTable的设计来源于 C语言中的 strcut结构,上面的例子就对应了下面的内容:
id = TStringID(“x”) value = (Tint)5
id = TStringID(“v”) value = (TFloat)3.14
id = TStringID(“name”) value = "example"
TTable可以简单、清晰的表示复杂信息结构,用途很多。下面是如何使用 TTable。

1、表的创建和删除

TTable * TTableCreate(void); /*创建一个空的TTable*/
void TTableDestroy(TTable *table); /*销毁所有节点和TTable 本身,释放所有内存*/
void TTableReset(TTable *table); /*清空TTable,销毁所有节点,释放节点内存,回到新创建时的状态*/
例如:
TTable * mytable = TTableCreate();
TTableReset(mytable);
TTableDestroy(mytable);
注意如果一个 TTable中含有 TTable类型的节点,即一个 TTable嵌套一个子 TTable,那么销毁这个节点时也会自动销毁这个子 TTable。

2、节点的查找、创建和删除

TTableNode * TTableGetNode(TTable *table, T_ID id, Tbool if_create);/*查找、创建*/
void TTableDeleteNode(TTable *table, TTableNode *node);/*删除指定节点*/
例子:
TTableNode *mynode1 = TTableGetNode(mytable, TStringID(“x”),TRUE);
TTableNode *mynode2 = TTableGetNode(mytable, TStringID(“y”),FALSE);
TTableNode *mynode3 = TTableGetNode(mytable, None, TRUE);
TTableDeleteNode(mynode1);
节点的查找和创建是同一个函数 TTableGetNode,该函数的功能是:当 table中存在指定 id的节点时,就返回这个节点的指针;当不存在时,如果 if_create等于 TRUE就创建一个节点并返回,如果 if_create等于 FALSE,就返回 NULL。当参数 id等于 None时,TTableGetNode函数就直接创建一个节点并返回(这时 if_create当然应该等于 TRUE)。
一个 TTable中的节点除了可以通过 id来查找外,还可以通过序号来直接访问,这个序号就是节点的创建顺序。
TTableNode * TTableGetIndexNode(TTable *table, Tint index);
Tint TTableGetCount(TTable *table); /*得到节点个数*/
TTableGetIndexNode 函数直接返回指定序号的节点,index 的范围为[0, 节点个数-1],TTableGetNode 函数当id 不等于None 时,它的时间复杂度为O(log(n));当id 等于None 时,时间复杂度为O(1) 。TTableGetIndexNode 的时间复杂度为O(1) ;TTableDeleteNode 的时间复杂度为O(n)。
3、节点的赋值,节点的值可以为以下几种类型
typedef enum { T_VALUE_NONE,
T_VALUE_STRING ='S', /*字符串*/
T_VALUE_TABLE='T', /*表*/
T_VALUE_INT ='I', /*整数*/
T_VALUE_FLOAT ='X', /*浮点数*/
T_VALUE_POINTER ='P', /*指针*/
} TTableNodeTypeEnum;
TTable新创建的节点都是没有值的,即值的类型为 T_VALUE_NONE。可以通过下面的函数来给一个节点赋值:
Tint TTableNodeSetInt(TTableNode *tnode, Tint value);
Tint TTableNodeSetInt(TTableNode *tnode, Tint value);
Tint TTableNodeSetFloat(TTableNode *tnode, TFloat value);
Tint TTableNodeSetPointer(TTableNode *tnode, void *value);
Tint TTableNodeSetString(TTableNode *tnode, const char *value, Tint len);
Tint TTableNodeSetTable(TTableNode *tnode, TTable *value); /*自动销毁之前
当节点没有值,或者已有的值类型和要赋值的类型一致时,赋值成功并返回 0,否则赋值失败并返回 -1。注意整数类型和浮点数类型是可以转换的,即当一个节点是整数类型时,给它赋值为浮点数是成功的,并且这个节点的类型也改为浮点类型;反之也可以从浮点类型改为整数类型。 TTableNodeSetString给节点赋值字符串,参数 len表示字符串的长度 (不包括尾部的 0),如果 len等于 -1,就用 strlen来得到字符串的长度。赋值成功会在内部复制一份该字符串的内容,并在尾部多分配一个字节填 0。
下面是获取节点的值:
Tint TTableNodeGetInt(TTableNode *tnode);
TFloat TTableNodeGetFloat(TTableNode *tnode);
void * TTableNodeGetPointer(TTableNode *tnode);
char * TTableNodeGetString(TTableNode *tnode, Tint *len);
TTable * TTableNodeGetTable(TTableNode *tnode, Tbool bring_out);
当想要获取的值类型和节点的值类型不符时,对于整数和浮点数类型返回 0,对于字符串、指针和 Table类型返回 NULL;注意整数类型和浮点数类型是可以转换的,即当一个节点是整数类型时,TTableNodeGetFloat会得到整数转换的浮点数,反之也可以得到浮点数转换的整数。 TTableNodeGetTable获取节点的 Table指针,参数 bring_out表示是否把该节点的值修改为 NULL,即断开该节点和这个子 Table的联系。这样做的目的就是把子 Table提取出来自己管理,防止以后删除该节点时自动删除这个子 Table,当然一般情况下 bring_out等于 FALSE。
通过下面的函数取得一个节点的值的类型:
TTableNodeTypeEnum TTableNodeGetType(TTableNode *tnode);
因为开发人员在实际使用过程中经常是先根据一个 id来创建节点,然后给该节点赋值,所以定义了下面几个辅助宏,来完成创建和赋值的操作:
#define TTableAddInt(table, id, value) \
TTableNodeSetInt(TTableGetNode(table, id, TRUE), value)
#define TTableAddFloat(table, id, value) \
TTableNodeSetFloat(TTableGetNode(table, id, TRUE), value)
#define TTableAddPointer(table, id, value) \
TTableNodeSetPointer(TTableGetNode(table, id, TRUE), value)
#define TTableAddTable(table, id, value) \
TTableNodeSetTable(TTableGetNode(table, id, TRUE), value)
#define TTableAddString(table, id, value, len) \
TTableNodeSetString(TTableGetNode(table, id, TRUE), value, len)
相应的也有下面几个根据 id来获取值的辅助宏:
#define TTableGetType(table, id) \
TTableNodeGetType(TTableGetNode(table, id, FALSE))
#define TTableGetInt(table, id) \
TTableNodeGetInt(TTableGetNode(table, id, FALSE))
#define TTableGetFloat(table, id) \
TTableNodeGetFloat(TTableGetNode(table, id, FALSE))
#define TTableGetPointer(table, id) \
TTableNodeGetPointer(TTableGetNode(table, id, FALSE))
#define TTableGetString(table, id, plen) \
TTableNodeGetString(TTableGetNode(table, id, FALSE), plen)
#define TTableGetTable(table, id) \
TTableNodeGetTable(TTableGetNode(table, id, FALSE), FALSE)
4、序列化和反序列化
可以将一个 TTable的所有内容(包括嵌套的子 TTable)转换成二进制数据流,方便信息传递和存盘。当然也可以把二进制数据流再转换回 TTable。
char * TTableToString(TTable *table, Tint *size);
TTable * TTableFromString(const char *buf, Tint size);
Tint TTableStringLength(TTable *table);
Tint TTableToString2(TTable *table, char *buf);
TTableToString函数把 table序列化成一段二进制数据,返回存放这段二进制数据的内存指针,size返回内存大小(由开发人员负责 free这段内存)。TTableFromString函数从一 段指定大小的二进制数据流反序列化,重构 table(由开发人员负责销毁这个 table)。
TTableStringLength函数可以单纯得到序列化所需的内存大小。 TTableToString2函
数直接在开发人员提供的内存里序列化二进制数据,但是开发人员要保证提供的内存足够大,该函数返回实际使用的内存大小。
也提供了把 table序列化的成二进制数据文件和从二进制数据文件加载 table的函数:
void TTableSaveToFile(TTable *table, const char *file);
TTable *TTableLoadFromFile(const char *file);

5、其他常用操作

T_ID TTableNodeGetID(TTableNode *tnode); /*得到一个节点的id*/
void TTableDump(TTable *table); /*打印一个TTable 的内容,用于调试*/
TTable * TTableDuplicate(TTable * table); /*复制一个TTable,当然复制的
TTable 需要用户自己销毁*/
5)ini文件
在应用程序的开发中,经常需要用文本文件来配置应用程序运行的参数,或者在运行时保存一些参数到文本文件。 TCore开发平台支持一种简单的 ini文本文件格式到 TTable的转换。
TTable *TLoadIniFile(TTable *table, const char *file, TIniFileFlag_Func
func);
void TSaveIniFile(TTable *table, const char *file);
例子:
TTable *mytable = TLoadIniFile(NULL, “ini_file_path”, NULL);
TLoadIniFile的参数 table如果不等于 NULL,就表示把 file的内容加入到已有的 table中,否则新创建一个 table。参数 func一般为 NULL。
下面是一个典型的 Ini的文件例子:
#这一行是注释
[section_name1]
key1=”string value1” #注释(直到换行)
key2=123
[section_name2]
“string_value2”

这个Ini 文件转换成的TTable 结构如下:

注意如果有两个节的 section_name相等,那么这两个节将合并成一个 table。
在 ini文件中,每一个节中也仍然可以再嵌套子 table,示例如下:

[section_name1]
key1={
    key2=”string value1”
    key3=123
    key4={
        “string value2”
        “key5=100
    }
}
Ini文件甚至还可以没有节,示例如下: 
key1=”string value1”
key2=123
key3={
    “string value2”
}
6)哈希( THash)
需要根据一个字符串来快速查找一个开发人员自定义的 struct结构时,需要使用额外提供的一个哈希(THash)数据结构(TTable用于模块或进程间的信息传递和保存较为的,而且支持根据整数 id来快速查找,但访问 table的成员没有直接的 struct结构访问快,并且需要把一个任意的字符串转换成整数 id)。
1、哈希( THash)的创建
#define THASH_TYPE_STRING 0x0
#define THASH_TYPE_ID 0x1
THash *THashCreate(Tint hash_type);
例子:
THash * myhash1 = THashCreate(THASH_TYPE_STRING);
THash * myhash2 = THashCreate(THASH_TYPE_ID);
可以创建两种类型的哈希,一种是根据一个字符串查找,另一种是根据一个整数 id查找。一旦初始化时设定了类型,那么就不允许进行另一种类型的操作
2、哈希( THash)节点的创建、查找和删除
THashNode *THashStringFind(THash *str_hash, const char *name, Tint len,Tbool if_add);
THashNode *THashIDFind(THash *id_hash, T_ID id, Tbool if_add);

哈希节点的创建和查找是同一个函数,字符串类型的哈希节点用 THashStringFind函数,整数类型的哈希节点用 THashIDFind函数。如果查找到指定字符串或整数的节点,就返回该节点,如果没有找到并且 if_add等于 TRUE,就创建一个节点并返回,如果 if_add等于 FALSE就返回 NULL。这两个查找函数的时间复杂度为 O(log(n))。注意哈希节点的整数id不能为None(如果id等于None,THashIDFind返回NULL)。
销毁一个节点都是用同一个函数THashFreeNode,该函数的时间复杂度为O(log(n))。

3、哈希( THash)节点的赋值

void THashNodeSetData(THashNode *hash, void *data);
void *THashNodeGetData(THashNode *hash);
可以给每个哈希节点关联一个开发人员指针,也可以之后从哈希节点得到这个关联的指针。当一个哈希节点创建时,这个指针默认为 NULL。

4、哈希( THash)的遍历和销毁

typedef Tbool (* THashNodeVisit_Func)(THashNode *node, void *arg);
THashNode*THashVisitEach(THash *str_id_hash, THashVisit_Func func,void *arg);
typedef void (* THashNodeDestroy_Func)(THashNode *node, void *arg);
void THashDestroy(THash *str_id_hash, THashNodeDestroy_Func func,

THashVisitEach函数会遍历每一个哈希节点,然后对每一个节点都回调参数 func函数,节点的遍历顺序不一定和节点的创建顺序相同。如果回调函数 func返回 TRUE就表示终止遍历,立即返回当前的哈希节点。如果 func返回 FALSE就表示继续遍历下一个节点,遍历完毕后返回 NULL。在回调参数 func中不允许销毁该节点。
THashDestroy函数销毁每个哈希节点和整个 THash数据结构,在销毁每个哈希节点之前都回调参数 func函数,使得开发人员可以删除这个节点关联的资源。