Patent ID: 8356020

Claim:
A lookup apparatus comprising: a plurality of stride tables that form a multi-bit Trie structure for performing lookups, wherein the stride tables are arranged into a plurality of levels; a lookup input for receiving an input lookup key dividable into a plurality of strides, wherein the plurality of strides correspond to the plurality of levels, wherein at least one of the strides has multiple bits, wherein a stride is for locating an entry in a stride table at a level in the plurality of levels; a compressed stride table in the plurality of stride tables at a compressed level in the plurality of levels, wherein the compressed stride table is pointed to by a table pointer in a prior-level selected entry in a prior stride table at a prior level in the plurality of levels, the prior-level selected entry being selected by a prior stride; a plurality of valid entries in the compressed stride table, wherein a selected valid entry in the compressed stride table is selected with compressed index bits, the compressed index bits being fewer bits than a current stride in the plurality of strides, the current stride for the compressed stride table; an index compressor, receiving current stride bits from the lookup input for the current stride of the input lookup key, the index compressor logically combining the current stride bits to generate logically combined compressed index bits; wherein the index compressor comprises a processor or hardware gates; and pointer fields stored in the plurality of valid entries, the pointer fields containing pointers to stride tables in a next level in the plurality of levels or pointers to lookup results, whereby stride bits are logically combined to form the logically combined compressed index bits for the compressed stride table; wherein the multi-bit stride for a level L in the level of tables comprises S current stride bits; wherein the compressed index comprise D compressed index bits; wherein the stride table is in a compressed format having a reduced number of invalid and empty entries that are present in a full-size stride table having 2^s entries, wherein the stride table has 2^D entries locatable by the D compressed index bits that are compressed from the S current stride bits from the input key; whereby the stride table has 2^s−2D fewer entries than the full-size stride table that stores a same set of valid entries.