Patent ID: 7539153

Claim:
A method for longest prefix matching based on a trie, wherein the trie represents multiple prefixes with a prefix distinguished by at least one step and each step indicated by one node, the method comprising the steps of: (A) reading a current-level trie node (TNODE) from a memory in the trie by a search engine; (B) determining whether an offset field of the TNODE indicates that a matched prefix exists in an upper level node by the search engine, if a matched prefix exists in the upper level node, 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 step (C); or, if no matched prefix exists in the upper level node, executing step (C); (C) determining whether the TNODE has a child node according to a child bitmap, when a branch flag of the TNODE matches a corresponding bit of a search keyword, by the search engine; and (D) when the TNODE has no child node, reading an 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 by the search engine.