Method and apparatus for performing radix lookups using valid bit tables with pointers

摘要

A method, apparatus, and article of manufacture for performing a radix search tree lookup with a key using a valid bit table with pointers. The key is used as a valid bit index into the valid bit table. A first pointer associated with the valid bit index is then used as a pointer into a first block of entries in a result table. A sum of valid bits in the valid bit table below the valid bit index is used as a result index into the first block of entries in the result table. The result index into the first block of entries may be used to reference a result of the radix search tree lookup. Extra space is added in the result table to enable insertion of entries after the first block of entries. A second pointer is used to add redundant entries from the first block of entries into a second block of entries in the result table.