Patent ID: 7290001

Claim:
A method for identifying trie data in a trie based on multiple tags, the trie including a header section containing a tag information field and a node section containing a plurality of nodes, each node containing a tag bit, the method comprising: receiving an input; determining a first value of the tag information field in the header; based on the first value, determining a second value of a tag bit in a node of the node section, the node corresponding to the input; based on the first value and the second value, identifying whether a tag mask field is present in the node, the tag mask field including a plurality of bits in the node wherein at least one bit in the plurality of bits of the tag mask field is set; if the tag mask field is present, identifying at least one set bit and a location of the at least one set bit in the plurality of bits of the tag mask field; generating trie data corresponding to the node based on the identified at least one set bit in the plurality of bits of the tag mask field; and outputting the generated trie data.