METHOD AND APPARATUS FOR PERFORMING RADIX LOOKUPS USING TRANSITION TABLES WITH POINTERS

A method, apparatus, and article of manufacture for performing a radix search tree lookup with a key using a transition table with pointers. The key is used as a transition index into the transition table. A first pointer associated with the transition index is then used as a pointer into a first block of entries in a result table. A sum of transition bits in the transition table below the transition 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.