Patent ID: 7861291

Claim:
A computer-implemented method comprising: constructing, using a processor, one or more subtables in a first memory area accessible by the processor; reading, from a second memory area using the processor, a plurality of rules in order of increasing rule priority, wherein each of the rules includes one or more subkeys and one or more submasks; upon reading each of the plurality of rules, using the processor to add rule information to the subtables in a manner that stores rule information distinguishing the rule being added from every rule previously added with lower rule priorities, the adding of the rule information further comprising: identifying a range of indices in one of the subtables corresponding to one of the rule's subkeys and one of the rule's submasks; looping through a plurality of entries of the subtables, starting at a first entry, wherein the plurality of entries is indexed by the identified range of indices and for each of the entries, determining whether a set of a plurality of key bits corresponding to the rule have been exhausted, wherein the rule's key bits are the bits included in the rule's subkey; and in response to the rule's key bits being exhausted: decrementing a counter corresponding to a second subtable being addressed by the first entry; removing the second subtable in response to the decremented counter indicating that no entries address the second subtable; receiving, at a network adapter, an incoming packet that includes a plurality of fields and forming a key from the plurality of the fields, wherein the formed key includes a plurality of subkeys; and searching the entries stored in the subtables for one or more of the subkeys, wherein a different subtable is used to search for each of the subkeys; and wherein a next level subkey is selected and a next level subtable is searched when a pointer value is encountered in the previous level subtable.