流数据缓冲库设计方案

流数据缓冲库设计方案

流数据的不对称

所谓流数据，指通道里的数据是串行的，没有分隔符的。流数据到达接收方后，如果没有一个机制来分割流数据，则犹如一堆乱码。这里的机制指发送方和接收方所商定的通信协议，例如一个基本消息（协议规定的最小单位）是以什么字节开头，以什么字节结尾，每个字节的含义是什么。

TCP和串口是面向数据流的传输方式。发送方发送一次的数据，接收方可能分多次接收（read返回）；也可能发送方分多次发送的数据，接收方一次性接收了，这种现象称为粘包，在一个发送方情况下发送数据过快，以及在多个发送方的情况下，粘包很频繁。特别是对于非阻塞read，这种现象就更加频繁了。对于阻塞read，发送方一次发送的数据，接收方一次性接收的可能性比较大，但也不排除分多次接收的可能。

接收方的难言之隐

通过上面的分析，在面向流的数据传输中，发送方与接收方相应的发送和接收操作不是一一对应的，接收方需要把所有接收到的数据“保存”下来，然后根据协议来“分割”数据流，从而“挖掘”出其中的消息。对于“保存”，接收方有诸多难言之隐：

#数据保存在什么数据结构的buffer中？

#从这个buffer中取出部分流数据进行解析，解析完后不能构成一个完整消息的剩余数据如何放回这个buffer？

#一个向buffer中存数据，一个向buffer中取数据，同步效率如何保证？

#因为read操作是在不断的进行的， 是一次性还是多次为buffer分配内存，是分配固定还是动态大小的内存？

需求需求

这样，对于这种普遍存在的传输方式中的接收方而言，APP希望能够对buffer的操作是透明、简单和通用的。这个buffer犹如是一个大小和内容动态变化的文件，里面有其所需要消息的流数据。APP的操作流程是打开这个文件，读取适量大小的流数据，然后“分割”和“挖掘”出消息，当确实“挖掘”不出有意义的消息了，则将剩余的流数据写回文件。

现在就让我来介绍下这样的一个工具的原理及实现，它用来保存流连接中接收方所接收到的数据，并且重点的是它是可扩展性，高效性的，线程安全的。

基本原理

采用双向循环链表作为存储结构，将每次收到的数据构成一个元素，采用固定元素个数的循环链表，并且只在初始化中申请一次内存，这大大提高了效率。

尾指针用来元素入链表，头指针用来元素出链表。当接收方收到数据后，将数据组成元素并放入链表；用户程序在取数据时，会指定期望最多取数据的长度（n），会有一个临时指针，以头指针所在的位置，向尾指针方向移动，直到第i个元素（小于头指针）的元素的数据长度加上前i-1个元素的长度，大于n，而前i-1个元素的数据长度m小于n，则返回前i-1个元素的总长度m以及前i-1个元素的数据组成的bit字符串。

同时支持将数据“反刍”进链表的操作，仍以上面的例子数据为例，如果返回的i-1个元素的m个字节中，“分割”的结果是：只有3/4m个字节是一个完整的消息，剩余的1/4m个字节是不完整的。这时，需要反刍回链表，以使下次取数据能得到完整的消息。

在取数据的过程中，头指针实际上没有真正进行移动，只是有一个临时指针指向了第i个元素，在取完数据后，用户程序会告之真正accept的数据长度h（<=m），如果h等于m，则头指针直接移动到临时指针的位置；如果h小于m，则移动头指针，直到第j个节点（<=i），前j个节点的长度k大于等于h，而前j-1个节点的长度g小于h，那么第一步将尾指针移动到第j个节点处，第二步，将第j个元素的数据的后面的k-h位移动到数据的前k-h位。

例如接收到的数据逻辑顺序为：

Abcdefghijkl

分四次接收，并放入循环链表中（用尾指针放）：

（head）abc def gh ijkl（rear）

取10个字节的数据（从头指针开始取）：

Abcdefghij

如果只有4个字节abcd组成了消息，则只接收4个字节，进行反刍：

（1）第一个节点abc，由于长度3小于4，则此节点不是分界点元素

（2）第二个节点defg，由于全两个元素长度3+3=6大于4，则此节点为分界点元素，将def中的后6-4=2个元素fg，移动到前6-4=2位，则分界点元素为ef

（3）将尾指针移动到分界点节点

最后链表如下：

（head）ef gh ijkl（rear）

数据结构定义

Typedef struct DOUBLECIRCLELIST

{

Char*data;

Intrllen; // real data length

Intbflen; //this buffer block length

structDOUBLECIRCLELIST* prev;

struct DOUBLECIRCLELIST* next;

}DoubleCircleList;

接口定义

Int FdbInit( int blockNum, int blockSize );

Int FdbPutData( char* ptData, int ptLen );

Int FdbGetData( char* gtData, int* gtLen );

Int FdbAcceptLength( int apLen );

//second steps

Int FdbPutDataRemoc( char* ptData, intptLen ); //Enlarge the size of one block

Int FdbEnlargeInit( int blockNum, intblockSize );// Enlarge the number of the list elements

固定元素个数的环形双向链表头尾指针说明：

1、head和rear之间的节点代表是具体的有数据的节点，包括head和rear这两个节点，也就是[head, rear]是有数据的。

2、链表满的条件是：rear->next == head;

3、链表只有一个节点的条件是：rear==head

4、链表为空的条件是：rear == NULL，head != NULL

5、在构造环形链表时，head->prev == reat&&　rear->next= head, 则始终是满的

6、在构建完环形链表后，rear = NULL