[發明專利]一種大容量查找表快速排序和查找裝置及其實現方法

有效

• 申請號: 201210090784.2
• 申請日: 2012-03-30
• 公開（公告）號: CN102663061A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 張靜;趙書鵬
• 申請（專利權）人: UT斯達康通訊有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 楊天嬌

1.一種大容量查找表快速排序和查找裝置，根據CPU指令對大容量查找表進行快速排序和搜索，其特征在于，所述裝置包括標簽查找模塊，排序模塊，預排序模塊和控制模塊，所述的排序模塊分別與預排序模塊，控制模塊以及查找表相連，所述的標簽查找模塊與排序模塊和查找表相連；

其中所述的預排序模塊接收CPU配置數據，對CPU配置數據進行預排序，維護一個預排序表；

所述控制模塊，根據接收到的CPU指令，控制排序模塊進行排序操作；

所述排序模塊包括添加排序模塊和刪除排序模塊，其中添加排序模塊根據控制模塊指令對查找表進行插入排序，刪除排序模塊根據控制模塊指令對查找表進行刪除排序；

所述標簽查找模塊，用于收到查找請求后發起查找申請并進行查找，輸出查找結果和查找完成信號。

2.如權利要求1所述的大容量查找表快速排序和查找裝置，其特征在于，包括冗余檢查模塊，所述冗余檢查模塊與所述控制模塊和查找表相連，用于對預排序表和查找表進行冗余檢查，若檢查到冗余則向CPU發出中斷請求。

3.如權利要求1所述的大容量查找表快速排序和查找裝置，其特征在于，所述標簽查找模塊收到查找請求后，向所述排序模塊發出查找申請，收到同意查找信號后，進行標簽查找，并輸出查找結果；查找結束發出查找完成信號給所述排序模塊。

4.如權利要求3所述的大容量查找表快速排序和查找裝置，其特征在于，所述排序模塊收到查找申請后，若排序模塊正在進行排序操作，則中斷當前排序操作，并發出查找同意信號；當檢測到查找完成信號有效后，繼續之前被中斷的操作；如果排序模塊在收到查找請求時，沒有進行排序操作，則直接發出查找同意信號。

5.一種大容量查找表快速排序和查找方法，其特征在于，包括步驟：

步驟1、對CPU配置數據進行預排序；

步驟2、收到數據排序指令后，對查找表中數據進行排序；

步驟3、收到查找請求，查找模塊向排序模塊發出查找申請，排序模塊收到查找申請后，若排序模塊正在進行排序操作，中斷當前排序操作，并發出查找同意信號；如果排序模塊在收到查找請求時，沒有進行排序操作，則直接發出查找同意信號；

步驟4、進行標簽查找；

步驟5、輸出查找結果和查找完成信號。

6.如權利要求5所述的大容量查找表快速排序和查找方法，其特征在于，如果是添加數據排序，所述的步驟2包括：

步驟2.1.1、則首先在查找表尾部拓展一段無效區間，其長度與待插入數據個數相同；

步驟2.1.2、將預排序表中最大數據標簽和查找表中最大數據標簽進行比較，若預排序表數據標簽較大，則將該數據插入無效區間最后一個地址，無效區間長度減1；若查找表數據較大，則將該數據插入無效區間最后一個地址，并將該數據原地址置為無效，無效區間長度不變，位置向地址小的方向移一個地址；

步驟2.1.3、將預排序表中剩余最大數據標簽和查找表中未參與比較的最大數據標簽進行比較，若預排序表數據標簽較大，則將該數據插入無效區間最后一個地址，無效區間長度減1；若查找表數據較大，則將該數據插入無效區間最后一個地址，并將該數據原地址置為無效，無效區間長度不變，位置向地址小的方向移一個地址；直到預排序表中數據全部插入查找表為止，此時無效區長度為0，插入排序結束。

7.如權利要求5所述的大容量查找表快速排序和查找方法，其特征在于，如果是刪除數據排序，所述的步驟2包括：

步驟2.2.1、若預排序表中最小數據標簽，與查找表中最小數據標簽相等，則將查找表該數據原地址置為無效；

步驟2.2.2、若預排序表中最小數據標簽，小于查找表中最小數據標簽，表示待刪除的標簽不存在，無需操作；

步驟2.2.3、若預排序表數據標簽大于查找表中數據標簽，則將查找表中該數據插入無效區間中第一個地址處，并將該數據原地址置為無效；

步驟2.2.4、若預排序表中剩余最小數據標簽，與查找表中未參與過比較的最小數據標簽相等，則將查找表該數據原地址置為無效；若預排序表中剩余最小數據標簽，小于查找表中最小數據標簽，表示待刪除的標簽不存在，無需操作；若預排序表數據標簽大于查找表中數據標簽，則將查找表中該數據插入無效區間中第一個地址處，并將該數據原地址置為無效；直到預排序表中數據全部從查找表中刪除為止，刪除排序結束。