[發明專利]遍歷樹表表項的方法及裝置

無效

• 申請號: 200710123961.1
• 申請日: 2007-10-16
• 公開（公告）號: CN101146038A
• 公開（公告）日: 2008-03-19
• 發明（設計）人: 於少峰
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/46
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種網絡處理器遍歷樹表表項的方法，其特征在于，包括以下步驟：

(1)查詢預先建立的樹表的樹表表項映射表，從該樹表表項映射表中獲取有效樹表表項的地址；

(2)根據所獲取的有效樹表表項的地址，處理所述樹表中對應該地址的有效樹表表項。

2.根據權利要求1所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述樹表表項映射表中與所述樹表的樹表表項一一對應設置標志位，各標志位標識其對應的樹表表項是否有效；所述網絡處理器通過標識其對應樹表表項有效的標志位在所述樹表表項映射表中的位置獲取該對應有效樹表表項的地址。

3.根據權利要求2所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述樹表表項映射表的標志位與所述樹表的樹表表項一一對應、依次設置，其中每一標志位在所述樹表表項映射表中的偏移與其對應樹表表項在所述樹表中的偏移相同；所述網絡處理器根據標識其對應樹表表項有效的標志位在所述樹表表項映射表中的偏移和所述樹表的表項基址得到該對應有效樹表表項的地址。

4.根據權利要求3所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述步驟(1)包括：

查詢所述樹表表項映射表，判斷該映射表中當前標志位標識其對應樹表表項是否為有效；

在判斷得知當前標志位標識其對應樹表表項有效時，根據該標志位在所述樹表表項映射表中的偏移與所述樹表的表項基址之和得到對應有效樹表表項的地址；

所述方法進一步在步驟(2)之后包括：

(3)判斷所述樹表表項映射表是否查詢完畢，如尚未查詢完畢，則返回步驟(1)，繼續查詢樹表表項映射表中下一個標志位；如映射表已查詢完畢，則結束遍歷。

5.根據權利要求2、3或4所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述網絡處理器在添加或刪除樹表表項時，對應修改該樹表表項對應的所述樹表表項映射表中的標志位。

6.根據權利要求1-4中任一所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述樹表表項映射表存放于所述網絡處理器的高速內存中。

7.根據權利要求1-4中任一所述的網絡處理器遍歷樹表表項的方法，其特征在于，所述樹表表項為虛擬專用局域網業務的介質訪問控制表項。

8.一種遍歷樹表表項的裝置，其特征在于，包括：

存儲裝置，存儲樹表及該樹表的樹表表項映射表；

查詢獲取裝置，查詢所述存儲裝置中存儲的樹表的樹表表項映射表，從該樹表表項映射表中獲取有效樹表表項的地址；

處理裝置，根據所獲取的有效樹表表項的地址，處理所述樹表中對應該地址的有效樹表表項。

9.根據權利要求8所述的遍歷樹表表項的裝置，其特征在于，所述樹表表項映射表中與所述樹表的樹表表項一一對應設置標志位，各標志位標識其對應的樹表表項是否有效；所述查詢獲取裝置通過標識其對應樹表表項有效的標志位在所述樹表表項映射表中的位置獲取該對應有效樹表表項的地址。

10.根據權利要求9所述的遍歷樹表表項的裝置，其特征在于，所述樹表表項映射表的標志位與所述樹表的樹表表項一一對應、依次設置，其中每一標志位在所述樹表表項映射表中的偏移與其對應樹表表項在所述樹表中的偏移相同；所述查詢獲取裝置根據標識其對應樹表表項有效的標志位在所述樹表表項映射表中的偏移和所述樹表的表項基址得到該對應有效樹表表項的地址。

11.根據權利要求10所述的遍歷樹表表項的裝置，其特征在于，所述查詢獲取裝置包括：

判斷單元，判斷所查詢的樹表表項映射表中當前標志位標識其對應樹表表項是否為有效；

獲取單元，在所述判斷單元判斷得知當前標志位標識其對應樹表表項有效時，根據該標志位在所述樹表表項映射表中的偏移與所述樹表的表項基址之和得到對應有效樹表表項的地址；

所述的遍歷樹表表項的裝置進一步包括：

判斷指示裝置，判斷所述樹表表項映射表是否查詢完畢，在判斷結果為已查詢完畢時，指示所述查詢獲取裝置結束查詢；否則，指示查詢獲取裝置繼續查詢。

12.根據權利要求9、10或11所述的遍歷樹表表項的裝置，其特征在于，所述處理裝置添加或刪除所述樹表中樹表表項時，對應修改所述存儲裝置中存儲的該樹表表項對應的所述樹表表項映射表中的標志位。