在前文中，我们有看到，数据发送的过程，大体是发送者CUDT将要发送的数据放进它的CSndBuffer m_pSndBuffer，并将它自己添加进它的CSndQueue m_pSndQueue的CSndUList m_pSndUList的堆里，后面CSndQueue m_pSndQueue的worker线程会通过CSndUList::pop()从CSndUList m_pSndUList的堆顶CUDT中获取一个要发送的包来发送，包的获取主要是通过CUDT::packData()来完成，而这个函数正是UDT中包发送的执行中心。
CUDT::packData()
===================
这里就来看一下CUDT::packData()的定义(src/core.cpp)：
1int CUDT::packData(CPacket& packet, uint64_t& ts) { 2 int payload = 0; 3 bool probe = false; 4 5 uint64_t entertime; 6 CTimer::rdtsc(entertime); 7 8 if ((0 != m_ullTargetTime) && (entertime > m_ullTargetTime)) 9 m_ullTimeDiff += entertime - m_ullTargetTime; 10 11 // Loss retransmission always has higher priority. 12 if ((packet.m_iSeqNo = m_pSndLossList->getLostSeq()) >= 0) { 13 // protect m_iSndLastDataAck from updating by ACK processing 14 CGuard ackguard(m_AckLock); 15 16 int offset = CSeqNo::seqoff(m_iSndLastDataAck, packet.m_iSeqNo); 17 if (offset < 0) 18 return 0; 19 20 int msglen; 21 22 payload = m_pSndBuffer->readData(&(packet.m_pcData), offset, packet.m_iMsgNo, msglen); 23 24 if (-1 == payload) { 25 int32_t seqpair[2]; 26 seqpair[0] = packet.m_iSeqNo; 27 seqpair[1] = CSeqNo::incseq(seqpair[0], msglen); 28 sendCtrl(7, &packet.m_iMsgNo, seqpair, 8); 29 30 // only one msg drop request is necessary 31 m_pSndLossList->remove(seqpair[1]); 32 33 // skip all dropped packets 34 if (CSeqNo::seqcmp(m_iSndCurrSeqNo, CSeqNo::incseq(seqpair[1])) < 0) 35 m_iSndCurrSeqNo = CSeqNo::incseq(seqpair[1]); 36 37 return 0; 38 } else if (0 == payload) 39 return 0; 40 41 ++m_iTraceRetrans; 42 ++m_iRetransTotal; 43 } else { 44 // If no loss, pack a new packet. 45 46 // check congestion/flow window limit 47 int cwnd = (m_iFlowWindowSize < (int) m_dCongestionWindow) ? m_iFlowWindowSize : (int) m_dCongestionWindow; 48 if (cwnd >= CSeqNo::seqlen(m_iSndLastAck, CSeqNo::incseq(m_iSndCurrSeqNo))) { 49 if (0 != (payload = m_pSndBuffer->readData(&(packet.m_pcData), packet.m_iMsgNo))) { 50 m_iSndCurrSeqNo = CSeqNo::incseq(m_iSndCurrSeqNo); 51 m_pCC->setSndCurrSeqNo(m_iSndCurrSeqNo); 52 53 packet.m_iSeqNo = m_iSndCurrSeqNo; 54 55 // every 16 (0xF) packets, a packet pair is sent 56 if (0 == (packet.m_iSeqNo & 0xF)) 57 probe = true; 58 } else { 59 m_ullTargetTime = 0; 60 m_ullTimeDiff = 0; 61 ts = 0; 62 return 0; 63 } 64 } else { 65 m_ullTargetTime = 0; 66 m_ullTimeDiff = 0; 67 ts = 0; 68 return 0; 69 } 70 } 71 72 packet.m_iTimeStamp = int(CTimer::getTime() - m_StartTime); 73 packet.m_iID = m_PeerID; 74 packet.setLength(payload); 75 76 m_pCC->onPktSent(&packet); 77 //m_pSndTimeWindow->onPktSent(packet.m_iTimeStamp); 78 79 ++m_llTraceSent; 80 ++m_llSentTotal; 81 82 if (probe) { 83 // sends out probing packet pair 84 ts = entertime; 85 probe = false; 86 } else { 87#ifndef NO_BUSY_WAITING 88 ts = entertime + m_ullInterval; 89#else 90 if (m_ullTimeDiff >= m_ullInterval) { 91 ts = entertime; 92 m_ullTimeDiff -= m_ullInterval; 93 } else { 94 ts = entertime + m_ullInterval - m_ullTimeDiff; 95 m_ullTimeDiff = 0; 96 } 97#endif 98 } 99 100 m_ullTargetTime = ts; 101 102 return payload; 103}
在这个函数中，处理了两大类packet的读取，一是丢失的packet，二是正常的顺序传输的包。来看一下这个函数具体的执行过程：
1. 读取当前的时间entertime。
2. 更新m_ullTimeDiff。在UDT中，包发送会有一个随着网络状况调整的一个发送周期，也就是m_ullInterval值。在每一次发送包时，都会根据m_ullInterval值计算下一次包发送的理想时间，并记录在m_ullTargetTime中。而m_ullTimeDiff则被用来记录当前的这次包发送想对于理想的发送时间的延滞值，这个值会被用于计算下一次包发送的理想时间。UDT正是通过这样的修正来尽可能使的包发送周期能够保持在m_ullInterval值附近。
3. 从丢失包列表m_pSndLossList中获取一个丢失的包的SeqNo，并赋值给packet.m_iSeqNo。这个丢失包列表中的包可能是来源于Timer，比如一个包超过了正常时间还没有得到响应，也有可能来源于发送端发回的NACK消息，后面会在来研究这个问题。
4. 前一步中获取的SeqNo大于等于0，这表明存在丢失了需要重传的包，则读取丢失的包的内容：
(1). 计算丢失的包的SeqNo与SndLastDataAck的差值offset。
(2). 检查前一步计算出来的offset值，若小于0，表明发送窗口已经滑过了，则直接返回，否则继续执行。
(3). 根据前面计算的offset值，通过m_pSndBuffer->readData()把数据读入packet中。packet的m_iMsgNo会被更新为packet的MsgNo，msglen也会在packet过期时被更新。
(4). m_pSndBuffer->readData()返回0，表明读取的packet的数据长度为0。这样的packet没有实际发送的必要，直接返回，无需进行后续的步骤。
(5). m_pSndBuffer->readData()返回-1，表明要读取的packet已经过期，同样没有发送这个数据包本身的必要。
但此时会发送一个DropMsgRequest给数据接收端。
然后将过期的packet从SndLossList中移除出去。
m_iSndCurrSeqNo的值为最近一次发送的packet的SeqNo，这里还会在必要的时候更新m_iSndCurrSeqNo，以跳过所有被丢弃的packets。必要指的是，m_iSndCurrSeqNo的值小于等于要丢弃的这个Msg的最后一个packet的SeqNo。这也就意味着，要丢弃的这个Msg直到过期被丢弃都没有发完。
这个地方有一点比较奇怪，简化来看，seqpair[0] == packet.m_iSeqNo，seqpair[1] == seqpair[0] + msglen，也就是说seqpair[1]的值为要被丢弃Msg的最后一个packet的SeqNo加1，但在判断是否要更新m_iSndCurrSeqNo时，却是拿m_iSndCurrSeqNo和（seqpair[1] + 1），也就是要被丢弃的Msg的最后一个packet的SeqNo加2在比较，而更新也是被设置为这个值。但实际上，将m_iSndCurrSeqNo设置为被丢弃Msg的最后一个packet的SeqNo已经可以跳过整个Msg的发送了，因为下次要用m_iSndCurrSeqNo来获得SeqNo，会先将这个值加1的。这个地方的逻辑疑似存在bug。
返回0，向调用者表明暂时没有数据要发送。
(6). m_pSndBuffer->readData()返回大于0的值，表明有一个丢失的包需要重新发送，则更新m_iTraceRetrans和m_iRetransTotal，这两个值分别表示一次trace重发的总次数，和此UDT Socket总的重发次数，两者的区别在于前者在被读取之后会被重置为0(CUDT::sample())，而后者则不会。此时需要继续执行后面的第6步。
5. 在第3步中读取的SeqNo小于0，表明没有丢失的packet。此时则：
(1). 根据m_iFlowWindowSize和m_dCongestionWindow的值计算cwnd发送窗口的大小。发送窗口大小取这两个值中较小的那个，默认情况下，前者为8192(来自于Handshke消息的m_iFlightFlagSize字段，而m_iFlightFlagSize则根据m_iRcvBufSize和m_iFlightFlagSize得出)，后者为16(来自于CC的m_dCWndSize字段，在CUDTCC::init()中该值被初始化为16。)。
(2). 检查发送窗口是否已满。若已满，则将m_ullTargetTime和m_ullTimeDiff重置为0，将ts置为0，然后返回0，向调用者表明没有数据要发送。否则继续执行。
m_iSndLastAck的值为下一次Ack应该确认的packet的SeqNo，CSeqNo::seqlen()计算的是包含两个端点在内的区间的长度。此处对CSeqNo::seqlen()的调用被用来计算，下个packet发送之后，发送窗口中所有的packet的个数。
(3). 读取下一个需要发送的packet，并检查返回的payload值。若payload值为0，表明数据缓冲区中所有的数据都已经发送了，无需再进行实际的发送，则将m_ullTargetTime和m_ullTimeDiff重置为0，将ts置为0，返回0，向调用者表明没有数据要发送。否则继续执行。
(4). 主要是更新m_iSndCurrSeqNo，并设置packet的SeqNo字段。如果SeqNo为16的整数倍，还会设置probe为true。
6. 设置packet的m_iTimeStamp，m_iID，及数据长度。
7. 更新m_llTraceSent和m_llSentTotal，其中前者表示CUDT这次Trace的过程中发送的总的packet数量，这个值会在CUDT::sample()获取trace数据之后被重置为0，而后者则表示发送的总共的packet数量，不会在CUDT::sample()获取trace数据之后被重置。
8. 根据probe的值，更新ts值等。配 合CUDT::packData()的调用者CSndUList::pop()一起看，可知ts是理想中该CUDT下次发送数据的时间点。
probe设置为true，就是表明，当前的这个packet被发送结束之后立即发送下一个packet。即使probe的值不为true，也有可能要立即发送下一个packet，比如延滞时间已经超过了理想的发生周期。存在延滞时间，但该延滞时间又没有超出理想的发送周期的，则下个packet的发送时间具体本次packet的发送时间会小于理想的packet发送周期。
总之这里是希望能够保持packet以接近理想的速率发送。
9. 更新m_ullTargetTime为ts。ts这个下次发包的理想时间点还需要m_ullTargetTime进行记录。
10. 返回payload值，也就是读取的packet的大小。
这里顺便来看下CSeqNo的设计与实现。这个类被用来帮助进行与SeqNo有关的一些计算(src/common.h)：
1class CSeqNo { 2 public: 3 inline static int seqcmp(int32_t seq1, int32_t seq2) { 4 return (abs(seq1 - seq2) < m_iSeqNoTH) ? (seq1 - seq2) : (seq2 - seq1); 5 } 6 7 inline static int seqlen(int32_t seq1, int32_t seq2) { 8 return (seq1 <= seq2) ? (seq2 - seq1 + 1) : (seq2 - seq1 + m_iMaxSeqNo + 2); 9 } 10 11 inline static int seqoff(int32_t seq1, int32_t seq2) { 12 if (abs(seq1 - seq2) < m_iSeqNoTH) 13 return seq2 - seq1; 14 15 if (seq1 < seq2) 16 return seq2 - seq1 - m_iMaxSeqNo - 1; 17 18 return seq2 - seq1 + m_iMaxSeqNo + 1; 19 } 20 21 inline static int32_t incseq(int32_t seq) { 22 return (seq == m_iMaxSeqNo) ? 0 : seq + 1; 23 } 24 25 inline static int32_t decseq(int32_t seq) { 26 return (seq == 0) ? m_iMaxSeqNo : seq - 1; 27 } 28 29 inline static int32_t incseq(int32_t seq, int32_t inc) { 30 return (m_iMaxSeqNo - seq >= inc) ? seq + inc : seq - m_iMaxSeqNo + inc - 1; 31 } 32 33 public: 34 static const int32_t m_iSeqNoTH; // threshold for comparing seq. no. 35 static const int32_t m_iMaxSeqNo; // maximum sequence number used in UDT 36};
连接发起端在执行CUDT::connect(const sockaddr* serv_addr)时，会计算一个随机的值作为m_iISN，也即是发送的首个数据packet的SeqNo，而在连接建立过程中，这个值会被同步给Peer端的Socket。
这里可以看到，UDT Packet的SeqNo是[0, 0x7FFFFFFF]区间中的一个值。每发送一个packet，m_iSndCurrSeqNo都会被递增。通过class CSeqNo可以看到这个递增的规则，即SeqNo超出0x7FFFFFFF时会被归0。也正是由于0是一个合法的SeqNo，在incseq(int32_t seq, int32_t inc)中，SeqNo超出最大值时的计算里能看到有额外的减1，在seqlen()里，SeqNo超出最大值时的计算里能看到加2。
由seqcmp()和seqoff()这两个函数可见，同一时刻同时有效的两个SeqNo seq1和seq2之间的距离不能超过m_iSeqNoTH 0x3FFFFFFF，若超过则表明一定有一个SeqNo越过了最大值0x7FFFFFFF，也即较小的那个值越过了最大值。
这里还可以再来看一下CSndBuffer::readData()：
1int CSndBuffer::readData(char** data, int32_t& msgno) { 2 // No data to read 3 if (m_pCurrBlock == m_pLastBlock) 4 return 0; 5 6 *data = m_pCurrBlock->m_pcData; 7 int readlen = m_pCurrBlock->m_iLength; 8 msgno = m_pCurrBlock->m_iMsgNo; 9 10 m_pCurrBlock = m_pCurrBlock->m_pNext; 11 12 return readlen; 13} 14 15int CSndBuffer::readData(char** data, const int offset, int32_t& msgno, int& msglen) { 16 CGuard bufferguard(m_BufLock); 17 18 Block* p = m_pFirstBlock; 19 20 for (int i = 0; i < offset; ++i) 21 p = p->m_pNext; 22 23 if ((p->m_iTTL >= 0) && ((CTimer::getTime() - p->m_OriginTime) / 1000 > (uint64_t) p->m_iTTL)) { 24 msgno = p->m_iMsgNo & 0x1FFFFFFF; 25 26 msglen = 1; 27 p = p->m_pNext; 28 bool move = false; 29 while (msgno == (p->m_iMsgNo & 0x1FFFFFFF)) { 30 if (p == m_pCurrBlock) 31 move = true; 32 p = p->m_pNext; 33 if (move) 34 m_pCurrBlock = p; 35 msglen++; 36 } 37 38 return -1; 39 } 40 41 *data = p->m_pcData; 42 int readlen = p->m_iLength; 43 msgno = p->m_iMsgNo; 44 45 return readlen; 46}
CSndBuffer::readData(char** data, int32_t& msgno)读取当前的Block。基本上就是读取Block，然后将指向当前Block的指针m_pCurrBlock向后移一个Block。
而CSndBuffer::readData(char** data, const int offset, int32_t& msgno, int& msglen)则是读取距未响应的Block中最旧一块Block offset个单位的Block。在这个函数中，首先是移动到要读取的目标Block，如果要读取的Block已过期，则使m_pCurrBlock跳过该packet所属的Msg的所有Packet，然后返回-1退出。目标Block没有过期，则读取Block后返回数据长度。
总结在CUDT::packData()中对发送过程的控制。
丢失的包具有最高的发送优先级，这也是发送可靠性的保障方法。所有丢失的packet都会被放进SndLossList，这个List中的包可能来源于超时未得到响应，也可能来源于消息接收端发回的NACK。
对于正常的顺序packet发送的控制主要在于两个方面，一是发送窗口的大小，也就是某个时刻已经发送但未得到相应的packet的最大个数，这一点主要由m_dCongestionWindow和m_iFlowWindowSize来表示；二是控制两个包发送的时间间隔，也就是包的发送速率，这一点则主要用m_ullInterval来表示。所有的发送控制机制主要通过影响这几个变量来控制发送过程。
SndLossList
先来看一下CSndLossList这个数据结构。这个Class的定义如下(src/list.h)：
1class CSndLossList { 2 public: 3 CSndLossList(int size = 1024); 4 ~CSndLossList(); 5 6 // Functionality: 7 // Insert a seq. no. into the sender loss list. 8 // Parameters: 9 // 0) [in] seqno1: sequence number starts. 10 // 1) [in] seqno2: sequence number ends. 11 // Returned value: 12 // number of packets that are not in the list previously. 13 int insert(int32_t seqno1, int32_t seqno2); 14 15 // Functionality: 16 // Remove ALL the seq. no. that are not greater than the parameter. 17 // Parameters: 18 // 0) [in] seqno: sequence number. 19 // Returned value: 20 // None. 21 void remove(int32_t seqno); 22 23 // Functionality: 24 // Read the loss length. 25 // Parameters: 26 // None. 27 // Returned value: 28 // The length of the list. 29 int getLossLength(); 30 31 // Functionality: 32 // Read the first (smallest) loss seq. no. in the list and remove it. 33 // Parameters: 34 // None. 35 // Returned value: 36 // The seq. no. or -1 if the list is empty. 37 int32_t getLostSeq(); 38 39 private: 40 int32_t* m_piData1; // sequence number starts 41 int32_t* m_piData2; // seqnence number ends 42 int* m_piNext; // next node in the list 43 44 int m_iHead; // first node 45 int m_iLength; // loss length 46 int m_iSize; // size of the static array 47 int m_iLastInsertPos; // position of last insert node 48 49 pthread_mutex_t m_ListLock; // used to synchronize list operation 50 51 private: 52 CSndLossList(const CSndLossList&); 53 CSndLossList& operator=(const CSndLossList&); 54};
这是一个不可复制容器。提供的接口不是很多，配合注释，都没有太多难以理解的地方。这是一个用数组实现的链表。接着来看这个class的构造和析构(src/list.cpp)：
1CSndLossList::CSndLossList(int size) 2 : m_piData1(NULL), 3 m_piData2(NULL), 4 m_piNext(NULL), 5 m_iHead(-1), 6 m_iLength(0), 7 m_iSize(size), 8 m_iLastInsertPos(-1), 9 m_ListLock() { 10 m_piData1 = new int32_t[m_iSize]; 11 m_piData2 = new int32_t[m_iSize]; 12 m_piNext = new int[m_iSize]; 13 14 // -1 means there is no data in the node 15 for (int i = 0; i < size; ++i) { 16 m_piData1[i] = -1; 17 m_piData2[i] = -1; 18 } 19 20 // sender list needs mutex protection 21#ifndef WIN32 22 pthread_mutex_init(&m_ListLock, 0); 23#else 24 m_ListLock = CreateMutex(NULL, false, NULL); 25#endif 26} 27 28CSndLossList::~CSndLossList() { 29 delete[] m_piData1; 30 delete[] m_piData2; 31 delete[] m_piNext; 32 33#ifndef WIN32 34 pthread_mutex_destroy(&m_ListLock); 35#else 36 CloseHandle(m_ListLock); 37#endif 38}
CUDT::connect()中创建CSndLossList时，size值为m_iFlowWindowSize * 2，也即8192 × 2 == 16384。如果不用数组，而用常规一点的方法来实现的话，链表的节点定义可能是这样的：
1struct Node { 2 int32_t m_iStart; 3 int32_t m_iEnd; 4 Node *m_pNext; 5};
然后来看这个class最关键的函数之一CSndLossList::insert()的定义：
1int CSndLossList::insert(int32_t seqno1, int32_t seqno2) { 2 CGuard listguard(m_ListLock); 3 4 if (0 == m_iLength) { 5 // insert data into an empty list 6 7 m_iHead = 0; 8 m_piData1[m_iHead] = seqno1; 9 if (seqno2 != seqno1) 10 m_piData2[m_iHead] = seqno2; 11 12 m_piNext[m_iHead] = -1; 13 m_iLastInsertPos = m_iHead; 14 15 m_iLength += CSeqNo::seqlen(seqno1, seqno2); 16 17 return m_iLength; 18 } 19 20 // otherwise find the position where the data can be inserted 21 int origlen = m_iLength; 22 int offset = CSeqNo::seqoff(m_piData1[m_iHead], seqno1); 23 int loc = (m_iHead + offset + m_iSize) % m_iSize; 24 25 if (offset < 0) { 26 // Insert data prior to the head pointer 27 28 m_piData1[loc] = seqno1; 29 if (seqno2 != seqno1) 30 m_piData2[loc] = seqno2; 31 32 // new node becomes head 33 m_piNext[loc] = m_iHead; 34 m_iHead = loc; 35 m_iLastInsertPos = loc; 36 37 m_iLength += CSeqNo::seqlen(seqno1, seqno2); 38 } else if (offset > 0) { 39 if (seqno1 == m_piData1[loc]) { 40 m_iLastInsertPos = loc; 41 42 // first seqno is equivlent, compare the second 43 if (-1 == m_piData2[loc]) { 44 if (seqno2 != seqno1) { 45 m_iLength += CSeqNo::seqlen(seqno1, seqno2) - 1; 46 m_piData2[loc] = seqno2; 47 } 48 } else if (CSeqNo::seqcmp(seqno2, m_piData2[loc]) > 0) { 49 // new seq pair is longer than old pair, e.g., insert [3, 7] to [3, 5], becomes [3, 7] 50 m_iLength += CSeqNo::seqlen(m_piData2[loc], seqno2) - 1; 51 m_piData2[loc] = seqno2; 52 } else 53 // Do nothing if it is already there 54 return 0; 55 } else { 56 // searching the prior node 57 int i; 58 if ((-1 != m_iLastInsertPos) && (CSeqNo::seqcmp(m_piData1[m_iLastInsertPos], seqno1) < 0)) 59 i = m_iLastInsertPos; 60 else 61 i = m_iHead; 62 63 while ((-1 != m_piNext[i]) && (CSeqNo::seqcmp(m_piData1[m_piNext[i]], seqno1) < 0)) 64 i = m_piNext[i]; 65 66 if ((-1 == m_piData2[i]) || (CSeqNo::seqcmp(m_piData2[i], seqno1) < 0)) { 67 m_iLastInsertPos = loc; 68 69 // no overlap, create new node 70 m_piData1[loc] = seqno1; 71 if (seqno2 != seqno1) 72 m_piData2[loc] = seqno2; 73 74 m_piNext[loc] = m_piNext[i]; 75 m_piNext[i] = loc; 76 77 m_iLength += CSeqNo::seqlen(seqno1, seqno2); 78 } else { 79 m_iLastInsertPos = i; 80 81 // overlap, coalesce with prior node, insert(3, 7) to [2, 5], ... becomes [2, 7] 82 if (CSeqNo::seqcmp(m_piData2[i], seqno2) < 0) { 83 m_iLength += CSeqNo::seqlen(m_piData2[i], seqno2) - 1; 84 m_piData2[i] = seqno2; 85 86 loc = i; 87 } else 88 return 0; 89 } 90 } 91 } else { 92 m_iLastInsertPos = m_iHead; 93 94 // insert to head node 95 if (seqno2 != seqno1) { 96 if (-1 == m_piData2[loc]) { 97 m_iLength += CSeqNo::seqlen(seqno1, seqno2) - 1; 98 m_piData2[loc] = seqno2; 99 } else if (CSeqNo::seqcmp(seqno2, m_piData2[loc]) > 0) { 100 m_iLength += CSeqNo::seqlen(m_piData2[loc], seqno2) - 1; 101 m_piData2[loc] = seqno2; 102 } else 103 return 0; 104 } else 105 return 0; 106 } 107 108 // coalesce with next node. E.g., [3, 7], ..., [6, 9] becomes [3, 9] 109 while ((-1 != m_piNext[loc]) && (-1 != m_piData2[loc])) { 110 int i = m_piNext[loc]; 111 112 if (CSeqNo::seqcmp(m_piData1[i], CSeqNo::incseq(m_piData2[loc])) <= 0) { 113 // coalesce if there is overlap 114 if (-1 != m_piData2[i]) { 115 if (CSeqNo::seqcmp(m_piData2[i], m_piData2[loc]) > 0) { 116 if (CSeqNo::seqcmp(m_piData2[loc], m_piData1[i]) >= 0) 117 m_iLength -= CSeqNo::seqlen(m_piData1[i], m_piData2[loc]); 118 119 m_piData2[loc] = m_piData2[i]; 120 } else 121 m_iLength -= CSeqNo::seqlen(m_piData1[i], m_piData2[i]); 122 } else { 123 if (m_piData1[i] == CSeqNo::incseq(m_piData2[loc])) 124 m_piData2[loc] = m_piData1[i]; 125 else 126 m_iLength--; 127 } 128 129 m_piData1[i] = -1; 130 m_piData2[i] = -1; 131 m_piNext[loc] = m_piNext[i]; 132 } else 133 break; 134 } 135 136 return m_iLength - origlen; 137}
1. 这个函数首先处理了最简单的向空链表中插入元素的case。
这种情况下，m_iHead被赋予0值。m_piData1[m_iHead]会被赋值为要插入的这段丢失packet范围的起始SeqNo。
如果起始SeqNo和结束SeqNo的值不同，m_piData2[m_iHead]还会被赋值为结束SeqNo；如果相同，则m_piData2[m_iHead]将仍然保持构造函数中初始化的-1，以表示这段丢失packet范围只有一个元素。
m_piNext[m_iHead]被赋值为-1以表示这是链表中的最后一个元素。m_iLastInsertPos用来记录上一次插入的位置，这里会被赋值为m_iHead。m_iLength表示CSndLossList中记录的丢失packet的总格数，这里会被设置为这段packet的长度。然后返回m_iLength。
可见m_iHead指向链表的头部。m_piData1，m_piData2和m_piNext这三个数组中相同位置的元素共同表示一个链表节点，它们分别表示一个丢失packet范围的起始SeqNo，结束SeqNo和该节点在链表中next节点的位置。
2. 链表中已经有元素了，则将m_iLength保存在origlen中。计算要插入的这段丢失packet的起始SeqNo与链表中原有的头节点的起始SeqNo字段的差值offset。然后计算要插入的这段丢失packet范围的的可能的位置loc，这个可能的位置主要由这段丢失packet范围的起始SeqNo与链表中原有的头节点的起始SeqNo字段的差值决定。
由loc的计算方法可见，数组中的空间是被循环利用的。比如要插入的节点是向CSndLossList中插入的第二个节点，则此时m_iHead仍然为0，而要插入的这个丢失packet范围的起始位置小于原有的头节点的起始SeqNo字段，则新插入的节点将被绕回到数组的尾部。
3. 处理offset小于0的情况。这表示插入的这个丢失packet范围的起始位置小于原有的头节点的起始SeqNo字段值，此时则会在loc位置插入一个新的节点以描述这段丢失packet范围。更新m_iHead和m_iLastInsertPos指向新插入的这个节点。并更新m_iLength以体现新加入的这个丢失packet范围。
向单向链表的头部插入元素总是比较简单。由此我们也看到，这个链表是以节点的起始SeqNo字段值的升序排列的有序链表。
但这个地方貌似没有处理新插入的这个丢失packet范围与原有头节点表示的丢失packet范围存在交叉的情况？没错，是没有处理，这种情况会在处理完所有的插入情况之后再统一来做。
4. 处理offset大于0的情况。这又分为两种情况：
(1). seqno1 == m_piData1[loc]，表明新节点的目标插入位置中原有节点保存的丢失Packet范围的起始SeqNo与要插入的这个丢失Packets范围的起始SeqNo相同。则此时会首先更新m_iLastInsertPos为loc，还需要处理这样的几种case，
case 1：原有的范围中只有一个元素，要插入的这个范围有多个元素。
case 2：原有的范围中有多个元素，要插入的这个范围有一个元素。
case 3：原有的范围和要插入的范围都只有一个元素。
case 4：原有的范围和要插入的范围中都有多个元素，但新插入的范围完全包含原有的范围。
case 5：原有的范围和要插入的范围中都有多个元素，但原有的范围完全包含新插入的范围。
case 6：原有的范围和要插入的范围中都有多个元素，且完全相同。
这些case包含的packet范围的相对关系可以用下图来简单表示：
代码的具体写法不同，这些case中的一些可能会以不同的方式被合并成一个处理，而有些case则不需要对原有的链表进行任何的调整。
if block中处理的是case1和case3，else-if block中处理的是case 4，else block中处理的是case 2，case 5和case 6。其中case 3，case 2，case 5和case 6都不需要对链表做出调整。
以此来看，在第一个if block的内部，应该再加一个else block来直接返回0会比较好一点。
那段代码的一种等价实现形式：
1if (seqno2 != seqno1) { 2 if (-1 == m_piData2[loc]) { 3 m_iLength += CSeqNo::seqlen(seqno1, seqno2) - 1; 4 m_piData2[loc] = seqno2; 5 } else if (CSeqNo::seqcmp(seqno2, m_piData2[loc]) > 0) { 6 // new seq pair is longer than old pair, e.g., insert [3, 7] to [3, 5], becomes [3, 7] 7 m_iLength += CSeqNo::seqlen(m_piData2[loc], seqno2) - 1; 8 m_piData2[loc] = seqno2; 9 } else { 10 return 0; 11 } 12 } else { 13 // Do nothing if it is already there 14 return 0; 15 }
(2). seqno1与m_piData1[loc]不相等。这其实主要有两种可能，一是loc位置已经有了其它的节点，但该节点所表示的范围的起始SeqNo与要插入的这个范围的起始SeqNo不同；二是loc位置还没有被插入节点。但第一种可能应该是不会出现的，因而这里实际要处理的也就是loc位置还没有节点插入的情况。
对于这种情况，节点的插入位置完全不是问题，关键的问题是调整链表中一些节点的关系。可以看到这里的处理过程：
查找新插入节点前面的那个节点。该查找过程的开始位置由m_piData1[m_iLastInsertPos]与seqno1的相对大小决定，如果前者较小，则从m_iLastInsertPos开始，否则，从m_iHead开始。这大概主要是想要利用空间局部性原理来提高查找的效率。然后就是通过一个循环找到新插入节点前面的那个节点。
找到的这前面的节点所表示的丢失packet范围与要插入的节点所要表示的范围之间的关系又有这样的几种case：
case 1：前面的节点表示的范围只有一个packet。
case 2：前面的节点表示的范围含有多个packet，但它的结束SeqNo仍然小于要插入的范围的起始SeqNo。
case 3：前面的节点表示的范围含有多个packet，但它的结束SeqNo大于等于要插入的范围的起始SeqNo。
前两个case表明两个范围不相交，而case 3则表明两个范围是相交的。对于前两个case，则在前面的那个节点之后插入一个节点，链表中节点的连接关系做适当的调整即可。对于case 3，则需要将插入的这个范围合并入前面的那个节点。如果前面的那个节点包含的范围完全覆盖了要插入的范围，则什麽都不做，如果不是则需要对结束SeqNo字段做一些调整。
5. offset值等于0，表明要插入的这个范围的起始SeqNo与Head节点表示的范围的起始SeqNo相同，这个过程则与offset大于0时，seqno1 == m_piData1[loc]中的处理基本一致。
6. 从插入新节点的位置开始，合并链表中与新插入的这个丢失packet范围相交，或被包含或紧紧相邻的节点。
7. 返回新加入CSndLossList的丢失packet的总个数。
有这个函数的整个执行过程不难看出，头节点中将包含最老的丢失packets。
看完了插入，自然不能不再来看一下CSndLossList::remove()：
1void CSndLossList::remove(int32_t seqno) { 2 CGuard listguard(m_ListLock); 3 4 if (0 == m_iLength) 5 return; 6 7 // Remove all from the head pointer to a node with a larger seq. no. or the list is empty 8 int offset = CSeqNo::seqoff(m_piData1[m_iHead], seqno); 9 int loc = (m_iHead + offset + m_iSize) % m_iSize; 10 11 if (0 == offset) { 12 // It is the head. Remove the head and point to the next node 13 loc = (loc + 1) % m_iSize; 14 15 if (-1 == m_piData2[m_iHead]) 16 loc = m_piNext[m_iHead]; 17 else { 18 m_piData1[loc] = CSeqNo::incseq(seqno); 19 if (CSeqNo::seqcmp(m_piData2[m_iHead], CSeqNo::incseq(seqno)) > 0) 20 m_piData2[loc] = m_piData2[m_iHead]; 21 22 m_piData2[m_iHead] = -1; 23 24 m_piNext[loc] = m_piNext[m_iHead]; 25 } 26 27 m_piData1[m_iHead] = -1; 28 29 if (m_iLastInsertPos == m_iHead) 30 m_iLastInsertPos = -1; 31 32 m_iHead = loc; 33 34 m_iLength--; 35 } else if (offset > 0) { 36 int h = m_iHead; 37 38 if (seqno == m_piData1[loc]) { 39 // target node is not empty, remove part/all of the seqno in the node. 40 int temp = loc; 41 loc = (loc + 1) % m_iSize; 42 43 if (-1 == m_piData2[temp]) 44 m_iHead = m_piNext[temp]; 45 else { 46 // remove part, e.g., [3, 7] becomes [], [4, 7] after remove(3) 47 m_piData1[loc] = CSeqNo::incseq(seqno); 48 if (CSeqNo::seqcmp(m_piData2[temp], m_piData1[loc]) > 0) 49 m_piData2[loc] = m_piData2[temp]; 50 m_iHead = loc; 51 m_piNext[loc] = m_piNext[temp]; 52 m_piNext[temp] = loc; 53 m_piData2[temp] = -1; 54 } 55 } else { 56 // target node is empty, check prior node 57 int i = m_iHead; 58 while ((-1 != m_piNext[i]) && (CSeqNo::seqcmp(m_piData1[m_piNext[i]], seqno) < 0)) 59 i = m_piNext[i]; 60 61 loc = (loc + 1) % m_iSize; 62 63 if (-1 == m_piData2[i]) 64 m_iHead = m_piNext[i]; 65 else if (CSeqNo::seqcmp(m_piData2[i], seqno) > 0) { 66 // remove part/all seqno in the prior node 67 m_piData1[loc] = CSeqNo::incseq(seqno); 68 if (CSeqNo::seqcmp(m_piData2[i], m_piData1[loc]) > 0) 69 m_piData2[loc] = m_piData2[i]; 70 71 m_piData2[i] = seqno; 72 73 m_piNext[loc] = m_piNext[i]; 74 m_piNext[i] = loc; 75 76 m_iHead = loc; 77 } else 78 m_iHead = m_piNext[i]; 79 } 80 81 // Remove all nodes prior to the new head 82 while (h != m_iHead) { 83 if (m_piData2[h] != -1) { 84 m_iLength -= CSeqNo::seqlen(m_piData1[h], m_piData2[h]); 85 m_piData2[h] = -1; 86 } else 87 m_iLength--; 88 89 m_piData1[h] = -1; 90 91 if (m_iLastInsertPos == h) 92 m_iLastInsertPos = -1; 93 94 h = m_piNext[h]; 95 } 96 } 97}
先来回忆下CSndLossList的类定义中，对于这个函数的语义的说明：移除所有不大于参数值的SeqNo。这个函数的主要执行过程如下：
1. 检查m_iLength是否为0，若为0，说明CSndLossList还没有加入任何SeqNo，则直接返回，否则继续执行。
2. 计算头节点所表示的丢失packet范围的起始SeqNo与参数seqno的offset，及可能以seqno作为起始SeqNo字段的节点的位置loc。
根据这个函数的语义，我们知道，其实是不需要处理offset小于的case的。如我们前面所了解的，头节点所表示的SeqNo范围是CSndLossList中SeqNo值最小的一个范围，而如果seqno小于这个范围的起始SeqNo的话，则说明不大于seqno的所有SeqNo都已经不存在了。
3. 处理offset == 0的情况。offset == 0，表明seqno是包含于头节点所表示的范围，而且还是这个范围的起始SeqNo。此时又主要分两种情况来处理：
(1). 头节点表示的这个范围只有一个SeqNo。
(2). 头节点表示的范围包含多个SeqNo。
对于情况(1)，则头节点将向后滑动一个节点，原来头节点的存放位置会被复位。对于情况(2)，为了保证两个节点的相对位置等于节点所表示的丢失packet范围的起始SeqNo的差值这样的一种节点间关系依然成立，需要将头节点保存的位置后移一个位置。对于情况(2)，还会再分为两种情况来处理，一是原来的头节点中只包含2个SeqNo，则在移除seqno后只剩下了一个，此时要保持m_piData2[loc]为-1，若包含3个及以上SeqNo的，则要复制原来的头节点的结束SeqNo到新的位置。
其它就是适当地更新m_iLastInsertPos，m_iHead和m_iLength了。这里似乎补一个
m_piNext[m_iHead] = -1;
要更好一点。
4. 处理offset大于0的情况。对于这种情况，比较麻烦的是找到seqno具体包含在哪个节点中。处理过程大致为：
(1). 检查一下，seqno与m_piData1[loc]是否相等，若相等，则要找的节点已经是找到了，且seqno为目标节点表示的丢失packet范围的起始seqno。此时则会再分为两种情况来处理，一是目标节点中只包含一个SeqNo，则使链表头指向目标节点的下一个节点。
二是目标节点中包含多个SeqNo，则需要将seqno排除在目标节点范围之外新建一个节点，将新节点保存在目标节点后面相邻的位置，若目标节点中包含2个节点，则需要设置新节点的结束SeqNo字段为-1，若大于等于3，则复制此字段的值，然后将原来的目标节点改造为只包含seqno的节点，并使它指向新建的这个节点。总之就是将原来的一个节点拆分成了两个节点，一个节点只包含seqno，另一个则包含原来的目标节点中其余的SeqNo。
(2). seqno与m_piData1[loc]不相等的情况，则需要先找到起始SeqNo字段小于seqno的SeqNo值最大的那个节点。这又可以分为3种case来处理，
case 1：找到的节点只包含一个SeqNo，此时则使链表头指向找到的节点的next节点。
case 2：找到的节点包含多个SeqNo，且seqno小于找到的节点的结束SeqNo字段，此时则需要将找到的节点裂为链表中的两个节点，一个包含的范围为[原节点的起始SeqNo，seqno]，另一个包含的范围为[seqno + 1, 原节点的结束SeqNo]。同时链表头应该指向后者。
case 3：找到的节点包含多个SeqNo，且seqno大于等于找到的节点的结束SeqNo字段，此时则同样使链表头指向找到的节点的next节点。
5. 移除新找到的头节点之前所有的节点。适当地更新m_iLength等。
这个地方移除的操作看起来好罗嗦。必须要计算出offset值，而不是简单的用比较符号，是由SeqNo的递增规则决定的。但对于offset大于等于0的情况，则可以使用统一的过程来处理：找到起始SeqNo字段不大于seqno的 SeqNo值最大的那个节点，然后根据seqno与这个节点描述的范围的4种关系，即seqno等于找到的节点的起始SeqNo值，seqno大于起始SeqNo值但小于结束SeqNo值，seqno等于结束SeqNo值，seqno大于结束SeqNo值，及找到的节点所描述的范围的大小，来分类处理即可。
还有我们前面在CUDT::packData()中看到的CSndLossList::getLostSeq()：
1int32_t CSndLossList::getLostSeq() { 2 if (0 == m_iLength) 3 return -1; 4 5 CGuard listguard(m_ListLock); 6 7 if (0 == m_iLength) 8 return -1; 9 10 if (m_iLastInsertPos == m_iHead) 11 m_iLastInsertPos = -1; 12 13 // return the first loss seq. no. 14 int32_t seqno = m_piData1[m_iHead]; 15 16 // head moves to the next node 17 if (-1 == m_piData2[m_iHead]) { 18 //[3, -1] becomes [], and head moves to next node in the list 19 m_piData1[m_iHead] = -1; 20 m_iHead = m_piNext[m_iHead]; 21 } else { 22 // shift to next node, e.g., [3, 7] becomes [], [4, 7] 23 int loc = (m_iHead + 1) % m_iSize; 24 25 m_piData1[loc] = CSeqNo::incseq(seqno); 26 if (CSeqNo::seqcmp(m_piData2[m_iHead], m_piData1[loc]) > 0) 27 m_piData2[loc] = m_piData2[m_iHead]; 28 29 m_piData1[m_iHead] = -1; 30 m_piData2[m_iHead] = -1; 31 32 m_piNext[loc] = m_piNext[m_iHead]; 33 m_iHead = loc; 34 } 35 36 m_iLength--; 37 38 return seqno; 39}
这个函数读取首个丢失packet的SeqNo。
这个函数会取链表头节点中最小的SeqNo，返回给调用者，然后将这个SeqNo从链表头节点中移除。移除的时候又可以分为2种情况：1. 头节点描述的packet范围只包含一个SeqNo，2. 包含多个SeqNo。
对于情况1，则将链表头节点向后移动一个节点，然后移除原来的头节点。对于情况2，则将原来的头节点分裂为两个节点，一个只包含首个丢失packet的SeqNo，另一个包含原来头节点中其余的SeqNo，令链表头节点指向后一个节点，并移除前一个节点。
可见，通过CSndLossList::getLostSeq()返回给调用者的Packet是会被从CSndLossList中移除出去的。
最后可以再来看一下，经过了这些操作的蹂躏之后，这个链表可能的样子。比如有4段丢失的packet，其SeqNo范围及被插入的顺序为[8, 9]，[3, 5]，[12，12]，[15, 19]，假设缓冲区大小为20，则看起来可能为：
UDT中，丢失packet列表大体如此。
Done。