The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 26, 2009
Filed:
Sep. 30, 2008
Jun Liang, Shenzhen, CN;
Shijun Shen, Shenzhen, CN;
Meng LI, Shenzhen, CN;
Juan Zhang, Shenzhen, CN;
Rui HU, Shenzhen, CN;
Jun Gong, Shenzhen, CN;
Jun Liang, Shenzhen, CN;
Shijun Shen, Shenzhen, CN;
Meng Li, Shenzhen, CN;
Juan Zhang, Shenzhen, CN;
Rui Hu, Shenzhen, CN;
Jun Gong, Shenzhen, CN;
Huawei Technologies Co., Ltd., Shenzhen, Guangdong, CN;
Abstract
The present invention discloses a method and apparatus for longest prefix matching. The method includes (A) reading a current-level trie node (TNODE) in the trie, (B) determining whether an offset field of the TNODE indicates that a matched prefix exists in an upper level node and, if so, adding the offset field of the TNODE to a pointer that points to a leaf array in the upper level node, updating a current best match pointer with the computation result and executing block (C), otherwise, executing block (C), (C) determining whether the TNODE has a child node according to a child bitmap, when it is determined that a branch flag of the TNODE matches a corresponding bit of a search keyword, and (D) when it is determined that the TNODE has no child node, reading the internal bitmap of the TNODE, computing a longest matched prefix in the TNODE according to the internal bitmap and a pointer that points to a leaf array in the TNODE, updating the current best match pointer with the computation result, and computing an address of a leaf node (LNODE) associated with the current best match pointer.