Method and apparatus for performing radix lookups using transition tables with pointers
US6233574A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 1, 1998 |
| Grant date | May 15, 2001 |
| Priority date | — |
| Expiry date | Jul 1, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.