[發明專利]一種地址查找、關鍵字存儲方法及設備

有效

• 申請號: 201710571150.1
• 申請日: 2017-07-13
• 公開（公告）號: CN107506310B
• 公開（公告）日: 2020-04-24
• 發明（設計）人: 秦增杰
• 申請（專利權）人: 北京東土軍悅科技有限公司;北京物芯科技有限責任公司
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 黃志華

1.一種地址查找方法，其特征在于，包括：

獲取待查找關鍵字，并確定所述待查找關鍵字的位寬；

根據TCAM的單位存儲單元的位寬和所述待查找關鍵字的位寬，確定存儲所述待查找關鍵字所需的單位存儲單元的數量2^N；其中，2^N為存儲所述待查找關鍵字所需的單位存儲單元的最小數量；所述TCAM中包括至少一個單位存儲單元，所述單位存儲單元的位寬不大于存儲的位寬最小的關鍵字的位寬；N為大于或等于零的整數；

將所述待查找關鍵字劃分成2^N個子關鍵字，并在所述2^N個子關鍵字中的每個子關鍵字中增加位寬標識，所述位寬標識用于指示所述待查找關鍵字的位寬；

將所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字進行匹配；其中，所述2^N個增加了位寬標識的子關鍵字分別與存儲在不同的且地址連續的單位存儲單元的關鍵字進行匹配；所述TCAM中存儲的關鍵字攜帶有指示所述存儲的關鍵字的位寬的位寬標識，當所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字的位寬標識相同時能夠匹配成功；

根據所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字的匹配結果，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址；

其中，所述TCAM中包括M個TCAM塊，M為大于零的整數，每個TCAM塊包括至少一個單位存儲單元，則將所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字進行匹配，包括：

當N為零時，則將所述2^N個增加了位寬標識的子關鍵字與所述TCAM中每一個單位存儲單元存儲的關鍵字進行匹配；或者，

當N不為零時，則將所述2^N個增加了位寬標識的子關鍵字中第X個子關鍵字與所述TCAM中編號為(2^NP+X)的TCAM塊包括的單位存儲單元存儲的關鍵字進行匹配；其中，X為不小于1且不大于2^N的整數，P的取值包括滿足大于或者等于零且小于或者等于(M/2^N)-1的整數中的所有值；所述TCAM中的TCAM塊按照順序從1開始進行編號。

2.如權利要求1所述的方法，其特征在于，所述根據所述2^N個增加了位寬標識的子關鍵字與所述TCAM中存儲的關鍵字的匹配結果，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址，包括：

根據所述匹配結果生成匹配狀態表；其中，所述匹配狀態表中的一列對應一個TCAM塊的每個單位存儲單元；當所述2^N個增加了位寬標識的子關鍵字中其中一個子關鍵字與對應的單位存儲單元存儲的關鍵字匹配成功，則將匹配成功的單位存儲單元的匹配狀態置為1，否則置為零；

當N為零時，則根據所述匹配狀態表中匹配狀態為1的單位存儲單元的地址，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址；或者，

當N不為零時，則將編號為(2^NP+1)至編號(2^NP+2^N)的每個TCAM塊中的地址相同的所有單位存儲單元的匹配狀態進行與運算，得到與運算后的匹配狀態表；其中，相互進行與運算的TCAM塊的P值相同；若與運算結果為1，則將相互進行與運算的單位存儲單元中處于編號為(2^NP+1)的TCAM塊的單位存儲單元的匹配狀態置為1，其余單位存儲單元的匹配狀態置為零；或者，若與運算結果為零，則將相互進行與運算的單位存儲單元的匹配狀態都置為零；

根據所述運算后的匹配狀態表中匹配狀態為1的單位存儲單元的地址，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址。

3.如權利要求2所述的方法，其特征在于，根據所述匹配狀態表中匹配狀態為1的單位存儲單元的地址，確定所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址，包括：

若所述匹配狀態表中匹配狀態為1的單位存儲單元有多個，則確定所述匹配狀態表中匹配狀態為1的單位存儲單元中優先級最高的單位存儲單元的地址；

將所述優先級最高的單位存儲單元的地址確定為所述TCAM中與所述待查找關鍵字相匹配的關鍵字的地址。