[發(fā)明專利]快速串行接口PCI?E協(xié)議數(shù)據(jù)完成包的重組排序方法

有效

• 申請?zhí)枺?/td>: 201210051147.4
• 申請日: 2012-03-01
• 公開（公告）號: CN102571609B
• 公開（公告）日: 2018-04-17
• 發(fā)明（設(shè)計）人: 梁燕;王曉嬌;邵凱;李志寬;段文亮;舒明華
• 申請（專利權(quán)）人: 重慶中天重郵通信技術(shù)有限公司
• 主分類號: H04L12/861
• 分類號: H04L12/861;H04L12/879;H04L12/883
• 代理公司: 重慶輝騰律師事務(wù)所50215
• 代理人: 寸南華

1.一種快速串行接口PCI-E協(xié)議數(shù)據(jù)完成包的重組排序方法，其特征在于：請求者在存儲器中定義一個數(shù)據(jù)緩沖區(qū)，并將其分為二個或二個以上大小相同的數(shù)據(jù)緩沖單元，數(shù)據(jù)緩沖單元大小為128字節(jié)，數(shù)據(jù)緩沖區(qū)大小不超過8K字節(jié)，每個數(shù)據(jù)緩沖單元順序?qū)?yīng)一個索引號且只存放一個數(shù)據(jù)完成包CplD；請求者將接收到的本次非轉(zhuǎn)發(fā)型的存儲器讀請求事務(wù)MRd請求所返回的CplD依次存入數(shù)據(jù)緩沖單元；同時，依據(jù)CplD頭標(biāo)Tag域中的值，即Tag值，按照Tag值從小到大的方式對數(shù)據(jù)緩沖區(qū)內(nèi)的CplD進行排序；并且，定義一個鏈表管理結(jié)構(gòu)用于保存CplD的排序結(jié)果，并在排序過程中動態(tài)建立和更新；在讀取數(shù)據(jù)緩沖區(qū)內(nèi)的CplD時，依據(jù)鏈表的排序指示順序讀取CplD；其中，請求者接收到CplD后分別存入數(shù)據(jù)緩沖單元，同時，依據(jù)CplD頭標(biāo)Tag域中的值，即Tag值，按照Tag值從小到大的方式對數(shù)據(jù)緩沖區(qū)內(nèi)的CplD進行排序；并且，定義一個鏈表管理結(jié)構(gòu)用于保存CplD的排序結(jié)果，并在排序過程中動態(tài)建立和更新；包括以下步驟：

①建立鏈表表頭，用于保存每一次排序后的數(shù)據(jù)序列中第一個CplD的所在數(shù)據(jù)緩沖單元的索引號；

②建立第一個結(jié)點，在其數(shù)據(jù)域中存儲第一個數(shù)據(jù)緩沖單元中CplD的Tag值，并將第一個數(shù)據(jù)緩沖單元的索引號寫入表頭；

③從第二個數(shù)據(jù)緩沖單元開始，依次提取其存儲的CplD的Tag值，并與當(dāng)前鏈表中已有結(jié)點的數(shù)據(jù)域的值進行比較，找到插入新結(jié)點的位置；新結(jié)點的數(shù)據(jù)域存儲此次進行排序的CplD的Tag值，指針域則根據(jù)下述三種不同插入位置進行相應(yīng)更新：

A.新結(jié)點插入當(dāng)前鏈表的第一個結(jié)點前

新結(jié)點成為新鏈表的第一個結(jié)點，其指針域保存插入前鏈表第一個結(jié)點的索引號，同時更新表頭信息，存儲新結(jié)點代表的CplD所在數(shù)據(jù)緩沖單元索引號；

B.新結(jié)點插入當(dāng)前鏈表的最后一個結(jié)點后

新結(jié)點成為新鏈表的最后一個結(jié)點，則其指針域待定，前一個結(jié)點的指針域更新為該新結(jié)點代表的CplD所在數(shù)據(jù)緩沖單元索引號；

C.新結(jié)點插入當(dāng)前鏈表的兩個連續(xù)結(jié)點之間

如果新結(jié)點在兩個連續(xù)結(jié)點之間插入，則更新新結(jié)點前一個結(jié)點的指針域指示為新結(jié)點代表的CplD所在數(shù)據(jù)緩沖單元索引號，同時也更新新結(jié)點的指針域，使其存儲后一個CplD所在數(shù)據(jù)緩沖單元的索引號；

④當(dāng)數(shù)據(jù)緩沖區(qū)內(nèi)暫存的所有CplD都已排序后，最終鏈表每個結(jié)點的數(shù)據(jù)域中存放的Tag值依次遞增1，鏈表最后一個結(jié)點的指針域置為空；

⑤根據(jù)鏈表的各結(jié)點指針域所指示的下一個CplD所在數(shù)據(jù)緩沖單元的索引號順序，將在數(shù)據(jù)緩沖區(qū)內(nèi)不連續(xù)的CplD序列進行排序重組。

2.根據(jù)權(quán)利要求1所述串行接口PCI-E協(xié)議數(shù)據(jù)完成包的重組排序方法，其特征在于：定義一個鏈表管理結(jié)構(gòu)用于保存CplD的排序結(jié)果，并在排序過程中動態(tài)建立和更新，包括，鏈表表頭指示當(dāng)前排序后的CplD序列中第一個CplD所在的數(shù)據(jù)緩沖單元索引號；每個結(jié)點分為數(shù)據(jù)域和指針域，數(shù)據(jù)域存儲本結(jié)點所代表的CplD的Tag值，指針域存儲下一個CplD所在的數(shù)據(jù)緩沖單元索引號；最后一個結(jié)點的指針域為空，表示已到達(dá)鏈表尾部。

3.根據(jù)權(quán)利要求1所述串行接口PCI-E協(xié)議數(shù)據(jù)完成包的重組排序方法，其特征在于：依次提取其存儲的CplD的Tag值，并與當(dāng)前鏈表中已有結(jié)點的數(shù)據(jù)域的值進行比較，包括從鏈表的尾部開始進行比較，即將存儲的CplD的Tag值依次與當(dāng)前鏈表中已有結(jié)點的數(shù)據(jù)域的值依次進行比較。